# Error Scaling Laws for Kernel Classification under Source and Capacity
Conditions

Hugo Cui  Statistical Physics Of Computation Laboratory, École Polytechnique
Fédérale de Lausanne (EPFL)  Bruno Loureiro  Information Learning and Physics
Laboratory, École Polytechnique Fédérale de Lausanne (EPFL)  Florent Krzakala
Information Learning and Physics Laboratory, École Polytechnique Fédérale de
Lausanne (EPFL)  Lenka Zdeborová  Statistical Physics Of Computation
Laboratory, École Polytechnique Fédérale de Lausanne (EPFL)

###### Abstract

In this manuscript we consider the problem of kernel classification. While
worst-case bounds on the decay rate of the prediction error with the number of
samples are known for some classifiers, they often fail to accurately describe
the learning curves of real data sets. In this work, we consider the important
class of data sets satisfying the standard source and capacity conditions,
comprising a number of real data sets as we show numerically. Under the
Gaussian design, we derive the decay rates for the misclassification
(prediction) error as a function of the source and capacity coefficients. We
do so for two standard kernel classification settings, namely margin-
maximizing Support Vector Machines (SVM) and ridge classification, and
contrast the two methods. We find that our rates tightly describe the learning
curves for this class of data sets, and are also observed on real data. Our
results can also be seen as an explicit prediction of the exponents of a
scaling law for kernel classification that is accurate on some real datasets.

##  I Introduction and related work

A recent line of work [1, 2, 3, 4] has empirically evidenced that the test
error of neural networks often obey scaling laws with the number of parameters
of the model, training set size, or other model parameters. Because of their
implications in terms of relating performance and model size, these findings
have been the object of sustained theoretical attention. Authors of [5] relate
the decay rate of the test loss with the number of parameters to the intrinsic
dimension of the data. This idea is refined by [6] for the case of regression
tasks, building on the observation that in a number of settings, the
covariance of the learnt features exhibits a power-law spectrum, whose rate of
decay controls the scaling of the error. This investigation is actually very
closely related to another large body of works. In fact, the study of a power-
law features spectrum (and of a target function whose components in the
corresponding eigenbasis also decay as a power-law) has a long history in the
kernel literature, dating back to the seminal works of [7, 8]. The
corresponding rates governing the power-laws are respectively known as the
capacity and source coefficients, and the scaling of the test error with the
training set size can be entirely characterized in terms of these two numbers.
While the study of kernel ridge regression [7, 8, 9, 10, 11, 12, 13, 14, 15]
therefore offers a rich viewpoint on the question of neural scaling laws with
the training set size, little is so far known for kernel classification. Since
ascertaining the test error decay under source and capacity conditions would
automatically translate into neural scaling laws in classification tasks –
similarly to [6] for regression – this is a question of sizeable interest
addressed in the present work.

### Related works

#### Neural scaling laws —

A number of works [1, 2, 3, 4] have provided empirical evidence of scaling
laws in neural networks, with the number of parameters, training samples,
compute, or other observables. These findings motivated theoretical
investigations of the underlying mechanisms. Authors of [5] show how the
scaling of the test loss with the number of parameters is related to the
intrinsic dimension of the data. This dimension is further tied in with the
kernel spectrum by [6], a work that leverages the kernel ridge regression
viewpoint to translate, in turn, the decay of the spectrum to test error
rates. Authors of [16] similarly study a simple toy model where the power-law
data is processed through a random features layer. Finally, [17] investigate a
toy model of scalar integer data in the context of classification, and
ascertain the corresponding scaling law. Relating in classification settings
the rate of decay of the kernel spectrum to the test error, like [6] for
regression, is still an open question.

#### Source and capacity conditions —

The source and capacity conditions are standard regularity assumptions in the
theoretical study of kernel methods, as they allow to subsume a large class of
learning setups, c.f. [18, 12, 8, 7, 15, 13].

#### Kernel ridge regression —

The error rates for kernel ridge regression have been extensively and
rigorously characterized in terms of the source/capacity coefficients in the
seminal work of [8, 7], with a sizeable body of work being subsequently
devoted thereto [19, 9, 10, 11, 12, 13, 14]. In particular, in [15] it was
shown that rates derived under worst-case assumptions [9, 10, 8, 7, 20] are
identical to the typical rates computed under the standard Gaussian design
[21, 22, 23] assumption. Crucially, it was observed that many real data-sets
satisfy the source/capacity conditions, and display learning rates in very
good agreement to the theoretical values [15].

#### Worst-case analyses for SVM —

The worst-case bounds for Support Vector Machines (SVM) classification  – see
e.g. [24, 25] for general introductions thereto– are known from the seminal
works of [24, 26, 27]. However, it is not known how tightly the corresponding
rates hold for a given realistic data distributions,  not even for synthetic
Gaussian data. We show that, contrary to the case of ridge regression, for
classification the worst case bounds are not tight for Gaussian data. This
effectively hinders the ability to predict and understand the error rates for
relevant classes of data-sets, and in particular the class of data described
by source/capacity conditions, which as mentioned above includes many real
data-sets [15]. The key goal of this work is to fill this gap  by leveraging
the recent work on learning curves for the Gaussian covariate model [28]
specified to data satisfying the capacity and source conditions.

### Main contribution

In this work, we investigate the decay rate of the misclassification
(generalization) error for  noiseless kernel classification, under the
Gaussian design and source/capacity regularity assumptions with capacity
coefficient $\alpha$ and source coefficient $r$. Building on the analytic
framework of [28], we consider the two most widely used classifiers: margin-
maximizing Support Vector Machines (SVMs) and ridge classifiers. We derive in
Section III the error rate (describing the decay of the prediction error with
the number of samples) for margin-maximizing SVM :

$\displaystyle\epsilon_{g}^{\rm SVM}\sim
n^{-\frac{\alpha\mathrm{min}(r,\frac{1}{2})}{1+\alpha\mathrm{min}(r,\frac{1}{2})}}.$

As a consequence, we conclude that the worst-case rates [26, 24, 27] are
indeed loose and fail to describe this class of data.  This fact alone is not
at all surprising. However, it becomes remarkable in the light of the fact
that for ridge regression the worst case bounds and the typical case rates do
agree [15].

We contrast the SVM rate with the rate for optimally regularized ridge
classification, which we establish in Section IV to be

$\displaystyle\epsilon_{g}^{\rm ridge}\sim
n^{-\frac{\alpha\mathrm{min}(r,1)}{1+2\alpha\mathrm{min}(r,1)}}.$

We argue in the light of these findings that the SVM always displays faster
rates than the ridge classifier for the classification task considered.

Finally, we observe that some real data-sets fall in the same universality
class as the considered setting, in the sense that, as illustrated in Section
V, their error rates are in very good agreement with the ones above. This work
is thus a key step for theoretically predicting the error rates of kernel
classification for a broad range of real data-sets.

##  II Setting

###  II.1 Kernel classification

Consider a data-set $\mathcal{D}=\\{(x^{\mu},y^{\mu})\\}_{\mu=1}^{n}$ with $n$
independent samples from a probability measure $\nu$ on
$\mathcal{X}\times\\{-1,+1\\}$, with $\mathcal{X}\subset\mathbb{R}^{d}$. We
will assume that the labels can be expressed as

$y^{\mu}=\mathrm{sign}{}(f^{\star}(x^{\mu}))$ (1)

for some  non-stochastic target function
$f^{\star}:\mathcal{X}\rightarrow\mathbb{R}$.  Note that the noiseless setting
considered here is out of the validity domain of many worst case analyses,
whose bounds become void without noise [27], whereas a number of real learning
settings are well described by a noiseless setup, see section V. Learning to
classify $\mathcal{D}$ in the direct space $\mathcal{X}$ for a linear
$f^{\star}$ has been the object of extensive studies. In the present work, we
focus on the case where $f^{\star}$ more generically belongs to the space of
square-integrable functions $L^{2}(\mathcal{X})$. To classify $\mathcal{D}$, a
natural method is then to perform kernel classification in a $p$\- dimensional
Reproducing Kernel Hilbert Space (RKHS) $\mathcal{H}$ associated to a kernel
$K$, by minimizing the regularized empirical risk:

$\hat{\mathcal{R}}_{n}(f)=\frac{1}{n}\sum\limits_{\mu=1}^{n}\ell(f(x^{\mu}),y^{\mu})+\lambda||f||^{2}_{\mathcal{H}}.$
(2)

The function $\ell(\cdot)$ is a loss function and $\lambda$ is the strength of
the $\ell_{2}$ regularization term. In this paper we shall more specifically
consider the losses $\ell(z,y)=\mathrm{max}(0,1-yz)$ (hinge classification)
and $\ell(z,y)=(y-z)^{2}$ (ridge classification), and the case of an infinite
dimensional RKHS ($p=\infty$). The risk (2) admits a dual rewriting in terms
of a standard parametric risk. To see this, diagonalize $K$ in an orthogonal
basis of kernel features $\\{\psi_{k}(\cdot)\\}_{k=1}^{p}$ of
$L^{2}(\mathcal{X})$, with corresponding eigenvalues
$\\{\omega_{k}\\}_{k=1}^{p}$:

$\int_{\mathcal{X}}\nu(\text{d}{x}^{\prime})K(x,x^{\prime})\psi_{k}(x^{\prime})=\omega_{k}\psi_{k}(x).$
(3)

It is convenient to normalize the eigenfunctions to

$\int_{\mathcal{X}}\nu(\text{d}{x})\psi_{k}(x)^{2}=\omega_{k},$ (4)

so that the kernel $K$ can be rewritten in simple scalar product form
$K(x,x^{\prime})=\psi(x)^{\top}\psi(x^{\prime})$, where we named $\psi(x)$ the
$p$-dimensional vector with components $\\{\psi_{k}(x)\\}_{k=1}^{p}$.

Furthermore, note that the covariance $\Sigma$ of the data in feature space
with this choice of feature map is simply diagonal

$\Sigma=\mathbb{E}_{x\sim\nu}(\psi(x)\psi(x)^{\top})=\mathrm{diag}(\omega_{1},\cdots,\omega_{p}).$
(5)

Any function $f\in\mathcal{H}$ can then be expressed as
$f(\cdot)=w^{\top}\psi(\cdot)$ for a vector $w$ with square summable
components. Using this parametrization, the risk (2) can be rewritten as

$\hat{\mathcal{R}}_{n}(w)=\frac{1}{n}\sum\limits_{\mu=1}^{n}\ell(w^{\top}\psi(x^{\mu}),y^{\mu})+\lambda
w^{\top}w.$ (6)

Throughout this manuscript we will refer to the components of the target
function in the features basis as the teacher $\theta^{\star}$, so that

$f^{\star}(\cdot)=\theta^{\star\top}\psi(\cdot).$

Note that any $f^{\star}\in L^{2}(\mathcal{X})$ can be formally written in
this form with a certain $\theta^{\star}$ (allowing for non square-summable
components if $f^{\star}\in L^{2}(\mathcal{X})\setminus\mathcal{H}$).
Similarly, the minimizer $\hat{w}$ of the parametric risk (6) is related to
the argmin $\hat{f}$ of (2) by $\hat{f}(\cdot)=\hat{w}^{\top}\psi(\cdot)$, and
will be referred to as the estimator in the following. We make two further
assumptions : first, we work under the Gaussian design, and assume the
features $\psi(x)$ to follow a Gaussian distribution with covariance $\Sigma$,
i.e. $\psi(x)\sim\mathcal{N}(0,\Sigma)$. Note that this assumption might
appear constraining  , as the distribution of the data in feature space
strongly depends on its distribution in the original space, and the feature
map associated to the kernel. In fact, for a large class of data distributions
and standard kernels, the Gaussian design assumption does not hold. However,
rates derived under Gaussian design can hold more broadly. For instance, the
rates established by [15] under Gaussian design were later proven by [29]
under weaker conditions on the features. We will moreover discuss in Section V
several settings in which our theoretical rates are in good agreement with
rates observed for real data.

Second, following [15], we assume that the regularization strength $\lambda$
decays as a power-law of the number of samples $n$ with an exponent $\ell$:
$\lambda=n^{-\ell}$. Note that this form of regularization is natural, since
the need for regularizing is lesser for larger training sets. Furthermore,
this allows to investigate the classical question of the asymptotically
optimal regularization [8, 7, 15], i.e. the decay $\ell$ of the regularization
yielding fastest decrease of the prediction error.

###  II.2 Source and capacity conditions

Under the above assumptions of Gaussian design with features covariance
$\Sigma$ and existence of a teacher $\theta^{\star}$ that generates the labels
using eq. (1) we can now study the error rates. In statistical learning theory
one often uses the source and capacity conditions, which assume the existence
of two parameters $\alpha>1,r\geq 0$ (hereafter referred to as the capacity
coefficient and the source coefficient respectively) so that

$\displaystyle\mathrm{tr}\Sigma^{\frac{1}{\alpha}}<\infty,$
$\displaystyle\theta^{\star\top}\Sigma^{1-2r}\theta^{\star}<\infty.$ (7)

As in [21, 30, 31, 13, 15], we will consider the particular case where both
the spectrum of $\Sigma$ and the teacher components $\theta^{\star}_{k}$ have
exactly a power-law form satisfying the limiting source/capacity conditions
(7):

$\displaystyle\omega_{k}=k^{-\alpha}\,,$
$\displaystyle\theta^{\star}_{k}=k^{-\frac{1+\alpha(2r-1)}{2}}\,.$ (8)

The power-law forms (8) have been empirically found in [15] in the context of
kernel regression to be a reasonable approximation for a number of real data-
sets including MNIST [32] and Fashion MNIST [33] and a number of standard
kernels such as polynomial kernels and radial basis functions. Similar
observations were also made in the present work and are discussed in F and
section V.

The capacity parameter $\alpha$ and source parameter $r$ capture the
complexity of the data-set  in feature space – i.e. after the data is
transformed through the kernel feature map into
$\\{\psi(x^{\mu}),y^{\mu}\\}_{\mu=1}^{n}$. A large $\alpha$, for example,
signals that the spectrum of the data covariance $\Sigma$ displays a fast
decay, implying that the data effectively lies along a small number of
directions, and has a low effective dimension. Conversely, a small capacity
$\alpha$ means that the data is effectively large dimensional, and therefore a
priori harder to learn. Similarly, a large $r$ signals a good alignment of the
teacher $\theta^{\star}$ with the main directions of the data, and a priori an
easier learning task. In terms of the target function $f^{\star}$, larger $r$
correspond to smoother $f^{\star}$. Note that $r>\nicefrac{{1}}{{2}}$ implies
that $f^{\star}\in\mathcal{H}$, while $r\leq\nicefrac{{1}}{{2}}$ implies
$f^{\star}\in L^{2}(\mathcal{X})\setminus\mathcal{H}$. Finally, note that
while [18] suggested an alternative definition for the source and capacity
coefficients in the case of non-square loss functions, their redefinition is
not directly applicable for the hinge loss.

###  II.3 Misclassification error

The performance of learning the data-set $\mathcal{D}$ using kernel
classification (6) is quantified by the misclassification (generalization)
error

$\epsilon_{g}=\frac{1}{2}-\frac{1}{2}\mathbb{E}_{\mathcal{D}}\mathbb{E}_{x,y\sim\nu}\left(y~{}\mathrm{sign}{}(\hat{w}^{\top}\psi(x))\right),$
(9)

where $\hat{w}$ is the minimizer of the risk (6). The error (9) corresponds to
the probability for the predicted label
$\mathrm{sign}{}(\hat{w}^{\top}\psi(x))$ of a test sample $x$ to be incorrect.
The rate at which the error (9) decays with the number of samples $n$ in
$\mathcal{D}$ depends on the complexity of the data-set, as captured by the
source and capacity coefficients $\alpha,r$ eq. (8). To compute this rate, we
build upon the work of [28] who, following a long body of work in the
statistical physics literature [34, 35, 36, 37, 31, 38], provided and proved a
mathematically rigorous closed form asymptotic characterization of the
misclassification error as

$\displaystyle\epsilon_{g}=\frac{1}{\pi}\mathrm{arccos}\left(\sqrt{\eta}\right),$
$\displaystyle\eta=\frac{m^{2}}{\rho q},$ (10)

where $\rho$ is the squared $L^{2}(\mathcal{X})$ norm of the target function
$f^{\star}$, i.e.
$\rho=\int_{\mathcal{X}}\nu(\text{d}{x})f^{\star}(x)^{2}=\theta^{\star\top}\Sigma\theta^{\star},$
and $m,q$ are the solution of a set of self-consistent equations, which are
later detailed and analyzed in Section III for margin-maximizing SVMs and
section IV for ridge classifiers. The order parameters $m,q$ are known as the
magnetization and the self-overlap in statistical physics and respectively
correspond to the target/estimator and estimator/estimator
$L^{2}(\mathcal{X})$ correlations:

$\displaystyle
m=\mathbb{E}_{\mathcal{D}}\int_{\mathcal{X}}\nu(\text{d}{x})f^{\star}(x)\hat{f}(x)=\mathbb{E}_{\mathcal{D}}\left(\hat{w}^{\top}\Sigma\theta^{\star}\right),$
$\displaystyle
q=\mathbb{E}_{\mathcal{D}}\int_{\mathcal{X}}\nu(\text{d}{x})\hat{f}(x)^{2}=\mathbb{E}_{\mathcal{D}}\left(\hat{w}^{\top}\Sigma\hat{w}\right).$
(11)

It follows from these interpretations that $\eta$ has to be thought of as the
cosine-similarity between the teacher $\theta^{\star}$ and the estimator
$\hat{w}$, with perfect alignment ($\eta=1$) resulting in minimal error
$\epsilon_{g}=0$ from (9).

Note that while this characterization has formally been proven in [28] in the
asymptotic proportional
$n,p\rightarrow\infty,\nicefrac{{n}}{{p}}=\mathcal{O}(1)$ limit, we are
presently using it in the $n\ll p=\infty$ limit, thereby effectively working
at $\nicefrac{{n}}{{p}}=0^{+}$. The non-asymptotic rate guarantees of [28] are
nevertheless encouraging in this respect, although a finer control of the
limit would be warranted to put the present analysis on fully rigorous
grounds. Further, [15] also build on [28] in the $\nicefrac{{n}}{{p}}=0^{+}$
limit, and display solid numerics-backed results, later rigorously proven by
[29]. We thus conjecture that this limit can be taken as well safely in our
case.  Finally, we mention that a recent line of works [39, 40, 41, 42] has
explored the connections between kernel regression and Bayesian learning for
networks in the $\nicefrac{{n}}{{p}}=\mathcal{O}(1)$ limit, where $p$ is in
this case the width of the network. While the high-dimensional limit is indeed
related to the one originally discussed in [28], which we relax here to
$\nicefrac{{n}}{{p}}=0^{+}$, the main object of [39, 40, 41] was not to study
kernel regression per se, but to show how observables in Bayesian regression
could be expressed in terms of well-chosen kernels. In the present work, we
focus on analyzing kernel classification in the $\nicefrac{{n}}{{p}}=0^{+}$
regime.

##  III Max-margin classification

Figure 1: Misclassification error $\epsilon_{g}$ for max-margin classification
on synthetic Gaussian features, as specified in (8), for different
source/capacity coefficients $\alpha,r$. In blue, the solution of the closed
set of eqs. (13) used in the characterization (9) for the misclassification
error, using the g3m package [28]. The dimension $p$ was cut-off at $10^{4}$.
Red dots corresponds to simulations using the scikit-learn SVC [43] package
run for vanishing regularization $\lambda=10^{-4}$ and averaged over $40$
instances, for $p=10^{4}$. The green dashed line indicates the power-law rate
(15) derived in this work.  The light blue dotted line indicates the classical
worst-case
$\min\left(\nicefrac{{1}}{{2}},\nicefrac{{\alpha}}{{(3+\alpha)}}\right)$ rate
for SVM classification (Theorem $2.3$ in [24]) in the cases where the theorem
readily applies ($r>\nicefrac{{1}}{{2}}$) (see also G). The code used for the
simulations is available here.

###  III.1 Self-consistent equations

In this section we study regression using Support Vector Machines. The risk
(6) then reads for the hinge loss

$\hat{\mathcal{R}}_{n}(w)=\frac{1}{n}\sum\limits_{\mu=1}^{n}\mathrm{max}\left(0,1-y^{\mu}w^{\top}\psi(x^{\mu})\right)+\lambda
w^{\top}w.$ (12)

In the following, we shall focus more specifically on the max-margin limit
with $\lambda=0^{+}$. We show in B that zero regularization is indeed
asymptotically optimal for the data following eq. (8) when the target function
is characterized by a source $r\leq\nicefrac{{1}}{{2}}$, i.e. $f^{\star}\in
L^{2}(\mathcal{X})\setminus\mathcal{H}$. We heuristically expect margin
maximization to be a fortiori optimal also for easier and smoother teachers
$f^{\star}\in\mathcal{H}$. For the risk (12) at $\lambda=0^{+}$, the self-
consistent equations defining $m,q$ in (11) read (see A)

$\displaystyle\begin{cases}\rho=&\sum\limits_{k=1}^{\infty}\theta_{k}^{\star
2}\omega_{k},\\\
m=&\hat{r}_{1}\frac{n}{z}\sum\limits_{k=1}^{\infty}\frac{\omega_{k}^{2}\theta_{k}^{\star
2}}{1+\frac{n}{z}\omega_{k}},\\\
q=&\hat{r}_{1}^{2}\frac{n^{2}}{z^{2}}\sum\limits_{k=1}^{\infty}\frac{\theta_{k}^{\star
2}\omega_{k}^{3}}{(1+\frac{n}{z}\omega_{k})^{2}}\\\
&+\hat{r}_{2}\frac{n}{z^{2}}\sum\limits_{k=1}^{\infty}\frac{\omega_{k}^{2}}{(1+\frac{n}{z}\omega_{k})^{2}}\end{cases},$
$\displaystyle\begin{cases}\hat{r}_{1}=&\frac{1}{2\pi\sqrt{\rho}}\frac{\left(\sqrt{2\pi}(1+\mathrm{erf}(\frac{1}{\sqrt{2q(1-\eta)}}))+2e^{-\frac{1}{2q(1-\eta)}}\sqrt{q(1-\eta)}\right)}{\int\limits_{-\infty}^{\frac{1}{\sqrt{q}}}dx\frac{e^{-\frac{1}{2}x^{2}}}{\sqrt{2\pi}}\left[1+\mathrm{erf}(\sqrt{\frac{\eta}{2(1-\eta)}}x)\right]},\\\
\hat{r}_{2}=&\frac{\int\limits_{-\infty}^{\frac{1}{\sqrt{q}}}dx\frac{e^{-\frac{1}{2}x^{2}}}{\sqrt{2\pi}}\left[1+\mathrm{erf}(\sqrt{\frac{\eta}{2(1-\eta)}}x)\right](1-\sqrt{q}x)^{2}}{\left(\int\limits_{-\infty}^{\frac{1}{\sqrt{q}}}dx\frac{e^{-\frac{1}{2}x^{2}}}{\sqrt{2\pi}}\left[1+\mathrm{erf}(\sqrt{\frac{\eta}{2(1-\eta)}}x)\right]\right)^{2}},\\\
z=&\frac{\frac{z}{n}\sum\limits_{k=1}^{\infty}\frac{\omega_{k}}{\frac{z}{n}+\omega_{k}}}{\int\limits_{-\infty}^{\frac{1}{\sqrt{q}}}dx\frac{e^{-\frac{1}{2}x^{2}}}{\sqrt{2\pi}}\left[1+\mathrm{erf}(\sqrt{\frac{\eta}{2(1-\eta)}}x)\right]}.\end{cases}$
(13)

Here $\hat{r}_{1}$ should be thought of as the ratio between the norms of the
estimator $\hat{w}$ and the teacher $\theta^{\star}$, while $z$ can be loosely
interpreted as an effective regularization. A detailed derivation of these
equations can be found in A.

###  III.2 Decay rates for max-margin

From the investigation of the eqs. (13), as detailed in A, the following
scalings are found to hold between the order parameters:

$m\sim\sqrt{q}\sim\hat{r}_{1}\sim
n\left(\frac{z}{n}\right)^{\frac{1}{\alpha}}\sim
n^{\frac{\alpha\mathrm{min}(r,\frac{1}{2})}{1+\alpha\mathrm{min}(r,\frac{1}{2})}}.$
(14)

Note that the mutual scaling between $m,~{}q$ also follows intuitively from
the interpretation of these order parameters –  as the overlap of $\hat{w}$
with the ground truth and itself respectively – see the discussion around eqs.
(11) and (13). Since the width of the margin is generically expected to shrink
with the number of samples (as more training data are likely to be sampled
close to the separating hyperplane), the increase of the norm of $\hat{w}$ (as
captured by $q,\hat{r}_{1}$) with $n$ is also intuitive. Finally, an analysis
of the subleading corrections to $m$ and $q$, detailed in A, leads to

$\epsilon_{g}\sim
n^{-\frac{\alpha\mathrm{min}(r,\frac{1}{2})}{1+\alpha\mathrm{min}(r,\frac{1}{2})}}.$
(15)

The error rate (15) stands in very good agreement with numerical simulations
on artificial Gaussian features generated using the model specification (8),
see Fig. 1. Two observations can further be made on the decay rate (15).
First, the rate is as expected an increasing function of $\alpha$ (low-
dimensionality of the features) and $r$ (smoothness of the target
$f^{\star}$). Second, for a source $r>\nicefrac{{1}}{{2}}$ (corresponding to a
target $f^{\star}\in\mathcal{H}$), the rate saturates, suggesting that all
functions in $\mathcal{H}$ are all equally easy to classify, while for rougher
target $f^{\star}\in L^{2}(\mathcal{X})\setminus\mathcal{H}$ the specific
roughness of the target function, as captured by its source coefficient $r$,
matters and conditions the rate of decay of the error.

Finally, we briefly discuss for completeness in E the more general case where
the label distribution (1) includes data noise, and show that the rates
display a crossover from the noiseless value (15) to a noisy value, much like
what was reported for kernel ridge regression [15].

###  III.3 Comparison to classical rates

To the best of the authors’ knowledge, there currently exists little work
addressing the error rates for datasets satisfying source and capacity
conditions (7). The closest result is the worst-case bound of [24] for SVM
classification, which can be adapted to the present setting provided
$f^{\star}\in\mathcal{H}$ ($r>\nicefrac{{1}}{{2}}$). The derivation is
detailed in G and results in an upper bound of
$\min\left(\nicefrac{{1}}{{2}},\nicefrac{{\alpha}}{{(3+\alpha)}}\right)$ for
the error rate for max-margin classification, which is always slower than
(15). This rate [24] is plotted for comparison in Fig. 1 against numerical
simulations and is visibly off, failing to capture the learning curves. It is
to be expected that the worst case rates will be loose when compared to rate
that assume a specific data distribution. What makes our result interesting is
the comparison with the more commonly studied ridge regression where, as
discussed already in the introduction, the worst case rates actually match
those derived for Gaussian data, see [15].

Importantly, the rates from [24] only hold for capacity
$r>\nicefrac{{1}}{{2}}$, while real datasets are typically characterized by
sources $r<\nicefrac{{1}}{{2}}$ (see for instance Fig. 4). The present work
therefore fills an important gap in the literature in providing rates (15)
which accurately capture the learning curves of datasets satisfying source and
capacity conditions. Further discussions of [24], along with [26, 27, 44] for
completeness, are provided in G. Also note that while [45] report
$\nicefrac{{\alpha}}{{(1+\alpha)}}$ rates under Gaussianity assumptions, they
rely on very stringent assumptions which are too strong and unfulfilled in our
setting.

##  IV Ridge classification

###  IV.1 Self-consistent equations

Another standard classification method is the ridge classifier, which
corresponds to minimizing

$\hat{\mathcal{R}}_{n}(w)=\frac{1}{n}\sum\limits_{\mu=1}^{n}\left(y^{\mu}-w^{\top}\psi(x^{\mu})\right)^{2}+\lambda
w^{\top}w.$ (16)

As previously discussed in section II, we consider a decaying regularization
$\lambda=n^{-\ell}$. The self-consistent equations characterizing the
quantities $(q,m)$, read for the ridge risk (16)

$\displaystyle\begin{cases}&\rho=\sum\limits_{k=1}^{\infty}\theta_{k}^{\star
2}\omega_{k},\\\
&m=\sqrt{\frac{2}{\pi\rho}}\frac{n}{z}\sum\limits_{k=1}^{\infty}\frac{\omega_{k}^{2}\theta_{k}^{\star
2}}{1+\frac{n}{z}\omega_{k}},\\\
&q=\frac{n^{2}}{z^{2}}\sum\limits_{k=1}^{\infty}\frac{\frac{2}{\pi\rho}\theta_{k}^{\star
2}\omega_{k}^{3}+\frac{1+q-2m\sqrt{\frac{2}{\pi\rho}}}{n}\omega_{k}^{2}}{\left(1+\frac{n}{z}\omega_{k}\right)^{2}},\\\
&z=n\lambda+\frac{z}{n}\sum\limits_{k=1}^{\infty}\frac{\lambda_{k}}{\lambda_{k}+\frac{z}{n}}.\end{cases}$
(17)

Further details on the derivation of (17) from [28] are provided in C. Like
(13), eqs. (17) have been formally proven in the proportional
$n,p\rightarrow\infty,\,n/p=\mathcal{O}(1)$ limit in [28], but are expected to
hold also in the present $n\ll p=\infty$ setting [15, 29]. Note that comparing
to (13), eqs. (17) correspond to a constant student/teacher norm ratio
$\hat{r}_{1}=\nicefrac{{2}}{{(\pi\rho)}}$ and to a simple
$\hat{r}_{2}=1+q-2m\sqrt{\nicefrac{{2}}{{(\pi\rho)}}}$. $\hat{r}_{2}$ moreover
admits a very intuitive interpretation as the prediction mean squared error
(MSE) between the true label
$y=\mathrm{sign}{}({\theta^{\star}}^{\top}\psi(x))$ and the pre-activation
linear predictor $\hat{w}^{\top}\psi(x)$, i.e.
$\hat{r}_{2}=\mathbb{E}_{\psi(x)}\left(\mathrm{sign}{}\left({\theta^{\star}}^{\top}\psi(x)\right)-\hat{w}^{\top}\psi(x)\right)^{2}.$

###  IV.2 Decay rates for ridge classification

Figure 2: Misclassification error $\epsilon_{g}$ for ridge classification on
synthetic Gaussian features, as specified in (8), for different
source/capacity coefficients $\alpha,r$, in the effectively regularized regime
$\ell\leq\alpha$ (top) and unregularized regime $\ell>\alpha$ (bottom). In
blue, the solution of the eqs. (13) used in the characterization (9) for the
misclassification error, using the g3m package [28]. The dimension $p$ was
cut-off at $10^{4}$. Red dots corresponds to simulations averaged over $40$
instances, for $p=10^{4}$. The green dashed lines indicate the power-laws (18)
(top) and (19) (bottom) derived in this work. The slight increase of the error
for larger $n$ in the unregularized regime (bottom) is due to finite size
effects of the simulations ran at $p=10^{4}<\infty$. Physically, it
corresponds to the onset of the ascent preceding the second descent that is
present for finite $p$, see D for further discussion. The code used for the
simulations is available here.

Similarly to [31, 15], an analysis of the eqs. (17) (see C) reveals that,
depending on how the rate of decay $\ell$ of the regularization compares to
the capacity $\alpha$, two regimes (called effectively regularized and
effectively un-regularized in [15] in the context of ridge regression) can be
found:

#### Effectively regularized regime –

$\ell\leq\alpha$. In this regime, an analysis of the corrections to the self-
overlap $q$ and magnetization $m$, presented in C, shows that the
misclassification error scales like

$\epsilon_{g}\sim
n^{-\frac{1}{2}\mathrm{min}\left(2\ell\mathrm{min}(r,1),\frac{\alpha-\ell}{\alpha}\right)}.$
(18)

The rate (18) compares very well to numerical simulations, see Fig. 2. Note
that the saturation for ridge happens for $r=1$, rather than
$r=\nicefrac{{1}}{{2}}$ as for max-margin classification (see discussion in
section III): very smooth targets $f^{\star}$ characterized by a source $r\geq
1$ are all equally easily classified by ridge. For rougher teachers
$f^{\star}$ characterized by $r\leq 1$ however, the rate of decay of the error
(18) depends on the specific roughness of the target, even if, in contrast to
max-margin, the latter belongs to $\mathcal{H}$ ($r>\nicefrac{{1}}{{2}}$). Two
important observations should further be made on the rates (18):

  * •

If the regularization remains small (fast decay
$\alpha>\ell>\nicefrac{{\alpha}}{{(1+2\alpha\mathrm{min}(r,1))}}$), the decay
(18) is determined only by the data capacity $\alpha$, while the source $r$
plays no role. As a matter of fact, with insufficient regularization, the
limiting factor to the learning is the tendency to overfit, which depends on
the effective dimension of the data as captured by the capacity $\alpha$.

  * •

For larger regularizations (slow decays
$\ell<\nicefrac{{\alpha}}{{(1+2\alpha\mathrm{min}(r,1))}}$), the limiting
factor becomes the complexity of the teacher $\theta^{\star}$, as captured by
the source $r$.

#### Effectively un-regularized regime –

$\ell>\alpha$. As derived in C, the error plateaus and stays of order $1$:

$\epsilon_{g}=\mathcal{O}(1).$ (19)

This plateau is further elaborated upon in D, and is visible in numerical
experiments, see Fig. 2. It corresponds to the first plateau in a double
descent curve, with the second descent never happening since $p=\infty$.
Intuitively, this phenomenon is attributable to the ridge classifier
overfitting the labels using the small-variance directions of the data (8).

Interestingly, all the rates (19) and (18) correspond exactly (up to a factor
$\nicefrac{{1}}{{2}}$) to those reported in [15] for the MSE of ridge
regression, where they are respectively called the red, blue and orange
exponents. Notably, the plateau (19) at low regularizations and the
$\nicefrac{{(\alpha-\ell)}}{{\alpha}}$ exponent in (18) only appeared in [15]
for noisy cases in which the labels are corrupted by an additive noise. The
fact that they hold in the present noiseless study very temptingly suggests
that model mis-specification (trying to interpolate binary labels using a
linear model) effectively plays the role of a large noise.

###  IV.3 Optimal rates

Figure 3: (red) Misclassification error $\epsilon_{g}$ for ridge
classification on synthetic Gaussian features, as specified in (8), for
different source/capacity coefficients $\alpha,r$, for optimal regularization
$\lambda^{\star}$. The dimension $p$ was cut-off at $10^{4}$ and the
regularization $\lambda$ numerically tuned to minimize the error
$\epsilon_{g}$ for avery $n$. Red dots correspond to simulations averaged over
$40$ instances, for $p=10^{4}$. Optimization over $\lambda$ was performed
using cross validation, with the help of the python scikit-learn GridSearchCV
package. The red dashed line represents the power-law (21). In blue, the
learning curves for max-margin for the same data-set are plotted for
reference, along the corresponding power law (15) (blue) and the loose
classical
$\min\left(\nicefrac{{1}}{{2}},\nicefrac{{\alpha}}{{(3+\alpha)}}\right)$ rate
[24] (light blue), see Section III. The code used for the simulations is
available here.

#### Optimally regularized ridge classification

In practice, the strength of the regularization $\lambda$ is a tunable
parameter. A natural question to ask is then the one of the asymptotically
optimal regularization, that is the regularization decay rate $\ell^{\star}$
leading to fastest decay rates for the misclassification error. From the
expressions of (18) (which hold provided $\ell<\alpha$) and (19) (which holds
provided $\ell>\alpha$), the value of $\ell$ maximizing the error rate is
found to be

$\ell^{\star}=\frac{\alpha}{1+2\alpha\mathrm{min}(r,1)},$ (20)

and the corresponding error rate for
$\epsilon_{g}^{\star}=\epsilon_{g}(\lambda^{\star}=n^{-\ell^{\star}})$ is

$\epsilon_{g}^{\star}\sim
n^{-\frac{\alpha\mathrm{min}(r,1)}{1+2\alpha\mathrm{min}(r,1)}},$ (21)

see the red dashed lines in Fig. 3. Coincidentally, the optimal rate (21) is
up to a factor $\nicefrac{{1}}{{2}}$ identical to the classical optimal rate
known for the rather distinct problem of the MSE of kernel ridge regression on
noisy data [8, 7]. Like the max-margin exponent (15), the optimal error rate
for ridge (21) is an increasing function of both the capacity $\alpha$ and the
source $r$, i.e. of the easiness of the learning task. Note that in contrast
to max-margin classification which is insensitive to the specifics of the
target function $f^{\star}$, provided it is in $\mathcal{H}$, ridge is
sensitive to the source (smoothness) $r$ of $f^{\star}$ up to $r=1$.

#### Comparison to max-margin

A comparison of the max-margin rate
$a_{\mathrm{SVM}}=\nicefrac{{\alpha\mathrm{min}(r,\frac{1}{2})}}{{(1+\alpha\mathrm{min}(r,\frac{1}{2}))}}$
(15) and the optimal ridge exponent
$a_{r}=\nicefrac{{\alpha\mathrm{min}(r,1)}}{{(1+2\alpha\mathrm{min}(r,1))}}$
(21) reveals that for any $\alpha>1,r\geq 0$, $a_{\mathrm{SVM}}-a_{r}>0.$ In
other words, the margin-maximizing SVM displays faster rates than the ridge
classifier for the class of data studied (8), see Fig. 3.

We finally briefly comment on support vector proliferation. [46, 47, 48]
showed that in some settings almost every training sample in $\mathcal{D}$
becomes a support vector for the SVM. In such settings, the estimators
$\hat{w}$ (and hence the error $\epsilon_{g}$) consequently coincide for the
ridge classifier and the margin-maximizing SVM. In the present setting
however, the result $a_{\mathrm{SVM}}-a_{r}>0$ establishes that for features
with a power-law decaying spectrum (8), there is no such support vector
proliferation. Note that this result does not follow immediately from Theorem
$3$ in [48]. In fact, the spiked covariance (8), with only a small number of
important (large variance) directions and a tail of unimportant (low-variance)
directions does effectively not offer enough overparametrization [20, 47] for
support vector proliferation, and the support consists only of the subset of
the training set with weakest alignment with the spike.

##  V Remarks for real data-sets

Figure 4: Dots: Misclassification error $\epsilon_{g}$ of kernel
classification on CIFAR 10 with a polynomial kernel (top left) and an RBF
kernel (top right), on Fashion MNIST with an RBF kernel (bottom left), on
MNIST with an RBF kernel (bottom right), for max-margin SVM (blue) and
optimally regularized ridge classification (red), using respectively the
python scikit-learn SVC and KernelRidge packages. Dashed lines: Theoretical
decay rates for the error $\epsilon_{g}$ (15) (blue) (21) (red), computed from
empirically estimated capacity $\alpha$ and source $r$ coefficients (see
section (V) and F for details).  The measure coefficients are summarized in
Table 1. The code used for the simulations is available here.

