Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published August 2018 | public
Journal Article

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

Abstract

A popular approach for estimating an unknown signal x_0 ∈ ℝ^n from noisy, linear measurements y = Ax_0 + z ∈ ℝ^m is via solving a so called regularized M-estimator: x:= arg min_x L(y – Ax) + λf(x). Here, L is a convex loss function, f is a convex (typically, non-smooth) regularizer, and, λ > 0 is a regularizer parameter. We analyze the squared error performance ‖x – x_0‖^2_2 of such estimators in the high-dimensional proportional regime where m,n → ∞ and m/n → δ. The design 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 squared 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 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 (such as the regularizer parameter, the number of measurements, etc.). The key ingredient of our proof is the 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.

Additional Information

© 2018 IEEE. Manuscript received March 17, 2016; revised September 20, 2017; accepted March 03, 2018. The work of B. Hassibi was supported in part by the National Science Foundation under grants CNS-0932428, CCF-1018927, CCF-1423663 and CCF-1409204, by the Office of Naval Research under the MURI grant N00014-08–0747, by a grant from Qualcomm Inc., and by King Abdulaziz University. C.T. would like to thank George Moustakides, Joel Tropp, P. P. Vaidyanathan and Panagiotis Vergados for helpful conversations and suggestions. Also, thanks to Ashkan Panahi and Linqi (Daniel) Guo; some of the ideas that led to this work were born in collaboration with them, cf. [34], [35].

Additional details

Created:
August 19, 2023
Modified:
March 5, 2024