Sharp Asymptotics and Optimal Performance for Inference in Binary Models

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.

References in corpus (7)

• Message Passing Algorithms for Compressed Sensing
• A framework to characterize performance of LASSO algorithms
• The LASSO with Non-linear Measurements is Equivalent to One With Linear Measurements
• The generalization error of max-margin linear classifiers: Benign overfitting and high dimensional asymptotics in the overparametrized regime
• Asymptotic behavior of unregularized and ridge-regularized high-dimensional robust regression estimators : rigorous results
• Various thresholds for ${\ell }_1$-optimization in compressed sensing
• Phase Retrieval via Polytope Optimization: Geometry, Phase Transitions, and New Algorithms

Cited by in corpus (5)

• A Precise High-Dimensional Asymptotic Theory for Boosting and Minimum-${\ell }_1$-Norm Interpolated Classifiers
• When Does Preconditioning Help or Hurt Generalization?
• Regularization in High-Dimensional Regression and Classification via Random Matrix Theory
• High Dimensional Classification via Regularized and Unregularized Empirical Risk Minimization: Precise Error and Optimal Loss
• Asymptotic Behavior of Adversarial Training in Binary Classification