The source and capacity condition (8) provide a simple framework to study a
large class of structured data-sets. While idealized, we observe, similarly to
[15], that many real data-sets seem to fall under this category of data-sets,
and hence display learning curves which are to a good degree described by the
rates (15) for SVM and (21) for ridge classification.  We present here three
examples of such data-sets : a data-set of $10^{4}$ randomly sampled CIFAR 10
[49] images of animals (labelled $+1$) and means of transport (labelled $-1$),
a data-set of $14000$ FashionMNIST [33] images of t-shirts (labelled $+1$) and
coats (labelled $-1$), and a data-set of $14702$ MNIST [32] images of $8s$
(labelled $+1$) and $1s$ (labelled $-1$). On the one hand, the learning curves
for max-margin classification and optimally regularized ridge classification
were obtained using the python scikit-learn SVC, KernelRidge packages. On the
other hand, the spectrum $\\{\omega{}_{k}\\}_{k}$ of the data covariance
$\Sigma$ in feature space was computed, and a teacher $\theta^{\star}$
providing perfect classification of the data-set was fitted using margin-
maximizing SVM. Then, the capacity and source coefficients $\alpha,\,r$ (8)
were estimated for the data-set by fitting $\\{\omega{}_{k}\\}_{k}$ and
$\\{\theta^{\star}_{k}\\}_{k}$ by power laws, and the theoretical rates (15)
and (21) computed therefrom. More details on this method, adapted from [31,
30], are provided in F. The results of the simulations are presented in Figure
4 and compared to the theoretical rates (15)(21) computed from the empirically
evaluated source and capacity coefficients for a Radial Basis Function (RBF)
kernel and a polynomial kernel of degree $5$, with overall very good
agreement.  We do not compare here with the worst case bounds because the
observed values of $r<1/2$ in which case we remind the known results do not
apply.

Dataset |  Kernel |  $\alpha$ |  $r$ |  $a_{\mathrm{SVM}}$ |  $a_{r}$
---|---|---|---|---|---
CIFAR 10 |  polynomial |  1.51 |  0.07 |  0.095 |  0.086
CIFAR 10 |  RBF |  1.005 |  0.07 |  0.067 |  0.063
Fashion MNIST |  RBF |  1.72 |  0.23 |  0.28 |  0.22
MNIST |  RBF |  1.65 |  0.39 |  0.39 |  0.28
Table 1: Values of the source and capacity coefficients (7) as estimated from
the data sets, and the corresponding theoretical error rates for SVM (15) and
ridge (21). The details on the estimation procedure can be found in Appendix
F.

##  VI Conclusion

We compute the generalization error rates as a function of the source and
capacity coefficients for two standard kernel classification methods, margin-
maximizing SVM and ridge classification, and show that SVM classification
consistently displays faster rates. Our results establish that known worst-
case upper bound rates for SVM classification fail to tightly capture the
rates of the class of data described by source/capacity conditions. We
illustrate empirically that a number of real data-sets fall under this class,
and display error rates which are to a very good degree described by the ones
derived in this work.

###### Acknowledgements.

We thank Loucas Pillaud-Vivien, Alessandro Rudi, Vittorio Erba and Mauro
Pastore for useful discussion. We acknowledge funding from the ERC under the
European Union’s Horizon 2020 Research and Innovation Programme Grant
Agreement 714608-SMiLe.

## References

  * [1] Joel Hestness, Sharan Narang, Newsha Ardalani, Gregory Diamos, Heewoo Jun, Hassan Kianinejad, Md Mostofa Ali Patwary, Yang Yang, and Yanqi Zhou.  Deep learning scaling is predictable, empirically.  arXiv preprint arXiv:1712.00409, 2017.
  * [2] Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei.  Scaling laws for neural language models.  arXiv preprint arXiv:2001.08361, 2020.
  * [3] Jonathan S Rosenfeld, Amir Rosenfeld, Yonatan Belinkov, and Nir Shavit.  A constructive prediction of the generalization error across scales.  arXiv preprint arXiv:1909.12673, 2019.
  * [4] Tom Henighan, Jared Kaplan, Mor Katz, Mark Chen, Christopher Hesse, Jacob Jackson, Heewoo Jun, Tom B Brown, Prafulla Dhariwal, Scott Gray, et al.  Scaling laws for autoregressive generative modeling.  arXiv preprint arXiv:2010.14701, 2020.
  * [5] Utkarsh Sharma and Jared Kaplan.  Scaling laws from the data manifold dimension.  J. Mach. Learn. Res., 23:9–1, 2022.
  * [6] Yasaman Bahri, Ethan Dyer, Jared Kaplan, Jaehoon Lee, and Utkarsh Sharma.  Explaining neural scaling laws.  arXiv preprint arXiv:2102.06701, 2021.
  * [7] Andrea Caponnetto and Ernesto De Vito.  Optimal rates for the regularized least-squares algorithm.  Foundations of Computational Mathematics, 7(3):331–368, 2007.
  * [8] A. Caponnetto and E. D. Vito.  Fast rates for regularized least-squares algorithm.  In ., 2005.
  * [9] Junhong Lin, Alessandro Rudi, L. Rosasco, and V. Cevher.  Optimal rates for spectral algorithms with least-squares regression over hilbert spaces.  Applied and Computational Harmonic Analysis, 48:868–890, 2018.
  * [10] Kwang-Sung Jun, Ashok Cutkosky, and Francesco Orabona.  Kernel truncated randomized ridge regression: Optimal rates and low noise acceleration.  In NeurIPS, 2019.
  * [11] Fanghui Liu, Zhenyu Liao, and Johan AK Suykens.  Kernel regression in high dimension: Refined analysis beyond double descent.  arXiv preprint arXiv:2010.02681, 2020.
  * [12] Loucas Pillaud-Vivien, Alessandro Rudi, and Francis Bach.  Statistical optimality of stochastic gradient descent on hard learning problems through multiple passes.  In Advances in Neural Information Processing Systems, volume 31, pages 8114–8124, 2018.
  * [13] Raphael Berthier, F. Bach, and P. Gaillard.  Tight nonparametric convergence rates for stochastic gradient descent under the noiseless linear model.  ArXiv, abs/2006.08212, 2020.
  * [14] Aditya Varre, Loucas Pillaud-Vivien, and Nicolas Flammarion.  Last iterate convergence of sgd for least-squares in the interpolation regime.  ArXiv, abs/2102.03183, 2021.
  * [15] Hugo Cui, Bruno Loureiro, F. Krzakala, and Lenka Zdeborová.  Generalization error rates in kernel regression: The crossover from the noiseless to noisy regime.  ArXiv, abs/2105.15004, 2021.
  * [16] Alexander Maloney, Daniel A Roberts, and James Sully.  A solvable model of neural scaling laws.  arXiv preprint arXiv:2210.16859, 2022.
  * [17] Marcus Hutter.  Learning curve theory.  arXiv preprint arXiv:2102.04074, 2021.
  * [18] Ulysse Marteau-Ferey, Dmitrii Ostrovskii, Francis R. Bach, and Alessandro Rudi.  Beyond least-squares: Fast rates for regularized empirical risk minimization through self-concordance.  In COLT, 2019.
  * [19] Ingo Steinwart, Don R Hush, Clint Scovel, et al.  Optimal rates for regularized least squares regression.  In COLT, pages 79–93, 2009.
  * [20] P. Bartlett, Philip M. Long, G. Lugosi, and Alexander Tsigler.  Benign overfitting in linear regression.  Proceedings of the National Academy of Sciences, 117:30063 – 30070, 2020.
  * [21] Edgar Dobriban and Stefan Wager.  High-dimensional asymptotics of prediction: Ridge regression and classification.  The Annals of Statistics, 46(1):247–279, 2018.
  * [22] Lee H Dicker et al.  Ridge regression and asymptotic minimax estimation over spheres of growing dimension.  Bernoulli, 22(1):1–37, 2016.
  * [23] Daniel Hsu, Sham M. Kakade, and Tong Zhang.  Random design analysis of ridge regression.  In Shie Mannor, Nathan Srebro, and Robert C. Williamson, editors, Proceedings of the 25th Annual Conference on Learning Theory, volume 23 of Proceedings of Machine Learning Research, pages 9.1–9.24, Edinburgh, Scotland, 25–27 Jun 2012. JMLR Workshop and Conference Proceedings.
  * [24] Ingo Steinwart and Andreas Christmann.  Support vector machines.  In Information science and statistics, 2008.
  * [25] Bernhard Schölkopf and Alexander J Smola.  Learning with kernels: support vector machines, regularization, optimization, and beyond.  MIT press, 2002.
  * [26] Ingo Steinwart and Clint Scovel.  Fast rates for support vector machines using gaussian kernels.  Annals of Statistics, 35:575–607, 2007.
  * [27] Jean-Yves Audibert and Alexandre B. Tsybakov.  Fast learning rates for plug-in classifiers.  Annals of Statistics, 35:608–633, 2007.
  * [28] Bruno Loureiro, Cédric Gerbelot, Hugo Cui, Sebastian Goldt, F. Krzakala, M. Mézard, and Lenka Zdeborová.  Capturing the learning curves of generic features maps for realistic data sets with a teacher-student model.  ArXiv, abs/2102.08127, 2021.
  * [29] Hui Jin, Pradeep Kr. Banerjee, and Guido Montúfar.  Learning curves for gaussian process regression with power-law priors and targets, 2021.
  * [30] Stefano Spigler, Mario Geiger, and Matthieu Wyart.  Asymptotic learning curves of kernel methods: empirical data versus teacher–student paradigm.  Journal of Statistical Mechanics: Theory and Experiment, 2020(12):124001, 2020.
  * [31] Blake Bordelon, Abdulkadir Canatar, and Cengiz Pehlevan.  Spectrum dependent learning curves in kernel regression and wide neural networks.  In International Conference on Machine Learning, pages 1024–1034. PMLR, 2020.
  * [32] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner.  Gradient-based learning applied to document recognition.  Proceedings of the IEEE, 86(11):2278–2324, 1998.
  * [33] Han Xiao, Kashif Rasul, and Roland Vollgraf.  Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms.  arXiv preprint arXiv:1708.07747, 2017.
  * [34] Marc Mézard, Giorgio Parisi, and Miguel Virasoro.  Spin glass theory and beyond: An Introduction to the Replica Method and Its Applications, volume 9.  World Scientific Publishing Company, 1987.
  * [35] Rainer Dietrich, Manfred Opper, and Haim Sompolinsky.  Statistical mechanics of support vector networks.  Physical Review Letters, 82:2975–2978, 1999.
  * [36] Andreas Engel and Christian Van den Broeck.  Statistical mechanics of learning.  Cambridge University Press, 2001.
  * [37] Marc Mézard and Andrea Montanari.  Information, physics, and computation.  Oxford University Press, 2009.
  * [38] Madhu S Advani, Andrew M Saxe, and Haim Sompolinsky.  High-dimensional dynamics of generalization error in neural networks.  Neural Networks, 132:428–446, 2020.
  * [39] Qianyi Li and Haim Sompolinsky.  Statistical mechanics of deep linear neural networks: The backpropagating kernel renormalization.  Physical Review X, 11(3):031059, 2021.
  * [40] S Ariosto, R Pacelli, M Pastore, F Ginelli, M Gherardi, and P Rotondo.  Statistical mechanics of deep learning beyond the infinite-width limit.  arXiv preprint arXiv:2209.04882, 2022.
  * [41] Inbar Seroussi, Gadi Naveh, and Zohar Ringel.  Separation of scales and a thermodynamic description of feature learning in some cnns.  Nature Communications, 14(1):908, 2023.
  * [42] Hugo Cui, Florent Krzakala, and Lenka Zdeborová.  Optimal learning of deep random networks of extensive-width.  arXiv preprint arXiv:2302.00375, 2023.
  * [43] Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al.  Scikit-learn: Machine learning in python.  the Journal of machine Learning research, 12:2825–2830, 2011.
  * [44] Stéphane Boucheron, Olivier Bousquet, and Gábor Lugosi.  Theory of classification : a survey of some recent advances.  Esaim: Probability and Statistics, 9:323–375, 2005.
  * [45] Andrea Della Vecchia, Jaouad Mourtada, Ernesto de Vito, and Lorenzo Rosasco.  Regularized erm on random subspaces.  ArXiv, abs/2006.10016, 2021.
  * [46] Vidya Muthukumar, Adhyyan Narang, Vignesh Subramanian, Mikhail Belkin, Daniel Hsu, and Anant Sahai.  Classification vs regression in overparameterized regimes: Does the loss function matter?  Journal of Machine Learning Research, 22(222):1–69, 2021.
  * [47] Daniel Hsu, Vidya Muthukumar, and Ji Xu.  On the proliferation of support vectors in high dimensions, 2020.
  * [48] Navid Ardeshir, Clayton Sanford, and Daniel Hsu.  Support vector machines and linear regression coincide with very high-dimensional features.  ArXiv, abs/2105.14084, 2021.
  * [49] Alex Krizhevsky, Geoffrey Hinton, et al.  Learning multiple layers of features from tiny images.  -, 2009.
  * [50] Benjamin Aubin, Florent Krzakala, Yue M Lu, and Lenka Zdeborová.  Generalization error in high-dimensional perceptrons: Approaching bayes error with convex optimization.  In Advances in Neural Information Processing Systems, volume 33, 2020.
  * [51] Abdulkadir Canatar, B. Bordelon, and C. Pehlevan.  Spectral bias and task-model alignment explain generalization in kernel regression and infinitely wide neural networks.  Nature Communications, 12:1–12, 2021.
  * [52] Jonas Paccolat, Stefano Spigler, and Matthieu Wyart.  How isotropic kernels perform on simple invariants.  Machine Learning: Science and Technology, 2, 2021.

##  Appendix A Rates for margin maximizing SVM

In this appendix, we provide some analytical discussion of the equations (13)
motivating the scaling (15) and (14). We remind the risk for the hinge loss
(12)

$\hat{\mathcal{R}}_{n}(w)=\frac{1}{n}\sum\limits_{\mu=1}^{n}\mathrm{max}\left(0,1-y^{\mu}w^{\top}\psi(x)\right)+\lambda
w^{\top}w,$ (22)

with $\lambda=0^{+}$ for max-margin. The predictor is then
$\hat{y}=\mathrm{sign}(\hat{w}\cdot\psi(x))$.

###  A.1 Mapping from (Loureiro et. al, 2021)

The starting point is the closed-form asymptotic characterization of the
misclassification error of [28]. We begin by reviewing the main results of
[28], and detail how their setting can be mapped to ours. Consider hinge
regression on $n$ independent $p-$ dimensional Gaussian samples
$\mathcal{D}=\\{x^{\mu},y^{\mu}\\}_{\mu=1}^{n}$, by minimizing the empirical
risk

$\hat{\mathcal{R}}_{n}(w)=\sum\limits_{\mu=1}^{n}\mathrm{max}\left(0,1-y^{\mu}\frac{w^{\top}x^{\mu}}{\sqrt{p}}\right)+\frac{\lambda}{2}w^{\top}w$
(23)

for some constant regularization strength $\lambda\geq 0$. Suppose that the
labels are generated from a teacher/target/oracle
$\theta^{\star}\in\mathbb{R}^{p}$ as
$y^{\mu}=\mathrm{sign}(\theta^{\star\top}x^{\mu})$. Then provided the
assumptions

  * •

A.1 $n\gg 1,\,p\gg 1,\,\frac{n}{p}=\mathcal{O}(1)$,

  * •

A.2 $0<\frac{1}{p}||\theta^{\star}||^{2}_{2}<\infty$,

are satisfied, there exist constants $C,c,c^{\prime}>0$ so that for all
$0<\epsilon<c^{\prime}$,

$\mathbb{P}\left(\left|\epsilon_{g}-\frac{1}{\pi}\mathrm{arccos}\left(\frac{m^{\star}}{\sqrt{\rho
q^{\star}}}\right)\right|>\epsilon\right)<\frac{C}{\epsilon}e^{-cn\epsilon^{2}},$
(24)

where $\rho=\theta^{\star\top}\Sigma\theta^{\star}/p$ and
$m^{\star},\,q^{\star}$ are the solutions of the fixed point equations

$\displaystyle\begin{cases}m=\frac{\hat{m}}{p}~{}\mathrm{tr}\frac{\Sigma\theta^{\star}\theta^{\star\top}\Sigma}{\lambda+\hat{V}\Sigma}\\\
q=\frac{1}{p}\mathrm{tr}\frac{\hat{m}^{2}\Sigma\theta^{\star}\theta^{\star\top}\Sigma^{2}+\hat{q}\Sigma^{2}}{(\lambda+\hat{V}\Sigma)^{2}}\\\
V=\frac{1}{p}\mathrm{tr}\frac{\Sigma}{\lambda+\hat{V}\Sigma}\end{cases},$
$\displaystyle\begin{cases}\begin{aligned}
\hat{m}&=\frac{\frac{n}{p}}{V\sqrt{\rho}}\frac{1}{2\pi}\Bigg{\\{}\sqrt{2\pi}\left[\mathrm{erf}\left(\frac{1}{\sqrt{2q(1-\eta)}}\right)-\mathrm{erf}\left(\frac{1-V}{\sqrt{2q(1-\eta)}}\right)\right]\\\
&+2\sqrt{q(1-\eta)}\left(e^{-\frac{1}{2q(1-\eta)}}-e^{-\frac{(1-V)^{2}}{2q(1-\eta)}}\right)+\sqrt{2\pi}V\left(1+\mathrm{erf}\left(\frac{1-V}{\sqrt{2q(1-\eta)}}\right)\right)\Bigg{\\}}\end{aligned}\\\
\hat{q}=\frac{n}{p}\Bigg{[}\int\limits_{-\infty}^{\frac{1-V}{\sqrt{q}}}dx\frac{e^{-\frac{1}{2}x^{2}}}{\sqrt{2\pi}}\left[1+\mathrm{erf}(\sqrt{\frac{\eta}{2(1-\eta)}}x)\right]+\frac{1}{V^{2}}\int\limits_{\frac{1-V}{\sqrt{q}}}^{\frac{1}{\sqrt{q}}}dx\frac{e^{-\frac{1}{2}x^{2}}}{\sqrt{2\pi}}\left[1+\mathrm{erf}(\sqrt{\frac{\eta}{2(1-\eta)}}x)\right](1-\sqrt{q}x)^{2}\Bigg{]}\\\
\hat{V}=\frac{\frac{n}{p}}{V}\int\limits_{\frac{1-V}{\sqrt{q}}}^{\frac{1}{\sqrt{q}}}dx\frac{e^{-\frac{1}{2}x^{2}}}{\sqrt{2\pi}}\left[1+\mathrm{erf}(\sqrt{\frac{\eta}{2(1-\eta)}}x)\right]\end{cases},$

with $\eta=m^{2}/(\rho q)$, and $\Sigma$ the covariance of the samples $x$.
The limit $\lambda=0^{+}$ can be taken using the rescaling [50]

$\displaystyle\hat{m}\leftarrow\frac{\hat{m}}{\lambda},$
$\displaystyle\hat{q}\leftarrow\frac{\hat{q}}{\lambda},$
$\displaystyle\hat{V}\leftarrow\frac{\hat{V}}{\lambda},$ $\displaystyle
V\leftarrow\lambda V.$ (25)

The equations (A.1) simplify in this limit to

$\displaystyle\begin{cases}m=\frac{\hat{m}}{p}~{}\mathrm{tr}\frac{\Sigma\theta^{\star}\theta^{\star\top}\Sigma}{1+\hat{V}\Sigma}\\\
q=\frac{1}{p}\mathrm{tr}\frac{\hat{m}^{2}\Sigma\theta^{\star}\theta^{\star\top}\Sigma^{2}+\hat{q}\Sigma^{2}}{(1+\hat{V}\Sigma)^{2}}\\\
V=\frac{1}{p}\mathrm{tr}\frac{\Sigma}{1+\hat{V}\Sigma}\end{cases},$
$\displaystyle\begin{cases}\hat{m}=\frac{\frac{n}{p}}{V\sqrt{\rho}}\frac{1}{2\pi}\left(\sqrt{2\pi}(1+\mathrm{erf}(\frac{1}{\sqrt{2q(1-\eta)}}))+2e^{-\frac{1}{2q(1-\eta)}}\sqrt{q(1-\eta)}\right)\\\
\hat{q}=\frac{\frac{n}{p}}{V^{2}}\int\limits_{-\infty}^{\frac{1}{\sqrt{q}}}dx\frac{e^{-\frac{1}{2}x^{2}}}{\sqrt{2\pi}}\left[1+\mathrm{erf}(\sqrt{\frac{\eta}{2(1-\eta)}}x)\right](1-\sqrt{q}x)^{2}\\\
\hat{V}=\frac{\frac{n}{p}}{V}\int\limits_{-\infty}^{\frac{1}{\sqrt{q}}}dx\frac{e^{-\frac{1}{2}x^{2}}}{\sqrt{2\pi}}\left[1+\mathrm{erf}(\sqrt{\frac{\eta}{2(1-\eta)}}x)\right]\end{cases}.$
(26)

Note that the risk studied by [28] (23) differs from the one we consider (12)
by the scaling $1/\sqrt{p}$, the missing $1/n$ in front of the sum, and a
factor $2$ for the regularization strength. All those scalings can be absorbed
in $\lambda\leftarrow 2\lambda/n$ and $\Sigma\leftarrow\Sigma/p$, leading to
(13):

$\displaystyle\begin{cases}m=\hat{m}p~{}\mathrm{tr}\frac{\Sigma\theta^{\star}\theta^{\star\top}\Sigma}{1+p\hat{V}\Sigma}\\\
q=p\mathrm{tr}\frac{p\hat{m}^{2}\Sigma\theta^{\star}\theta^{\star\top}\Sigma^{2}+\hat{q}\Sigma^{2}}{(1+p\hat{V}\Sigma)^{2}}\\\
V=\mathrm{tr}\frac{\Sigma}{1+p\hat{V}\Sigma}\\\ \end{cases},$
$\displaystyle\begin{cases}\hat{m}=\frac{\frac{n}{p}}{V\sqrt{\rho}}\frac{1}{2\pi}\left(\sqrt{2\pi}(1+\mathrm{erf}(\frac{1}{\sqrt{2q(1-\eta)}}))+2e^{-\frac{1}{2q(1-\eta)}}\sqrt{q(1-\eta)}\right)\\\
\hat{q}=\frac{\frac{n}{p}}{V^{2}}\int\limits_{-\infty}^{\frac{1}{\sqrt{q}}}dx\frac{e^{-\frac{1}{2}x^{2}}}{\sqrt{2\pi}}\left[1+\mathrm{erf}(\sqrt{\frac{\eta}{2(1-\eta)}}x)\right](1-\sqrt{q}x)^{2}\\\
\hat{V}=\frac{\frac{n}{p}}{V}\int\limits_{-\infty}^{\frac{1}{\sqrt{q}}}dx\frac{e^{-\frac{1}{2}x^{2}}}{\sqrt{2\pi}}\left[1+\mathrm{erf}(\sqrt{\frac{\eta}{2(1-\eta)}}x)\right]\end{cases},$
(27)

thereby completeing the mapping from the setup in [28] to the present setting.

###  A.2 Equations for max-margin under source and capacity conditions

In the following, we detail the asymptotic scaling analysis of the equations
(13). For a diagonal covariance
$\Sigma=\mathrm{diag}(\omega_{1},...,\omega_{p})$ and
$\theta^{\star}=(\theta_{k}^{\star})_{k}$, (13) reads

$\displaystyle\begin{cases}\rho=\sum\limits_{k=1}^{p}\theta_{k}^{\star
2}\omega_{k}\\\
m=\hat{m}p\sum\limits_{k=1}^{d}\frac{\omega_{k}^{2}\theta_{k}^{\star
2}}{1+\hat{V}p\omega_{k}}\\\
q=p\sum\limits_{k=1}^{p}\frac{p\hat{m}^{2}\theta_{k}^{\star
2}\omega_{k}^{3}+\hat{q}\omega_{k}^{2}}{(1+\hat{V}p\omega_{k})^{2}}\\\
V=\sum\limits_{k=1}^{p}\frac{\omega_{k}}{1+\hat{V}p\omega_{k}}\\\
\end{cases},$
$\displaystyle\begin{cases}\hat{m}=\frac{\frac{n}{p}}{V\sqrt{\rho}}\frac{1}{2\pi}\left(\sqrt{2\pi}(1+\mathrm{erf}(\frac{1}{\sqrt{2q(1-\eta)}}))+2e^{-\frac{1}{2q(1-\eta)}}\sqrt{q(1-\eta)}\right)\\\
\hat{q}=\frac{\frac{n}{p}}{V^{2}}\int\limits_{-\infty}^{\frac{1}{\sqrt{q}}}dx\frac{e^{-\frac{1}{2}x^{2}}}{\sqrt{2\pi}}\left[1+\mathrm{erf}(\sqrt{\frac{\eta}{2(1-\eta)}}x)\right](1-\sqrt{q}x)^{2}\\\
\hat{V}=\frac{\frac{n}{p}}{V}\int\limits_{-\infty}^{\frac{1}{\sqrt{q}}}dx\frac{e^{-\frac{1}{2}x^{2}}}{\sqrt{2\pi}}\left[1+\mathrm{erf}(\sqrt{\frac{\eta}{2(1-\eta)}}x)\right]\end{cases}.$
(28)

To simplify the equations (28), we introduce the auxiliary variables
$z=\frac{n}{p}/\hat{V}$, $\hat{r}_{1}=\hat{m}/\hat{V}$ and
$\hat{r}_{2}=(n\hat{q})/(p\hat{V}^{2})$. The intuitive meaning of $z$ is
loosely that of an effective regularization. In the context of kernel ridge
regression where a similar variable appears, the role of $z$ as an effective
regularizing term is quite clear in [15]. We also refer the reader to the
discussion in [28], also for ridge regression, where the role of $\hat{V}$ as
parametrizing the gap between training and test error is mentionned.
$\hat{r}_{1}$ is to be regarded as the ratio between the norm of the estimator
$\hat{w}$ minimizing the risk (12), and the norm of the teacher
$\theta^{\star}$. Introducing these variables in (28) allows to have a well
defined $p=\infty$ limit, which reads

$\displaystyle\begin{cases}\rho=\sum\limits_{k=1}^{\infty}\theta_{k}^{\star
2}\omega_{k}\\\
m=\hat{r}_{1}\frac{n}{z}\sum\limits_{k=1}^{\infty}\frac{\omega_{k}^{2}\theta_{k}^{\star
2}}{1+\frac{n}{z}\omega_{k}}\\\
q=\frac{n^{2}}{z^{2}}\sum\limits_{k=1}^{\infty}\frac{\hat{r}_{1}^{2}\theta_{k}^{\star
2}\omega_{k}^{3}+\frac{1}{n}\hat{r}_{2}\omega_{k}^{2}}{(1+\frac{n}{z}\omega_{k})^{2}}\\\
V=\sum\limits_{k=1}^{d}\frac{\omega_{k}}{1+\frac{n}{z}\omega_{k}}\\\
\end{cases},$
$\displaystyle\begin{cases}\hat{r}_{1}=\frac{\hat{m}}{\hat{V}}=\frac{1}{2\pi\sqrt{\rho}}\frac{\left(\sqrt{2\pi}(1+\mathrm{erf}(\frac{1}{\sqrt{2q(1-\eta)}}))+2e^{-\frac{1}{2q(1-\eta)}}\sqrt{q(1-\eta)}\right)}{\int\limits_{-\infty}^{\frac{1}{\sqrt{q}}}dx\frac{e^{-\frac{1}{2}x^{2}}}{\sqrt{2\pi}}\left[1+\mathrm{erf}(\sqrt{\frac{\eta}{2(1-\eta)}}x)\right]}\\\
\hat{r}_{2}=\frac{\frac{n}{p}\hat{q}}{\hat{V}^{2}}=\frac{\int\limits_{-\infty}^{\frac{1}{\sqrt{q}}}dx\frac{e^{-\frac{1}{2}x^{2}}}{\sqrt{2\pi}}\left[1+\mathrm{erf}(\sqrt{\frac{\eta}{2(1-\eta)}}x)\right](1-\sqrt{q}x)^{2}}{\left(\int\limits_{-\infty}^{\frac{1}{\sqrt{q}}}dx\frac{e^{-\frac{1}{2}x^{2}}}{\sqrt{2\pi}}\left[1+\mathrm{erf}(\sqrt{\frac{\eta}{2(1-\eta)}}x)\right]\right)^{2}}\\\
\end{cases}.$ (29)

From (28), $z$ satisfies the self-consistent equation

$z=\frac{\frac{z}{n}\sum\limits_{k=1}^{\infty}\frac{\omega_{k}}{\frac{z}{n}+\omega_{k}}}{\int\limits_{-\infty}^{\frac{1}{\sqrt{q}}}dx\frac{e^{-\frac{1}{2}x^{2}}}{\sqrt{2\pi}}\left[1+\mathrm{erf}(\sqrt{\frac{\eta}{2(1-\eta)}}x)\right]}\approx\frac{\left(\frac{z}{n}\right)^{1-\frac{1}{\alpha}}\int_{\left(\frac{z}{n}\right)^{\frac{1}{\alpha}}}^{\infty}\frac{dx}{1+x^{\alpha}}}{\int\limits_{-\infty}^{\frac{1}{\sqrt{q}}}dx\frac{e^{-\frac{1}{2}x^{2}}}{\sqrt{2\pi}}\left[1+\mathrm{erf}(\sqrt{\frac{\eta}{2(1-\eta)}}x)\right]},$
(30)

where a Riemann approximation of the sum was used. We introduce its to-be-
determined scaling $\gamma$,

$z\sim C_{z}n^{1-\alpha\gamma},$ (31)

where $C_{z}$ designates the prefactor. In the following, we discuss the
scaling and the corrections of the order parameters and express them as a
function of $\gamma$, before determining its value using the numerical
solution of (29). Note that the scaling (31) implies in particular the
following scaling for the integral

$\int\limits_{-\infty}^{\frac{1}{\sqrt{q}}}dx\frac{e^{-\frac{1}{2}x^{2}}}{\sqrt{2\pi}}\left[1+\mathrm{erf}(\sqrt{\frac{\eta}{2(1-\eta)}}x)\right]\sim
n^{\gamma-1}.$ (32)

###  A.3 First order corrections

We now plug the source and capacity ansatz (7) into the equations (29)

$\displaystyle\omega_{k}\sim k^{-\alpha},$
$\displaystyle\theta_{k}^{\star}\sim k^{-\frac{1+\alpha(2r-1)}{2}},$ (33)

yielding

$\displaystyle\begin{cases}\rho=&\sum\limits_{k=1}^{\infty}k^{-1-2\alpha r}\\\
m=&\hat{r}_{1}\sum\limits_{k=1}^{\infty}\frac{k^{-1-2\alpha
r}}{1+\frac{z}{n}k^{\alpha}}\\\
q=&\hat{r}_{1}^{2}\sum\limits_{k=1}^{\infty}\frac{k^{-1-2\alpha
r}}{(1+\frac{z}{n}k^{\alpha})^{2}}\\\
&+\frac{\hat{r}_{2}}{n}\sum\limits_{k=1}^{\infty}\frac{1}{(1+\frac{z}{n}k^{\alpha})^{2}}\\\
V=&\frac{z}{n}\sum\limits_{k=1}^{\infty}\frac{1}{1+\frac{z}{n}k^{\alpha}}\end{cases},$
$\displaystyle\begin{cases}\hat{r}_{1}=\frac{1}{2\pi\sqrt{\rho}}\frac{\left(\sqrt{2\pi}(1+\mathrm{erf}(\frac{1}{\sqrt{2q(1-\eta)}}))+2e^{-\frac{1}{2q(1-\eta)}}\sqrt{q(1-\eta)}\right)}{\int\limits_{-\infty}^{\frac{1}{\sqrt{q}}}dx\frac{e^{-\frac{1}{2}x^{2}}}{\sqrt{2\pi}}\left[1+\mathrm{erf}(\sqrt{\frac{\eta}{2(1-\eta)}}x)\right]}\\\
\hat{r}_{2}=\frac{\int\limits_{-\infty}^{\frac{1}{\sqrt{q}}}dx\frac{e^{-\frac{1}{2}x^{2}}}{\sqrt{2\pi}}\left[1+\mathrm{erf}(\sqrt{\frac{\eta}{2(1-\eta)}}x)\right](1-\sqrt{q}x)^{2}}{\left(\int\limits_{-\infty}^{\frac{1}{\sqrt{q}}}dx\frac{e^{-\frac{1}{2}x^{2}}}{\sqrt{2\pi}}\left[1+\mathrm{erf}(\sqrt{\frac{\eta}{2(1-\eta)}}x)\right]\right)^{2}}\\\
\end{cases}.$

Massaging the expression for $m$ (and remembering $z\sim n^{1-\alpha\gamma}$
(31))

$\displaystyle m$
$\displaystyle=\hat{r}_{1}\rho-\hat{r}_{1}\sum\limits_{k=1}^{\infty}\frac{k^{-1-2\alpha
r}C_{z}\left(\frac{k}{n^{\gamma}}\right)^{\alpha}}{1+C_{z}\left(\frac{k}{n^{\gamma}}\right)^{\alpha}}$
$\displaystyle=\hat{r}_{1}\rho-
C_{z}\hat{r}_{1}n^{-\gamma\alpha}\sum\limits_{k=1}^{\infty}\frac{k^{-1-2\alpha(r-\frac{1}{2})}}{1+C_{z}\left(\frac{k}{n^{\gamma}}\right)^{\alpha}}$
$\displaystyle\approx\hat{r}_{1}\rho-\mathbbm{1}_{r\geq\frac{1}{2}}\hat{r}_{1}C_{z}\left[n^{-\gamma\alpha}\sum\limits_{k=1}^{n^{\gamma}}\frac{k^{-1-2\alpha(r-\frac{1}{2})}}{1+C_{z}\left(\frac{k}{n^{\gamma}}\right)^{\alpha}}+n^{-2\gamma\alpha
r}\int\limits_{1}^{\infty}\frac{x^{-1+\alpha(1-2r)}}{1+C_{z}x^{\alpha}}\right]$
$\displaystyle~{}~{}~{}~{}-\mathbbm{1}_{r\leq\frac{1}{2}}C_{z}\hat{r}_{1}n^{-2\gamma\alpha
r}\int\limits_{0}^{\infty}\frac{x^{-1+\alpha(1-2r)}}{1+C_{z}x^{\alpha}}$
$\displaystyle=\hat{r}_{1}\left[\rho-\mathbbm{1}_{r\geq\frac{1}{2}}C_{z}A^{n}_{m}n^{-\gamma\alpha}-C_{z}n^{-2\gamma\alpha
r}\int\limits_{\Theta(r-\frac{1}{2})}^{\infty}\frac{x^{-1+\alpha(1-2r)}}{1+C_{z}x^{\alpha}}+o\left(\mathrm{max}\left(n^{-\gamma\alpha},n^{-2\gamma\alpha
r}\right)\right)\right],$ (34)

where we used the shorthand

$A_{m}^{n}\overset{\mathrm{def}}{=}\sum\limits_{k=1}^{n^{\gamma}}\frac{k^{-1-2\alpha(r-\frac{1}{2})}}{1+C_{z}\left(\frac{k}{n^{\gamma}}\right)^{\alpha}}.$
(35)

Massaging by the same token the equation for $q$,

$\displaystyle q$
$\displaystyle\approx\hat{r}_{1}^{2}\rho-\hat{r}_{1}^{2}\sum\limits_{k=1}^{\infty}\frac{k^{-1-2\alpha
r}\left(C_{z}^{2}\left(\frac{k}{n^{\gamma}}\right)^{2\alpha}+2C_{z}\left(\frac{k}{n^{\gamma}}\right)^{\alpha}\right)}{\left(1+C_{z}\left(\frac{k}{n^{\gamma}}\right)^{\alpha}\right)^{2}}+\hat{r}_{2}n^{\gamma-1}\int\limits_{0}^{\infty}\frac{1}{(1+C_{z}x^{\alpha})^{2}}$
$\displaystyle\approx\hat{r}_{1}^{2}\rho+\hat{r}_{2}n^{\gamma-1}\int\limits_{0}^{\infty}\frac{1}{(1+C_{z}x^{\alpha})^{2}}$
$\displaystyle~{}~{}~{}~{}-2\hat{r}_{1}^{2}C_{z}\Bigg{[}\mathbbm{1}_{r\geq\frac{1}{2}}\left(n^{-\gamma\alpha}\sum\limits_{k=1}^{n^{\gamma}}\frac{k^{-1-2\alpha(r-\frac{1}{2})}}{\left(1+C_{z}\left(\frac{k}{n^{\gamma}}\right)^{\alpha}\right)^{2}}+n^{-2\gamma\alpha
r}\int\limits_{1}^{\infty}\frac{x^{-1+\alpha(1-2r)}}{(1+C_{z}x^{\alpha})^{2}}\right)$
$\displaystyle~{}~{}~{}~{}+\mathbbm{1}_{r\leq\frac{1}{2}}n^{-2\gamma\alpha
r}\int\limits_{0}^{\infty}\frac{x^{-1+\alpha(1-2r)}}{(1+C_{z}x^{\alpha})^{2}}\Bigg{]}$
$\displaystyle~{}~{}~{}~{}-\hat{r}_{1}^{2}C_{z}^{2}\Bigg{[}\mathbbm{1}_{r\geq
1}\Bigg{(}n^{-2\gamma\alpha}\sum\limits_{k=1}^{n^{\gamma}}\frac{k^{-1-2\alpha(r-1)}}{\left(1+C_{z}\left(\frac{k}{n^{\gamma}}\right)^{\alpha}\right)^{2}}$
$\displaystyle~{}~{}~{}~{}+n^{-2\gamma\alpha
r}\int\limits_{1}^{\infty}\frac{x^{-1+\alpha(2-2r)}}{(1+C_{z}x^{\alpha})^{2}}\Bigg{)}+\mathbbm{1}_{r\leq
1}n^{-2\gamma\alpha
r}\int\limits_{0}^{\infty}\frac{x^{-1+\alpha(2-2r)}}{(1+C_{z}x^{\alpha})^{2}}\Bigg{]}$
$\displaystyle=\hat{r}_{1}^{2}\Bigg{[}\rho+\frac{\hat{r}_{2}}{\hat{r}_{1}^{2}}n^{\gamma-1}\int\limits_{0}^{\infty}\frac{1}{(1+C_{z}x^{\alpha})^{2}}-\mathbbm{1}_{r\geq\frac{1}{2}}2C_{z}A^{n}_{q}n^{-\gamma\alpha}-\mathbbm{1}_{r\geq
1}C_{z}^{2}B^{n}_{q}n^{-2\gamma\alpha}$
$\displaystyle~{}~{}~{}~{}-n^{-2\gamma\alpha
r}\Bigg{(}2C_{z}\int\limits_{\Theta(r-\frac{1}{2})}^{\infty}\frac{x^{-1+\alpha(1-2r)}}{(1+C_{z}x^{\alpha})^{2}}+C_{z}^{2}\int\limits_{\Theta(r-1)}^{\infty}\frac{x^{-1+\alpha(2-2r)}}{(1+C_{z}x^{\alpha})^{2}}\Bigg{)}$
$\displaystyle~{}~{}~{}~{}+o\left(\mathrm{max}\left(\frac{\hat{r}_{2}}{\hat{r}_{1}^{2}}n^{\gamma-1},n^{-\gamma\alpha},n^{-2\gamma\alpha
r}\right)\right)\Bigg{]},$ (36)

