# A High Dimensional Model for Adversarial Training: Geometry and Trade-Offs

Kasimir Tanner<EMAIL_ADDRESS>Information, Learning and Physics
Laboratory, EPFL, 1015 Lausanne, Switzerland  Matteo Vilucchio
<EMAIL_ADDRESS>Information, Learning and Physics Laboratory, EPFL,
1015 Lausanne, Switzerland  Bruno Loureiro  Departement d’Informatique, École
Normale Supérieure de Paris, PSL & CNRS, France  Florent Krzakala
Information, Learning and Physics Laboratory, EPFL, 1015 Lausanne, Switzerland

###### Abstract

This work investigates adversarial training in the context of margin-based
linear classifiers in the high-dimensional regime where the dimension $d$ and
the number of data points $n$ diverge with a fixed ratio $\alpha=n/d$. We
introduce a tractable mathematical model where the interplay between the data
and adversarial attacker geometries can be studied, while capturing the core
phenomenology observed in the adversarial robustness literature. Our main
theoretical contribution is an exact asymptotic description of the sufficient
statistics for the adversarial empirical risk minimiser, under generic convex
and non-increasing losses. Our result allow us to precisely characterise which
directions in the data are associated with a higher generalisation/robustness
trade-off, as defined by a robustness and a usefulness metric. In particular,
we unveil the existence of directions which can be defended without penalising
accuracy. Finally, we show the advantage of defending non-robust features
during training, identifying a uniform protection as an inherently effective
defence mechanism.

##  I Introduction

The susceptibility of machine learning models to adversarial attacks — subtle
yet strategically crafted data perturbations — has been an ongoing concern for
various machine learning models, from linear classifiers to deep neural
networks. In particular, this vulnerability is intrinsic to margin-based
classifiers [23]. Also in image classification, seemingly innocuous
modifications, like tiny stickers on road signs, can dramatically mislead
models that otherwise exhibit strong generalisation [49].

The problem has been theoretically studied in linear models where solutions
could be obtained analytically. Previous studies were focusing on the
fundamental limits of the trade-off between adversarial and generalisation
errors [26] or on including a non trivial data covariance and comparing the
performances of adversarial training to Bayes optimal errors [64].

Nonetheless a comprehensive understanding of how structure defines feature
types — robust, useful, or both — affect model performance is still
developing. The interplay of the data structure with attack and training
geometries remains a particularly fertile ground for investigation, with
potential implications for enhancing adversarial robustness and developing
more effective protection methods.

In this paper, we introduce a structured, high-dimensional model for studying
adversarial classification under margin-based classifiers. Our main
contributions are threefold:

  * •

We introduce a mathematically tractable model for investigating the interplay
between the data, attack and defence geometries. Despite its simplicity, we
show our model is rich enough to capture the key phenomenology observed in
practical adversarial training setups.

  * •

We show that the relevant statistical properties of the adversarial empirical
risk minimiser can be exactly characterised in terms of a finite set of
sufficient statistics in the high-dimensional proportional limit where the
number of samples and covariate dimension diverge at a constant rate.

  * •

Finally, we leverage our result to investigate the interplay between data and
attack geometry in the effectiveness of adversarial training. In particular,
we show how directional attacks can be decomposed in directions leading to a
robustness/generalisation trade-off and directions that can be successfully
defended without sacrificing accuracy.

This manuscript is organised as follows. Section II introduces the data model
and the margin-based adversarial training protocol we study. Section III
describes our main theoretical results, namely the asymptotic characterisation
of the adversarial estimator. Finally, Section IV discusses the implications
of our formulas. The code used to produce all the figures in this manuscript
is available at github.com/IdePHICS/Adversarial-Setting.

### Related works

##### Adversarial attacks —

In the study of neural networks, the vulnerability to adversarial attacks is
well-established, with early works like [63, 21, 47] uncovering this
intriguing weakness. Adversarial Training, particularly through methods like
projected gradient descent, has emerged as a leading defence strategy, as
explored in-depth in [34].

Understanding adversarial robustness has been a long standing challenge. [58]
showed that it is necessary to have higher sample complexity in adversarial
training to achieve the same generalisation performance as standard training.
[23] showed that datasets contain predictive yet imperceptible features
vulnerable to attacks. Additionally, [69] find that it is difficult to
optimise a data-set to improve adversarial robustness. The adversarial setting
has also been studied in the neural tangent kernel regime by [68].

The idea of a fundamental trade-off between adversarial robustness and
standard accuracy has been noted in [70, 79, 61]. Later, theoretical studies
like [5, 11, 25] have examined this trade-off in the case of Gaussian Mixture
Models. In [53] the authors show that a class of augmented estimators can have
a worse generalisation error than the standard estimator. Additionally [64,
26] contribute to this discourse by examining the impact of adversarial
training on the interpolation threshold and double descent in the case of
Gaussian data. In [19] they study how adversarial vulnerability depends on the
dimensions of the perturbation and the dimension of ambient space.

More recently [57, 56] has studied adversarial training as a form of data
dependent regularisation.

##### Exact asymptotics —

Our main theoretical result pertains to an established literature employing
techniques from high-dimensional probability [66, 67, 62, 64, 13], random
matrix theory [4, 35, 30, 36, 77, 59] and statistical physics [3, 39, 16, 6,
32, 72, 44, 2, 1] to derive exact asymptotic results of high-dimensional
statistical estimation problems. Of particular relevance to our work is [32],
who proved a formula for the sufficient statistics of general Gaussian
Covariate models. While our work leverage their results, our formulas are more
general, as it accounts for adversarial attacks and training. Moreover, in our
proof we use a mapping to an Approximate Message Passing (AMP) for adversarial
training on structured problems, which builds upon [54, 24, 55, 65, 17, 33,
31, 18].

##  II Setting Specification

Consider a supervised binary classification problem with training data
$\mathcal{D}=\quantity{(\boldsymbol{x}_{i},y_{i})}_{i=1}^{n}\in\mathbb{R}^{d}\times\\{-1,+1\\}$.
In the following, we focus on a generalised estimation problem, where for each
$i=1,\cdots,n$ we assume the covariates are independently drawn from
$\boldsymbol{x}_{i}\sim\mathcal{N}\quantity(\boldsymbol{0},\boldsymbol{\Sigma}_{\boldsymbol{\boldsymbol{x}}})$
and the labels are drawn as:

$\displaystyle
y_{i}\sim\mathbb{P}(y|\boldsymbol{\theta}_{0}^{\top}\boldsymbol{x}_{i}).$ (1)

for a fixed parameter $\boldsymbol{\theta}_{0}\in\mathbb{R}^{d}$.111Note our
results also hold under the assumption of
$\boldsymbol{\theta}_{0}\sim\mathcal{N}\quantity(\boldsymbol{0},\boldsymbol{\Sigma}_{\boldsymbol{\theta}})$.
Although our theoretical results in Section III hold under a generic
likelihood $P(y|z)$, for concreteness the discussion in Section IV will be
mostly focused on the probit model
$\mathbb{P}\left(y|z\right)=\nicefrac{{1}}{{2}}\operatorname*{erfc}\left(-\nicefrac{{z}}{{\sqrt{2}\tau}}\right)$,
where the parameter $\tau>0$ control the noise level. In particular, note that
for $\tau\to 0$ we have $P(y|z)=\delta(y-\operatorname{sign}(z))$.

Our choice of Gaussian covariates echoes the recent findings in Gaussian
universality [20, 40, 74, 15, 52, 12] suggesting their broad scope in the
context of high-dimensional generalised linear estimation, often mirroring
real-world datasets.

Given the training data $\mathcal{D}$, our goal in the following is to
investigate the capacity of margin-based linear classifiers:

$\hat{y}(\hat{\boldsymbol{\theta}},\boldsymbol{x})=\operatorname{sign}\quantity(\frac{\hat{\boldsymbol{\theta}}^{\top}\boldsymbol{x}}{\sqrt{d}})\,,$
(2)

in robustly and efficiently classifying the data under adversarial attacks,
where $\hat{\boldsymbol{\theta}}=\hat{\boldsymbol{\theta}}(\mathcal{D})$ is an
estimator that has been learned from the training data data.

The problem introduced above is often refereed to as a _teacher-student_
setting, and is widespread in the high-dimensional statistics literature, e.g.
[62, 64, 10, 9].

In machine learning, a pivotal concern is evaluating the extent to which a
model generalises beyond its training data. The cornerstone metric for this
assessment is the generalisation error defined as

$E_{\mathrm{gen}}=\mathbb{E}_{y,\boldsymbol{x}}\quantity[\mathbb{1}(y\neq\hat{y}(\hat{\boldsymbol{\theta}},\boldsymbol{x}))]$
(3)

where the expectation is taken over input-output pairs generated using the
same $\boldsymbol{\theta}_{0}$ as in training.

Our focus is to study the consequences of an adversary attacking the student
estimate $\hat{y}$. The adversary can manipulate the data to fool the student.
Given an input sample $\boldsymbol{x}_{i}$, the adversary aims to find a
perturbation $\boldsymbol{\upsilon}_{i}$ such that
$y(\boldsymbol{x}_{i})\neq\hat{y}(\hat{\boldsymbol{\theta}},\boldsymbol{x}_{i}+\boldsymbol{\upsilon}_{i})$,
which leads the student to wrongly classify the sample.

The efficacy of such attacks hinges on the adversary’s knowledge. We focus on
a white-box adversary who has access to the student estimate
$\hat{\boldsymbol{\theta}}$, the dataset $\mathcal{D}$ and possibly to the
true teacher parameters $\boldsymbol{\theta}_{0}$. Additionally the allowed
perturbations must have a
$\boldsymbol{\Sigma}_{\boldsymbol{\upsilon}}$-induced norm smaller or equal
than an attack strength, beyond which an attack could be identified —
$\norm{\boldsymbol{\upsilon}}_{\boldsymbol{\Sigma}_{\boldsymbol{\upsilon}}^{-2}}\leq\varepsilon_{g}$.
This model generalises the case considered in [26, 64] where they only
consider the cases of bounded attacks in $\ell_{2}$ norm.

Introducing this attack geometry is crucial to distinguish features that are
easier or harder to attack. Often, we normalise
$\boldsymbol{\Sigma}_{\boldsymbol{\upsilon}}$ allowing us to interpret the
global strength of the attack to be proportional to $\varepsilon_{g}$ among
different geometries.

Given these adversarial dynamics, we introduce the adversarial generalisation
error. This metric quantifies the student’s performance under adversarial
attack

$E_{\mathrm{adv}}=\mathbb{E}_{y,\boldsymbol{x}}\quantity[\max_{\norm{\boldsymbol{\delta}}_{\boldsymbol{\Sigma}_{\boldsymbol{\upsilon}}^{-2}}\leq\varepsilon_{g}}\mathbb{1}(y\neq\hat{y}(\hat{\boldsymbol{\theta}},\boldsymbol{x}+\boldsymbol{\delta}))]\,,$
(4)

where the expectation is taken over pairs of input-output generated with the
same $\boldsymbol{\theta}_{0}$ used during training. Notably, this adversarial
generalisation error is an extension of the standard generalisation error,
with the latter being the special case where
$E_{\mathrm{gen}}=E_{\mathrm{adv}}(\varepsilon_{g}=0)$.

The current definition of adversarial error has a draw back with respect to
real adversarial attacks, it allows for attacks that fool both the student and
the teacher. For this reason we propose the class-preserving adversarial
error, which we define as

$E_{\mathrm{CP}}=\mathbb{E}_{y,\boldsymbol{x}}\quantity[\max_{\begin{subarray}{c}\norm{\boldsymbol{\delta}}_{\boldsymbol{\Sigma}_{\boldsymbol{\upsilon}}^{-2}}\leq\varepsilon_{g}\\\
y\boldsymbol{\theta}_{0}^{\top}(\boldsymbol{x}+\boldsymbol{\delta})>0\end{subarray}}\mathbb{1}(y\neq\hat{y}(\hat{\boldsymbol{\theta}},\boldsymbol{x}+\boldsymbol{\delta}))]\,,$
(5)

where a given attack is not allowed to fool the teacher. We achieve this by
constraining the attack strength whenever it would fool the teacher.

###  II.1 Empirical Risk Minimisation and Adversarial Case

To estimate a ‘student’ model with minimal (adversarial) generalisation error,
our goal is to optimise the metrics defined in Eqs. 3 and 4 by choosing
$\hat{\boldsymbol{\theta}}$. Typically, this optimisation is approached by
substituting these metrics with a convex surrogate and replacing the
expectation with an empirical mean over the available dataset. This method,
known as Empirical Risk Minimization (ERM), is a cornerstone in machine
learning for parameter estimation [71]. This approach is adapted in the
context of training neural networks robust to adversarial attacks, starting
with the adversarial generalisation error as the primary metric. Formally, the
ERM estimated weights $\hat{\boldsymbol{\theta}}$, are the minimiser of the
following empirical risk function

$\sum_{i=1}^{n}\max_{\norm{\boldsymbol{\delta}_{i}}_{\boldsymbol{\Sigma}_{\boldsymbol{\delta}}^{-2}}\leq\varepsilon_{t}}g\quantity(y_{i}\frac{\boldsymbol{\theta}^{\top}\quantity(\boldsymbol{x}_{i}+\boldsymbol{\delta}_{i})}{\sqrt{d}})+r(\boldsymbol{\theta})\,,$
(6)

where $\boldsymbol{\Sigma}_{\boldsymbol{\delta}}$ is a metric chosen for
perturbations and $r(\boldsymbol{\theta})$ is a regularisation term. We will
normalise $\boldsymbol{\Sigma}_{\boldsymbol{\delta}}$ in the same way as
$\boldsymbol{\Sigma}_{\boldsymbol{\upsilon}}$.

By opting for a decreasing convex surrogate $g$, we can simplify the inner
maximisation problem. For each sample $i=1,...n$, we have a binary label
$y_{i}\in\quantity{\pm 1}$, and thus the optimal perturbation
$\boldsymbol{\delta}_{i}$ is given by
$\boldsymbol{\delta}_{i}=-y_{i}\varepsilon_{t}\boldsymbol{\Sigma}_{\boldsymbol{\delta}}\boldsymbol{\theta}/\norm{\boldsymbol{\theta}}_{2}$.
Having solved the inner maximisation, the equivalent risk function to minimise
is

$\sum_{i=1}^{n}g\quantity(y_{i}\frac{\boldsymbol{\theta}^{\top}\boldsymbol{x}_{i}}{\sqrt{d}}-\varepsilon_{t}\frac{\boldsymbol{\theta}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\delta}}\boldsymbol{\theta}}{\sqrt{d}\,\norm{\boldsymbol{\theta}}_{2}})+r(\boldsymbol{\theta})\,.$
(7)

In the rest of the paper, we fix the function $g(x)=\log(1+\exp(-x))$ to be
the logistic loss. While our framework is versatile enough to accommodate
various convex regularisation functions for $r(\boldsymbol{\theta})$, our
analysis specifically focuses on $\ell_{2}$ regularisation. We choose
$r(\boldsymbol{\theta})=\frac{\lambda}{2}\norm{\boldsymbol{\theta}}_{2}^{2}$
due to its prevalent use in machine learning.

Our analysis primarily centres on examining the behaviour of (adversarial)
generalisation error in high-dimensional scenarios. Specifically, we
investigate settings where both the dimension $d$ and the number of training
samples $n$ are large $d,n\to\infty$, whilst maintaining finite sample
complexity $\alpha=n/d$. We refer to this limit as the high-dimensional
proportional limit.

###  II.2 Block Feature Data Model

The model is inspired by the discourse on feature categorisation in
adversarial contexts, notably distinguishing between useful and robust
features. Pioneering work in this area [23] posits that adversarial
vulnerability increases with highly predictive yet non-robust features, a
scenario frequently encountered in image classification tasks. On the one
hand, usefulness is a measure of the correlation between the output and the
feature. On the other hand, robustness is a measure of the correlation between
the output and the given feature when an attack is performed.

More formally, we define usefulness by

$\mathcal{U}_{\boldsymbol{\theta}_{0}}=\frac{1}{\sqrt{d}}\mathbb{E}_{\boldsymbol{x},y}[y\boldsymbol{\theta}_{0}^{\top}\boldsymbol{x}]\,,$
(8)

and robustness by

$\mathcal{R}_{\boldsymbol{\theta}_{0}}=\frac{1}{\sqrt{d}}\mathbb{E}_{\boldsymbol{x},y}\quantity[\inf_{\norm{\boldsymbol{\delta}}_{\boldsymbol{\Sigma}_{\boldsymbol{\upsilon}}^{-2}}\leq\varepsilon_{g}}y\boldsymbol{\theta}_{0}^{\top}(\boldsymbol{x}+\boldsymbol{\delta})]\,.$
(9)

These metrics can also be defined empirically in terms of the student estimate
and can be used to find non-robust features as we demonstrate in Appendix G.

##### The Block Feature Model

While our theoretical results stated in the next section hold for a wide array
of data models, we want to study adversarial robustness in a reductionist
spirit. To achieve this, we propose the following Block Feature Model (BFM),
which allows to systematically vary feature usefulness and robustness to
understand their impact on (adversarial) generalisation metrics.

For a given dimension $d$ we define $k\leq d$ blocks with individual sub-
dimensions $\quantity{d_{\ell}}_{\ell=1}^{k}$ satisfying
$\sum_{\ell=1}^{k}d_{\ell}=d$. This allows us to write the quantities of
interest as

$\displaystyle\boldsymbol{\Sigma}_{\boldsymbol{\boldsymbol{x}}}$
$\displaystyle=\operatorname{blockdiag}\quantity(\psi_{1}\mathbb{1}_{d_{1}},\psi_{2}\mathbb{1}_{d_{2}},\cdots,\psi_{k}\mathbb{1}_{d_{k}})\,,$
(10) $\displaystyle\boldsymbol{\Sigma}_{\boldsymbol{\delta}}$
$\displaystyle=\operatorname{blockdiag}\quantity(\Delta_{1}\mathbb{1}_{d_{1}},\Delta_{2}\mathbb{1}_{d_{2}},\cdots,\Delta_{k}\mathbb{1}_{d_{k}})\,,$
$\displaystyle\boldsymbol{\Sigma}_{\boldsymbol{\upsilon}}$
$\displaystyle=\operatorname{blockdiag}\quantity(\Upsilon_{1}\mathbb{1}_{d_{1}},\Upsilon_{2}\mathbb{1}_{d_{2}},\cdots,\Upsilon_{k}\mathbb{1}_{d_{k}})\,,$
$\displaystyle\boldsymbol{\Sigma}_{\boldsymbol{\theta}}$
$\displaystyle=\operatorname{blockdiag}\quantity(t_{1}\mathbb{1}_{d_{1}},t_{2}\mathbb{1}_{d_{2}},\cdots,t_{k}\mathbb{1}_{d_{k}})\,,$

where each $\psi_{\ell},\Delta_{\ell},t_{\ell}$ and $\Upsilon_{\ell}$ is
greater than zero for each $\ell=1,\dots k$ to preserve the positive
definiteness. Notice, that this model can easily be extended to allow for
power-law distributions on the eigenvalues by considering $d_{\ell}=1$ and
$\psi_{\ell}=\ell^{-\beta_{\psi}}$ for some exponent $\beta_{\psi}$.

The BFM allows for the expression of artificial datasets capturing the
simplest definitions of structure, whilst capturing the intricacies of power-
law distributed data, as can be found in images [73, 60].

Additionally, we define the Strong Weak Feature Model (SWFM) as a special case
of the BFM. In the SWFM, we only consider two blocks $k=2$ where the relative
sizes are tuned as $d_{\ell}/d\to\phi_{\ell}\in(0,1)$.

##  III Main Technical Results

The core technical result is a rigorous closed-form characterisation of the
properties of the estimator for the Gaussian covariate model, and the
corresponding training and generalisation errors in the high-dimensional
proportional limit.

Assumptions First of all we refer to the spectral decomposition of the data
covariance
$\boldsymbol{\Sigma}_{\boldsymbol{\boldsymbol{x}}}=\mathrm{S}^{\top}\operatorname{diag}(\omega_{i})\mathrm{S}$.
We additionally define
$\rho=\boldsymbol{\theta}_{0}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\boldsymbol{x}}}\boldsymbol{\theta}_{0}/d$,
$a=\boldsymbol{\theta}_{0}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\upsilon}}\boldsymbol{\theta}_{0}/d$,
$n=\boldsymbol{\theta}_{0}^{\top}\boldsymbol{\theta}_{0}/d$ and
$\bar{\boldsymbol{\theta}}=\mathrm{S}\boldsymbol{\Sigma}_{\boldsymbol{\boldsymbol{x}}}^{\top}\boldsymbol{\theta}_{0}/\sqrt{\rho}$.
Also, we consider
$\zeta_{i}=\operatorname{diag}(\mathrm{S}\boldsymbol{\Sigma}_{\boldsymbol{\delta}}\mathrm{S}^{\top})_{i}$,
$\upsilon_{i}=\operatorname{diag}(\mathrm{S}\boldsymbol{\Sigma}_{\boldsymbol{\upsilon}}\mathrm{S}^{\top})_{i}$
and
$\mathbf{f}=\mathrm{S}\boldsymbol{\Sigma}_{\boldsymbol{\upsilon}}^{\top}\boldsymbol{\theta}_{0}/\sqrt{\rho}$.
Next, we suppose that in the high dimensional limit

$\frac{1}{d}\sum_{i=1}^{d}\delta\quantity(\omega-\omega_{i})\delta\quantity(\bar{\theta}-\bar{\theta}_{i})\delta\quantity(\zeta-\zeta_{i})\delta(\upsilon-\upsilon_{i})\delta(f-f_{i})\to\mu$
(11)

converges to a distribution. Furthermore, we assume
$\boldsymbol{\Sigma}_{\boldsymbol{\delta}}$ and
$\boldsymbol{\Sigma}_{\boldsymbol{\upsilon}}$ to be independent of
$\boldsymbol{\theta}_{0}$.

######  Theorem III.1.

For the ERM estimator of the risk function with $\ell_{2}$ regularisation
$r(\boldsymbol{\theta})=\frac{\lambda}{2}\norm{\boldsymbol{\theta}}_{2}^{2}$
and $\lambda\geq 0$, under the data model defined and in the high dimensional
proportional limit, the two generalisation errors defined in Eqs. 3 and 4 are
given by

$\displaystyle E_{\mathrm{gen}}$
$\displaystyle=\frac{1}{\pi}\arccos\quantity(\frac{m}{\sqrt{(\rho+\tau^{2})q}})\,,$
(12) $\displaystyle E_{\mathrm{adv}}$
$\displaystyle=E_{\mathrm{gen}}\\!+\\!\int_{0}^{\varepsilon_{g}\frac{A}{\sqrt{q}\sqrt{N}}}\\!\\!\operatorname*{erfc}\left(\frac{-m\nu}{\sqrt{2\quantity(q(\rho+\tau^{2})-m^{2})}}\right)\mathcal{D}_{1}\quantity[\nu]\,,$
(13)

the equation for the CP error is given in Appendix B and

$\displaystyle A$
$\displaystyle=\mathbb{E}_{\mu}\quantity[\upsilon\frac{\hat{m}^{2}\bar{\theta}^{2}\omega+\hat{q}\omega^{2}}{(\lambda+\hat{V}\omega+\hat{P}\delta+\hat{N})^{2}}]$
(14) $\displaystyle F$
$\displaystyle=\mathbb{E}_{\mu}\quantity[\frac{\hat{m}f\bar{\theta}}{(\lambda+\hat{V}\omega+\hat{P}\delta+\hat{N})^{2}}]$

and $\gamma^{\star}=\varepsilon_{g}F/\sqrt{N}$. We define
$\mathcal{D}_{\rho}[\nu]$ to be the p.d.f. of a Gaussian variable with
variance $\rho$ and zero mean.

The values $(m,q,V,P,N)$ and $(\hat{m},\hat{q},\hat{V},\hat{P},\hat{N})$ can
be obtained as the solution of a system of ten self-consistent equations.
These saddle point equations are

$\begin{cases}\hat{m}=\alpha\mathbb{E}_{\xi}\left[\int_{\mathbb{R}}\differential{y}\partial_{\omega}\mathcal{Z}_{0}f_{g}(y,\sqrt{q}\xi,P,N)\right]\\\
\hat{q}=\alpha\mathbb{E}_{\xi}\left[\int_{\mathbb{R}}\differential{y}\mathcal{Z}_{0}f_{g}^{2}(y,\sqrt{q}\xi,P,N)\right]\\\
\hat{V}=-\alpha\mathbb{E}_{\xi}\left[\int_{\mathbb{R}}\differential{y}\mathcal{Z}_{0}\partial_{\omega}f_{g}(y,\sqrt{q}\xi,P,N)\right]\\\
\hat{P}=\frac{\varepsilon_{t}}{\sqrt{N}}\alpha\mathbb{E}_{\xi}\quantity[\int_{\mathbb{R}}\differential{y}y\mathcal{Z}_{0}f_{g}(y,\sqrt{q}\xi,P,N)]\\\
\hat{N}=-\frac{\varepsilon_{t}P}{N^{3/2}}\alpha\mathbb{E}_{\xi}\quantity[\int_{\mathbb{R}}\differential{y}y\mathcal{Z}_{0}f_{g}(y,\sqrt{q}\xi,P,N)]\end{cases}$
(15)
$\begin{cases}m=\mathbb{E}_{\mu}\quantity[\frac{\hat{m}\bar{\theta}^{2}}{\lambda+\hat{V}\omega+\hat{P}\delta+\hat{N}}]\\\
q=\mathbb{E}_{\mu}\quantity[\frac{\hat{m}^{2}\bar{\theta}^{2}\omega+\hat{q}\omega^{2}}{(\lambda+\hat{V}\omega+\hat{P}\delta+\hat{N})^{2}}]\\\
V=\mathbb{E}_{\mu}\quantity[\frac{\omega}{\lambda+\hat{V}\omega+\hat{P}\delta+\hat{N}}]\\\
P=\mathbb{E}_{\mu}\quantity[\zeta\frac{\hat{m}^{2}\bar{\theta}^{2}+\hat{q}\omega^{2}}{(\lambda+\hat{V}\omega+\hat{P}\delta+\hat{N})^{2}}]\\\
N=\mathbb{E}_{\mu}\quantity[\frac{\hat{m}^{2}\bar{\theta}^{2}+\hat{q}\omega}{(\lambda+\hat{V}\omega+\hat{P}\delta+\hat{N})^{2}}]\end{cases}$
(16)

where $\xi\sim\mathcal{N}\quantity(0,1)$ and

$\displaystyle\mathcal{Z}_{0}(y,\omega,V)$
$\displaystyle=\frac{1}{2}\operatorname*{erfc}\quantity(-\frac{y\omega}{\sqrt{2(V+\tau^{2})}})\,,$
(17) $\displaystyle f_{g}(y,\omega,V,P,N)$
$\displaystyle=\frac{1}{V}\quantity(\mathcal{P}_{Vg(\cdot;y,P,N)}(\omega)-\omega)\,,$

where $\mathcal{P}_{Vf(\cdot)}(\omega)$ indicates the proximal operator of a
function $f:\mathbb{R}\to\mathbb{R}$.

Additionally, we provide closed form expressions for the robustness and
usefulness metrics defined in Eqs. 8 and 9 as functions of the previously
mentioned overlaps

$\mathcal{U}_{\boldsymbol{\theta}_{0}}=\sqrt{\frac{2}{\pi}}\frac{\rho}{\sqrt{\rho+\tau^{2}}}\,,\quad\mathcal{R}_{\boldsymbol{\theta}_{0}}=\mathcal{U}-\varepsilon_{g}\frac{a}{\sqrt{n}}\,.$
(18)

The proof of this result can be found in Appendix A for what concerns the form
of the fixed-point equations and in Appendix B for the form of the error
metrics. It is based on rephrasing the minimisation in Eq. 7 as a constrained
optimisation problem. The new form makes it easy to map to the case already
proven in [32]. The parameters $m,q,P,N,A$ and $F$ appearing in the previous
statement have a simple interpretation, they are the values around which the
teacher-student and student-student overlaps concentrate in high dimension

$\displaystyle m$
$\displaystyle=\frac{1}{d}\mathbb{E}_{\mathcal{D}}\quantity[\boldsymbol{\theta}_{0}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\boldsymbol{x}}}\hat{\boldsymbol{\theta}}]\,,$
$\displaystyle\ q$
$\displaystyle=\frac{1}{d}\mathbb{E}_{\mathcal{D}}\quantity[\hat{\boldsymbol{\theta}}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\boldsymbol{x}}}\hat{\boldsymbol{\theta}}]\,,$
(19) $\displaystyle P$
$\displaystyle=\frac{1}{d}\mathbb{E}_{\mathcal{D}}\quantity[\hat{\boldsymbol{\theta}}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\delta}}\hat{\boldsymbol{\theta}}]\,,$
$\displaystyle\ N$
$\displaystyle=\frac{1}{d}\mathbb{E}_{\mathcal{D}}\quantity[\norm{\hat{\boldsymbol{\theta}}}_{2}^{2}]\,,$
$\displaystyle A$
$\displaystyle=\frac{1}{d}\mathbb{E}_{\mathcal{D}}\quantity[\hat{\boldsymbol{\theta}}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\upsilon}}\hat{\boldsymbol{\theta}}]\,,$
$\displaystyle\ F$
$\displaystyle=\frac{1}{d}\mathbb{E}_{\mathcal{D}}\quantity[\boldsymbol{\theta}_{0}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\upsilon}}\hat{\boldsymbol{\theta}}]\,.$

The overlap $m$ describes the angle between student estimate
$\hat{\boldsymbol{\theta}}$ and the ground truth teacher vector
$\boldsymbol{\theta}_{0}$, the overlap $q$ represents the data-weighted norm
of the weights, $N$ is exactly the norm of the weights, $P$ quantifies the
norm of the weights scaled by the defence direction, $A$ quantifies how much
the student lies in the attack geometry and $F$ quantifies the overlap between
teacher and student in the attack geometry.

It is important to note that all the summary statistics involved in the
statement of the theorem are finite-dimensional as the dimension increases,
and therefore the result is a fully asymptotic characterisation, in the sense
that it does not involve any high-dimensional object.

In Appendix C we provide an expansion of the fixed point equations in the high
sample complexity limit, in which the equations simplify. Additionally, we
show that the adversarial error converges to a constant in this limit.

##  IV Discussion of Main Results

$\boldsymbol{\theta}_{0}$$\hat{\boldsymbol{\theta}}$ABCDEFGH Figure 1:
Adversarial trade-off in our model occurs due to improved robustness of a
worse estimate $\hat{\boldsymbol{\theta}}$. The colour marks the true label of
the data points. The arrows indicate the adversarial attack perturbation.
There are four cases to be distinguished. Points F and E are correctly
classified after the perturbation. The points C and D contribute to
generalisation error. The perturbations on B and A cancel each other on
average. Only points H and G contribute to the boundary error. A worse angle
decreases the number of points contributing to boundary error at the cost of
these points contributing to generalisation error.

##### Adversarial Trade-Off

The adversarial error in Eq. 13 can be decomposed into a sum between
generalisation error and boundary error. Simplifying the formulas, we get

$E_{\mathrm{adv}}=E_{\mathrm{gen}}(\vartheta,\mathcal{U}_{\boldsymbol{\theta}_{0}})+\int_{0}^{\varepsilon_{g}\frac{A}{\sqrt{q}\sqrt{N}}}f(\xi;\vartheta,\mathcal{U}_{\boldsymbol{\theta}_{0}})\differential{\xi}$
(20)

where we introduce the variable $\vartheta=m/\sqrt{\rho q}$, directly related
to the angle between the teacher weights $\boldsymbol{\theta}_{0}$ and the
student estimate $\hat{\boldsymbol{\theta}}$ and define $f(\xi;\vartheta)$ to
be a positive function for $\xi\in[0,+\infty)$ and
$\forall\vartheta,\,\mathcal{U}_{\boldsymbol{\theta}_{0}}$.

On the one hand, the generalisation error is a monotonically decreasing
function of $\vartheta$. In other words, to improve generalisation error, it
is best to align well with $\boldsymbol{\theta}_{0}$. On the other hand, the
boundary error inversely depends on the angle: for a fixed attack strength,
the boundary error is a decreasing function of the angle as the integral with
fixed bounds increases. To reduce the boundary error, adversarial training
must choose an angle such that attacked samples are perturbed with respect to
the student estimate, but not the teacher estimate. This property hurts
generalisation, and is at the heart of the trade-off. In summary, a worse
student estimate $\hat{\boldsymbol{\theta}}$ decreases boundary error at the
cost of generalisation error, as we depict in Fig. 1.

The key insight for the rest of this paper, is that the boundary error
dominates adversarial error only when the student is able to align with the
teacher. Otherwise, the phenomena are driven by generalisation error.

In Appendix C, we prove that the adversarial error always goes to a constant

$\lim_{\alpha\to\infty}\partial_{\alpha}E_{\mathrm{adv}}=0\,,$ (21)

where the limit is taken after the high-dimensional proportional limit.
Additionally, we show that the constant to which $E_{\mathrm{adv}}$ converges,
can be zero only if $\tau=\varepsilon_{g}=0$.

In Section D.1, we show that the adversarial generalisation error can be
formulated in terms of Owen’s T function.

Figure 2:  We construct combinations of non-robust/non-useful features and
observe the (adversarial) generalisation error together with the boundary
error and the class preserving error as a function of the sample complexity.
We see a good agreement between the theory (lines) and finite size simulations
(points). The setting of this figure is described in Section H.1.

###  IV.1 Building Non-Robust, but Useful Features

To study the effect of robustness and usefulness on the error metrics, the
simplest model to consider is a SWFM with a single block. In the following, we
explain this setting with an experiment in Fig. 2. As we explained in the
previous section, generalisation error dominates the low sample complexity,
because the angle is not yet very good. Conversely, boundary error starts to
dominate once the student vector aligns with the teacher vector. Hence,
adversarial training $\varepsilon_{t}>0$ start to influence performance only
at high sample complexities. Furthermore, we provide asymptotic results for
the generalisation and boundary errors in Appendix C. We interpret both in
terms of

##### Usefulness

Usefulness controls the alignment between the student and the teacher
direction. At low usefulness the plateau reached by the generalisation error
$E_{\mathrm{gen}}$ in terms of the sample complexity is higher than in the
case of high usefulness, in which the generalisation error reaches a lower
value and hence better value. If in the high sample complexity region we have
that $\vartheta\to 1$ the plateau for the generalisation error is

$E_{\mathrm{gen}}\\!=\\!E_{\mathrm{gen}}\quantity(\vartheta,\mathcal{U}_{\boldsymbol{\theta}_{0}})\\!\underset{\alpha\rightarrow\infty}{=}\\!\frac{1}{\pi}\arccos(\sqrt{\frac{\pi}{2\rho}}\mathcal{U}_{\boldsymbol{\theta}_{0}})\,.$
(22)

We note that $\rho$ and $\mathcal{U}_{\boldsymbol{\theta}_{0}}$ are
responsible for the asymptotic value of the generalisation error. The key
quantities defining them are
$\boldsymbol{\Sigma}_{\boldsymbol{\boldsymbol{x}}}$ and
$\boldsymbol{\theta}_{0}$.

##### Robustness

High robustness implies a lower boundary term and low robustness a high
boundary term. Robust features have less samples within an attack range of the
student decision boundary. We can explain the boundary error as a function of
both $\mathcal{U}_{\boldsymbol{\theta}_{0}}$ and
$\mathcal{R}_{\boldsymbol{\theta}_{0}}$, it is given by

$\int_{0}^{\varepsilon_{g}\frac{1}{\sqrt{q}}(\mathcal{U}_{\boldsymbol{\theta}_{0}}-\mathcal{R}_{\boldsymbol{\theta}_{0}})}f(\xi;\vartheta,\mathcal{U}_{\boldsymbol{\theta}_{0}})\differential{\xi}$
(23)

Increasing the intensity of adversarial training reduces the boundary error.
However, this can only occur through a worsening of generalisation error.
Hence, the adversarial training reduces the usefulness in favour of higher
robustness.

The CP error qualitatively mimics the adversarial error at low sample
complexities. In contrast, at high sample complexities, the CP error dips
below the adversarial error as more and more attacks are disregarded. The
dependency of the CP error on adversarial training also becomes apparent, as
it influences the CP error through the angle of alignment found between the
student and teacher.

Figure 3:  We show the adversarial errors as a function of the adversarial
defence strength in the case $\alpha\gg 1$. (Right) Defending features that
are on average pointed in the teacher direction leads to a trade-off. (Left)
Defending the features that are on average orthogonal to the teacher barely
increases generalisation error. These features can be defended at less cost.
Due to using an average over $\boldsymbol{\Sigma}_{\boldsymbol{\theta}}$, we
observe a trade-off at small $\varepsilon_{t}$. The setting of this figure is
described in Section H.2.

###  IV.2 Optimal Defence Geometry

Depending on the attack geometry $\boldsymbol{\Sigma}_{\boldsymbol{\upsilon}}$
one can choose different defence geometries
$\boldsymbol{\Sigma}_{\boldsymbol{\delta}}$ and ask if and for which,
protection without trade-off is possible. This question translates to asking
if we can minimise $A/\sqrt{qN}$ without decreasing the angle
$\vartheta=m/\sqrt{\rho q}$.

As explained in Appendix F we can split any attack in directions orthogonal to
the teacher and directions aligned with the teacher. Both have very different
roles in the adversarial trade-off. The directions orthogonal to the teacher
are simple to protect against. We can achieve it by reducing the norm of the
weights in these directions, effectively reducing $E_{\mathrm{adv}}$ to
$E_{\mathrm{gen}}$. The directions aligned to $\boldsymbol{\theta}_{0}$
however, are at the heart of the trade-off and cannot be regularised away.

We demonstrate this behaviour in Fig. 3. We consider two kinds of attacks, an
attack that is on average directed along the teacher direction and an attack
that is on average directed along a direction orthogonal to the teacher. We
protect against the attack geometry by setting
$\boldsymbol{\Sigma}_{\boldsymbol{\delta}}=\boldsymbol{\Sigma}_{\boldsymbol{\upsilon}}$
and examine, how the error metrics behave as the adversarial training strength
$\varepsilon_{t}$ increases.

###  IV.3 Directional Defences on Structured Data

A popular and successful idea in the adversarial literature is to defend non-
robust features more strongly. To precisely characterise this phenomenon we
build a SWFM with two blocks of equal relative size. Both blocks have the same
constant unity teacher vector, the first block has a much higher data variance
$\psi_{1}$ than the second. This construction induces high robustness for the
first block of features and low robustness for the second half. We then
consider three different trace-normalised protection matrices
$\boldsymbol{\Sigma}_{\boldsymbol{\delta}}$ corresponding to three defensive
strategies and we show the results in Fig. 4 (Left). The attack matrix
$\boldsymbol{\Sigma}_{\boldsymbol{\upsilon}}$ is uniform and this implies that
we will inevitably see a trade-off.

The defensive strategies are dependent on the robustness of the features. In
Appendix C we explain how our expression for the boundary term in Eq. 23 is
affected by the variance of the features. Features with a low variance
increase the total boundary error and are hence non-robust, conversely,
features with a high variance decrease the boundary error and are more robust.
We compare the following defence strategies in the experiment in Fig. 4
(Left).

  * •

Defend the robust features \- In the high sample complexity regime, we observe
also a trade-off between boundary and generalisation error. There is no need
to tune the angle so strongly, but conversely, there are still a lot of weakly
protected low-robustness features. This leads to a high boundary error.
Interestingly, such adversarial training leads to increased boundary error in
the small sample complexity regime.

  * •

Uniformly defend all the features \- The trade-off achieved by an uniform
defence is only slightly weaker than the trade-off achieved by protecting the
non-robust features.

  * •

Defend the non-robust features \- In the high sample complexity ratio,
protecting the non-robust features improves adversarial generalisation error.
This provokes a higher trade-off in generalisation error.

In Appendix G we perform the same experiment on some archetypical image
datasets. We project the data onto the first principal components, use an
empirical measure of robustness inspired from Eq. 9 to identify robust
components and observe a qualitatively similar behaviour in defensive
strategies when we consider the explained variance of the components to define
the defence geometry.

Realistic datasets usually have power-law distributed eigenvalues on the
covariance matrix. We show two experiments with a power-law BFM in Fig. 4
(Right).

The boundary/generalisation error is independent from the tail of the power-
law in the high sample complexity limit and $\varepsilon_{t}=0$. The total
usefulness and the noise level determine the asymptotic values. Adversarial
training with $\varepsilon_{g}>0$ decreases the adversarial error and the
boundary term monotonically with the power-law exponent. Heavier tails
increase the total number of robust features and thus more features are
sensible to the attack. Conversely, weaker tails reduce the number of robust
samples. This phenomenology considers different decay coefficients $\beta$ for
$\boldsymbol{\Sigma}_{\boldsymbol{\boldsymbol{x}}}$ keeping fixed the total
usefulness. We assume an identity teacher covariance, and uniform protection
and attack.

Figure 4:  (Left) We show the behaviour of a SWFM consisting equally of
features with high and low robustness, which correspond to features with high
or low variance in the data. We can study the effect of protecting either
feature category more or of protecting all features uniformly. Each strategy
leads to a different asymptotic trade-off as the adversarial training strength
$\varepsilon_{t}$ increases. (Right) (Top) Adversarial training tunes the
trade-off generalisation/boundary error even in the high sample complexity
regime. (Bottom) The power-law spectrum of the data does not by itself affect
the (adversarial) generalisation performance in the $\alpha\gg 1$ regime
without adversarial training. The relevant metric for $\varepsilon_{t}=0$ is
the usefulness as explained in Section IV.1. If $\varepsilon_{t}>0$, the
metrics depend on $\beta$. A higher coefficient increases the percentage of
non-robust features. The setting of this figure is described in Section H.3.

The uniform defence strategy performs well as it successfully defends the non-
robust features, which are prioritised when acting on all of the features. The
robust features are less affected by the perturbation as they have a bigger
margin. Weaker tails thus imply a less effective identity protection.

###  IV.4 Approximating Adversarial Training as a Data-Dependent
Regularisation

Figure 5:  (Left) Adversarial training is not just an
$\ell_{2}$-regularisation, we show the value of the generalisation error
$E_{\mathrm{gen}}$ as a function of the sample complexity where the parameter
$\lambda$ is chosen such that it minimises the generalisation error. (Right)
We present a comparison of the learning curves after adversarial training
(Top) and the ones for the equivalent problem Eq. 24 (Bottom). The setting of
this figure is described in Section H.4.

Adversarial training can be understood as an $\ell_{2}$ regularisation acting
on non-robust features. It is, however, not only an $\ell_{2}$-regularisation.
If this were true, we would see that the generalisation error with the optimal
choice for $\ell_{2}$-regularisation strength $\lambda$ would be independent
of the $\varepsilon_{t}$ used during training. Using the results of Theorem
III.1, we probe this independence in a model where all the BFM matrices are
the identity and we see that the optimal performances are indeed dependant on
$\varepsilon_{t}$. The optimal generalisation error as a function of the
sample complexity for three different values of $\varepsilon_{t}$ can be seen
in Fig. 5 (Left).

By expansion of the loss function, we provide the rationale for an approximate
loss to the one used in Eq. 7 where we separated two data dependant
regularisation terms. The details are shown in Appendix E. The form for the
approximate loss is

$\sum_{i=1}^{n}g\quantity(y_{i}\frac{\boldsymbol{\theta}^{\top}\boldsymbol{x}_{i}}{\sqrt{d}})+\tilde{\lambda}_{1}\frac{\boldsymbol{\theta}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\delta}}\boldsymbol{\theta}}{\,\sqrt{\boldsymbol{\theta}^{\top}\boldsymbol{\theta}}}+\tilde{\lambda}_{2}\boldsymbol{\theta}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\delta}}\boldsymbol{\theta}\,,$
(24)

where $\tilde{\lambda}_{1}$ and $\tilde{\lambda}_{2}$ depend on the model’s
parameters and perturbed margins of the points that shift sign under
perturbation. The approximate loss captures the main features of the
phenomenology of the learning curves, which we demonstrate in Fig. 5 (Right)
by comparing the adversarial training and the approximate problem. We see that
qualitatively the behaviour is similar between the adversarial training and
the approximate loss function where we fixed the values of
$\tilde{\lambda}_{1}$ and $\tilde{\lambda}_{2}$.

The two regularisation strengths mediated by $\tilde{\lambda}_{1}$ and
$\tilde{\lambda}_{2}$ emerge implicitly during adversarial training. They give
rise to a directional $\sqrt{\ell_{2}}+\ell_{2}$ regularisation. Contrary to
an $\ell_{2}$-regularisation, the $\sqrt{\ell_{2}}$ term indicates a
regularisation linearly proportional to the norm of the student vector.

The dependence of $\tilde{\lambda}_{2}$ on the perturbed margins of the points
that shift sign under perturbation, is implicitly a dependence on the number
of non-robust features. This intuitively explains the phenomenology seen
previously in Fig. 4 on why the uniform defence strategy performed well. The
regularisation induced by adversarial training is stronger when the percentage
on non-robust features is higher.

###### Acknowledgements.

We thank Lenka Zdeborová for fruitful discussions and insightful ideas
regarding the class-preserving error, Lucas Clarte for useful discussions
about the relevant literature, Guillaume Dalle for help in with the numerical
implementation, Nikolaos Tsilivis for the discussion during the Cargese 2023
Workshop Statistical Physics and Machine Learning back together again, Pierre
Mergny for the always helpful clarifications about Random Matrix Theory, Paul
Krzakala for pointing relevant literature on adversarial training, and Julia
Kempe for the fruitful discussions. BL acknowledges support from the Choose
France - CNRS AI Rising Talents program, and FK from the Swiss National
Science Foundation grant SNFS OperaGOST (grant number $200390$).

## References

  * [1] Urte Adomaityte, Leonardo Defilippis, Bruno Loureiro, and Gabriele Sicuro, _High-dimensional robust regression under heavy-tailed data: Asymptotics and universality_ , 2023.
  * [2] Urte Adomaityte, Gabriele Sicuro, and Pierpaolo Vivo, _Classification of Heavy-tailed Features in High Dimensions: a Superstatistical Approach_ , October 2023, arXiv:2304.02912 [cond-mat, stat].
  * [3] Benjamin Aubin, Florent Krzakala, Lu Yue, and Lenka Zdeborová, _Generalization error in high-dimensional perceptrons: Approaching bayes error with convex optimization_ , Advances in Neural Information Processing Systems. 33, vol. 33, Curran Associates, Inc., 2020, pp. 12199–12210.
  * [4] Derek Bean, Peter J. Bickel, Noureddine El Karoui, and Bin Yu, _Optimal m-estimation in high-dimensional regression_ , Proceedings of the National Academy of Sciences 110 (2013), no. 36, 14563–14568.
  * [5] Arjun Nitin Bhagoji, Daniel Cullina, and Prateek Mittal, _Lower bounds on adversarial robustness from optimal transport_ , Advances in Neural Information Processing Systems 32 (2019).
  * [6] Blake Bordelon, Abdulkadir Canatar, and Cengiz Pehlevan, _Spectrum dependent learning curves in kernel regression and wide neural networks_ , Proceedings of the 37th International Conference on Machine Learning (Hal Daumé III and Aarti Singh, eds.), Proceedings of Machine Learning Research, vol. 119, PMLR, 13–18 Jul 2020, pp. 1024–1034.
  * [7] Stephen Boyd and Lieven Vandenberghe, _Convex optimization_ , Cambridge University Press, 2004.
  * [8] Luis M. Briceño-Arias, Giovanni Chierchia, Emilie Chouzenoux, and Jean-Christophe Pesquet, _A random block-coordinate douglas–rachford splitting method with low computational complexity for binary logistic regression_ , Computational Optimization and Applications 72 (2019), no. 3, 707–726.
  * [9] Lucas Andry Clarté, Bruno Loureiro, Florent Krzakala, and Lenka Zdeborová, _On double-descent in uncertainty quantification in overparametrized models_ , vol. 206, PMLR Proceedings of Machine Learning Research, 2023, pp. 7089–7125.
  * [10] , _Theoretical characterization of uncertainty in high-dimensional linear classification_ , Machine Learning: Science and Technology 4 (2023), no. 2, 025029.
  * [11] Chen Dan, Yuting Wei, and Pradeep Ravikumar, _Sharp statistical guaratees for adversarially robust gaussian classification_ , International Conference on Machine Learning, PMLR, 2020, pp. 2345–2355.
  * [12] Yatin Dandi, Ludovic Stephan, Florent Krzakala, Bruno Loureiro, and Lenka Zdeborová, _Universality laws for gaussian mixtures in generalized linear models_ , 2023.
  * [13] Oussama Dhifallah and Yue M. Lu, _A precise performance analysis of learning with random features_ , 2020.
  * [14] David L. Donoho, Arian Maleki, and Andrea Montanari, _Message passing algorithms for compressed sensing: I. motivation and construction_ , 2010 IEEE Information Theory Workshop on Information Theory (ITW 2010, Cairo), 2010, pp. 1–5.
  * [15] Federica Gerace, Florent Krzakala, Bruno Loureiro, Ludovic Stephan, and Lenka Zdeborová, _Gaussian universality of perceptrons with random labels_ , 2023.
  * [16] Federica Gerace, Bruno Loureiro, Florent Krzakala, Marc Mézard, and Lenka Zdeborová, _Generalisation error in learning with random features and the hidden manifold model*_ , Journal of Statistical Mechanics: Theory and Experiment 2021 (2021), no. 12, 124013.
  * [17] Cédric Gerbelot, Alia Abbara, and Florent Krzakala, _Asymptotic errors for high-dimensional convex penalized linear regression beyond gaussian matrices_ , Proceedings of Thirty Third Conference on Learning Theory (Jacob Abernethy and Shivani Agarwal, eds.), Proceedings of Machine Learning Research, vol. 125, PMLR, 09–12 Jul 2020, pp. 1682–1713.
  * [18] Cédric Gerbelot and Raphaël Berthier, _Graph-based approximate message passing iteration_ , Information and Inference: A Journal of the IMA 12 (2023), no. 4, 2562–2628.
  * [19] C. Godfrey, H. Kvinge, E. Bishoff, M. Mckay, D. Brown, T. Doster, and E. Byler, _How many dimensions are required to find an adversarial example?_ , 2023 IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops (CVPRW) (Los Alamitos, CA, USA), IEEE Computer Society, jun 2023, pp. 2353–2360.
  * [20] Sebastian Goldt, Bruno Loureiro, Galen Reeves, Florent Krzakala, Marc Mezard, and Lenka Zdeborová, _The gaussian equivalence of generative models for learning with shallow neural networks_ , Proceedings of Machine Learning Research. 145, 2021, pp. 426–471.
  * [21] Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy, _Explaining and harnessing adversarial examples_ , 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings (Yoshua Bengio and Yann LeCun, eds.), 2015.
  * [22] Y. Gordon, _On milman’s inequality and random subspaces which escape through a mesh in ${\mathbb{r}}^{n}$_, Geometric Aspects of Functional Analysis (Berlin, Heidelberg) (Joram Lindenstrauss and Vitali D. Milman, eds.), Springer Berlin Heidelberg, 1988, pp. 84–106.
  * [23] Andrew Ilyas, Shibani Santurkar, Dimitris Tsipras, Logan Engstrom, Brandon Tran, and Aleksander Madry, _Adversarial Examples Are Not Bugs, They Are Features_ , Advances in Neural Information Processing Systems, vol. 32, Curran Associates, Inc., 2019.
  * [24] Adel Javanmard and Andrea Montanari, _State evolution for general approximate message passing algorithms, with applications to spatial coupling_ , Information and Inference: A Journal of the IMA 2 (2013), no. 2, 115–144.
  * [25] Adel Javanmard and Mahdi Soltanolkotabi, _Precise statistical analysis of classification accuracies for adversarial training_ , The Annals of Statistics 50 (2022), no. 4, 2127–2156.
  * [26] Adel Javanmard, Mahdi Soltanolkotabi, and Hamed Hassani, _Precise tradeoffs in adversarial training for linear regression_ , Proceedings of Thirty Third Conference on Learning Theory (Jacob Abernethy and Shivani Agarwal, eds.), Proceedings of Machine Learning Research, vol. 125, PMLR, 09–12 Jul 2020, pp. 2034–2078.
  * [27] N.E. Korotkov and A.N. Korotkov, _Integrals related to the error function (1st ed.)_ , Chapman and Hall/CRC, 2020.
  * [28] Alex Krizhevsky, _Learning Multiple Layers of Features from Tiny Images_ (en).
  * [29] Florent Krzakala, Marc Mézard, Francois Sausset, Yifan Sun, and Lenka Zdeborová, _Probabilistic reconstruction in compressed sensing: algorithms, phase diagrams, and threshold achieving matrices_ , Journal of Statistical Mechanics: Theory and Experiment 2012 (2012), no. 08, P08009.
  * [30] Zhenyu Liao, Romain Couillet, and Michael W Mahoney, _A random matrix analysis of random fourier features: beyond the gaussian kernel, a precise phase transition, and the corresponding double descent_ , Advances in Neural Information Processing Systems (H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, eds.), vol. 33, Curran Associates, Inc., 2020, pp. 13939–13950.
  * [31] Bruno Loureiro, Cedric Gerbelot, Maria Refinetti, Gabriele Sicuro, and Florent Krzakala, _Fluctuations, bias, variance and ensemble of learners: Exact asymptotics for convex losses in high-dimension_ , Proceedings of the 39th International Conference on Machine Learning (Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, eds.), Proceedings of Machine Learning Research, vol. 162, PMLR, 17–23 Jul 2022, pp. 14283–14314.
  * [32] Bruno Loureiro, Cédric Gerbelot, Hugo Cui, Sebastian Goldt, Florent Krzakala, Marc Mézard, and Lenka Zdeborová, _Learning curves of generic features maps for realistic datasets with a teacher-student model*_ , Journal of Statistical Mechanics: Theory and Experiment 2022 (2022), no. 11, 114001.
  * [33] Bruno Loureiro, Gabriele Sicuro, Cedric Gerbelot, Alessandro Pacco, Florent Krzakala, and Lenka Zdeborová, _Learning gaussian mixtures with generalized linear models: Precise asymptotics in high-dimensions_ , Advances in Neural Information Processing Systems. 34, 2021.
  * [34] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu, _Towards deep learning models resistant to adversarial attacks_ , 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings, OpenReview.net, 2018.
  * [35] Xiaoyi Mai, Zhenyu Liao, and Romain Couillet, _A large scale analysis of logistic regression: Asymptotic performance and new insights_ , ICASSP 2019 - 2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2019, pp. 3357–3361.
  * [36] Song Mei and Andrea Montanari, _The generalization error of random features regression: Precise asymptotics and the double descent curve_ , Communications on Pure and Applied Mathematics 75 (2022), no. 4, 667–766.
  * [37] M. Mezard, G. Parisi, and M.A. Virasoro, _Spin glass theory and beyond: An introduction to the replica method and its applications_ , World Scientific Lecture Notes In Physics, World Scientific Publishing Company, 1987.
  * [38] Marc Mezard and Andrea Montanari, _Information, physics, and computation_ , Oxford University Press, 2009.
  * [39] Francesca Mignacco, Florent Krzakala, Yue Lu, Pierfrancesco Urbani, and Lenka Zdeborova, _The role of regularization in classification of high-dimensional noisy gaussian mixture_ , International conference on machine learning, PMLR, 2020, pp. 6874–6883.
  * [40] Andrea Montanari and Basil Saeed, _Universality of empirical risk minimization_ , 2022.
  * [41] Martin Mächler, _Accurately Computing log(1 - exp( - |a|)) Assessed by the Rmpfr package_ , 2012.
  * [42] Edward W. Ng and Murray Geller, _A table of integrals of the error functions._ , Journal of Research of the National Bureau of Standards, Section B: Mathematical Sciences (1969), 1.
  * [43] Note our results also hold under the assumption of $\boldsymbol{\theta}_{0}\sim\mathcal{N}\quantity(\boldsymbol{0},\boldsymbol{\Sigma}_{\boldsymbol{\theta}})$.
  * [44] Koki Okajima, Xiangming Meng, Takashi Takahashi, and Yoshiyuki Kabashima, _Average case analysis of lasso under ultra sparse conditions_ , Proceedings of The 26th International Conference on Artificial Intelligence and Statistics (Francisco Ruiz, Jennifer Dy, and Jan-Willem van de Meent, eds.), Proceedings of Machine Learning Research, vol. 206, PMLR, 25–27 Apr 2023, pp. 11317–11330.
  * [45] D. B. Owen, _A table of normal integrals_ , Communications in Statistics - Simulation and Computation 9 (1980), no. 4, 389–419.
  * [46] Donald B. Owen, _Tables for Computing Bivariate Normal Probabilities_ , The Annals of Mathematical Statistics 27 (1956), no. 4, 1075 – 1090.
  * [47] Nicolas Papernot, Patrick McDaniel, Somesh Jha, Matt Fredrikson, Z Berkay Celik, and Ananthram Swami, _The limitations of deep learning in adversarial settings_ , 2016 IEEE European symposium on security and privacy (EuroS&P), IEEE, 2016, pp. 372–387.
  * [48] Neal Parikh and Stephen Boyd, _Proximal algorithms_ , Found. Trends Optim. 1 (2014), no. 3, 127–239.
  * [49] Svetlana Pavlitska, Nico Lambing, and J. Marius Zöllner, _Adversarial attacks on traffic sign recognition: A survey_ , 2023 3rd International Conference on Electrical, Computer, Communications and Mechatronics Engineering (ICECCME), Tenerife, Spain, 19-21 July 2023, Institute of Electrical and Electronics Engineers (IEEE), 2023, 46.23.03; LK 01, p. 1–6 (english).
  * [50] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay, _Scikit-learn: Machine learning in Python_ , Journal of Machine Learning Research 12 (2011), 2825–2830.
  * [51] Fabian Pedregosa, _How to Evaluate the Logistic Loss and not NaN trying_ , September 2019.
  * [52] Luca Pesce, Florent Krzakala, Bruno Loureiro, and Ludovic Stephan, _Are Gaussian data all you need? The extents and limits of universality in high-dimensional generalized linear estimation_ , Proceedings of the 40th International Conference on Machine Learning (Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, eds.), Proceedings of Machine Learning Research, vol. 202, PMLR, 23–29 Jul 2023, pp. 27680–27708.
  * [53] Aditi Raghunathan, Sang Michael Xie, Fanny Yang, John Duchi, and Percy Liang, _Understanding and mitigating the tradeoff between robustness and accuracy. proceedings of machine learning research._ , International Conference on Machine Learning, PMLR, 2020.
  * [54] Sundeep Rangan, _Generalized approximate message passing for estimation with random linear mixing_ , 2011 IEEE International Symposium on Information Theory Proceedings, 2011, pp. 2168–2172.
  * [55] Sundeep Rangan, Philip Schniter, Erwin Riegler, Alyson K. Fletcher, and Volkan Cevher, _Fixed points of generalized approximate message passing with arbitrary matrices_ , IEEE Transactions on Information Theory 62 (2016), no. 12, 7464–7474.
  * [56] Antônio H. Ribeiro, Dave Zachariah, Francis Bach, and Thomas B. Schön, _Regularization properties of adversarially-trained linear regression_ , 2023.
  * [57] Kevin Roth, Yannic Kilcher, and Thomas Hofmann, _Adversarial Training is a Form of Data-dependent Operator Norm Regularization_ , Advances in Neural Information Processing Systems, vol. 33, Curran Associates, Inc., 2020, pp. 14973–14985.
  * [58] Ludwig Schmidt, Shibani Santurkar, Dimitris Tsipras, Kunal Talwar, and Aleksander Madry, _Adversarially Robust Generalization Requires More Data_ , Advances in neural information processing systems 31 (2018).
  * [59] Dominik Schröder, Hugo Cui, Daniil Dmitriev, and Bruno Loureiro, _Deterministic equivalent and error universality of deep random features learning_ , Proceedings of the 40th International Conference on Machine Learning (Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, eds.), Proceedings of Machine Learning Research, vol. 202, PMLR, 23–29 Jul 2023, pp. 30285–30320.
  * [60] Eero P Simoncelli and Bruno A Olshausen, _Natural Image Statistics and Neural Representation_ , Annual Review of Neuroscience 24 (2001), no. 1, 1193–1216 (en).
  * [61] Arun Sai Suggala, Adarsh Prasad, Vaishnavh Nagarajan, and Pradeep Ravikumar, _Revisiting adversarial risk_ , The 22nd International Conference on Artificial Intelligence and Statistics, PMLR, 2019, pp. 2331–2339.
  * [62] Pragya Sur and Emmanuel J. Candès, _A modern maximum-likelihood theory for high-dimensional logistic regression_ , Proceedings of the National Academy of Sciences 116 (2019), no. 29, 14516–14525.
  * [63] Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus, _Intriguing properties of neural networks_ , February 2014, arXiv:1312.6199 [cs].
  * [64] Hossein Taheri, Ramtin Pedarsani, and Christos Thrampoulidis, _Asymptotic behavior of adversarial training in binary linear classification_ , IEEE Trans. Neural Netw. Learn. Syst. PP (2023) (en).
  * [65] Takashi Takahashi and Yoshiyuki Kabashima, _Macroscopic analysis of vector approximate message passing in a model-mismatched setting_ , IEEE Transactions on Information Theory 68 (2022), no. 8, 5579–5600.
  * [66] Christos Thrampoulidis, Samet Oymak, and Babak Hassibi, _The gaussian min-max theorem in the presence of convexity_ , 2015.
  * [67] Christos Thrampoulidis, Samet Oymak, and Babak Hassibi, _Regularized Linear Regression: A precise analysis of the estimation error_ , Proceedings of The 28th Conference on Learning Theory (Paris, France) (Peter Grünwald, Elad Hazan, and Satyen Kale, eds.), Proceedings of Machine Learning Research, vol. 40, PMLR, 03–06 Jul 2015, pp. 1683–1709.
  * [68] Nikolaos Tsilivis and Julia Kempe, _What can the neural tangent kernel tell us about adversarial robustness?_ , Advances in Neural Information Processing Systems 35 (2022), 18116–18130.
  * [69] Nikolaos Tsilivis, Jingtong Su, and Julia Kempe, _Can we achieve robustness from data alone?_ , ICML Workshop on New Frontiers in Adversarial Machine Learning, 2022.
  * [70] Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry, _Robustness may be at odds with accuracy_ , International Conference on Learning Representations, 2019.
  * [71] V. Vapnik, _Principles of Risk Minimization for Learning Theory_ , Advances in Neural Information Processing Systems, vol. 4, Morgan-Kaufmann, 1991.
  * [72] Matteo Vilucchio, Emanuele Troiani, Vittorio Erba, and Florent Krzakala, _Asymptotic characterisation of robust empirical risk minimisation performance in the presence of outliers_ , 2023.
  * [73] Martin J Wainwright and Eero Simoncelli, _Scale Mixtures of Gaussians and the Statistics of Natural Images_ , Advances in Neural Information Processing Systems, vol. 12, MIT Press, 1999.
  * [74] Alexander Wei, Wei Hu, and Jacob Steinhardt, _More than a toy: Random matrix models predict how real-world neural representations generalize_ , Proceedings of the 39th International Conference on Machine Learning (Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, eds.), Proceedings of Machine Learning Research, vol. 162, PMLR, 17–23 Jul 2022, pp. 23549–23588.
  * [75] Stephen J. Wright, Robert D. Nowak, and MÁrio A. T. Figueiredo, _Sparse reconstruction by separable approximation_ , IEEE Transactions on Signal Processing 57 (2009), no. 7, 2479–2493.
  * [76] Han Xiao, Kashif Rasul, and Roland Vollgraf, _Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms_ , arXiv preprint arXiv:1708.07747 (2017).
  * [77] Lechao Xiao, Hong Hu, Theodor Misiakiewicz, Yue Lu, and Jeffrey Pennington, _Precise learning curves and higher-order scalings for dot-product kernel regression_ , Advances in Neural Information Processing Systems 35 (2022), 4558–4570.
  * [78] Lenka Zdeborová and Florent Krzakala, _Statistical physics of inference: thresholds and algorithms_ , Advances in Physics 65 (2016), no. 5, 453–552.
  * [79] Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan, _Theoretically principled trade-off between robustness and accuracy_ , International conference on machine learning, PMLR, 2019, pp. 7472–7482.

##  Appendix A Proof of Main Result

In this Appendix we provide a proof of the fixed-point equations presented in
Theorem III.1. For a reader that is also acquainted with the tools of
statistical physics we derive the same formulas using the replica method in
Appendix I.

###  A.1 Notations and definitions

In this paper, we extensively employ the concepts of Moreau envelopes and
proximal operators, pivotal elements in convex analysis frequently encountered
in recent works on high-dimensional asymptotic of convex problems [7, 48]. For
an in-depth analysis of their properties, we refer the reader to the cited
literature. Here, we briefly outline their definition and the main properties
for context.

The Moreau envelope and the proximal operator associated to a scalar function
$f:\mathbb{R}\to\mathbb{R}$ are defined as

$\mathcal{M}_{Vf(\cdot)}(\omega)=\min_{x}\quantity[\frac{(x-\omega)^{2}}{2V}+f(x)]\,,\quad\mathcal{P}_{Vf(\cdot)}(\omega)=\operatorname*{arg\,min}_{x}\quantity[\frac{(x-\omega)^{2}}{2V}+f(x)]\,,$
(25)

where the $(\cdot)$ indicates the variable considered if the function is of
more variables. Generally one can consider the Moreau envelope or the proximal
with respect to just one of the inputs of a function depending on more
variables.

In the rest of the paper we will use the following proprieties of the Moreau
and Proximal that can be found in [48]. We will be using the envelope theorem
which states

$\partial_{\omega}\mathcal{M}_{Vg(y,\cdot)}(\omega)=V^{-1}\left(\omega-\mathcal{P}_{Vg(y,\cdot)}(\omega)\right)\,.$
(26)

###  A.2 Assumptions

For our results to hold we will need all the assumptions required in [32] for
the application of their results on the saddle point equations. Our
assumptions are thus all of the ones contained in [32], specified in Appendix
B.1. Additionally we need

(A1)

The attack and defence geometry $\boldsymbol{\Sigma}_{\boldsymbol{\delta}}$
and $\boldsymbol{\Sigma}_{\boldsymbol{\upsilon}}$ should be
$\boldsymbol{\Sigma}_{\boldsymbol{\upsilon}},\boldsymbol{\Sigma}_{\boldsymbol{\delta}}\succ
0$. The spectral distributions of the matrices
$\boldsymbol{\Sigma}_{\boldsymbol{\delta}},\boldsymbol{\Sigma}_{\boldsymbol{\upsilon}}$
converge to distributions such that the overlaps

$P=\frac{1}{d}\mathbb{E}_{\mathcal{D}}\quantity[\hat{\boldsymbol{\theta}}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\delta}}\hat{\boldsymbol{\theta}}]\,,\quad
A=\frac{1}{d}\mathbb{E}_{\mathcal{D}}\quantity[\hat{\boldsymbol{\theta}}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\upsilon}}\hat{\boldsymbol{\theta}}]\,,\quad
F=\frac{1}{d}\mathbb{E}_{\mathcal{D}}\quantity[\boldsymbol{\theta}_{0}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\upsilon}}\hat{\boldsymbol{\theta}}]\,,$
(27)

are well-defined. Additionally, the maximum singular values of them are
bounded with high probability when $n,p\to\infty$.

(A2)

The values
$\zeta_{i}=\operatorname{diag}(\mathrm{S}\boldsymbol{\Sigma}_{\boldsymbol{\delta}}\mathrm{S}^{\top})_{i}$,
$\upsilon_{i}=\operatorname{diag}(\mathrm{S}\boldsymbol{\Sigma}_{\boldsymbol{\upsilon}}\mathrm{S}^{\top})_{i}$
and
$\mathbf{f}_{i}=(\mathrm{S}\boldsymbol{\Sigma}_{\boldsymbol{\upsilon}}^{\top}\boldsymbol{\theta}_{0}/\sqrt{\rho})_{i}$,
where additionally
$\rho=\boldsymbol{\theta}_{0}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\boldsymbol{x}}}\boldsymbol{\theta}_{0}/d$,
$a=\boldsymbol{\theta}_{0}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\upsilon}}\boldsymbol{\theta}_{0}/d$,
$n=\boldsymbol{\theta}_{0}^{\top}\boldsymbol{\theta}_{0}/d$ and
$\bar{\boldsymbol{\theta}}=\mathrm{S}\boldsymbol{\Sigma}_{\boldsymbol{\boldsymbol{x}}}^{\top}\boldsymbol{\theta}_{0}/\sqrt{\rho}$
should have jointly a well defined limit when $n,p\to\infty$. More formally

$\frac{1}{d}\sum_{i=1}^{d}\delta\quantity(\omega-\omega_{i})\delta\quantity(\bar{\theta}-\bar{\theta}_{i})\delta\quantity(\zeta-\zeta_{i})\delta(\upsilon-\upsilon_{i})\delta(f-f_{i})\to\mu$
(28)

should converge for $n,p\to\infty$.

(A3)

The choice of the matrices $\boldsymbol{\Sigma}_{\boldsymbol{\delta}}$ and
$\boldsymbol{\Sigma}_{\boldsymbol{\upsilon}}$ should be independent of the
teacher vector $\boldsymbol{\theta}_{0}$.

###  A.3 Reformulation of the problem

The problem that we start from can be found in Eq. 6 and consists of finding a
minimiser $\hat{\boldsymbol{\theta}}$ of

$\sum_{i=1}^{n}\max_{\norm{\boldsymbol{\delta}_{i}}_{\boldsymbol{\Sigma}_{\boldsymbol{\delta}}^{-2}}\leq\varepsilon_{t}}g\quantity(y_{i}\frac{\boldsymbol{\theta}^{\top}\quantity(\boldsymbol{x}_{i}+\boldsymbol{\delta}_{i})}{\sqrt{d}})+r(\boldsymbol{\theta})\,,$
(29)

where we remind that the regularisation function
$r:\mathbb{R}^{d}\rightarrow\mathbb{R}$ is convex and the loss function
$g:\mathbb{R}\rightarrow\mathbb{R}$ is non increasing, meaning that $x_{1}\leq
x_{2}$ implies $g(x_{1})\geq g(x_{2})$.

Because of the last propriety we have that the $\boldsymbol{\delta}_{i}$ that
solves the inner maximisation problem is
$\boldsymbol{\delta}_{i}=-\varepsilon_{t}y_{i}\boldsymbol{\Sigma}_{\boldsymbol{\delta}}\boldsymbol{\theta}/\norm{\boldsymbol{\theta}}_{2}$.
Thus we actually want to minimise

$\sum_{i=1}^{n}g\quantity(y_{i}\frac{\boldsymbol{\theta}^{\top}\boldsymbol{x}_{i}}{\sqrt{d}}-\varepsilon_{t}\frac{\boldsymbol{\theta}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\delta}}\boldsymbol{\theta}}{\sqrt{d}\,\norm{\boldsymbol{\theta}}_{2}})+r(\boldsymbol{\theta})\,.$
(30)

We can introduce two constrains to rewrite the minimisation as

$\sum_{i=1}^{n}g\quantity(y_{i},\frac{\boldsymbol{\theta}^{\top}\boldsymbol{x}_{i}}{\sqrt{d}}-y_{i}\varepsilon_{t}\frac{P}{\sqrt{N}})+r(\boldsymbol{\theta})\quad\text{
such that }\quad
dP=\boldsymbol{\theta}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\delta}}\boldsymbol{\theta}\,,\,\,dN=\norm{\boldsymbol{\theta}}_{2}^{2}\,.$
(31)

The Lagrangian form of this problem reads

$\displaystyle\mathcal{L}(\boldsymbol{\theta},\boldsymbol{z},\boldsymbol{s},P,\hat{P},N,\hat{N})=$
$\displaystyle
g\quantity(\boldsymbol{z}-\frac{\varepsilon_{t}P}{\sqrt{N}}\boldsymbol{y})+r(\boldsymbol{\theta})+\boldsymbol{s}\quantity(\frac{1}{\sqrt{d}}\boldsymbol{X}\boldsymbol{\theta}-\boldsymbol{z})+$
(32)
$\displaystyle\hat{P}\quantity(\boldsymbol{\theta}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\delta}}\boldsymbol{\theta}-dP)+\hat{N}\quantity(\boldsymbol{\theta}^{\top}\boldsymbol{\theta}-dN)$

where we have simplified the notations by introducing

$g\quantity(\boldsymbol{z}-\frac{\varepsilon_{t}P}{\sqrt{N}}\boldsymbol{y})=\sum_{i=1}^{n}g\quantity(y_{i},z_{i}-y_{i}\varepsilon_{t}\frac{P}{\sqrt{N}})\,,$
(33)

and defined the feature matrix $\boldsymbol{X}\in\mathbb{R}^{n\times d}$.

###  A.4 Fixed Point Equations for the constrain variables

To obtain the equations for $P,\hat{P},N,\hat{N}$ we go back to the complete
optimisation problem

$\displaystyle\sup_{\boldsymbol{s},\hat{P},\hat{N}}\inf_{\boldsymbol{\theta},\boldsymbol{z},P,N}$
$\displaystyle\
\mathcal{L}(\boldsymbol{\theta},\boldsymbol{z},\boldsymbol{s},P,\hat{P},N,\hat{N})=\sup_{\boldsymbol{s},\hat{P},\hat{N}}\Bigg{[}\inf_{\boldsymbol{\theta}}\quantity[r(\boldsymbol{\theta})+\hat{P}\boldsymbol{\theta}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\delta}}\boldsymbol{\theta}+\hat{N}\boldsymbol{\theta}^{\top}\boldsymbol{\theta}+\frac{1}{\sqrt{d}}\boldsymbol{s}^{\top}\boldsymbol{X}\boldsymbol{\theta}]+$
(34) $\displaystyle\
\inf_{\boldsymbol{z},P,N}\quantity[g\quantity(\boldsymbol{z}-\frac{\varepsilon_{t}P}{\sqrt{N}}\boldsymbol{y})-\boldsymbol{s}^{\top}\boldsymbol{z}-d\hat{P}P-d\hat{N}N]\Bigg{]}$
$\displaystyle=\sup_{\boldsymbol{s},\hat{P},\hat{N}}\Bigg{[}\inf_{\boldsymbol{\theta}}\quantity[f(\boldsymbol{\theta})+\hat{P}\boldsymbol{\theta}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\delta}}\boldsymbol{\theta}+\hat{N}\boldsymbol{\theta}^{\top}\boldsymbol{\theta}+\frac{1}{\sqrt{d}}\boldsymbol{s}^{\top}\boldsymbol{X}\boldsymbol{\theta}]+\inf_{\boldsymbol{z}}\quantity[g(\boldsymbol{z})-\boldsymbol{s}^{\top}\boldsymbol{z}]+$
$\displaystyle\
\inf_{P,N}\quantity[\frac{\varepsilon_{t}P}{\sqrt{N}}\boldsymbol{s}^{\top}\boldsymbol{y}-d\hat{P}P-d\hat{N}N]\Bigg{]}$

