Fundamental Limits of Ridge -Regularized Empirical Risk Minimization in High Dimensions
Hossein Taheri, Ramtin Pedarsani, and Christos Thrampoulidis ††All authors are with the Electrical and Computer Engineering Department, University of California, Santa Barbara, Santa Barbara, CA 93106, USA. Emails: {hossein, ramtin, .
Abstract
Empirical Risk Minimization (ERM) algorithms are widely used in a variety of estimation and prediction tasks in signal-processing and machine learning applications. Despite their popularity, a theory that explains their statistical properties in modern regimes where both the number of measurements and the number of unknown parameters is large is only recently emerging. In this paper, we characterize for the first time the fundamental limits on the statistical accuracy of convex ERM for inference in high-dimensional generalized linear models. For a stylized setting with Gaussian features and problem dimensions that grow large at a proportional rate, we start with sharp performance characterizations and then derive tight lower bounds on the estimation and prediction error that hold over a wide class of loss functions and for any value of the regularization parameter. Our precise analysis has several attributes. First, it leads to a recipe for optimally tuning the loss function and the regularization parameter. Second, it allows to precisely quantify the sub-optimality of popular heuristic choices: for instance, we show that optimally-tuned least-squares is (perhaps surprisingly) appr
中文速览
在高维场景下，当测量数量和未知参数数量同量级增长时，经验风险最小化（Empirical Risk Minimization, ERM）该如何选择损失函数和正则化参数、其统计精度的极限究竟在哪里，此前缺乏系统性的理论回答。这篇论文针对高斯特征的广义线性模型（Generalized Linear Models, GLM），通过分析一组刻画ERM渐近误差的非线性方程组的代数结构，首次推导出凸ERM在估计误差和预测误差上的紧下界，并给出了最优调参的具体方案。研究发现，对于标准逻辑回归数据，经过最优调参的最小二乘法意外地接近最优，但随着信号强度增大，其次优差距会急剧扩大；同时，论文还精确刻画了岭正则化在不同过参数化比例下的收益。这些界与经典统计学中的Fisher信息（Fisher Information）直接挂钩，将高维渐近理论与经典统计基础紧密联系起来，为高维推断中损失函数与正则化的设计提供了坚实的理论依据。
原文 arXiv:2006.08917;中英对照 + 大白话阅读 https://aha.fim.ai/paper/2006.08917v2