Nonconvex Optimization with Auxiliary Similarity
Descriptions may be stale. Consult the linked Lean sources.
Nonconvex Optimization with Auxiliary Similarity
We consider minimizing a possibly nonconvex function
The optimization problem is
Our assumptions:
Assumption 1 (Hessian regularity). The objective
Assumption 2 (Auxiliary smoothness and similarity).
The auxiliary function
Assumption 3 (Initial objective gap). The given
point
Both oracles accept queries at any point of
Results
On a finite-dimensional real inner-product space,
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) AuxiliarySimilarityAcceleration
(Ours) |
|||
| (2) AuxMOM (Chayti and Karimireddy 2025), Sec. 4.2, noiseless | (1): fewer |
(1) needs Hessian
Lipschitzness and |
|
| (3) Restarted AGD (Li and Lin 2023), Thm. 1 | (1): for |
(1) needs helper calls
and |
Abbr: