Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 40 min ago
PreprintCC BY 4.0arXiv

On the Complexity of Finding Stationary Points of p-th Order Hölder Smooth Functions in One Dimension

  • Huanjian Zhou
  • Taiji Suzuki
Open at sourcePDFDOICite

Abstract

We study the query complexity of finding an an ε-stationary points of a one-dimensional non-convex function whose p-th derivative is βp-Hölder continuous. We determine the optimal complexity for deterministic and randomized algorithms and for oracles that return only derivatives, only function values, or full local information. Randomness provably helps when only derivatives are available, function values help in all cases, and higher-order derivatives never do. Together with known results in higher dimensions, this shows how these benefits depend on the dimension. Our deterministic lower bound also implies that the optimal accuracy exponents of objective-function-free adaptive regularization of order p (OFFARp) in every dimension d≥1 and of deterministic gradient-only trapping in dimension d=2.

Related

  1. The Complexity of Finding Stationary Points in Nonsmooth Nonconvex Optimization
    Guy Kornowski
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv
  2. On the Complexity of Finding Stationary Points in Stochastic (L0, L1)-Smooth Nonconvex Optimization
    Yanpeng Liang, Luo Luo
    arXivPreprintCC BY 4.0Full textOptimisation & controlarXiv
  3. On the Complexity of Finding Fixed Points for Set-Valued Contractions
    Emmanouil-Vasileios Vlatakis-Gkaragkounis, Pucheng Xiong
    arXivPreprintarXiv licenceFull textGeometry & topologyarXiv
  4. Finding Stationary Points under Higher-Order Smoothness: Trapping Algorithms and First-Order Lower Bounds
    Huanjian Zhou, Masashi Sugiyama, Taiji Suzuki
    arXivPreprintCC BY 4.0Full textOptimisation & controlarXiv
  5. Finding New Limit Points of Mahler Measure by Methods of Missing Data Restoration
    Jean-Marc Sac-Épée, Souad El Otmani, Armand Maul +1
    arXivPreprintarXiv licenceFull textAlgebra & number theoryarXiv

Cite

BibTeXRIS
BibTeX
@misc{zhou2026complexity,
  title = {{On the Complexity of Finding Stationary Points of p-th Order Hölder Smooth Functions in One Dimension}},
  author = {Huanjian Zhou and Taiji Suzuki},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.16295},
  eprint = {2610.16295},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.16295},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - On the Complexity of Finding Stationary Points of p-th Order Hölder Smooth Functions in One Dimension
AU  - Huanjian Zhou
AU  - Taiji Suzuki
PY  - 2026
DA  - 2026/10/12
PB  - arXiv
DO  - 10.48550/arxiv.2610.16295
UR  - https://arxiv.org/abs/2610.16295
AB  - We study the query complexity of finding an an ε-stationary points of a one-dimensional non-convex function whose p-th derivative is β_p-Hölder continuous. We determine the optimal complexity for deterministic and randomized algorithms and for oracles that return only derivatives, only function values, or full local information. Randomness provably helps when only derivatives are available, function values help in all cases, and higher-order derivatives never do. Together with known results in higher dimensions, this shows how these benefits depend on the dimension. Our deterministic lower bound also implies that the optimal accuracy exponents of objective-function-free adaptive regularization of order p (OFFARp) in every dimension d≥1 and of deterministic gradient-only trapping in dimension d=2.
ER  -