Smooth Convex Minimization
Descriptions may be stale. Consult the linked Lean sources.
Smooth Convex Minimization
We consider minimizing a differentiable convex function
The optimization problem is
Our assumptions:
Assumption 1 (Convexity). For every
Assumption 2 (Smoothness). The function
Assumption 3 (Initial distance). There exists
Queries may be made at any point of
Results
A convex differentiable
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) AcceleratedConvex (Ours) (review) | |||
| (2) GdConvex (Ours) (review) | |||
| (3) Nesterov AGD (d’Aspremont et al. 2021, Cor. 4.9) | (1): Matches known rate; Lean formalization. The dimension-free argument extends to Hilbert spaces. | (2): For |
|
| (4) OGM (d’Aspremont et al. 2021, Cor. 4.6) | (1): Matches known order
on |
(1): About |
|
| (5) Classical GD (Drori and Teboulle 2012, Eq. (3.1)) | (1): Known acceleration
gives |
||
| (6) Tight GD (Drori and Teboulle 2012, Thms. 3.1–3.2) | (2): Matches known order
on |
(2): About twice as many
calls when |
|
| (7) FISTA (Beck and Teboulle 2009, Thm. 4.4) | (1): Matches known rate
at |
(1): Up to one extra call
at |
Abbr: Costs count exact gradient evaluations.