Sharp Asymptotics and Optimal Performance for Inference in Binary Models
Hossein Taheri, Ramtin Pedarsani, and Christos Thrampoulidis Department of Electrical and Computer Engineering, University of California, Santa Barbara. ††Part of this work to appear in the 23rd International Conference on Artificial Intelligence and Statistics (AISTATS), 2020. Emails: {hossein, ramtin,
Abstract
We study convex empirical risk minimization for high-dimensional inference in binary models. Our first result sharply predicts the statistical performance of such estimators in the linear asymptotic regime under isotropic Gaussian features. Importantly, the predictions hold for a wide class of convex loss functions, which we exploit in order to prove a bound on the best achievable performance among them. Notably, we show that the proposed bound is tight for popular binary models (such as Signed, Logistic or Probit), by constructing appropriate loss functions that achieve it. More interestingly, for binary linear classification under the Logistic and Probit models, we prove that the performance of least-squares is no worse than 0.997 and 0.98 times the optimal one. Numerical simulations corroborate our theoretical findings and suggest they are accurate even for relatively small problem dimensions.
中文速览
在高维二分类问题中，研究者长期面临一个困境：当样本数和参数数量同等量级时，用凸优化做经验风险最小化（empirical risk minimization）效果究竟有多好，不同损失函数之间差距有多大，却缺乏精确的理论刻画。这篇论文针对带等方向高斯特征的二元观测模型（包括 Signed、Logistic、Probit 等），给出了一套精确渐近分析框架：通过凸高斯极小极大定理（CGMT）推导出一个仅含三个非线性方程的方程组，就能精确预测任意凸损失函数对应估计量的相关性表现。在此基础上，论文进一步给出了所有凸损失函数可达性能的理论上界，并为多种常见模型构造出能够达到该上界的最优损失函数；尤为出人意料的是，对 Logistic 和 Probit 模型，论文严格证明了最简单的最小二乘损失的表现不低于最优性能的 99.7% 和 98%，几乎无需付出任何代价。这一系列精确结论不仅澄清了高维二分类中损失函数选择的理论边界，也为实际系统设计提供了坚实的理论依据。
原文 arXiv:2002.07284;中英对照 + 大白话阅读 https://aha.fim.ai/paper/2002.07284v2