Finding Stationary Points under Higher-Order Smoothness: Trapping Algorithms and First-Order Lower Bounds

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(ε^−(d−1)) on ℝ^d and O(ε^{−(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(ε^−4/3) gradient queries on ℝ², breaking the deterministic gradient-only Θ(ε⁻²) barrier. For general dimension, we introduce a trapping-or-descent framework that lazily reuses boundary models. For C^p,β_p objectives with p≥2, it achieves deterministic query complexities O(d^p+d^{p−1+β_p/(ν−1)} ε^{−ν/(ν−1)}) using function values and O(d^p−1+d^{p−2+β_p/(ν−1)} ε^{−ν/(ν−1)}) using gradients. These bounds apply to approximate stationary points on ℝ^d and approximate KKT points on [0,1]^d. Their dimension-independent accuracy exponent matches the classical ARp exponent (p+1)/p when β_p=1. For sufficiently high dimension, we prove randomized lower bounds for gradient-only methods. For C^1,1∩ C^p,1 objectives, our lower bound is Ω(ε^{−(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 Ω(ε^−5/3) lower bound for every fixed p≥3.

The Complexity of Finding Stationary Points in Nonsmooth Nonconvex Optimization
Guy Kornowski
arXiv15 Sep 2026PreprintarXiv licenceFull textOptimisation & controlarXiv
On the Complexity of Finding Stationary Points of p-th Order Hölder Smooth Functions in One Dimension
Huanjian Zhou, Taiji Suzuki
arXiv12 Oct 2026PreprintCC BY 4.0Full textOptimisation & controlarXiv
On the Complexity of Finding Stationary Points in Stochastic (L₀, L₁)-Smooth Nonconvex Optimization
Yanpeng Liang, Luo Luo
arXiv15 Oct 2026PreprintCC BY 4.0Full textOptimisation & controlarXiv
Zero Crossings on the Accuracy-Smoothness Frontier: Maximal Monotone and Minimal Inflection Non Stationary Predictors
Marc Wildi
arXiv30 Oct 2026PreprintCC BY 4.0Full textStatisticsarXiv
Finding New Limit Points of Mahler Measure by Methods of Missing Data Restoration
Jean-Marc Sac-Épée, Souad El Otmani, Armand Maul +1
arXiv17 Sep 2026PreprintarXiv licenceFull textAlgebra & number theoryarXiv

Cite

BibTeX RIS

BibTeX

@misc{zhou2026finding,
  title = {{Finding Stationary Points under Higher-Order Smoothness: Trapping Algorithms and First-Order Lower Bounds}},
  author = {Huanjian Zhou and Masashi Sugiyama and Taiji Suzuki},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.02791},
  eprint = {2610.02791},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.02791},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Finding Stationary Points under Higher-Order Smoothness: Trapping Algorithms and First-Order Lower Bounds
AU  - Huanjian Zhou
AU  - Masashi Sugiyama
AU  - Taiji Suzuki
PY  - 2026
DA  - 2026/10/02
PB  - arXiv
DO  - 10.48550/arxiv.2610.02791
UR  - https://arxiv.org/abs/2610.02791
AB  - 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(ε^−(d−1)) on ℝ^d and O(ε^−(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(ε^−4/3) gradient queries on ℝ^2, breaking the deterministic gradient-only Θ(ε^−2) barrier. For general dimension, we introduce a trapping-or-descent framework that lazily reuses boundary models. For C^p,β_p objectives with p≥2, it achieves deterministic query complexities O(d^p+d^p−1+β_p/(ν−1) ε^−ν/(ν−1)) using function values and O(d^p−1+d^p−2+β_p/(ν−1) ε^−ν/(ν−1)) using gradients. These bounds apply to approximate stationary points on ℝ^d and approximate KKT points on [0,1]^d. Their dimension-independent accuracy exponent matches the classical ARp exponent (p+1)/p when β_p=1. For sufficiently high dimension, we prove randomized lower bounds for gradient-only methods. For C^1,1∩ C^p,1 objectives, our lower bound is Ω(ε^−(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 Ω(ε^−5/3) lower bound for every fixed p≥3.
ER  -

Abstract

Related

Cite