Generalization error in high-dimensional perceptrons: Approaching Bayes error with convex optimization

Introduction

High-dimensional statistics, where the ratio $\alpha={n}/{d}$ is kept finite while the dimensionality $d$ and the number of samples $n$ grow, often display interesting non-intuitive features. Asymptotic generalization performances for such problems in the so-called teacher-student setting, with synthetic data, have been the subject of intense investigations spanning many decades . To understand the effectiveness of modern machine learning techniques, and also the limitations of the classical statistical learning approaches , it is of interest to revisit this line of research. Indeed, this direction is currently the subject to a renewal of interests, as testified by some very recent, yet already rather influential papers . The present paper subscribes to this line of work and studies high-dimensional classification within one of the simplest models considered in statistics and machine learning: convex linear estimation with data generated by a teacher perceptron . We will focus on the generalization abilities in this problem, and compare the performances of Bayes-optimal estimation to the more standard Empirical Risk Minimization (ERM). We then compare the results with the prediction of standard generalization bounds that illustrate in particular their limitation even in this simple, yet non-trivial, setting.

We consider a supervised machine learning task, whose dataset is generated by a single layer neural network, often named a teacher , that belongs to the Generalized Linear Model (GLM) class. Therefore, we assume the $n$ samples are generated according to

This particular setting was extensively studied in the past and is interesting in the sense it does not show a computational-to-statistical gap. Yet, our analysis and the set of equations presented in SM III.3 eq. (71) are valid more generically to any other ground truth distributions $P_{{\rm out}^{\star}}$ and $P_{{\rm{w}}^{\star}}$. Finally, the isotropic Gaussian hypothesis of the input vectors X can be relaxed to non-isotropic Gaussian.

The above learning problem has been extensively studied in the statistical physics community using the heuristic replica method . Due to the interest in high-dimensional statistics, they have experienced a resurgence in popularity in recent years. In particular, rigorous works on related problems are much more recent. The authors of established rigorously the replica-theory predictions for the Bayes-optimal generalization error. Here we focus on standard ERM estimation and compare it to the information theoretic baseline results obtained in . Authors of analyzed rigorously M-estimators for the regression case where data are generated by a linear-activation teacher. Here we analyze classification with a more general and non-linear teacher, focusing in particular on the sign-teacher. The case of max-margin loss was studied in with a technically closely related proof, but with a focus on the over-parametrized regime, thus not addressing the questions that we focus on. A range of unregularized losses was also analyzed for a sigmoid teacher (that is very similar to a sign-teacher) again in the context of the double-descent behavior in . Here we focus instead on the regularized case as it drastically improves generalization performances of the ERM and that allows us to compare with the Bayes-optimal estimation as well as to standard generalization bounds. Our proof, as in the above mentioned works and , is based on Gordon’s Gaussian Min-max inequalities , including in particular the effect of the regularization.

Third, in Sec. 4, we design a custom (non-convex) loss and regularizer from the knowledge of the ground truth distributions $P_{{\rm out}^{\star}},P_{{\rm{w}}^{\star}}$ that provably gives a plug-in estimator that efficiently achieves Bayes-optimal performances, including the optimal $\Theta\left(\alpha^{-1}\right)$ rate for the generalization error. Our construction is related to the one discussed in , but is not restricted to convex losses.

Main technical results

In the formulas that arise for this statistical estimation problem, the correlations between the estimator $\hat{{\textbf{w}}}$ and the ground truth vector ${\textbf{w}}^{\star}$ play a fundamental role and we thus define two scalar overlap parameters to measure the statistical reconstruction:

where $\hat{y}\left(\hat{{\textbf{w}}}(\alpha);{\textbf{x}}\right)$ denotes the predicted label, has both at finite $d$ and in the asymptotic limit an explicit expression depending only on the above overlaps $m$ and $q$:

In our synthetic binary classification task, the generalization error of ERM (or equivalently the test error) is given by

The proof, shown in SM. II, is a simple computation based on Gaussian integration. ∎

As $n,d\to\infty$ with $n/d=\alpha=\Theta(1)$, the overlap parameters $m,q$ and the prior’s second moment $\rho_{d,{\rm{w}}^{\star}}$ concentrate to

where parameters $\mu^{\ast}$ and $\delta^{\ast}$ are solutions of

and $g,s$ are two iid standard normal random variables. The solutions $(\mu^{\ast},\delta^{\ast})$ of (9) can be reformulated as a set of fixed point equations

This set of fixed point equations can be finally mapped to the ones obtained equivalently by the heuristic replica method from statistical physics (whose heuristic derivation is shown in SM. IV) as well as the state evolution of the Approximate Message-Passing (AMP) algorithm . Notice that the main reason why we rely on Convex Gaussian Min-lax Theory (CGMT) to make this set of equation rigorous is that we do not know how to prove that the AMP state evolution corresponds to the solution of ERM. Only after having the CGMT proof in hand, it follows that the SE of AMP gives the same equations than the CGMT. As a result, their validity for this convex estimation problem is rigorously established by the following theorem:

As $n,d\to\infty$ with $n/d=\alpha=\Theta(1)$, the overlap parameters $m,q$ concentrate to the fixed point of the following set of equations:

Finally, we shall compare the ERM performances to the Bayes-optimal generalization error. Being the information-theoretically best possible estimator, we will use it as a reference baseline for comparison. The expression of the Bayes-optimal generalization was derived in and proven in and we recall here the result:

For the model (1) with $P_{{\rm{w}}^{\star}}({\textbf{w}}^{\star})=\mathcal{N}_{{\textbf{w}}^{\star}}\left({\textbf{0}},\rho_{d,{\rm{w}}^{\star}}{\rm{I}}_{d}\right)$ with $\rho_{d,{\rm{w}}^{\star}}\underset{d\to\infty}{\longrightarrow}\rho_{{\rm{w}}^{\star}}$, the Bayes-optimal generalization error is quantified by two scalar parameters $q_{\rm b}$ and $\hat{q}_{\rm b}$ that verify asymptotically the set of fixed point equations

Generalization errors

First, to highlight the accuracy of the theoretical predictions, we compare in Figs. 1(a)-2(a) the ERM asymptotic ($d\to\infty$) generalization error with the performances of numerical simulations ($d=10^{3}$, averaged over $n_{s}=20$ samples) of ERM of the training loss eq. (3). Presented for a wide range of number of samples $\alpha$ and of regularization strength $\lambda$, we observe a perfect match between theoretical predictions and numerical simulations so that the error bars are barely visible and have been therefore removed. This shows that the asymptotic predictions are valid even with very moderate sizes. As an information theoretical baseline, we also show the Bayes-optimal performances (black) given by the solution of eq. (13).

