← All setups

Comparison-Based Nonconvex Stationarity

Descriptions may be stale. Consult the linked Lean sources.

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.

Results

On a finite-dimensional real inner-product space, f∈C2 has L-Lipschitz gradient and ρ-Lipschitz Hessian, with f(x0)−f(x)≤Δ for every x; L,ρ,ε>0, Δ≥0. Queries return exact bits [f(x)≤f(y)]. The target is a list containing x with ∥∇f(x)∥≤ε on every run. The setup restricts list entries to x0 or queried points, not to a particular method.

Comparison-oracle stationarity under ComparisonHessianLipschitz.
Result Oracle complexity Novelty Limitations
(1) ComparisonTrustAccelerated (Ours) (⋆⋆⋆) (review) O((1+Δρε−3/2)
⋅(n+1)(1+q)ℓ3) comparisons
(2) (Wang et al. 2026, Thm. 8, v1) O((1+Δρε−3/2)
⋅n2polylog(n,L,ρ,ε−1)) comparisons; success 2/3.
(1): leading cost saves n/(1+q) up to logs when n≫(1+q)ℓ3; deterministic instead of success 2/3. (1) loses second-order accuracy λmin(∇2f)≥−ρε; polynomial L1/2 dependence, worse when n≲q.
(3) (Zhang and Li 2024, Thm. 4, v1) O((1+LΔ/ε2)nlog⁡(2+n)) comparisons; selected point succeeds with probability 2/3. (1): leading cost saves q up to logs for ε≪L2/ρ. At L=ρ=Δ=1, n=ε−1/2: O(ε−9/4log3⁡(1/ε)) versus O(ε−5/2log⁡(1/ε)). (1) needs Lipschitz Hessian and guarantees a containing list, not a selected stationary point.

Abbr: n=dim⁡E, q=(L2/(ρε))1/4, ℓ=log⁡(2+n+L/ρε+LΔ/ε). polylog denotes the logarithmic factors suppressed in the cited bound. Leading-cost comparisons assume Δρε−3/2≳1; the numerical regime is as ε↓0.

Wang, Helin, Chenyi Zhang, Xiwen Tao, Yexin Zhang, and Tongyang Li. 2026. Finding Stationary Points by Comparisons. https://arxiv.org/abs/2606.27082v1.
Zhang, Chenyi, and Tongyang Li. 2024. Comparisons Are All You Need for Optimizing Smooth Functions. https://doi.org/10.48550/arXiv.2405.11454.

Lean setup