← All setups

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 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.

Results

On a finite-dimensional real inner-product space, f∈C2, h is differentiable, ∇2f is ρ-Lipschitz, ∇h is L-Lipschitz, and ∇(f−h) is δ-Lipschitz. Assume f(x0)−f(x)≤Δ for every x, L,Δ≥0, and δ,ρ,ε>0. Exact oracles return (f,∇f) and (h,∇h). The target is a returned point x^ with ∥∇f(x^)∥≤ε almost surely; (1) is deterministic.

Nonconvex optimization with auxiliary similarity: AuxiliarySimilarityNonconvex.
Result Oracle complexity Novelty Limitations
(1) AuxiliarySimilarityAcceleration (Ours) (⋆⋆⋆) (review) Nf=O((1+A)1+δ/sℓδℓL);
Nh=O(Nf(1+L/δ)
⋅[ℓL+log⁡(1+A)])
(2) AuxMOM (Chayti and Karimireddy 2025), Sec. 4.2, noiseless Nf=O(1+δΔ/ε2);
Nh=O((1+L/δ)Nf). Random output: E∥∇f(x^)∥2≤ε2.
(1): fewer f calls when A≥1 and δ/s≫(ℓδℓL)2; gain δ/s/(ℓδℓL). For ρ=Δ=δ=1, L=ε−1/2: O(ε−7/4log2⁡(1/ε)) versus O(ε−2) f calls. (1) needs Hessian Lipschitzness and ρ,Δ; extra helper logarithms and larger constants. Worse f cost when δ≲s.
(3) Restarted AGD (Li and Lin 2023), Thm. 1 Nf=O(1+L+δρ1/4Δε−7/4), Nh=0; ε≲(L+δ)2/ρ. (1): for A≥1, δ≥s, replaces L+δ by δℓδℓL; gains when L≫δ(ℓδℓL)2. The example in (2) also improves (3)’s O(ε−2) f calls. (1) needs helper calls and Δ; loses logarithmic factors when L≲δ.

Abbr: Nf,Nh: respective total oracle calls (gradient calls for prior work); s=ρε, A=Δρε−3/2, ℓδ=log⁡(2+δ/s), ℓL=log⁡(2+(L+δ)/s). In the Nh formulas, Nf denotes its displayed upper-bound expression. ≲ hides universal constants; ≫ denotes asymptotic separation.

Chayti, El Mahdi, and Sai Praneeth Karimireddy. 2025. Optimization with Access to Auxiliary Information. https://doi.org/10.48550/arXiv.2206.00395.
Li, Huan, and Zhouchen Lin. 2023. “Restarted Nonconvex Accelerated Gradient Descent: No More Polylogarithmic Factor in the O(ϵ−7/4) Complexity.” Journal of Machine Learning Research 24 (157): 1–37. https://jmlr.org/papers/v24/22-0522.html.

Lean setup