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 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.

Introduction

In classical statistical theory, the number of observations ($m$) is typically assumed to be much larger than the number of parameters ($n$). However, modern data science frequently encounters "high-dimensional" scenarios where $m$ and $n$ are of the same order. In this regime, traditional asymptotic tools often fail to provide accurate performance guarantees. While recent progress has been made in understanding linear regression in high dimensions, binary classification models—where outputs are discrete labels—present unique analytical challenges.

This paper addresses these challenges by providing a precise mathematical framework to predict the performance of convex optimization methods, such as Logistic Regression and Least-Squares, in high-dimensional binary classification.

Theoretical Framework: The CGMT Approach

The authors utilize the Convex Gaussian Min-Max Theorem (CGMT) to analyze Empirical Risk Minimization (ERM) for a broad class of convex loss functions. The CGMT allows for the reduction of a complex, high-dimensional optimization problem into a manageable system of three non-linear equations with three unknowns.

Key to this analysis is the characterization of estimators through Moreau Envelopes, which effectively smooth the loss functions. By establishing fundamental lower bounds on estimation error using the Fisher Information of the "effective noise," the authors define the theoretical limits of performance for any convex loss function. This approach also provides a recipe for designing "optimal" loss functions tailored to specific data-generating processes by inverting the Moreau envelope.

Key Insights: The Efficiency of Simple Methods

A central finding of the research is the "effective noise" parameter, $\sigma_\ell$. The statistical performance of any convex estimator is essentially determined by this single value; minimizing $\sigma_\ell$ maximizes the correlation between the estimate and the true signal.

One of the most striking results is the near-optimality of Least-Squares (LS) for common probabilistic models. Although LS is typically intended for continuous regression, the authors prove that for Logistic and Probit models, it achieves nearly the same performance as the best possible convex estimator. Specifically, LS achieves at least 99.72% of the optimal correlation for Logistic models and 98.04% for Probit models. This suggests that in many practical high-dimensional settings, the added complexity of specialized loss functions may offer diminishing returns.

Furthermore, the paper characterizes separability thresholds. For loss functions like Logistic or Hinge loss, there is a critical ratio of observations to parameters ($\delta = m/n$). Below this threshold, the data becomes linearly separable, and the optimization solution can diverge—a phenomenon the authors' framework precisely quantifies.

Numerical Validation and Results

The theoretical predictions were tested against numerical simulations using synthetic data with Gaussian features. The results demonstrate that the asymptotic theory holds even for relatively small dimensions (e.g., $n=128$).

Comparison of performance metrics and loss functions across different models and sampling ratios.

As shown in the figure above, the theoretical curves for Least Absolute Deviation (LAD), Least-Squares (LS), and the derived Optimal loss function align closely with empirical data points. The right panel illustrates how the optimal loss function evolves with the sampling ratio $\delta = m/n$. The precision of these predictions is further highlighted in the following table, which compares predicted versus empirical performance across various values of $\delta$.

Predicted vs. Empirical performance values for varying sampling ratios.

Conclusion and Future Directions

This work establishes a "best achievable performance" bound for all convex loss functions in high-dimensional binary classification, providing a rigorous benchmark for algorithm design. While the current study assumes Gaussian features and focuses on binary labels, it opens several avenues for future research, including the investigation of non-Gaussian features, multi-class classification, and the potential benefits of non-convex optimization in breaking established fundamental limits.

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 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.
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