# Nearly optimal first-order methods for convex optimization under gradient norm measure: An adaptive regularization approach

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Dec 2019.

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

- [Parameter-free Locally Accelerated Conditional Gradients](https://mlsanity.com/paper/2102.06806/) (2021)
- [Accelerated first-order methods for convex optimization with locally Lipschitz continuous gradient](https://mlsanity.com/paper/2206.01209/) (2022)
- [Potential Function-based Framework for Making the Gradients Small in Convex and Min-Max Optimization](https://mlsanity.com/paper/2101.12101/) (2021)
- [Practical Schemes for Finding Near-Stationary Points of Convex Finite-Sums](https://mlsanity.com/paper/2105.12062/) (2021)

## Abstract (arXiv)

In the development of first-order methods for smooth (resp., composite) convex optimization problems, where smooth functions with Lipschitz continuous gradients are minimized, the gradient (resp., gradient mapping) norm becomes a fundamental optimality measure. Under this measure, a fixed iteration algorithm with the optimal iteration complexity is known, while determining this number of iteration to obtain a desired accuracy requires the prior knowledge of the distance from the initial point to the optimal solution set. In this paper, we report an adaptive regularization approach, which attains the nearly optimal iteration complexity without knowing the distance to the optimal solution set. To obtain further faster convergence adaptively, we secondly apply this approach to construct a first-order method that is adaptive to the H"olderian error bound condition (or equivalently, the Lojasiewicz gradient property), which covers moderately wide classes of applications. The proposed method attains nearly optimal iteration complexity with respect to the gradient mapping norm.