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
The optimization problem is
Our assumptions:
Assumption 1 (Convexity and initial distance). The
function
Assumption 2 (Unbiasedness and strong growth). There
exist a probability measure
Assumption 3 (Mean-square smoothness and paired
sampling). For every
Queries may be chosen adaptively anywhere in
Results
- Strong Growth Mean Squared Lower Bound · Lean proof
- Strong Growth Mean Squared Upper Bound · Lean proof
Convex differentiable
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) StrongGrowthMeanSquaredLowerBound (Ours) (review) | |||
| (2) StrongGrowthMeanSquaredUpperBound (Ours) (review) | |||
| (3) Exact smooth-convex oracle (Novoselov et al. 2026), Lemma A.9 | (1): necessary budget
larger by |
(1): requires the stated noise-dependent accuracy regime. | |
| (4) Derived bound (Novoselov et al.
2026), Theorem A.10, |
(1): matches necessary rate; explicitly states the mean-squared-smooth pair-oracle guarantee. The oracle classes overlap through masking. | ||
| (5) ProximalStorm (LongTails 2026) | (2): matches known rate
and identical numerical budget. Against (1), the
remaining gap is |
(2): narrower scope:
Euclidean space, large |
|
| (6) Accelerated SGD (Vaswani et al. 2019), Theorem 2; AGNES (Gupta et al. 2024), Theorem 3 | (2): inherited cost
saving |
(2): needs mean-squared
smoothness and same-sample pairs; logarithmic loss at |
Abbr: