Generalized Smooth Convex Minimization
Descriptions may be stale. Consult the linked Lean sources.
Generalized Smooth Convex Minimization
We consider minimizing a convex function
The optimization problem is
Our assumptions:
Assumption 1 (Convexity). For every
Assumption 2 (Generalized smoothness). The function
Assumption 3 (Minimizer and initialization). There
exists
Queries may be made at any point of
Results
Convex
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) GeneralizedSelfNormalizedConvex
(Ours) |
|||
| (2) GeneralizedAcceleratedConvex
(Ours) |
|||
(3) AGD (Tyurin 2026, Theorem 4.3, v2) |
(1): for (2): |
(2): startup can be
worse when (1), (2): two gradients per iteration instead of one; restricted to full domains. |
|
(4) AGMsDR (Vankov et al. 2025, Theorem 6.2, v3) |
(1): startup (2): matches iteration rate. (1), (2): bounded gradient-only
cost; no values or exact search. Total-call rates are not comparable
with unbounded |
(1),
(2): need |
|
(5) Accelerated GRAAL (Borodich and Kovalev 2025, Corollary 3, v2) |
(1),
(2): no values. For (2): startup |
(1),
(2): need |
Abbr: