Sharp Asymptotics and Optimal Performance for Inference in Binary Models

Hossein Taheri, Ramtin Pedarsani, Christos Thrampoulidis

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. This allows for a precise comparison between different loss functions. We then establish fundamental limits on the performance of any convex estimator and identify the optimal loss function for specific models. Notably, we find that simple Least Squares is nearly optimal for common models like Logistic and Probit regression.

Introduction

In modern statistical learning, we frequently encounter high-dimensional datasets where the number of features $n$ is comparable to the number of observations $m$. In this regime, classical asymptotic theory—which assumes $m \gg n$—fails to provide accurate predictions. While significant progress has been made in understanding high-dimensional linear regression, binary classification models present unique challenges due to the discrete nature of the outputs ($\pm 1$).

This work addresses three fundamental questions:

  1. Can we precisely predict the correlation between an estimate and the true signal for any convex loss function?
  2. Is there an absolute theoretical limit to the performance of convex estimators?
  3. Which loss functions are most efficient, and how do standard choices like Logistic or Hinge loss compare to the theoretical optimum?

Methodology: The Convex Gaussian Min-Max Theorem

The core of our analysis relies on the Convex Gaussian Min-Max Theorem (CGMT). This framework allows us to reduce a complex, high-dimensional stochastic optimization problem into a deterministic one involving only three scalar variables. By analyzing the properties of Empirical Risk Minimization (ERM) through Moreau Envelopes, we can derive sharp asymptotic predictions for the estimator's performance.

The performance of an estimator is characterized by its correlation with the true signal vector $\mathbf{x}_0$. Our theory shows that this correlation is entirely determined by a single "effective noise" parameter, $\sigma_\ell$, which is the solution to a system of three non-linear equations.

Performance in the Signed Model

We first consider the "Signed" model, where observations are generated as $y = \text{sign}(\mathbf{a}^T \mathbf{x}_0)$. We compare the performance of Least Absolute Deviation (LAD), Least Squares (LS), and a theoretically derived optimal loss function.

Figure 1: Comparison of theoretical predictions and empirical results for the Signed model.

As shown in Figure 1, our theoretical curves (solid and dashed lines) perfectly match the empirical simulations (markers), even for moderate dimensions ($n=128$). The optimal loss function provides a clear upper bound on performance, while LS and LAD show distinct behaviors as the measurement ratio $\delta = m/n$ varies.

The Surprising Efficiency of Least Squares

A key contribution of this work is the evaluation of standard loss functions against the information-theoretic optimal convex estimator. For models like Logistic and Probit regression, we find that the Least Squares (LS) estimator—often overlooked for classification tasks—is remarkably efficient.

Figure 2: Performance comparison in the Logistic model, demonstrating the near-optimality of Least Squares and the existence of a phase transition.

In the Logistic model (Figure 2), LS achieves over 99.7% of the performance of the optimal convex estimator. Similarly, for the Probit model, it reaches at least 98.0% efficiency. This suggests that in high-dimensional settings, the choice of a complex loss function may offer diminishing returns over simpler alternatives. Furthermore, we observe phase transitions for Logistic and Hinge losses; they only yield stable solutions when the data is sufficiently separable, typically requiring $\delta$ to exceed a specific threshold (indicated by the vertical dashed line).

Conclusion

This paper provides a rigorous framework for predicting and optimizing the performance of convex estimators in high-dimensional binary classification. By establishing sharp asymptotics and fundamental limits, we reveal that simple estimators like Least Squares are surprisingly close to optimal for standard models. Future work will focus on relaxing the Gaussian assumption for feature vectors and extending these results to the undersampled regime ($\delta < 1$) using regularized estimators.

Summary updated

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 asymptoti...
BibTeX
@inproceedings{taheri2020sharp,
  author = {Hossein Taheri and Ramtin Pedarsani and Christos Thrampoulidis},
  title = {{Sharp Asymptotics and Optimal Performance for Inference in Binary Models}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2020},
  url = {https://openreview.net/forum?id=Q-CXvajy8ep},
}
Figure