As we might expect the square loss gives the worst performances. For low values of the generalization, it leads to an interpolation-peak at $\alpha=1$. The limit of vanishing regularization $\lambda\to 0$ leads to the least-norm or pseudo-inverse estimator $\hat{{\textbf{w}}}_{\rm pseudo}=\left({\textrm{X}}^{\intercal}{\textrm{X}}\right)^{-1}{\textrm{X}}^{\intercal}{\textbf{y}}$. The corresponding generalization error presents the largest interpolation-peak and achieves a maximal generalization error $e_{\rm g}=0.5$. These are well known observations, discussed as early as in , that are object of a renewal of interest under the name double descent, following a recent series of papers . This double descent behavior for the pseudo-inverse is shown in Fig. 1(a) with a yellow line. On the contrary, larger regularization strengths do not suffer this peak at $\alpha=1$, but their generalization error performance is significantly worse than the Bayes-optimal baseline for larger values of $\alpha$. Indeed, as we might expect, for a large number of samples, a large regularization biases wrongly the training. However, even with optimized regularizations, performances of the ridge estimator remains far away from the Bayes-optimal performance.

Both these losses, which are the classical ones used in classification problems, improve drastically the generalization error. First of all, let us notice that they do not display a double-descent behavior. This is due to the fact that our results are illustrated in the noiseless case and that our synthetic dataset is always linearly separable. Optimizing the regularization, our results in Fig. 1(b)-2(a) show both hinge and logistic ERM-based classification approach very closely the Bayes error. This might be an interesting message for practitioners, even though showing it in more realistic settings would be preferable. To offset these results, note that performances of logistic regression on non-linearly separable data are however very poor, as illustrated by our analysis of a rectangle door teacher (see SM. V.6).

As discussed in , both the logistic and hinge estimator converge, for vanishing regularization $\lambda\to 0$, to the max-margin solution. Taking the $\lambda\to 0$ limit in our equations, we thus obtain the max-margin estimator performances. While this is not what gives the best generalization error (as can be seen in Fig.2(a) the logistic with an optimized $\lambda$ has a lower error), the max-margin estimator gives very good results, and gets very close to the Bayes-error.

Defining the regularization value that optimizes the generalization as

we show in Figs. 1(b)-2(a) that both optimal values $\lambda^{\rm opt}\left(\alpha\right)$ (dashed-dotted orange) for logistic and hinge regression decrease to as $\alpha$ grows and more data are given. Somehow surprisingly, we observe in particular that the generalization performances of logistic regression with optimal regularization are extremely close to the Bayes performances. The difference with the optimized logistic generalization error is barely visible by eye, so that we explicitly plotted the difference, which is roughly of order $10^{-5}$.

Ridge regression Fig. 1(a) shows a singular behavior: there exists an optimal value (purple) which is moreover independent of $\alpha$ achieved for $\lambda^{\rm opt}\simeq 0.5708$. This value was first found numerically and confirmed afterwards semi-analytically in SM. V.3.

Finally, we turn to the very instructive behavior at large values of $\alpha$ when a large amount of data is available. First, we notice that the Bayes-optimal generalization error, whose large $\alpha$ analysis is performed in SM. V.1, decreases as $e_{\rm g}^{\rm bayes}\underset{\alpha\to\infty}{\sim}0.4417\alpha^{-1}$. Compared to this optimal value, ridge regression gives poor performances in this regime. For any value of the regularization $\lambda$ — and in particular for both the pseudo-inverse case at $\lambda=0$ and the optimal estimator $\lambda^{\rm opt}$ — its generalization performances decrease much slower than the Bayes rate, and goes only as $e_{\rm g}^{\rm ridge}\!\underset{\alpha\to\infty}{\sim}\!0.2405\alpha^{-1/2}$ (see SM. V.3 for the derivation). Hinge and logistic regressions present a radically different, and more favorable, behavior. Fig. 1(b)-2(a) show that keeping $\lambda$ finite when $\alpha$ goes to $\infty$, does not yield the Bayes-optimal rates. However the max-margin solution (that corresponds to the $\lambda\to 0$ limit of these estimators) gives extremely good performances $e_{\rm g}^{\rm logistic,hinge}\underset{\lambda\to 0}{\sim}e_{\rm g}^{\rm max-margin}\!\underset{\alpha\to\infty}{\sim}\!0.500\alpha^{-1}$ see derivation in SM. V.4). This is the same rate as the Bayes one, only that the constant is slightly higher. However, we do not know whether there is a general criteria that would distinguish when the decay is $\Theta(\alpha^{-1})$ or $\Theta(\alpha^{-1/2})$. Providing such a generic criteria is definitely a line of research we would like to investigate in the future. Moreover, let us point out the work that discusses fast convergence rates $\Theta(n^{-1})$ for the hinge loss, whose analysis for only very large $\alpha$ and Lipshitz functions does not directly apply to our setting.

Given the fact that both the max-margin estimator and the optimized logistic achieve optimal generalization rates going as $\Theta\left(\alpha^{-1}\right)$, it is of interest to compare those rates to the prediction of statistical learning theory bounds. Statistical learning analysis (see e.g. ) relies to a large extent on the Vapnik-Chervonenkis dimension (VC) analysis and on the so-called Rademacher complexity. The uniform convergence result states that if the Rademacher complexity or the Vapnik-Chervonenkis dimension $d_{\rm VC}$ is finite, then for a large enough number of samples the generalization gap will vanish uniformly over all possible values of parameters. Informally, uniform convergence tells us that with high probability, for any value of the weights w, the generalization gap satisfies ${\mathcal{R}}_{\rm population}({\textbf{w}})-{\cal R}_{\rm empirical}^{n}({\textbf{w}})=\Theta\left(\sqrt{d_{\rm VC}/n}\right)$ where $d_{\rm VC}=d-1$ for our GLM hypothesis class. Therefore, given that the empirical risk can go to zero (since our data are separable), this provides a generalization error upper-bound $e_{\rm g}\!\leq\!\Theta(\alpha^{-1/2})$. This is much worse that what we observe in practice, where we reach the Bayes rate $e_{\rm g}=\Theta(\alpha^{-1})$. Tighter bounds can be obtained using the Rademacher complexity, and this was studied recently (using the aforementioned replica method) in for the very same problem. To bring to light interesting conclusions, we reproduced their results and plotted the Rademacher complexity generalization bound in Fig.2 (dashed-green) that decreases as $\Theta\left(\alpha^{-1/2}\right)$ for the binary classification task eq. (2).

One may wonder if this could be somehow improved. Another statistical-physics heuristic computation, however, suggests that, unfortunately, uniform bound are plagued to a slow rate $\Theta\left(\alpha^{-1/2}\right)$. Indeed, the authors of showed with a replica method-style computation that there exists some set of weights, in the binary classification task eq. (2), that leads to $\Theta\left(\alpha^{-1/2}\right)$ rates: the uniform bound is thus tight. The gap observed between the uniform bound and the almost Bayes-optimal results observed in practice in this case is therefore not a paradox, but an illustration that the price to pay for uniform convergence is the inability to describe the optimal rates one can sometimes get in practice. Therefore, we believe, that the fact this phenomena can be observed in a such simple problem sheds an interesting light on the current debate in understanding generalization in deep learning .

Remarking our synthetic dataset is linearly separable, we may try to take this fact into consideration to improve the generalization rate. In particular, it can be done using the max-margin based generalization error for separable data:

Given $S=\{{\textbf{x}}_{1},\cdots,{\textbf{x}}_{n}\}$ such that $\forall\mu\in[1:n],\|{\textbf{x}}_{\mu}\|\leq r$. Let $\hat{{\textbf{w}}}$ the hard-margin SVM estimator on $S$ drawn with distribution $D$. With probability $1-\delta$, the generalization error is bounded by

Reaching Bayes optimality

Given the fact that logistic and hinge losses reach values extremely close to Bayes optimal generalization performances, one may wonder if by somehow slightly altering these losses one could actually reach the Bayesian values with a plug-in estimator obtained by ERM. This is what we achieve in this section, by constructing a (non-convex) optimization problem with a specially tuned loss and regularization from the knowledge of the teacher distributions $P_{\rm out^{\star}}$, $P_{\rm w^{\star}}$, whose solution yields Bayes-optimal generalization. Indeed, in the Bayes-optimal setting, we may directly use the Bayes-optimal AMP algorithm to achieve optimal performances as proven in . Nevertheless, it seems to us interesting to point out that Bayes performances, which require in principle to compute an intractable high-dimensional posterior sampling, can be obtained instead by the easier, more common and practical ERM estimation. Recent insights have shown that indeed one can sometime re-interpret Bayesian estimation as an optimization program in inverse problems. In particular, showed explicitly, on the basis of the non-rigorous replica method of statistical mechanics, that some Bayes-optimal reconstruction problems could be turned into convex M-estimation.

See SM. VI for the derivation. Following these considerations, we provide the following theorem:

The result of empirical risk minimization eq. (3) with $l^{\rm opt}$ and $r^{\rm opt}$ in eq. (17), leads to Bayes optimal generalization error in the high-dimensional regime.

We present only the sketch of the proof here. First we note that the so called Bayes-optimal Generalized Approximate Message Passing (GAMP) algorithm , recalled in SM. VI.1, with Bayes-optimal updates $f_{\rm out}^{\rm bayes}$ and $f_{\rm w}^{\rm bayes}$ in SM. I.3.1 is provably convergent and reaches Bayes-optimal performances (see ). Second, we remark that the GAMP algorithm is valid for ERM estimation with the corresponding updates $f_{\rm out}^{\rm erm}(l,r),f_{\rm w}^{\rm erm}(l,r)$, defined in SM. I.3.2, for a given loss $l$ and regularizer $r$. To achieve Bayes-optimal performances, we design optimal loss $l^{\rm opt}$ and regularizer $r^{\rm opt}$ eq. 17 such that at each time step the ERM denoisers match the Bayes-optimal ones: $f_{\rm out}^{\rm erm}(l^{\rm opt},r^{\rm opt})=f_{\rm out}^{\rm bayes}$ and $f_{\rm w}^{\rm erm}(l^{\rm opt},r^{\rm opt})=f_{\rm w}^{\rm bayes}$. In this context, AMP algorithm for ERM with loss and regularization given by (17) is exactly identical to the Bayes-optimal AMP. This shows that AMP applied to the ERM problem corresponding to (17) both converge to its fixed point and reach Bayes-optimal performances. The theorem finally follows by noting (see ) that the AMP fixed point corresponds to the extremization conditions of the loss. ∎

Acknowledgments

This work is supported by the ERC under the European Unions Horizon 2020 Research and Innovation Program 714608-SMiLe, by the French Agence Nationale de la Recherche under grant ANR-17-CE23-0023-01 PAIL and ANR-19-P3IA-0001 PRAIRIE, and by the US National Science Foundation under grants CCF-1718698 and CCF-1910410. We would also like to thank the Kavli Institute for Theoretical Physics (KITP) for welcoming us during part of this research, with the support of the National Science Foundation under Grant No. NSF PHY-1748958. We also acknowledge support from the chaire CFM-ENS “Science des données”. Part of this work was done when Yue M. Lu was visiting Ecole Normale as a CFM-ENS “Laplace” invited researcher.

References

Supplementary material

We recall the supervised machine learning task considered in the main manuscript eq. (1), whose dataset is generated by a single layer neural network, often named a teacher, that belongs to the Generalized Linear Model (GLM) class. Therefore we assume the $n$ samples are drawn according to

I.2 Bayes-optimal and ERM estimation

Inferring the above statistical model from observations $\{{\textbf{y}},{\textrm{X}}\}$ can be tackled in several ways. In particular, Bayesian inference provides a generic framework for statistical estimation based on the high-dimensional, often intractable, posterior distribution

I.3 Denoising distributions and updates

Analyzing the posterior distribution eq. (19) in the high-dimensional regime will boil down to introducing the scalar denoising distributions $Q_{{\rm{w}}},Q_{{\rm out}}$ and their respective normalizations $\mathcal{Z}_{{\rm{w}}}$, $\mathcal{Z}_{{\rm out}}$

We define as well the denoising functions, that play a central role in Bayesian inference. Note in particular that they correspond to the updates of the Approximate Message Passing algorithm in that we recalled in Sec. VI.1. They are defined as the derivatives of $\log\mathcal{Z}_{{\rm{w}}}$ and $\log\mathcal{Z}_{{\rm out}}$, namely

In Bayes-optimal estimation, the ground truth prior and channel distributions $P_{{\rm{w}}^{\star}}(w)$ and $P_{{\rm out}^{\star}}\left(y|z\right)$ of the teacher eq. (1) are known. Hence, replacing $P_{{\rm{w}}}$ and $P_{{\rm out}}$ in (22), we obtain the Bayes-optimal scalar denoising distributions in terms of which the Bayes-optimal free entropy eq. (95) is written

