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

zbMATH Open1360.62276arXiv1305.2436MaRDI QIDQ5502126FDOQ5502126

Authors: Po-Ling Loh, Martin J. Wainwright 

Publication date: 17 August 2015

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-$el{l}_1$; and high-dimensional graphical model estimation. We quantify statistical accuracy by providing bounds on the $el{l}_1$-, $el{l}_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.

Full work available at URL: https://arxiv.org/abs/1305.2436

Recommendations

• Sparse recovery via nonconvex regularized \(M\)-estimators over \(\ell_q\)-balls
• Optimal computational and statistical rates of convergence for sparse nonconvex learning problems
• Statistical consistency and asymptotic normality for high-dimensional robust \(M\)-estimators
• Support recovery without incoherence: a case for nonconvex regularization
• I-LAMM for sparse learning: simultaneous control of algorithmic complexity and statistical error

zbMATH Keywords

model selectionhigh-dimensional statisticsnonconvex optimization\(M\)-estimationnonconvex regularization

Mathematics Subject Classification ID

Statistical ranking and selection procedures (62F07) Estimation in multivariate analysis (62H12) Ridge regression; shrinkage estimators (Lasso) (62J07) Applications of mathematical programming (90C90) Nonconvex programming, global optimization (90C26)

Cited In (only showing first 100 items - show all)

