Auxiliary Similarity Acceleration — Nonconvex Optimization with Auxiliary Similarity
Descriptions may be stale. Consult the linked Lean sources.
Nonconvex Optimization with Auxiliary Similarity · Lean proof
Nonconvex
Optimization with Auxiliary Similarity
We consider minimizing a possibly nonconvex function on a finite-dimensional
real inner product space , with a
differentiable auxiliary function . The objective is twice
continuously differentiable with Lipschitz Hessian; both the auxiliary
gradient and the gradient difference are Lipschitz. A given point has bounded objective gap above
the infimum. Two exact oracles return and at a query . For , the goal is an output
satisfying
almost surely under , the law of
the algorithm’s randomness.
The optimization problem is The norm is induced by the inner product
on , and denotes the
induced operator norm. The parameters satisfy The algorithm receives
, , , , , , and .
Our assumptions:
Assumption 1 (Hessian regularity). The objective
is twice continuously Fréchet
differentiable on . Its Hessian,
viewed as a linear operator from
to , satisfies
Assumption 2 (Auxiliary smoothness and similarity).
The auxiliary function is Fréchet
differentiable on . For every
,
Assumption 3 (Initial objective gap). The given
point satisfies
Both oracles accept queries at any point of , and their calls are counted
separately. After the allotted calls, the required accuracy is
Proved result
OracleTemplate.Convergence LongTails.Setups.AuxiliarySimilarityNonconvex.spec
OracleTemplate.AuxiliarySimilarityAcceleration.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.