# Sparse Polyak: an adaptive step size rule for high-dimensional M-estimation

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 43 references that are in the map.
- First posted on arXiv 11 Sep 2025.

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

- [Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence](https://mlsanity.com/paper/2002.10542/) (2020)
- [Adaptive Gradient Descent without Descent](https://mlsanity.com/paper/1910.09529/) (2019)
- [Regularized M-estimators with nonconvexity: Statistical and algorithmic theory for local optima](https://mlsanity.com/paper/1305.2436/) (2013)
- [Revisiting the Polyak step size](https://mlsanity.com/paper/1905.00313/) (2019)
- [On Iterative Hard Thresholding Methods for High-dimensional M-Estimation](https://mlsanity.com/paper/1410.5137/) (2014)
- [Adaptive Proximal Gradient Method for Convex Optimization](https://mlsanity.com/paper/2308.02261/) (2023)
- [Adaptive proximal algorithms for convex optimization under local Lipschitz continuity of the gradient](https://mlsanity.com/paper/2301.04431/) (2023)
- [Directional Smoothness and Gradient Methods: Convergence and Adaptivity](https://mlsanity.com/paper/2403.04081/) (2024)
- [A Tight Bound of Hard Thresholding](https://mlsanity.com/paper/1605.01656/) (2016)
- [Generalized Polyak Step Size for First Order Optimization with Momentum](https://mlsanity.com/paper/2305.12939/) (2023)
- [Optimal computational and statistical rates of convergence for sparse nonconvex learning problems](https://mlsanity.com/paper/1306.4960/) (2013)
- [IHT dies hard: Provable accelerated Iterative Hard Thresholding](https://mlsanity.com/paper/1712.09379/) (2017)
- [Iterative Hard Thresholding with Adaptive Regularization: Sparser Solutions Without Sacrificing Runtime](https://mlsanity.com/paper/2204.08274/) (2022)
- [AdaBB: Adaptive Barzilai-Borwein Method for Convex Optimization](https://mlsanity.com/paper/2401.08024/) (2024)
- [Stability and Risk Bounds of Iterative Hard Thresholding](https://mlsanity.com/paper/2203.09413/) (2022)
- [Nonconvex Sparse Learning via Stochastic Optimization with Progressive Variance Reduction](https://mlsanity.com/paper/1605.02711/) (2016)
- [Towards Statistical and Computational Complexities of Polyak Step Size Gradient Descent](https://mlsanity.com/paper/2110.07810/) (2021)
- [Exact Convergence rate of the subgradient method by using Polyak step size](https://mlsanity.com/paper/2407.15195/) (2024)
- [Polyak Minorant Method for Convex Optimization](https://mlsanity.com/paper/2310.07922/) (2023)

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

- [Safeguarded Stochastic Polyak Step Sizes for Non-smooth Optimization: Robust Performance Without Small (Sub)Gradients](https://mlsanity.com/paper/2512.02342/) (2025)
- [Sparse Polyak with optimal thresholding operators for high-dimensional M-estimation](https://mlsanity.com/paper/2511.18167/) (2025)

## Abstract (arXiv)

We propose and study Sparse Polyak, a variant of Polyak's adaptive step size, designed to solve high-dimensional statistical estimation problems where the problem dimension is allowed to grow much faster than the sample size. In such settings, the standard Polyak step size performs poorly, requiring an increasing number of iterations to achieve optimal statistical precision-even when, the problem remains well conditioned and/or the achievable precision itself does not degrade with problem size. We trace this limitation to a mismatch in how smoothness is measured: in high dimensions, it is no longer effective to estimate the Lipschitz smoothness constant. Instead, it is more appropriate to estimate the smoothness restricted to specific directions relevant to the problem (restricted Lipschitz smoothness constant). Sparse Polyak overcomes this issue by modifying the step size to estimate the restricted Lipschitz smoothness constant. We support our approach with both theoretical analysis and numerical experiments, demonstrating its improved performance.