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 on a
finite-dimensional real inner product space . Its gradient and Hessian are Lipschitz
with constants and , respectively. A given point
satisfies for all , where . The oracle returns the truth
value of for queried
points . For , the goal is a finite
output list containing a point with gradient norm at most in every realization; each
listed point must be or a
queried point.
We seek approximate stationarity for the optimization problem The norm is induced by the inner product
on , and denotes the
induced operator norm. The Hessian acts from to . The algorithm receives , , , , , and .
Our assumptions:
Assumption 1 (Gradient and Hessian regularity). The
function belongs to . For every ,
Assumption 2 (Initial objective gap). The given
point satisfies
Queries may be any pair . The comparison oracle returns 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 completed queries , , the output list must satisfy 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
Proved result
OracleTemplate.Convergence LongTails.Setups.ComparisonHessianLipschitz.spec
OracleTemplate.ComparisonTrustAccelerated.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.