and the denoising updates are therefore given by eq. (23) with the corresponding distributions

Before defining similar denoising functions to analyze the MAP for ERM estimation, we first recall the definition of the Moreau-Yosida regularization.

Let $\Sigma>0$, $f(,z)$ a convex function in $z$. Defining the regularized functional

the Moreau-Yosida regularization $\mathcal{M}_{\Sigma}$ and the proximal map $\mathcal{P}_{\Sigma}$ are defined by

where $(,z)$ denotes all the arguments of the function $f$, where $z$ plays a central role. The MAP denoising functions for any convex loss $l(,.)$ and convex separable regularizer $r(.)$ can be written in terms of the Moreau-Yosida regularization or the proximal map as follows

The above updates can be considered as definitions, but it is instructive to derive them from the generic definition of the denoising distributions eq. (23) if we maximize the posterior distribution. This is done by taking, in a physics language, a zero temperature limit and we present it in details in the next paragraph.

To have access to the maximum of the generic distributions eq. (22), we introduce a fictive noise/temperature $\Delta$ or inverse temperature $\beta$, $\Delta=\frac{1}{\beta}$. In particular for Bayes-optimal estimation this temperature is finite and fixed to $\Delta=\beta=1$. Indeed with the mapping eq. (21), minimizing the loss function $\mathcal{L}$ (20) is equivalent to maximize the posterior distribution. Therefore it can be done by taking the zero noise/temperature limit $\Delta\to 0$ of the channel and prior denoising distributions $Q_{{\rm out}}$ and $Q_{{\rm{w}}}$. It is the purpose of the following paragraphs where we present the derivation leading to the result (29).

Note that the case of the square loss $l(y,z)=\frac{1}{2}\left(y-z\right)^{2}$ is very specific. Its channel distribution simply reads $P_{\rm out}\left(y|z\right)=\frac{e^{-\frac{1}{2\Delta}(y-z)^{2}}}{\sqrt{2\pi\Delta}}$ and is therefore equivalent to predict labels $y$ according to a noisy Gaussian linear model $y=z+\sqrt{\Delta}\xi$, where $\xi\sim\mathcal{N}(0,1)$ and $\Delta$ denotes therefore the real noise of the model.

In order to obtain a non trivial limit and a closed set of equations when $\Delta\to 0$, we must define rescaled variables as follows:

where we denote the rescaled quantities after taking the limit $\Delta\to 0$ by $\dagger$. Similarly to eq. (26), we introduce therefore the rescaled functional

such that, injecting $P_{\rm out}^{\rm map}$, the channel denoising distribution $Q_{{\rm out}}^{\rm map}$ and the corresponding partition function $\mathcal{Z}_{\rm out}^{\rm map}$ eq. (22) simplify in the zero temperature limit as follows:

that involve the proximal map and the Moreau-Yosida regularization defined in eq. (28). Finally taking the zero temperature limit, the MAP denoising function $f_{{\rm out},{\dagger}}^{\rm map}$ leads to the result (29):

Similarly as above, using the mapping eq. (21), for a convex and separable regularizer $r$, the corresponding prior distribution at temperature $\Delta$ can be written

such that in the zero temperature limit, the prior denoising distribution $Q_{{\rm{w}}}^{\rm map}$ and the partition function $\mathcal{Z}_{\rm{w}}^{\rm map}$ reduce to

that involve again the proximal map $\mathcal{P}_{\Lambda_{\dagger}^{-1}}$ and the Moreau-Yosida regularization $\mathcal{M}_{\Lambda_{\dagger}^{-1}}$ defined in eq. (28). Finally the MAP denoising update $f_{\rm w,{\dagger}}^{\rm map}$ is simply given by:

I.4 Applications

In this section we list the explicit expressions of the Bayes-optimal eq. (25) and ERM eq. (29) denoising functions largely used to produce the examples in Sec. 3.

The Bayes-optimal denoising functions (25) are detailed in the case of a linear, sign and rectangle door channel with a Gaussian noise $\xi\sim\mathcal{N}(0,1)$ and variance $\Delta\geq 0$, and for Gaussian and sparse-binary weights.

The proximal map for the square loss $l^{\rm square}(y,z)=\frac{1}{2}(y-z)^{2}$ is easily obtained and reads

The proximal map of the hinge loss $l^{\rm hinge}(y,z)=\max\left(0,1-yz\right)$

can be expressed analytically by distinguishing all the possible cases:

$1-yz<0$: $\mathcal{L}_{0}=\frac{1}{2V}\left(z-\omega\right)^{2}\Rightarrow$ $z^{\star}=\omega$ if $yz^{\star}<1\Leftrightarrow z^{\star}=\omega$ if $\omega y<1$.

$1-yz>0$: $\mathcal{L}_{0}=\frac{1}{2V}\left(z-\omega\right)^{2}+1-yz\Rightarrow(z^{\star}-\omega)=yV\Leftrightarrow z^{\star}=\omega+Vy$ if $1-yz^{\star}>0\Leftrightarrow z^{\star}=\omega+Vy$ if $\omega y<1-y^{2}V=1-V$, as $y^{2}=1$.

Hence we have one last region to study $1-V<\omega y<1$. It follows $y(1-V)<\omega<y$:

Finally we obtain a simple analytical expression for the proximal and its derivative

Hence with (29), the hinge denoising function and its derivative read

In general, finding the proximal map in (29) is intractable. In particular, it is the case for the logistic loss considered in Sec. V.5. However assuming the convex loss is a generic two times differentiable function $l\in\mathcal{D}^{2}$, taking the derivative of the proximal map

verifies therefore the implicit equations:

Once those equations solved, the denoising function and its derivative are simply expressed as

with $z^{\star}\left(y,\omega,V\right)=\mathcal{P}_{V}\left[l(y,.)\right](\omega)$ solution of (45).

Appendix II Binary classification generalization errors

In this section, we present the computation of the asymptotic generalization error

leading to expressions in Proposition. 2.1 and Thm. 2.4. The computation at finite dimension is similar if we do not consider the limit $d\to\infty$.

The generalization error $e_{\rm g}$ is the prediction error of the estimator $\hat{{\textbf{w}}}$ on new samples $\{{\textbf{y}},{\textrm{X}}\}$, where X is an iid Gaussian matrix and y are $\pm 1$ labels generated according to (18):

The classification generalization error is given by the probability that the predicted labels $\hat{y}$ and the true labels $y$ do not match. To compute it, first note that the vectors $({\textbf{z}},\hat{{\textbf{z}}})$ averaged over all possible ground truth vectors ${\textbf{w}}^{\star}$ (or equivalently labels $y$) and input matrix X follow in the large size limit a joint Gaussian distribution with zero mean and covariance matrix

The asymptotic generalization error depends only on the covariance matrix $\sigma$ and as the samples are iid it reads

where we used the fact that $\atan(x)=\frac{\pi}{2}-\frac{1}{2}\acos\left(\frac{x^{2}-1}{1+x^{2}}\right)$ and $\frac{1}{2}\acos(2x^{2}-1)=\acos(x)$. Finally

II.2 Bayes-optimal generalization error

The Bayes-optimal generalization error for classification is equal to eq. (54) where the Bayes estimator $\hat{{\textbf{w}}}$ is the average over the posterior distribution eq. (19) denoted $\langle.\rangle$, knowing the teacher prior $P_{{\rm{w}}^{\star}}$ and channel $P_{{\rm out}^{\star}}$ distributions: $\hat{{\textbf{w}}}=\langle{\textbf{w}}\rangle_{{\textbf{w}}}$. Hence the parameters $\sigma_{\hat{{\rm{w}}}}$ and $\sigma_{{\rm{w}}^{\star}\hat{{\rm{w}}}}$ read in the Bayes-optimal case

Using Nishimori identity , we easily obtain $m_{\rm b}=q_{\rm b}$ which is solution of eq. (13). Therefore the generalization error simplifies

II.3 ERM generalization error

The generalization error of the ERM estimator is given again by eq. (54) with parameters

where the parameters $m,q$ are the asymptotic ERM overlaps solutions of eq. (11) and that finally lead to the ERM generalization error for classification:

Appendix III Proofs of the ERM fixed points

We consider in this section that the data have been generated by a teacher (18) with Gaussian weights

In what follows, we prove a theorem that characterizes the asymptotic performance of empirical risk minimization

As $n,d\to\infty$ with $n/d=\alpha=\Theta(1)$, the overlap parameters $m,q$ concentrate to

where the parameters $\mu^{\ast},\delta^{\ast}$ are the solutions of

Here, $\mathcal{M}_{\tau}[l(,.)](x)$ is the Moreau-Yosida regularization defined in (28), and $g,s$ are two iid standard normal random variables.

Since the teacher weight vector ${\textbf{w}}^{\star}$ is independent of the input data matrix X, we can assume without loss of generality that

where $s_{i}$ is the $i$th entry of the Gaussian vector s in (61).

Let $\Phi_{d}$ denote the cost of the ERM in (58), normalized by $d$. Using our new representations introduced above, we have

where ${\textbf{b}}_{i}^{\intercal}$ denotes the $i$th row of B. Since the loss function $l(y_{i},z)$ is convex with respect to $z$, we can rewrite it as

where $l^{\ast}(y_{i},q)=\sup_{z}\{qz-l(y_{i},z)\}$ is its convex conjugate. Substituting (64) into (63), we have

where $h\sim\mathcal{N}\left({\textbf{0}},{\rm{I}}_{d-1}\right)$ and $g\sim\mathcal{N}\left({\textbf{0}},{\rm{I}}_{n}\right)$ are two independent standard normal vectors. It follows from Gordon’s minimax comparison inequality (see, e.g., ) that

for any constants $c$ and $\epsilon>0$. This implies that $\widetilde{\Phi}_{d}$ serves as a surrogate of $\Phi_{d}$. Specifically, if $\widetilde{\Phi}_{d}$ concentrates around some deterministic limit $c$ as $d\to\infty$, so does $\Phi_{d}$. In what follows, we proceed to solve the surrogate problem in (66). First, let $\delta=\norm{{\textbf{v}}}/\sqrt{d}$. It is easy to see that (66) can be simplified as

In $(a)$, we have introduced an auxiliary variable $\tau$ to rewrite $-\delta\frac{\norm{{\textbf{q}}}}{\sqrt{d}}\frac{\norm{{\textbf{h}}}}{\sqrt{d}}$ as

As $n,d\to\infty$ with $n/d=\alpha=\Theta(1)$, the overlap parameters $m,q$ concentrate to

where parameters $\mu^{\ast},\delta^{\ast}$ are solutions of

and $g,s$ are two iid standard normal random variables. The solutions $(\mu^{\ast},\delta^{\ast},\tau^{\ast})$ of (69) can be reformulated as a set of fixed point equations

We start by deriving (69) as a special case of (60). To that end, we note that

where to reach the last equality we have used the fact that $y\in\{\pm 1\}$. Substituting this special form into (60) and recalling (62), we reach (69).

Finally, to obtain the fixed point equations (70), we simply take the partial derivatives of the cost function in (69) with respect to $\mu,\delta,\tau$, and use the following well-known calculus rules for the Moreau-Yosida regularization :

III.2 Replica’s formulation

The replica computation presented in Sec. IV boils down to the characterization of the overlaps $m,q$ in the high-dimensional limit $n,d\to\infty$ with $\alpha=\frac{n}{d}=\Theta(1)$, given by the solution of a set of, in the most general case, six fixed point equations over $m,q,Q,\hat{m},\hat{q},\hat{Q}$. Introducing the natural variables $\Sigma\equiv Q-q$, $\hat{\Sigma}\equiv\hat{Q}+\hat{q}$, $\eta\equiv\frac{m^{2}}{\rho_{{\rm{w}}^{\star}}q}$ and $\hat{\eta}\equiv\frac{\hat{m}^{2}}{\hat{q}}$, the set of fixed point equations for arbitrary $P_{{\rm{w}}^{\star}},P_{{\rm out}^{\star}}$, convex loss $l(y,z)$ and regularizer $r(w)$, is finally given by

The above equations depend on the Bayes-optimal partition functions $\mathcal{Z}_{{\rm{w}}^{\star}},\mathcal{Z}_{{\rm out}^{\star}}$ defined in eq. (24), the updates $f_{{\rm{w}}^{\star}}$, $f_{{\rm out}^{\star}}$ in eq. (25) and the ERM updates $f_{{\rm{w}}}$, $f_{{\rm out}}$ eq. (29).

Hence, removing the hat variables in eqs. (71), the set of fixed point equations can be rewritten in a more compact way leading to the Corollary. 2.3 that we recall here:

The set of fixed point equations (70) in Thm. III.2 that govern the asymptotic behaviour of the overlaps $m$ and $q$ is equivalent to the following set of equations, obtained from the heuristic replica computation:

For the sake of clarity, we use the abusive notation $\mathcal{P}_{V}(y,\omega)=\mathcal{P}_{V}[l(y,.)](\omega)$, and we remove the $\ast$.

We first map the Gordon’s parameters ($\mu,\delta,\tau)$ in eq. (70) to ($m,q,\Sigma$) in eq. (73):

From eq. (24), we can rewrite the channel partition function $\mathcal{Z}_{{\rm out}^{\star}}$ and its derivative

where $z$ denotes a standard normal random variable.

Let us start with the equation over $m$ in eq. (73):

where we used the fact that $P_{{\rm out}^{\star}}\left(y|z\right)=\delta(y-\varphi_{{\rm out}^{\star}}(z))$, the change of variables

and finally in the last equality the definition of the second fixed point equation in eqs. (70):

Let us now compute the equation over $q$ in eq. (73):

Let us conclude with the equation over $\Sigma$ in eq. (73) that we encountered in eq. (76). Let us first compute

therefore, the last equation over $\Sigma$ in eq. (73) reads

where we used the Stein’s lemma in the last equality, we finally obtain

Appendix IV Replica computation for Bayes-optimal and ERM estimations

In this section, we present the statistical physics framework and the replica computation leading to the general set of fixed point equations (11) and to the Bayes-optimal fixed point equations (13).

known as the so-called partition function in the physics literature. It is the generating function of many useful statistical quantities and is defined by

where we introduced the variable ${\textbf{z}}=\frac{1}{\sqrt{d}}{\textrm{X}}{\textbf{w}}$. However in the considered high-dimensional regime ($d\to\infty,n\to\infty,\alpha=\Theta(1)$), we are interested instead in the averaged (over instances of input data X and teacher weights ${\textbf{w}}^{\star}$ or equivalently over the output labels y) free entropy $\Phi$ defined as

The replica method is an heuristic method of statistical mechanics that allows to compute the above average over the random dataset $\{{\textbf{y}},{\textrm{X}}\}$. We show in the next section the classical computation for the Generalized Linear Model hypothesis class and iid data X.

IV.2 Replica computation

We present here the replica computation of the averaged free entropy $\Phi(\alpha)$ in eq. (80) for general prior distributions $P_{{\rm{w}}},P_{{\rm{w}}^{\star}}$ and channel distributions $P_{{\rm out}},P_{{\rm out}^{\star}}$, so that the computation remain valid for both Bayes-optimal and ERM estimation (with any convex loss $l$ and regularizer $r$).

The average in eq. (80) is intractable in general, and the computation relies on the so called replica trick that consists in applying the identity

Thus the replicated partition function in eq. (81) can be written as

with the decoupled channel $P_{{\rm out}}\left({\textbf{y}}|{\textbf{z}}\right)=\displaystyle\prod_{\mu=1}^{n}P_{{\rm out}}\left(y_{\mu}|z_{\mu}\right)$. Note that the average over y is equivalent to the one over the ground truth vector ${\textbf{w}}^{\star}$, which can be considered as a new replica ${\textbf{w}}^{0}$ with index $a=0$ leading to a total of $r+1$ replicas.

because the channel and the prior distributions factorize. Introducing the change of variable and the Fourier representation of the $\delta$-Dirac function, which involves a new ad-hoc parameter $\hat{Q}$:

Finally switching the two limits $r\to 0$ and $d\to\infty$, the quenched free entropy $\Phi$ simplifies as a saddle point equation

with $Q^{0}=\rho_{{\rm{w}}^{\star}}=\frac{1}{d}\|{\textbf{w}}^{\star}\|_{2}^{2}$. Let’s compute separately the terms involved in the functional $\Phi^{(r)}(Q,\hat{Q})$ eq. (86) with this ansatz: the first is a trace term, the second a term $\Psi_{{\rm{w}}}^{(r)}$ depending on the prior distributions $P_{\rm{w}}$, $P_{{\rm{w}}^{\star}}$ and finally the third a term $\Psi_{{\rm out}}^{(r)}$ that depends on the channel distributions $P_{{\rm out}^{\star}}$,$P_{\rm out}$.

The trace term can be easily computed and takes the following form:

Using the same kind of Gaussian transformation, we obtain

IV.3 ERM and Bayes-optimal free entropy

Taking carefully the derivative and the $r\to 0$ limit imposes $\hat{Q}^{0}=0$ and we finally obtain the replica symmetric free entropy $\Phi_{\rm rs}$:

where again $\mathcal{Z}_{{\rm out}^{\star}}$ and $\mathcal{Z}_{{\rm{w}}^{\star}}$ are defined in eq. (24) and depend on the teacher, while the denoising functions $\mathcal{Z}_{{\rm out}}$ and $\mathcal{Z}_{{\rm{w}}}$ depend on the inference model. In particular, we explicit in the next sections the above free entropy in the case of ERM and Bayes-optimal estimation.

with the Moreau-Yosida regularization (28).

with free entropy terms $\Psi_{{\rm{w}}}^{\rm b}$ and $\Psi_{{\rm out}}^{\rm b}$ given by

and again $\mathcal{Z}_{{\rm out}^{\star}}$ and $\mathcal{Z}_{{\rm{w}}^{\star}}$ are defined in eq. (24). The above replica symmetric free entropy in the Bayes-optimal case has been rigorously proven in .

IV.4 Sets of fixed point equations

As highlighted in Sec. II, the asymptotic overlaps $m,q$ measure the performances of the ERM or Bayes-optimal statistical estimators, whose behaviours are respectively characterized by extremizing the free entropy (92) and (95). This section is devoted to derive the corresponding sets of fixed point equations.

Extremizing the free entropy eq. (92), we easily obtain the set of six fixed point equations

These equations can be formulated as functions of the partition functions $\mathcal{Z}_{{\rm out}^{\star}}$, $\mathcal{Z}_{{\rm{w}}^{\star}}$ and the denoising functions $f_{{\rm out}^{\star}},f_{{\rm{w}}^{\star}},f_{\rm out},f_{{\rm{w}}}$ defined in eq. (25) and eq. (29). The derivation is shown in Appendix. IV.5.3 and defining the natural variables $\Sigma=Q-q$, $\hat{\Sigma}=\hat{Q}+\hat{q}$, $\eta\equiv\frac{m^{2}}{\rho_{{\rm{w}}^{\star}}q}$ and $\hat{\eta}\equiv\frac{\hat{m}^{2}}{\hat{q}}$, it can be written as

and we finally obtain the set of equations eqs. (71).

