Metraipolis › archive › dc_30219fabd97b

Optimal First-Order Methods for a Class of Structured Hölder-Smooth Problems — arXiv:2610.21595

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.21595
License (as archived)
CC0-1.0
Archived
2026-10-16T10:28:37.918Z
SHA-256 of the archived text
493bfa789e98ce7a4f3c3675f38e61e84952b790bfa06ad36a1333b3b2495169
Stable URL of this page
https://metraipolis.com/documento/dc_30219fabd97b

How to cite

Optimal First-Order Methods for a Class of Structured Hölder-Smooth Problems — arXiv:2610.21595 — arXiv (en), https://arxiv.org/abs/2610.21595 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_30219fabd97b (Metraipolis archive dc_30219fabd97b, sha256 493bfa789e98ce7a4f3c3675f38e61e84952b790bfa06ad36a1333b3b2495169)
BibTeX
@misc{dc30219fabd97b,
  title = {Optimal First-Order Methods for a Class of Structured Hölder-Smooth Problems — arXiv:2610.21595},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.21595},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_30219fabd97b; sha256 493bfa789e98ce7a4f3c3675f38e61e84952b790bfa06ad36a1333b3b2495169},
  year = {2026}
}

Archived text

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

Convex optimization with Hölder-continuous gradients has attracted considerable attention as a framework bridging smooth and nonsmooth optimization. For this class, Nesterov's universal fast gradient method attains the optimal black-box complexity, and we study whether exploiting further problem structure can further improve this bound. In this paper, we study an important class of Hölder-smooth problems, namely regularized $\ell_p$ regression with $p\in(1,2)$, whose loss has a $(p-1)$-Hölder-continuous gradient and for which the universal method requires $\mathcal{O}(\varepsilon^{-2/(3p-2)})$ iterations. Exploiting the problem structure, we characterize a family of smooth approximations based on $p$-Huber smoothing and prove that, for any prescribed smoothness level, it minimizes the worst-case approximation error among smooth lower approximations of the scalar loss. Combined with accelerated proximal gradients, the smoothing approach attains an $\varepsilon$-optimal solution in $\mathcal{O}(\varepsilon^{-1/p})$ matrix--vector products, which significantly improves the complexity guarantee for $1<p<2$. We show that this bound is optimal by providing a matching lower bound. Numerical experiments on synthetic and real data demonstrate the practical performance of the proposed methods.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.OC, nuovi lavori del giorno).
Categorie arXiv: Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2610.21595 — 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-10-16T08:49:47.926Z dalla pagina https://arxiv.org/list/math.OC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).