← All setups

Euclidean Strong-Growth Stochastic Minimization

Descriptions may be stale. Consult the linked Lean sources.

Euclidean Strong-Growth Stochastic Minimization

We consider minimizing a differentiable convex function f:Rd→R, where d is a positive integer. A given point x0∈Rd lies within distance R>0 of a global minimizer x⋆. The stochastic gradient is unbiased, is Lipschitz in mean square with constant L¯>0, and has variance bounded by Γ2∥∇f(x)∥2 at each x, where Γ≥0. Each oracle call returns gradients at two queried points using a shared sample, with independent, identically distributed samples across calls. For ε>0, the goal is a measurable output x¯∈Rd with integrable objective gap satisfying EP[f(x¯)−f(x⋆)]≤ε, where P is the law of the algorithm’s and oracle’s randomness.

The optimization problem is minx∈Rdf(x), where ∥⋅∥ denotes the Euclidean norm. The parameters satisfy L¯>0,Γ≥0,R>0,ε>0,671088641+Γ2ε≤L¯R2,(L¯R21+Γ2ε)3≤d. Let Ω be a measurable sample space containing distinct points a,b whose singletons are measurable. The algorithm receives d, Ω with its measurable structure, L¯, Γ, R, ε, and x0; the objective and the oracle distribution are accessed through oracle replies.

Our assumptions:

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

Assumption 2 (Unbiasedness and strong growth). There exist a probability measure ν on Ω and a jointly measurable map g:Rd×Ω→Rd. For every x∈Rd, the map g(x,⋅) is Bochner integrable, the squared error ∥g(x,⋅)−∇f(x)∥2 is integrable, and Eξ∼ν[g(x,ξ)]=∇f(x),Eξ∼ν[∥g(x,ξ)−∇f(x)∥2]≤Γ2∥∇f(x)∥2.

Assumption 3 (Mean-square smoothness and paired sampling). For every x,y∈Rd, the squared difference ∥g(x,⋅)−g(y,⋅)∥2 is integrable and satisfies Eξ∼ν[∥g(x,ξ)−g(y,ξ)∥2]≤L¯2∥x−y∥2. The oracle uses a sequence (ξk)k≥0 of measurable, independent random variables, each with law ν, independent of the algorithm’s randomness. At call k, a query (xk,yk)∈Rd×Rd returns (g(xk,ξk), g(yk,ξk)). Both components use the same sample, and the pair counts as one oracle call.

Queries may be chosen adaptively anywhere in Rd×Rd. After the allotted paired oracle calls, the output x¯ must be measurable, its objective gap must be integrable under P, and it must satisfy EP[f(x¯)−f(x⋆)]≤ε.

Results

Convex differentiable f:Rd→R has a minimizer x⋆ with ∥x0−x⋆∥≤R. Each call returns (g(x,ξ),g(y,ξ)) with fresh IID ξ∼p. The jointly measurable oracle satisfies ∫g(x,ξ)dp=∇f(x), ∫∥g(x,ξ)−∇f(x)∥2dp≤Γ2∥∇f(x)∥2, and ∫∥g(x,ξ)−g(y,ξ)∥2dp≤L¯2∥x−y∥2, with the corresponding integrability assumptions. Here L¯,R,ε>0, Γ≥0, 2261+Γ2ε≤L¯R2, d≥[L¯R2/(1+Γ2ε)]3, and the sample space contains two distinct measurable singletons. Target: measurable output with integrable gap ∫[f(x^)−f(x⋆)]dP≤ε, where P is the execution law. No algorithm family is imposed.

Sufficient and necessary budgets for EuclideanStrongGrowthMeanSquared: a logarithmic upper/lower gap.
Result Oracle complexity Novelty Limitations
(1) StrongGrowthMeanSquaredLowerBound (Ours) (review) Ω((1+Γ2)3/4L¯R2/ε) pair calls necessary; hardness for every randomized adaptive algorithm, at every budget up to the proved threshold.
(2) StrongGrowthMeanSquaredUpperBound (Ours) (review) O((1+Γ)3/2ℓL¯R2/ε) pair calls, including all inner solves and batches; ProximalStorm last outer iterate.
(3) Exact smooth-convex oracle (Novoselov et al. 2026), Lemma A.9 Ω(L¯R2/ε) exact-gradient calls; deterministic-oracle special case, randomized algorithms. d≳N2. Two gradients simulate one pair call. (1): necessary budget larger by (1+Γ2)3/4; strict order gain for Γ≫1, same order for bounded Γ. (1): requires the stated noise-dependent accuracy regime.
(4) Derived bound (Novoselov et al. 2026), Theorem A.10, m=1 Ω((1+Γ2)3/4L¯R2/ε) on masked quadratics: ρ=1+Γ2, Hs=ρL, L¯=ρL. Fresh single-point bound transfers to pairs at constant cost; d≳N2. (1): matches necessary rate; explicitly states the mean-squared-smooth pair-oracle guarantee. The oracle classes overlap through masking.
(5) ProximalStorm (LongTails 2026) O([(1+Γ)3/2L¯R2/ε+(1+Γ)2]ℓ) pair calls; the initialization term is dominated on the target domain. (2): matches known rate and identical numerical budget. Against (1), the remaining gap is ℓ on the shared domain. (2): narrower scope: Euclidean space, large d, small ε, R>0, and two measurable singletons.
(6) Accelerated SGD (Vaswani et al. 2019), Theorem 2; AGNES (Gupta et al. 2024), Theorem 3 O(1+(1+Γ2)LR2/ε) fresh single-point gradients; L-smooth objective and strong growth, without mean-squared smoothness. (2): inherited cost saving ≍ΓL/L¯/ℓ for Γ≫1 and L¯≪ΓL/ℓ2. (2): needs mean-squared smoothness and same-sample pairs; logarithmic loss at L¯≍ΓL.

Abbr: ℓ=1+log⁡(1+Γ); L≤L¯ is an objective-gradient Lipschitz constant; ρ is the second-moment growth factor; Hs is sample-gradient smoothness; N counts calls. Pair calls return two same-sample gradients; a single-point query is available by repeating its point. Ω denotes a necessary lower bound; O denotes a sufficient upper bound, up to universal constants.

Gupta, Kanan, Jonathan W. Siegel, and Stephan Wojtowytsch. 2024. Nesterov Acceleration Despite Very Noisy Gradients. https://doi.org/10.48550/arXiv.2302.05515.
LongTails: ProximalStormStrongGrowth. 2026. Repository convergence theorem and oracle budget, commit 8102682315586237df316aef7ac0ea05d02bf755. https://github.com/k3nfalt/longtails/blob/8102682315586237df316aef7ac0ea05d02bf755/LongTails/Theorems/ProximalStormStrongGrowth.lean.
Novoselov, Kirill, Yuriy Dorn, Darina Dvinskikh, and Alexander Gasnikov. 2026. The Minimax Complexity of Federated Optimization Under Interpolation: The Role of Oracle Models. https://doi.org/10.48550/arXiv.2610.38354.
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