TY - JOUR
T1 - Adaptive proximal algorithms for convex optimization under local Lipschitz continuity of the gradient
AU - Latafat, Puya
AU - Themelis, Andreas
AU - Stella, Lorenzo
AU - Patrinos, Panagiotis
N1 - Publisher Copyright:
© Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society 2024.
PY - 2024
Y1 - 2024
N2 - Backtracking linesearch is the de facto approach for minimizing continuously differentiable functions with locally Lipschitz gradient. In recent years, it has been shown that in the convex setting it is possible to avoid linesearch altogether, and to allow the stepsize to adapt based on a local smoothness estimate without any backtracks or evaluations of the function value. In this work we propose an adaptive proximal gradient method, adaPGM, that uses novel estimates of the local smoothness modulus which leads to less conservative stepsize updates and that can additionally cope with nonsmooth terms. This idea is extended to the primal-dual setting where an adaptive three-term primal-dual algorithm, adaPDM, is proposed which can be viewed as an extension of the PDHG method. Moreover, in this setting the “essentially” fully adaptive variant adaPDM+ is proposed that avoids evaluating the linear operator norm by invoking a backtracking procedure, that, remarkably, does not require extra gradient evaluations. Numerical simulations demonstrate the effectiveness of the proposed algorithms compared to the state of the art.
AB - Backtracking linesearch is the de facto approach for minimizing continuously differentiable functions with locally Lipschitz gradient. In recent years, it has been shown that in the convex setting it is possible to avoid linesearch altogether, and to allow the stepsize to adapt based on a local smoothness estimate without any backtracks or evaluations of the function value. In this work we propose an adaptive proximal gradient method, adaPGM, that uses novel estimates of the local smoothness modulus which leads to less conservative stepsize updates and that can additionally cope with nonsmooth terms. This idea is extended to the primal-dual setting where an adaptive three-term primal-dual algorithm, adaPDM, is proposed which can be viewed as an extension of the PDHG method. Moreover, in this setting the “essentially” fully adaptive variant adaPDM+ is proposed that avoids evaluating the linear operator norm by invoking a backtracking procedure, that, remarkably, does not require extra gradient evaluations. Numerical simulations demonstrate the effectiveness of the proposed algorithms compared to the state of the art.
KW - 65K05
KW - 90C06
KW - 90C25
KW - 90C30
KW - 90C47
KW - Convex minimization
KW - Linesearch-free adaptive stepsizes
KW - Locally Lipschitz gradient
KW - Primal-dual algorithms
KW - Proximal gradient method
UR - http://www.scopus.com/inward/record.url?scp=85207967803&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85207967803&partnerID=8YFLogxK
U2 - 10.1007/s10107-024-02143-7
DO - 10.1007/s10107-024-02143-7
M3 - Article
AN - SCOPUS:85207967803
SN - 0025-5610
JO - Mathematical Programming
JF - Mathematical Programming
ER -