# Regularized M-estimators with nonconvexity: Statistical and algorithmic theory for local optima

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

## Key facts

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

## Built on by (most cited first, 30 of 66)

- [Transfer Learning under High-dimensional Generalized Linear Models](https://mlsanity.com/paper/2105.14328/) (2021)
- [Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2209.05045/) (2022)
- [High Dimensional Differentially Private Stochastic Optimization with Heavy-tailed Data](https://mlsanity.com/paper/2107.11136/) (2021)
- [Scaled ReLU Matters for Training Vision Transformers](https://mlsanity.com/paper/2109.03810/) (2021)
- [Differentially private inference via noisy optimization](https://mlsanity.com/paper/2103.11003/) (2021)
- [Score Attack: A Lower Bound Technique for Optimal Differentially Private Learning](https://mlsanity.com/paper/2303.07152/) (2023)
- [Fast Composite Optimization and Statistical Recovery in Federated Learning](https://mlsanity.com/paper/2207.08204/) (2022)
- [Quantizing Heavy-tailed Data in Statistical Estimation: (Near) Minimax Rates, Covariate Quantization, and Uniform Recovery](https://mlsanity.com/paper/2212.14562/) (2022)
- [Hardness and Algorithms for Robust and Sparse Optimization](https://mlsanity.com/paper/2206.14354/) (2022)
- [Iterative Approximate Cross-Validation](https://mlsanity.com/paper/2303.02732/) (2023)
- [Group-Sparse Matrix Factorization for Transfer Learning of Word Embeddings](https://mlsanity.com/paper/2104.08928/) (2021)
- [Optimal network online change point localisation](https://mlsanity.com/paper/2101.05477/) (2021)
- [Towards Statistical and Computational Complexities of Polyak Step Size Gradient Descent](https://mlsanity.com/paper/2110.07810/) (2021)
- [Sparse Graph Learning Under Laplacian-Related Constraints](https://mlsanity.com/paper/2111.08161/) (2021)
- [Analysis of Generalized Bregman Surrogate Algorithms for Nonsmooth Nonconvex Statistical Learning](https://mlsanity.com/paper/2112.09191/) (2021)
- [Quantized Low-Rank Multivariate Regression with Random Dithering](https://mlsanity.com/paper/2302.11197/) (2023)
- [Correntropy-Based Logistic Regression with Automatic Relevance Determination for Robust Sparse Brain Activity Decoding](https://mlsanity.com/paper/2207.09693/) (2022)
- [Efficient Graph Laplacian Estimation by Proximal Newton](https://mlsanity.com/paper/2302.06434/) (2023)
- [PRISE: Demystifying Deep Lucas-Kanade with Strongly Star-Convex Constraints for Multimodel Image Alignment](https://mlsanity.com/paper/2303.11526/) (2023)
- [Feature Space Sketching for Logistic Regression](https://mlsanity.com/paper/2303.14284/) (2023)
- [Machine Learning and the Future of Bayesian Computation](https://mlsanity.com/paper/2304.11251/) (2023)
- [Partial Maximum Correntropy Regression for Robust Trajectory Decoding from Noisy Epidural Electrocorticographic Signals](https://mlsanity.com/paper/2106.13086/) (2021)
- [Zeroth-Order Hard-Thresholding: Gradient Error vs. Expansivity](https://mlsanity.com/paper/2210.05279/) (2022)
- [Online Linearized LASSO](https://mlsanity.com/paper/2211.06039/) (2022)
- [Unified Transfer Learning Models in High-Dimensional Linear Regression](https://mlsanity.com/paper/2307.00238/) (2023)
- [Deep Loss Convexification for Learning Iterative Models](https://mlsanity.com/paper/2411.10649/) (2024)
- [On the instrumental variable estimation with many weak and invalid instruments](https://mlsanity.com/paper/2207.03035/) (2022)
- [High dimensional stochastic linear contextual bandit with missing covariates](https://mlsanity.com/paper/2207.11165/) (2022)
- [Adaptive Estimation of Graphical Models under Total Positivity](https://mlsanity.com/paper/2210.15471/) (2022)
- [Online Detection of Changes in Moment-Based Projections: When to Retrain Deep Learners or Update Portfolios?](https://mlsanity.com/paper/2302.07198/) (2023)

## Abstract (arXiv)

We provide novel theoretical results regarding local optima of regularized M-estimators, allowing for nonconvexity in both loss and penalty functions. Under restricted strong convexity on the loss and suitable regularity conditions on the penalty, we prove that any stationary point of the composite objective function will lie within statistical precision of the underlying parameter vector. Our theory covers many nonconvex objective functions of interest, including the corrected Lasso for errors-in-variables linear models; regression for generalized linear models with nonconvex penalties such as SCAD, MCP, and capped-ℓ1; and high-dimensional graphical model estimation. We quantify statistical accuracy by providing bounds on the ℓ1-, ℓ2-, and prediction error between stationary points and the population-level optimum. We also propose a simple modification of composite gradient descent that may be used to obtain a near-global optimum within statistical precision ε in log(1/ε) steps, which is the fastest possible rate of any first-order method. We provide simulation studies illustrating the sharpness of our theoretical results.