  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.