We also consider the gradients with respect to the new variables

$\displaystyle\partialderivative{P}$
$\displaystyle=\frac{\varepsilon_{t}}{\sqrt{N}}\boldsymbol{s}^{\top}\boldsymbol{y}-d\hat{P}\,,\quad$
$\displaystyle\partialderivative{N}$
$\displaystyle=-\frac{\varepsilon_{t}P}{2\sqrt{N^{3}}}\boldsymbol{s}^{\top}\boldsymbol{y}-d\hat{N}\,,$
(35) $\displaystyle\partialderivative{\hat{P}}$
$\displaystyle=\boldsymbol{\theta}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\delta}}\boldsymbol{\theta}-dP\,,\quad$
$\displaystyle\partialderivative{\hat{N}}$
$\displaystyle=\boldsymbol{\theta}^{\top}\boldsymbol{\theta}-dN\,.$ (36)

###  A.5 Mapping of Saddle point Equations

To prove the form of the fixed point equations we would like to map a part of
them to already proven set of fixed point equations proved in [32]. The result
proven in the previously mentioned paper has been proven with the application
of Convex Gordon Min-Max theorem, that is a tight version of [22] developed by
[67, 66].

If we consider the values of the overlaps to be values we have that one can
prove the equations for $m,q,V$ and $\hat{m},\hat{q},\hat{V}$ as being a case
of a specific loss for Theorem 1 in [32], proven in Appendix B of the same
paper. For each fixed value of $P,N,\hat{P},\hat{N}$ which will be specified
afterwards. The mapping from the notation of this current paper to the other
one involves a different loss function and regularisation

$g(z)\leftrightarrow g\quantity(z-\varepsilon_{t}\frac{P}{\sqrt{N}})\,,\qquad
r(\boldsymbol{\theta})\leftrightarrow
r(\boldsymbol{\theta})+\hat{P}\boldsymbol{\theta}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\delta}}\boldsymbol{\theta}+\hat{N}\boldsymbol{\theta}^{\top}\boldsymbol{\theta}\,,$
(37)

where the first ones are the notations used in [32] and the second ones the
one used in this paper. For fixed values of $P,N,\hat{P},\hat{N}$ this can be
seen by comparing the Lagrangian formulation in Eq. 32 to the one in Eq.
(B.61) of [32]. If we consider that the regularisation is $\ell_{2}$ we have
that we can apply the equations with the effective regularisation that is
$\boldsymbol{\theta}^{\top}((\lambda/2+\hat{N})\mathbb{1}+\hat{P}\boldsymbol{\Sigma}_{\boldsymbol{\delta}})\boldsymbol{\theta}$,
under the previously stated assumptions

$\displaystyle\hat{m}$
$\displaystyle=\alpha\mathbb{E}_{\xi}\left[\int_{\mathbb{R}}\differential{y}\partial_{\omega}\mathcal{Z}_{0}f_{g}(\sqrt{q}\xi,P,N)\right]$
$\displaystyle\quad m$
$\displaystyle=\mathbb{E}_{\mu}\quantity[\frac{\hat{m}\bar{\theta}^{2}}{\lambda+\hat{V}\omega+\hat{P}\delta+\hat{N}}]$
(38) $\displaystyle\hat{q}$
$\displaystyle=\alpha\mathbb{E}_{\xi}\left[\int_{\mathbb{R}}\differential{y}\mathcal{Z}_{0}f_{g}^{2}(\sqrt{q}\xi,P,N)\right]$
$\displaystyle\quad q$
$\displaystyle=\mathbb{E}_{\mu}\quantity[\frac{\hat{m}^{2}\bar{\theta}^{2}\omega+\hat{q}\omega^{2}}{(\lambda+\hat{V}\omega+\hat{P}\delta+\hat{N})^{2}}]$
$\displaystyle\hat{V}$
$\displaystyle=-\alpha\mathbb{E}_{\xi}\left[\int_{\mathbb{R}}\differential{y}\mathcal{Z}_{0}\partial_{\omega}f_{g}(\sqrt{q}\xi,P,N)\right]$
$\displaystyle\quad V$
$\displaystyle=\mathbb{E}_{\mu}\quantity[\frac{\omega}{\lambda+\hat{V}\omega+\hat{P}\delta+\hat{N}}]$

where we have the same definitions for $\mathcal{Z}_{0}$ and $f_{g}$ as in the
Theorem III.1.

At optimality we want the gradients in Eqs. 35 and 36 to be equal to zero.
Thus these equations should be considered as equalities to zero also in the
limit. To find the limiting form of these equations we would like to apply
Theorem 5 of [32]. We can start from the condition for the gradients of the
dual variables. The function satisfies the assumptions of the theorem and thus
can be applied. To obtain the specific form

$P=\mathbb{E}\quantity[\zeta\frac{\hat{m}^{2}\bar{\theta}^{2}+\hat{q}\omega}{(\lambda+\hat{V}\omega+\hat{P}\delta+\hat{N})^{2}}]\,,\quad
N=\mathbb{E}\quantity[\frac{\hat{m}^{2}\bar{\theta}^{2}+\hat{q}\omega}{(\lambda+\hat{V}\omega+\hat{P}\delta+\hat{N})^{2}}]\,.$
(39)

For the other two equations we can remember that at optimality the value of
$\boldsymbol{s}$ is connected to the proximal operator and the function
$f_{g}$. We have that these functions are pseudo-Lipschitz and thus satisfy
the assumptions of the previously applied theorem. Thus the optimality
conditions read in the limit are

$\displaystyle\hat{P}$
$\displaystyle=\alpha\frac{\varepsilon_{t}}{\sqrt{N}}\mathbb{E}_{\xi}\quantity[\int\differential{y}\mathcal{Z}_{0}yf_{g}(\sqrt{q}\xi,P,N,\varepsilon_{t})]\,,$
(40) $\displaystyle\hat{N}$
$\displaystyle=-\alpha\frac{\varepsilon_{t}P}{2\sqrt{N^{3}}}\mathbb{E}_{\xi}\quantity[\int\differential{y}\mathcal{Z}_{0}yf_{g}(\sqrt{q}\xi,P,N,\varepsilon_{t})]\,,$

thus proving the set of equations.

Input: Matrix $\boldsymbol{X}\in\mathbb{R}^{n\times d}$, functions
$r(\boldsymbol{\theta}),g(z)\in\mathbb{R}$

Output: An estimate $\boldsymbol{\theta}\in\mathbb{R}^{d}$

1 $t\leftarrow 0$

2

3Initialise
$\boldsymbol{\theta}^{t}\in\mathbb{R}^{d},\boldsymbol{\tau}_{w}^{t}\in\mathbb{R}_{+}^{d}$

4 $\boldsymbol{s}^{t-1}\leftarrow\boldsymbol{0}\in\mathbb{R}^{n}$

5 $\boldsymbol{F}\leftarrow\boldsymbol{X}\odot\boldsymbol{X}$

6

7repeat

// Output node update

8
$\boldsymbol{\tau}_{\omega}^{t}\leftarrow\boldsymbol{F}\boldsymbol{\tau}_{w}^{t}$

9

10
$\boldsymbol{\omega}^{t}\leftarrow\boldsymbol{X}\boldsymbol{\theta}^{t}-\boldsymbol{s}^{t-1}\odot\boldsymbol{\tau}_{\omega}^{t}$

11

12
$P^{t}\leftarrow\frac{1}{d}\boldsymbol{\theta}^{t}\boldsymbol{\Sigma}_{\boldsymbol{\delta}}\boldsymbol{\theta}^{t}$

13

14
$N^{t}\leftarrow\frac{1}{d}\boldsymbol{\theta}^{t}\cdot\boldsymbol{\theta}^{t}$

15

16
$\boldsymbol{z}^{t}\leftarrow\mathcal{P}_{\boldsymbol{\tau}_{p}^{t}}\quantity[g(\cdot;P^{t},N^{t})]\quantity(\boldsymbol{\omega}^{t})$

17

18
$\boldsymbol{\tau}_{z}^{t}\leftarrow\boldsymbol{\tau}_{p}^{t}\odot\mathcal{P}^{\prime}_{\boldsymbol{\tau}_{p}^{t}}\quantity[g(\cdot;P^{t},N^{t})]\quantity(\boldsymbol{\omega}^{t})$

19

20
$\boldsymbol{s}^{t}\leftarrow(\boldsymbol{z}^{t}-\boldsymbol{\omega}^{t})\oslash\boldsymbol{\tau}_{p}^{t}$

21

22
$\boldsymbol{\tau}_{s}^{t}\leftarrow(\boldsymbol{1}-\boldsymbol{\tau}_{z}^{t}\oslash\boldsymbol{\tau}_{p}^{t})\oslash\boldsymbol{\tau}_{p}^{t}$

23

// Input node update

24
$\hat{P}^{t}\leftarrow\frac{\varepsilon_{t}}{\sqrt{N}}\frac{1}{d}\boldsymbol{s}^{\top}\boldsymbol{y}$

25

26
$\hat{N}^{t}\leftarrow-\frac{\varepsilon_{t}P}{2\sqrt{N^{3}}}\frac{1}{d}\boldsymbol{s}^{\top}\boldsymbol{y}$

27

28
$\boldsymbol{\tau}_{r}^{t}\leftarrow\boldsymbol{1}\oslash(\boldsymbol{F}^{\top}\boldsymbol{\tau}_{s}^{t})$

29

30
$\boldsymbol{r}^{t}\leftarrow\boldsymbol{\theta}^{t}+\boldsymbol{\tau}_{r}^{t}\odot\boldsymbol{x}^{\top}\boldsymbol{s}^{t}$

31

32
$\boldsymbol{\theta}^{t+1}\leftarrow\mathcal{P}_{\boldsymbol{\tau}_{r}^{t}}[r(\cdot;\hat{P}^{t},\hat{N}^{t})](r^{t})$

33

34
$\boldsymbol{\tau}_{x}^{t+1}\leftarrow\boldsymbol{\tau}_{r}^{t}\odot\mathcal{P}^{\prime}_{\boldsymbol{\tau}_{r}^{t}}[r(\cdot,\hat{P}^{t},\hat{N}^{t})](r^{t})$

35

36until  _Termination condition_

Algorithm 1 Adversarial Generalised Approximate Message Passing (advGAMP)

###  A.6 Generalised AMP mapping of our problem

In the landscape of high-dimensional statistical inference, Approximate
Message Passing (AMP) algorithms have emerged as a cornerstone for efficiently
solving problems like compress sensing [14, 29]. At their hearts AMP
algorithms are iterative schemes, inspired by the ISTA algorithm [75], that in
addition leverage the statistical properties of high-dimensional random
matrices to remove correlation at each step. A key feature of AMP algorithms
is their connection with state evolution (SE), a powerful analytical tool that
tracks the evolution of the AMP algorithm’s performance across iterations.
State evolution provides a set of deterministic equations that accurately
predict the algorithm’s behaviour in the limit of large system sizes, thus
offering deep insights into the convergence properties and asymptotic accuracy
of AMP algorithms. This method has been extensively used to understand
problems like the learning of Gaussian mixtures [33] or learning curves of
ensembling methods [31]. This kind of connection and algorithm has been also
know by statistical physicist [78].

In the case of estimation of an i.i.d. random vector observed through a linear
transform followed by a component-wise, probabilistic (possibly nonlinear)
measurement channel an optimal algorithm, called generalised approximate
message passing (GAMP) and its respective SE has been introduced by [54]. The
main lemma for the SE has been proven later by [24]. Thus the idea is that the
fixed point equations could be seen as the state evolution equations for a
specific Generalised AMP algorithm that minimises the equivalent minimisation
problem in Eq. 96. This way of proving the result also gives the advantage of
defining an algorithm the could in principle be run to estimate the vector
$\hat{\boldsymbol{\theta}}$.

In Algorithm 1, we present the advGAMP that will be the object of the study of
this subsection. The notation $\odot$ represents the component-wise product
and $\oslash$ the component-wise division. After an initialisation, we have to
update the variables alternating by output channel variables and input channel
variables until some convergence condition of the variables is reached.

This algorithm can be seen as a specialisation of a GAMP algorithm where the
denoising function change at each iteration because dependant on the constants
$P,N,\hat{P},\hat{N}$ that are updated in Lines 8, 9, 14, 15.

Enforcing these constraints at each step guarantees that the $\hat{P},\hat{N}$
(respectively Lines 14 and 15) variables will be such that they minimise the
Lagrangian with respect to the primal variables. Additionally for the way the
$P,N$ variables are updated in Algorithm 1 (respectively Lines 8 and 9) it is
guaranteed that the definition is satisfied. In other words these constraints
satisfy the conditions for having a zero gradient in Eqs. 35 and 36. Once
these constraints are enforced we have that the same steps for the proof of
Theorem 1 in [55] follows. Thus we also have that advGAMP is like an ADMM
algorithm where the dual step in the constraint variable are exact each time.

The SE equations corresponding to the GAMP algorithm defined in [54, 55]
correspond exactly the the equations in Eq. 38 with the dependence on the
constants $P,N,\hat{P},\hat{N}$. To prove the state evolution form for the new
variables one can apply Theorem 1 in [24] to the update for
$P,N,\hat{P},\hat{N}$ and obtain the results in Eq. 39.

###  A.7 Form for the overlaps $A$ and $F$

Similarly to before we want to find the high dimensional form for

$A=\frac{1}{d}\hat{\boldsymbol{\theta}}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\upsilon}}\hat{\boldsymbol{\theta}}\,,\quad
F=\frac{1}{d}\hat{\boldsymbol{\theta}}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\upsilon}}\boldsymbol{\theta}_{0}$
(41)

Again we can leverage Theorem 5 from [32] or Theorem 1 from [24] to obtain in
both cases

$A=\mathbb{E}_{\mu}\quantity[\upsilon\frac{\hat{m}^{2}\bar{\theta}^{2}\omega+\hat{q}\omega^{2}}{(\lambda+\hat{V}\omega+\hat{P}\delta+\hat{N})^{2}}]\,,\quad
F=\mathbb{E}_{\mu}\quantity[\frac{\hat{m}f\bar{\theta}}{\lambda+\hat{V}\omega+\hat{P}\delta+\hat{N}}]$
(42)

as explained before.

##  Appendix B Error metrics

As is common in machine learning, we want to see how the model trained
performs on different metrics. This section is devoted to defining the metrics
of our interest and expressing them as a function of the overlaps solutions of
the fixed-point equations in Theorem III.1. In general, we distinguish between
the strength of the training attack and indicate it as $\varepsilon_{t}$ and
the strength of the actual attacker considered in generalisation, which we
call $\varepsilon_{g}$. In each subsection, we provide the formula to compute
the value from the overlap solution of Eq. 15 or directly from a data set
generated with the distribution explained in Section II.

Some of these metrics will be computed using the method of “local fields”
where one can suppose the jointly Gaussian behaviour for
$(\hat{\boldsymbol{\theta}}^{\top}\boldsymbol{x}/\sqrt{d},\boldsymbol{\theta}_{0}^{\top}\boldsymbol{x}/\sqrt{d})$
with mean zero and covariance
$\boldsymbol{\sigma}=\bigl{(}\begin{smallmatrix}\rho&m\\\
m&q\end{smallmatrix}\bigr{)}$. We will refer to the following probability
distribution

$\differential{\mu}(\nu,\lambda)=\frac{1}{2\pi\sqrt{\det\boldsymbol{\sigma}}}\exp\quantity(-\frac{1}{2}\begin{pmatrix}\nu\\\
\lambda\end{pmatrix}^{\top}\boldsymbol{\sigma}^{-1}\begin{pmatrix}\nu\\\
\lambda\end{pmatrix})$ (43)

This method is explained at length in [10] and applies also in the case
considered here. For other computations we refer to the places where the
computation can be found in detail.

###  B.1 Generalisation

In machine learning, particularly in the context of adversarial training, we
are concerned with how well our model, referred to as the student model, can
make correct predictions on data that has not been altered or perturbed. We
quantify this ability using a metric called the generalisation error. The
generalisation error, denoted by $E_{\mathrm{gen}}$, is the expected value
over all possible data points of whether the model’s prediction $\hat{y}$ is
incorrect. When the model’s predictions are based on the estimated parameter
vector $\hat{\boldsymbol{\theta}}$, the generalisation error is mathematically
expressed as

$E_{\mathrm{gen}}=\mathbb{E}_{y,\boldsymbol{x}}\quantity[\mathbb{1}[y\neq\hat{y}(\hat{\boldsymbol{\theta}};\boldsymbol{x})]]$
(44)

This can also be represented in terms of overlaps using

$E_{\mathrm{gen}}=\int\differential{y}\differential{\mu}(\nu,\lambda)P(y\mid\lambda)\mathbb{1}\quantity[y\neq
f(\nu)]=\frac{1}{\pi}\arccos\quantity(\frac{m}{\sqrt{(\rho+\tau^{2})q}})$ (45)

where this integral can be simplified further in the case of simple models,
e.g. the case of a noiseless channel. The final form in the case of in the
noiseless case has been presented in [3] Appendix II. For the noisy case the
derivation can be found in [10, 9]. The general form can be found in [16],
Appendix D.

However, in the case of adversarial learning, we’re not only interested in the
generalisation error under normal conditions but also under adversarial
attacks. The adversarial generalisation error measures the model’s robustness
against such attacks by evaluating the probability of misclassification when
the input data is perturbed within a certain norm bound determined by
$\varepsilon_{g}$ and the covariance matrix
$\boldsymbol{\Sigma}_{\boldsymbol{\upsilon}}$. Formally, the adversarial
generalisation error is given by

$E_{\mathrm{adv}}=\mathbb{E}_{y,\boldsymbol{x}}\quantity[\max_{\norm{\boldsymbol{\delta}}_{\boldsymbol{\Sigma}_{\boldsymbol{\upsilon}}^{-2}}\leq\varepsilon_{g}}\mathbb{1}[y\neq\hat{y}(\hat{\boldsymbol{\theta}}(\alpha);\boldsymbol{x}+\boldsymbol{\delta})]]=\mathbb{E}_{y,\boldsymbol{x}}\quantity[\mathbb{1}[y\neq\hat{y}\quantity(\hat{\boldsymbol{\theta}}(\alpha);\boldsymbol{x}-y\varepsilon_{g}\frac{\boldsymbol{\Sigma}_{\boldsymbol{\upsilon}}\hat{\boldsymbol{\theta}}}{\norm{\hat{\boldsymbol{\theta}}}_{2}})]]$
(46)

where the inner maximisation, for a fixed choice of $\boldsymbol{x}$ and
$\hat{\boldsymbol{\theta}}$, is solved explicitly by choosing
$\boldsymbol{\delta}=-y\varepsilon_{g}\boldsymbol{\Sigma}_{\boldsymbol{\upsilon}}\hat{\boldsymbol{\theta}}/\norm{\hat{\boldsymbol{\theta}}}_{2}$.

