← All setups

Stochastic Generalized Lipschitz Convex Minimization

Descriptions may be stale. Consult the linked Lean sources.

Stochastic Generalized Lipschitz Convex Minimization

We consider minimizing a continuous convex function f:E→R on a separable real Hilbert space E. A given point x0∈E satisfies ∥x0−x⋆∥≤R, where R>0 and x⋆ is a global minimizer. At x∈E, the oracle returns a random vector whose mean is a subgradient of f. Each reply decomposes into a component with second moment at most G02 and a component bounded almost surely in norm by G1(f(x)−f(x⋆)), where G0>0 and G1≥0. Samples are independent and identically distributed. For ε>0, the goal is a measurable output x¯∈E satisfying f(x¯)−f(x⋆)≤ε with probability at least 9/10.

The optimization problem is minx∈Ef(x). Write ⟨⋅,⋅⟩ for the inner product and ∥⋅∥ for its induced norm. The algorithm receives E, x0, R, G0, G1, and ε; the objective and sampling distribution are accessed through the oracle.

Our assumptions:

Assumption 1 (Convexity and initial distance). The function f is continuous, and for every x,y∈E and t∈[0,1], f((1−t)x+ty)≤(1−t)f(x)+tf(y). There exists a fixed x⋆∈E such that f(x⋆)≤f(x)for every x∈E,∥x0−x⋆∥≤R.

Assumption 2 (Stochastic subgradient oracle). Let Ω be a measurable space, let ν be a probability measure on Ω, and let g:E×Ω→E be jointly measurable. For every x∈E, the map g(x,⋅) is Bochner integrable under ν, and f(x)−f(y)≤⟨Eξ∼ν[g(x,ξ)],x−y⟩,x,y∈E. At call k=0,1,…, a query x∈E receives g(x,ξk). The random variables (ξk)k≥0 are measurable, mutually independent, and each has law ν. Algorithm randomness is independent of this sample sequence.

Assumption 3 (Generalized moment bound). For every x∈E, there exist measurable maps ux,vx:Ω→E such that ∥ux(⋅)∥2 is integrable under ν and g(x,ξ)=ux(ξ)+vx(ξ)ν-a.s.,Eξ∼ν[∥ux(ξ)∥2]≤G02,∥vx(ξ)∥≤G1(f(x)−f(x⋆))ν-a.s.

After the allotted oracle calls, the algorithm must return a measurable output x¯∈E satisfying P(f(x¯)−f(x⋆)>ε)≤110, where P is the joint law of the algorithm’s randomness and the oracle sample sequence.

Results

Continuous convex f on a second-countable real Hilbert space with its Borel structure; a minimizer x⋆ satisfies ∥x0−x⋆∥≤R. Here R,G0,ε>0 and G1≥0. IID samples have law p and joint law P. The jointly measurable, integrable oracle g has mean in ∂f(x) and a measurable decomposition g=u+v with ∫∥u∥2dp≤G02 and ∥v∥≤G1(f(x)−f(x⋆)) almost surely. Target: P{f(x^)−f(x⋆)>ε}≤1/10.

Stochastic generalized Lipschitz convex optimization: StochasticGeneralizedLipschitzConvex.
Result Oracle complexity Novelty Limitations
(1) StochasticGeneralizedLipschitzConvex (Ours) (⋆⋆⋆) (review) O((κ3+κ2b+b2)ℓ3)
(2) Clipped AdamW (Kovalev 2026), Thm. 7, Cor. 4 O(κ3log⁡(e+FG1/G0)
+(κ3+κ2b+b2)log⁡(e+b/κ)). For RG1≥1; finite-dimensional setting; Markov conversion.
(1): Worst-case localization κ4→κ3ℓ3. Total gain when κ≫ℓ3, b≪κ2/ℓ3; at b=κ, O(κ4)→O(κ3log3⁡κ). (1): No expected-gap guarantee; larger constant. Extra logarithms lose for b≳κ2; no assured gain when log⁡(e+FG1/G0)≲ℓ3.
(3) SGD / AdaGrad-Norm (Kovalev 2026), Thms. 3–4 O(1+exp⁡(O(RG1))b+b2). Finite-dimensional setting; Markov conversion. (1): Polynomial instead of exponential dependence on RG1; improves the growth-dominated regime. (1): No expected-gap guarantee; extra logarithms in the accuracy term.
(4) Classical SGD (Nemirovski et al. 2009), Eq. (2.21) O(1+b2). Special case G1=0, finite dimension; projection onto the known R-ball; Markov conversion. (1): No established improvement on this restriction. (1): Extra log3⁡(2+b) factor; no expected-gap guarantee.

Abbr: κ=1+RG1, b=RG0/ε, ℓ=log⁡(2+κ+b); F=sup∥x−x0∥≤R(f(x)−f(x⋆)). Costs count all sampled oracle calls, including batches in (1). Markov conversion means tuning the expected gap to ε/10. (1) uses R,G0,G1,ε as tuning inputs.

Kovalev, Dmitry. 2026. Stochastic Non-Smooth Convex Optimization with Unbounded Gradients. https://doi.org/10.48550/arXiv.2605.15522.
Nemirovski, Arkadi, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. 2009. “Robust Stochastic Approximation Approach to Stochastic Programming.” SIAM Journal on Optimization 19 (4): 1574–609. https://doi.org/10.1137/070704277.

Lean setup