Research map / Learning theory and algorithms / Matrix and tensor methods

Nonconvex Theory of $M$-estimators with Decomposable Regularizers

ICML 2025 · Learning theory and algorithms › Matrix and tensor methods · approach: Nonconvex low-rank and sparse optimization

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Extends the Negahban et al. framework for regularized M-estimators with decomposable regularizers from convex to nonconvex losses, showing stationary points keep the restricted error set and recover convergence rates, illustrated on corrected linear regression and a Lasso variant with noise.

Problem

Regularized M-estimation theory in high dimensions (Negahban et al. 2009) assumes a convex loss; many high-dimensional losses (noisy/missing-data corrected regression, mixture models) are nonconvex, so it is unclear whether error cone containment and convergence rates survive.

Approach

Shows that the error cone containment (Proposition 2.2) holds for any first-order stationary point without convexity, and replaces convex-loss RSC with a stationarity-compatible RSC condition on gradient differences to recover the l2 rate; applies this to corrected linear regression (noisy/missing covariates) and a Lasso with noise variance parameter.

Key results

• Theorem 3.1 shows that for any stationary point of the regularized M-estimator, the error lies in the same restricted set C(M, M-bar-perp) as in the convex case.
• Theorem 3.3 gives the l2 error bound ||theta_hat - theta*||^2 <= eps_n^2 for any stationary point under a weaker RSC condition when tau_n^2 Psi^2(M-bar) <= kappa/128.
• For noisy/missing corrected linear regression (Theorem 4.2) and noisy Lasso (Theorem 4.6), the paper derives s-sparse l2 error bounds of order sqrt(s log d / n) with high probability.

Limitations

• Results are only illustrated on two simple examples without experiments.
• Requires a bound on the dual norm and an RSC condition assumed to hold for the nonconvex loss, with sample size requirements n >= c s log d.
• The paper does not analyze global optima or whether stationary points are statistically good beyond the stated bounds.

Experimental setup

Baselines: Negahban et al. 2009 convex framework Loh & Wainwright 2015 nonconvex regularizer results

Builds on: Negahban et al. 2009 unified framework Loh & Wainwright 2012 Loh & Wainwright 2015 Wainwright 2019 high-dimensional statistics

Closest papers by meaning

• An equivalence between high dimensional Bayes optimal inference and M-estimation (NeurIPS 2016 · similarity 0.86)
• Statistical Limits of Adaptive Linear Models: Low-Dimensional Estimation and Inference (NeurIPS 2023 · similarity 0.85)
• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval and Matrix Completion (ICML 2018 · similarity 0.84)
• Graphical Nonconvex Optimization via an Adaptive Convex Relaxation (ICML 2018 · similarity 0.84)
• A Non-Asymptotic Moreau Envelope Theory for High-Dimensional Generalized Linear Models (NeurIPS 2022 · similarity 0.84)
• Bounds on $L_p$ Errors in Density Ratio Estimation via $f$-Divergence Loss Functions (ICLR 2025 · similarity 0.82)