Hidden Diagonal Curvature Minimization
Descriptions may be stale. Consult the linked Lean sources.
Hidden Diagonal Curvature Minimization
We consider minimizing a differentiable function
The optimization problem is
Our assumptions:
Assumption 1 (Diagonal curvature bounds). The
function
Assumption 2 (Initial objective gap). There exists
Queries may be made at any point of
Results
On
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) BlackBoxDiagonalAcceleration
(Ours) |
|||
| (2) Multidimensional backtracking, derived bound (Kunstner et al. 2023), Prop. 3.2, Thm. 5.3 | (1): leading accuracy
term saves |
(1): warm-up |
|
| (3) OSGM-R (Gao et al. 2025), Thm. 6.2 | (1): leading accuracy
term saves |
(1): dimension-dependent
warm-up; extra |
|
| (4) Centre of gravity, derived bound (Bubeck 2015), Sec. 2.1 | (1): no |
(1): worse oracle cost
when |
Abbr: