← All setups

Stochastic Composite Stationarity

Descriptions may be stale. Consult the linked Lean sources.

Stochastic Composite Stationarity

We consider minimizing F=f+ψ over a convex set Q in a finite-dimensional real inner product space E. The possibly nonconvex function f:E→R has an L-Lipschitz gradient and a ρ-Lipschitz Hessian, with L>0 and ρ≥0, while ψ:E→R is convex on Q. A given x0∈Q has objective gap at most Δ≥0. The oracle returns unbiased stochastic gradients with variance at most σ2, σ≥0, from independent identically distributed samples, or exact proximal minimizers Ta(z,v) of ∥u−z∥2/(2a)+⟨v,u−z⟩+ψ(u) over u∈Q, for a>0 and z,v∈E. For ε>0, the goal is a feasible output x¯ with E∥L(x¯−T1/L(x¯,∇f(x¯)))∥≤ε.

The optimization problem is minx∈QF(x),F(x):=f(x)+ψ(x). The norm is induced by the inner product on E; operator norms below are the induced operator norms. The algorithm receives E, the measurable sample space Ω, L, ρ, σ, Δ, ε, and x0, and accesses the objective through the oracle described below.

Our assumptions:

Assumption 1 (Gradient and Hessian regularity). The function f is Fréchet differentiable on E, its gradient is Fréchet differentiable on E, and, for every x,y∈E, ∥∇f(x)−∇f(y)∥≤L∥x−y∥,∥∇2f(x)−∇2f(y)∥op≤ρ∥x−y∥. Here ∇2f(x) is a linear operator from E to E.

Assumption 2 (Convex composite term and proximal access). The set Q⊆E is convex, and, for every x,y∈Q and t∈[0,1], ψ((1−t)x+ty)≤(1−t)ψ(x)+tψ(y). For every a>0 and z,v∈E, the exact proximal reply satisfies Ta(z,v)∈Q,Ta(z,v)∈argminu∈Q{∥u−z∥22a+⟨v,u−z⟩+ψ(u)}. The map on R×E×E equal to Ta(z,v) when a>0 and to 0 otherwise is measurable.

Assumption 3 (Initial objective gap). The given starting point and gap bound satisfy x0∈Q,F(x0)−F(x)≤Δfor every x∈Q.

Assumption 4 (Stochastic gradient access). There is a probability measure μ on Ω and a jointly measurable map g:E×Ω→E. For each x∈E, the random vector g(x,ξ) is Bochner integrable and ∥g(x,ξ)−∇f(x)∥2 is integrable under ξ∼μ, with Eξ∼μ[g(x,ξ)]=∇f(x),Eξ∼μ∥g(x,ξ)−∇f(x)∥2≤σ2. The oracle samples form a measurable, mutually independent sequence (ξk)k≥0 with common law μ, under a joint probability law P on ΩN. This sequence is independent of the algorithm’s internal randomness. At call k, a gradient query at any x∈E returns g(x,ξk); a proximal query returns Ta(z,v) exactly. Each query of either type counts as one oracle call in a common budget. Proximal queries may use any real a, although the minimization and measurability conditions above concern positive a.

Define the composite gradient mapping by GL(x):=L(x−T1/L(x,∇f(x))). After the allotted oracle calls, the output x¯ must be measurable, its residual norm ∥GL(x¯)∥ must be integrable, and it must satisfy x¯∈QP-a.s.,EP[∥GL(x¯)∥]≤ε, where P is the joint law of the algorithm’s internal randomness and the independent oracle sample sequence.

Results

On a finite-dimensional real inner-product space, minimize F=f+ψ on convex Q, with x0∈Q, F(x0)−infQF≤Δ, convex ψ on Q, and measurable exact proximal evaluations. Globally, ∇f is L-Lipschitz and ∇2f is ρ-Lipschitz. The jointly measurable IID oracle is unbiased with integrable gradients and centered second moment at most σ2. Here L,ε>0 and ρ,σ,Δ≥0. Target: a measurable feasible output with ∫∥GL(xτ(ω))∥dP(ω)≤ε; P includes sampling and output randomization.

Comparison for StochasticCompositeHessianLipschitz.
Result Oracle complexity Novelty Limitations
(1) CompositeImplicitTransport (Ours) (⋆⋆⋆) (review) O(1+LΔε2+ρΔε3/2+σ2ρΔε7/2+σ2ε2) gradient plus prox calls, including initialization.
(2) Proximal momentum SGD (Gao et al. 2024), Theorem 4, initialization in Section 5.2 O(1+LΔσ2ε4+LΔε2+σ2LΔ) gradient plus prox calls; Δ>0, including initial batch. (1): noise term smaller by L/ρε when ρε≪L2; total gain when noise dominates, σ≳ε, and initialization does not dominate. (1) needs global Hessian regularity and known ρ; noise term worsens if ρε>L2. Loses squared subgradient stationarity.
(3) NIGT (Cutkosky and Mehta 2020), Theorem 3 O(1+LΔε2+ρΔσ2ε7/2+σ13/3Δ4/3ρ2/3ε7/3) gradient calls; ψ=0, Q=E, Δ,ρ,σ>0. (1): Scope extends to convex composite penalties and constrained, possibly unbounded Q. Matches leading deterministic and noise terms on the overlap. (1): remaining terms incomparable. On ψ=0, Q=E, the prox is a closed-form update.

Abbr: proxa(x,v)=arg⁡minu∈Q{∥u−x∥2/(2a)+⟨v,u−x⟩+ψ(u)}; GL(x)=L(x−prox1/L(x,∇f(x))); Δ is the initial objective-gap bound, σ2 the variance bound. Costs count every stochastic gradient and exact prox call. (1) uses known L,ρ,σ,Δ,ε and a uniformly random iterate.

Cutkosky, Ashok, and Harsh Mehta. 2020. “Momentum Improves Normalized SGD.” Proceedings of the 37th International Conference on Machine Learning, Proceedings of machine learning research, vol. 119: 2260–68. https://proceedings.mlr.press/v119/cutkosky20b.html.
Gao, Yuan, Anton Rodomanov, and Sebastian U. Stich. 2024. Non-Convex Stochastic Composite Optimization with Polyak Momentum. https://doi.org/10.48550/arXiv.2403.02967.

Lean setup