# Accelerated first-order methods for convex optimization with locally Lipschitz continuous gradient

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 20 references that are in the map.
- First posted on arXiv 2 Jun 2022.

## Builds on (most cited first, 10 of 10)

- [Relatively-Smooth Convex Optimization by First-Order Methods, and Applications](https://mlsanity.com/paper/1610.05708/) (2016)
- [A Forward-Backward Splitting Method for Monotone Inclusions Without Cocoercivity](https://mlsanity.com/paper/1808.04162/) (2018)
- [Accelerated, Parallel and Proximal Coordinate Descent](https://mlsanity.com/paper/1312.5799/) (2013)
- [Accelerated Bregman Proximal Gradient Methods for Relatively Smooth Convex Optimization](https://mlsanity.com/paper/1808.03045/) (2018)
- [Complexity of first order inexact Lagrangian and penalty methods for conic convex programming](https://mlsanity.com/paper/1506.05320/) (2015)
- [On the non-ergodic convergence rate of an inexact augmented Lagrangian framework for composite convex programming](https://mlsanity.com/paper/1603.05738/) (2016)
- [Iteration complexity of first-order augmented Lagrangian methods for convex conic programming](https://mlsanity.com/paper/1803.09941/) (2018)
- [Adaptive inexact fast augmented Lagrangian methods for constrained convex optimization](https://mlsanity.com/paper/1505.03175/) (2015)
- [Nearly optimal first-order methods for convex optimization under gradient norm measure: An adaptive regularization approach](https://mlsanity.com/paper/1912.12004/) (2019)
- [An Augmented Lagrangian Method for Conic Convex Programming](https://mlsanity.com/paper/1302.6322/) (2013)

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

- [A simple uniformly optimal method without line search for convex optimization](https://mlsanity.com/paper/2310.10082/) (2023)
- [Directional Smoothness and Gradient Methods: Convergence and Adaptivity](https://mlsanity.com/paper/2403.04081/) (2024)
- [Federated Learning with Convex Global and Local Constraints](https://mlsanity.com/paper/2310.10117/) (2023)
- [Armijo Line-search Can Make (Stochastic) Gradient Descent Provably Faster](https://mlsanity.com/paper/2503.00229/) (2025)
- [Glocal Smoothness: Line search and adaptive step sizes can help in theory too!](https://mlsanity.com/paper/2506.12648/) (2025)

## Abstract (arXiv)

In this paper we develop accelerated first-order methods for convex optimization with locally Lipschitz continuous gradient (LLCG), which is beyond the well-studied class of convex optimization with Lipschitz continuous gradient. In particular, we first consider unconstrained convex optimization with LLCG and propose accelerated proximal gradient (APG) methods for solving it. The proposed APG methods are equipped with a verifiable termination criterion and enjoy an operation complexity of cal O(varepsilon-1/2log varepsilon-1) and cal O(log varepsilon-1) for finding an varepsilon-residual solution of an unconstrained convex and strongly convex optimization problem, respectively. We then consider constrained convex optimization with LLCG and propose an first-order proximal augmented Lagrangian method for solving it by applying one of our proposed APG methods to approximately solve a sequence of proximal augmented Lagrangian subproblems. The resulting method is equipped with a verifiable termination criterion and enjoys an operation complexity of cal O(varepsilon-1log varepsilon-1) and cal O(varepsilon-1/2log varepsilon-1) for finding an varepsilon-KKT solution of a constrained convex and strongly convex optimization problem, respectively. All the proposed methods in this paper are parameter-free or almost parameter-free except that the knowledge on convexity parameter is required. In addition, preliminary numerical results are presented to demonstrate the performance of our proposed methods. To the best of our knowledge, no prior studies were conducted to investigate accelerated first-order methods with complexity guarantees for convex optimization with LLCG. All the complexity results obtained in this paper are new.