Extremizing the Bayes-optimal free entropy eq. (95), we easily obtain the set of 2 fixed point equations over the scalar parameters $q_{\rm b},\hat{q}_{\rm b}$. In fact, it can also be deduced from eq. (97) using the Nishimori conditions $f_{{\rm{w}}}=f_{{\rm{w}}^{\star}}$, $f_{{\rm out}}=f_{{\rm out}^{\star}}$, $m=q=q_{\rm b},\Sigma=\rho_{{\rm{w}}^{\star}}-q,\hat{m}=\hat{q}=\hat{q}_{\rm b}$ and $\hat{Q}=0$ that lead to the result (13) in Thm. 2.4, from

IV.5 Useful derivations

In this section, we give useful computation steps that we used to transform the sets of fixed point equations (96).

In specific simple cases, the prior free entropy term

In the Bayes-optimal case for $\rho_{{\rm{w}}^{\star}}=1$, the computation is similar and is given by the above expression with $\lambda=1$, $\hat{Q}=0$, $\hat{m}=\hat{q}$:

We recover exactly the same free entropy term than for Gaussian prior teacher eq. (99) for $\rho_{{\rm{w}}^{\star}}=1$.

Let’s compute, in full generality, the derivative of the partition functions defined in Sec. 22 and that will be useful to simplify the set (96).

We recall the set of fixed point equations eq. (96)

that can be simplified and formulated as functions of $\mathcal{Z}_{{\rm out}^{\star}}$, $\mathcal{Z}_{{\rm{w}}^{\star}}$,$f_{{\rm out}^{\star}},f_{{\rm{w}}^{\star}},f_{\rm out}$, and $f_{{\rm{w}}}$ defined in eq. (25) and eq. (29), using the derivatives in (102).

Appendix V Applications

In this section, we provide details of the results presented in Sec. 3. In particular as an illustration, we consider a Gaussian teacher ($\rho_{{\rm{w}}^{\star}}=1$) with a noiseless sign activation:

whose corresponding denoising functions are derived in eq. (39) and eq. (41).

Using expressions eq. (39) and eq. (41), corresponding to the teacher model eq. (110), the prior equation eq. (98) can be simplified while the channel one has no analytical expression. Hence the set of fixed point equations eqs. (100) for the model eq. (110) read

Let us derive the large $\alpha$ behaviour of the Bayes-optimal generalization error eq. (55) that depends only on the overlap $q_{\rm b}$ solution of eq. (111). $q_{\rm b}$ measures the correlation with the ground truth, so we expect that in the limit $\alpha\to\infty$, $q_{\rm b}\to 1$. Therefore, we need to extract the behaviour of $\hat{q}_{\rm b}$ in eq. (111). Injecting expressions $\mathcal{Z}_{{\rm out}^{\star}}$ and $f_{{\rm out}^{\star}}$ from eq. (39), we obtain

where the last integral can be computed in the limit $q_{\rm b}\to 1$:

with $c_{0}\equiv\int{\rm d}\eta\frac{e^{-\eta^{2}}}{1+\erf\left(\frac{\eta}{\sqrt{2}}\right)}\simeq 2.83748$. Finally, we obtain in the large $\alpha$ limit:

with $k\equiv\frac{2c_{0}}{\pi\sqrt{2\pi}}\simeq 0.720647$. The above equations can be solved analytically and lead to:

and therefore the Bayes-optimal asymptotic generalization error is given by

In general for a generic loss, the proximal eq. (29) has no analytical expression, just as the fixed point equations (97). The square loss is particular in the sense eqs. (97) have a closed form solution. Also the Hinge loss has an analytical proximal. Apart from that, eqs. (97) must be solved numerically. However it is useful to notice that the proximal can be easily found for a two times differentiable loss using eq. (46). This is for example the case of the logistic loss.

The prior equations over $m,q,\Sigma$ are already derived in eq. (113) and remain valid. Combining eq. (39) for the considered sign channel with a potential additional Gaussian noise $\Delta^{\star}$ in (110) and the square loss eq. (43), the channel fixed point equations for $\hat{q},\hat{m},\hat{\Sigma}$ eqs. (97) lead to

We analyze the fixed point equations eqs. (114) for the pseudo-inverse estimator, that is in the limit $\lambda\to 0$.

Combining the two first equations over $\Sigma$ and $\hat{\Sigma}$ in (114), we obtain

that exhibits two different behaviour depending if $\alpha<1$ or $\alpha>1$.

In this regime $\alpha<1$, eq. (115) becomes

that leads to the closed set of equations in the limit $\lambda\to 0$

and the corresponding generalization error

Note in particular that $e_{\rm g}^{\rm pseudo}\left(\alpha\right)\underset{\alpha\to 1}{\longrightarrow}0.5$, meaning that the interpolation peak at $\alpha=1$ reaches the maximum generalization error.

In the limit $\lambda\to 0$, the fixed point equations eqs. (114) reduce to

and the corresponding generalization error

From this expression we easily obtain the large $\alpha$ behaviour of the pseudo-inverse estimator:

where $C=\frac{\pi}{2}\left(1+\Delta^{\star}\right)-1$ and $c=\frac{\sqrt{C}}{\pi}$. In particular for a noiseless teacher $\Delta^{\star}=0$, $c=\sqrt{\frac{\pi-2}{2\pi^{2}}}\simeq 0.240487$, leading to

Let us now consider the set of fixed point equation eq. (114) for finite $\lambda\neq 0$. Defining

the equations can be in fact fully solved analytically and read

Expanding the ratio $\frac{m}{\sqrt{q}}$ in the large $\alpha$ limit, we obtain

Thus, the asymptotic generalization error for ridge regression with any regularization strength $\lambda\geq 0$ decrease as $\frac{0.2405}{\sqrt{\alpha}}$, similarly to the pseudo-inverse result.

The optimal value $\lambda^{\rm opt}(\alpha)$, introduced in Sec. 3, which minimizes the generalization error at a given $\alpha$ can be found taking the derivative of $\frac{m}{\sqrt{q}}$ and is written as the root of the following functional

Unfortunately, this functional cannot be analyzed analytically. Instead we plot its value for a wide range of $\alpha$ as a function of $\lambda$ (for $\Delta^{\star}=0$) and we observe in particular that there exists a unique value $\lambda^{\rm opt}\simeq 0.570796$ as illustrated in Fig. 4 (left) that is independent of $\alpha$. As an illustration, we show the generalization error of ridge regression with the optimal regularization $\lambda^{\rm opt}=0.5708$ compared to the Bayes-optimal performances in Fig. 4 (right).

The hinge loss $l^{\rm hinge}(y,z)=\max\left(0,1-yz\right)$ is linear by part and is therefore another simple example of analytical loss to analyze. In particular its proximal map can computed in eq. (44) and the corresponding denoising functions read:

The fixed point equations eq. (97) have unfortunately no closed form and need to be solved numerically.

As proven in both the hinge and logistic estimators converge to the max-margin solution in the limit $\lambda\to 0$ as soon as the data are linearly separable. We will start with the fixed point equations for hinge, whose denoising functions (124) are analytical. Taking the $\lambda\to 0$ limit is non-trivial and we need therefore to introduce some rescaled variables to obtain a closed set of equations. Numerical evidences at finite $\alpha$ show that we shall use the following rescaled variables:

The fixed point equations eq. (97) simplify and become

Numerically at large $\alpha$ (and $\lambda\to 0$), we obtain the following scalings

Therefore, in order to close the equations, we introduce new variables $(c_{q},c_{\eta})$ such that

In this limit, we can extract the large $\alpha$ behaviours of integrals $\mathcal{I}_{\hat{m}},\mathcal{I}_{\hat{q}},\mathcal{I}_{\hat{\Sigma}}$:

where $\mathcal{I}_{\hat{m}}^{\infty},\mathcal{I}_{\hat{q}}^{\infty},\mathcal{I}_{\hat{\Sigma}}^{\infty}$ are $\Theta(1)$ and read

Hence the set of fixed-point equations eq. (125) simplifies to:

which can be closed by rewriting the equations eqs. (128):

Equivalently $(c_{q}^{\star},c_{\eta}^{\star})$ is the root of the set of non-linear fixed point equations $(F_{\eta}(c_{q},c_{\eta}),F_{q}(c_{q},c_{\eta}))$:

that cannot be solved analytically. However a unique numerical solution is found and lead to $(c_{q}^{\star},c_{\eta}^{\star})=(0.9911,2.4722)$. Therefore the generalization error of the max-margin estimator in the large $\alpha$ regime is given by

with $K=\frac{\sqrt{c_{\eta}^{\star}}}{\pi}\simeq 0.5005$, leading to

V.5 Logistic regression

The logistic loss is a combination of the cross entropy loss $l(y,z)=-y\log(\sigma(z))-(1-y)\log(1-\sigma(z))$ with as sigmoid activation function $\sigma$, that simplifies for binary labels $y\pm 1$ to $l^{\rm logistic}(y,z)=\log(1+\exp(-yz))$ with the two first derivatives given by

Its proximal is not analytical, but it can be written as the solution of the implicit equation (45) providing the corresponding denoising functions (46). Solving the fixed point equations (97), we obtain performances that approach closely the Bayes-optimal baseline as illustrated in Fig. 5 (left).

V.6 Logistic with non-linearly separable data - A rectangle door teacher

Appendix VI Reaching Bayes optimality

In this section, we propose a derivation inspired by of the fine-tuned loss and regularizer (17) discussed in Sec. 4. We assume that the dataset is generated by a teacher (18) such that $\mathcal{Z}_{{\rm out}^{\star}}(.,\omega,.)$ and $\mathcal{Z}_{{\rm{w}}^{\star}}(\gamma,.)$ are respectively log-concave in $\omega$ and $\gamma$. The derivation is based on the GAMP algorithm introduced in for the model eq. (1), that we start by recalling.

The GAMP algorithm can be written as the following set of iterative equations that depend on the update functions (23):

It has been proven in that the GAMP algorithm with Bayes-optimal update functions $f_{{\rm{w}}}=f_{{\rm{w}}^{\star}}$ and $f_{{\rm out}}=f_{{\rm out}^{\star}}$ (25) converges to the Bayes-optimal performances in the large size limit. Yet the GAMP denoising functions are generic and can be chosen as will depending on the statistical estimation method. In particular we may choose the denoising functions for Bayes-optimal estimation (25) or the ones corresponding to ERM estimation (29)

whose corresponding GAMP algorithms (137) will achieve potentially different fixed points and thus different performances. As it is proven that GAMP with Bayes-optimal updates lead to the optimal generalization error, so that ERM matches the same performances it is sufficient to enforce that at each time step $t$ the Bayes-optimal and ERM denoising functions are equal $f^{\rm bayes}=f^{\rm erm}$. Enforcing these two constraints will lead to the expressions for the optimal loss $l^{\rm opt}$ and regularizer $r^{\rm opt}$, so that ERM matches Bayes-optimal performances.

VI.2 Matching Bayes-optimal and ERM performances

Imposing the equality on the channel updates we obtain

Integrating, leaving aside the constant that will not influence the final result, and taking the Moreau-Yosida regularization on both sides, we obtain:

where we invert the Moreau-Yosida regularization in the last equality that is valid as long as $\mathcal{Z}_{{\rm out}^{\star}}(y,\omega,V)$ is assumed to be log-concave in $\omega$, (see for a derivation). We finally obtain

Let us perform the same computation for the prior updates. First we introduce a rescaled denoising distribution:

Imposing the equivalence of the Bayes-optimal and ERM prior update,

and assuming that $\mathcal{Z}_{\rm w}(\gamma,\Lambda)$ is log-concave in $\gamma$, we may invert the Moreau-Yosida regularization, that leads to:

The last step, is to characterize the variances $V$ and $\Lambda$ involved in (139) and (143) that are so far undetermined. To achieve the Bayes-optimal performances, we therefore need to use the variances $V$ and $\Lambda$ solutions of the Bayes-optimal GAMP algorithm (137). In the large size limit, these quantities concentrate and are given by the State Evolution (SE) of the GAMP algorithm, that we recall herein.

In the large size limit, the expectation of the parameter $V$ and $\Lambda$ over the ground truth ${\textbf{w}}^{\star}$ and the input data X lead to :

where $q_{\rm b}$ and $\hat{q}_{\rm b}$ are solutions of the Bayes-optimal set of fixed point equations eq. (13).

VI.3 Summary and numerical evidences

Choosing the fine-tuned (potentially non-convex depending on $\mathcal{Z}_{{\rm out}^{\star}}$ and $\mathcal{Z}_{{\rm{w}}^{\star}}$) loss and regularizer

with $q_{\rm b}$ and $\hat{q}_{\rm b}$ are solutions of the Bayes-optimal set of fixed point equations eq. (13), we showed that ERM can provably match the Bayes-optimal performances. In particular we illustrated the behaviour of the optimal loss and regularizer $\lambda^{\rm opt}$ and $r^{\rm opt}$ for the model (2) in Fig. 3 of the main text. Note in particular that even though the loss $l^{\rm opt}$ is not convex (but seems quasi-convex), numerical simulations of ERM with (145) (black dots) presented in Fig. 6 show that ERM achieves indeed the Bayes-optimal performances (black line) even at finite dimension.