Metraipolis › archive › dc_098f21113cd2

Tight Lower Bounds under Matched High-Order Hölder Smoothness and Uniform Convexity — arXiv:2611.05527

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.05527
License (as archived)
CC0-1.0
Archived
2026-11-05T18:22:30.725Z
SHA-256 of the archived text
28c49f73fe5fa5dab9a761dfac1eca5d2dd0967afc6b6650c8408ec3e969de83
Stable URL of this page
https://metraipolis.com/documento/dc_098f21113cd2

How to cite

Tight Lower Bounds under Matched High-Order Hölder Smoothness and Uniform Convexity — arXiv:2611.05527 — arXiv (en), https://arxiv.org/abs/2611.05527 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_098f21113cd2 (Metraipolis archive dc_098f21113cd2, sha256 28c49f73fe5fa5dab9a761dfac1eca5d2dd0967afc6b6650c8408ec3e969de83)
BibTeX
@misc{dc098f21113cd2,
  title = {Tight Lower Bounds under Matched High-Order Hölder Smoothness and Uniform Convexity — arXiv:2611.05527},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.05527},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_098f21113cd2; sha256 28c49f73fe5fa5dab9a761dfac1eca5d2dd0967afc6b6650c8408ec3e969de83},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.05527. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In this paper, we provide tight lower bounds for minimizing high-order Hölder-smooth and uniformly convex functions when their orders match. Specifically, we consider functions whose $p^{th}$-order derivatives are Hölder continuous with degree $\nu$ and parameter $H$, and that are uniformly convex with degree $q$ and parameter $\sigma$. When these orders match, namely, $q = p + \nu$, we show that any deterministic algorithm with access to derivatives up to order $p$ requires $\Omega\left(\left(\frac{H}{\sigma}\right)^{\frac{2}{3(p+\nu)-2}}\log\frac{\Delta_0}{\epsilon}\right)$ oracle calls to reduce an initial optimality gap of $\Delta_0$ to $\epsilon$. This matches the corresponding upper bound and establishes a higher-order uniformly convex counterpart to Nesterov's classical first-order lower bound for strongly convex functions. Rather than directly generalizing Nesterov's classical quadratic-chain construction, we develop a multiscale phase-wise construction that preserves previous oracle responses while maintaining global Hölder smoothness and uniform convexity. Our result resolves the matched case left open by existing lower bounds for the two asymmetric regimes.

Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.LG, nuovi lavori del giorno).
Categorie arXiv: Optimization and Control (math.OC) ; Machine Learning (cs.LG); Machine Learning (stat.ML).
Pagina del lavoro: https://arxiv.org/abs/2611.05527 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-05T18:15:49.029Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).