# Adaptive proximal algorithms for convex optimization under local Lipschitz continuity of the gradient

arXiv: https://arxiv.org/abs/2301.04431 · HTML: https://mlsanity.com/paper/2301.04431/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 78 references that are in the map.
- First posted on arXiv 11 Jan 2023.

## Builds on (most cited first, 30 of 36)

- [AdaGrad stepsizes: Sharp convergence over nonconvex landscapes](https://mlsanity.com/paper/1806.01811/) (2018)
- [On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizes](https://mlsanity.com/paper/1805.08114/) (2018)
- [Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization](https://mlsanity.com/paper/2011.00364/) (2020)
- [Adaptive Gradient Descent without Descent](https://mlsanity.com/paper/1910.09529/) (2019)
- [Golden Ratio Algorithms for Variational Inequalities](https://mlsanity.com/paper/1803.08832/) (2018)
- [A Forward-Backward Splitting Method for Monotone Inclusions Without Cocoercivity](https://mlsanity.com/paper/1808.04162/) (2018)
- [A Three-Operator Splitting Scheme and its Optimization Applications](https://mlsanity.com/paper/1504.01032/) (2015)
- [Barzilai-Borwein Step Size for Stochastic Gradient Descent](https://mlsanity.com/paper/1605.04131/) (2016)
- [Solving Nonconvex-Nonconcave Min-Max Problems exhibiting Weak Minty Solutions](https://mlsanity.com/paper/2201.12247/) (2022)
- [Playing with Duality: An Overview of Recent Primal-Dual Approaches for Solving Large-Scale Optimization Problems](https://mlsanity.com/paper/1406.5429/) (2014)
- [A New Randomized Block-Coordinate Primal-Dual Proximal Algorithm for Distributed Optimization](https://mlsanity.com/paper/1706.02882/) (2017)
- [Beyond the Golden Ratio for Variational Inequality Algorithms](https://mlsanity.com/paper/2212.13955/) (2022)
- [A Coordinate Descent Primal-Dual Algorithm with Large Step Size and Possibly Non Separable Functions](https://mlsanity.com/paper/1508.04625/) (2015)
- [Stabilized Barzilai-Borwein method](https://mlsanity.com/paper/1907.06409/) (2019)
- [A new primal-dual algorithm for minimizing the sum of three functions with a linear operator](https://mlsanity.com/paper/1611.09805/) (2016)
- [Grad-GradaGrad? A Non-Monotone Adaptive Stochastic Gradient Method](https://mlsanity.com/paper/2206.06900/) (2022)
- [Asymmetric Forward-Backward-Adjoint Splitting for Solving Monotone Inclusions Involving Three Operators](https://mlsanity.com/paper/1602.08729/) (2016)
- [On the convergence of stochastic primal-dual hybrid gradient](https://mlsanity.com/paper/1911.00799/) (2019)
- [A first-order primal-dual algorithm with linesearch](https://mlsanity.com/paper/1608.08883/) (2016)
- [Adaptive Three Operator Splitting](https://mlsanity.com/paper/1804.02339/) (2018)
- [Distributed Proximal Splitting Algorithms with Rates and Acceleration](https://mlsanity.com/paper/2010.00952/) (2020)
- [Bregman Finito/MISO for nonconvex regularized finite sum minimization without Lipschitz gradient continuity](https://mlsanity.com/paper/2102.10312/) (2021)
- [A first-order primal-dual method with adaptivity to local smoothness](https://mlsanity.com/paper/2110.15148/) (2021)
- [Parameter-free accelerated gradient descent for nonconvex minimization](https://mlsanity.com/paper/2212.06410/) (2022)
- [A Relaxed Inertial Forward-Backward-Forward Algorithm for Solving Monotone Inclusions with Application to GANs](https://mlsanity.com/paper/2003.07886/) (2020)
- [Three Operator Splitting with Subgradients, Stochastic Gradients, and Adaptive Learning Rates](https://mlsanity.com/paper/2110.03274/) (2021)
- [Block-coordinate and incremental aggregated proximal gradient methods for nonsmooth nonconvex problems](https://mlsanity.com/paper/1906.10053/) (2019)
- [Nonlinear Forward-Backward Splitting with Projection Correction](https://mlsanity.com/paper/1908.07449/) (2019)
- [Proximal Gradient Algorithms under Local Lipschitz Gradient Continuity: A Convergence and Robustness Analysis of PANOC](https://mlsanity.com/paper/2112.13000/) (2021)
- [The variable metric forward-backward splitting algorithm under mild differentiability assumptions](https://mlsanity.com/paper/1605.00952/) (2016)

## Built on by (most cited first, 19 of 19)

- [Prodigy: An Expeditiously Adaptive Parameter-Free Learner](https://mlsanity.com/paper/2306.06101/) (2023)
- [DoWG Unleashed: An Efficient Universal Parameter-Free Gradient Descent Method](https://mlsanity.com/paper/2305.16284/) (2023)
- [Adaptive Proximal Gradient Method for Convex Optimization](https://mlsanity.com/paper/2308.02261/) (2023)
- [A simple uniformly optimal method without line search for convex optimization](https://mlsanity.com/paper/2310.10082/) (2023)
- [Adaptive Federated Learning with Auto-Tuned Clients](https://mlsanity.com/paper/2306.11201/) (2023)
- [Projected gradient methods for nonconvex and stochastic smooth optimization: new complexities and auto-conditioned stepsizes](https://mlsanity.com/paper/2412.14291/) (2024)
- [Analysis of an Idealized Stochastic Polyak Method and its Application to Black-Box Model Distillation](https://mlsanity.com/paper/2504.01898/) (2025)
- [Adaptive proximal gradient methods are universal without approximation](https://mlsanity.com/paper/2402.06271/) (2024)
- [On the convergence of adaptive first order methods: proximal gradient and alternating minimization algorithms](https://mlsanity.com/paper/2311.18431/) (2023)
- [Sparse Polyak: an adaptive step size rule for high-dimensional M-estimation](https://mlsanity.com/paper/2509.09802/) (2025)
- [Towards Stability of Parameter-Free Optimization](https://mlsanity.com/paper/2405.04376/) (2024)
- [The inexact power augmented Lagrangian method for constrained nonconvex optimization](https://mlsanity.com/paper/2410.20153/) (2024)
- [Randomized Feasibility Methods for Constrained Optimization with Adaptive Step Sizes](https://mlsanity.com/paper/2601.20076/) (2026)
- [Safeguarding adaptive methods: global convergence of Barzilai-Borwein and other stepsize choices](https://mlsanity.com/paper/2404.09617/) (2024)
- [Stochastic Adaptive Gradient Descent Without Descent](https://mlsanity.com/paper/2509.14969/) (2025)
- [Sparse Polyak with optimal thresholding operators for high-dimensional M-estimation](https://mlsanity.com/paper/2511.18167/) (2025)
- [Adaptive Decentralized Composite Optimization via Three-Operator Splitting](https://mlsanity.com/paper/2602.17545/) (2026)
- [Adaptive Delayed-Update Cyclic Algorithm for Variational Inequalities](https://mlsanity.com/paper/2603.29128/) (2026)
- [Stochastic Auto-conditioned Fast Gradient Methods with Optimal Rates](https://mlsanity.com/paper/2604.06525/) (2026)

## Abstract (arXiv)

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, adaPG, 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, adaPD, is proposed which can be viewed as an extension of the PDHG method. Moreover, in this setting the "essentially" fully adaptive variant adaPD^+ 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.