Regularized M-estimators with nonconvexity: Statistical and algorithmic theory for local optima
arXiv:1305.2436
Abstract
We provide novel theoretical results regarding local optima of regularized -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-; and high-dimensional graphical model estimation. We quantify statistical accuracy by providing bounds on the -, -, 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 steps, which is the fastest possible rate of any first-order method. We provide simulation studies illustrating the sharpness of our theoretical results.
arXiv comment58 pages, 13 figures. To appear in JMLR
References in corpus (2)
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
- -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