Skip to content
DraconiticResearch
Search Sources API
210,043 studies31 sourcesUpdated 40 min ago
PreprintCC BY 4.0HAL

An optimal first-order method for smooth and strongly convex composite optimization and its stationary limit

  • Manu Upadhyaya
  • Daniel Berg Thomsen
  • Aymeric Dieuleveut
  • Adrien B Taylor
Open at sourcePDFCite

Abstract

We introduce Prox-ITEM, an optimal proximal-gradient method for minimizing f + g, where f is smooth and strongly convex, and g is convex, proper, and lower semicontinuous. In the smooth case g = 0, Prox-ITEM reduces to the information-theoretic exact method (ITEM). We prove an exact distance-to-solution bound for Prox-ITEM with the same distance-convergence rate as ITEM, and show that this rate is minimax optimal among span-based first-order methods using the same number of gradient-oracle calls for f and an arbitrary number of proximal-oracle calls for g. We also identify the stationary limit of Prox-ITEM, denoted Prox-TMM, which gives a proximal extension of the triple momentum method (TMM) to the composite setting and achieves the corresponding TMM distance-convergence rate.

Related

  1. Near-Optimal Single-Loop Predictor--Corrector Extragradient Method for Strongly Convex--Strongly Concave Minimax Optimization
    Minhao Zhang, Zi Xu
    arXivPreprintarXiv licenceFull textOptimisation & controlStatisticsarXiv
  2. An Optimal First-Order Active-Hull Method for Convex Composite Hölder Smooth Optimization
    Renbo Zhao
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv
  3. Near-Optimal Complexity of Finite-Sum Nonconvex-Strongly-Concave Minimax Optimization
    Qihao Zhou
    arXivPreprintCC BY 4.0Full textOptimisation & controlarXiv
  4. Accelerated Proximal Gradient Method for Non-Strongly Convex Time-Varying Optimization
    Tomoya Kamijima, Naoki Marumo, Akiko Takeda
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv
  5. Near-Optimal Exact-Value Zeroth-Order Complexity for Smooth Strongly Convex Optimization
    Wendao Wu, Haihan Zhang, Chenheng Zhang +5
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv

Cite

BibTeXRIS
BibTeX
@misc{upadhyaya2026optimal,
  title = {{An optimal first-order method for smooth and strongly convex composite optimization and its stationary limit}},
  author = {Manu Upadhyaya and Daniel Berg Thomsen and Aymeric Dieuleveut and Adrien B Taylor},
  howpublished = {HAL},
  year = {2026},
  month = aug,
  url = {https://hal.science/hal-05858407v1},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - An optimal first-order method for smooth and strongly convex composite optimization and its stationary limit
AU  - Manu Upadhyaya
AU  - Daniel Berg Thomsen
AU  - Aymeric Dieuleveut
AU  - Adrien B Taylor
PY  - 2026
DA  - 2026/08/21
PB  - HAL
UR  - https://hal.science/hal-05858407v1
AB  - We introduce Prox-ITEM, an optimal proximal-gradient method for minimizing f + g, where f is smooth and strongly convex, and g is convex, proper, and lower semicontinuous. In the smooth case g = 0, Prox-ITEM reduces to the information-theoretic exact method (ITEM). We prove an exact distance-to-solution bound for Prox-ITEM with the same distance-convergence rate as ITEM, and show that this rate is minimax optimal among span-based first-order methods using the same number of gradient-oracle calls for f and an arbitrary number of proximal-oracle calls for g. We also identify the stationary limit of Prox-ITEM, denoted Prox-TMM, which gives a proximal extension of the triple momentum method (TMM) to the composite setting and achieves the corresponding TMM distance-convergence rate.
ER  -