where we defined

$\displaystyle
A_{q}^{n}\overset{\mathrm{def}}{=}\sum\limits_{k=1}^{n^{\gamma}}\frac{k^{-1-2\alpha(r-\frac{1}{2})}}{\left(1+C_{z}\left(\frac{k}{n^{\gamma}}\right)^{\alpha}\right)^{2}},$
$\displaystyle
B^{n}_{q}\overset{\mathrm{def}}{=}\sum\limits_{k=1}^{n^{\gamma}}\frac{k^{-1-2\alpha(r-1)}}{\left(1+C_{z}\left(\frac{k}{n^{\gamma}}\right)^{\alpha}\right)^{2}}.$
(37)

An important remark on (A.3) and (A.3) is that $A^{m}_{q}$ and $A^{n}_{m}$
tend to the same limit as $n\rightarrow\infty$,

$A^{\infty}_{m,q}=\sum\limits_{k=1}^{\infty}k^{-1-2\alpha(r-\frac{1}{2})},$
(38)

with (for $r\geq\frac{1}{2}$ since there is an indicator function in front of
$A^{n}_{m,q}$)

$\displaystyle\begin{cases}n^{-\gamma\alpha}|A^{n}_{m}-A^{\infty}|=&\frac{n^{-2\alpha\gamma
r}}{2\alpha(r-\frac{1}{2})}+\mathbbm{1}_{\frac{1}{2}\leq r\leq
1}C_{z}n^{-2\alpha\gamma
r}\int\limits_{0}^{1}\frac{x^{-1-2\alpha(r-1)}}{1+C_{z}x^{\alpha}}\\\
&+\mathbbm{1}_{r\geq
1}C_{z}n^{-2\gamma\alpha}\sum\limits_{k=1}^{\infty}k^{-1-2\alpha(r-1)},\\\
n^{-\gamma\alpha}|A^{n}_{q}-A^{\infty}|=&\frac{n^{-2\alpha\gamma
r}}{2\alpha(r-\frac{1}{2})}+2\mathbbm{1}_{\frac{1}{2}\leq r\leq
1}C_{z}n^{-2\alpha\gamma
r}\int\limits_{0}^{1}\frac{x^{-1-2\alpha(r-1)}}{(1+C_{z}x^{\alpha})^{2}}\\\
&+2\mathbbm{1}_{r\geq
1}C_{z}n^{-2\gamma\alpha}\sum\limits_{k=1}^{\infty}k^{-1-2\alpha(r-1)}+o(n^{-2\gamma\alpha}).\end{cases}$

More straigtforwardly,

$B^{\infty}_{q}=\sum\limits_{k=1}^{\infty}k^{-1-2\alpha(r-1)}.$ (39)

Finally, remark that the expansions (A.3) and (A.3) imply that
$m\sim\hat{r}_{1}\rho$ and $q\sim\hat{r}_{1}^{2}\rho$, which echoes the
intuitive meaning of $m,q$ as
$\langle\hat{w},\theta^{\star}\rangle_{L^{2}(\mathcal{X})},\,||\hat{w}||^{2}_{L^{2}(\mathcal{X})}$
and of $\hat{r}_{1}$ as
$||\hat{w}||^{2}_{L^{2}(\mathcal{X})}/||\theta^{\star}||^{2}_{L^{2}(\mathcal{X})}$,
see also discussion in section II under equation (11).

The expansions (A.3) and (A.3) can be plugged into the expression of the
cosine similarity $\eta$ (9) to access the decay rate for the
misclassification error.

$\displaystyle\eta$
$\displaystyle=\Bigg{(}1-\mathbbm{1}_{r\geq\frac{1}{2}}C_{z}\frac{A^{n}_{m}}{\rho}n^{-\gamma\alpha}-n^{-2\gamma\alpha
r}\frac{C_{z}}{\rho}\int\limits_{\Theta(r-\frac{1}{2})}^{\infty}\frac{x^{-1+\alpha(1-2r)}}{1+C_{z}x^{\alpha}}\Bigg{)}^{2}\Bigg{/}\Bigg{(}1+$
$\displaystyle\frac{\hat{r}_{2}}{\rho\hat{r}_{1}^{2}}n^{\gamma-1}\int\limits_{0}^{\infty}\frac{1}{(1+x^{\alpha})^{2}}-\frac{\mathbbm{1}_{r\geq\frac{1}{2}}2C_{z}A^{n}_{q}n^{-\gamma\alpha}-\mathbbm{1}_{r\geq
1}C_{z}^{2}B^{n}_{q}n^{-2\gamma\alpha}}{\rho}$
$\displaystyle-n^{-2\gamma\alpha
r}\frac{C_{z}}{\rho}\Bigg{(}2\int\limits_{\Theta(r-\frac{1}{2})}^{\infty}\frac{x^{-1+\alpha(1-2r)}}{(1+C_{z}x^{\alpha})^{2}}+C_{z}\int\limits_{\Theta(r-1)}^{\infty}\frac{x^{-1+\alpha(2-2r)}}{(1+C_{z}x^{\alpha})^{2}}\Bigg{)}\Bigg{)}^{-1}$
$\displaystyle=1-\mathcal{O}\left(\frac{\hat{r}_{2}}{\rho\hat{r}_{1}^{2}}n^{\gamma-1}\right)+\mathbbm{1}_{r\geq
1}\mathcal{O}\left(n^{-2\gamma\alpha}\right)+\mathcal{O}\left(n^{-2\gamma\alpha
r}\right),$ (40)

where we used $A^{\infty}_{q}=A^{\infty}_{m}$, meaning the leading order of
the $n^{-\alpha\gamma}$ term cancels out. The scaling of the other order
parameters $q,m,\hat{r}_{1},\hat{r}_{2}$ can at this point also be deduced. To
see how, notice that

$\displaystyle\int\limits_{-\infty}^{\frac{1}{\sqrt{q}}}dx\frac{e^{-\frac{1}{2}x^{2}}}{\sqrt{2\pi}}\left[1+\mathrm{erf}(\sqrt{\frac{\eta}{2(1-\eta)}}x)\right]\approx\frac{1}{\sqrt{q}}\int\limits_{-\infty}^{1}dx\frac{e^{-\frac{x^{2}}{2q}}}{\sqrt{2\pi}}\left[1+\mathrm{erf}(\sqrt{\frac{\eta}{2q(1-\eta)}}x)\right]\sim\frac{1}{\sqrt{q}},$
(41)

which together with the observation (32) implies

$q\sim\hat{r}_{1}^{2}\sim n^{2(1-\gamma)}.$ (42)

In parallel, it follows from a similar change of variables in the expression
of $\hat{r}_{2}$ that

$\hat{r}_{2}\sim\sqrt{q}\sim\hat{r}_{1}\sim n^{1-\gamma}.$ (43)

Then, returning to (A.3),

$1-\eta=\mathcal{O}\left(n^{2(\gamma-1)}\right)+\mathbbm{1}_{r\geq
1}\mathcal{O}\left(n^{-2\gamma\alpha}\right)+\mathcal{O}\left(n^{-2\gamma\alpha
r}\right).$ (44)

The final step is to determine the value of $\gamma$. Suppose self-
consistently that the leading rate in (A.3) is $2(\gamma-1)$. Since from the
physical meaning of the order parameters (11) one expects the leading
corrections of $m$ and $q$ to share the same decay rate  – since in (11), only
$\hat{w}$ admits a correction with $n$ –, and since the leading corrections of
$m$ has rate $-2\gamma\alpha\mathrm{min}(r,1/2)$ (A.3), it follows from
equating the two rates that $\gamma$ should be

$\gamma=\frac{1}{1+\alpha\mathrm{min}(r,\frac{1}{2})}.$ (45)

Plugging the expression (45) back in (A.3), it can be checked that the
$2(\gamma-1)$ term is indeed leading. (45) compares very well with numerical
simulations, and with the numerical solution of (29), see Fig. 1.

Assuming (45) to be true, since
$\epsilon_{g}=\mathrm{cos}^{-1}(\eta)\sim\sqrt{1-\eta}$,

$\epsilon_{g}\sim
n^{-\gamma\alpha\mathrm{min}(r,\frac{1}{2})}=n^{-\frac{\alpha\mathrm{min}(r,\frac{1}{2})}{1+\alpha\mathrm{min}(r,\frac{1}{2})}},$
(46)

which is the error rate for max-margin classification (15).

##  Appendix B Rates for regularized hinge classification

In this Appendix, we show that margin-maximizing SVM is optimal for
classifying teachers with source $r\leq\frac{1}{2}$, i.e. in
$L^{2}(\mathcal{X})\setminus\mathcal{H}$, and argue why this is also expected
to extend to teachers in $\mathcal{H}$. In other words, we give evidence that
the optimal regularization in the hinge classification risk (12) on the
dataset (8) is for vanishing $\lambda=0$. To this end, we derive the rates for
the misclassification error of ERM on (12) for generic regularization
$\lambda$, building upon the results of [28] in similar fashion to Appendix A.

###  B.1 Regularized hinge classification under source and capacity conditions

We remind the fixed point equations for the risk (12) (see Appendix A):

$\displaystyle\begin{cases}m=\hat{m}p~{}\mathrm{tr}\frac{\Sigma\theta^{\star}\theta^{\star\top}\Sigma}{\frac{n\lambda}{2}+p\hat{V}\Sigma}\\\
q=p~{}\mathrm{tr}\frac{p\hat{m}^{2}\Sigma\theta^{\star}\theta^{\star\top}\Sigma^{2}+\hat{q}\Sigma^{2}}{(\frac{n\lambda}{2}+p\hat{V}\Sigma)^{2}}\\\
V=\mathrm{tr}\frac{\Sigma}{\frac{n\lambda}{2}+p\hat{V}\Sigma}\\\ \end{cases},$
$\displaystyle\begin{cases}\begin{aligned}
\hat{m}&=\frac{\frac{n}{p}}{V\sqrt{\rho}}\frac{1}{2\pi}\Bigg{\\{}\sqrt{2\pi}\left[\mathrm{erf}\left(\frac{1}{\sqrt{2q(1-\eta)}}\right)-\mathrm{erf}\left(\frac{1-V}{\sqrt{2q(1-\eta)}}\right)\right]\\\
&+2\sqrt{q(1-\eta)}\left(e^{-\frac{1}{2q(1-\eta)}}-e^{-\frac{(1-V)^{2}}{2q(1-\eta)}}\right)+\sqrt{2\pi}V\left(1+\mathrm{erf}\left(\frac{1-V}{\sqrt{2q(1-\eta)}}\right)\right)\Bigg{\\}}\end{aligned}\\\
\hat{q}=\frac{n}{p}\Bigg{[}\int\limits_{-\infty}^{\frac{1-V}{\sqrt{q}}}dx\frac{e^{-\frac{1}{2}x^{2}}}{\sqrt{2\pi}}\left[1+\mathrm{erf}(\sqrt{\frac{\eta}{2(1-\eta)}}x)\right]+\frac{1}{V^{2}}\int\limits_{\frac{1-V}{\sqrt{q}}}^{\frac{1}{\sqrt{q}}}dx\frac{e^{-\frac{1}{2}x^{2}}}{\sqrt{2\pi}}\left[1+\mathrm{erf}(\sqrt{\frac{\eta}{2(1-\eta)}}x)\right](1-\sqrt{q}x)^{2}\Bigg{]}\\\
\hat{V}=\frac{\frac{n}{p}}{V}\int\limits_{\frac{1-V}{\sqrt{q}}}^{\frac{1}{\sqrt{q}}}dx\frac{e^{-\frac{1}{2}x^{2}}}{\sqrt{2\pi}}\left[1+\mathrm{erf}(\sqrt{\frac{\eta}{2(1-\eta)}}x)\right]\end{cases}.$

Introducing the effective regularization $z=\frac{\alpha n\lambda}{2\hat{V}}$,
satisfying

$z=\frac{\frac{z}{n}\sum\limits_{k=1}^{\infty}\frac{\lambda_{k}}{\frac{z}{n}+\lambda_{k}}}{\int\limits_{\frac{1-V}{\sqrt{q}}}^{\frac{1}{\sqrt{q}}}dx\frac{e^{-\frac{1}{2}x^{2}}}{\sqrt{2\pi}}\left[1+\mathrm{erf}(\sqrt{\frac{\eta}{2(1-\eta)}}x)\right]}\approx\frac{\left(\frac{z}{n}\right)^{1-\frac{1}{\alpha}}\int_{\left(\frac{z}{n}\right)^{\frac{1}{\alpha}}}^{\infty}\frac{dx}{1+x^{\alpha}}}{\int\limits_{\frac{1-V}{\sqrt{q}}}^{\frac{1}{\sqrt{q}}}dx\frac{e^{-\frac{1}{2}x^{2}}}{\sqrt{2\pi}}\left[1+\mathrm{erf}(\sqrt{\frac{\eta}{2(1-\eta)}}x)\right]},$
(48)

the equations (LABEL:eq:app:reg:loureiro_g3m_reg) can be rewritten as

$\displaystyle\begin{cases}\rho=\sum\limits_{k=1}^{\infty}\theta_{k}^{2}\lambda_{k}\\\
m=\hat{r}_{1}\frac{n}{z}\sum\limits_{k=1}^{\infty}\frac{\lambda_{k}^{2}\theta_{k}^{2}}{1+\frac{n}{z}\lambda_{k}}\\\
q=\frac{n^{2}}{z^{2}}\sum\limits_{k=1}^{\infty}\frac{\hat{r}_{1}^{2}\theta_{k}^{2}\lambda_{k}^{3}+\frac{1}{n}\hat{r}_{2}\lambda_{k}^{2}}{(1+\frac{n}{z}\lambda_{k})^{2}}\\\
V=\frac{1}{n\lambda}\sum\limits_{k=1}^{d}\frac{\lambda_{k}}{1+\frac{n}{z}\lambda_{k}}\\\
\end{cases}$ (49)
$\displaystyle\begin{cases}\hat{r}_{1}=&\frac{\hat{m}}{\hat{V}}=\frac{1}{2\pi\sqrt{\rho}}\frac{\sqrt{2\pi}\left[\mathrm{erf}\left(\frac{1}{\sqrt{2q(1-\eta)}}\right)-\mathrm{erf}\left(\frac{1-V}{\sqrt{2q(1-\eta)}}\right)\right]}{\int\limits_{\frac{1-V}{\sqrt{q}}}^{\frac{1}{\sqrt{q}}}dx\frac{e^{-\frac{1}{2}x^{2}}}{\sqrt{2\pi}}\left[1+\mathrm{erf}(\sqrt{\frac{\eta}{2(1-\eta)}}x)\right]}\\\
&+\frac{1}{2\pi\sqrt{\rho}}\frac{2\sqrt{q(1-\eta)}\left(e^{-\frac{1}{2q(1-\eta)}}-e^{-\frac{(1-V)^{2}}{2q(1-\eta)}}\right)+\sqrt{2\pi}V\left(1+\mathrm{erf}\left(\frac{1-V}{\sqrt{2q(1-\eta)}}\right)\right)}{\int\limits_{\frac{1-V}{\sqrt{q}}}^{\frac{1}{\sqrt{q}}}dx\frac{e^{-\frac{1}{2}x^{2}}}{\sqrt{2\pi}}\left[1+\mathrm{erf}(\sqrt{\frac{\eta}{2(1-\eta)}}x)\right]}\\\
\hat{r}_{2}=&\frac{\alpha\hat{q}}{\hat{V}^{2}}=\frac{V^{2}\int\limits_{-\infty}^{\frac{1-V}{\sqrt{q}}}dx\frac{e^{-\frac{1}{2}x^{2}}}{\sqrt{2\pi}}\left[1+\mathrm{erf}(\sqrt{\frac{\eta}{2(1-\eta)}}x)\right]+\int\limits_{\frac{1-V}{\sqrt{q}}}^{\frac{1}{\sqrt{q}}}dx\frac{e^{-\frac{1}{2}x^{2}}}{\sqrt{2\pi}}\left[1+\mathrm{erf}(\sqrt{\frac{\eta}{2(1-\eta)}}x)\right](1-\sqrt{q}x)^{2}}{\left(\int\limits_{\frac{1-V}{\sqrt{q}}}^{\frac{1}{\sqrt{q}}}dx\frac{e^{-\frac{1}{2}x^{2}}}{\sqrt{2\pi}}\left[1+\mathrm{erf}(\sqrt{\frac{\eta}{2(1-\eta)}}x)\right]\right)^{2}}\\\
\end{cases}.$

Specializing to the source/capacity power-law forms (8)

$\displaystyle\omega_{k}\sim k^{-\alpha},$ $\displaystyle\theta_{k}\sim
k^{-\frac{1+\alpha(2r-1)}{2}},$ (50)

one finally reaches

$\displaystyle\begin{cases}\rho=\sum\limits_{k=1}^{\infty}k^{-1-2\alpha r}\\\
m=\hat{r}_{1}\sum\limits_{k=1}^{\infty}\frac{k^{-1-2\alpha
r}}{1+\frac{z}{n}k^{\alpha}}\\\
q=\hat{r}_{1}^{2}\sum\limits_{k=1}^{\infty}\frac{k^{-1-2\alpha
r}}{(1+\frac{z}{n}k^{\alpha})^{2}}+\frac{\hat{r}_{2}}{n}\sum\limits_{k=1}^{\infty}\frac{1}{(1+\frac{z}{n}k^{\alpha})^{2}}\\\
V=\frac{1}{n\lambda}\frac{z}{n}\sum\limits_{k=1}^{\infty}\frac{1}{1+\frac{z}{n}k^{\alpha}}\end{cases}$
(51)
$\displaystyle\begin{cases}\hat{r}_{1}=&\frac{\hat{m}}{\hat{V}}=\frac{1}{2\pi\sqrt{\rho}}\frac{\sqrt{2\pi}\left[\mathrm{erf}\left(\frac{1}{\sqrt{2q(1-\eta)}}\right)-\mathrm{erf}\left(\frac{1-V}{\sqrt{2q(1-\eta)}}\right)\right]}{\int\limits_{\frac{1-V}{\sqrt{q}}}^{\frac{1}{\sqrt{q}}}dx\frac{e^{-\frac{1}{2}x^{2}}}{\sqrt{2\pi}}\left[1+\mathrm{erf}(\sqrt{\frac{\eta}{2(1-\eta)}}x)\right]}\\\
&+\frac{1}{2\pi\sqrt{\rho}}\frac{2\sqrt{q(1-\eta)}\left(e^{-\frac{1}{2q(1-\eta)}}-e^{-\frac{(1-V)^{2}}{2q(1-\eta)}}\right)+\sqrt{2\pi}V\left(1+\mathrm{erf}\left(\frac{1-V}{\sqrt{2q(1-\eta)}}\right)\right)}{\int\limits_{\frac{1-V}{\sqrt{q}}}^{\frac{1}{\sqrt{q}}}dx\frac{e^{-\frac{1}{2}x^{2}}}{\sqrt{2\pi}}\left[1+\mathrm{erf}(\sqrt{\frac{\eta}{2(1-\eta)}}x)\right]}\\\
\hat{r}_{2}=&\frac{\alpha\hat{q}}{\hat{V}^{2}}=\frac{V^{2}\int\limits_{-\infty}^{\frac{1-V}{\sqrt{q}}}dx\frac{e^{-\frac{1}{2}x^{2}}}{\sqrt{2\pi}}\left[1+\mathrm{erf}(\sqrt{\frac{\eta}{2(1-\eta)}}x)\right]+\int\limits_{\frac{1-V}{\sqrt{q}}}^{\frac{1}{\sqrt{q}}}dx\frac{e^{-\frac{1}{2}x^{2}}}{\sqrt{2\pi}}\left[1+\mathrm{erf}(\sqrt{\frac{\eta}{2(1-\eta)}}x)\right](1-\sqrt{q}x)^{2}}{\left(\int\limits_{\frac{1-V}{\sqrt{q}}}^{\frac{1}{\sqrt{q}}}dx\frac{e^{-\frac{1}{2}x^{2}}}{\sqrt{2\pi}}\left[1+\mathrm{erf}(\sqrt{\frac{\eta}{2(1-\eta)}}x)\right]\right)^{2}}\\\
\end{cases}$ (52)