Again by using the idea of local fields one can compute the the value of the
adversarial error as a function of the overlaps. The definitions of the
overlap parameters $A,F$ is fixed after training and thus it doesn’t get
included in the average. We have that the from of the error is

$\displaystyle E_{\mathrm{adv}}=$
$\displaystyle\int_{0}^{\infty}\operatorname*{erfc}\left(\frac{\frac{m}{\sqrt{q}}\xi}{\sqrt{2\left(\rho+\tau^{2}-m^{2}/q\right)}}\right)\frac{e^{-\frac{\xi^{2}}{2}}}{\sqrt{2\pi}}\differential{\xi}$
(47) $\displaystyle+$
$\displaystyle\int_{0}^{\varepsilon_{g}\frac{A}{\sqrt{q}\sqrt{N}}}\operatorname*{erfc}\left(\frac{-\frac{m}{\sqrt{q}}\xi}{\sqrt{2\left(\rho+\tau^{2}-m^{2}/q\right)}}\right)\frac{e^{-\frac{\xi^{2}}{2}}}{\sqrt{2\pi}}\differential{\xi}$
$\displaystyle=$ $\displaystyle
E_{\mathrm{gen}}+\int_{0}^{\varepsilon_{g}\frac{A}{\sqrt{q}\sqrt{N}}}\operatorname*{erfc}\left(\frac{-\frac{m}{\sqrt{q}}\xi}{\sqrt{2\left(\rho+\tau^{2}-m^{2}/q\right)}}\right)\frac{e^{-\frac{\xi^{2}}{2}}}{\sqrt{2\pi}}\differential{\xi}$

One could modify the equation even more to relate it to the Owen’s T function
as we show in Section D.1.

###  B.2 Training

The training error reflects the model’s performance on the dataset it was
trained on. The goal during the training phase is to minimise this error and
we can expect to reach an optimal zero training error for the estimator
$\hat{\boldsymbol{\theta}}$ on noise less dataset. The training error is
expressed as

$E_{\mathrm{train}}=\sum_{i=1}^{n}\mathbb{1}\quantity[\hat{y}(\hat{\boldsymbol{\theta}};\boldsymbol{x}_{i})\neq
y_{i}]$ (48)

where the sum is over the same dataset used to find
$\hat{\boldsymbol{\theta}}$.

Following [16], Appendix D.2, one can find the following form of the training
error as a function of overlaps as

$E_{\mathrm{train}}=\frac{1}{2}\mathbb{E}_{\xi}\left[\int\differential{y}\mathcal{Z}_{0}\quantity(y,\sqrt{\eta}\xi,\rho-\rho\eta)\mathbb{1}\quantity[\operatorname{sign}\quantity(\mathcal{P}_{Vg(\cdot;y,P,N)}(\sqrt{q}\xi))\neq
y]\right]$ (49)

where $z^{\star}$ indicates the value of the proximal and
$\eta=\frac{m}{\sqrt{\rho q}}$.

Arguably more interesting than the training error is the training loss since
it is a part of the actual risk to minimise. This metric also brings more
information than the training error since usually the losses used for
classification are also sensitive to the norm of the solution and not only the
direction of $\hat{\boldsymbol{\theta}}$. The definition as a function of the
predicted ERM weights is

$\ell_{\mathrm{train}}=\sum_{i=1}^{n}g\quantity(y_{i}\frac{\hat{\boldsymbol{\theta}}^{\top}\boldsymbol{x}_{i}}{\sqrt{d}})$
(50)

and as a function of overlaps

$\ell_{\mathrm{train}}=\mathbb{E}_{y,\xi}\left[\mathcal{Z}_{0}\quantity(y,\sqrt{\eta}\xi,\rho-\rho\eta)\,g\left(y,\mathcal{P}_{Vg(\cdot;y,P,N)}(\sqrt{q}\xi),\varepsilon_{t}\frac{P}{\sqrt{N}}\right)\right]$
(51)

###  B.3 Class-preserving adversarial attacks

We propose a more refined metric called the class-preserving generalisation
error. This metric only considers attacks that mislead the student model while
not affecting the teacher model’s classification or its confidence in that
classification. The teacher’s confidence is quantified by a margin, denoted as
$\gamma$, which represents the minimum allowable distance from the decision
boundary to consider a classification confident.

This is an artificial metric, as it would be inaccessible to a student. We are
interested in measuring the error with respect to the noisy labels by only
considering attacks which are fair with respect to the ground truth.

We focus on attacks that attempt to deceive the student model within a
specified norm bound but also ensure that the teacher model does not
misclassify the perturbed data. The class-preserving generalisation error,
incorporating these considerations, is defined as:

$\displaystyle E_{\mathrm{CP}}(\varepsilon_{g},\gamma)=$
$\displaystyle\mathbb{E}_{y,\boldsymbol{x}}\quantity[\max_{\begin{subarray}{c}\norm{\boldsymbol{\delta}}_{\boldsymbol{\Sigma}_{\boldsymbol{\upsilon}}^{-2}}\leq\varepsilon_{g}\\\
y\boldsymbol{\theta}_{0}^{\top}(\boldsymbol{x}+\boldsymbol{\delta})>\sqrt{d}\gamma\end{subarray}}\mathbb{1}(y\neq\hat{y}(\hat{\boldsymbol{\theta}},\boldsymbol{x}+\boldsymbol{\delta}))\mathbb{1}(y\boldsymbol{\theta}_{0}^{\top}\boldsymbol{x}>\sqrt{d}\gamma)]+$
(52)
$\displaystyle\mathbb{E}_{y,\boldsymbol{x}}\quantity[\mathbb{1}(y\neq\hat{y}(\hat{\boldsymbol{\theta}},\boldsymbol{x}))\mathbb{1}(y\boldsymbol{\theta}_{0}^{\top}\boldsymbol{x}\leq\sqrt{d}\gamma)]$

The constraint within the maximisation ensure that the perturbation does not
cause the teacher model’s confidence classification is not diminished beyond
the margin $\gamma$ and that the total length of the perturbation doesn’t
surpass the value $\varepsilon_{g}$. The two constraints can be rewritten as

$\displaystyle\boldsymbol{\delta}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\upsilon}}^{-2}\boldsymbol{\delta}\leq\varepsilon_{g}^{2}\,,$
(53) $\displaystyle
y\boldsymbol{\theta}_{0}^{\top}\boldsymbol{\delta}>\gamma-y\boldsymbol{\theta}_{0}^{\top}\boldsymbol{x}\,,$
(54)

this means that the projection of the perturbation on the teacher should
always be greater in absolute value than the projection of the data, i.e. the
data point classified from the teacher should not change.

To simplify further one can consider the vanishing margin case as in the main
text, formally

$E_{\mathrm{CP}}(\varepsilon_{g})=\lim_{\gamma\to
0^{+}}E_{\mathrm{CP}}(\varepsilon_{g},\gamma)\,.$ (55)

We want to fool the student, so we consider a perturbation in the direction of
$\hat{\boldsymbol{\theta}}$. Based on different conditions we have different
attacks and thus different norm of this perturbation. We will indicate the
norm as

$\boldsymbol{\delta}_{(\cdot)}=\alpha_{(\cdot)}\frac{\boldsymbol{\Sigma}_{\boldsymbol{\upsilon}}\hat{\boldsymbol{\theta}}}{\norm{\hat{\boldsymbol{\theta}}}_{2}}$
(56)

where the subscript can indicate any of the cases and we will define them
later.

The first case is if the point $\boldsymbol{x}$ already has a margin with the
teacher that it is smaller than $\gamma$. The condition for this to happen is
that

$y\boldsymbol{\theta}_{0}^{\top}\boldsymbol{x}<\gamma\quad\implies\quad\alpha_{\mathrm{LM}}=0\,,\quad\boldsymbol{\delta}_{\mathrm{LM}}=\boldsymbol{0}\,,$
(57)

in this case we do not perturb the input data point.

By just considering Eq. 53 we have that the maximum norm the perturbation can
have is

$\alpha_{\mathrm{MAX}}=-y\varepsilon_{g}\,,\quad\boldsymbol{\delta}_{\mathrm{MAX}}=-y\varepsilon_{g}\frac{\boldsymbol{\Sigma}_{\boldsymbol{\upsilon}}\hat{\boldsymbol{\theta}}}{\norm{\hat{\boldsymbol{\theta}}}_{2}}$
(58)

this is the strongest attack, but we can only use it if the perturbed image
does not cross the margin $\gamma$ of the teacher $\boldsymbol{\theta}_{0}$.
In equations, it means that Eq. 54 is satisfied, which means that

$y\frac{\boldsymbol{\theta}_{0}^{\top}(\boldsymbol{x}+\boldsymbol{\delta}_{\mathrm{MAX}})}{\sqrt{d}}\geq\gamma\,\iff\,y\frac{\boldsymbol{\theta}_{0}^{\top}\boldsymbol{x}}{\sqrt{d}}-\varepsilon_{g}\frac{\boldsymbol{\theta}_{0}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\upsilon}}\hat{\boldsymbol{\theta}}}{\sqrt{d}\norm{\hat{\boldsymbol{\theta}}}_{2}}\geq\gamma$
(59)

thus if this previous condition is satisfied we can perturb with
$\boldsymbol{\delta}_{\mathrm{MAX}}$.

If instead Eqs. 54 and 59 are not satisfied we can proceed the attack but with
a smaller norm, that is found by imposing that the final margin is equal to
$\gamma$. By doing that we can solve for the final norm and obtain

$\alpha_{\gamma}=\frac{\sqrt{d}\norm{\hat{\boldsymbol{\theta}}}_{2}}{\boldsymbol{\theta}_{0}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\upsilon}}\hat{\boldsymbol{\theta}}}\quantity(y\gamma-\frac{\boldsymbol{\theta}_{0}^{\top}\boldsymbol{x}}{\sqrt{d}})\,,\quad\boldsymbol{\delta}_{\gamma}=\frac{\sqrt{d}\boldsymbol{\Sigma}_{\boldsymbol{\upsilon}}\hat{\boldsymbol{\theta}}}{\boldsymbol{\theta}_{0}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\upsilon}}\hat{\boldsymbol{\theta}}}\quantity(y\gamma-\frac{\boldsymbol{\theta}_{0}^{\top}\boldsymbol{x}}{\sqrt{d}})$
(60)

where remember that $y$ is just a sign.

One can thus rewrite explicitly the maximisation in Eq. 52 as follows

$\displaystyle E_{\mathrm{CP}}(\varepsilon_{g},\gamma)$
$\displaystyle=\mathbb{E}_{y,\boldsymbol{x}}\quantity[\mathbb{1}\quantity(y\neq\hat{y}(\hat{\boldsymbol{\theta}},\boldsymbol{x}+\boldsymbol{\delta}_{\gamma}))\mathbb{1}\quantity(y\frac{\boldsymbol{\theta}_{0}^{\top}\boldsymbol{x}}{\sqrt{d}}-\varepsilon_{g}\frac{\boldsymbol{\theta}_{0}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\upsilon}}\hat{\boldsymbol{\theta}}}{\sqrt{d}\norm{\hat{\boldsymbol{\theta}}}_{2}}<\gamma)\mathbb{1}(y\boldsymbol{\theta}_{0}^{\top}\boldsymbol{x}>\sqrt{d}\gamma)]$
(61)
$\displaystyle+\mathbb{E}_{y,\boldsymbol{x}}\quantity[\mathbb{1}\quantity(y\neq\hat{y}(\hat{\boldsymbol{\theta}},\boldsymbol{x}+\boldsymbol{\delta}_{\mathrm{MAX}}))\mathbb{1}\quantity(y\frac{\boldsymbol{\theta}_{0}^{\top}\boldsymbol{x}}{\sqrt{d}}-\varepsilon_{g}\frac{\boldsymbol{\theta}_{0}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\upsilon}}\hat{\boldsymbol{\theta}}}{\sqrt{d}\norm{\hat{\boldsymbol{\theta}}}_{2}}\geq\gamma)\mathbb{1}(y\boldsymbol{\theta}_{0}^{\top}\boldsymbol{x}>\sqrt{d}\gamma)]$
$\displaystyle+\mathbb{E}_{y,\boldsymbol{x}}\quantity[\mathbb{1}(y\neq\hat{y}(\hat{\boldsymbol{\theta}},\boldsymbol{x}))\mathbb{1}(y\boldsymbol{\theta}_{0}^{\top}\boldsymbol{x}\leq\sqrt{d}\gamma)]$

where each one of the lines correspond to one of the previously explained
cases. To compute the expectations in Eq. 61, because of the presence of $y$
one should consider the actual channel that generates the data. Nevertheless
the form in Eq. 61 is well suited for estimation from a given test dataset by
replacing the expectations with empirical averages over that training dataset.

####  B.3.1 Noiseless Channel

In the case that the channel is a noiseless sign channel we have

$\displaystyle E_{\mathrm{CP}}(\varepsilon_{g},\gamma)$
$\displaystyle=\int\differential{\mu(\nu,\lambda)}\mathbb{1}\quantity[\operatorname{sign}(\nu)\neq\operatorname{sign}\quantity(\lambda+\operatorname{sign}(\nu)\frac{A}{F}\quantity(\gamma-\absolutevalue{\nu}))]\mathbb{1}\quantity[\absolutevalue{\nu}-\varepsilon_{g}\frac{F}{\sqrt{N}}<\gamma]\mathbb{1}\quantity[\absolutevalue{\nu}>\gamma]$
(62)
$\displaystyle+\int\differential{\mu(\nu,\lambda)}\mathbb{1}\quantity[\operatorname{sign}(\nu)\neq\operatorname{sign}\quantity(\lambda-\operatorname{sign}(\nu)\varepsilon_{g}\frac{A}{\sqrt{N}})]\mathbb{1}\quantity[\absolutevalue{\nu}-\varepsilon_{g}\frac{F}{\sqrt{N}}\geq\gamma]\mathbb{1}\quantity[\absolutevalue{\nu}>\gamma]$
$\displaystyle+\int\differential{\mu(\nu,\lambda)}\mathbb{1}\quantity[\operatorname{sign}(\nu)\neq\operatorname{sign}(\lambda)]\mathbb{1}\quantity[\absolutevalue{\nu}\leq\gamma]$

where we have that the local fields $\nu,\lambda$ are jointly Gaussian with
zero mean and covariance $\bigl{(}\begin{smallmatrix}\rho&m\\\
m&q\end{smallmatrix}\bigr{)}$, this is the probability distribution
$\differential{\mu(\nu,\lambda)}$.

To simplify the double integral in Eq. 62 it is a matter of integrating over
$\lambda$ and then computing the integration over $\nu$ numerically, as it is
in a single variable. In the end, we obtain

$\displaystyle E_{\mathrm{CP}}(\varepsilon_{g},\gamma)$
$\displaystyle=\int_{0}^{\gamma}\operatorname*{erfc}\quantity(\frac{m\nu}{\sqrt{2\rho\left(q\rho-m^{2}\right)}})\mathcal{D}_{\rho}\quantity[\nu]+\int_{\gamma^{\star}}^{\infty}\operatorname*{erfc}\quantity(\frac{m\nu-\varepsilon_{g}\sqrt{N}\rho}{\sqrt{2\rho\left(q\rho-m^{2}\right)}})\mathcal{D}_{\rho}\quantity[\nu]$
(63)
$\displaystyle+\frac{1}{2}\quantity[\int_{\gamma}^{\gamma^{\star}}\operatorname*{erfc}\quantity(\frac{A\rho\gamma+\nu(mF-A\rho)}{F\sqrt{2\rho\left(q\rho-m^{2}\right)}})\mathcal{D}_{\rho}\quantity[\nu]+\int_{-\gamma^{\star}}^{-\gamma}\operatorname*{erfc}\quantity(\frac{A\rho\gamma-\nu(mF-A\rho)}{F\sqrt{2\rho\left(q\rho-m^{2}\right)}})\mathcal{D}_{\rho}\quantity[\nu]]$

where the notation $\mathcal{D}_{\rho}\quantity[\nu]$ indicates the p.d.f. of
a random variable $\nu\sim\mathcal{N}(0,\rho^{2})$ and
$\gamma^{\star}=\max(\gamma,\gamma+\varepsilon_{g}F/\sqrt{N})$.

####  B.3.2 Probit Channel

In the case where the channel is a probit channel we have that the class
preserving error could be computed similarly at the addition of one integral.
The integration is done over the measure $\differential{\mu}(\nu,\lambda)$ as
before but one should add the probability distribution of the channel. Thus we
have that the integration becomes

$\displaystyle E_{\mathrm{CP}}(\varepsilon_{g},\gamma)$
$\displaystyle=\int\differential{y}\differential{\mu(\nu,\lambda)}P(y\mid\nu)\mathbb{1}\quantity[y\neq\operatorname{sign}\quantity(\lambda+\operatorname{sign}(\nu+z)\frac{A}{F}\quantity(\gamma-\absolutevalue{\nu}))]\mathbb{1}\quantity[y\nu-\varepsilon_{g}\frac{F}{\sqrt{N}}<\gamma]\mathbb{1}\quantity[y\nu>\gamma]$
(64)
$\displaystyle+\int\differential{y}\differential{\mu(\nu,\lambda)}P(y\mid\nu)\mathbb{1}\quantity[y\neq\operatorname{sign}\quantity(\lambda-\operatorname{sign}(\nu)\varepsilon_{g}\frac{A}{\sqrt{N}})]\mathbb{1}\quantity[y\nu-\varepsilon_{g}\frac{F}{\sqrt{N}}\geq\gamma]\mathbb{1}\quantity[y\nu>\gamma]$
$\displaystyle+\int\differential{y}\differential{\mu(\nu,\lambda)}P(y\mid\nu)\mathbb{1}\quantity[y\neq\operatorname{sign}(\lambda)]\mathbb{1}\quantity[y\nu\leq\gamma]$

where we have introduced the channel probability distribution.

###  B.4 Expression for Teacher Usefulness and Robustness

The equations for the usefulness and the robustness can be found using the
same approach as before. We remember assumption (A1) and (A4) of [32] in
Appendix B for the assumptions on the teacher. We explicitly have that

$\displaystyle\mathcal{U}_{\boldsymbol{\theta}_{0}}$
$\displaystyle=\frac{1}{\sqrt{d}}\mathbb{E}_{\boldsymbol{x},y}[y\boldsymbol{\theta}_{0}^{\top}\boldsymbol{x}]=\sqrt{\frac{2}{\pi}}\frac{\rho}{\sqrt{\rho+\tau^{2}}}\,,$
(65) $\displaystyle\mathcal{R}_{\boldsymbol{\theta}_{0}}$
$\displaystyle=\frac{1}{\sqrt{d}}\mathbb{E}_{\boldsymbol{x},y}\quantity[\inf_{\norm{\boldsymbol{\delta}}_{\boldsymbol{\Sigma}_{\boldsymbol{\upsilon}}^{-2}}\leq\varepsilon_{g}}y\boldsymbol{\theta}_{0}^{\top}(\boldsymbol{x}+\boldsymbol{\delta})]$
$\displaystyle=\frac{1}{\sqrt{d}}\mathbb{E}_{\boldsymbol{x},y}[y\boldsymbol{\theta}_{0}^{\top}\boldsymbol{x}]-\frac{\varepsilon_{g}}{\sqrt{d}}\mathbb{E}\quantity[\frac{\boldsymbol{\theta}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\upsilon}}\boldsymbol{\theta}}{\norm{\boldsymbol{\theta}}_{2}}]=\mathcal{U}_{\boldsymbol{\theta}_{0}}-\varepsilon_{g}\frac{a}{\sqrt{n}}\,.$

and in the end we have integrated using the local fields method in the case of
averaged teacher.

##  Appendix C High $\alpha$ expansion

In this Appendix, we provide expansion of the fixed point equations in Theorem
III.1. In practical terms, the high sample complexity regime is challenging to
access due to the computational resources it demands to simulate the ERM. By
providing a theoretical expansion, we offer a lens through which the system’s
behaviour under high sample complexity can be understood and predicted at less
computational cost.

Figure 6: We provide the scalings of the overlaps in the large sample
complexity regime. For the experiment, we consider a BFM with one block and
identity matrices. This is why some overlaps are exactly equal.

In the large $\alpha$ behaviour regime we have that at leading order the
parameters scale as

$\displaystyle q\underset{\alpha\rightarrow\infty}{=}q_{0}\,,$
$\displaystyle\hat{q}\underset{\alpha\rightarrow\infty}{=}\hat{q}_{0}\alpha\,,$
(66) $\displaystyle m\underset{\alpha\rightarrow\infty}{=}m_{0}\,,$
$\displaystyle\hat{m}\underset{\alpha\rightarrow\infty}{=}\hat{m}_{0}\alpha\,,$
$\displaystyle V\underset{\alpha\rightarrow\infty}{=}\frac{V_{0}}{\alpha}\,,$
$\displaystyle\hat{V}\underset{\alpha\rightarrow\infty}{=}\hat{V}_{0}\alpha\,,$
$\displaystyle P\underset{\alpha\rightarrow\infty}{=}P_{0}\,,$
$\displaystyle\hat{P}\underset{\alpha\rightarrow\infty}{=}\hat{P}_{0}\alpha\,,$
$\displaystyle N\underset{\alpha\rightarrow\infty}{=}N_{0}\,,$
$\displaystyle\hat{N}\underset{\alpha\rightarrow\infty}{=}\hat{N}_{0}\alpha\,,$
$\displaystyle A\underset{\alpha\rightarrow\infty}{=}A_{0}\,,$
$\displaystyle\hat{A}\underset{\alpha\rightarrow\infty}{=}0\,,$ $\displaystyle
F\underset{\alpha\rightarrow\infty}{=}F_{0}\,,$
$\displaystyle\hat{F}\underset{\alpha\rightarrow\infty}{=}0\,,$

where the sub scripted quantities are independent of $\alpha$. These scaling
assumptions break down whenever $\varepsilon_{t}=\tau=0$, in this case, the
first row of overlaps except $V$ scale linearly in $\alpha$. This case is
studied in [3].

To simplify the proximal operator we start by its formulation as a function of
the generalised Lambert function [8] and then expand

$\mathcal{P}_{Vg(\cdot;y,P,N)}(\sqrt{q}\xi)=\sqrt{q_{0}}\xi+y\mathbf{W}_{\exp(-\frac{\sqrt{q_{0}}\xi}{y}+\varepsilon_{t}\frac{P_{0}}{\sqrt{N_{0}}})}\quantity(\frac{V_{0}}{\alpha}\exp(-\frac{\sqrt{q_{0}}\xi}{y}+\varepsilon_{t}\frac{P_{0}}{\sqrt{N_{0}}}))\underset{\alpha\rightarrow\infty}{=}\sqrt{q_{0}}\xi+\frac{c(\xi)}{\alpha}$
(67)

where $\mathbf{W}_{r}$ is the generalised Lambert-W function and we are
expanding around 0. And is given by

$c(\xi)=yV_{0}\frac{\exp(-y\sqrt{q_{0}}\xi+\varepsilon_{t}\frac{P_{0}}{\sqrt{N_{0}}})}{1+\exp(-y\sqrt{q_{0}}\xi+\varepsilon_{t}\frac{P_{0}}{\sqrt{N_{0}}})}\,.$
(68)

With this, we can simplify the channel and the prior equations as follows

$\begin{cases}\hat{q}_{0}&=\frac{1}{2}\frac{1}{V_{0}^{2}}\mathbb{E}_{y,\xi}\left[\operatorname*{erfc}\left(\frac{-y\frac{m_{0}}{\sqrt{q_{0}}}\xi}{\sqrt{2\left(\rho-
m_{0}^{2}/q_{0}\right)}}\right)c(\xi)^{2}\right]\\\
\hat{m}_{0}&=\frac{1}{V_{0}}\frac{1}{\sqrt{2\pi\left(\rho-
m_{0}^{2}/q_{0}\right)}}\mathbb{E}_{y,\xi}\left[\exp\left(-\frac{1}{2}\frac{m_{0}^{2}}{q_{0}}\frac{\xi}{\rho-\frac{m_{0}^{2}}{q_{0}}}\right)c(\xi)\right]\\\
\hat{V}_{0}&=\frac{\alpha}{2}\mathbb{E}_{y,\xi}\left[\operatorname*{erfc}\left(\frac{-y\frac{m_{0}}{\sqrt{q_{0}}}\xi}{\sqrt{2\left(\rho-
m_{0}^{2}/q_{0}+\tau^{2}\right)}}\right)\frac{\partial_{z}^{2}g(y,z^{*},\varepsilon_{t}\frac{P_{0}}{\sqrt{N_{0}}})}{1+\frac{V_{0}}{\alpha}\left(\partial_{z}^{2}g(y,z^{*},\varepsilon_{t}\frac{P_{0}}{\sqrt{N_{0}}})\right)}\right]\\\
\hat{P}_{0}&=\mathbb{E}_{y,\xi}\left[\operatorname*{erfc}\left(\frac{-y\frac{m_{0}}{\sqrt{q_{0}}}\xi}{\sqrt{2\left(\rho-
m_{0}^{2}/q_{0}\right)}}\right)\frac{\varepsilon_{t}\frac{1}{\sqrt{N_{0}}}}{1+e^{y\sqrt{q_{0}}\xi-\varepsilon_{t}\frac{P_{0}}{\sqrt{N_{0}}}}}\right]\\\
\hat{N}_{0}&=\mathbb{E}_{y,\xi}\left[\operatorname*{erfc}\left(\frac{-y\frac{m_{0}}{\sqrt{q_{0}}}\xi}{\sqrt{2\left(\rho-
m_{0}^{2}/q_{0}\right)}}\right)\frac{\varepsilon_{t}\frac{-P_{0}}{2N_{0}^{3/2}}}{1+e^{y\sqrt{q_{0}}\xi-\varepsilon_{t}\frac{P_{0}}{\sqrt{N_{0}}}}}\right]\\\
\end{cases}$ (69)
$\begin{cases}m_{0}&=\frac{1}{d}\tr\quantity[\hat{m}_{0}\boldsymbol{\Sigma}_{\boldsymbol{\boldsymbol{x}}}^{\top}\boldsymbol{\theta}_{0}\boldsymbol{\theta}_{0}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\boldsymbol{x}}}\boldsymbol{\Lambda}^{-1}]\\\
q_{0}&=\frac{1}{d}\tr\quantity[\quantity(\hat{m}_{0}^{2}\boldsymbol{\Sigma}_{\boldsymbol{\boldsymbol{x}}}^{\top}\boldsymbol{\theta}_{0}\boldsymbol{\theta}_{0}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\boldsymbol{x}}})\boldsymbol{\Sigma}_{\boldsymbol{\boldsymbol{x}}}\boldsymbol{\Lambda}^{-2}]\\\
V_{0}&=\frac{1}{d}\tr\quantity[\boldsymbol{\Sigma}_{\boldsymbol{\boldsymbol{x}}}\boldsymbol{\Lambda}^{-1}]\\\
P_{0}&=\frac{1}{d}\tr\quantity[\quantity(\hat{m}_{0}^{2}\boldsymbol{\Sigma}_{\boldsymbol{\boldsymbol{x}}}^{\top}\boldsymbol{\theta}_{0}\boldsymbol{\theta}_{0}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\boldsymbol{x}}})\boldsymbol{\Sigma}_{\boldsymbol{\delta}}\boldsymbol{\Lambda}^{-2}]\\\
N_{0}&=\frac{1}{d}\tr\quantity[\quantity(\hat{m}_{0}^{2}\boldsymbol{\Sigma}_{\boldsymbol{\boldsymbol{x}}}^{\top}\boldsymbol{\theta}_{0}\boldsymbol{\theta}_{0}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\boldsymbol{x}}})\boldsymbol{\Lambda}^{-2}]\end{cases}$
(70)

with
$\boldsymbol{\Lambda}=\frac{\lambda}{\alpha}\mathbb{1}+\hat{V}_{0}\boldsymbol{\Sigma}_{\boldsymbol{\boldsymbol{x}}}+\hat{P}_{0}\boldsymbol{\Sigma}_{\boldsymbol{\delta}}+\hat{N}_{0}\mathbb{1}$
.

The additional values are

$A_{0}=\frac{1}{d}\tr\quantity[\quantity(\hat{m}_{0}^{2}\boldsymbol{\Sigma}_{\boldsymbol{\boldsymbol{x}}}^{\top}\boldsymbol{\theta}_{0}\boldsymbol{\theta}_{0}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\boldsymbol{x}}})\boldsymbol{\Sigma}_{\boldsymbol{\upsilon}}\boldsymbol{\Lambda}^{-2}]\,,\qquad
F_{0}=\frac{1}{d}\tr\quantity[\hat{m}_{0}^{2}\left(\boldsymbol{\Sigma}_{\boldsymbol{\boldsymbol{x}}}^{\top}\boldsymbol{\theta}_{0}\boldsymbol{\theta}_{0}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\upsilon}}\right)\boldsymbol{\Lambda}^{-1}]\,.$
(71)

###  C.1 Large Alpha Limit of the Adversarial Test Error

Using above simplifications, we can simplify the following quantities in the
large sample complexity limit. The angle can be written as

$\displaystyle\lim_{\alpha\to\infty}\frac{m_{0}}{\sqrt{(\rho+\tau^{2})q_{0}}}$
$\displaystyle=\frac{\tr\quantity[\boldsymbol{\Sigma}_{\boldsymbol{\boldsymbol{x}}}^{\top}\boldsymbol{\theta}_{0}\boldsymbol{\theta}_{0}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\boldsymbol{x}}}\boldsymbol{\Lambda}^{-1}]}{\sqrt{(\boldsymbol{\theta}_{0}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\boldsymbol{x}}}\boldsymbol{\theta}_{0}+\tau^{2})\tr\quantity[\boldsymbol{\Sigma}_{\boldsymbol{\boldsymbol{x}}}^{\top}\boldsymbol{\theta}_{0}\boldsymbol{\theta}_{0}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\boldsymbol{x}}}\boldsymbol{\Sigma}_{\boldsymbol{\boldsymbol{x}}}\boldsymbol{\Lambda}^{-2}]}}$
(72)

and the overlap ratio determining how strong an attack is, is given by

$\displaystyle\lim_{\alpha\to\infty}\frac{A_{0}}{\sqrt{q_{0}N_{0}}}=$
$\displaystyle\frac{\tr\quantity[\boldsymbol{\Sigma}_{\boldsymbol{\boldsymbol{x}}}^{\top}\boldsymbol{\theta}_{0}\boldsymbol{\theta}_{0}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\boldsymbol{x}}}\boldsymbol{\Sigma}_{\boldsymbol{\upsilon}}\boldsymbol{\Lambda}^{-2}]}{\sqrt{\tr\quantity[\boldsymbol{\Sigma}_{\boldsymbol{\boldsymbol{x}}}^{\top}\boldsymbol{\theta}_{0}\boldsymbol{\theta}_{0}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\boldsymbol{x}}}\boldsymbol{\Sigma}_{\boldsymbol{\boldsymbol{x}}}\boldsymbol{\Lambda}^{-2}]\tr\quantity[\boldsymbol{\Sigma}_{\boldsymbol{\boldsymbol{x}}}^{\top}\boldsymbol{\theta}_{0}\boldsymbol{\theta}_{0}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\boldsymbol{x}}}\boldsymbol{\Lambda}^{-2}]}}$
(73)

Notably, the previous equations no longer depend on $\hat{q}_{0}$ and
$\hat{m}_{0}$, with this the adversarial generalisation error is characterised
by the following equation, which is a function of the limiting values we just
defined.

$\displaystyle E_{AG}\underset{\alpha\rightarrow\infty}{=}$
$\displaystyle\frac{1}{\pi}\arccos\quantity(\frac{m_{0}}{\sqrt{(\rho+\tau^{2})q_{0}}})+\int_{0}^{\varepsilon_{g}\frac{A_{0}}{\sqrt{q_{0}}\sqrt{N_{0}}}}\operatorname*{erfc}\left(\frac{-m_{0}\xi}{\sqrt{2\left(q_{0}(\rho+\tau^{2})-m_{0}^{2}\right)}}\right)\frac{e^{-\frac{\xi^{2}}{2}}}{\sqrt{2\pi}}\differential{\xi}$
(74)

The derivative of the adversarial generalisation error is given by

$\displaystyle\partial_{\alpha}E_{AG}=$
$\displaystyle\frac{1}{\pi}\frac{-1}{\sqrt{1-\frac{m^{2}}{(\rho+\tau^{2})q}}}\partial_{\alpha}(\frac{m}{\sqrt{(\rho+\tau^{2})q}})+\operatorname*{erfc}\left(\frac{-\frac{m}{\sqrt{(\rho+\tau^{2})q}}\frac{A}{\sqrt{q}\sqrt{N}}}{\sqrt{2\left(1-\frac{m^{2}}{(\rho+\tau^{2})q}\right)}}\right)\frac{e^{-\frac{\frac{A}{\sqrt{q}\sqrt{N}}^{2}}{2}}}{\sqrt{2\pi}}\partial_{\alpha}(\frac{A}{\sqrt{q}\sqrt{N}})$
(75)
$\displaystyle-\int_{0}^{\varepsilon_{g}\frac{A}{\sqrt{q}\sqrt{N}}}\exp\left(-\frac{\frac{m^{2}}{(\rho+\tau^{2})q}\xi^{2}}{2\left(1-\frac{m^{2}}{(\rho+\tau^{2})q}\right)}\right)\frac{\sqrt{2}e^{-\frac{\xi^{2}}{2}}}{\pi}\frac{1}{\sqrt{2}(1-\frac{m^{2}}{(\rho+\tau^{2})q})^{3/2}}\partial_{\alpha}(\frac{m}{\sqrt{(\rho+\tau^{2})q}})\differential{\xi}$

For the derivative and the large alpha limit, we will need the derivatives of
the following expressions

$\displaystyle\frac{m}{\sqrt{\rho q}}=$
$\displaystyle\frac{\frac{1}{d}\tr\quantity[\hat{m}_{0}\boldsymbol{\Sigma}_{\boldsymbol{\boldsymbol{x}}}^{\top}\boldsymbol{\theta}_{0}\boldsymbol{\theta}_{0}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\boldsymbol{x}}}\boldsymbol{\Lambda}^{-1}]}{\sqrt{\frac{1}{d}\boldsymbol{\theta}_{0}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\boldsymbol{x}}}\boldsymbol{\theta}_{0}\frac{1}{d}\tr\quantity[\quantity(\hat{m}_{0}^{2}\boldsymbol{\Sigma}_{\boldsymbol{\boldsymbol{x}}}^{\top}\boldsymbol{\theta}_{0}\boldsymbol{\theta}_{0}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\boldsymbol{x}}}+\frac{\hat{q}_{0}}{\alpha}\boldsymbol{\Sigma}_{\boldsymbol{\boldsymbol{x}}})\boldsymbol{\Sigma}_{\boldsymbol{\boldsymbol{x}}}\boldsymbol{\Lambda}^{-2}]}}$
(76) $\displaystyle\frac{A}{\sqrt{qN}}=$
$\displaystyle\frac{\frac{1}{d}\tr\quantity[\quantity(\hat{m}_{0}^{2}\boldsymbol{\Sigma}_{\boldsymbol{\boldsymbol{x}}}^{\top}\boldsymbol{\theta}_{0}\boldsymbol{\theta}_{0}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\boldsymbol{x}}}+\frac{\hat{q}_{0}}{\alpha}\boldsymbol{\Sigma}_{\boldsymbol{\boldsymbol{x}}})\boldsymbol{\Sigma}_{\boldsymbol{\upsilon}}\boldsymbol{\Lambda}^{-2}]}{\sqrt{\frac{1}{d}\tr\quantity[\quantity(\hat{m}_{0}^{2}\boldsymbol{\Sigma}_{\boldsymbol{\boldsymbol{x}}}^{\top}\boldsymbol{\theta}_{0}\boldsymbol{\theta}_{0}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\boldsymbol{x}}}+\frac{\hat{q}_{0}}{\alpha}\boldsymbol{\Sigma}_{\boldsymbol{\boldsymbol{x}}})\boldsymbol{\Sigma}_{\boldsymbol{\boldsymbol{x}}}\boldsymbol{\Lambda}^{-2}]\frac{1}{d}\tr\quantity[\quantity(\hat{m}_{0}^{2}\boldsymbol{\Sigma}_{\boldsymbol{\boldsymbol{x}}}^{\top}\boldsymbol{\theta}_{0}\boldsymbol{\theta}_{0}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\boldsymbol{x}}}+\frac{\hat{q}_{0}}{\alpha}\boldsymbol{\Sigma}_{\boldsymbol{\boldsymbol{x}}})\boldsymbol{\Lambda}^{-2}]}}$

To compute the derivative, we use the property

$\tr(\mathbf{A}+\mathbf{B})=\tr(\mathbf{A})+\tr(\mathbf{B})$ (77)

Note, that we compute the derivative with respect to a scalar that is not
dependent on the trace itself. Thus, every derivative in both
$\frac{m}{\sqrt{\rho q}}$ and $\frac{A}{\sqrt{qN}}$ will lead to a factor of
the form $\frac{c}{\alpha^{2}}\tr(M)$, which goes to zero as
$\alpha\to\infty$.

Thus the adversarial generalisation error approaches a constant in the large
sample complexity limit

$\displaystyle\partial_{\alpha}E_{AG}\underset{\alpha\rightarrow\infty}{=}$
$\displaystyle 0,\quad E_{AG}\underset{\alpha\rightarrow\infty}{=}$
$\displaystyle cst.$ (78)

The behaviour of the adversarial training error is given in Fig. 7.

Figure 7: We show the asymptotic behaviour of the (adversarial) generalisation
error at a noise level $\tau=0.05$, $\lambda=0.001$,
$\varepsilon_{g}=\varepsilon_{t}=0.2$.

###  C.2 Simplified Expressions for Generalisation and Boundary Errors

We can rewrite the key quantity describing generalisation error as follows

$\frac{m_{0}}{\sqrt{(\rho+\tau^{2})q_{0}}}=\frac{m_{0}}{\sqrt{\rho
q_{0}}}\frac{1}{\sqrt{1+\frac{\tau^{2}}{\rho}}}\,.$ (79)

Whenever $\vartheta=\frac{m_{0}}{\sqrt{\rho q_{0}}}\to 1$ when
$\alpha\to\infty$, we can leverage, that the angle between teacher and student
is zero, and the actual vectors differ only up to a constant, that is
$\boldsymbol{\theta}=c\boldsymbol{\theta}_{0}$.

$E_{\mathrm{gen}}\underset{\alpha\rightarrow\infty}{=}\frac{1}{\pi}\arccos(\vartheta\sqrt{\frac{\pi}{2}}\frac{\mathcal{U}_{\boldsymbol{\theta}_{0}}}{\sqrt{\rho}})\underset{\alpha\rightarrow\infty}{=}\frac{1}{\pi}\arccos(\frac{\sqrt{\rho}}{\sqrt{\rho+\tau^{2}}})$
(80)

Furthermore, the quantity $\frac{A}{\sqrt{qN}}$ converges to
$\frac{a}{\sqrt{\rho n}}$ by definition. Writing the boundary error as a
function of
$\mathcal{U}_{\boldsymbol{\theta}_{0}}-\mathcal{R}_{\boldsymbol{\theta}_{0}}$,
leads thus

$E_{\mathrm{bound}}=\int_{0}^{\varepsilon_{g}\frac{1}{\sqrt{q}}(\mathcal{U}_{\boldsymbol{\theta}_{0}}-\mathcal{R}_{\boldsymbol{\theta}_{0}})}f(\xi;\vartheta,\frac{\mathcal{U}_{\boldsymbol{\theta}_{0}}}{\sqrt{\rho}})\differential{\xi}\underset{\alpha\rightarrow\infty}{=}\int_{0}^{\varepsilon_{g}\frac{a}{\sqrt{\rho
n}}}f(\xi;\frac{1}{\sqrt{1+\frac{\tau^{2}}{\rho}}})\differential{\xi}\,.$ (81)

We can simplify this expression further under the assumption of a uniform
attack in a BFM with a singular block. In this case, the boundary term can be
simplified and we obtain

$E_{\mathrm{bound}}\underset{\alpha\rightarrow\infty}{=}\int_{0}^{\varepsilon_{g}\frac{1}{\sqrt{\psi_{\ell}}}}f(\xi;\frac{\sqrt{\rho}}{\sqrt{\rho+\tau^{2}}})\differential{\xi}\,.$
(82)

In this simple setting, the variance of the data influences inverse
proportionally the integration bound.

##  Appendix D Additional Results regarding the Adversarial Generalisation
Error

###  D.1 Adversarial Error and Owen’s T function

We demonstrate that the adversarial error from Eq. 47 can be written in terms
of Owen’s T function, we begin by explicitly stating the adversarial error. We
believe that given the usual definition of the Owen’s T function this is a
interesting geometrical approach.

We start from the definition of the adversarial error

$E_{\mathrm{adv}}(\varepsilon_{g})=\int_{0}^{\infty}\operatorname*{erfc}\left(\frac{\frac{m}{\sqrt{q}}\xi}{\sqrt{2\left(\rho+\tau^{2}-m^{2}/q\right)}}\right)\frac{e^{-\frac{\xi^{2}}{2}}}{\sqrt{2\pi}}\differential{\xi}+\int_{0}^{\varepsilon_{g}\frac{A}{\sqrt{q}\sqrt{N}}}\operatorname*{erfc}\left(\frac{-\frac{m}{\sqrt{q}}\xi}{\sqrt{2\left(\rho+\tau^{2}-m^{2}/q\right)}}\right)\frac{e^{-\frac{\xi^{2}}{2}}}{\sqrt{2\pi}}\differential{\xi}$
(83)

where we did a change of variable with an opposite sign and we changed the
order of integration.

Now we would like to use some identities to deal with the non-adversarial part
of the generalisation error. We use the formula

$\int_{0}^{\infty}\operatorname*{erfc}(ax)e^{b^{2}x^{2}}dx=\frac{1}{2\sqrt{\pi}b}\ln\left[\frac{a+b}{a-b}\right],\quad
b\text{ may be complex, }\quad|\arg a|<\frac{\pi}{4}$ (84)

Finally, we obtain an expression for the adversarial generalisation error as a
function of the standard generalisation error and an integral for the boundary
error.

$E_{AG}=\frac{1}{\pi}\arccos\quantity(\frac{m}{\sqrt{(\rho+\tau^{2})q}})+\int_{0}^{\varepsilon_{g}\frac{A}{\sqrt{q}\sqrt{N}}}\operatorname*{erfc}\left(\frac{-\frac{m}{\sqrt{q}}\xi}{\sqrt{2\left(\rho+\tau^{2}-m^{2}/q\right)}}\right)\frac{e^{-\frac{\xi^{2}}{2}}}{\sqrt{2\pi}}\differential{\xi}$
(85)

We would like to simplify this part more and obtain a relation to the Owen T
function definition [46]. From [42, 27] we use the following identity

$\int_{0}^{b}e^{-x^{2}}\operatorname*{erfc}(ax)dx=\frac{1}{2\sqrt{\pi}a}\quantity[-4\pi\sqrt{a^{2}}T\left(\sqrt{2}\sqrt{a^{2}}b,\frac{1}{\sqrt{a^{2}}}\right)+\pi
a\erf(b)\operatorname*{erfc}(ab)+2a\cot^{-1}(a)]$ (86)

where we are using Owen’s T function which is defined as

$T(h,a)=\frac{1}{2\pi}\int_{0}^{a}\frac{e^{-\frac{1}{2}h^{2}\left(1+x^{2}\right)}}{1+x^{2}}dx\quad(-\infty<h,a<+\infty).$
(87)

By performing a change of variables $\xi^{\prime}=\xi/\sqrt{2}$ we can
simplify further the second term of Eq. 85 as

$\frac{1}{2\pi}\left[4\pi
T\left(\frac{m\varepsilon_{g}}{\sqrt{(\rho+\tau^{2})q-m^{2}}},\frac{\sqrt{(\rho+\tau^{2})q-m^{2}}}{m}\right)+\pi\erf(\frac{\varepsilon_{g}}{\sqrt{2}})\operatorname*{erfc}(\frac{-m\frac{\varepsilon_{g}}{\sqrt{2}}}{\sqrt{(\rho+\tau^{2})q-m^{2}}})+2\cot^{-1}(\frac{-m}{\sqrt{((\rho+\tau^{2})+\tau^{2})q-m^{2}}})\right]\\\
$ (88)

The complete expression for the adversarial generalisation error is

$E_{AG}=2T\left(\frac{m\varepsilon_{g}}{\sqrt{(\rho+\tau^{2})q-m^{2}}},\frac{\sqrt{(\rho+\tau^{2})q-m^{2}}}{m}\right)+\frac{1}{2}\erf\quantity(\frac{\varepsilon_{g}}{\sqrt{2}})\operatorname*{erfc}\quantity(\frac{-m\varepsilon_{g}}{\sqrt{2((\rho+\tau^{2})q-m^{2})}})$
(89)

Given that the adversarial test error in the case where it is not attacked is
equal to the standard test error, it should be possible to simplify the
expression for the owen’s T function. Indeed, the following property [45]
holds

$T(0,a)=\frac{1}{2\pi}\arctan(a)=\frac{1}{2\pi}\arccos\quantity(\frac{a}{\sqrt{1+a^{2}}})$
(90)

and this leads us to the unperturbed version of the generalisation error.

###  D.2 How fair are our attacks?

In the context of adversarial attacks, it is crucial to distinguish between
transformations that change the underlying class of a data point and those
that do not. Consider an example in image recognition: if an image of a cat is
altered so extensively that it appears to be a dog, it is appropriate for a
model to classify it as a dog. However, this does not constitute a meaningful
adversarial attack. A sensible adversarial attack modifies the image in a way
that does not alter the class identified by the original teacher model, which
serves as a reference for correct classifications.

The following expression tells us the ratio of wrongly classified samples with
respect to the noisy labels when we use the optimal attack we introduced
earlier.

$\mathbb{E}_{y,\boldsymbol{x}}\quantity[\operatorname{sign}\quantity(\frac{\boldsymbol{\theta}_{0}^{\top}(\boldsymbol{x}+\boldsymbol{\upsilon})}{\sqrt{d}})\neq
y]=1-\int_{\varepsilon_{g}\frac{F}{\sqrt{N}}}^{\infty}d\nu\frac{1}{\sqrt{2\pi\rho}}\exp\quantity(-\frac{\nu^{2}}{2\rho})\quantity(1+\erf(\frac{\nu}{\sqrt{2\tau^{2}}})))$
(91)

Notice that there is a nuance regarding the knowledge of the student and the
adversary. The metric above tells us the wrongly classified ratio among all
samples as a student not knowing ground truth would assess it. Instead of
considering the noisy labels
$y=\operatorname{sign}(\boldsymbol{\theta}_{0}^{\top}\boldsymbol{x}/\sqrt{d}+\tau\chi)$,
one could also ask for the fairness achievable with respect to the teacher
ground truth by instead considering the noiseless activation inaccessible to
the student
$y=\operatorname{sign}(\boldsymbol{\theta}_{0}^{\top}\boldsymbol{x}/\sqrt{d})$.
The metrics for generalisation and training are using the noisy labels
accessible by the student.

##  Appendix E Rewriting the adversarial problem in the data-dependent
regularisation form

In other settings, adversarial training has been studied as a form of data
dependent regularisation [57, 56]. In this Appendix, we provide an
approximately equivalent loss function that can also be understood as a data
dependent regularisation.

Figure 8:  Behaviour of the loss function for positive and negative margins as
a function of the norm of the student estimate. A negative margin favours a
zero norm solution.

Recall the minimisation problem in Eq. 7 is

$\sum_{\mu=1}^{n}g\quantity(y^{\mu}\frac{\boldsymbol{\theta}^{\top}\boldsymbol{x}^{\mu}}{\sqrt{d}}-\varepsilon_{t}\frac{\boldsymbol{\theta}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\delta}}\boldsymbol{\theta}}{\sqrt{d}\,\sqrt{\boldsymbol{\theta}^{\top}\boldsymbol{\theta}}})+\frac{\lambda}{2}\norm{\boldsymbol{\theta}}_{2}^{2}$
(92)

where we specified the $\ell_{2}$ regularisation. Also in this Appendix we
will use $g$ to specifically indicate the logistic loss, the same analysis
could be performed for other losses similarly. We want to split the sum into a
first part, where the shifted margin is positive and a second part, where the
shifted margin is negative

$\sum_{\mu=1}^{n_{1}}g\quantity(y^{\mu}\frac{\boldsymbol{\theta}^{\top}\boldsymbol{x}^{\mu}}{\sqrt{d}}-\varepsilon_{t}\frac{\boldsymbol{\theta}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\delta}}\boldsymbol{\theta}}{\sqrt{d}\,\sqrt{\boldsymbol{\theta}^{\top}\boldsymbol{\theta}}})+\frac{\lambda}{2}\norm{\boldsymbol{\theta}}_{2}^{2}+\sum_{\mu=n_{1}+1}^{n}g\quantity(y^{\mu}\frac{\boldsymbol{\theta}^{\top}\boldsymbol{x}^{\mu}}{\sqrt{d}}-\varepsilon_{t}\frac{\boldsymbol{\theta}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\delta}}\boldsymbol{\theta}}{\sqrt{d}\,\sqrt{\boldsymbol{\theta}^{\top}\boldsymbol{\theta}}})\,.$
(93)

Here, $n_{1}$ is the number of points that have shifted positive margin. We
call a margin positive,
when$y^{\mu}\frac{\boldsymbol{\theta}^{\top}\boldsymbol{x}^{\mu}}{\sqrt{d}}-\varepsilon_{t}\frac{\boldsymbol{\theta}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\delta}}\boldsymbol{\theta}}{\sqrt{d}\,\sqrt{\boldsymbol{\theta}^{\top}\boldsymbol{\theta}}}>0$.
We expand the term with the negative margin around zero for the logistic loss
to obtain

$\sum_{\mu=1}^{n_{1}}g\quantity(\dots)+\frac{\lambda}{2}\norm{\boldsymbol{\theta}}_{2}^{2}-\frac{1}{2}\sum_{\mu=n_{1}+1}^{n}\quantity[y^{\mu}\frac{\boldsymbol{\theta}^{\top}\boldsymbol{x}^{\mu}}{\sqrt{d}}-\varepsilon_{t}\frac{\boldsymbol{\theta}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\delta}}\boldsymbol{\theta}}{\sqrt{d}\,\sqrt{\boldsymbol{\theta}^{\top}\boldsymbol{\theta}}}]+\frac{1}{8}\sum_{\mu=n_{1}+1}^{n}\quantity[y^{\mu}\frac{\boldsymbol{\theta}^{\top}\boldsymbol{x}^{\mu}}{\sqrt{d}}-\varepsilon_{t}\frac{\boldsymbol{\theta}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\delta}}\boldsymbol{\theta}}{\sqrt{d}\,\sqrt{\boldsymbol{\theta}^{\top}\boldsymbol{\theta}}}]^{2}$
(94)

The expansion around zero is justified, as a negative margin favours a zero
norm solution, which we show in Fig. 8. Note, that we successfully optimised
this formulation of the loss. We can now resume all of the terms that do not
contain $\varepsilon_{t}$ and keep just the first terms that remain

$\sum_{\mu=1}^{n_{1}}g\quantity(\dots)+\sum_{\mu=n_{1}+1}^{n}g\quantity(y^{\mu}\frac{\boldsymbol{\theta}^{\top}\boldsymbol{x}^{\mu}}{\sqrt{d}})+\frac{\lambda}{2}\norm{\boldsymbol{\theta}}_{2}^{2}+(n-n_{1})\frac{\varepsilon_{t}}{2}\frac{\boldsymbol{\theta}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\delta}}\boldsymbol{\theta}}{\sqrt{d}\,\sqrt{\boldsymbol{\theta}^{\top}\boldsymbol{\theta}}}-\frac{\varepsilon_{t}}{4}\frac{\boldsymbol{\theta}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\delta}}\boldsymbol{\theta}}{\sqrt{d}\,\sqrt{\boldsymbol{\theta}^{\top}\boldsymbol{\theta}}}\sum_{\mu=n_{1}+1}^{n}\quantity[y^{\mu}\frac{\boldsymbol{\theta}^{\top}\boldsymbol{x}^{\mu}}{\sqrt{d}}-\frac{\varepsilon_{t}}{2}\frac{\boldsymbol{\theta}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\delta}}\boldsymbol{\theta}}{\sqrt{d}\,\sqrt{\boldsymbol{\theta}^{\top}\boldsymbol{\theta}}}]\,.$
(95)

There are two types of regularisation, the first is an $\sqrt{\ell_{2}}$
regularisation and the other is a negative shifted margin dependent $\ell_{2}$
regularisation.

In our setting we suppose that the coefficient for the second term is positive
as we are considering Gaussian data and in high dimension most of the data
lies very close to the boundary.

The loss can then be written as

$\sum_{i=1}^{n}g\quantity(y_{i}\frac{\boldsymbol{\theta}^{\top}\boldsymbol{x}_{i}}{\sqrt{d}})+\tilde{\lambda}_{1}\frac{\boldsymbol{\theta}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\delta}}\boldsymbol{\theta}}{\,\sqrt{\boldsymbol{\theta}^{\top}\boldsymbol{\theta}}}+\tilde{\lambda}_{1}\boldsymbol{\theta}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\delta}}\boldsymbol{\theta}\,.$
(96)

This approximately equivalent loss can be optimised and, we can estimate the
constants $\tilde{\lambda}_{1}$ and $\tilde{\lambda}_{2}$ by optimising first
Eq. 94 on the same data-model.

$\displaystyle\tilde{\lambda}_{1}$
$\displaystyle=\frac{n_{2}}{2}\frac{\varepsilon_{t}\boldsymbol{w}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\delta}}\boldsymbol{w}}{\sqrt{d}\sqrt{\boldsymbol{w}^{\top}\boldsymbol{w}}}$
(97) $\displaystyle\tilde{\lambda}_{2}$
$\displaystyle=\frac{-\varepsilon_{t}}{8}\frac{1}{\sqrt{\boldsymbol{\theta}^{\top}\boldsymbol{\theta}}}\sum_{i=n_{1}+1}^{n}\quantity[2y_{i}\frac{\boldsymbol{\theta}^{\top}\boldsymbol{x}_{i}}{\sqrt{d}}-\frac{\varepsilon_{t}\boldsymbol{w}^{\top}\boldsymbol{\Sigma}_{\boldsymbol{\delta}}\boldsymbol{w}}{\sqrt{d}\sqrt{\boldsymbol{w}^{\top}\boldsymbol{w}}}]$

Note, that we count $n_{2}$ in the final optimisation step.

##  Appendix F Defendable Attacks and Inevitable Trade-Offs

In this Appendix we want to study the relation between the attack geometry
$\boldsymbol{\Sigma}_{\boldsymbol{\upsilon}}$ and the defence geometry
$\boldsymbol{\Sigma}_{\boldsymbol{\delta}}$. We assume to know the attack
geometry. If we can successfully defend against a geometry, without incurring
a trade-off, we call the geometry defendable, otherwise not defendable. A
trade-off does not occur, if the adversarial error is dominated by the
generalisation error and if the generalisation error behaves roughly as a
constant as a function of the protection strength $\varepsilon_{t}$.

To make a fair comparison between the geometries we are going to consider a
normalised version of the matrices
$\boldsymbol{\Sigma}_{\boldsymbol{\upsilon}}$ and
$\boldsymbol{\Sigma}_{\boldsymbol{\delta}}$ and consider the total cost of the
attack/defence to be tuned by $\varepsilon_{g}$/$\varepsilon_{t}$. We are
asking how to spend a fixed budget among the defence directions, to protect
most effectively against a given attack. Since both matrices are symmetric we
can write them as
$\boldsymbol{\Sigma}=\sum_{i=1}^{d}\lambda_{i}\boldsymbol{v}_{i}\boldsymbol{v}_{i}^{\top}$
where $\sum_{i=1}^{d}\lambda_{i}=1$ and the eigenvectors are normalised
$\norm{\boldsymbol{v}_{i}}_{2}=1$.

To keep things simple, we can suppose that the attack matrix is
$\boldsymbol{\Sigma}_{\boldsymbol{\upsilon}}=\boldsymbol{v}\boldsymbol{v}^{\top}$.
We will refer to $\boldsymbol{v}$ as the unit vector that is composed of a sum
between $\boldsymbol{\theta}_{0}$ and another vector $\boldsymbol{u}$
perpendicular to $\boldsymbol{\theta}_{0}$.

We can thus decompose the attack matrix as