Stochastic Smooth Convex Minimization
Descriptions may be stale. Consult the linked Lean sources.
Stochastic Smooth Convex Minimization
We consider minimizing a differentiable convex function
The optimization problem is
Our assumptions:
Assumption 1 (Convexity). For every
Assumption 2 (Smoothness). The function
Assumption 3 (Initial distance). There exists
Assumption 4 (Stochastic gradients). There exist a
probability measure
Queries may be made at any point of
Results
Convex differentiable
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) AcceleratedStochasticConvex (Ours) (review) | |||
| (2) SgdConvex (Ours) (review) | |||
| (3) AC-SA (Ghadimi and Lan 2012), Prop. 7, (4.10)–(4.11). Unconstrained Euclidean specialization. | (1): Matches known rate;
Lean formalization in Hilbert space of a dimension-free analysis.
(2): Matches when |
(2): At |
|
| (4) Smooth SGD (Bubeck 2015), Thm. 6.3 proof. Derived bound: unconstrained Euclidean quadratic mirror map. | (2): Matches known rate;
Lean formalization. Step omits |
||
| (5) AC-SA (Ghadimi and Lan
2012), Prop. 7, (4.5), (4.10)–(4.12). Bounded convex |
(1), (2): No established improvement for this probability target. Different domain and accuracy guarantees prevent direct rate comparison. | (1), (2): Expectation only; no corresponding high-probability guarantee. |
Abbr: Costs count individual stochastic-gradient
calls; in (5) each call also uses one projection.