Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 3 min ago
PreprintCC BY 4.0arXiv

Complexity analysis of trust-region methods under (α,L0,L1)-smoothness

  • Youssef Diouane
  • Mohamed L. Habiboullah
  • Awa Khouna
  • Dominique Orban
Open at sourcePDFDOICite

Abstract

Generalized smoothness assumptions have attracted growing attention in recent years, motivated in part by machine learning problems in which the gradient of the objective function may not be Lipschitz continuous. Among the most prominent of these is the (α, L0, L1)-smoothness assumption. Existing methods that attain the best known complexity bounds require knowledge of, or upper bounds on, α, L0 and L1, while the few parameter-agnostic methods available do not recover those bounds. In this paper, we show that trust-region methods attain the best known bounds for (α, L0, L1)-smooth objective functions without prior knowledge of these parameters. Establishing these results requires new analytical tools, beyond those used in classical trust-region complexity analyses. We further show that our working model assumption allows the use of general model Hessian approximations and, in particular, accommodates limited-memory quasi-Newton updates. Finally, we show that our complexity bound is sharp in the nonconvex setting.

Related

  1. Structural conditions on trust-region radius updates. Part I: first-order convergence and complexity
    Jérémy Rieussec, Fabian Bastin
    arXivPreprintCC BY-SA 4.0Full textNumerical analysis & scientific computingOptimisation & controlarXiv
  2. Bayesian Optimization with Fisher Information Geometry: Gradient Bounds and Trust-Region Methods
    Saksham Kiroriwal, Julius Pfrommer, Jürgen Beyerer
    arXivPreprintarXiv licenceFull textGeneral mathematicsarXiv
  3. Relative Primal--Dual Gap Certificates for Operator-Composite Trust-Region Methods
    Harbir Antil
    arXivPreprintarXiv licenceFull textAnalysis & PDEsNumerical analysis & scientific computingarXiv
  4. Random-subspace Ellipsoidal Trust-region Methods for Derivative-free Optimization
    Yiwen Chen, Pengcheng Xie
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv
  5. Descending Everest with First-Order Oracles: Oracle Complexity of Convex Optimization under (L0,L1)-Smoothness
    Mikhail Rudomanov, Ivan Fomin, Alexander V. Gasnikov +1
    arXivPreprintCC BY 4.0Full textOptimisation & controlarXiv

Cite

BibTeXRIS
BibTeX
@misc{diouane2026complexity,
  title = {{Complexity analysis of trust-region methods under $(α,L_0,L_1)$-smoothness}},
  author = {Youssef Diouane and Mohamed L. Habiboullah and Awa Khouna and Dominique Orban},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.33238},
  eprint = {2609.33238},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.33238},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Complexity analysis of trust-region methods under (α,L_0,L_1)-smoothness
AU  - Youssef Diouane
AU  - Mohamed L. Habiboullah
AU  - Awa Khouna
AU  - Dominique Orban
PY  - 2026
DA  - 2026/09/27
PB  - arXiv
DO  - 10.48550/arxiv.2609.33238
UR  - https://arxiv.org/abs/2609.33238
AB  - Generalized smoothness assumptions have attracted growing attention in recent years, motivated in part by machine learning problems in which the gradient of the objective function may not be Lipschitz continuous. Among the most prominent of these is the (α, L_0, L_1)-smoothness assumption. Existing methods that attain the best known complexity bounds require knowledge of, or upper bounds on, α, L_0 and L_1, while the few parameter-agnostic methods available do not recover those bounds. In this paper, we show that trust-region methods attain the best known bounds for (α, L_0, L_1)-smooth objective functions without prior knowledge of these parameters. Establishing these results requires new analytical tools, beyond those used in classical trust-region complexity analyses. We further show that our working model assumption allows the use of general model Hessian approximations and, in particular, accommodates limited-memory quasi-Newton updates. Finally, we show that our complexity bound is sharp in the nonconvex setting.
ER  -