← All setups

Strong-Growth Mean-Square Smooth Convex Minimization

Descriptions may be stale. Consult the linked Lean sources.

Strong-Growth Mean-Square Smooth Convex Minimization

We consider minimizing a differentiable convex function f:E→R on a separable real Hilbert space E. A given point x0∈E lies within distance R≥0 of a global minimizer x⋆. The oracle returns (g(x,ξ),g(y,ξ)) at a pair (x,y)∈E2, using a shared sample ξ from a probability law p on a measurable space Ω, independently across calls. The estimator g:E×Ω→E is unbiased, with variance bounded by Γ2∥∇f(x)∥2, where Γ≥0, and is mean-square Lipschitz with constant L¯>0. For ε>0, the goal is a measurable output x¯∈E with integrable objective gap satisfying E[f(x¯)−f(x⋆)]≤ε, averaging over oracle and algorithm randomness.

The optimization problem is minx∈Ef(x). The norm ∥⋅∥ is induced by the inner product on E, which is equipped with its Borel sigma-algebra. The algorithm receives E, Ω, L¯, Γ, R, ε, and x0; the objective is accessed through the oracle.

Our assumptions:

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

Assumption 2 (Unbiasedness and strong growth). The map g:E×Ω→E is jointly measurable. For every x∈E, g(x,⋅) is Bochner integrable under p, the squared error ∥g(x,⋅)−∇f(x)∥2 is integrable, and Eξ∼p[g(x,ξ)]=∇f(x),Eξ∼p[∥g(x,ξ)−∇f(x)∥2]≤Γ2∥∇f(x)∥2.

Assumption 3 (Mean-square smoothness). For every x,y∈E, the squared difference ∥g(x,⋅)−g(y,⋅)∥2 is integrable under p, and Eξ∼p[∥g(x,ξ)−g(y,ξ)∥2]≤L¯2∥x−y∥2.

More precisely, the oracle samples form a sequence (ξk)k≥0 of measurable, mutually independent random variables, each with law p. Algorithm randomness is independent of this sequence. At call k, the algorithm may query any pair (x,y)∈E×E and receives (g(x,ξk),g(y,ξk)). Each paired reply counts as one oracle call; both components use the same sample.

After the allotted oracle calls, the output x¯ must be measurable, its objective gap f(x¯)−f(x⋆) must be integrable, and EP[f(x¯)−f(x⋆)]≤ε, where P is the joint law of the algorithm randomness and the oracle sample sequence.

Results

Convex differentiable f on a second-countable real Hilbert space with its Borel σ-algebra; a minimizer x⋆ satisfies ∥x0−x⋆∥≤R. For L¯,ε>0 and Γ,R≥0, a jointly measurable oracle with the stated moments integrable satisfies Epg(x,ξ)=∇f(x), Ep∥g(x,ξ)−∇f(x)∥2≤Γ2∥∇f(x)∥2, and Ep∥g(x,ξ)−g(y,ξ)∥2≤L¯2∥x−y∥2. Each query returns a same-sample pair, with fresh IID samples of law p under P. Target: measurable output y with integrable gap and ∫[f(y(ω))−f(x⋆)]dP(ω)≤ε.

Strong growth with mean-squared smoothness: StrongGrowthMeanSquaredSmoothConvex.
Result Oracle complexity Novelty Limitations
(1) ProximalStormStrongGrowth (Ours) (⋆⋆⋆) (review) O((1+Γ)3/2ℓL¯R2/ε+(1+Γ)2ℓ) pair calls, including batches and warm-up; two gradient evaluations per pair.
(2) Accelerated SGD (Vaswani et al. 2019, Thm. 2); AGNES (Gupta et al. 2024, Thm. 3) O(1+(1+Γ2)LR2/ε) single-point stochastic gradients. On Rd; L may be replaced by the public bound L¯. (1): Rate: Γ3/2ℓL¯ instead of Γ2L for large Γ. Lower total cost if L¯≪ΓL/ℓ2 and ε≪LR2/ℓ2.
With L=L¯ tuning: factor Γ/ℓ for ε≲L¯R2/Γ.
(1) needs MSS and same-sample pairs; adds (1+Γ)2ℓ overhead. At L¯≍ΓL, loses a logarithmic factor and the additive term. Larger proved constants.
(3) Derived bound (Jain et al. 2018, Thm. 1) O(κκ~[1+log(1+κκ~dLR2ε)]) single-point stochastic gradients. Realizable least squares on Rd, H≻0, finite fourth moments. (1): Scope extends from strongly convex quadratics to convex nonquadratic objectives, without a PL condition. (1) loses linear convergence on this overlap: ε−1/2 instead of logarithmic accuracy dependence.

Abbr: MSS: mean-squared smoothness; PL: Polyak–Łojasiewicz; ℓ=1+log⁡(1+Γ); L≤L¯: gradient Lipschitz constant of f; R: initial-distance bound; Γ: relative-noise level. In (3), f(x)=12E(a⊤x−b)2, b=a⊤x⋆ almost surely, d=dim⁡x, H=Eaa⊤=∇2f, L=λmax(H), κ=C4/λmin(H); C4 and κ~ are the least constants satisfying E[∥a∥2aa⊤]⪯C4H and E[(a⊤H−1a)aa⊤]⪯κ~H. The initial gap obeys f(x0)−f(x⋆)≤LR2/2.

Gupta, Kanan, Jonathan W. Siegel, and Stephan Wojtowytsch. 2024. Nesterov Acceleration Despite Very Noisy Gradients. https://doi.org/10.48550/arXiv.2302.05515.
Jain, Prateek, Sham M. Kakade, Rahul Kidambi, Praneeth Netrapalli, and Aaron Sidford. 2018. “Accelerating Stochastic Gradient Descent for Least Squares Regression.” In Proceedings of the 31st Conference on Learning Theory, edited by Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet, vol. 75. Proceedings of Machine Learning Research. PMLR. https://proceedings.mlr.press/v75/jain18a.html.
Vaswani, Sharan, Francis Bach, and Mark Schmidt. 2019. “Fast and Faster Convergence of SGD for over-Parameterized Models and an Accelerated Perceptron.” In Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, edited by Kamalika Chaudhuri and Masashi Sugiyama, vol. 89. Proceedings of Machine Learning Research. PMLR. https://proceedings.mlr.press/v89/vaswani19a.html.

Lean setup