Precise Error Analysis of Regularized M-estimators in High-dimensions

Abstract

A popular approach for estimating an unknown signal from noisy, linear measurements is via solving a so called \emph{regularized M-estimator}, which minimizes a weighted combination of a convex loss function and of a convex (typically, non-smooth) regularizer. We accurately predict the squared error performance of such estimators in the high-dimensional proportional regime. The random measurement matrix is assumed to have entries iid Gaussian, only minimal and rather mild regularity conditions are imposed on the loss function, the regularizer, and on the noise and signal distributions. We show that the error converges in probability to a nontrivial limit that is given as the solution to a minimax convex-concave optimization problem on four scalar optimization variables. We identify a new summary parameter, termed the Expected Moreau envelope to play a central role in the error characterization. The \emph{precise} nature of the results permits an accurate performance comparison between different instances of regularized M-estimators and allows to optimally tune the involved parameters (e.g. regularizer parameter, number of measurements). The key ingredient of our proof is the \emph{Convex Gaussian Min-max Theorem} (CGMT) which is a tight and strengthened version of a classical Gaussian comparison inequality that was proved by Gordon in 1988.

References in corpus (10)

• A framework to characterize performance of LASSO algorithms
• Various thresholds for ${\ell }_1$-optimization in compressed sensing
• Block-length dependent thresholds in block-sparse compressed sensing
• The generalized Lasso with non-linear observations
• Variance Breakdown of Huber (M)-estimators: $n/p\to m\in (1,\infty )$
• Robustness in sparse linear models: relative efficiency based on robust approximate message passing
• Meshes that trap random subspaces
• Upper-bounding ${\ell }_1$-optimization weak thresholds
• Maximin Analysis of Message Passing Algorithms for Recovering Block Sparse Signals
• BER Analysis of the box relaxation for BPSK Signal Recovery

Cited by in corpus (8)

• Phase Retrieval via Polytope Optimization: Geometry, Phase Transitions, and New Algorithms
• Phase Transitions in Transfer Learning for High-Dimensional Perceptrons
• On the Inherent Regularization Effects of Noise Injection During Training
• Optimization-based AMP for Phase Retrieval: The Impact of Initialization and ${\ell }_2$-regularization
• Overcoming The Limitations of Phase Transition by Higher Order Analysis of Regularization Techniques
• Precise Performance Analysis of the LASSO under Matrix Uncertainties
• Concentration of the Frobenius norm of generalized matrix inverses
• Low noise sensitivity analysis of Lq-minimization in oversampled systems