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

Abstract

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 \emph{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-${\ell }_1$; and high-dimensional graphical model estimation. We quantify statistical accuracy by providing bounds on the ${\ell }_1$-, ${\ell }_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 $\epsilon$ in $\log (1/\epsilon )$ steps, which is the fastest possible rate of any first-order method. We provide simulation studies illustrating the sharpness of our theoretical results.

58 pages, 13 figures. To appear in JMLR

References in corpus (1)

• Nearly unbiased variable selection under minimax concave penalty

Cited by in corpus (61)

• Challenges of Big Data Analysis
• Deeply-Supervised Nets
• Guaranteed Matrix Completion via Non-convex Factorization
• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• Functional additive regression
• Endogeneity in high dimensions
• The Landscape of Empirical Risk for Non-convex Losses
• Statistical Inference, Learning and Models in Big Data
• Convergence guarantees for a class of non-convex and non-smooth optimization problems
• Local Maxima in the Likelihood of Gaussian Mixture Models: Structural Results and Algorithmic Consequences
• Nonconvex Sparse Logistic Regression with Weakly Convex Regularization
• Vector-Valued Graph Trend Filtering with Non-Convex Penalties
• Oracle Estimation of a Change Point in High Dimensional Quantile Regression
• Sparse Classification: a scalable discrete optimization perspective
• Optimal Change Point Detection and Localization in Sparse Dynamic Networks
• Global solutions to folded concave penalized nonconvex learning
• Nonconvex Sparse Learning via Stochastic Optimization with Progressive Variance Reduction
• A General Theory of Hypothesis Tests and Confidence Regions for Sparse High Dimensional Models
• Local and Global Inference for High Dimensional Nonparanormal Graphical Models
• Robust Estimation of High-Dimensional Mean Regression
• An unbiased approach to compressed sensing
• Fully Bayesian Classification with Heavy-tailed Priors for Selection in High-dimensional Features with Grouping Structure
• A Unified Computational and Statistical Framework for Nonconvex Low-Rank Matrix Estimation
• TraDE: Transformers for Density Estimation
• Towards Faster Rates and Oracle Property for Low-Rank Matrix Estimation
• Between hard and soft thresholding: optimal iterative thresholding algorithms
• Correntropy-Based Logistic Regression with Automatic Relevance Determination for Robust Sparse Brain Activity Decoding
• Optimal network online change point localisation
• Generalized Kalman Smoothing: Modeling and Algorithms
• A Unified Framework for Low-Rank plus Sparse Matrix Recovery
• Alternating minimization and alternating descent over nonconvex sets
• Iterative Hard Thresholding for Model Selection in Genome-Wide Association Studies
• The log-shift penalty for adaptive estimation of multiple Gaussian graphical models
• Gradient descent with nonconvex constraints: local concavity determines convergence
• Linear convergence of SDCA in statistical estimation
• High-dimensional robust approximated M-estimators for mean regression with asymmetric data
• Towards Optimal Problem Dependent Generalization Error Bounds in Statistical Learning Theory
• A High-dimensional M-estimator Framework for Bi-level Variable Selection
• Bias Reduction in Compressed Sensing
• Nonregular and Minimax Estimation of Individualized Thresholds in High Dimension with Binary Responses
• SAGA and Restricted Strong Convexity
• A note relating ridge regression and OLS p-values to preconditioned sparse penalized regression
• Non-bifurcating phylogenetic tree inference via the adaptive LASSO
• ${\ell }_1$-penalized Multinomial Regression: Estimation, inference, and prediction, with an application to risk factor identification for different dementia subtypes
• Online Learning and Decision-Making under Generalized Linear Model with High-Dimensional Data
• MOCCA: mirrored convex/concave optimization for nonconvex composite functions
• Nonconvex penalized multitask regression using data depth-based penalties
• A Bregman Method for Structure Learning on Sparse Directed Acyclic Graphs
• Sparse Regression for Extreme Values
• Optimal prediction for sparse linear models? Lower bounds for coordinate-separable M-estimators
• High-Dimensional Semiparametric Selection Models: Estimation Theory with an Application to the Retail Gasoline Market
• Nonconvex Penalization in Sparse Estimation: An Approach Based on the Bernstein Function
• High Dimensional Multivariate Regression and Precision Matrix Estimation via Nonconvex Optimization
• Sparse Optimization on General Atomic Sets: Greedy and Forward-Backward Algorithms
• Projection-Free Algorithms in Statistical Estimation
• On the Conditions of Sparse Parameter Estimation via Log-Sum Penalty Regularization
• A Greedy Homotopy Method for Regression with Nonconvex Constraints
• Fast Global Convergence via Landscape of Empirical Loss
• On the Impossibility of Convex Inference in Human Computation
• A Knowledge Transfer Framework for Differentially Private Sparse Learning
• Estimation Rates for Sparse Linear Cyclic Causal Models