OpenAlex ·
Finding Stationary Points under Higher-Order Smoothness: Trapping Algorithms and First-Order Lower Bounds
- Published
- Source
- OpenAlex
- Published in
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2610.02791
- Original
- Read it at the publisher
- Topics
Abstract
We study the query complexity of finding approximate stationary points under higher-order smoothness using only function values or only gradients. Our results cover different dimensions, oracle models, randomization, and constraints. For constant dimension $d$ and $C^{p,β_p}$ objectives, with $ν:=p+β_p$, we give deterministic function-value gradient trapping algorithms with query complexities $O(\varepsilon^{-(d-1)})$ on $\mathbb R^d$ and $O(\varepsilon^{-(d-1)/ν})$ on $[0,1]^d$. High-order line integration enables gradient-only trapping. For two-dimensional $C^{1,1}$ objectives, randomized integration yields $O(\varepsilon^{-4/3})$ gradient queries on $\mathbb R^2$, breaking the deterministic gradient-only $Θ(\varepsilon^{-2})$ barrier. For general dimension, we introduce a trapping-or-descent framework that lazily reuses boundary models. For $C^{p,β_p}$ objectives with $p\ge2$, it achieves deterministic query complexities $O(d^p+d^{p-1+β_p/(ν-1)} \varepsilon^{-ν/(ν-1)})$ using function values and $O(d^{p-1}+d^{p-2+β_p/(ν-1)} \varepsilon^{-ν/(ν-1)})$ using gradients. These bounds apply to approximate stationary points on $\mathbb R^d$ and approximate KKT points on $[0,1]^d$. Their dimension-independent accuracy exponent matches the classical AR$p$ exponent $(p+1)/p$ when $β_p=1$. For sufficiently high dimension, we prove randomized lower bounds for gradient-only methods. For $C^{1,1}\cap C^{p,1}$ objectives, our lower bound is $Ω(\varepsilon^{-(3/2+1/(2p))})$, matching known upper bounds for $p=2$ and, up to logarithmic factors, for $p=3$. Without the $C^{1,1}$ assumption, we obtain an $Ω(\varepsilon^{-5/3})$ lower bound for every fixed $p\ge3$.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Artificial Intelligence
Hamiltonian locality testing and certification do not achieve the Heisenberg limit
A Hand-Checkable Proof That Two Hidden ReLU Layers Compute the Maximum of Six Numbers
No Size-Preserving Amplification with Quantum Advice
Nonuniform QCPH Collapse Implies QCPH Collapse
The Plan Language of a Curriculum: A Formal Model and the Complexity of Degree Planning
Get the few papers worth your time in Artificial Intelligence every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.