Precise Error Analysis of Regularized $M$ -Estimators in High Dimensions
Precise Error Analysis of Regularized $M$ -Estimators in High Dimensions
复制标题
DOI：
10.1109/tit.2018.2840720
复制
发表时间：
2016-01
影响因子：
2.5
通讯作者：
Christos Thrampoulidis;Ehsan Abbasi;B. Hassibi
中科院分区：
文献类型：
--
作者：
Christos Thrampoulidis;Ehsan Abbasi;B. Hassibi
一种流行的方法，用于估计未知信号$ \ mathbf {x} _ {0} \ in \ Mathbb {r} x} _ {0}+ \ \ \ \ m athbf {z} \ in \ mathbb {r}^{m} $是通过求解一个所谓的正规化$ m $ - 示数器：$ \ hat {\ mathbf {x}}}}：= \ arg arg \ min _ \ mathbf {x} \ mathcal {x Mathcal {l}（\ Mathbf {y} - \ Mathbf {a} \ Mathbf {x}）+\ lambda f（\ mathbf {x}）$。在这里，$ \ MATHCAL {l} $是凸损失函数，$ f $是凸（通常是非平滑的）正常化程序，$ \ lambda> 0 $是正常的参数。我们分析平方错误性能$ \ | \ hat {\ mathbf {x}} - \ MathBf {x} _ {0} \ | _ {2}^{2}^{2} $ $ m，n \ rightarrow \ infty $和$ m/n \ rightarrow \ delta $。假定设计矩阵$ \ mathbf {a} $具有iid gaussian的条目；仅对损耗函数，正规器以及噪声和信号分布施加最小和相当轻微的规律条件。我们表明，在四个标量式优化变量上，平方误差的概率收敛到非平凡限制，作为对Minimax convex-concave优化问题的解决方案。我们确定了一个新的摘要参数，称为预期的Moreau包络，以在误差表征中发挥核心作用。结果的确切性质允许在不同实例$ m $估计器的不同实例之间进行准确的性能比较，并允许最佳调整所涉及的参数（例如正常化程序参数和测量数）。我们证明的关键要素是凸高斯最低 - 最大定理，这是戈登在1988年证明的经典高斯比较不平等的紧密而增强的版本。
A popular approach for estimating an unknown signal $ \mathbf {x}_{0}\in \mathbb {R} ^{n}$ from noisy, linear measurements $ \mathbf {y}= \mathbf {A} \mathbf {x} _{0}+ \mathbf {z}\in \mathbb {R}^{m}$ is via solving a so called regularized $M$ -estimator: $\hat{\mathbf {x}} :=\arg \min _ \mathbf {x} \mathcal {L} (\mathbf {y}- \mathbf {A} \mathbf {x})+\lambda f(\mathbf {x})$ . Here, $ \mathcal {L}$ is a convex loss function, $f$ is a convex (typically, non-smooth) regularizer, and $\lambda > 0$ is a regularizer parameter. We analyze the squared error performance $\|\hat{\mathbf {x}} - \mathbf {x}_{0}\|_{2}^{2}$ of such estimators in the high-dimensional proportional regime where $m,n\rightarrow \infty $ and $m/n\rightarrow \delta $ . The design matrix $ \mathbf {A}$ 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 and the number of measurements). The key ingredient of our proof is the convex Gaussian min-max theorem which is a tight and strengthened version of a classical Gaussian comparison inequality that was proved by Gordon in 1988.