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
The optimization problem is
Our assumptions:
Assumption 1 (Convexity and initial distance). The
function
Assumption 2 (Stochastic subgradient oracle). Let
Assumption 3 (Generalized moment bound). For every
After the allotted oracle calls, the algorithm must return a
measurable output
Results
Continuous convex
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) StochasticGeneralizedLipschitzConvex
(Ours) |
|||
| (2) Clipped AdamW (Kovalev 2026), Thm. 7, Cor. 4 | (1): Worst-case
localization |
(1): No expected-gap
guarantee; larger constant. Extra logarithms lose for |
|
| (3) SGD / AdaGrad-Norm (Kovalev 2026), Thms. 3–4 | (1): Polynomial instead
of exponential dependence on |
(1): No expected-gap guarantee; extra logarithms in the accuracy term. | |
| (4) Classical SGD (Nemirovski et al. 2009), Eq. (2.21) | (1): No established improvement on this restriction. | (1): Extra |
Abbr: