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 (Initial distance). There exists
Queries may be made at any point of
Results
Convex
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) FullGeneralizedSmoothConvexLowerBound
(Ours) |
Lower bound: |
||
| (2) (Rudomanov et al. 2026a), Thm. 4.10 | Lower bound: |
(1): Scope: randomized instead of deterministic hardness for expected accuracy, retaining arbitrary queries and outputs. | (1): Initialization term
is weaker by |
| (3) Classical smooth
lower bound (Garg et
al. 2021), Secs. 1–2; |
Lower bound: |
(1): Scope: extends to
|
(1): Gradient-only hardness. Ball-domain and unrestricted-query models differ; full oracle-complexity bounds are not directly comparable. |
| (4) (Rudomanov et al. 2026b), Thm. 7.1; finite sums | Lower bound: |
(1): Single-function
randomized hardness at fixed budgets. Rates not comparable: no
established |
Abbr: