Sharp Guarantees and Optimal Performance for Inference in Binary and Gaussian-Mixture Models ^†

Abstract

We study convex empirical risk minimization for high-dimensional inference in binary linear classification under both discriminative binary linear models, as well as generative Gaussian-mixture models. Our first result sharply predicts the statistical performance of such estimators in the proportional asymptotic regime under isotropic Gaussian features. Importantly, the predictions hold for a wide class of convex loss functions, which we exploit to prove bounds on the best achievable performance. Notably, we show that the proposed bounds are tight for popular binary models (such as signed and logistic) and for the Gaussian-mixture model by constructing appropriate loss functions that achieve it. Our numerical simulations suggest that the theory is accurate even for relatively small problem dimensions and that it enjoys a certain universality property.

1. Introduction

1.1. Motivation

Classical estimation theory studies problems in which the number of unknown parameters n is small compared to the number of observations m. In contrast, modern inference problems are typically high-dimensional, that is n can be of the same order as m. Examples are abundant in a wide range of signal processing and machine learning applications such as medical imaging, wireless communications, recommendation systems, etc. Classical tools and theories are not applicable in these modern inference problems [1]. As such, over the last two decades or so, the study of high-dimensional estimation problems has received significant attention.

Perhaps the most well-studied setting is that of noisy linear observations (namely, linear regression). The literature on the topic is vast with remarkable contributions from the statistics, signal processing and machine learning communities. Several recent works focus on the proportional/linear asymptotic regime and derive sharp results on the inference performance of appropriate convex optimization methods (e.g., [2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23]). These works show that, albeit challenging, sharp results are advantageous over loose order-wise bounds. Not only do they allow for accurate comparisons between different choices of the optimization parameters, but they also form the basis for establishing optimal such choices as well as fundamental performance limitations (e.g., [12,14,15,16,24,25,26]).

This paper takes this recent line of work a step further by demonstrating that results of this nature can be achieved in binary observation models. While we depart from the previously studied linear regression model, we remain faithful to the requirement and promise of sharp results. Binary models are popularly applicable in a wide range of signal-processing (e.g., highly quantized measurements) and machine learning (e.g., binary classification) problems. We derive sharp asymptotics for a rich class of convex optimization estimators, which include least-squares, logistic regression and hinge loss as special cases. Perhaps more interestingly, we use these results to derive fundamental performance limitations and design optimal loss functions that provably outperform existing choices. Our results hold both for discriminative and generative data models.

In Section 1.2, we formally introduce the problem setup. The paper’s main contributions and organization are presented in Section 1.4. A detailed discussion of prior art follows in Section 1.5.

Notation 1.

The symbols $\mathbb{P}(·)$, $\mathbb{E}\left[·\right]$ and $\mathit{Var}[·]$ denote probability, expectation and variance, respectively. We use boldface notation for vectors. ${\parallel \mathbf{v}\parallel }_2$ denotes the Euclidean norm of a vector $\mathbf{v}$. We write $i\in \left[m\right]$ for $i=1,2,\dots ,m$. When writing $x_{*}=arg{min}_{x}f\left(x\right),$ we let the operator $argmin$ return any one of the possible minimizers of f. For all $x\in \mathbb{R}$, $\Phi \left(x\right)$ is the cumulative distribution function of standard normal and Gaussian Q-function at x is defined as $Q\left(x\right)=1-\Phi \left(x\right).$

1.2. Data Models

Consider m data pairs ${(y_i,{\mathbf{a}}_i)}_{i=1}^m$ generated i.i.d from one of the following two models such that $y_i\in \{-1,+1\}$ and ${\mathbf{a}}_i\in {\mathbb{R}}^n$ for all $i\in \left[m\right]$.

Binary models with Gaussian features: Here, the feature/measurement vectors ${\mathbf{a}}_i,i\in \left[n\right]$ have i.i.d Gaussian entries, i.e., ${\mathbf{a}}_i\sim \mathcal{N}(0,{\mathbf{I}}_n).$ Given the feature vector ${\mathbf{a}}_i$, the corresponding label takes the form

$$\begin{array}{c}\hfill y_i=f\left({\mathbf{a}}_i^T{\mathbf{x}}_0\right),i\in \left[m\right],\end{array}$$

(1)

for some unknown true signal ${\mathbf{x}}_0\in {\mathbb{R}}^n$ and a label/link function $f:\mathbb{R}\to \{-1,+1\}$ a (possibly random) binary function. Some popular examples for the label function f include the following:

• (Noisy) Signed: $\left\{\begin{array}{cc}\mathrm{sign}\left({\mathbf{a}}_i^T{\mathbf{x}}_0\right)\hfill & ,\mathrm{w}.\mathrm{p}.1-\epsilon ,\hfill \\ -\mathrm{sign}\left({\mathbf{a}}_i^T{\mathbf{x}}_0\right)\hfill & ,\mathrm{w}.\mathrm{p}.\epsilon ,\hfill \end{array}\right.\mathrm{where}\epsilon \in [0,1/2].$
• Logistic: $y_i=\left\{\begin{array}{cc}+1\hfill & ,\mathrm{w}.\mathrm{p}.\frac{1}{1+exp\left(-{\mathbf{a}}_i^T{\mathbf{x}}_0\right)},\hfill \\ -1\hfill & ,\mathrm{w}.\mathrm{p}.1-\frac{1}{1+exp\left(-{\mathbf{a}}_i^T{\mathbf{x}}_0\right)}.\hfill \end{array}\right.$
• Probit: $y_i=\left\{\begin{array}{cc}+1\hfill & ,\mathrm{w}.\mathrm{p}.\Phi \left({\mathbf{a}}_i^T{\mathbf{x}}_0\right),\hfill \\ -1\hfill & ,\mathrm{w}.\mathrm{p}.1-\Phi \left({\mathbf{a}}_i^T{\mathbf{x}}_0\right).\hfill \end{array}\right.$

We remark that when the signal strength $\parallel {\mathbf{x}}_0{\parallel }_2\to +\infty$, logistic and Probit label functions approach the signed model (i.e., noisy-signed function with $\epsilon =0$).

Throughout, we assume that $\parallel {\mathbf{x}}_0{\parallel }_2=1$. This assumption is without loss of generality since the norm of ${\mathbf{x}}_0$ can always be absorbed in the link function. Indeed, letting $\parallel {\mathbf{x}}_0{\parallel }_2=r$, we can always write the measurements as $f\left({\mathbf{a}}^T{\mathbf{x}}_0\right)=\tilde{f}\left({\mathbf{a}}^T{\tilde{\mathbf{x}}}_0\right)$, where ${\tilde{\mathbf{x}}}_0={\mathbf{x}}_0/r$ (hence, $\parallel {\tilde{\mathbf{x}}}_0{\parallel }_2=1$) and $\tilde{f}\left(t\right)=f\left(rt\right)$. We make no further assumptions on the distribution of the true vector ${\mathbf{x}}_0$.

Gaussian-mixture model: In Section 5, we also study the following generative Gaussian-mixture model (GMM):

$$\begin{array}{c}\hfill y_i=\left\{\begin{array}{cc}+1\hfill & ,\mathrm{w}.\mathrm{p}.\pi ,\hfill \\ -1\hfill & ,\mathrm{w}.\mathrm{p}.1-\pi ,\hfill \end{array}\right.,{\mathbf{a}}_i|y_i\sim \mathcal{N}(y_i{\mathbf{x}}_0,{\mathbf{I}}_n),i\in \left[m\right].\end{array}$$

(2)

Above, $\pi \in [0,1]$ is the prior of class $+1$ and ${\mathbf{x}}_0\in {\mathbb{R}}^n$ is the true signal, which here represents the mean of the features.

1.3. Empirical Risk Minimization

We study the performance of empirical-risk minimization (ERM) estimators ${\widehat{\mathbf{x}}}_{\ell }$ of ${\mathbf{x}}_0$ that solve the following optimization problem for some convex loss function $\ell :\mathbb{R}\to \mathbb{R}$

$$\begin{array}{c}\hfill {\widehat{\mathbf{x}}}_{\ell }:=arg\underset{\mathbf{x}}{min}\frac{1}{m}\sum _{i=1}^m\ell \left(y_i{\mathbf{a}}_i^T\mathbf{x}\right).\end{array}$$

(3)

Loss function. Different choices for ℓ lead to popular specific estimators including the following:

• Least Squares (LS):$\ell \left(t\right)={(t-1)}^2$,
• Least-Absolute Deviations (LAD):$\ell \left(t\right)=|t-1|$,
• Logistic Loss:$\ell \left(t\right)=log(1+exp(-t\left)\right)$,
• Exponential Loss:$\ell \left(t\right)=exp\left(-t\right)$,
• Hinge Loss:$\ell \left(t\right)=max\{1-t,0\}$.

Performance Measure. We measure performance of the estimator ${\widehat{\mathbf{x}}}_{\ell }$ by the value of its correlation to ${\mathbf{x}}_0$, i.e.,

$$\begin{array}{c}\hfill \mathrm{corr}\left({\widehat{\mathbf{x}}}_{\ell };{\mathbf{x}}_0\right):=\frac{\langle {\widehat{\mathbf{x}}}_{\ell },{\mathbf{x}}_0\rangle }{\parallel {\widehat{\mathbf{x}}}_{\ell }{\parallel }_2{\parallel {\mathbf{x}}_0\parallel }_2}\in [-1,1].\end{array}$$

(4)

Obviously, we seek estimates that maximize correlation. While correlation is the measure of primal interest, our results extend rather naturally to other prediction metrics, such as classification error given by (e.g., see [27] (Section D.2.)),

$$\begin{array}{c}\hfill {\mathcal{E}}_{\ell }:={\mathbb{E}}_{\mathbf{a},y}\left[{\mathbb{1}}_{\left\{y\ne \mathrm{sign}\left(\langle {\widehat{\mathbf{x}}}_{\ell },\mathbf{a}\rangle \right)\right\}}\right].\end{array}$$

(5)

Expectation in (5) is derived based on a test sample $(\mathbf{a},y)$ from the same distribution of the training set.

1.4. Contributions and Organization

As mentioned, our techniques naturally apply to both binary Gaussian and Gaussian-mixture models. For concreteness, we focus our presentation on the former models (see Section 2, Section 3 and Section 4.1). Then, we extend our results to Gaussian mixtures in Section 5. Numerical simulations corroborating our theoretical findings for both models are presented in Section 6.

Now, we state the paper’s main contributions:

• Precise Asymptotics: We show that the absolute value of correlation of ${\widehat{\mathbf{x}}}_{\ell }$ to the true vector ${\mathbf{x}}_0$ is sharply predicted by $\sqrt{1/(1+{\sigma }_{\ell }^2)}$ where the “effective noise” parameter ${\sigma }_{\ell }$ can be explicitly computed by solving a system of three non-linear equations in three unknowns. We find that the system of equations (and, thus, the value of ${\sigma }_{\ell }$) depends on the loss function ℓ through its Moreau envelope function. Our prediction holds in the linear asymptotic regime in which $m,n\to \infty$ and $m/n\to \delta >1$ (see Section 2).
• Fundamental Limits: We establish fundamental limits on the performance of convex optimization-based estimators by computing an upper bound on the best possible correlation performance among all convex loss functions. We compute the upper bound by solving a certain nonlinear equation and we show that such a solution exists for all $\delta >1$ (see Section 3.1).
• Optimal Performance and (sub)-optimality of LS for binary models: For certain binary models including signed and logistic, we find the loss functions that achieve the optimal performance, i.e., they attain the previously derived upper bound (see Section 3.2). Interestingly, for logistic and Probit models with $\parallel {\mathbf{x}}_0{\parallel }_2=1$, we prove that the correlation performance of least-squares (LS) is at least as good 0.9972 and 0.9804 times the optimal performance. However, as $\parallel {\mathbf{x}}_0{\parallel }_2$ grows large, logistic and Probit models approach the signed model, in which case LS becomes sub-optimal (see Section 4.1).
• Extension to the Gaussian-Mixture Model: In Section 5, we extend the fundamental limits and the system of equations to the Gaussian-mixture model. Interestingly, our results indicate that, for this model, LS is optimal among all convex loss functions for all $\delta >1$.
• Numerical Simulations: We do numerous experiments to specialize our results to popular models and loss functions, for which we provide simulation results that demonstrate the accuracy of the theoretical predictions (see Section 6 and Appendix E).

Figure 1 contains a pictorial preview of our results described above for the special case of signed measurements. First, Figure 1a depicts the correlation performance of LS and LAD estimators as a function of the aspect ratio $\delta$. Both theoretical predictions and numerical results are shown; note the close match between theory and empirical results for both i.i.d. Gaussian (shown by circles) and i.i.d. Rademacher (shown by squares) distributions of the feature vectors for even small dimensions. Second, the red line on the same figure shows the upper bound derived in this paper—there is no convex loss function that results in correlation exceeding this line. Third, we show that the upper bound can be achieved by the loss functions depicted in Figure 1b for several values of $\delta$. We solve (3) for this choice of loss functions using gradient descent and numerically evaluate the achieved correlation performance. The recorded values are compared in

Table 1. Theoretical predictions and empirical performance of the optimal loss function for signed model. Empirical results are averaged over 20 experiments for $n=128$.

$\mathit{\delta }$	2	3	4	5	6	7	8	9
Predicted Performance	$0.8168$	$0.9101$	$0.9457$	$0.9645$	$0.9748$	$0.9813$	$0.9855$	$0.9885$
Empirical (Gaussian)	$0.8213$	$0.9045$	$0.9504$	$0.9669$	$0.9734$	$0.9801$	$0.9834$	$0.9873$
Empirical (Rademacher)	$0.8096$	$0.9158$	$0.9490$	$0.9633$	$0.9644$	$0.9768$	$0.9808$	$0.9829$

to the corresponding values of the upper bound; again, note the close agreement between the values as predicted by the findings of this paper, which suggests that the fundamental limits derived in this paper hold for sub-Gaussian features. We present corresponding results for the logistic and Probit models in Section 6 and for the noisy-signed model in Appendix E.

A remark on the Gaussianity assumption. Our results on precise asymptotics (to which our study of fundamental limits rely upon) hold rigorously for the two data models in Section 1.2, in which the feature vectors have entries i.i.d. standard Gaussian. However, we conjecture that the Gaussianity assumption can be relaxed. As partial numerical evidence, note in Figure 1a the perfect match of our theory with the empirical performance over data in which the feature vectors ${\mathbf{a}}_i,i\in \left[m\right]$ have entries i.i.d. Rademacher (i.e., centered Bernoulli with probability 1/2). Figure 2 shows corresponding results for the Gaussian-mixture model. Our conjecture that the so-called universality property holds in our setting is also in line with similar numerical observations and partial theoretical evidence previously made for linear regression settings [7,28,29,30,31]. A formal proof of universality of our results is beyond the scope of this paper. However, we remark that, as long as the asymptotic predictions of Section 2 enjoy this property, then all our results on fundamental performance limits and optimal functions automatically hold under the same relaxed assumptions.

1.5. Related Works

Over the past two decades, there has been a long list of works that derive statistical guarantees for high-dimensional estimation problems. Many of these are concerned with convex optimization-based inference methods. Our work is most closely related to the following three lines of research.

(a)

Sharp asymptotics for linear measurements.

Most of the results in the literature of high-dimensional statistics are order-wise in nature. Sharp asymptotic predictions have only more recently appeared in the literature for the case of noisy linear measurements with Gaussian measurement vectors. There are by now three different approaches that have been used towards asymptotic analysis of convex regularized estimators: (i) the one that is based on the approximate message passing (AMP) algorithm and its state-evolution analysis (e.g., [5,8,14,20,32,33,34]); (ii) the one that is based on Gaussian process (GP) inequalities, specifically on the convex Gaussian min-max Theorem (CGMT) (e.g., [9,10,13,15,18,19]); and (iii) the “leave-one-out” approach [11,35]. The three approaches are quite different to each other and each comes with its unique distinguishing features and disadvantages. A detailed comparison is beyond our scope.

Our results in Theorems 2 and 3 for achieving the best performance across all loss functions is complementary to [12] (Theorem 1) and the work of Advani and Ganguli [16], who proposed a method for deriving optimal loss function and measuring its performance, albeit for linear models. Instead, we study binary models. The optimality of regularization for linear measurements is recently studied in [22].

In terms of analysis, we follow the GP approach and build upon the CGMT. Since the previous works are concerned with linear measurements, they consider estimators that solve minimization problems of the form

$$\begin{array}{c}\hfill \widehat{\mathbf{x}}:=arg\underset{\mathbf{x}}{min}\sum _{i=1}^m\tilde{\ell }(y_i-{\mathbf{a}}_i^T\mathbf{x})+rR\left(\mathbf{x}\right)\end{array}$$

(6)

Specifically, the loss function $\tilde{\ell }$ penalizes the residual. In this paper, we show that the CGMT is applicable to optimization problems in the form of (3). For our case of binary observations, (3) is more general than (6). To see this, note that, for $y_i\in \pm 1$ and popular symmetric loss functions $\tilde{\ell }\left(t\right)=\tilde{\ell }(-t)$, e.g., least-squares (LS), (3) results in (6) by choosing $\ell \left(t\right)=\tilde{\ell }(t-1)$ in the former. Moreover, (3) includes several other popular loss functions such as the logistic loss and the hinge loss which cannot be expressed by (6).

(b)

One-bit compressed sensing.

Our work naturally relates to the literature on one-bit compressed sensing (CS) [36]. The vast majority of performance guarantees for one-bit CS are order-wise in nature (e.g., [37,38,39,40,41,42]). To the best of our knowledge, the only existing sharp results are presented in [43] for Gaussian measurement vectors, which studies the asymptotic performance of regularized LS. Our work can be seen as a direct extension of the work in [43] to loss functions beyond least-squares (see Section 4.1 for details).

Similar to the generality of our paper, Genzel [41] also studied the high-dimensional performance of general loss functions. However, in contrast to our results, their performance bounds are loose (order-wise); as such, they are not informative about the question of optimal performance which we also address here.

(c)

Classification in high-dimensions.

In [44,45], the authors studied the high-dimensional performance of maximum-likelihood (ML) estimation for the logistic model. The ML estimator is a special case of (3) and we consider general binary models. In addition, their analysis is based on the AMP framework. The asymptotics of logistic loss under different classification models is also recently studied in [46]. In yet another closely related recent work [47], the authors extended the results of Sur and Candes [45] to regularized ML by using the CGMT. Instead, we present results for general convex loss functions and for binary linear models. Importantly, we also study performance bounds and optimal loss functions.

We also remark on the following closely related parallel works. While the conference version of this paper was being reviewed, the CGMT was applied by Montanari et al. [48] and Deng et al. [49] to determine the generalization performance of max-margin linear classifiers in a binary classification setting. In essence, these results are complementary to the results of our paper in the following sense. Consider a binary classification setting under the logistic model and Gaussian regressors. As discussed in Section 4.2, the optimal set of (3) is bounded with probability approaching one if and only if $\delta >{\delta }_f^{☆}$, for appropriate threshold ${\delta }_f^{☆}$ determined for first time in [44] (see also Figure 3a). Our results hold in this regime. In contrast, the papers by Montanari et al. [48] and Deng et al. [49] study the regime $\delta <{\delta }_f^{☆}$.

We close this section by mentioning works that build on our results and appeared after the initial submission of this paper. The paper by Mignacco et al. [50] studies sharp asymptotics of ridge-regularized ERM with an intercept for Gaussian-mixture models. In [27], we extend the results of this paper on fundamental limits and optimality to the case of ridge-regularized ERM (see also the concurrent work by Aubin et al. [51]).

2. Sharp Performance Guarantees

2.1. Definitions

Moreau Envelopes. Before stating the first result, we need a definition. We write

$${\mathcal{M}}_{\ell }\left(x;\lambda \right):=\underset{v}{min}\frac{1}{2\lambda }{(x-v)}^2+\ell \left(v\right),$$

for the Moreau envelope function of the loss $\ell :\mathbb{R}\to \mathbb{R}$ at x with parameter $\lambda >0$. The minimizer (which is unique by strong convexity) is known as the proximal operator of ℓ at x with parameter $\lambda$ and we denote it as ${\mathrm{prox}}_{\ell }\left(x;\lambda \right)$. A useful property of the Moreau envelope function is that it is continuously differentiable with respect to both x and $\lambda$ [52]. We denote these derivatives as follows

$$\begin{array}{cc}\hfill {\mathcal{M}}_{\ell ,1}^{\prime }\left(x;\lambda \right)& :=\frac{\partial {\mathcal{M}}_{\ell }\left(x;\lambda \right)}{\partial x},\hfill \\ \hfill {\mathcal{M}}_{\ell ,2}^{\prime }\left(x;\lambda \right)& :=\frac{\partial {\mathcal{M}}_{\ell }\left(x;\lambda \right)}{\partial \lambda }.\hfill \end{array}$$

2.2. A System of Equations

As we show shortly the asymptotic performance of the optimization in (3) is tightly connected to the solution of a certain system of nonlinear equations, which we introduce here. Specifically, define random variables $G,S$ and Y as follows:

$$\begin{array}{c}\hfill G,S\stackrel{\mathrm{i}.\mathrm{i}.\mathrm{d}.}{\sim }\mathcal{N}(0,1)\mathrm{and}Y=f\left(S\right),\end{array}$$

(7)

and consider the following system of non-linear equations in three unknowns $(\mu ,\alpha \ge 0,\lambda \ge 0)$:

$$\begin{array}{cc}\hfill \mathbb{E}\left[YS·{\mathcal{M}}_{\ell ,1}^{\prime }\left(\alpha G+\mu SY;\lambda \right)\right]& =0,\hfill \end{array}$$

(8a)

$$\begin{array}{cc}\hfill {\lambda }^2\delta \mathbb{E}\left[{\left({\mathcal{M}}_{\ell ,1}^{\prime }\left(\alpha G+\mu SY;\lambda \right)\right)}^2\right]& ={\alpha }^2,\hfill \end{array}$$

(8b)

$$\begin{array}{cc}\hfill \lambda \delta \mathbb{E}\left[G·{\mathcal{M}}_{\ell ,1}^{\prime }\left(\alpha G+\mu SY;\lambda \right)\right]& =\alpha .\hfill \end{array}$$

(8c)

The expectations are with respect to the randomness of the random variables G, S and Y. We remark that the equations are well defined even if the loss function ℓ is not differentiable. In Appendix A, we summarize some well-known properties of the Moreau envelope function and use them to simplify (8) for differentiable loss functions.

2.3. Asymptotic Prediction

We are now ready to state our first main result.

Theorem 1.

(Sharp Asymptotics). Assume data generated from the binary model with Gaussian features and assume $\delta >1$ such that the set of minimizers in (3) is bounded and the system of Equation (8) has a unique solution $(\mu ,\alpha \ge 0,\lambda \ge 0)$, such that $\mu \ne 0$. Let ${\widehat{\mathbf{x}}}_{\ell }$ be as in (3). Then, in the limit of $m,n\to +\infty$, $m/n\to \delta$, it holds with probability one that

$$\begin{array}{c}\hfill \underset{n\to \infty }{lim}\mathrm{corr}\left({\widehat{\mathbf{x}}}_{\ell };{\mathbf{x}}_0\right)=\frac{\mu }{\sqrt{{\mu }^2+{\alpha }^2}}.\end{array}$$

(9)

Moreover,

$$\begin{array}{c}\hfill \underset{n\to \infty }{lim}{∥{\widehat{\mathbf{x}}}_{\ell }-\mu ·\frac{{\mathbf{x}}_0}{\parallel {\mathbf{x}}_0{\parallel }_2}∥}_2^2={\alpha }^2.\end{array}$$

(10)

Theorem 1 holds for any convex loss function. In Section 4, we specialize the result to specific popular choices and also present numerical simulations that confirm the validity of the predictions (see Figure 1a, Figure 3a, Figure 4a and Figure A4a,b). Before that, we include a few remarks on the conditions, interpretation and implications of the theorem. The proof is deferred to Appendix B and uses the convex Gaussian min-max theorem (CGMT) [13,15].

Remark 1.

(The Role of $\mu$ and $\alpha$). According to (9), the prediction for the limiting behavior of the correlation value is given in terms of an effective noise parameter ${\sigma }_{\ell }:=\alpha /\mu$, where μ and α are unique solutions of (8). The smaller is the value of ${\sigma }_{\ell }$ is, the larger the correlation value becomes. While the correlation value is fully determined by the ratio of α and μ, their individual role is clarified in (10). Specifically, according to (10), ${\widehat{\mathbf{x}}}_{\ell }$ is a biased estimate of the true ${\mathbf{x}}_0$ and μ represents exactly the correlation bias term. In other words, solving (3) returns an estimator that is close to a μ-scaled version of ${\mathbf{x}}_0$. When ${\mathbf{x}}_0$ and ${\widehat{\mathbf{x}}}_{\ell }$ are scaled appropriately, the ${\ell }_2$-norm of their difference converges to α.

Remark 2.

(Why $\delta >1$). The theorem requires that $\delta >1$ (equivalently, $m>n$ asymptotically). Here, we show that this condition is necessary for Equations (8) to have a bounded solution. To see this, take squares in both sides of (8c) and divide by (8b) to find that

$$\delta =\frac{\mathbb{E}\left[{\left({\mathcal{M}}_{\ell ,1}^{\prime }\left(\alpha G+\mu SY;\lambda \right)\right)}^2\right]}{{\left(\mathbb{E}\left[G·{\mathcal{M}}_{\ell ,1}^{\prime }\left(\alpha G+\mu SY;\lambda \right)\right]\right)}^2}\ge 1.$$

The inequality follows by applying Cauchy–Schwarz and using the fact that $\mathbb{E}\left[G^2\right]=1$.

Remark 3.

(On the Existence of a Solution to (8)). While $\delta >1$ is a necessary condition for the equations in (8) to have a solution, it is not sufficient in general. This depends on the specific choice of the loss function. For example, in Section 4.1, we show that, for the squared loss $\ell \left(t\right)={(t-1)}^2$, the equations have a unique solution iff $\delta >1$. On the other hand, for logistic loss and hinge loss, it is argued in Section 4.2 that there exists a threshold value ${\delta }_f^{☆}>2$ such that the set of minimizers in (3) is unbounded if $\delta <{\delta }_f^{☆}$. In this case, the assumptions of Theorem 1 do not hold. We conjecture that, for these choices of loss, Equations (8) are solvable iff $\delta >{\delta }_f^{☆}$. Justifying this conjecture and further studying more general sufficient and necessary conditions under which the Equation (8) admit a solution is left to future work. However, in what follows, given such a solution, we prove that it is unique for a wide class of convex loss functions of interest.

Remark 4.

(On the Uniqueness of Solutions to (8)). We show that, if the system of equations in (8) has a solution, then it is unique provided that ℓ is strictly convex, continuously differentiable and its derivative satisfies ${\ell }^{\prime }\left(0\right)\ne 0$. For instance, this class includes the square, the logistic and the exponential losses. However, it excludes non-differentiable functions such as the LAD and hinge loss. We believe that the differentiability assumption can be relaxed without major modification in our proof, but we leave this for future work. Our result is summarized in Proposition 1 below.

Proposition 1.

(Uniqueness). Assume that the loss function $\ell :\mathbb{R}\to \mathbb{R}$ has the following properties: (i) it is proper strictly convex; and (ii) it is continuously differentiable and its derivative ${\ell }^{\prime }$ is such that ${\ell }^{\prime }\left(0\right)\ne 0$. Further, assume that the (possibly random) link function f is such that $SY=Sf\left(S\right),S\sim \mathcal{N}(0,1)$ has strictly positive density on the real line. The following statement is true. For any $\delta >1$, if the system of equations in (8) has a bounded solution, then it is unique.

The detailed proof of Proposition 1 is deferred to Appendix B.5. Here, we highlight some key ideas. The CGMT relates—in a rather natural way—the original ERM optimization (3) to the following deterministic min-max optimization on four variables

$$\begin{array}{c}\hfill \underset{\alpha >0,\mu ,\tau >0}{min}\underset{\gamma >0}{max}F(\alpha ,\mu ,\tau ,\gamma ):=\frac{\gamma \tau }{2}-\frac{\alpha \gamma }{\sqrt{\delta }}+\mathbb{E}\left[{\mathcal{M}}_{\ell }\left(\alpha G+\mu YS;\frac{\tau }{\gamma }\right)\right].\end{array}$$

(11)

In Appendix B.4, we show that the optimization above is convex-concave for any lower semi-continuous, proper and convex function $\ell :\mathbb{R}\to \mathbb{R}$. Moreover, it is shown that one arrives at the system of equations in (8) by simplifying the first-order optimality conditions of the min-max optimization in (11). This connection is key to the proof of Proposition 1. Indeed, we prove uniqueness of the solution (if such a solution exists) to (8), by proving instead that the function $F(\alpha ,\mu ,\tau ,\gamma )$ above is (jointly) strictly convex in $(\alpha ,\mu ,\tau )$ and strictly concave in γ, provided that ℓ satisfies the conditions of the proposition. Next, let us briefly discuss how strict convex-concavity of (11) can be shown. For concreteness, we only discuss strict convexity here; the ideas are similar for strict concavity. At the heart of the proof of strict convexity of F is understanding the properties of the expected Moreau envelope function $\Omega :{\mathbb{R}}_{+}\times \mathbb{R}\times {\mathbb{R}}_{+}\times {\mathbb{R}}_{+}\to \mathbb{R}$ defined as follows:

$$\Omega (\alpha ,\mu ,\tau ,\gamma ):=\mathbb{E}\left[{\mathcal{M}}_{\ell }\left(\alpha G+\mu YS;\frac{\tau }{\gamma }\right)\right].$$

Specifically, we prove in Proposition A7 in Appendix A.6 that if ℓ is strictly convex, differentiable and does not attain its minimum at 0, then Ω is strictly convex in $(\alpha ,\mu ,\tau )$ and strictly concave in γ. It is worth noting that the Moreau envelope function ${\mathcal{M}}_{\ell }\left(\alpha g+\mu ys;\tau \right)$ for fixed $g,s$ and $y=f\left(s\right)$ is not necessarily strictly convex. Interestingly, we show that the expected Moreau envelope has this desired feature. We refer the reader to Appendix A.6 and Appendix B.5 for more details.

3. On Optimal Performance

3.1. Fundamental Limits

In this section, we establish fundamental limits on the performance of (3) by deriving an upper bound on the absolute value of correlation $\mathrm{corr}\left({\widehat{\mathbf{x}}}_{\ell };{\mathbf{x}}_0\right)$ that holds for all choices of loss functions satisfying Theorem 1. The result builds on the prediction of Theorem 1. In view of (9), upper bounding correlation is equivalent to lower bounding the effective noise parameter ${\sigma }_{\ell }=\alpha /\mu$. Theorem 2 derives such a lower bound.

Before stating the theorem, we need a definition. For a random variable H with density $p_H\left(h\right)$ that has a derivative $p_H^{\prime }\left(h\right),\forall h\in \mathbb{R}$, we denote its score function ${\xi }_H\left(h\right):=\frac{\partial }{\partial h}log{p}_H\left(h\right)=\frac{p_H^{\prime }\left(h\right)}{p_H\left(h\right)}$. Then, the Fisher information of H, denoted by $\mathcal{I}\left(H\right)\in {\mathbb{R}}_{+}$, is defined as follows (e.g., [53] (Sec. 2)):

$$\mathcal{I}\left(H\right):=\mathbb{E}\left[{\left({\xi }_H\left(H\right)\right)}^2\right].$$

Theorem 2.

(Best Achievable Performance). Let the assumptions and notation of Theorem 1 hold and recall the definition of random variables $G,S$ and Y in (7). For $\sigma >0$, define a new random variable $W_{\sigma }:=\sigma G+SY,$ and the function $\kappa :(0,\infty ]\to [0,1]$ as follows,

$$\begin{array}{c}\hfill \kappa \left(\sigma \right):=\frac{{\sigma }^2\left({\sigma }^2\mathcal{I}\left(W_{\sigma }\right)+\mathcal{I}\left(W_{\sigma }\right)-1\right)}{1+{\sigma }^2\left({\sigma }^2\mathcal{I}\left(W_{\sigma }\right)-1\right)}.\end{array}$$

Further, define ${\sigma }_{\mathrm{opt}}$ as follows,

$$\begin{array}{c}\hfill {\sigma }_{\mathrm{opt}}:=min\left\{\sigma \ge 0:\kappa \left(\sigma \right)=\frac{1}{\delta }\right\}.\end{array}$$

(12)

Then, for ${\sigma }_{\ell }:=\frac{\alpha }{\mu }$, it holds that ${\sigma }_{\ell }\ge {\sigma }_{\mathrm{opt}}$.

The theorem above establishes an upper bound on the best possible correlation performance among all convex loss functions. In Section 3.2, we show that this bound is often tight, i.e., there exists a loss function that achieves the specified best possible performance.

Remark 5.

Theorem 2 complements the results in [12,14] (Lem. 3.4) and [15] (Rem. 5.3.3), in which the authors considered only linear regression. In particular, Theorem 2 shows that it is possible to achieve results of this nature for the more challenging setting of binary classification considered here.

Proof of Theorem 2.

Fix a loss function ℓ and let $(\mu \ne 0,\alpha >0,\lambda \ge 0)$ be a solution to (8), which by assumptions of Theorem 1 is unique. The first important observation is that the error of a loss function is unique up to a multiplicative constant. To see this, consider an arbitrary loss function $\ell \left(t\right)$ and let ${\widehat{\mathbf{x}}}_{\ell }$ be a minimizer in (3). Now, consider (3) with the following loss function instead, for some arbitrary constants $C_1>0,C_2\ne 0$:

$$\begin{array}{c}\hfill \widehat{\ell }\left(t\right):=\frac{1}{C_1}\ell \left(C_{2}t\right).\end{array}$$

(13)

It is not hard to see that $\frac{1}{C_2}{\widehat{\mathbf{x}}}_{\ell }$ is the minimizer for $\widehat{\ell }$. Clearly, $\frac{1}{C_2}{\widehat{\mathbf{x}}}_{\ell }$ has the same correlation value with ${\mathbf{x}}_0$ as ${\widehat{\mathbf{x}}}_{\ell }$, showing that the two loss functions ℓ and $\widehat{\ell }$ perform the same. With this observation in mind, consider the function $\widehat{\ell }:\mathbb{R}\to \mathbb{R}$ such that $\widehat{\ell }\left(t\right)=\frac{\lambda }{{\mu }^2}\ell \left(\mu t\right)$. Then, notice that

$${\mathcal{M}}_{\ell ,1}^{\prime }\left(x;\lambda \right)=\frac{1}{\lambda }{\mathcal{M}}_{\widehat{\ell },1}^{\prime }\left(x/\mu ;1\right).$$

Using this relation in (8) and setting $\sigma :={\sigma }_{\ell }=\alpha /\mu$, the system of equations in (8) can be equivalently rewritten in the following convenient form,

$$\begin{array}{cc}& \mathbb{E}\left[YS·{\mathcal{M}}_{\widehat{\ell },1}^{\prime }\left(W_{\sigma };1\right)\right]=0,\hfill \end{array}$$

(14a)

$$\begin{array}{cc}& \mathbb{E}\left[{\left({\mathcal{M}}_{\widehat{\ell },1}^{\prime }\left(W_{\sigma };1\right)\right)}^2\right]={\sigma }^2/\delta ,\hfill \end{array}$$

(14b)

$$\begin{array}{cc}& \mathbb{E}\left[G·{\mathcal{M}}_{\widehat{\ell },1}^{\prime }\left(W_{\sigma };1\right)\right]=\sigma /\delta .\hfill \end{array}$$

(14c)

Next, we show how to use (14) to derive an equivalent system of equations based on $W_{\sigma }$. Starting with (14c), we have

$$\begin{array}{c}\hfill \mathbb{E}\left[G·{\mathcal{M}}_{\widehat{\ell },1}^{\prime }\left(W_{\sigma };1\right)\right]=\frac{1}{\sigma }\int \int u{\mathcal{M}}_{\widehat{\ell },1}^{\prime }\left(u+z;1\right){\varphi }_{\sigma }\left(u\right)p_{SY}\left(z\right)\mathrm{d}u\mathrm{d}z,\end{array}$$

(15)

where ${\varphi }_{\sigma }\left(u\right):=p_{\sigma G}\left(u\right)=\frac{1}{\sigma \sqrt{2\pi }}{e}^{-\frac{u^2}{2{\sigma }^2}}$. Since it holds that ${\varphi }_{\sigma }\left(u\right)=\frac{-{\sigma }^2}{u}{\varphi }_{\sigma }^{\prime }\left(u\right)$, using (A74), it follows that

$$\begin{array}{c}\hfill \begin{array}{cc}\hfill \mathbb{E}\left[G·{\mathcal{M}}_{\widehat{\ell },1}^{\prime }\left(W_{\sigma };1\right)\right]& =-\sigma \int \int {\mathcal{M}}_{\widehat{\ell },1}^{\prime }\left(u+z;1\right){\varphi }_{\sigma }^{\prime }\left(u\right)p_{SY}\left(z\right)\mathrm{d}u\mathrm{d}z\hfill \\ \hfill & =-\sigma \int \int {\mathcal{M}}_{\widehat{\ell },1}^{\prime }\left(w;1\right){\varphi }_{\sigma }^{\prime }\left(u\right)p_{SY}(w-u)\mathrm{d}u\mathrm{d}w\hfill \\ & =-\sigma \int {\mathcal{M}}_{\widehat{\ell },1}^{\prime }\left(w;1\right)p_{W_{\sigma }}^{\prime }\left(w\right)\mathrm{d}w,\hfill \end{array}\end{array}$$

(16)

where in the last step we use

$$p_{W_{\sigma }}^{\prime }\left(w\right)=\int {\varphi }_{\sigma }^{\prime }\left(u\right)p_{SY}(w-u)\mathrm{d}u.$$

Therefore, we have by (16) that

$$\begin{array}{c}\hfill \mathbb{E}\left[G·{\mathcal{M}}_{\widehat{\ell },1}^{\prime }\left(W_{\sigma };1\right)\right]=-\sigma \mathbb{E}\left[{\mathcal{M}}_{\widehat{\ell },1}^{\prime }\left(W_{\sigma };1\right){\xi }_{W_{\sigma }}\left(W_{\sigma }\right)\right].\end{array}$$

(17)

This combined with (14c) gives $\mathbb{E}\left[{\mathcal{M}}_{\widehat{\ell },1}^{\prime }\left(W_{\sigma };1\right){\xi }_{W_{\sigma }}\left(W_{\sigma }\right)\right]=-1/\delta .$ Second, multiplying (14c) with ${\sigma }^2$ and adding it to (14a) yields that,

$$\begin{array}{cc}\hfill \mathbb{E}\left[W_{\sigma }·{\mathcal{M}}_{\widehat{\ell },1}^{\prime }\left(W_{\sigma };1\right)\right]& ={\sigma }^2/\delta ,\hfill \end{array}$$

(18)

Putting these together, we conclude with the following system of equations which is equivalent to (14),

$$\begin{array}{cc}& \mathbb{E}\left[W_{\sigma }·{\mathcal{M}}_{\widehat{\ell },1}^{\prime }\left(W_{\sigma };1\right)\right]={\sigma }^2/\delta ,\hfill \end{array}$$

(19a)

$$\begin{array}{cc}& \mathbb{E}\left[{\left({\mathcal{M}}_{\widehat{\ell },1}^{\prime }\left(W_{\sigma };1\right)\right)}^2\right]={\sigma }^2/\delta ,\hfill \end{array}$$

(19b)

$$\begin{array}{cc}& \mathbb{E}\left[{\mathcal{M}}_{\widehat{\ell },1}^{\prime }\left(W_{\sigma };1\right){\xi }_{W_{\sigma }}\left(W_{\sigma }\right)\right]=-1/\delta .\hfill \end{array}$$

(19c)

Note that, for $\sigma >0$, ${\xi }_{W_{\sigma }}=p_{W_{\sigma }}^{\prime }/p_{W_{\sigma }}$ exists everywhere. This is because for all $w\in \mathbb{R}$: $p_{W_{\sigma }}\left(w\right)>0$ and $p_{W_{\sigma }}(·)$ is continuously differentiable. Combining (19a) and (19c), we derive the following equation which holds for ${\alpha }_1,{\alpha }_2\in \mathbb{R}$,

$$\begin{array}{cc}\hfill \mathbb{E}\left[({\alpha }_1{W}_{\sigma }+{\alpha }_2{\xi }_{W_{\sigma }}\left(W_{\sigma }\right))·{\mathcal{M}}_{\widehat{\ell },1}^{\prime }\left(W_{\sigma };1\right)\right]& ={\alpha }_1{\sigma }^2/\delta -{\alpha }_2/\delta .\hfill \end{array}$$

By Cauchy–Schwarz inequality, we have that

$$\begin{array}{cc}\hfill & {\left(\mathbb{E}\left[({\alpha }_1{W}_{\sigma }+{\alpha }_2{\xi }_{W_{\sigma }}\left(W_{\sigma }\right))·{\mathcal{M}}_{\widehat{\ell },1}^{\prime }\left(W_{\sigma };1\right)\right]\right)}^2\le \hfill \\ & \mathbb{E}\left[{({\alpha }_1{W}_{\sigma }+{\alpha }_2{\xi }_{W_{\sigma }}\left(W_{\sigma }\right))}^2\right]\mathbb{E}\left[{\left({\mathcal{M}}_{\widehat{\ell },1}^{\prime }\left(W_{\sigma };1\right)\right)}^2\right].\hfill \end{array}$$

(20)

Using the fact that $\mathbb{E}\left[W_{\sigma }{\xi }_{W_{\sigma }}\left(W_{\sigma }\right)\right]=-1$ (by integration by parts), $\mathbb{E}\left[{\left({\xi }_{W_{\sigma }}\left(W_{\sigma }\right)\right)}^2\right]=\mathcal{I}\left(W_{\sigma }\right)$, $\mathbb{E}\left[W_{\sigma }^2\right]={\sigma }^2+1$ and (19b), the right hand side of (20) is equal to

$$\begin{array}{c}\hfill \left({\alpha }_1^2({\sigma }^2+1)+{\alpha }_2^2\mathcal{I}\left(W_{\sigma }\right)-2{\alpha }_1{\alpha }_2\right){\sigma }^2/\delta .\end{array}$$

Therefore, we conclude with the following inequality for $\sigma$,

$$\begin{array}{c}\hfill \delta {\sigma }^2\left({\alpha }_1^2({\sigma }^2+1)+{\alpha }_2^2\mathcal{I}\left(W_{\sigma }\right)-2{\alpha }_1{\alpha }_2\right)\ge {({\alpha }_1{\sigma }^2-{\alpha }_2)}^2,\end{array}$$

(21)

which holds for all ${\alpha }_1,{\alpha }_2\in \mathbb{R}$. In particular, (21) holds for the following choice of values for ${\alpha }_1$ and ${\alpha }_2$:

$$\begin{array}{c}\hfill {\alpha }_1=\frac{1-{\sigma }^2\mathcal{I}\left(W_{\sigma }\right)}{\delta ({\sigma }^2\mathcal{I}\left(W_{\sigma }\right)+\mathcal{I}\left(W_{\sigma }\right)-1)},{\alpha }_2=\frac{1}{\delta ({\sigma }^2\mathcal{I}\left(W_{\sigma }\right)+\mathcal{I}\left(W_{\sigma }\right)-1)}.\end{array}$$

(The choice above is motivated by the result of Section 3.2; see Theorem 3). Rewriting (21) with the chosen values of ${\alpha }_1$ and ${\alpha }_2$ yields the following inequality,

$$\begin{array}{c}\hfill \frac{1}{\delta }\le \frac{{\sigma }^2({\sigma }^2\mathcal{I}\left(W_{\sigma }\right)+\mathcal{I}\left(W_{\sigma }\right)-1)}{1+{\sigma }^2({\sigma }^2\mathcal{I}\left(W_{\sigma }\right)-1)}=\kappa \left(\sigma \right),\end{array}$$

(22)

where on the right-hand side above, we recognize the function $\kappa$ defined in the theorem.

Next, we use (22) to show that ${\sigma }_{\mathrm{opt}}$ defined in (12) yields a lower bound on the achievable value of $\sigma$. For the sake of contradiction, assume that $\sigma <{\sigma }_{\mathrm{opt}}$. By the above, $1/\delta \le \kappa \left(\sigma \right)$. Moreover, by the definition of ${\sigma }_{\mathrm{opt}}$, we must have that $1/\delta <\kappa \left(\sigma \right).$ Since $\kappa \left(0\right)=0$ and $\kappa (·)$ is a continuous function we conclude that for some ${\sigma }_1\in (0,\sigma )$, it holds that $\kappa \left({\sigma }_1\right)=1/\delta$. Therefore, for ${\sigma }_1<{\sigma }_{\mathrm{opt}}$, we have $\kappa \left({\sigma }_1\right)=1/\delta$, which contradicts the definition of ${\sigma }_{\mathrm{opt}}$. This proves that $\sigma \ge {\sigma }_{\mathrm{opt}}$, as desired.

To complete the proof, it remains to show that the equation $\kappa \left(\sigma \right)=1/\delta$ admits a solution for all $\delta >1$. For this purpose, we use the continuous mapping theorem and the fact that the Fisher information is a continuous function [54]. Recall that, for two independent and non-constant random variables, it holds that $\mathcal{I}(X+Y)<\mathcal{I}\left(X\right)$ [53] (Eq. 2.18). Since G and $SY$ are independent random variables, we find that $\mathcal{I}(\sigma G+SY)<\mathcal{I}\left(SY\right)$ which implies that $\mathcal{I}(\sigma G+SY)$ is uniformly bounded for all values of $\sigma$. Therefore,

$$\underset{\sigma \to 0}{lim}\kappa \left(\sigma \right)=\underset{\sigma \to 0}{lim}\frac{{\sigma }^2\left({\sigma }^2\mathcal{I}\left(W_{\sigma }\right)+\mathcal{I}\left(W_{\sigma }\right)-1\right)}{1+{\sigma }^2\left({\sigma }^2\mathcal{I}\left(W_{\sigma }\right)-1\right)}=0.$$

Furthermore, ${\sigma }^2\mathcal{I}(\sigma G+SY)=\mathcal{I}(G+\frac{1}{\sigma }SY)\to \mathcal{I}\left(G\right)=1$ when $\sigma \to \infty$. Hence,

$$\underset{\sigma \to \infty }{lim}\kappa \left(\sigma \right)=\underset{\sigma \to \infty }{lim}\frac{{\sigma }^2\left({\sigma }^2\mathcal{I}\left(W_{\sigma }\right)+\mathcal{I}\left(W_{\sigma }\right)-1\right)}{1+{\sigma }^2\left({\sigma }^2\mathcal{I}\left(W_{\sigma }\right)-1\right)}=1.$$

Note that ${\sigma }^2\mathcal{I}(\sigma G+SY)<{\sigma }^2\mathcal{I}\left(\sigma G\right)=1$, which further yields that $\kappa \left(\sigma \right)<1$ for all $\sigma \ge 0$. Finally, since $\mathcal{I}(·)$ is a continuous function, we deduce that range of $\kappa :{\mathbb{R}}^{+}\cup 0\to \mathbb{R}$ is $[0,1)$, implying the existence of a solution to (12) for all $\delta >1$. This completes the proof of Theorem 2. □

A useful closed-form bound on the best achievable performance: In general, determining ${\sigma }_{\mathrm{opt}}$ requires computing the Fisher information of the random variable $\sigma G+SY$ for $\sigma >0$. If the probability distribution of $SY$ is continuously differentiable (e.g., logistic model; see Appendix C.1), then we obtain the following simplified bound.

Corollary 1.

(Closed-form Lower Bound on ${\sigma }_{\mathrm{opt}}$). Let $p_{SY}:\mathbb{R}\to \mathbb{R}$ be the probability distribution of $SY$. If $p_{SY}\left(x\right)$ is differentiable for all $x\in \mathbb{R}$, then,

$$\begin{array}{c}\hfill {\sigma }_{\mathrm{opt}}^2\ge \frac{1}{(\delta -1)\left(\mathcal{I}\right(SY)-1)}.\end{array}$$

(23)

Proof. 

Based on Theorem 2, the following equation holds for $\sigma ={\sigma }_{\mathrm{opt}}$

$$\frac{1}{\delta }=\kappa \left(\sigma \right)$$

or, equivalently, by rewriting the right-hand side,

$$\begin{array}{c}\hfill \frac{1}{\delta }=1-\frac{1}{\frac{1}{1-{\sigma }^2\mathcal{I}\left(W_{\sigma }\right)}-{\sigma }^2}.\end{array}$$

(24)

Define the following function

$$\begin{array}{c}\hfill h\left(x\right):=1-\frac{1}{\frac{1}{1-{\sigma }^{2}x}-{\sigma }^2}.\end{array}$$

The function h is increasing in the region ${\mathcal{R}}_{\sigma }=\{z:z>{\sigma }^{-2}-{\sigma }^{-4}\}.$ According to Stam’s inequality [55], for two independent random variables X and Y with continuously differentiable $p_X$ and $p_Y$, it holds that

$$\mathcal{I}(X+Y)\le \frac{\mathcal{I}\left(X\right)·\mathcal{I}\left(Y\right)}{\mathcal{I}\left(X\right)+\mathcal{I}\left(Y\right)},$$

where equality is achieved if and only if X and Y are independent Gaussian random variables. Therefore, since by assumption $p_{SY}$ is differentiable on the real line, Stam’s inequality yields

$$\begin{array}{c}\hfill \mathcal{I}\left(W_{\sigma }\right)=\mathcal{I}(\sigma G+SY)\le \frac{\mathcal{I}\left(\sigma G\right)·\mathcal{I}\left(SY\right)}{\mathcal{I}\left(\sigma G\right)+\mathcal{I}\left(SY\right)}.\end{array}$$

(25)

Next, we prove that for all $\sigma >0$, both sides of (25) are in the region ${\mathcal{R}}_{\sigma }$. First, we prove that $\mathcal{I}\left(W_{\sigma }\right)\in {\mathcal{R}}_{\sigma }$. By Cramer–Rao bound (e.g., see [53] (Eq. 2.15)) for Fisher information of a random variable X, we have that $\mathcal{I}\left(X\right)\ge 1/\left(\mathrm{Var}\left[X\right]\right)$. In addition, for the random variable $W_{\sigma }$, we know that $\mathrm{Var}\left[W_{\sigma }\right]=1+{\sigma }^2-{\left(\mathbb{E}\left[SY\right]\right)}^2$, thus

$$\begin{array}{c}\hfill \mathcal{I}\left(W_{\sigma }\right)\ge \frac{1}{1+{\sigma }^2-{\left(\mathbb{E}\left[SY\right]\right)}^2}.\end{array}$$

(26)

Using the relation ${\left(\mathbb{E}\left[SY\right]\right)}^2\le \mathbb{E}\left[S^2\right]\mathbb{E}\left[Y^2\right]=1$, one can check that the following inequality holds:

$$\begin{array}{c}\hfill \frac{1}{1+{\sigma }^2-{\left(\mathbb{E}\left[SY\right]\right)}^2}\ge {\sigma }^{-2}-{\sigma }^{-4}.\end{array}$$

(27)

Therefore, from (26) and (27), we derive that $\mathcal{I}\left(W_{\sigma }\right)\in {\mathcal{R}}_{\sigma }$ for all $\sigma >0$. Furthermore, by the inequality in (25) and the definition of ${\mathcal{R}}_{\sigma }$ it directly follows that for all $\sigma >0$

$$\frac{\mathcal{I}\left(\sigma G\right)\mathcal{I}\left(SY\right)}{\mathcal{I}\left(\sigma G\right)+\mathcal{I}\left(SY\right)}\in {\mathcal{R}}_{\sigma }.$$

Finally, noting that $h(·)$ is increasing in ${\mathcal{R}}_{\sigma }$, combined with (25), we have

$$\frac{1}{\delta }=h\left(\mathcal{I}\left(W_{\sigma }\right)\right)\le h\left(\frac{\mathcal{I}\left(\sigma G\right)·\mathcal{I}\left(SY\right)}{\mathcal{I}\left(\sigma G\right)+\mathcal{I}\left(SY\right)}\right),$$

which after using the relation $\mathcal{I}\left(\sigma G\right)={\sigma }^{-2}$ and further simplification yields the inequality in the statement of the corollary. □

The proof of the corollary reveals that (23) holds with equality when $SY$ is Gaussian. In Appendix C.1, we compute $p_{SY}$ for the logistic and the Probit models with $\parallel {\mathbf{x}}_0{\parallel }_2=1$ and numerically show that it is close to the density of a Gaussian random variable. Consequently, the lower bound of Corollary 1 is almost exact when measurements are obtained according to the logistic and Probit models (see Figure A2 in the Appendix C).

3.2. On the Optimal Loss Function

It is natural to ask whether there exists a loss function that attains the bound of Theorem 2. If such a loss function exists, then we say it is optimal in the sense that it maximizes the correlation performance among all convex loss functions in (3).

Our next theorem derives a candidate for the optimal loss function, which we denote ${\ell }_{\mathrm{opt}}$. Before stating the result, we provide some intuition about the proof which builds on Theorem 2. The critical observation in the proof of Theorem 2 is that the effective noise ${\sigma }_{\widehat{\ell }}$ of $\widehat{\ell }$ is minimized (i.e., it attains the value ${\sigma }_{\mathrm{opt}}$) if the Cauchy–Schwartz inequality in (20) holds with equality. Hence, we seek $\widehat{\ell }={\ell }_{\mathrm{opt}}$ so that for some $c\in \mathbb{R}$,

$$\begin{array}{c}\hfill {\mathcal{M}}_{{\ell }_{\mathrm{opt}},1}^{\prime }\left(w;1\right)=c({\alpha }_{1}w+{\alpha }_2·{\xi }_{W_{\mathrm{opt}}}\left(w\right)).\end{array}$$

(28)

By choosing $c=-1$, integrating and ignoring constants irrelevant to the minimization of the loss function, the previous condition is equivalent to the following ${\mathcal{M}}_{{\ell }_{\mathrm{opt}}}\left(w;1\right)=-{\alpha }_1{w}^2/2-{\alpha }_{2}log\left(p_{W_{\mathrm{opt}}}\left(w\right)\right).$ It turns out that this condition can be “inverted” to yield the explicit formula for ${\ell }_{\mathrm{opt}}$ as, ${\ell }_{\mathrm{opt}}\left(w\right)=-{\mathcal{M}}_{{\alpha }_{1}q+{\alpha }_{2}log\left(p_{W_{\mathrm{opt}}}\right)}\left(w;1\right).$ Of course, one has to properly choose ${\alpha }_1$ and ${\alpha }_2$ to make sure that this function satisfies the system of equations in (19) with $\sigma ={\sigma }_{\mathrm{opt}}$. The correct choice is specified in the theorem below. The proof is deferred to Appendix D.1.

Theorem 3.

(Optimal Loss Function). Recall the definition of ${\sigma }_{\mathrm{opt}}$ in (12). Define the random variable $W_{\mathrm{opt}}:={\sigma }_{\mathrm{opt}}G+SY$ and let $p_{W_{\mathrm{opt}}}$ denote its density. Consider the following loss function ${\ell }_{\mathrm{opt}}:\mathbb{R}\to \mathbb{R}$

$$\begin{array}{c}\hfill {\ell }_{\mathrm{opt}}\left(w\right)=-{\mathcal{M}}_{{\alpha }_{1}q+{\alpha }_{2}log\left(p_{W_{\mathrm{opt}}}\right)}\left(w;1\right),\end{array}$$

(29)

where $q\left(x\right)=x^2/2$ and

$$\begin{array}{c}\hfill \begin{array}{cc}\hfill {\alpha }_1& =\frac{1-{\sigma }_{\mathrm{opt}}^2\mathcal{I}\left(W_{\mathrm{opt}}\right)}{\delta ({\sigma }_{\mathrm{opt}}^2\mathcal{I}\left(W_{\mathrm{opt}}\right)+\mathcal{I}\left(W_{\mathrm{opt}}\right)-1)},\hfill \\ \hfill {\alpha }_2& =\frac{1}{\delta ({\sigma }_{\mathrm{opt}}^2\mathcal{I}\left(W_{\mathrm{opt}}\right)+\mathcal{I}\left(W_{\mathrm{opt}}\right)-1)}.\hfill \end{array}\end{array}$$

(30)

If ${\ell }_{\mathrm{opt}}$ defined as in (29) is convex and the equation $\kappa \left(\sigma \right)=1/\delta$ has a unique solution, then ${\sigma }_{{\ell }_{\mathrm{opt}}}={\sigma }_{\mathrm{opt}}$.

In general, there is no guarantee that the function ${\ell }_{\mathrm{opt}}(·)$ as defined in (29) is convex. However, if this is the case, the theorem above guarantees that it is optimal (Strictly speaking, the performance is optimal among all convex loss functions ℓ for which (8) has a unique solution as required by Theorem 2.). A sufficient condition for ${\ell }_{\mathrm{opt}}\left(w\right)$ to be convex is provided in Appendix D.2. Importantly, in Appendix D.2.1, we show that this condition holds for observations following the signed model. Thus, for this case, the resulting function is convex. Although we do not prove the convexity of optimal loss function for the logistic and Probit models, our numerical results (e.g., see Figure 3b) suggest that this is the case. Concretely, we conjecture that the loss function ${\ell }_{\mathrm{opt}}$ is convex for logistic and Probit models, and therefore by Theorem 3 its performance is optimal.

4. Special Cases

4.1. Least-Squares

By choosing $\ell \left(t\right)={(t-1)}^2$ in (3), we obtain the standard least-squares estimate. To see this, note that since $y_i=\pm 1$, it holds for all i that ${(y_i{\mathbf{a}}_i^T\mathbf{x}-1)}^2={(y_i-{\mathbf{a}}_i^T\mathbf{x})}^2.$ Thus, $\widehat{\mathbf{x}}$ is minimizing the sum of squares of the residuals:

$$\begin{array}{c}\hfill \widehat{\mathbf{x}}=arg\underset{\mathbf{x}}{min}\sum {(y_i-{\mathbf{a}}_i^T\mathbf{x})}^2.\end{array}$$

(31)

For this choice of a loss function, we can solve the equations in (8) in closed form. Furthermore, the equations have a (unique, bounded) solution for any $\delta >1$ provided that $\mathbb{E}\left[SY\right]>0$. The final result is summarized in the corollary below (see Appendix F.1 for the proof).

Corollary 2.

(Least-squares). Assume data generated from the binary model and $\delta >1$. For the label function assume that $\mathbb{E}\left[SY\right]>0$ in the notation of (7). Let $\widehat{\mathbf{x}}$ be as in (41). Then, in the limit of $m,n\to +\infty$, $m/n\to \delta$, Equations (9) and (10) hold with probability one with α and μ given as follows:

$$\begin{array}{cc}\hfill \mu & =\mathbb{E}\left[SY\right],\hfill \end{array}$$

(32)

$$\begin{array}{cc}\hfill \alpha & =\sqrt{1-{\left(\mathbb{E}\left[SY\right]\right)}^2}·\sqrt{\frac{1}{\delta -1}}.\hfill \end{array}$$

(33)

Corollary 2 appears in [43] (see also [40,41,56] and Appendix F for an interpretation of the result). However, these previous works obtain results that are limited to least-squares loss. In contrast, our results are general and LS prediction is obtained as a simple corollary of our general Theorem 1. Moreover, our study of fundamental limits allows us to quantify the sub-optimality gap of least-square (LS) as follows.

On the Optimality of LS. On the one hand, Corollary 2 derives an explicit formula for the effective noise variance ${\sigma }_{\mathrm{LS}}=\alpha /\mu$ of LS in terms of $E\left[YS\right]$ and $\delta$. On the other hand, Corollary 1 provides an explicit lower bound on the optimal value ${\sigma }_{\mathrm{opt}}$ in terms of $\mathcal{I}\left(SY\right)$ and $\delta$. Combining the two, we conclude that

$$\frac{{\sigma }_{\mathrm{LS}}^2}{{\sigma }_{\mathrm{opt}}^2}\le \xi :=(\mathcal{I}\left(SY\right)-1)\frac{1-{\left(\mathbb{E}\left[SY\right]\right)}^2}{{\left(\mathbb{E}\left[SY\right]\right)}^2}.$$

In terms of correlation,

$$\begin{array}{c}\hfill \frac{{\mathrm{corr}}_{\mathrm{opt}}}{{\mathrm{corr}}_{\mathrm{LS}}}=\sqrt{\frac{1+{\sigma }_{\mathrm{LS}}^2}{1+{\sigma }_{\mathrm{opt}}^2}}\le \frac{{\sigma }_{\mathrm{LS}}}{{\sigma }_{\mathrm{opt}}}\le \sqrt{\xi },\end{array}$$

where the first inequality follows from the fact that ${\sigma }_{\mathrm{LS}}\ge {\sigma }_{\mathrm{opt}}.$ Therefore, the performance of LS is at least as good as $\frac{1}{\sqrt{\xi }}$ times the optimal one. In particular, assuming $\parallel {\mathbf{x}}_0\parallel =1$ and for logistic and Probit models (for which Corollary 1 holds), we can explicitly compute $\frac{1}{\sqrt{\xi }}=0.9972\mathrm{and}0.9804$, respectively. However, we recall that for large $\parallel {\mathbf{x}}_0\parallel$ logistic and Probit models approach the signed model, and, as Figure 1a demonstrates, LS becomes suboptimal.

Another interesting consequence of combining Corollaries 1 and 2 is that LS would be optimal if $SY$ were a Gaussian random variable. To see this, recall from Corollary 1 that, if $SY$ is Gaussian, then:

$${\sigma }_{\mathrm{opt}}^2=\frac{1}{(\delta -1)\left(\mathcal{I}\right(SY)-1)}.$$

However, for $SY$ Gaussian, we can explicitly compute $\mathcal{I}\left(SY\right)=1/\mathrm{Var}\left[SY\right]$, which leads to

$${\sigma }_{\mathrm{opt}}^2=\frac{1-{\left(\mathbb{E}\left[SY\right]\right)}^2}{{\left(\mathbb{E}\left[SY\right]\right)}^2(\delta -1)}.$$

The right hand side is exactly ${\sigma }_{\mathrm{LS}}^2$. Therefore, the optimal performance is achieved by the square loss function if $SY$ is a Gaussian random variable. Remarkably, for logistic and Probit models with small SNR (i.e., small $\parallel {\mathbf{x}}_0\parallel$), density of $SY$ is close to the density of a normal random variable (see Figure A2 in the Appendix C), implying the optimality of LS for these models.

4.2. Logistic and Hinge Loss

Theorem 1 only holds in regimes for which the set of minimizers of (3) is bounded. As we show here, this is $not$ always the case. Specifically, consider non-negative loss functions $\ell \left(t\right)\ge 0$ with the property ${lim}_{t\to +\infty }\ell \left(t\right)=0$. For example, the hinge, exponential and logistic loss functions all satisfy this property. Now, we show that for such loss functions the set of minimizers is unbounded if $\delta <{\delta }_f^{☆}$ for some appropriate ${\delta }_f^{☆}>2$. First, note that the set of minimizers is unbounded if the following condition holds:

$$\begin{array}{c}\hfill \exists {\mathbf{x}}_s\ne \mathbf{0}\mathrm{such}\mathrm{that}{y}_i{\mathbf{a}}_i^T{\mathbf{x}}_s\ge 0,\forall i\in \left[m\right].\end{array}$$

(34)

Indeed, if (34) holds then $\mathbf{x}=c·{\mathbf{x}}_s$ with $c\to +\infty$, attains zero cost in (3); thus, it is optimal and the set of minimizers is unbounded. To proceed, we rely on a recent result by Candes and Sur [44] who proved that (34) holds iff (To be precise, Candes and Sur [44] proved the statement for measurements $y_i,i\in \left[m\right]$ that follow a logistic model. Close inspection of their proof shows that this requirement can be relaxed by appropriately defining the random variable Y in (7) (see also [48,49]).)

$$\begin{array}{c}\hfill \delta \le {\delta }_f^{☆}:={\left(\underset{c\in \mathbb{R}}{min}\mathbb{E}\left[{\left(G+cSY\right)}_{-}^2\right]\right)}^{-1},\end{array}$$

(35)

where $G,S$ and Y are random variables as in (7) and ${\left(t\right)}_{-}:=min\{0,t\}$. We highlight that logistic and hinge losses give unbounded solutions in the noisy-signed model with $\epsilon =0$, since the condition (34) holds for ${\mathbf{x}}_s={\mathbf{x}}_0$. However, their performances are comparable to the optimal performance in both logistic and Probit models (see Figure 3a and Figure 4a).

5. Extensions to Gaussian-Mixture Models

In this section, we show that our results on sharp asymptotics and lower bounds on error can be extended to include the Gaussian-Mixture model (GMM) presented in Section 1.2. The discussions on the phase transition for the existence of a bounded solution in Section 4.2 applies here as well. We rely on a phase-transition result [49] (Prop. 3.1), which proves that (34) holds if and only if

$$\begin{array}{c}\hfill \delta \le {\delta }^{☆}:={\left(\underset{t\in \mathbb{R}}{min}\mathbb{E}\left[{\left(W_1+t{W}_2\right)}_{-}^2\right]\right)}^{-1},\end{array}$$

(36)

where $W_1$ and $W_2$ are random variables defined in (7) and ${\left(x\right)}_{-}^2:={\left(min\{x,0\}\right)}^2$. Therefore, for loss functions satisfying this property, e.g., hinge loss and logistic loss, the solution to (3) is unbounded if and only if $\delta \le {\delta }^{☆}.$

5.1. System of Equations for GMM

It turns out that, similar to the generative models, the asymptotic performance of (3) for GMM depends on the loss function ℓ via its Moreau envelope. Specifically, let $W_1$ and $W_2$ be independent Gaussian random variables such that

$$\begin{array}{c}\hfill W_1\sim \mathcal{N}(0,1),W_2\sim \mathcal{N}(r,1),\end{array}$$

(37)

where $r:=\parallel {\mathbf{x}}_{\mathbf{0}}{\parallel }_2>0.$ Consider the following system of non-linear equations in three unknowns $(\mu ,\alpha \ge 0,\lambda \ge 0)$:

$$\begin{array}{cc}\hfill 0& =\mathbb{E}\left[W_2·{\mathcal{M}}_{\ell ,1}^{\prime }\left(\alpha W_1+\mu W_2;\lambda \right)\right],\hfill \end{array}$$

(38a)

$$\begin{array}{cc}\hfill {\alpha }^2& ={\lambda }^2\delta \mathbb{E}\left[{\left({\mathcal{M}}_{\ell ,1}^{\prime }\left(\alpha W_1+\mu W_2;\lambda \right)\right)}^2\right],\hfill \end{array}$$

(38b)

$$\begin{array}{cc}\hfill \alpha & =\lambda \delta \mathbb{E}\left[W_1·{\mathcal{M}}_{\ell ,1}^{\prime }\left(\alpha W_1+\mu W_2;\lambda \right)\right].\hfill \end{array}$$

(38c)

The expectations above are with respect to the randomness of the random variables $W_1$ and $W_2$.

As we show shortly, the solution to these equations is tightly connected to the asymptotic behavior of the optimization in (3).

5.2. Theoretical Prediction of Error for Convex Loss Functions

Theorem 4.

(Asymptotic Prediction). Assume data generated from the Gaussian-mixture model and assume $\delta >1$ such that the set of minimizers in (3) is bounded and the system of Equation (38) has a unique solution $(\mu ,\alpha ,\lambda )$, such that $\mu \ne 0$. Let ${\widehat{\mathbf{x}}}_{\ell }$ be as in (3) and ${\sigma }_{\ell }=\alpha /\mu$. Then, in the limit of $m,n\to +\infty$, $m/n\to \delta$, it holds with probability one that

$$\begin{array}{c}\hfill \underset{n\to \infty }{lim}\mathrm{corr}\left({\widehat{\mathbf{x}}}_{\ell };{\mathbf{x}}_0\right)=\frac{\mu }{\sqrt{{\mu }^2+{\alpha }^2}},\underset{n\to \infty }{lim}{\mathcal{E}}_{\ell }=Q\left(\frac{r}{\sqrt{1+{\sigma }_{\ell }^2}}\right),\end{array}$$

(39)

where ${\mathcal{E}}_{\ell }$ denotes the classification test error defined in (5).

Remark 6

(Proof of Theorem 4). The high-level steps of the proof of Theorem 4 follow closely the proof of Theorem 1. Particularly, for GMM one can show the correlation of the ERM estimate with the true vector ${\mathbf{x}}_0$ is predicted by a system of Equations as in (38), only with $W_2$ replaced by a non-gaussian random variable (denoted as $SY$ in Theorem 1). Specifically, by rotational invariance of the Gaussian feature vectors ${\mathbf{a}}_i$, we can assume, without loss of generality, that ${\mathbf{x}}_0={[r,0,0,\dots ,0]}^T$. Then, we can can guarantee that with probability one it holds that

$$\begin{array}{c}\hfill \underset{n\to \infty }{lim}{\widehat{\mathbf{x}}}_{\ell }\left(1\right)=\mu ,\underset{n\to \infty }{lim}\sum _{j=2}^n{\widehat{\mathbf{x}}}_{\ell }^2\left(j\right)={\alpha }^2,\end{array}$$

(40)

where μ and α are specified by (38). To see how this implies (39), we argue as follows. Recalling that $\mathbf{x}|y\sim \mathcal{N}(y{\mathbf{x}}_0,\mathbf{I})$, we have

$$y\langle {\widehat{\mathbf{x}}}_{\ell },\mathbf{a}\rangle \sim \mathcal{N}\left(r{\widehat{\mathbf{x}}}_{\ell }\left(1\right),{∥{\widehat{\mathbf{x}}}_{\ell }∥}_2^2\right).$$

Using this and (40) leads to the asymptotic value of correlation and classification error as presented in (39).

Remark 7.

(On the Uniqueness of Solutions to Equation (38)) Our results in proving the uniqueness of solutions to the equations for generative models (8) in Proposition 1, extend to GMM. Noting that $W_2\sim \mathcal{N}(r,1)$ in (38) plays the role of $SY$ in (8), we straightforwardly deduce the following result for uniqueness of solutions to (38).

Proposition 2.

Assume that the loss function $\ell :\mathbb{R}\to \mathbb{R}$ has the following properties: (i) it is proper strictly convex; and (ii) it is continuously differentiable and its derivative ${\ell }^{\prime }$ is such that ${\ell }^{\prime }\left(0\right)\ne 0$. The following statement is true. For any $\delta >1$, if the system of equations in (38) has a bounded solution, then it is unique.

5.3. Special Case: Least-Squares

By choosing $\ell \left(t\right)={(t-1)}^2$ in (3), we obtain the standard least-squares estimate. To see this, note that since $y_i=\pm 1$, it holds for all i that ${(y_i{\mathbf{a}}_i^T\mathbf{x}-1)}^2={(y_i-{\mathbf{a}}_i^T\mathbf{x})}^2.$

Thus, the estimator ${\widehat{\mathbf{x}}}_{LS}$ is minimizing the sum of squares of the residuals:

$$\begin{array}{c}\hfill {\widehat{\mathbf{x}}}_{LS}=arg\underset{\mathbf{x}}{min}\sum {(y_i-{\mathbf{a}}_i^T\mathbf{x})}^2.\end{array}$$

(41)

For the choice $\ell \left(t\right)={(t-1)}^2$, it turns out that we can solve the equations in (38) in closed form. The final result is summarized in the corollary below and proved in Appendix G.1.

Corollary 3.

(Least-Squares). Let ${\widehat{\mathbf{x}}}_{LS}$ be as in (31) and $\delta >1$. Then, in the limit of $m,n\to +\infty$, $m/n\to \delta$, Equation (39) holds with probability one with ${\sigma }_{LS}^2$ given as follows:

$$\begin{array}{c}\hfill {\sigma }_{LS}^2=\frac{1+r^2}{r^2}·\frac{1}{(\delta -1)}.\end{array}$$

(42)

5.4. Optimal Risk for GMM

Next, we characterize the best achievable classification error by different choices of loss function. Considering (39), we see that an optimal choice of ℓ is the one that minimizes ${\sigma }_{\ell }^2$. The next theorem characterizes the best achievable ${\sigma }_{\ell }$ among convex loss functions by deriving an equivalent set of equations to (38) and combining them with proper coefficients. Similar to the proof of Theorem 2, a key step in the proof is properly setting up a Cauchy–Schwarz inequality that exploits the structure of the new set of equations. The proof is deferred to Appendix G.2.

Theorem 5.

(Lower Bound on Risk). Under the assumptions of Theorem 4, the following inequality holds for the effective risk parameter (${\sigma }_{\ell }$) of a loss function ℓ:

$$\begin{array}{c}\hfill \underset{n\to \infty }{lim}{\sigma }_{\ell }^2\ge {\sigma }_{☆}^2:=\frac{1+r^2}{r^2}·\frac{1}{\delta -1}\end{array}$$

(43)

Remark 8.

(Optimality of Least-squares for GMM). Theorem 5 provides a lower bound for the asymptotic value of ${\sigma }_{\ell }$ which holds for all $\delta >1$ and $r>0$. This result together with Corollary 3 implies that least-squares achieves the least value of risk (i.e., ${\sigma }_{\ell }$ and ${\mathcal{E}}_{\ell }$) for all $\delta >1$ and $r>0$ among all convex loss functions ℓ for which the set of minimizers in (3) is bounded.

6. Numerical Experiments

In this section, we present numerical simulations that validate the predictions of Theorems 1–5. To begin, we use the following three popular models as our case study: signed, logistic and Probit. We generate random measurements according to (1). Without loss of generality (due to rotational invariance of the Gaussian measure), we set ${\mathbf{x}}_0={[1,0,\dots ,0]}^T$. We then obtain estimates ${\widehat{\mathbf{x}}}_{\ell }$ of ${\mathbf{x}}_0$ by numerically solving (3) and measure performance by the correlation value $\mathrm{corr}\left({\widehat{\mathbf{x}}}_{\ell };{\mathbf{x}}_0\right)$. Throughout the experiments, we set $n=128$ and the recorded values of correlation are averages over 25 independent realizations. For each label function, we first provide plots that compare results of Monte Carlo simulations to the asymptotic predictions for loss functions discussed in Section 4, as well as to the optimal performance of Theorem 2. We next present numerical results on optimal loss functions. To empirically derive the correlation of optimal loss function, we run gradient descent-based optimization with 1000 iterations. As a general comment, we note that, despite being asymptotic, our predictions appear accurate even for relatively small problem dimensions. For the analytical predictions, we apply Theorem 1. In particular, for solving the system of non-linear equations in (3), we empirically observe (see also [15,47] for similar observation) that, if a solution exists, then it can be efficiently found by the following fixed-point iteration method. Let $\mathbf{v}:={[\mu ,\alpha ,\lambda ]}^T$ and $\mathcal{F}:{\mathbb{R}}^3\to {\mathbb{R}}^3$ be such that (3) is equivalent to $\mathbf{v}=\mathcal{F}\left(\mathbf{v}\right)$. With this notation, we initialize $\mathbf{v}={\mathbf{v}}_0$ and for $k\ge 1$ repeat the iterations ${\mathbf{v}}_{k+1}=\mathcal{F}\left({\mathbf{v}}_k\right)$ until convergence.

Logistic model. For the logistic model, comparison between the predicted values and the numerical results is illustrated in Figure 3a. Results are shown for LS, logistic and hinge loss functions. Note that minimizing the logistic loss corresponds to the maximum-likelihood estimator (MLE) for logistic model. An interesting observation in Figure 3a is that in the high-dimensional setting (finite $\delta$) LS has comparable (if not slightly better) performance to MLE. Additionally, we observe that in this model, performance of LS is almost the same as the best possible performance derived according to Theorem 2. This confirms the analytical conclusion of Section 4.1. The comparison between the optimal loss function as in Theorem 3 and other loss functions is illustrated in Figure 3b. We note the obvious similarity between the shapes of optimal loss functions and LS which further explains the similarity between their performance.

Probit model. Theoretical predictions for the performance of hinge and LS loss functions are compared with the empirical results and optimal performance of Theorem 2 in Figure 4a. Similar to the logistic model, in this model, LS also outperforms hinge loss and its performance resembles the performance of optimal loss function derived according to Theorem 3. Figure 4b illustrates the shapes of LS, hinge loss and the optimal loss functions for the Probit model. The obvious similarity between the shape of LS and optimal loss functions for all values of $\delta$ explains the close similarity of their performance.

Additionally, by comparing the LS performance for the three models in Figure 1a, Figure 3a and Figure 4a, it is clear that higher (respectively, lower) correlation values are achieved for signed (respectively, logistic) measurements. This behavior is indeed predicted by Corollary 2: correlation performance is higher for higher values of $\mu =\mathbb{E}\left[SY\right]$. It can be shown that, for the signed, probit and logistic models (with $\parallel {\mathbf{x}}_0{\parallel }_2=1$), we have $\mu =\sqrt{2/\pi },\sqrt{1/\pi }\mathrm{and}0.4132$, respectively.

Optimal loss function. By putting together Theorems 2 and 3, we obtain a method on deriving the optimal loss function for generative binary models. This requires the following steps.

• Find ${\sigma }_{\mathrm{opt}}$ by solving (12).
• Compute the density of $W_{\mathrm{opt}}={\sigma }_{\mathrm{opt}}G+SY$.
• Compute ${\ell }_{\mathrm{opt}}$ according to (29).

Note that computing ${\sigma }_{\mathrm{opt}}$ needs the density function $p_W$ of the random variable $W=\sigma G+SY$. In principle $p_W$ can be calculated as the convolution of the Gaussian density with the pdf $p_{SY}$ of $SY$. Moreover, it follows from the recipe above that the optimal loss function depends on $\delta$ in general. This is because ${\sigma }_{\mathrm{opt}}$ itself depends on $\delta$ via (12).

Numerical Experiments for GMM

Theorem 5 implies the optimality of least-squares among convex loss functions in the under-parameterized regime $\delta >1$. In Figure 2, we demonstrate the classification risk of least-squares alongside other well-known loss functions LAD and logistic, for $r=1$. Solid lines correspond to the theoretical predictions of Theorem 4. For least-squares we rely on the result of Corollary 3 and for LAD and logistic loss, the system of equations are solved by iterating over the equations, where we observe that after relatively small number of iterations the triple $(\mu ,\alpha ,\lambda )$ converges to $({\mu }^{☆},{\alpha }^{☆},{\lambda }^{☆})$. We use ${10}^5$ and ${10}^3$ samples to compute the expectations in (38) for LAD and logistic loss, respectively. After deriving ${\sigma }_{\ell }=\alpha /\mu$, the classification risk ${\mathcal{E}}_{\ell }$ is obtained according to the formula in (39). Dots correspond to the empirical evaluations of the classification risk of loss functions for $n=60$ and for different values of $\delta =m/n>1.$ The resulting numbers are averaged over 30 independent experiments. As is observed, the empirical results closely follow the theoretical predictions of Theorem 4. Furthermore, as predicted by Theorem 5, least-squares has the minimum expected classification risk among other convex loss functions and for all $\delta >1$.

7. Conclusions

We derive theoretical predictions for the generalization error of estimators obtained by ERM for generative binary models and a Gaussian Mixture model. Furthermore, we use this theoretical characterizations to find the optimal performance and optimal loss function among all convex losses. Although our analysis is true for Gaussian matrices, we empirically show they hold for sub-Gaussian matrices as well. As an exciting future direction, we plan to extend our analysis on sharp asymptotics and optimal loss function to non-isotropic (Gaussian) features with arbitrary covariance. A more challenging, albeit interesting, direction is going beyond (binary) linear models studied in this paper, by considering asymptotics and optimal error for kernel models and neural networks (see [48,57] for partial progress in this direction).