###  B.2 Rate analysis for targets outside the Hilbert space

In the following, we deliver an asymptotic analysis of eqs. (52). To that end,
we first ascertain the scaling of the effective regularization $z$ using the
self-consistent equation (48). Depending on the scaling of the order parameter
$V$, two regimes can be distinguished.

#### Effectively regularized regime
$V\xrightarrow[]{n\rightarrow\infty}\infty$

In this regime the denominator of (48) scales like

$\displaystyle\int\limits_{\frac{1-V}{\sqrt{q}}}^{\frac{1}{\sqrt{q}}}dx\frac{e^{-\frac{1}{2}x^{2}}}{\sqrt{2\pi}}\left[1+\mathrm{erf}(\sqrt{\frac{\eta}{2(1-\eta)}}x)\right]$
$\displaystyle\approx\frac{1}{\sqrt{q}}\int\limits_{-\infty}^{1}dx\frac{e^{-\frac{1}{2q}x^{2}}}{\sqrt{2\pi}}\left[1+\mathrm{erf}(\sqrt{\frac{\eta}{2q(1-\eta)}}x)\right]=\mathcal{O}\left(\frac{1}{\sqrt{q}}\right),$
(53)

which is exactly the scaling for the corresponding integral in the vanishing
regularization case $\lambda=0^{+}$, see Appendix A eq. (32). In this regime,
all the discussion in Appendix A then carries through and the error rate
coincides with the one for margin-maximizing SVM (15)

$\epsilon_{g}\sim
n^{-\frac{\alpha\mathrm{min}(r,\frac{1}{2})}{1+\alpha\mathrm{min}(r,\frac{1}{2})}}.$
(54)

#### Effectively regularized regime $V\xrightarrow[]{n\rightarrow\infty}0$

The integral in the denominator in (48) then admits the following scaling

$\displaystyle\int\limits_{\frac{1-V}{\sqrt{q}}}^{\frac{1}{\sqrt{q}}}dx\frac{e^{-\frac{1}{2}x^{2}}}{\sqrt{2\pi}}\left[1+\mathrm{erf}(\sqrt{\frac{\eta}{2(1-\eta)}}x)\right]$
$\displaystyle=\frac{1}{\sqrt{q}}\int\limits_{1-V}^{1}dx\frac{e^{-\frac{1}{2q}x^{2}}}{\sqrt{2\pi}}\left[1+\mathrm{erf}(\sqrt{\frac{\eta}{2q(1-\eta)}}x)\right]=\mathcal{O}\left(\frac{V}{\sqrt{q}}\right).$
(55)

This means in particular that

$z=\frac{Vn\lambda}{\int\limits_{\frac{1-V}{\sqrt{q}}}^{\frac{1}{\sqrt{q}}}dx\frac{e^{-\frac{1}{2}x^{2}}}{\sqrt{2\pi}}\left[1+\mathrm{erf}(\sqrt{\frac{\eta}{2(1-\eta)}}x)\right]}=\mathcal{O}(n\lambda\sqrt{q})\overset{\mathrm{def}}{\sim}C_{z}n^{1-\alpha\gamma},$
(56)

where we introduced similarly to the max-margin case the to-be determined
parameter $\gamma$, see also Appendix A. Note that it follows from equation
(56) and the definition of $\lambda=n^{-\ell}$ that

$q\sim n^{2(\ell-\alpha\gamma)}.$ (57)

Since $n\lambda V\sim(z/n)^{1-\frac{1}{\alpha}}$, one also has that

$V\sim n^{-1+\gamma(1-\alpha)+\ell}.$ (58)

In particular, it can be seen from (58) that the assumption
$V\xrightarrow[]{n\rightarrow\infty}0$ only holds for large enough
regularizations (slow enough decays $\ell<\ell^{\star}$ for some limiting
value $\ell^{\star}$), satisfying

$-1+\gamma(1-\alpha)+\ell<0.$ (59)

The regularization decay $\ell=\ell^{\star}$ gives the boundary between the
effectively regularized and unregularized regime. Because of this, the rate of
$q$ at $\ell^{\star}$ should coincide with its max-margin rate (14). This,
together with (59), allow to determine $\ell^{\star}$ as the solution of the
system (denoting $\gamma^{\star}$ the value of $\gamma$ at
$\ell=\ell^{\star}$)

$\displaystyle\begin{cases}&-1+\gamma^{\star}(1-\alpha)+\ell=0,\\\
&\ell^{\star}-\alpha\gamma^{\star}=\frac{\alpha\mathrm{min}(r,\frac{1}{2})}{1+\alpha\mathrm{min}(r,\frac{1}{2})},\end{cases}$
(60)

viz.

$\ell^{\star}=\alpha\frac{1+\mathrm{min}(r,\frac{1}{2})}{1+\alpha\mathrm{min}(r,\frac{1}{2})}.$
(61)

Summarizing, for $\ell>\ell^{\star}$, in the effectively unregularized regime,
the max-margin scalings (14), (15) hold. In the following, we focus on
pursuing the discussion for the new $\ell<\ell^{\star}$ (effectively
regularized) regime.

Figure 5: Misclassification error $\epsilon_{g}$ for hinge classification on
synthetic Gaussian data, as specified in (8), for different source/capacity
coefficients $\alpha,r$, for a regularization $\lambda=n^{-\ell}$. In blue,
the solution of the closed set of equations
(LABEL:eq:app:reg:loureiro_g3m_reg) used in the characterization (9) for the
misclassification error, using the g3m package [28]. The dimension $p$ was
cut-off at $10^{4}$. Red dots corresponds to simulations using the scikit-
learn SVC package and averaged over $40$ instances, for $p=10^{4}$. The green
dashed line indicates the power-law rate (67) derived in this work.

The expansion for $m$ and $q$ carry over in similar fashion to max-margin (see
Appendix A), yielding

$\begin{cases}m=\hat{r}_{1}\left[\rho-\mathbbm{1}_{r\geq\frac{1}{2}}C_{z}A^{n}_{m}n^{-\gamma\alpha}-C_{z}n^{-2\gamma\alpha
r}\int\limits_{\Theta(r-\frac{1}{2})}^{\infty}\frac{x^{-1+\alpha(1-2r)}}{1+C_{z}x^{\alpha}}\right]+o\left(\mathrm{max}\left(n^{-\gamma\alpha},n^{-2\gamma\alpha
r}\right)\right),\\\ \begin{aligned}
q&=\hat{r}_{1}^{2}\Bigg{[}\rho+\frac{\hat{r}_{2}}{\hat{r}_{1}^{2}}n^{\gamma-1}\int\limits_{0}^{\infty}\frac{1}{(1+C_{z}x^{\alpha})^{2}}-\mathbbm{1}_{r\geq\frac{1}{2}}2C_{z}A^{n}_{q}n^{-\gamma\alpha}-\mathbbm{1}_{r\geq
1}C_{z}^{2}B^{n}_{q}n^{-2\gamma\alpha}\\\ &~{}~{}-n^{-2\gamma\alpha
r}\Bigg{(}2C_{z}\int\limits_{\Theta(r-\frac{1}{2})}^{\infty}\frac{x^{-1+\alpha(1-2r)}}{(1+C_{z}x^{\alpha})^{2}}+C_{z}^{2}\int\limits_{\Theta(r-1)}^{\infty}\frac{x^{-1+\alpha(2-2r)}}{(1+C_{z}x^{\alpha})^{2}}\Bigg{)}\Bigg{]}\\\
&~{}~{}+o\left(\mathrm{max}\left(\frac{\hat{r}_{2}}{\hat{r}_{1}^{2}}n^{\gamma-1},n^{-\gamma\alpha},n^{-2\gamma\alpha
r}\right)\right).\end{aligned}\end{cases}$ (62)

Therefore $\hat{r}_{1}\sim\sqrt{q}\sim n^{\ell-\alpha\gamma}$, while a
rescaling of the integrals in the equations for $\hat{r}_{2}$ also reveal that
$\hat{r}_{2}\sim\hat{r}_{1}\sim\sqrt{q}\sim n^{\ell-\alpha\gamma}$.
Summarizing

$m\sim\hat{r}_{2}\sim\hat{r}_{1}\sim\sqrt{q}\sim n^{\ell-\alpha\gamma}.$ (63)

Note that the mutual scaling of the order parameters $m,q,\hat{r}_{1}$ is the
same as for max-margin classification (14), which is the mutual scaling
directly following from the physical interpretation of $m,q$ as
$\langle\hat{w},\theta^{\star}\rangle_{L^{2}(\mathcal{X})},\,||\hat{w}||^{2}_{L^{2}(\mathcal{X})}$
and of $\hat{r}_{1}$ as
$||\hat{w}||^{2}_{L^{2}(\mathcal{X})}/||\theta^{\star}||^{2}_{L^{2}(\mathcal{X})}$,
see also discussion in section II under equation (11). Finally,

$\displaystyle\eta$
$\displaystyle=\Bigg{(}1-\mathbbm{1}_{r\geq\frac{1}{2}}C_{z}\frac{A^{n}_{m}}{\rho}n^{-\gamma\alpha}-n^{-2\gamma\alpha
r}\frac{C_{z}}{\rho}\int\limits_{\Theta(r-\frac{1}{2})}^{\infty}\frac{x^{-1+\alpha(1-2r)}}{1+C_{z}x^{\alpha}}\Bigg{)}^{2}\Bigg{/}\Bigg{(}1+$
$\displaystyle~{}~{}\frac{\hat{r}_{2}}{\rho\hat{r}_{1}^{2}}n^{\gamma-1}\int\limits_{0}^{\infty}\frac{1}{(1+x^{\alpha})^{2}}-\frac{\mathbbm{1}_{r\geq\frac{1}{2}}2C_{z}A^{n}_{q}n^{-\gamma\alpha}-\mathbbm{1}_{r\geq
1}C_{z}^{2}B^{n}_{q}n^{-2\gamma\alpha}}{\rho}$
$\displaystyle~{}~{}-n^{-2\gamma\alpha
r}\frac{C_{z}}{\rho}\Bigg{(}2\int\limits_{\Theta(r-\frac{1}{2})}^{\infty}\frac{x^{-1+\alpha(1-2r)}}{(1+C_{z}x^{\alpha})^{2}}+C_{z}\int\limits_{\Theta(r-1)}^{\infty}\frac{x^{-1+\alpha(2-2r)}}{(1+C_{z}x^{\alpha})^{2}}\Bigg{)}\Bigg{)}^{-1}$
$\displaystyle=1-\mathcal{O}\left(\frac{\hat{r}_{2}}{\rho\hat{r}_{1}^{2}}n^{\gamma-1}\right)+\mathbbm{1}_{r\geq
1}\mathcal{O}\left(n^{-2\gamma\alpha}\right)+\mathcal{O}\left(n^{-2\gamma\alpha
r}\right)$
$\displaystyle=1-\mathcal{O}\left(n^{\gamma(\alpha+1)-1-\ell}\right)+\mathcal{O}\left(n^{-2\alpha\gamma
r}\right),$ (64)

where we specialized to $r\leq\frac{1}{2}$ in the last line, thereby focusing
on target functions $f^{\star}\in L^{2}(\mathcal{X})\setminus\mathcal{H}$. At
this point, it remains to heuristically determine $\gamma$, a rigorous
analytical derivation of our results being left for future work. Making the
two (numerically verified) assumptions

######  Assumption B.1.

Like the max-margin case, $1-\eta\sim q^{-1}$,

######  Assumption B.2.

The term of rate $2\alpha\gamma r$ dominates in (B.2).

$\gamma$ can be guessed as

$\gamma=\frac{\ell}{\alpha\left(1+r\right)}.$ (65)

Note that consistently, the value of $\gamma$ at the boundary
$\ell=\ell^{\star}$ with the unregularized regime $\gamma^{\star}$ coincides
with its max-margin value (45). In the effectively regularized regime, under
these assumptions, we thus conjecture the error to scale for
$r\leq\frac{1}{2}$ as

$\epsilon_{g}\sim\sqrt{1-\eta}\sim n^{\alpha\gamma-\ell}\sim
n^{-\ell\frac{r}{1+r}}.$ (66)

Finally observe that the rates for the effectively unregularized regime
$\ell\geq\ell^{\star}$ (54) and regularized regime $\ell\leq\ell^{\star}$ (66)
can be subsumed in the more compact form, still for $r\leq\frac{1}{2}$:

$\epsilon_{g}\sim
n^{-\mathrm{min}(\ell,\ell^{\star})\frac{r}{1+r}}=n^{-\mathrm{min}\left(\ell,\alpha\frac{1+r}{1+\alpha
r}\right)\frac{r}{1+r}}.$ (67)

Fig. 5 contrasts the rates (67) to the numerical solution of the equations
(LABEL:eq:app:reg:loureiro_g3m_reg) and to numerical simulations, and displays
a very good agreement. The main conclusion from (67) is that for any $\ell$,
the rate is necessarily slower than $\ell^{\star}r/(1+r)=\alpha r/(1+\alpha
r)$, which is the max-margin rate (15). Therefore, the max-margin rate (15) is
optimal for $r\leq\frac{1}{2}$, and is achieved for any regularization
$\lambda$ decaying at least as fast as $n^{-\ell^{\star}}$. In particular, it
is achieved for the limit case $\ell=\infty$, i.e. $\lambda=0^{+}$ a.k.a. the
max-margin case, thereby suggesting that no regularization is optimal for
rough enough target functions $f^{\star}\in
L^{2}(\mathcal{X})\setminus\mathcal{H}$. Since regularization is not needed
for hard teachers (small source $r$), we do not a fortiori expect it to help
for easier, smoother teachers $f^{\star}\in\mathcal{H}$ characterized by
source $r\geq\frac{1}{2}$. This suggests that $\lambda=0^{+}$ (max-margin)
should be optimal for all sources $r$, i.e. any target $f^{\star}\in
L^{2}(\mathcal{X})$. While this conjecture is observed to hold in numerical
simulations, a more thorough theoretical analysis of the error rates for
$r\geq\frac{1}{2}$ is nevertheless warranted. We leave this more challenging
analysis to future work.

##  Appendix C Rates for ridge classification

In this section we derive the rates (18) for ridge classifiers.

###  C.1 Ridge classification under the source and capacity conditions

The equations on $m,\,q$ for ridge classification [28] can as in Appendix A be
adapted to the $p=\infty,\,n\gg 1$ limit as

$\displaystyle\begin{cases}m=\hat{m}p~{}\mathrm{tr}\frac{\Sigma\theta^{\star}\theta^{\star\top}\Sigma}{n\lambda+p\hat{V}\Sigma}\\\
q=p~{}\mathrm{tr}\frac{p\hat{m}^{2}\Sigma\theta^{\star}\theta^{\star\top}\Sigma^{2}+\hat{q}\Sigma^{2}}{(n\lambda+p\hat{V}\Sigma)^{2}}\\\
V=\mathrm{tr}\frac{\Sigma}{n\lambda+p\hat{V}\Sigma}\\\ \end{cases},$
$\displaystyle\begin{cases}&\hat{V}=\frac{\frac{n}{p}}{1+V}\\\
&\hat{q}=\frac{n}{p}\frac{1+q-2m\sqrt{\frac{2}{\pi\rho}}}{(1+V)^{2}}=\frac{\hat{V}^{2}}{\frac{n}{p}}\left(1+q-2m\sqrt{\frac{2}{\pi\rho}}\right)\\\
&\hat{m}=\sqrt{\frac{2}{\pi\rho}}\frac{\frac{n}{p}}{1+V}=\sqrt{\frac{2}{\pi\rho}}\hat{V}.\end{cases}$
(68)

Following [15], we introduce the effective regularization $z$

$\displaystyle
z=\frac{\frac{n}{p}n\lambda}{\hat{V}}=n\lambda+\frac{z}{n}\sum\limits_{k=1}^{\infty}\frac{\lambda_{k}}{\lambda_{k}+\frac{z}{n}}\approx
n\lambda+\left(\frac{z}{n}\right)^{1-\frac{1}{\alpha}}\int\limits_{\left(\frac{z}{n}\right)^{\frac{1}{\alpha}}}^{\infty}\frac{dx}{1+x^{\alpha}}.$
(69)

Like in Appendix A, we denote $z\sim C_{z}n^{1-\alpha\gamma}$ the scaling of
$z$. In contrast to Appendices A and B for SVM, the exponent $\gamma$ for
ridge classifier can be straightforwardly determined. Depending on the
relative strength of the two terms in (69), two possible values for $\gamma$
exist:

  * •

$\gamma=\frac{\ell}{\alpha}$ if $n\lambda\gg(z/n)^{1-1/\alpha}$ in (69), i.e.
$\ell<\alpha$. This correspond to the effectively regularized regime [15].

  * •

$\gamma=1$ if $n\lambda\ll(z/n)^{1-1/\alpha}$ in (69), i.e. $\ell>\alpha$. In
this regime, the regularization $\lambda$ is negligible and therefore the
learning is effectively un-regularized [15].

Rewriting the equations (68) using (69), the equations (17) of the main text
are reached (see section IV):

$\displaystyle\begin{cases}&\rho=\sum\limits_{k=1}^{\infty}k^{-1-2\alpha r}\\\
&m=\sqrt{\frac{2}{\pi\rho}}\sum\limits_{k=1}^{\infty}\frac{k^{-1-2\alpha
r}}{1+\frac{z}{n}k^{\alpha}}\\\
&q=\frac{2}{\pi\rho}\sum\limits_{k=1}^{\infty}\frac{k^{-1-2\alpha
r}}{\left(1+\frac{z}{n}k^{\alpha}\right)^{2}}+\frac{1+q-2m\sqrt{\frac{2}{\pi\rho}}}{n}\sum\limits_{k=1}^{\infty}\frac{1}{\left(1+\frac{z}{n}k^{\alpha}\right)^{2}}\\\
&V=\frac{z}{n^{2}\lambda}\sum\limits_{k=1}^{\infty}\frac{1}{1+\frac{z}{n}k^{\alpha}}\end{cases}.$
(70)

###  C.2 Scaling analysis

We proceed to deliver an scaling analysis of eqs. (17). We know from Appendix
A the following scalings

