# The Strength of Nesterov's Extrapolation in the Individual Convergence of Nonsmooth Optimization

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Jun 2020.

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

- [Minimax risk classifiers with 0-1 loss](https://mlsanity.com/paper/2201.06487/) (2022)
- [The Role of Momentum Parameters in the Optimal Convergence of Adaptive Polyak's Heavy-ball Methods](https://mlsanity.com/paper/2102.07314/) (2021)
- [Provable Convergence of Nesterov's Accelerated Gradient Method for Over-Parameterized Neural Networks](https://mlsanity.com/paper/2107.01832/) (2021)
- [MRCpy: A Library for Minimax Risk Classifiers](https://mlsanity.com/paper/2108.01952/) (2021)
- [Minimax Classification under Concept Drift with Multidimensional Adaptation and Performance Guarantees](https://mlsanity.com/paper/2205.15942/) (2022)
- [Distributed stochastic proximal algorithm with random reshuffling for non-smooth finite-sum optimization](https://mlsanity.com/paper/2111.03820/) (2021)
- [Minimax Forward and Backward Learning of Evolving Tasks with Performance Guarantees](https://mlsanity.com/paper/2310.15974/) (2023)
- [Adapting Step-size: A Unified Perspective to Analyze and Improve Gradient-based Methods for Adversarial Attacks](https://mlsanity.com/paper/2301.11546/) (2023)
- [Nonsmooth Projection-Free Optimization with Functional Constraints](https://mlsanity.com/paper/2311.11180/) (2023)

## Abstract (arXiv)

The extrapolation strategy raised by Nesterov, which can accelerate the convergence rate of gradient descent methods by orders of magnitude when dealing with smooth convex objective, has led to tremendous success in training machine learning tasks. In this article, the convergence of individual iterates of projected subgradient (PSG) methods for nonsmooth convex optimization problems is theoretically studied based on Nesterov's extrapolation, which we name individual convergence. We prove that Nesterov's extrapolation has the strength to make the individual convergence of PSG optimal for nonsmooth problems. In light of this consideration, a direct modification of the subgradient evaluation suffices to achieve optimal individual convergence for strongly convex problems, which can be regarded as making an interesting step toward the open question about stochastic gradient descent (SGD) posed by Shamir. Furthermore, we give an extension of the derived algorithms to solve regularized learning tasks with nonsmooth losses in stochastic settings. Compared with other state-of-the-art nonsmooth methods, the derived algorithms can serve as an alternative to the basic SGD especially in coping with machine learning problems, where an individual output is needed to guarantee the regularization structure while keeping an optimal rate of convergence. Typically, our method is applicable as an efficient tool for solving large-scale l1-regularized hinge-loss learning problems. Several comparison experiments demonstrate that our individual output not only achieves an optimal convergence rate but also guarantees better sparsity than the averaged solution.