• Support recovery without incoherence: a case for nonconvex regularization
• Sparse recovery via nonconvex regularized \(M\)-estimators over \(\ell_q\)-balls
• Restricted strong convexity implies weak submodularity
• Functional additive regression
• Finite-sample analysis of \(M\)-estimators using self-concordance
• A New Principle for Tuning-Free Huber Regression
• Sorted concave penalized regression
• A general family of trimmed estimators for robust high-dimensional data analysis
• Composite difference-MAX programs for modern statistical estimation problems
• Statistical consistency and asymptotic normality for high-dimensional robust \(M\)-estimators
• Global solutions to folded concave penalized nonconvex learning
• Minimum distance Lasso for robust high-dimensional regression
• The finite sample properties of sparse M-estimators with pseudo-observations
• Pathwise coordinate optimization for sparse learning: algorithm and theory
• Rate optimal estimation and confidence intervals for high-dimensional regression with missing covariates
• Statistical Inference, Learning and Models in Big Data
• Distributed testing and estimation under sparse high dimensional models
• Learning Markov models via low-rank optimization
• Title not available (Why is that?)
• Graphical-model based high dimensional generalized linear models
• Folded concave penalized sparse linear regression: sparsity, statistical performance, and algorithmic theory for local solutions
• Endogeneity in high dimensions
• Sparse classification: a scalable discrete optimization perspective
• Broken adaptive ridge regression and its asymptotic properties
• I-LAMM for sparse learning: simultaneous control of algorithmic complexity and statistical error
• Penalised robust estimators for sparse and high-dimensional linear models
• A tight bound of hard thresholding
• Bayesian regularization for graphical models with unequal shrinkage
• Accelerated methods for nonconvex optimization
• Consistency bounds and support recovery of d-stationary solutions of sparse sample average approximations
• Multiparameter Regularization for Construction of Extrapolating Estimators in Statistical Learning Theory
• Non-local estimators: a new class of multigrid convergent length estimators
• Non-concave penalization in linear mixed-effect models and regularized selection of fixed effects
• Title not available (Why is that?)
• Bayesian Estimation of Gaussian Conditional Random Fields
• Optimality condition and complexity analysis for linearly-constrained optimization without differentiability on the boundary
• Lower bounds for finding stationary points I
• Minimum average variance estimation with group Lasso for the multivariate response central mean subspace
• A unified primal dual active set algorithm for nonconvex sparse recovery
• A convex-Nonconvex strategy for grouped variable selection
• Efficient learning with a family of nonconvex regularizers by redistributing nonconvexity
• Oracle inequalities for local and global empirical risk minimizers
• On the finite-sample analysis of \(\Theta\)-estimators
• High-dimensional rank-based graphical models for non-Gaussian functional data
• Bi-selection in the high-dimensional additive hazards regression model
• Iteratively reweighted \(\ell_1\)-penalized robust regression
• Sparse estimation via lower-order penalty optimization methods in high-dimensional linear regression
• Asymptotic linear expansion of regularized M-estimators
• Adaptive Huber Regression
• Stability of the minimizers of least squares with a non-convex regularization. II: Global behavior
• An outer-inner linearization method for non-convex and nondifferentiable composite regularization problems
• On an extension of the promotion time cure model
• The cost of privacy: optimal rates of convergence for parameter estimation with differential privacy
• Misspecified nonconvex statistical optimization for sparse phase retrieval
• Hypothesis testing in large-scale functional linear regression
• The robust desparsified lasso and the focused information criterion for high-dimensional generalized linear models
• Fast global convergence of gradient methods for high-dimensional statistical recovery
• Wavelet-based robust estimation and variable selection in nonparametric additive models
• Matrix completion with nonconvex regularization: spectral operators and scalable algorithms
• Analysis of generalized Bregman surrogate algorithms for nonsmooth nonconvex statistical learning
• Asymptotic properties on high-dimensional multivariate regression M-estimation
• The landscape of empirical risk for nonconvex losses
• Statistical analysis of sparse approximate factor models
• Penalized wavelet estimation and robust denoising for irregular spaced data
• Title not available (Why is that?)
• Going beyond oracle property: selection consistency and uniqueness of local solution of the generalized linear model
• Optimal prediction for sparse linear models? Lower bounds for coordinate-separable M-estimators
• GSDAR: a fast Newton algorithm for \(\ell_0\) regularized generalized linear models with statistical guarantee
• ROCKET: robust confidence intervals via Kendall's tau for transelliptical graphical models
• D4R: doubly robust reduced rank regression in high dimension
• Numerical characterization of support recovery in sparse regression with correlated design
• High-dimensional linear regression with hard thresholding regularization: theory and algorithm
• Sparse M-estimators in semi-parametric copula models
• Bias versus non-convexity in compressed sensing
• Non-convex projected gradient descent for generalized low-rank tensor regression
• Penalized Estimation of Frailty-Based Illness–Death Models for Semi-Competing Risks
• Group sparse structural smoothing recovery: model, statistical properties and algorithm
• A generalized formulation for group selection via ADMM
• A few theoretical results for Laplace and arctan penalized ordinary least squares linear regression estimators
• Regularized distributionally robust optimization with application to the index tracking problem
• Retire: robust expectile regression in high dimensions
• Projection Test for Mean Vector in High Dimensions
• Nonconvex regularization for sparse neural networks
• Hard thresholding regularised logistic regression: theory and algorithms
• A diffusion process perspective on posterior contraction rates for parameters
• Sample average approximation with sparsity-inducing penalty for high-dimensional stochastic programming
• Robust estimation and shrinkage in ultrahigh dimensional expectile regression with heavy tails and variance heterogeneity
• Robustness and Tractability for Non-convex M-estimators
• Asymptotic Properties of Stationary Solutions of Coupled Nonconvex Nonsmooth Empirical Risk Minimization
• On high-dimensional Poisson models with measurement error: hypothesis testing for nonlinear nonconvex optimization
• Zero-norm regularized problems: equivalent surrogates, proximal MM method and statistical error bound
• Asymptotic behaviour of penalized robust estimators in logistic regression when dimension increases
• A high-dimensional M-estimator framework for bi-level variable selection
• Rejoinder
• Semiparametric efficient estimation in high-dimensional partial linear regression models
• Sparse precision matrix estimation with missing observations
• Byzantine-robust distributed sparse learning for \(M\)-estimation
• On two recent nonconvex penalties for regularization in machine learning
• Building a telescope to look into high-dimensional image spaces
• Low-rank matrix estimation via nonconvex optimization methods in multi-response errors-in-variables regression

Uses Software

• glasso
• sparsenet

This page was built for publication: Regularized \(M\)-estimators with nonconvexity: statistical and algorithmic theory for local optima

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5502126)