← All setups

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 f:E→R on a finite-dimensional real inner product space E, with a differentiable auxiliary function h:E→R. The objective is twice continuously differentiable with Lipschitz Hessian; both the auxiliary gradient and the gradient difference ∇f−∇h are Lipschitz. A given point x0∈E has bounded objective gap above the infimum. Two exact oracles return (f(x),∇f(x)) and (h(x),∇h(x)) at a query x∈E. For ε>0, the goal is an output x¯∈E satisfying ∥∇f(x¯)∥≤ε almost surely under P, the law of the algorithm’s randomness.

The optimization problem is infx∈Ef(x). The norm ∥⋅∥ is induced by the inner product on E, and ∥⋅∥op denotes the induced operator norm. The parameters satisfy L≥0,δ>0,ρ>0,Δ≥0,ε>0. The algorithm receives E, x0, L, δ, ρ, Δ, and ε.

Our assumptions:

Assumption 1 (Hessian regularity). The objective f is twice continuously Fréchet differentiable on E. Its Hessian, viewed as a linear operator from E to E, satisfies ∥∇2f(x)−∇2f(y)∥op≤ρ∥x−y∥,x,y∈E.

Assumption 2 (Auxiliary smoothness and similarity). The auxiliary function h is Fréchet differentiable on E. For every x,y∈E, ∥∇h(x)−∇h(y)∥≤L∥x−y∥,∥(∇f(x)−∇h(x))−(∇f(y)−∇h(y))∥≤δ∥x−y∥.

Assumption 3 (Initial objective gap). The given point x0 satisfies f(x0)−f(x)≤Δ,x∈E.

Both oracles accept queries at any point of E, and their calls are counted separately. After the allotted calls, the required accuracy is ∥∇f(x¯)∥≤εP-a.s.

Proved result

Oracle 0:(⌈219⋅Δ⋅ρ⋅εε2⌉++1)⋅((⌈6⋅1+δρ⋅ε⋅log⁡(8+8⋅δρ⋅ε)⌉++1)⋅(⌈15⋅log⁡(400⋅(1+L+δρ⋅ε))⌉++2)+6) Oracle 1:(⌈219⋅Δ⋅ρ⋅εε2⌉++1)⋅((⌈6⋅1+δρ⋅ε⋅log⁡(8+8⋅δρ⋅ε)⌉++1)⋅((⌈15⋅log⁡(400⋅(1+L+δρ⋅ε))⌉++1)⋅(⌈(Lδ+6)⋅log⁡(2110⋅(1+L+δρ⋅ε)10⋅(1+Δ⋅ρ⋅εε2))⌉++3)+1))

OracleTemplate.Convergence LongTails.Setups.AuxiliarySimilarityNonconvex.spec
  OracleTemplate.AuxiliarySimilarityAcceleration.budget

Relevant previous results

No qualifying prior reference verified; this is not a proof of novelty.