Finite-Variance Generalized Smooth Convex Minimization
Descriptions may be stale. Consult the linked Lean sources.
Finite-Variance Generalized Smooth Convex Minimization
We consider minimizing a convex function
The optimization problem is
Our assumptions:
Assumption 1 (Convexity and generalized smoothness).
The function
Assumption 2 (Initial distance and objective gap).
There exists
Assumption 3 (Finite-variance stochastic gradients).
There exist a probability measure
Queries may be made at any point of
Results
- Adaptive Robust Generalized Accelerated Convex · Lean proof
- Finite Variance Generalized Accelerated Convex · Lean proof
- Finite Variance Generalized Radius Accelerated Convex · Lean proof
Convex
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) AdaptiveRobustGeneralizedAcceleratedConvex
(Ours) |
For fixed |
||
| (2) FiniteVarianceGeneralizedAcceleratedConvex
(Ours) |
|||
| (3) RCSAG (Lobanov et al.
2026), Thm. 9, App. C; derived bound on |
(1): removes the (1), (2): for |
(1),
(2): require a Hessian bound and finite variance;
(3) permits first-order local smoothness, (1): worse for (2): extra noise and optimization logarithms. |
|
| (4) Clipped accelerated
mirror descent (Nguyen et al. 2023), Thm. 4.1;
special case |
(1): |
(1), (2)
need |
|
| (5) (Tyurin 2026),
Thm. 4.3; special case |
(2): at |
(2) pays |
|
| (6) FiniteVarianceGeneralizedRadiusAcceleratedConvex
(Ours) |
|||
| (7) Clip-SSTM (El Bakkali El Kadi
and Gorbunov 2026), Thm. 2, Remark 1; derived bound on |
(6): curvature |
(6): extra logarithmic
overhead and larger leading constant; covers only |
|
| (8) Clip-SSTM (El Bakkali El Kadi
and Gorbunov 2026), Thm. 2, Remark 2; derived radius-only bound
on |
(6): curvature |
(6): extra logarithmic
overhead and larger leading constant; excludes the |
|
| (9) Earlier repository bound (LongTails, n.d.); comparison with (2) on the identical setup. | (6): no |
(6): worse for small
known gaps; e.g. fixed |
|
| (10) Clipped SGD (Gaash et al.
2025), Thm. 1; derived bound on |
(6): |
(6): extra logarithmic factors on optimization terms. | |
| (11) (Rudomanov et al.
2026), Thm. 3.7; special case |
(6): extends the radius-only guarantee to finite-variance stochastic gradients; retains linear curvature dependence up to logarithms. | (6): at |
Abbr: