Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 36 min ago
PreprintarXiv licencearXiv

Exponential Deterministic Query Complexity of Goldstein Stationarity

  • Yixi Ding
  • Ya-xiang Yuan
Open at sourcePDFDOICite

Abstract

We study the deterministic query complexity of finding approximate Goldstein stationary points of globally Lipschitz functions that may be nonsmooth and nonconvex. Under prescribed bounds on the Lipschitz constant and on the difference between the initial function value and the infimum, we prove a lower bound on the worst-case number of oracle calls that is exponential in the dimension at fixed sufficiently small accuracy parameters. The result holds for a local oracle and gives explicit dependence on the accuracy parameters. A complementary deterministic algorithm using only function values gives an exponential upper bound, establishing the exponential order in the dimension in this regime. For a coarser stationarity requirement, we also give a deterministic first-order algorithm with a dimension-free query bound. Thus, the dimension dependence differs between the two accuracy regimes.

Related

  1. Deterministic Oracle Complexity for Goldstein Stationarity in Nonsmooth Nonconvex Optimization with Constraints
    Yixi Ding, Ya-xiang Yuan
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv
  2. An Exponential Deterministic--Randomized Gap in ERM-Oracle Complexity for Thresholds on an Unknown Order
    Xuan Li
    arXivPreprintarXiv licenceFull textStatisticsarXiv
  3. Directed Cut-Query Complexity of Finding a King
    Ziad Ismaili Alaoui, Oded Lachish, Nikhil S. Mande
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. Entropy hypocoercivity and query complexity for the bouncy particle sampler
    Jianfeng Lu, Yinchen Luo
    arXivPreprintCC BY 4.0Full textProbabilityarXiv
  5. Windowed thinning and query complexity for the bouncy particle and Zigzag samplers
    Jianfeng Lu, Yinchen Luo
    arXivPreprintCC BY 4.0Full textNumerical analysis & scientific computingProbabilityarXiv

Cite

BibTeXRIS
BibTeX
@misc{ding2026exponential,
  title = {{Exponential Deterministic Query Complexity of Goldstein Stationarity}},
  author = {Yixi Ding and Ya-xiang Yuan},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2609.38082},
  eprint = {2609.38082},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.38082},
}
RIS
TY  - UNPB
TI  - Exponential Deterministic Query Complexity of Goldstein Stationarity
AU  - Yixi Ding
AU  - Ya-xiang Yuan
PY  - 2026
DA  - 2026/10/07
PB  - arXiv
DO  - 10.48550/arxiv.2609.38082
UR  - https://arxiv.org/abs/2609.38082
AB  - We study the deterministic query complexity of finding approximate Goldstein stationary points of globally Lipschitz functions that may be nonsmooth and nonconvex. Under prescribed bounds on the Lipschitz constant and on the difference between the initial function value and the infimum, we prove a lower bound on the worst-case number of oracle calls that is exponential in the dimension at fixed sufficiently small accuracy parameters. The result holds for a local oracle and gives explicit dependence on the accuracy parameters. A complementary deterministic algorithm using only function values gives an exponential upper bound, establishing the exponential order in the dimension in this regime. For a coarser stationarity requirement, we also give a deterministic first-order algorithm with a dimension-free query bound. Thus, the dimension dependence differs between the two accuracy regimes.
ER  -