$\begin{cases}m=\sqrt{\frac{2}{\pi\rho}}\left[\rho-\mathbbm{1}_{r\geq\frac{1}{2}}C_{z}A^{n}_{m}n^{-\gamma\alpha}-n^{-2\gamma\alpha
r}C_{z}\int\limits_{\Theta(r-\frac{1}{2})}^{\infty}\frac{x^{-1+\alpha(1-2r)}}{1+C_{z}x^{\alpha}}\right]+o\left(\mathrm{max}\left(n^{-\gamma\alpha},n^{-2\gamma\alpha
r}\right)\right),\\\ \begin{aligned}
q&=\frac{2}{\pi\rho}\Bigg{[}\rho+\frac{\pi\rho
C_{z}}{2}\left(1+q-2m\sqrt{\frac{2}{\pi\rho}}\right)n^{\gamma-1}\int\limits_{0}^{\infty}\frac{1}{(1+C_{z}x^{\alpha})^{2}}-\mathbbm{1}_{r\geq\frac{1}{2}}2C_{z}A^{n}_{q}n^{-\gamma\alpha}-\mathbbm{1}_{r\geq
1}C_{z}^{2}B^{n}_{q}n^{-2\gamma\alpha}\\\ &~{}~{}-n^{-2\gamma\alpha
r}\Bigg{(}2C_{z}\int\limits_{\Theta(r-\frac{1}{2})}^{\infty}\frac{x^{-1+\alpha(1-2r)}}{(1+C_{z}x^{\alpha})^{2}}+C_{z}^{2}\int\limits_{\Theta(r-1)}^{\infty}\frac{x^{-1+\alpha(2-2r)}}{(1+C_{z}x^{\alpha})^{2}}\Bigg{)}\Bigg{]}\\\
&~{}~{}+o\left(\mathrm{max}\left(\frac{\hat{r}_{2}}{\hat{r}_{1}^{2}}n^{\gamma-1},n^{-\gamma\alpha},n^{-2\gamma\alpha
r}\right)\right).\end{aligned}\end{cases}$ (71)

Once again, we defined the shorthands

$\displaystyle
A_{m}^{n}\overset{\mathrm{def}}{=}\sum\limits_{k=1}^{n^{\gamma}}\frac{k^{-1-2\alpha(r-\frac{1}{2})}}{1+C_{z}\left(\frac{k}{n^{\gamma}}\right)^{\alpha}},$
$\displaystyle
A_{q}^{n}\overset{\mathrm{def}}{=}\sum\limits_{k=1}^{n^{\gamma}}\frac{k^{-1-2\alpha(r-\frac{1}{2})}}{\left(1+C_{z}\left(\frac{k}{n^{\gamma}}\right)^{\alpha}\right)^{2}},$
$\displaystyle
B^{n}_{q}\overset{\mathrm{def}}{=}\sum\limits_{k=1}^{n^{\gamma}}\frac{k^{-1-2\alpha(r-1)}}{\left(1+C_{z}\left(\frac{k}{n^{\gamma}}\right)^{\alpha}\right)^{2}}.$
(72)

We remind that, similarly to the discussion in Appendix A, the sequences
$A^{n}_{m}$ and $A^{n}_{q}$ admit identical limits as $n\rightarrow\infty$ :
$A^{\infty}_{q}=A^{\infty}_{m}$. The consequences of this identity are
expounded below. We now focus on ascertaining the scalings of the order
parameters $m,\,q$. These scalings depend on the regime considered.

#### Regularized regime $\ell<\alpha$

In the case $\ell<\alpha$, we have $\gamma=\ell/\alpha<1$. Then the expansion
for $q$ reads

$q(1-o(1))=\frac{2}{\pi\rho}\left(\rho-\mathbbm{1}_{r\geq\frac{1}{2}}2C_{z}A^{n}_{q}n^{-\ell}\right)-\mathcal{O}\left(n^{-2\ell\mathrm{min}(r,1)}\right)-\frac{4-\pi}{\pi}C_{z}n^{-\frac{\alpha-\ell}{\alpha}}\int\limits_{0}^{\infty}\frac{1}{(1+C_{z}x^{\alpha})^{2}},$
(73)

from which it follows that

$q=\frac{2}{\pi\rho}\left(\rho-\mathbbm{1}_{r\geq\frac{1}{2}}2C_{z}A^{n}_{q}n^{-\ell}\right)-\mathcal{O}\left(n^{-\mathrm{min}\left(2\ell\mathrm{min}(r,1),\frac{\alpha-\ell}{\alpha}\right)}\right).$
(74)

Therefore the cosine similarity $\eta$ admits the following expression

$\eta=\frac{m^{2}}{\rho
q}=\frac{\frac{2}{\pi\rho}\rho^{2}\left[1-\mathbbm{1}_{r\geq\frac{1}{2}}\frac{C_{z}A^{n}_{m}}{\rho}n^{-\ell}+\mathcal{O}\left(n^{-2\ell
r}\right)\right]^{2}}{\frac{2}{\pi\rho}\rho^{2}\left[1-\mathbbm{1}_{r\geq\frac{1}{2}}\frac{2C_{z}A^{n}_{q}}{\rho}n^{-\ell}-\mathcal{O}\left(n^{-\mathrm{min}\left(2\ell\mathrm{min}(r,1),\frac{\alpha-\ell}{\alpha}\right)}\right)\right]}=1-\mathcal{O}\left(n^{-\mathrm{min}\left(2\ell\mathrm{min}(r,1),\frac{\alpha-\ell}{\alpha}\right)}\right),$
(75)

where we used that $A^{n}_{q}$ and $A^{n}_{m}$ share the same limit. Finally,
the scaling for the misclassification error can be accessed:

$\displaystyle\epsilon_{g}\sim\sqrt{1-\eta}\sim
n^{-\frac{1}{2}\mathrm{min}\left(2\ell\mathrm{min}(r,1),\frac{\alpha-\ell}{\alpha}\right)},$
(76)

which is equation (18).

######  Remark C.1.

Note that only the classification error (9) tends to zero, while neither the
MSE betwen the label $y=\mathrm{sign}({\theta^{\star\top}}\psi(x))$ and the
pre-activation linear predictor $\hat{w}^{\top}\psi(x)$ (below denoted
$\mathrm{MSE}_{1}$) nor the MSE between the teacher and student preactivations
$\theta^{\star\top}\psi(x)$, $\hat{w}^{\top}\psi(x)$ (below denoted
$\mathrm{MSE}_{2}$) tend to zero:

$\displaystyle\mathrm{MSE}_{1}=\mathbb{E}_{\psi(x)}\left(\mathrm{sign}({\theta^{\star\top}}\psi(x))-\hat{w}^{\top}\psi(x)\right)^{2}=1+q-2m\sqrt{\frac{2}{\pi\rho}}\xrightarrow[]{n\rightarrow\infty}1-\frac{2}{\pi},$
(77)
$\displaystyle\mathrm{MSE}_{2}=\mathbb{E}_{\psi(x)}\left(\theta^{\star\top}\psi(x)-\hat{w}^{\top}\psi(x)\right)^{2}=\rho+q-2m\xrightarrow[]{n\rightarrow\infty}\rho\left(1-\sqrt{\frac{2}{\pi\rho}}\right)^{2}.$
(78)

Note also the identity between the order parameter $\hat{r}_{2}$ and
$\mathrm{MSE}_{1}$: $\hat{r}_{2}=\mathrm{MSE}_{1}$, discussed in section IV in
the main text.

#### Unregularized regime $\ell>\alpha$

If $\ell>\alpha$, then $\gamma=1$ and

$q\left(1-C_{z}\int\limits_{0}^{\infty}\frac{1}{(1+C_{z}x^{\alpha})^{2}}\right)=\frac{2}{\pi}-\frac{4-\pi}{\pi}C_{z}\int\limits_{0}^{\infty}\frac{1}{(1+C_{z}x^{\alpha})^{2}}-\mathcal{O}\left(n^{-2\alpha\mathrm{min}(r,\frac{1}{2})}\right).$
(79)

Hence

$\eta=\frac{m^{2}}{\rho
q}\xrightarrow[]{n\rightarrow\infty}\frac{1-C_{z}\int\limits_{0}^{\infty}\frac{1}{(1+C_{z}x^{\alpha})^{2}}}{1-\frac{4-\pi}{2}C_{z}\int\limits_{0}^{\infty}\frac{1}{(1+C_{z}x^{\alpha})^{2}}}\neq
1.$ (80)

Since $\eta$ is now bounded away from $1$, the misclassification error
$\epsilon_{g}$ fails to go to $0$ asymptotically, and plateaus to a finite
value:

$\epsilon_{g}=\mathcal{O}(1),$ (81)

which is equation (19). This plateau is attributable to ridge classifiers
overfitting the binary labels, see Appendix D for further discussion.

###  C.3 Rates for noisy ridge classification

In this seubsection, we provide briefly the derivation of the optimal rate for
noisy ridge classification, defined by (92), which is plotted in Fig. 9 of the
main text. Introducing the noise (92) in the equations of [28] and mapping to
our setting along identical lines as Appendix A, the self-consistent equations
read

$\displaystyle\begin{cases}m=\hat{m}p~{}\mathrm{tr}\frac{\Sigma\theta^{\star}\theta^{\star\top}\Sigma}{n\lambda+p\hat{V}\Sigma}\\\
q=p\mathrm{tr}\frac{p\hat{m}^{2}\Sigma\theta^{\star}\theta^{\star\top}\Sigma^{2}+\hat{q}\Sigma^{2}}{(n\lambda+p\hat{V}\Sigma)^{2}}\\\
V=\mathrm{tr}\frac{\Sigma}{n\lambda+p\hat{V}\Sigma}\\\ \end{cases},$
$\displaystyle\begin{cases}&\hat{V}=\frac{\frac{n}{p}}{1+V}\\\
&\hat{q}=\frac{n}{p}\frac{1+q-2m\sqrt{\frac{2}{\pi(\rho+\sigma^{2})}}}{(1+V)^{2}}=\frac{\hat{V}^{2}}{\frac{n}{p}}\left(1+q-2m\sqrt{\frac{2}{\pi(\rho+\sigma^{2})}}\right)\\\
&\hat{m}=\sqrt{\frac{2}{\pi(\rho+\sigma^{2})}}\frac{\frac{n}{p}}{1+V}=\sqrt{\frac{2}{\pi(\rho+\sigma^{2})}}\hat{V}.\end{cases}$
(82)

This differs from (68) by a the replacement of $\rho$ by $\rho+\sigma^{2}$,
simply reflecting the fact that the teacher $L^{2}(\mathcal{X})$ squared norm
should now include the contribution of the additive noise.

In the regularized regime $\ell<\alpha$,the expression (75) for the cosine-
similarity $\eta$ becomes

$\eta=\frac{m^{2}}{\rho
q}=\frac{\frac{2}{\pi(\rho+\sigma^{2})}\rho^{2}\left[1-\mathbbm{1}_{r\geq\frac{1}{2}}\frac{C_{z}A^{n}_{m}}{\rho}n^{-\ell}+\mathcal{O}\left(n^{-2\ell
r}\right)\right]^{2}}{\frac{2}{\pi(\rho+\sigma^{2})}\rho^{2}\left[1-\mathbbm{1}_{r\geq\frac{1}{2}}\frac{2C_{z}A^{n}_{q}}{\rho}n^{-\ell}-\mathcal{O}\left(n^{-\mathrm{min}\left(2\ell\mathrm{min}(r,1),\frac{\alpha-\ell}{\alpha}\right)}\right)\right]}=1-\mathcal{O}\left(n^{-\mathrm{min}\left(2\ell\mathrm{min}(r,1),\frac{\alpha-\ell}{\alpha}\right)}\right).$
(83)

Therefore the excess error reads

$\displaystyle\epsilon_{g}-\epsilon_{g}^{\infty}$
$\displaystyle=\frac{1}{\pi}\mathrm{cos}^{-1}\left(\sqrt{\frac{\rho}{\rho+\sigma^{2}}\eta}\right)-\frac{1}{\pi}\mathrm{cos}^{-1}\left(\sqrt{\frac{\rho}{\rho+\sigma^{2}}}\right)$
$\displaystyle=\begin{cases}\frac{1}{\sqrt{2}\pi}\left(\sqrt{\frac{\sigma^{2}}{\rho+\sigma^{2}}+(1-\eta)}-\sqrt{\frac{\sigma^{2}}{\rho+\sigma^{2}}}\right)&\mathrm{if}~{}\sigma^{2}\ll
1\\\
\frac{1}{2\pi}\frac{\rho+\sigma^{2}}{\rho}(1-\eta)&\mathrm{if}~{}\sigma^{2}\sim
1\end{cases}$ (84) $\displaystyle\sim
1-\eta=\mathcal{O}\left(n^{-\mathrm{min}\left(2\ell\mathrm{min}(r,1),\frac{\alpha-\ell}{\alpha}\right)}\right).$
(85)

Note that the noisy rate (85) corresponds to twice the noiseless rate (18).

In the unregularized regime $\ell>\alpha$, the discussion in the noiseless
setting carries through and the excess error also asymptotically saturates to
a non-zero limit

$\epsilon_{g}-\epsilon_{g}^{\infty}=\mathcal{O}(1)$ (86)

Figure 6: Misclassification error $\epsilon_{g}$ for ridge classification on
synthetic Gaussian data, as specified in (8) and (92), for different
source/capacity coefficients $\alpha,r$, for a regularization
$\lambda=n^{-\ell}$ and noise strength $\sigma$. In blue, the solution of the
closed set of equations (LABEL:eq:app:reg:loureiro_g3m_reg) used in the
characterization (9) for the misclassification error, using the g3m package
[28]. The dimension $p$ was cut-off at $10^{4}$. Red dots corresponds to
simulations using the scikit-learn SVC package and averaged over $40$
instances, for $p=10^{4}$. The green dashed line indicates the power-law rate
(85).

##  Appendix D Remark on the overfitting regime of ridge classification

In this Appendix, we provide further discussion on the saturation of the error
(9) to a finite value in the effectively unregularized regime of ridge
classification (19), which defies the common intuition that for large enough
sample complexity $n$, ridge classification should be able to generalize
almost perfectly. In this section, we first provide an analytical reminder of
why the error does go to zero for finite-dimensional feature spaces
($p<\infty,\,n\gg 1$), before discussing what differs in the setup at hand
($1\ll n\ll p=\infty$). We argue that while in the first limit a double-
descent phenomenon is observed, the second limit always corresponds to a
learning regime located in the plateau/valley following the first descent. In
the following, we consider directly the $\lambda=0$ case for the sake of
simplicity.

Figure 7: Misclassification error $\epsilon_{g}$ for ridge classification on
artificial Gaussian data, as specified in (8), for source $r=1.2$, capacity
$\alpha=2$, at regularization $\lambda=n^{-3}$. The dimension was cut-off to
$p=10^{6}$. The blue curve corresponds to the numerical solution of the
equations (17) using the g3m package [28]. While for sample complexities
comparable or larger than the dimension $n\geq p$ a second descent, followed
by a drop of the error to zero, is observable, in the $1\ll n\ll p=\infty$
limit considered in the present work the second descent, which happens for
$n\gtrapprox p$ (red hashed region), is no longer observed. Instead, only the
plateau following the first descent is observed, which corresponds to the
saturation effect of Fig. 2

###  D.1 The finite dimensional setup

We first sketch up an brief analysis for the limit of finite feature space
dimension $\infty>p\gg 1$ setting, with large sample complexity $n\gg p$.
Naming $X\in\mathbb{R}^{n\times p}$ (with the $\mu^{\mathrm{th}}$ row of $X$
being $\psi(x^{\mu})$) the matrix of the data in feature space and
$y=\mathrm{sign}(X\theta^{\star})\in\mathbb{R}^{n}$ the corresponding vector
of stacked labels, the ridge estimator can be compactly written as

$\hat{w}=(X^{T}X)^{-1}X^{T}\mathrm{sign}(X\theta^{\star}).$ (87)

In the $n\xrightarrow{}\infty$ limit

$\displaystyle\frac{1}{n}X^{T}X=\Sigma+\mathcal{O}\left(\frac{1}{\sqrt{n}}\right),$
$\displaystyle\frac{1}{n}X^{T}\mathrm{sign}(X\theta^{\star})=\mathbb{E}_{x}^{\mathcal{N}(0,\Sigma)}\left[x\mathrm{sign}(x\cdot\theta^{\star})\right]+\mathcal{O}\left(\frac{1}{\sqrt{n}}\right).$
(88)

Hence

$\displaystyle\hat{w}$
$\displaystyle\approx\Sigma^{-1}\mathbb{E}_{x}^{\mathcal{N}(0,\Sigma)}\left[x\mathrm{sign}(\theta^{\star
T}x)\right]$
$\displaystyle\approx\Sigma^{-1}\Sigma^{\frac{1}{2}}\mathbb{E}_{x}^{\mathcal{N}(0,1)}\left[x\mathrm{sign}(x^{T}\Sigma^{\frac{1}{2}}\theta^{\star})\right]$
$\displaystyle\approx\Sigma^{-\frac{1}{2}}\mathbb{E}_{x_{\parallel}}^{\mathcal{N}(0,1)}\left[x_{\parallel}\mathrm{sign}(x_{\parallel})\right]\frac{\Sigma^{\frac{1}{2}}\theta^{\star}}{||\Sigma^{\frac{1}{2}}\theta^{\star}||_{2}},$
(89)

where we noted $x_{\parallel}$ the component of $x$ parallel to
$\theta^{\star}$. So

$\hat{w}=\sqrt{\frac{2}{\pi}}\frac{\theta^{\star}}{||\Sigma^{\frac{1}{2}}\theta^{\star}||_{2}}\propto\theta^{\star}.$
(90)

This means in particular the direction of the teacher is perfectly recovered,
and that the prediction error $\epsilon_{g}$ (9) goes to zero in the $p\ll
n\rightarrow\infty$ limit.

###  D.2 Infinite dimensional feature space

We now argue why this discussion ceases to hold in the setup of interest $n\ll
p=\infty$ (plateau reached after the first descent, see Fig. 7). In this
limit, loosely written,

$\displaystyle\hat{w}$
$\displaystyle\approx\left(\Sigma^{-1}+\mathcal{O}\left(\frac{1}{\sqrt{n}}\right)\right)\left(\mathbb{E}_{x}^{\mathcal{N}(0,\Sigma)}\left[x\mathrm{sign}(\theta^{\star
T}x)\right]+\mathcal{O}\left(\frac{1}{\sqrt{n}}\right)\right)$
$\displaystyle=\sqrt{\frac{2}{\pi}}\frac{\theta^{\star}}{||\Sigma^{\frac{1}{2}}\theta^{\star}||_{2}}+\mathcal{O}\left(\sqrt{\frac{p}{n}}\right)\neq\mathrm{cte.}\times\theta^{\star}.$
(91)

The last term comes from the sum of $p$ random terms of order $1/\sqrt{n}$
entailed by the matrix multiplication. In particular, this implies that the
teacher fails to be perfectly recovered by ERM in this limit, causing the
misclassification error to plateau to a finite limit, see equation (19). This
is due to the fact that in an infinite-dimensional space, the ridge ERM (16)
always has enough dimensions to overfit the dataset. Another way to look at
this limit is in the framework of the well-known double-descent phenomenon
which occurs in the finite dimensional limit $p<\infty$ discussed in
subsection D.1. In the $p=\infty$ limit, the second descent, which commences
at $n\approx p$, happens at infinite sample complexity and is thus not
observed for finitely large $n$. In fact, the $1\ll n\ll p=\infty$ limit
always correspond to the plateau following the first descent, see Fig. 7.

##  Appendix E Crossovers in noisy kernel classification

In this appendix, we briefly discuss the noisy setup where the target function
$f^{\star}$ is corrupted by a Gaussian noise of variance $\sigma^{2}$, i.e.

$y^{\mu}=\mathrm{sign}\left(f^{\star}(x^{\mu})+\sigma\mathcal{N}(0,1)\right).$
(92)

In this setting, the misclassification error (9) no longer tends
asymptotically to $0$, but instead converges to a positive value dictated by
the noise strength

$\epsilon_{g}\xrightarrow[]{n\rightarrow\infty}\epsilon_{g}^{\infty}=\frac{1}{\pi}\mathrm{arccos}\left(\sqrt{\frac{\rho}{\rho+\sigma^{2}}}\right).$
(93)

Observe that the residual error $\epsilon_{g}^{\infty}$ corresponds to the
smallest achievable $0/1$ risk, and is achieved by the teacher $f^{\star}$. In
contrast to the noiseless setting (1), the stochasticity in the generation of
the labels (92) induces a non-zero error even for $f^{\star}$. Numerical
experiments presented in Fig. 8 show that the rate of decay of the excess
misclassification error $\epsilon_{g}-\epsilon_{g}^{\infty}$, when optimized
over the regularization strength $\lambda$, transitions from the noiseless
rate (15) to a $\alpha/(1+\alpha)$ rate as the sample complexity $n$ is
increased. Note that interestingly the rate $\alpha/(1+\alpha)$ has been
reported in [24] as an upper bound for the excess misclassification error,
although it is possible to show that the noisy setup (92) does not satisfy the
conditions of their corresponding theorem. This crossover phenomenon is highly
similar to the one observed in [15] for kernel regression.

Figure 8: Excess misclassification error $\epsilon_{g}-\epsilon_{g}^{\infty}$
for max-margin classification on synthetic Gaussian data corrupted by a
Gaussian noise of variance $\sigma^{2}$, as specified in (8), for different
source/capacity coefficients $\alpha,r$, for optimal $\lambda^{\star}$. In
blue, the solution of the closed set of equations (13) used in the
characterization (9) for the misclassification error, using the g3m package
[28]. The dimension $p$ was cut-off at $10^{4}$. Red dots corresponds to
simulations using the scikit-learn SVC package averaged over $40$ instances,
for $p=10^{4}$. Optimization over $\lambda$ was performed using cross
validation, with the help of the python scikit-learn GridSearchCV package. The
green dashed line indicates the power-law rate (15) derived in this work; the
black dashed line indicates the classical optimal rate $\alpha/(1+\alpha)$
[24].

Finally, we note that for some real datasets the learning curves are
satisfactorily described by the noisy rate $\alpha/(1+\alpha)$[24] (see also
the discussion in section A). This is for instance the case for Fashion MNIST
when a polynomial kernel SVM is employed, see Fig. 9. Interestingly, the rate
which describes the learning curve of an optimally regularized ridge
classifier in this setting is also the noisy rate (85)(see Appendix C), rather
than the noiseless rate (21). For MNIST classified using an RBF kernel, both
the noiseless rates (15),(21) and the noisy rates $\alpha/(1+\alpha)$,(85) are
observed, with a crossover phenomenon during which the learning curve
transitions from the former to the latter.

Figure 9: Dots: Misclassification error $\epsilon_{g}$ of kernel
classification on Fashion MNIST with a polynomial kernel (left) and MNIST with
an RBF kernel, for optimally regularized SVM (blue) and optimally regularized
ridge classification (red), using respectively the python scikit-learn SVC and
KernelRidge packages. Dashed lines: Theoretical decay rates for the error
$\epsilon_{g}$ (blue: (15), light purple :[26], red: (21), purple: (85)),
computed from empirically estimated capacity $\alpha$ and source $r$
coefficients (see section (V) and Appendix F for details). These coefficients
were estimated to $\alpha\approx 1.28,\,r\approx 0.28$ for FashionMNIST using
the polynomial kernel and $\alpha\approx 1.5,\,r\approx 0.5$ for MNIST using
the RBF kernel, see Appendix F.

##  Appendix F Details on real data-sets

###  F.1 Measuring the capacity and source of real datasets

Figure 10: Cumulative functions (96) for $10^{4}$ CIFAR 10 sampled at random,
for a RBF kernel (top) and a polynomial kernel (bottom). The slopes fitted
using least-squares linear regression on the regions the curves are
qualitatively resembling power-laws are represented in dashed lines.

In this section we provide details on the experiments on real data (section V,
Fig. 4), which can also be found in [30, 31, 15]. Consider a real dataset
$\mathcal{D}_{m}=\\{x^{\mu},y^{\mu}\\}^{m}_{\mu=1}$ of size $m$. The data
distribution $\nu$ defined in section II is then the empirical distribution
over $\mathcal{D}_{m}$:

$\nu(\cdot)=\frac{1}{m}\sum\limits_{\mu=1}^{m}\delta(\cdot-x^{\mu}).$ (94)

Then the definitions of the feature map $\psi$ (3) and of the feature
covariance $\Sigma$ (5) admit the simple rewriting

$\displaystyle\frac{1}{m}G\Psi=\Psi\Sigma,$
$\displaystyle\Sigma=\frac{1}{m}\Psi^{\top}\Psi,$ (95)

provided we introduce the Gram matrix
$G_{\mu,\nu}=K(x^{\mu},x^{\nu})\in\mathbb{R}^{m\times m}$ and the matrix of
horizontally stacked features $\Psi_{\mu
k}=\psi(x^{\mu})_{k}\in\mathbb{R}^{m\times m}$. Note that for real data, one
has that the dimension of the feature space $p$ is equal to the total size of
the dataset $m$. A teacher $\theta^{\star}$ providing perfect classification
$y=\mathrm{sign}(\Psi\theta^{\star})$ can be found e.g. by performing max
margin classification on $(\Psi,y)$. While the method to fit a perfect
classifier $\theta^{\star}$ is not unique, we observed that using logistic
classifiers or regularized hinge classifiers instead of max-margin classifiers
did not significantly impact the measured source coefficient.

From the eigenvalues $\\{\omega_{k}\\}_{k=1}^{p}$ of the covariance $\Sigma$
(95) and the components of the teacher $\\{\theta^{\star}_{k}\\}_{k=1}^{p}$,
the capacity and source $\alpha,\,r$ (8) can be estimated. From (8), the
following scalings should hold:

$\displaystyle\sum\limits_{k^{\prime}=k}^{p}\omega_{k^{\prime}}\sim
k^{1-\alpha},$
$\displaystyle\sum\limits_{k^{\prime}=k}^{p}\omega_{k^{\prime}}\theta_{k^{\prime}}^{\star
2}\sim k^{-2\alpha r}.$ (96)

These curves are presented in Fig. 10 for the dataset comprised of $10^{4}$
randomly samples CIFAR 10 images, see section V of the main text. Note that we
estimate the cumulative functions (96) following [30, 15] because the
summation allows to smoothen out the curves, thus permitting a relatively more
precise evaluation. Because the feature space is finite, the functions (96)
fail to be exact power-laws, and exhibit in particular a sharp drop for $n$
approaching $m$. Nonetheless, we identify for each curve a region of indices
$k$ for which the curve looks qualitatively like a power-law, and fit the
curves by a power-law using least-squares linear regression to finally extract
the coefficients $\alpha,r$ therefrom. These fits are shown in Fig. 10 for the
reduced CIFAR 10 dataset discussed in the main text (see section V), for an
RBF kernel with inverse variance $10^{-7}$ and a polynomial kernel of degree
$5$. The capacity and source were estimated to be $\alpha\approx
1.16,\,r\approx 0.10$ for the RBF kernel and $\alpha\approx 1.51,\,r\approx
0.07$ for the polynomial kernel.

###  F.2 Details on numerical simulations

In this subsection, we provide further details on the simulations presented in
Fig. 4 of the main text. For each sample complexity $n$, a subset of size $n$
was randomly sampled without replacements from $\mathcal{D}_{m}$. Like in [51,
28, 15], the whole dataset $\mathcal{D}_{m}$ was used as a test set. The max-
margin simulations in Fig. 4 were performed using the scikit-learn SVC package
at vanishing regularization $\lambda=10^{-5}$, and averaged over $50$
realizations of the training set. The ridge simulations in Fig. 4 were
realized using the scikit-learn KernelRidge package, with the optimal
$\lambda$ estimated using scikit-learn GridSearchCV’s default $5$-fold cross
validation routine over a grid $\lambda\in\\{0\\}\cup(10^{-10},10^{5})$, with
logarithmic step size $0.026$. The misclassification error was also averaged
over $50$ realizations of the training set.

##  Appendix G Comparison to the classical rates

In this Appendix, we provide a detailed comparison of the presently reported
rate for noiselesss max-margin classification (15) and the rate reported in
[24] (equation $7.53$, following from Theorem $7.23$ and Lemma $A.1.7$), in
the case of a teacher in the Hilbert space $f^{\star}\in\mathcal{H}$, for
which the latter result holds. We alternatively point the reader to section
$5$ of [45], where the same bound, and the underlying assumptions thereof, are
reminded in concise fashion. We first provide a brief reminder of this upper
bound, before proceeding to evaluate it in the present setting (8), and show
that it yields a slower rate than (15), i.e. that the bound in [24] is loose.
For completeness, we finally provide a comparison to the rates reported in
[27].

###  G.1 Theorem 7.23 in [23]

In the following, $\ell(y,a)=\mathrm{max}(0,1-ya)$ designates the hinge loss,
and the script cl refers to the clipped value [24]. Suppose that

  1. A.1

$\underset{w}{\mathrm{inf}}\mathbb{E}_{\psi(x),y}\ell(y,w^{\top}\psi(x))=\mathbb{E}_{\psi(x),y}\ell\left(y,f^{*}(\psi(x))\right)$
where the Bayes estimator $f^{*}$ is defined as
$f^{*}(\psi(x))=\underset{a}{\mathrm{argmin}}\mathbb{E}_{\psi(x),y}\ell(y,a)$.
The expectation refers to the joint distribution of the data $\psi(x)$ and the
labels $y$.

  2. A.2

(Bernstein condition) There exist $B>0,\,\theta\in[0,1],\,V\geq B^{2-\theta}$
so that for all $w$, $\ell(y,(w^{\top}\psi(x))^{\mathrm{cl}})\leq
B~{}~{}\mathrm{a.s.}$ and

$\displaystyle\mathbb{E}_{\psi(x),y}\left(\left[\ell(y,(w^{\top}\psi(x))^{\mathrm{cl}})-\ell(y,f^{*}(\psi(x)))\right]^{2}\right)\leq$
$\displaystyle
V\Bigg{[}\mathbb{E}_{\psi(x),y}\Bigg{(}\ell(y,(w^{\top}\psi(x))^{\mathrm{cl}})$
$\displaystyle-\ell(y,f^{*}(\psi(x)))\Bigg{)}\Bigg{]}^{\theta}$ (97)

  3. A.3

the spectrum of the covariance
$\Sigma=\mathbb{E}_{\psi(x)}\psi(x)\psi(x)^{\top}$ has a polynomial decay with
rate $\alpha$

  4. A.4

The approximation error
$\mathcal{A}_{2}(\lambda)=\underset{w}{\mathrm{min}}\mathbb{E}_{\psi(x),y}\ell(y,w^{\top}\psi(x))+\lambda||w||^{2}-\underset{w}{\mathrm{inf}}\mathbb{E}_{\psi(x),y}\ell(y,w^{\top}\psi(x))$
is upperbounded by $\lambda^{b}$ for $b\in(0,1]$

Then with high probability [24]

$\epsilon_{g}-\epsilon_{g}^{*}\lesssim
n^{-\mathrm{min}\left(\frac{2b}{1+b},\frac{\alpha
b}{b(2\alpha-1-\alpha\theta+\theta)+1}\right)}.$ (98)

In (98), $\epsilon^{*}$ refers to the infimum of the classification error over
all measurable functions (as opposed to $\epsilon_{g}$ resulting from ERM (12)
over linear estimators only).

###  G.2 Specialization to the noiseless source/capacity setting

We proceed to translate Theorem (98) [24] for our setting (8) (1), in the case
where the teacher $f^{\star}$ is in $\mathcal{H}$ ($r\geq\frac{1}{2})$, for
which assumption (A.1) is readily satisfied. To this end, one must evaluate
the parameters $\theta,\,b$ entering in (98). First note that the Bayes
estimator $f^{*}$ assumes the simple form
$f^{*}(x)=\mathrm{sign}(\theta^{\star\top}x)$ in the presence of the teacher
$\theta^{\star}$. As a consequence, in the noiseless setting,

$\mathbb{E}_{\psi(x),y}\ell\left(y,f^{*}(\psi(x))\right)=\mathbb{E}_{\psi(x)}\ell\left(\mathrm{sign}(\theta^{\star\top}x),\mathrm{sign}(\theta^{\star\top}x))\right)=0.$
(99)

The Bernstein condition is straightforwardly satisfied with $B=V=2$ and
$\theta=1$, since $\ell(1,\cdot^{\mathrm{cl}})$ (resp.
$\ell(1,\cdot^{\mathrm{cl}})$) is a piecewise continuous function, constant
equal to $0$ on $(1,\infty)$ (resp$(-\infty,-1)$) and to $2$ on $(-\infty,-1)$
(resp. $(1,\infty)$), and linear in between. In our model, the argmin in the
definition of $\mathcal{A}_{2}(\lambda)$ can be approximated first as
$w\approx c\times\theta^{\star}/||\theta^{\star}||$, i.e. for a $w$
proportional to the teacher. Note that this is an approximation, and in
general there exist a small (shrinking with $\lambda$ going to $0$) angle
between the true minimizer and the teacher. Typically, $c$ will tend to
infinity as $\lambda$ goes to zero. Let us evaluate the proportionality
constant $c$:

$\displaystyle\mathbb{E}_{\psi(x),y}\ell(y,w^{\top}\psi(x))$
$\displaystyle\propto\int
dxe^{-\frac{1}{2}x^{\top}\Sigma^{-1}x}\mathrm{max}(0,1-\mathrm{sign}(\theta^{\star\top}x)c\theta^{\star\top}x/||\theta^{\star}||)$
$\displaystyle\propto\int\limits_{c\theta^{\star\top}x/||\theta^{\star}||<1}dxe^{-\frac{1}{2}x^{\top}\Sigma^{-1}x}(1-\mathrm{sign}(\theta^{\star\top}x)c\theta^{\star\top}x/||\theta^{\star}||)$
$\displaystyle\overset{x_{\parallel}=\theta^{\star\top}x/||\theta^{\star}||}{\propto}\int\limits_{-\frac{1}{c}}^{\frac{1}{c}}dx_{\parallel}e^{-\frac{x_{\parallel}^{2}}{2\theta^{\star\top}\Sigma\theta^{\star}/||\theta^{\star}||^{2}}}(1-c|x_{\parallel}|)$
$\displaystyle\propto
2\int\limits_{0}^{1}dx_{\parallel}e^{-\frac{x_{\parallel}^{2}}{2c\theta^{\star\top}\Sigma\theta^{\star}/||\theta^{\star}||^{2}}}(1-x)\sim\frac{1}{c}$
(100)

where in the last line we supposed $c$ large. Then

$\mathcal{A}(\lambda)\approx\underset{c}{\mathrm{min}}\left\\{\frac{A}{c}+\lambda
c^{2}\right\\}$ (101)

for some constant $A$, for $\lambda$ small ($c$ large). Minimizing the
function leads to $c\sim\lambda^{-\frac{1}{3}}$, then to
$\mathcal{A}(\lambda)\sim\lambda^{\frac{1}{3}}$, i.e. $b=\frac{1}{3}$. We also
checked this scaling by numerically solving the self-consistent equations (13)
in the large sample complexity limit ($n\gg p$), noticing that the train loss
admits the following expression in terms of the order parameters
$m,q,\rho,V,\hat{m},\hat{q},\hat{V}$ [28]:

$\displaystyle\mathcal{A}_{2}(\lambda)\approx\underset{n\gg
p}{\mathrm{lim}}~{}~{}$ $\displaystyle
2\int\limits_{0}^{\infty}\frac{e^{-\frac{u^{2}}{2}}}{\sqrt{2\pi}}\int\limits_{-\infty}^{\infty}\frac{e^{-\frac{h^{2}}{2}}}{\sqrt{2\pi}}\mathrm{max}\left(0,1-\mathrm{prox}_{V\mathrm{max}(0,1-\cdot)}\left(\frac{m}{\sqrt{\rho}}s+\sqrt{q(1-\eta)}h\right)\right)$
$\displaystyle+\lambda
p\mathrm{tr}\frac{p\hat{m}^{2}\Sigma\theta^{\star}\theta^{\star\top}\Sigma+\hat{q}\Sigma}{(\frac{n\lambda}{2}+p\hat{V}\Sigma)^{2}},$
(102)

where the proximal map is given by

$\displaystyle\mathrm{prox}_{V\mathrm{max}(0,1-y\cdot)}(\omega)=\begin{cases}\omega+yV~{}~{}\mathrm{if}~{}~{}y\omega\leq
1-V,\\\ y~{}~{}\mathrm{if}~{}~{}1-V\leq y\omega\leq 1,\\\
\omega~{}~{}\mathrm{if}~{}~{}y\omega\geq 1.\end{cases}.$ (103)

The function $\mathcal{A}_{2}(\lambda)$ is plotted for several values of
source/capacity coefficients $\alpha,r$ in Fig. 11 and is well captured by a
power law with rate $b=\frac{1}{3}$.

Figure 11: Approximation error $\mathcal{A}_{2}(\lambda)$ as a function of the
regularization strength $\lambda$. In blue, the numerical solution of the
self-consistent equations (13) using the g3m package [28]. Red dotted lines
represent the power law $\lambda^{\frac{1}{3}}$, which provides a very
satisfying fit for all values of capacity/source coefficients $\alpha,r$.

Finally, the bound provided by the Theorem (98) [24] reads (notice that
$\epsilon^{*}_{g}=0)$

$\epsilon_{g}-\epsilon_{g}^{*}\lesssim
n^{-\mathrm{min}\left(\frac{1}{2},\frac{\frac{\alpha}{3}}{\frac{\alpha}{3}+1}\right)}$
(104)

Note that the rate (15) is always faster:

$n^{-\frac{\frac{\alpha}{2}}{1+\frac{\alpha}{2}}}\ll
n^{-\mathrm{min}\left(\frac{1}{2},\frac{\frac{\alpha}{3}}{\frac{\alpha}{3}+1}\right)}.$
(105)

In other words, the upper bound of [24] is loose in the present setting when
$f^{\star}\in\mathcal{H}$. While numerical investigations suggest this is also
true for $f^{\star}\in L^{2}(\mathcal{X})\setminus\mathcal{H}$, we leave a
more detailed comparison to [24] in this case to future work.

###  G.3 Theorems 3.3 and 3.5 in [25]

Finally, we discuss the rates reported in [27] under margin assumptions as
[44, 26]. Note that the regression function
$\eta\left(\psi(x)\right)\equiv\mathbb{P}(y=1|\psi(x))$ has in the noiseless
setting (1) the compact form
$\eta\left(\psi(x)\right)=\mathrm{sign}(\theta^{\star\top}\psi(x))$ and is
therefore not Hölder class for any $\beta>0$, rendering Theorems $3.3$ and
$3.5$ in [27] effectively inapplicable. Note that in addition, the rates would
in any case be ambiguous, as both the margin exponent $\alpha$ and the
dimension $d$ are infinite in our setting. Finally remark that [26, 52]
provide rates under similar margin conditions in direct space, for the
particular case of Gaussian kernels. Relating those conditions to the
characterization (8) in feature space used in the present work is out of the
scope of the present manuscript.