Diagonal Smooth Strongly Convex Minimization
Descriptions may be stale. Consult the linked Lean sources.
Diagonal Smooth Strongly Convex Minimization
We consider minimizing a differentiable function
The optimization problem is
Our assumptions:
Assumption 1 (Diagonal smoothness and strong
convexity). The function
Assumption 2 (Attained minimum and initial gap).
There exists
Queries may be made at any point of
Results
Differentiable
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) OnlineMetricAccelerated
(Ours) |
|||
| (2) Derived bound: secant diagonal + restarted AGD (Roulet and d’Aspremont 2019, Prop. 4.1) | (1): |
(1): larger warm-up at
moderate accuracy or large |
|
| (3) Ellipsoid multidimensional backtracking (Kunstner et al. 2023, Thm. 5.3, Prop. 3.2) | (1): leading coefficient
|
(1) needs |
|
| (4) Lookahead OSGM-R (Gao et al. 2025, Eq. (5), Thms. 6.1–6.2) | (1): |
(1) can lose when
full-matrix scaling gives |
|
| (5) Euclidean AGD + known-value restarts (Roulet and d’Aspremont 2019, Prop. 4.1) | (1): gain for |
(1) pays |
Abbr: