# Optimal computational and statistical rates of convergence for sparse nonconvex learning problems

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

## Key facts

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

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

- [On the Global Convergence of Imitation Learning: A Case for Linear Quadratic Regulator](https://mlsanity.com/paper/1901.03674/) (2019)
- [Fast Composite Optimization and Statistical Recovery in Federated Learning](https://mlsanity.com/paper/2207.08204/) (2022)
- [Can We Find Nash Equilibria at a Linear Rate in Markov Games?](https://mlsanity.com/paper/2303.03095/) (2023)
- [Optimal Regularization for a Data Source](https://mlsanity.com/paper/2212.13597/) (2022)
- [Analysis of Generalized Bregman Surrogate Algorithms for Nonsmooth Nonconvex Statistical Learning](https://mlsanity.com/paper/2112.09191/) (2021)
- [Covariate-assisted Sparse Tensor Completion](https://mlsanity.com/paper/2103.06428/) (2021)
- [Variance-Aware Linear UCB with Deep Representation for Neural Contextual Bandits](https://mlsanity.com/paper/2411.05979/) (2024)
- [Slow Kill for Big Data Learning](https://mlsanity.com/paper/2305.01726/) (2023)
- [Sparse Polyak: an adaptive step size rule for high-dimensional M-estimation](https://mlsanity.com/paper/2509.09802/) (2025)
- [Robust High-Dimensional Regression with Coefficient Thresholding and its Application to Imaging Data Analysis](https://mlsanity.com/paper/2109.14856/) (2021)
- [Provable Low Rank Plus Sparse Matrix Separation Via Nonconvex Regularizers](https://mlsanity.com/paper/2109.12713/) (2021)
- [Sketching for Convex and Nonconvex Regularized Least Squares with Sharp Guarantees](https://mlsanity.com/paper/2311.01806/) (2023)
- [Sparse PCA with Oracle Property](https://mlsanity.com/paper/2312.16793/) (2023)
- [Sparse Polyak with optimal thresholding operators for high-dimensional M-estimation](https://mlsanity.com/paper/2511.18167/) (2025)

## Abstract (arXiv)

We provide theoretical analysis of the statistical and computational properties of penalized M-estimators that can be formulated as the solution to a possibly nonconvex optimization problem. Many important estimators fall in this category, including least squares regression with nonconvex regularization, generalized linear models with nonconvex regularization and sparse elliptical random design regression. For these problems, it is intractable to calculate the global solution due to the nonconvex formulation. In this paper, we propose an approximate regularization path-following method for solving a variety of learning problems with nonconvex objective functions. Under a unified analytic framework, we simultaneously provide explicit statistical and computational rates of convergence for any local solution attained by the algorithm. Computationally, our algorithm attains a global geometric rate of convergence for calculating the full regularization path, which is optimal among all first-order algorithms. Unlike most existing methods that only attain geometric rates of convergence for one single regularization parameter, our algorithm calculates the full regularization path with the same iteration complexity. In particular, we provide a refined iteration complexity bound to sharply characterize the performance of each stage along the regularization path. Statistically, we provide sharp sample complexity analysis for all the approximate local solutions along the regularization path. In particular, our analysis improves upon existing results by providing a more refined sample complexity bound as well as an exact support recovery result for the final estimator. These results show that the final estimator attains an oracle statistical property due to the usage of nonconvex penalty.