# Sparse Polyak with optimal thresholding operators for high-dimensional M-estimation

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 20 references that are in the map.
- First posted on arXiv 22 Nov 2025.

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

- [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)
- [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)
- [Between hard and soft thresholding: optimal iterative thresholding algorithms](https://mlsanity.com/paper/1804.08841/) (2018)
- [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)
- [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)
- [Sparse Polyak: an adaptive step size rule for high-dimensional M-estimation](https://mlsanity.com/paper/2509.09802/) (2025)

## Abstract (arXiv)

We propose and analyze a variant of Sparse Polyak for high dimensional M-estimation problems. Sparse Polyak proposes a novel adaptive step-size rule tailored to suitably estimate the problem's curvature in the high-dimensional setting, guaranteeing that the algorithm's performance does not deteriorate when the ambient dimension increases. However, convergence guarantees can only be obtained by sacrificing solution sparsity and statistical accuracy. In this work, we introduce a variant of Sparse Polyak that retains its desirable scaling properties with respect to the ambient dimension while obtaining sparser and more accurate solutions.