← All setups

Comparison Trust Accelerated — Comparison-Based Nonconvex Stationarity

Descriptions may be stale. Consult the linked Lean sources.

Comparison-Based Nonconvex Stationarity · Lean proof

Comparison-Based Nonconvex Stationarity

We consider a twice continuously differentiable, possibly nonconvex function f:E→R on a finite-dimensional real inner product space E. Its gradient and Hessian are Lipschitz with constants L>0 and ρ>0, respectively. A given point x0∈E satisfies f(x0)−f(x)≤Δ for all x∈E, where Δ≥0. The oracle returns the truth value of f(x)≤f(y) for queried points x,y∈E. For ε>0, the goal is a finite output list containing a point with gradient norm at most ε in every realization; each listed point must be x0 or a queried point.

We seek approximate stationarity for the optimization problem infx∈Ef(x). The norm ∥⋅∥ is induced by the inner product on E, and ∥⋅∥op denotes the induced operator norm. The Hessian ∇2f(x) acts from E to E. The algorithm receives E, x0, L, ρ, Δ, and ε.

Our assumptions:

Assumption 1 (Gradient and Hessian regularity). The function f belongs to C2(E;R). For every x,y∈E, ∥∇f(x)−∇f(y)∥≤L∥x−y∥,∥∇2f(x)−∇2f(y)∥op≤ρ∥x−y∥.

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

Queries may be any pair (x,y)∈E×E. The comparison oracle returns c(x,y)=1{f(x)≤f(y)}, so equality produces a true reply.

We restrict the output to a finite list of previously queried points and the given starting point. Precisely, in any run with m completed queries (uk,vk), 1≤k≤m, the output list X must satisfy x∈X⟹x∈{x0}∪⋃k=1m{uk,vk}. This restriction holds for every call budget and every realization, even for arbitrary Boolean oracle replies. With the exact comparison oracle, the required accuracy is ∃x∈X:∥∇f(x)∥≤εin every realization.

Proved result

(⌊400⋅Δ⋅ρε32⌋++1)⋅⌈250000⋅(dimR⁡(E)+1)⋅2⋅Lρ⋅ε+4⋅(log⁡(2+dimR⁡(E)+Lρ⋅ε+2⋅L⋅Δε))3⌉+

OracleTemplate.Convergence LongTails.Setups.ComparisonHessianLipschitz.spec
  OracleTemplate.ComparisonTrustAccelerated.budget

Relevant previous results

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