Convex Minimization with Hidden Smoothness
Descriptions may be stale. Consult the linked Lean sources.
Convex Minimization with Hidden Smoothness
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 and objective gap).
There exists
Queries may be made at any point of
Results
Convex
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) BacktrackingGeneralizedAccelerated
(Ours) |
|||
| (2) Accelerated GRAAL
(Borodich
and Kovalev 2025, Cor. 3, v2). Restriction: |
(1): for Example: |
(1): backtracking incurs constant-factor overhead. | |
| (3) AGD (Tyurin 2026, Thm. 4.3,
v2). Restriction: |
(1): removes |
(1): possible |
|
| (4) AGMsDR (Vankov et al. 2025,
Thm. 6.2, v3). Restriction: |
(1): no |
(1) loses the |
Abbr: