# Overparameterized Linear Regression
under Adversarial Attacks

Antônio H. Ribeiro and Thomas B. Schön The authors are with the Department of
Information Technology, Uppsala University, Sweden (emails:
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

As machine learning models start to be used in critical applications, their
vulnerabilities and brittleness become a pressing concern. Adversarial attacks
are a popular framework for studying these vulnerabilities. In this work, we
study the error of linear regression in the face of adversarial attacks. We
provide bounds of the error in terms of the traditional risk and the parameter
norm and show how these bounds can be leveraged and make it possible to use
analysis from non-adversarial setups to study the adversarial risk. The
usefulness of these results is illustrated by shedding light on whether or not
overparameterized linear models can be adversarially robust. We show that
adding features to linear models might be either a source of additional
robustness or brittleness. We show that these differences appear due to
scaling and how the $\ell_{1}$ and $\ell_{2}$ norms of random projections
concentrate. We also show how the reformulation we propose allows for solving
adversarial training as a convex optimization problem. This is then used as a
tool to study how adversarial training and other regularization methods might
affect the robustness of the estimated models.

##  I Introduction

The seminal work by [1] has shown an interesting line of reasoning that help
explain how very rich models such as neural networks that are trained to
exactly fit the data can still generalize well into new datapoints. Indeed
increasing the model size has been a standard strategy in obtaining better
models of this type and one of the big mysteries behind them [2]. The so-
called double-descent phenomenon [1] provides insight into this observation
and shows that as we increase the model flexibility, it is possible to reach a
point where the training error is zero. If we continue to increase the model
complexity beyond this point, the model can eventually start to generalize
well again.

The explanation is that larger models can fit the training dataset with
smoother solutions and hence generalize better in the test. Smoothness is
naturally related to robustness. The idea that increasing the model size can
be a recipe to obtain more robust models has indeed recently been developed by
[3] using isoperimetric inequalities.

In another line of work, adversarial examples have provided a useful setting
when it comes to studying robustness. They consider inputs contaminated with
small disturbances chosen to maximize the model error when compared to the
initial and correct prediction. The susceptibility of state-of-the-art neural
network models to very small input modifications [4] gave the framework a lot
of attention from the research community. Initial speculation that the highly
nonlinear nature of deep neural networks was the cause of its vulnerabilities
to attacks [4] was later dismissed. Indeed, [5] shows that the existence of
vulnerabilities to adversarial attacks can be explained and observed in a
purely linear setting and the high dimensionality is pointed out as a main
cause of the problem.

This somewhat conflicting view of the relation between high dimensionality and
model robustness served as the driving force for this work. High-
dimensionality is both seen as a source of brittleness and as a potential
recipe for producing robust models. Indeed, linear models are a natural setup
to study and understand these ideas: not only can they be made vulnerable to
adversarial attacks, but the double-descent phenomenon can also be observed in
a purely linear setting [6, 7]. Here we show how both views can be reconciled
and how each behavior can to observed (see Figure 1).

### Contributions

This paper makes the following contributions:

  1. 1.

We show that the analysis of adversarial attacks can be significantly
simplified in linear regression problems. This is developed in Section III,
where we show how to reformulate the expression of the adversarial risk, and
in Section IV, where we obtain bounds that allow for reusing the analysis from
other setups in adversarial scenarios.

  2. 2.

The minimum-norm solution is commonly used to select overparameterized models
in connection to the study of the double-descent phenomenon [1, 6]. In Section
IV, we study the adversarial robustness of the minimum-norm solution.

    1. (a)

We use asymptotic and non-asymptotic analysis to explain when we can observe
double-descent in adversarial scenarios.

    2. (b)

We show how overparameterized models tend to become smoother in the $\ell_{2}$
norm, but not in the $\ell_{1}$ norm. It is also shown how this can be used to
explain when more features make the model more vulnerable to some types of
adversarial attacks.

  3. 3.

Adversarial training is a standard method to produce models that are robust to
adversarial attacks [8]. In Section V, we show how adversarial training
affects the conclusion obtained for minimum-norm solution models.

    1. (a)

We show how our formulation allows for solving adversarial training in linear
regression as a convex optimization problem.

    2. (b)

We show how adversarial training affects the way robustness changes with the
number of features. An illustration of cases when it is effective and when it
is not is also provided.

    3. (c)

We compare and establish similarities with ridge regression and lasso [9].

Figure 1: Double-descent vs robustness-accuracy trade-off. On the $x$-axis we
have the ratio between the number of features $m$ and the number of training
datapoints $n$. The model traditional risk (no adv.) continually decreases in
the overparameterized region, achieving significantly better results than in
the underparameterized region. On the other hand, increasing the number of
features continuously produce worse adversarial robustness for the risk of
$\ell_{\infty}$ adversarial attacks. For an $\ell_{2}$ adversary, however, the
model actually benefits from operating in the overparameterized region and
larger models yield better adversarial robustness. The precise setup for this
example is provided in Section IV-G.

### Related work

The study of adversarial attacks pre-dates the widespread use of deep neural
networks [10, 11]. An overview of earlier work is provided by [12].
Nonetheless, the susceptibility of high-performance neural networks gave this
framework higher visibility [4]. The conflict between robustness and high-
performance models is explored by [13] and [14]. Indeed, one of the examples
we give for the worst-case scenario of the $\ell_{\infty}$ adversarial error
is motivated by an idea presented in [13]. Moreover, simple examples where
high-dimensional inputs yield easy-to-construct adversarial examples are
abundant in the literature [15]. Also close to our work is that from [16],
which provides an analysis of $\ell_{\infty}$ attack on linear classifiers
based on the Rademacher complexity. They showed an unavoidable dimension
dependence, unless the weight vector has a bounded $\ell_{1}$ norm.

The analysis of the robustness of more general nonlinear models, such as
neural networks is provided in [17] and extended in [3]. They show how
overparameterization can be a recipe for robustness. An alternative view is
provided in [18, 19], where it is shown that ReLU neural networks can be made
vulnerable since what these models learn is locally very similar to random
linear functions. As we mentioned in the introduction, our work tries to
reconcile these somewhat conflicting views in the context of linear models.

The double-descent performance curve has been experimentally observed for a
variety of machine learning models, such as random Fourier features, random
forest, shallow networks, transformers and convolutional network and nonlinear
ARX models; and for datasets obtained in diverse context, including image
classification, natural language processing datasets and the identification of
nonlinear dynamical systems [1, 20, 21, 22, 23]. Theoretical models for such
phenomena are also often pursued: [6] derive non-asymptotic bounds for linear
regression models using concentration inequalities. In [21] the authors draw
connections with the physical phenomena of "jamming" in a class of glassy
systems. [24] characterize logistic regression test error using the Gaussian
min-max theorem. [25] provides bounds on the risk.

Random matrix theory has been a useful tool for studying statistical
phenomenon. The framework and its potential for explaining and studying neural
networks have been the focus of recent work [28, 29, 30]. It has also been a
powerful tool in producing theoretical models for the double-descent
phenomenon [31, 27, 7, 32, 33]. In our study of linear regression with random
covariates, we make direct use of the asymptotic results obtained by [7].

Theoretical analysis of models under adversarial attacks is currently a rather
popular topic. [26] provide asymptotics based on [27]. They take a different
approach than us and study scenarios where the adversarial attack is
constrained to not change the risk. The theoretical model is used to explain
how underspecification might present a challenge in deployment, and is backed
by experiments. Under additional assumptions, it is generally possible to
obtain sharper bounds than ours [34, 35]. Moreover, there is a plethora of
work developing exact asymptotics to the adversarial risk and for
adversarially trained models. [36] derived asymptotics for adversarial
training in binary classification. Moreover, [37] provide asymptotics for
adversarial attacks in linear regression. [38] study it in classification
settings and [39] obtain exact asymptotics for random feature regressions.

These asymptotics are often used to gain insight into the effect of
adversarial training and adversarial robustness. [37] use it to study the
trade-off between adversarial risk and standard risk using the parameter of
the adversarial training to control the trade-off between these two. [38]
studies how overparameterization affects robustness to perturbations in the
input and [40] studies how the size of the dataset affects adversarial
performance. Interestingly, while they take a very different route, our
results are consistent with theirs, and here we can observe cases where the
adversarial performance degrades as the size of the dataset increases.

The derivation of exact asymptotics is an impressive technical development,
however, we point out that it is not always trivial to gain insight from these
results. The asymptotics obtained often do not have closed-form expressions
and require the solution of either polynomials or integral equations. Here, we
advocate a simpler approach: approximating the adversarial risk using terms
that often appear in other contexts. We believe that this is a powerful tool
to gain insight into the problem, providing extra flexibility for quickly
navigating between different setups.

##  II Problem formulation

Consider a training dataset $\mathcal{S}=\\{(x_{i},y_{i})\\}_{i=1}^{n}$
consisting of $n$ i.i.d. datapoints of dimension
$\mathbb{R}^{m}\times\mathbb{R}$, sampled from the distribution
${(x_{i},y_{i})\sim P_{x,y}}$. To this data, we fit a _linear model_ from the
function class
$\left\\{\tilde{\beta}^{\mathsf{T}}x\mid\tilde{\beta}\in\mathbb{R}^{m}\right\\}$.
We use ${\hat{\beta\mkern 1.0mu}\mkern-1.0mu}{}$ to denote the parameter
estimated from the training data. The estimation method is detailed in what
follows.

We will use subscripts to denote the source of randomness considered in the
conditional expectation. For instance, let $x,y,z,w$ be random variables, we
use $\mathbb{E}_{{x,y}}\left[{f(x,y,z,w)}\right]$ to denote the expectation
with respect to $x,y$ and conditioned on the variables that are not explicitly
mentioned in the subscript, here $z$ and $w$.

Let $(x_{0},y_{0})\sim P_{x,y}$ be a point not seen during training and
independently sampled from the same distribution as the rest of the data. We
denote the out-of-sample _prediction risk_ by

$R(\hat{\beta})=\mathbb{E}_{{x_{0},y_{0}}}\left[{(y_{0}-x_{0}^{\mathsf{T}}{\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{})^{2}}\right].$ (1)

The $\ell_{p}$ _adversarial risk_ is defined as

$R^{\text{adv}}_{p}({\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{})=\mathbb{E}_{{x_{0},y_{0}}}\left[{\max_{\|\Delta
x_{0}\|_{p}\leq\delta}(y_{0}-(x_{0}+\Delta
x_{0})^{\mathsf{T}}{\hat{\beta\mkern 1.0mu}\mkern-1.0mu}{})^{2}}\right],$ (2)

which is the risk when the model is subject to a disturbance $\Delta x_{0}$
that results in the worst possible performance inside the region $\|\Delta
x_{0}\|_{p}\leq\delta$. Here, we use $\|\cdot\|_{p}$ to denote the $\ell_{p}$
norm of a vector, i.e.,

######  Definition 1 (Vector $p$-norms).

Let $a\in\mathbb{R}^{n}$ and $p\in\mathbb{R}$, $p\geq 1$, then the $p$-norm of
this vector is defined as

$\|a\|_{p}=\left(\sum_{i=1}^{n}|a_{i}|^{p}\right)^{\frac{1}{p}},$ (3)

with $\|a\|_{\infty}=\max_{1\leq i\leq n}{|a_{i}|}$.

Moreover, the _empirical risk_ is denoted by

${\hat{R\mkern
1.0mu}\mkern-1.0mu}{}(\hat{\beta})=\frac{1}{n}\sum_{i=1}^{n}{(y_{i}-x_{i}^{\mathsf{T}}{\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{})}^{2},$ (4)

where the expectation w.r.t. the true distribution is replaced by the average
over the observed training samples. We use a similar notation for the
_empirical adversarial risk_ , ${\hat{R\mkern
1.0mu}\mkern-1.0mu}{}^{\text{adv}}_{p}({\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{})$.

##  III Adversarial risk in linear regression

In this paper, we show that the adversarial risk for linear regression can be
simplified. The following lemma gives a quadratic form for the adversarial
risk defined in Eq. (2).

######  Lemma 2.

Let $q$ be a positive real number for which $\frac{1}{p}+\frac{1}{q}=1$,
then111The result still holds for the pair of values ${(p=1,q=\infty)}$ and
${(p=\infty,q=1)}$.

$R_{p}^{\text{adv}}({\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{})=\mathbb{E}_{{x_{0},y_{0}}}\left[{\left(|y_{0}-x_{0}^{\mathsf{T}}{\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{}|+\delta\|{\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{}\|_{q}\right)^{2}}\right].$ (5)

The lemma is simple, but it turns out to be a useful tool when analysing
robustness to adversarial attacks and adversarial training. A contribution of
this paper is to show how it can be used in various situations. In Section IV,
Lemma 2 is used to analyse the adversarial robustness of linear models and the
interplay between overparameterization and robustness. In Section V, we show
how the formula allows for an efficient method for adversarial training using
convex programming.

The proof of the lemma is based on Hölder’s inequality
${|\beta^{\mathsf{T}}\Delta x|\leq\|\beta\|_{p}\|\Delta x\|_{q}}$ and on the
fact that we can, given $\beta$, construct $\Delta x$ such that the equality
holds. The next proposition gives the precise construction that we will make
use of.

######  Proposition 3.

Given $p,q\in(1,\infty)$ such that $1/p+1/q=1$ and $\beta\in\mathbb{R}^{m}$,
$\Delta x\in\mathbb{R}^{m}$. We have $|\beta^{\mathsf{T}}\Delta
x|=\|\beta\|_{p}\|\Delta x\|_{q}$ when the $i$-th component is $\Delta
x_{i}=|\beta_{i}|^{q/p}$. Moreover, if $\Delta x_{i}=\text{sign}(\beta_{i})$
for every $i$, then $|\beta^{\mathsf{T}}\Delta x|=\|\beta\|_{1}\|\Delta
x\|_{\infty}$. If

$\Delta x_{i}=\frac{s_{i}}{\sum_{i}s_{i}}\quad\text{for}\quad
s_{i}=\begin{cases}1&\text{if }\beta_{i}=\max_{i}\beta_{i}\\\
0&\text{otherwise}\end{cases}$

then $|\beta^{\mathsf{T}}\Delta x|=\|\beta\|_{\infty}\|\Delta x\|_{1}$.

The above proposition is well-known. Indeed, most adversarial attacks are
constructed based on it. For instance, the Fast Gradient Sign Method (FGSM)
[5] linearizes the neural network and applies the above construction for
$p=\infty$ to obtain the adversarial perturbation. We are now ready to prove
Lemma 2.

###### Proof of Lemma 2.

For $1\leq p\leq\infty$, let $q$ be a positive real number such that
$\frac{1}{p}+\frac{1}{q}=1$. Let
$e_{0}=y_{0}-x_{0}^{\mathsf{T}}{\hat{\beta\mkern 1.0mu}\mkern-1.0mu}{}$. The
adversarial risk (2) can, after some algebraic manipulation, be rewritten as

$R_{p}^{\text{adv}}({\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{})=\mathbb{E}_{{x_{0},y_{0}}}\left[{e_{0}^{2}+\max_{\|\Delta
x_{0}\|_{p}\leq\delta}\left((\Delta x_{0}^{\mathsf{T}}{\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{})^{2}-2e_{0}\Delta x_{0}^{\mathsf{T}}{\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{}\right)}\right].$

In turn, if we let $r=\Delta x_{0}^{\mathsf{T}}{\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{}$ since $\|\Delta x_{0}\|_{p}\leq\delta$, Hölder’s
inequality yields $|r|\leq\delta\|{\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{}\|_{q}$, for $q$ satisfying $1/p+1/q=1$. Since
Proposition 3 guarantees that we can always choose vectors such that the
equality holds, the term inside the expectation of the right-hand side is
equal to:

$M=\max_{|r|\leq\delta\|{\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{}\|_{q}}(r^{2}-2e_{0}r).$

Now the maximum is attained at $r=-\delta\|{\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{}\|_{q}$ if $e_{0}\geq 0$ and at
$r=\delta\|{\hat{\beta\mkern 1.0mu}\mkern-1.0mu}{}\|_{q}$ if $e_{0}<0$, hence
$M=\delta^{2}\|{\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{}\|_{q}^{2}+2\delta\|{\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{}\|_{q}|e_{0}|$ and

$R_{p}^{\text{adv}}({\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{})=\mathbb{E}_{{x_{0},y_{0}}}\left[{\delta^{2}\|{\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{}\|_{q}^{2}+2\delta\|{\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{}\|_{q}|e_{0}|+|e_{0}|^{2}}\right].$ (6)

∎

##  IV Adversarial robustness of linear models

Lemma 2 provides an easy to analyse formula for the adversarial risk. By
expanding the square and using the linearity of the expectation we obtain:

$R_{p}^{\text{adv}}({\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{})=\delta^{2}\|{\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{}\|_{q}^{2}+2\delta\|{\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{}\|_{q}\mathbb{E}_{{x_{0},y_{0}}}\left[{|y_{0}-x_{0}^{\mathsf{T}}{\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{}|}\right]+R({\hat{\beta\mkern 1.0mu}\mkern-1.0mu}{}).$
(7)

An approximation of Eq. (7) can be obtained by simply dropping the middle term
on the right-hand side

$R_{p}^{\text{adv}}({\hat{\beta\mkern 1.0mu}\mkern-1.0mu}{})\approx
R({\hat{\beta\mkern 1.0mu}\mkern-1.0mu}{})+\delta^{2}\|{\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{}\|_{q}^{2}.$ (8)

We will formalize the notion later. However, for now, we just highlight that
this approximation makes the similarity between the adversarial risk and other
loss functions used in more traditional regularized regression settings
explicit. We can naturally see similarities with lasso for $q=1$ and with
ridge regression for $q=2$.

The approximation is also a useful simplification since it allows for the
analysis of adversarial robustness from values that are often obtained from
other analysis (the traditional risk and the parameter norm). For instance,
from the double-descent literature, it is well-known that the $\ell_{2}$-norm
of the estimated parameter often also exhibits a double-descent behavior as a
function of the number of features. This is observed experimentally, for
instance, by [1]. Hence, the above approximation gives an easy way to
understand why we can expect double-descent behavior for the $\ell_{2}$
adversarial risk. The approximation is also enough to justify the potential
brittleness of high-dimensional models. The next example demonstrates a fairly
simple case where such behavior can be observed.

###  IV-A Motivating example: weak features

In this section, we show brittleness and vulnerability to $\ell_{\infty}$
adversarial attacks arising from high dimensionality. [13] makes use of a
linear example to motivate their argument that robustness and accuracy might
be at odds. We show a modified construction222The construction is quite
similar. The only differences are: 1) it is a regression problem rather then a
classification problem; and, 2) we use $y/\eta$ rather than $y$ as the
conditional mean of $x^{j}$ (in Eq. (9)). This is done to ensure that the
signal-to-noise ratio is constant with $\eta$. to motivate how brittleness
might appear in linear examples. The construction makes use of many features
that are weakly correlated with the output. Let the input
$x=(x^{1},\cdots,x^{m})$ and the output $y$ be normally distributed:

$y\sim\mathcal{N}(0,1)\text{ and }x^{j}\mid
y\sim\mathcal{N}\left(\frac{y}{\eta},\frac{1}{\eta}\right)\text{ for
}j=1,\dots,m.$ (9)

Following the choice of [13], we use $\eta=\frac{1}{\sqrt{m}}$ so that
$\mathbb{E}_{{x}}\left[{\|x\|_{2}}\right]$ remains constant with the number of
features. Here, we can show that the optimal predictor ${{\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{}=\left[\frac{1}{\sqrt{m}},\cdots,\frac{1}{\sqrt{m}}\right]}$
results in a prediction $\hat{y}={\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{}^{\mathsf{T}}x$ that follows the distributions
${({\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{}^{\mathsf{T}}x)|y\sim\mathcal{N}(y,\frac{1}{m})}$. This
means that the prediction risk of this model is $R({\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{})=\mathbb{E}_{{x,y}}\left[{(y-{\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{}^{\mathsf{T}}x)^{2}}\right]=\frac{1}{m}$. Hence, the risk
of our predictor goes to zero $R\rightarrow 0$ as the number of features goes
to infinity, $m\rightarrow\infty$.

Here, $\|{\hat{\beta\mkern 1.0mu}\mkern-1.0mu}{}\|_{1}=\sqrt{m}$, implying
that the $\ell_{\infty}$ adversarial risk would grow with a rate $\Omega(m)$
by Eq. (8). This is one example where the traditional risk goes to zero with
the number of features at the same time as the $\ell_{\infty}$ adversarial
risk grows indefinitely.

There are two aspects of this example that we will further refine in the
coming sections. The first is that we are using an estimator that is obtained
by minimizing the true risk, which is not a procedure that can be used in
practice. In what follows, we show that a similar effect can be obtained if
the empirical risk is minimized. The second aspect is the scaling $\eta$, we
will motivate different choices and show how they can yield quite different
results.

###  IV-B Preliminaries

Here we focus the minimum norm solution, which is often used when studying the
behavior of overparameterized models in connection with the double-descent
phenomenon [1]. In our analysis, we will formalize the notion conveyed by the
approximation in Eq. (8), using the upper and lower bounds

$R({\hat{\beta\mkern 1.0mu}\mkern-1.0mu}{})+\delta^{2}\|{\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{}\|_{q}^{2}\leq R_{p}^{\text{adv}}({\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{})\leq\left(\sqrt{R({\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{})}+\delta\|{\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{}\|_{q}\right)^{2},$ (10)

which follow directly from Lemma 2. We will assume that the training and test
data have been generated linearly with additive noise:

$\displaystyle(x_{i},\epsilon_{i})\sim P_{x}\times P_{\epsilon},\qquad
y_{i}=x_{i}^{\mathsf{T}}\beta+\epsilon_{i},$ (11)

where $P_{\epsilon}$ is a distribution in $\mathbb{R}$ such that
$\mathbb{E}\left[{\epsilon_{i}}\right]=0$ and
$\mathbb{V}\left[{\epsilon_{i}}\right]=\sigma^{2}$ and $\epsilon_{i}$ is
assumed to be independent of $x_{i}$. Moreover,
$\mathbb{E}\left[{x_{i}}\right]=0$ and $\text{Cov}\left[x_{i}\right]=\Sigma$.
The $\ell_{2}$ norm of the data generation parameter is denoted by
$\|\beta\|^{2}_{2}=r^{2}$.

Let $X\in\mathbb{R}^{n\times m}$ denote the matrix consisting of stacked
training inputs $x_{i}^{\mathsf{T}}$ and similarly let $y\in\mathbb{R}^{n}$
denote the output vector. The parameters are estimated as

${\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{}=(X^{\mathsf{T}}X)^{\dagger}X^{\mathsf{T}}y,$ (12)

where $(X^{\mathsf{T}}X)^{\dagger}$ represents the pseudo-inverse of
$X^{\mathsf{T}}X$. In the underparameterized ($m<n$) region, it corresponds to
the least-square solution. In the overparameterized ($m>n$) case, when more
than one solution is possible, this corresponds to the solution for which the
parameter norm $\|{\hat{\beta\mkern 1.0mu}\mkern-1.0mu}{}\|_{2}$ is minimum,
the minimum-norm solution.

From Eq. (11) and Eq. (12) it follows that:

$\hat{\beta}=\underbrace{(X^{\mathsf{T}}X)^{\dagger}X^{\mathsf{T}}X}_{\Phi}\beta+\underbrace{(X^{\mathsf{T}}X)^{\dagger}}_{n\hat{\Sigma}^{\dagger}}X^{\mathsf{T}}\epsilon,$
(13)

where we denote $\hat{\Sigma}=\frac{1}{n}X^{\mathsf{T}}X$,
$\Phi=\hat{\Sigma}^{\dagger}\hat{\Sigma}$ and $\Pi=I-\Phi$. Here, $\Phi$ and
$\Pi$ are orthogonal projectors: $\Pi$ is the projection into the null space
and $\Phi$ into the row space of $X$. The first term in Eq. (13) can be
understood as a projection of the original parameter into the row space of the
regressors and it is the parameters estimated in a noiseless scenario. The
second term is the consequence of the noise. It follows from it, that the risk
and the expected parameter norm can be decomposed as in the next Lemma. The
proof is provided in the Supplementary Material.

######  Lemma 4 (Bias-variance decomposition).

Denote $\|z\|_{\Sigma}^{2}=z^{\mathsf{T}}\Sigma z$. The expected risk and
$\ell_{2}$ parameter norm are

$\displaystyle\mathbb{E}_{{\epsilon}}\left[{R(\beta)}\right]$ $\displaystyle=$
$\displaystyle\|\Pi\beta\|_{\Sigma}^{2}+\frac{\sigma^{2}}{n}\text{tr}(\hat{\Sigma}^{\dagger}\Sigma)+\sigma^{2},$
(14) $\displaystyle\mathbb{E}_{{\epsilon}}\left[{\|{\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{}\|_{2}^{2}}\right]$ $\displaystyle=$
$\displaystyle\|\Phi\beta\|_{2}^{2}+\frac{\sigma^{2}}{n}\text{tr}(\hat{\Sigma}^{\dagger}).$
(15)

The following bounds can be used in conjunction with Lemma 4 to analyze the
adversarial risk

$R+\delta^{2}L_{q}\leq
R_{p}^{\text{adv}}\leq\left(\sqrt{R}+\delta\sqrt{L_{q}}\right)^{2},$ (16)

where $L_{q}=\mathbb{E}_{{\epsilon}}\left[{\|{\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{}\|_{q}^{2}}\right]$,
$R=\mathbb{E}_{{\epsilon}}\left[{R({\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{})}\right]$ and
$R_{p}^{\text{adv}}=\mathbb{E}_{{\epsilon}}\left[{R_{p}^{\text{adv}}({\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{})}\right]$.

Figure 2: Adversarial $\ell_{2}$ risk, isotropic features. The solid line
shows the upper and lower bounds on the asymptotic risk. The results are for
isotropic features with $r^{2}=2$, $\sigma^{2}=1$. The error bars give the
median and the 0.25 and 0.75 quantiles obtained from numerical experiments (10
realizations) with a fixed training dataset of size $n=300$.

###  IV-C Isotropic feature model

Here, we analyse the case of isotropic features, i.e. we assume that the input
$x_{i}$ has mean zero and unit variance ($\Sigma=I_{m}$). For this case,
results from random matrix theory can be used to establish asymptotics for the
terms in Eqs. (14) and (15).

######  Lemma 5 (Isotropic features, [7]).

For isotropic features with a moment of order greater than 4 that is finite.
As $m,n\rightarrow\infty$, $m/n\rightarrow\gamma$, almost surely

$\displaystyle\mathbb{E}_{{\epsilon}}\left[{R(\hat{\beta})}\right]$
$\displaystyle\rightarrow$
$\displaystyle\begin{cases}\sigma^{2}\frac{\gamma}{1-\gamma}+\sigma^{2}&\gamma<1,\\\
r^{2}(1-\frac{1}{\gamma})+\sigma^{2}\frac{1}{\gamma-1}+\sigma^{2}&\gamma>1,\end{cases}$
(17) $\displaystyle\mathbb{E}_{{\epsilon}}\left[{\|{\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{}\|_{2}^{2}}\right]$ $\displaystyle\rightarrow$
$\displaystyle\begin{cases}r^{2}+\sigma^{2}\frac{\gamma}{1-\gamma}&\gamma<1,\\\
r^{2}\frac{1}{\gamma}+\sigma^{2}\frac{1}{\gamma-1}&\gamma>1.\end{cases}$ (18)

Both terms do have an asymptotic behavior that depends on the ratio $\gamma$
between the number of features ($m$) and the number of training datapoints
($n$). In Figure 2, we illustrate one example of how the bounds in (16) can be
combined with the asymptotic results above to obtain asymptotic lower and
upper bounds. The results obtained from the experiments closely follow these
asymptotic bounds.

Let us already now informally point out that the second part of Lemma 5 states
that for a sufficiently large problem, in the overparameterized region,

$\|\hat{\beta}\|^{2}_{2}\approx\left(r^{2}\frac{1}{m/n}+\sigma^{2}\frac{1}{m/n-1}\right).$
(19)

We formalize the notion in Section IV-D using concentration of measure. It
follows from it that even for a fixed signal magnitude, the norm of the
estimated parameter decays with the number of parameters for overparameterized
problems, i.e.,
$\|\hat{\beta}\|_{2}=\mathcal{O}\left((\frac{m}{n})^{-\frac{1}{2}}\right)$.
The model becomes ‘smoother‘ as more parameters are added to the model. This
naturally yields models more robust to $\ell_{2}$ perturbations. This can be
observed in Figure 2: after the local minima $\gamma=\frac{r}{r+\sigma}$ in
the standard risk, the risk is increasing with $\gamma$. However, the
adversarial risk for, say, $\delta=2$ is decreasing due to the tendency of the
minimum-norm solution to select smoother solutions. Moreover, while the
standard risk does not have better results in the overparameterized region
than in the underparameterized region, the adversarial risk in the
overparameterized region can actually be better than the adversarial risk in
the underparameterized region.

###  IV-D Non-asymptotic results for the parameter $\ell_{2}$ norm

Central to our analysis of $\ell_{2}$ adversarial attacks is the idea that the
parameter norm decays with the rate
$\mathcal{O}\left((\frac{m}{n})^{-\frac{1}{2}}\right)$ even when the data
generator parameter remain constant, i.e. $\|\beta\|_{2}=r$. The next theorem
formalizes this intuition. We do not attempt to provide the most general
result, instead, our choice of formulation is motivated by the fact that many
of the steps in proving this theorem can be carried on to the $\ell_{1}$ norm,
as we will discuss later.

######  Theorem 6.

Let the data be generated according to Eq. (11). Assume additionally that
$m>n$ and:

  1. 1.

The noise $\epsilon$ and the regressors $x$ are sub-Gaussian.

  2. 2.

the regressor vector $x$ is sampled from a rotationally invariant
distribution.

Then there exists constants $c,C>0$ such that for all $t<\sqrt{\frac{m}{n}}$
with probability ${1-2\exp(-ct^{2}n)}$ we have:

$\|\hat{\beta}\|_{2}\leq
r\frac{1+t}{\sqrt{\nicefrac{{m}}{{n}}}}+\sigma\frac{1+t}{C\sqrt{\nicefrac{{m}}{{n}}}-1}.$

This theorem provides a non-asymptotic result and an exponential rate of
convergence. It strengthens the assumptions from the previous section in two
ways. First, it assumes the variables are sub-Gaussian, which is used to
obtain an exponential rate of convergence. If this assumption is relaxed lower
rates of concentration are obtained. For instance, [7] does not assume this,
which results in a convergence rate of $n^{-1/7}$.

Secondly, it assumes the regressor vector to be rotationally invariant. That
is, given an orthogonal matrix $Q$, multiplication by this matrix does not
alter the distribution of the original vectors, i.e. $x\sim Qx$. Standard
examples where $x$ is rotationally invariant are values sampled from standard
Gaussian or from the uniform distribution over the sphere. Rotational
invariance implies isotropy but not all isotropic distributions are
rotationally invariant. Hence, this is again a stronger assumption.

From Lemma 4 we have:

$\mathbb{E}_{{\epsilon}}\left[{\|{\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{}\|_{2}^{2}}\right]=\|\Phi\beta\|^{2}_{2}+\frac{\sigma^{2}}{n}\text{tr}(\hat{\Sigma}^{\dagger}).$

The next Lemma gives concentration inequalities for the eigenvalues of
$\hat{\Sigma}^{\dagger}$. If we use $\lambda_{i}(\hat{\Sigma}^{\dagger})$ to
denote the $i$-th eigenvalue of $\hat{\Sigma}^{\dagger}$, we have that
$\text{tr}(\hat{\Sigma}^{\dagger})=\frac{1}{n}\sum_{i}\lambda_{i}(\hat{\Sigma}^{\dagger})$.
Hence, the following result immediately implies that the second term of the
above expression concentrates around $\Theta((\frac{m}{n})^{-1})$. The proof
is provided in the Supplementary Material.

######  Lemma 7.

Let $x_{i}\in\mathbb{R}^{m}$ be independently sampled sub-Gaussian random
vectors, $\hat{\Sigma}=\frac{1}{n}\sum_{i=1}^{n}x_{i}x_{i}^{\mathsf{T}}$, and
let $m>n$. Then there exist a constant $C>0$ such that, with probability
greater then $1-2\exp(-m)$,

$\frac{1}{\left(C\sqrt{\frac{m}{n}}+1\right)^{2}}\leq\lambda_{i}(\hat{\Sigma}^{\dagger})\leq\frac{1}{\left(C\sqrt{\frac{m}{n}}-1\right)^{2}}.$

Next, we turn to the analysis of the first term in Eq. (15). In the case
$m>n$, $\Phi$ is a projection matrix that projects a vector from
$\mathbb{R}^{m}$ into a subspace of dimension $n$. The set of all possible
subspaces of dimension $n$ in $\mathbb{R}^{m}$ is well studied and known as
the Grassmannian manifold $G(m,n)$. There is a one-to-one relationship between
the projection matrices $\Phi$ and the points in this manifold. For the case
when $X$ is rotationally invariant, we have, given any orthogonal matrix $Q$
that

$\Phi=(X^{\mathsf{T}}X)^{\dagger}(X^{\mathsf{T}}X)\sim
Q(X^{\mathsf{T}}X)^{\dagger}(X^{\mathsf{T}}X)Q^{\mathsf{T}}=Q\Phi
Q^{\mathsf{T}}.$

Hence, the subspace is invariant to rotation and it is possible to establish
that the matrix $\Phi$ is a random projection that projects into a subspace
sampled uniformly (i.e., Haar measure) from the Grassmannian $G(m,n)$. The
next result is from [41, Lemma 5.3.2] and it states that the norm
$\|\Phi\beta\|_{2}$ of the projection of $\beta$ into this $n$ dimensional
subspace concentrates around $\sqrt{\frac{n}{m}}\|\beta\|$.

######  Lemma 8 ([41, Lemma 5.3.2 ]).

Let $\beta\in\mathbb{R}^{m}$ be a vector and $\Phi\in\mathbb{R}^{m\times m}$
be a projection from $\mathbb{R}^{m}$ onto a random $n$-dimensional subspace
uniformly sampled from $G(m,n)$. Then,

  1. 1.

$\mathbb{E}_{{\Phi}}\left[{\|\Phi\beta\|_{2}^{2}}\right]=\frac{n}{m}\|\beta\|_{2}^{2}$;

  2. 2.

There exist a constant $c$, such that with probability greater then
$1-2\exp(-ct^{2}n)$, we have:

$(1-t)\sqrt{\frac{n}{m}}\|\beta\|_{2}\leq\|\Phi\beta\|_{2}\leq(1+t)\sqrt{\frac{n}{m}}\|\beta\|_{2}$
(20)

The proof of Theorem 6 follows from the lemmas and from the proposition below.
The proof for the following proposition is provided in the Supplementary
Material.

######  Proposition 9.

We have that:

$\left|\|{\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{}\|_{2}-\|\Phi\beta\|_{2}\right|\leq\frac{1}{\sqrt{n}}\sqrt{\|\hat{\Sigma}^{\dagger}\|_{2}}\|\epsilon\|_{2}.$
(21)

###### Proof of Theorem 6.

From Proposition 9 we have
$\|\hat{\beta}\|_{2}\leq\|\Phi\beta\|_{2}+\frac{\|\epsilon\|_{2}}{\sqrt{n}}\sqrt{\lambda_{\max}(\hat{\Sigma}^{\dagger})}$.
Due to the fact that the noise is sub-Gaussian, a straightforward application
of Theorem 3.1.1 from [41] implies that
$\left|\frac{\|\epsilon\|_{2}}{\sqrt{n}}-\sigma^{2}\right|\leq t$ with
probability greater than $1-2\exp(ct^{2}n)$. This together with Lemma 7
results in the desired upper bound for the second term. The first term can be
bounded using Lemma 8, which yields the desired result. ∎

We mention here that Lemma 4 could provide another possible route to prove
similar results and (most likely) tighter bounds. Nonetheless, here, we choose
to use Proposition 9 for two reasons: 1) it can be easily combined with non-
asymptotic results; 2) the same argument applied above can be extended for any
other $p$-norms. We also point out that an analogous procedure could be used
to provide a lower bound on $\|\hat{\beta}\|_{2}$.

###  IV-E $\ell_{p}$ adversaries

(a) Risk

(b) Parameter norm

Figure 3: Adversarial $\ell_{p}$ risk, isotropic features. The error bars give
the median and the 0.25 and 0.75 quantiles obtained from numerical experiments
(10 realizations) with a fixed training dataset of size $n=100$ and for
adversarial disturbances of magnitude $\delta=2$. The shaded region in blue
give the upper and lower bounds for $p=2$. The bounds obtained from norm
inequalities (22) for $p,q\in\\{1,\infty\\}$ are given in red and green. The
results are for $r^{2}=1$, $\sigma^{2}=1$.

We now turn to the study of $\ell_{p}$ adversarial attacks when $p\not=2$. As
in Eq. (16), let $q$ be the complement of $p$. The following well-known
relationship between vector norms will be useful in our developments.

######  Lemma 10 (Relationship between vector $p$-norms).

Let $p$ and $q$ be values in the range $[1,\infty]$ and ${\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{}\in\mathbb{R}^{m}$. Assume that $q>p$, then:

$\|{\hat{\beta\mkern 1.0mu}\mkern-1.0mu}{}\|_{q}\leq\|{\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{}\|_{p}\leq m^{1/p-1/q}\|{\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{}\|_{q}.$ (22)

The leftmost inequality follows from an application of Minkowski’s inequality
and the rightmost from an application of Hölder’s inequality.

The asymptotic results from Lemma 5 to compute $R$ and $L_{2}$ can now be used
in conjunction with the above inequalities to find the upper and lower bounds
on the adversarial risk. Hence, for any $1\leq p<2$, the upper bound is the
same as the upper bound obtained for $\ell_{2}$ attacks. However, there is a
new multiplicative term in the lower bound. For instance, the $\ell_{1}$
adversarial risk is bounded by

$R({\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{})+\frac{\delta^{2}}{m}\|{\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{}\|_{2}^{2}\leq R_{1}^{\text{adv}}({\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{})\leq\left(\sqrt{R({\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{})}+\delta|{\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{}\|_{2}\right)^{2}.$ (23)

On the other hand, for $\ell_{p}$ adversarial attacks with $p>2$, we obtain an
asymptotic upper bound that grows with $m^{1-\frac{2}{p}}$. As an example, for
$\ell_{\infty}$ attacks,

$R({\hat{\beta\mkern 1.0mu}\mkern-1.0mu}{})+\delta^{2}\|{\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{}\|_{2}^{2}\leq R_{\infty}^{\text{adv}}({\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{})\leq\left(\sqrt{R}+\delta\sqrt{m}\\\ |{\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{}\|_{2}\right)^{2}.$ (24)

In Figure 3(a) we illustrate the bounds obtained in this way. We note that the
$\ell_{\infty}$ adversarial risk follows the upper bound closely. Moreover,
Lemma 10 implies that

$\|\hat{\beta}\|_{2}\leq\|\hat{\beta}\|_{1}\leq\sqrt{m}\|\hat{\beta}\|_{2}.$
(25)

From Figure 3(b) we see that the $\ell_{1}$ norm of the estimated parameter
seemingly follows the upper bound closely. The adversarial risk also seems to
follow the upper bound closely. Next, we provide some insight into this
observation, by following the same steps used in the non-asymptotic analysis
of the $\ell_{2}$ parameter norm.

Lemma 8 show how $\|\Phi\beta\|_{2}$ concentrate around
$\sqrt{\frac{n}{m}}\|\beta\|_{2}$. One might wonder whether similar
concentration inequalities can be obtained also for the $\ell_{1}$ norm. In
Figure 4 we illustrate the experiments for both $\|\Phi\beta\|_{1}$ and
$\|\Phi\beta\|_{2}$. The first plot just illustrate the results know from the
$\ell_{2}$ norm (i.e. Lemma 8) the second plot seem to suggest that the
$\ell_{1}$ norm of the projection concentrates around
$c\sqrt{n}\|\beta\|_{2}$. From the experiments, we also estimate that
$c\approx 0.8$. We state this result as a conjecture.

######  Conjecture 11.

Let $\Phi$ be a projection from $\mathbb{R}^{m}$ onto a random $n$-dimensional
subspace uniformly sampled from $G(m,n)$. Let $\beta\in\mathbb{R}$. Then,
there is a constant $c$ such that,

$|\|\Phi\beta\|_{1}-c\sqrt{n}\|\beta\|_{2}|<t$

with probability higher then $p(t)$.

We leave the proof of this conjecture for future work. Here, we limit
ourselves to point out that this conjecture does have important consequences
for the study of overparameterized models: the idea that overparameterization
yield smoother models is at the heart of the explanation of their good
performance. The conjecture shows that, while this might be the case for the
$\ell_{2}$ norm, it might not be the case for the $\ell_{1}$ norm. Indeed, the
conjecture implies that with high probability

$\left|\frac{\|\Phi\beta\|_{1}}{\|\Phi\beta\|_{2}}-c\sqrt{m}\|\beta\|_{2}\right|<t.$
(26)

Now, using exactly the same argument as in Lemma 9, we obtain

$\|\Phi\beta\|_{1}-\|\epsilon\|_{2}\sqrt{\tfrac{m}{n}\|\hat{\Sigma}^{\dagger}\|_{2}}\leq\|{\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{}\|_{1}\leq\|\Phi\beta\|_{1}+\|\epsilon\|_{2}\sqrt{\tfrac{m}{n}\|\hat{\Sigma}^{\dagger}\|_{2}}$

The conjecture implies that $\|\Phi\beta\|_{1}=\Theta(\sqrt{n})\|\beta\|_{2}$,
and Lemma 7 implies that the second term is
$\Theta(\sqrt{n})\|\epsilon\|_{2}$. Hence, for a sufficiently large signal-to-
noise ratio ($r>\sigma$) it follows from the conjecture that
$\|{\hat{\beta\mkern 1.0mu}\mkern-1.0mu}{}\|_{1}=\Theta(\sqrt{n})$. Since we
obtained in the Theorem 6 that $\|{\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{}\|_{2}=\Theta(\sqrt{\frac{n}{m}})$, it follows that
$\|{\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{}\|_{1}=\Theta(\sqrt{m})\|{\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{}\|_{2}$, which is consistent with the results we are
experimentally observing.

(a) $\ell_{2}$ norm of projection

(b) $\ell_{1}$ norm of projection

Figure 4: Random projection and norms. Let $\Phi$ be a (uniform) random
projection from $R^{n}$ into a subspace of dimension $m$. The full lines give
the values predicted when $m<n$: $(m/n)^{-1/2}$ for the $\ell_{2}$ norm; and,
the constant rate $c\sqrt{n}$ for $c=0.8$ for the $\ell_{1}$ norm. The error
bars give the median and interquartile range of $100$ experiments.

###  IV-F Scaling

The scaling of variables plays an important role in the analysis. Assume that
a given ${\hat{\beta\mkern 1.0mu}\mkern-1.0mu}{}$ was estimated and the
corresponding model prediction is ${\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{}^{\mathsf{T}}x$. By simply redefining the input variable
as $\tilde{x}=\frac{1}{\eta}x$ we could obtain an equivalent model
$\tilde{\beta}^{\mathsf{T}}\tilde{x}$ that, for
$\tilde{\beta}=\eta{\hat{\beta\mkern 1.0mu}\mkern-1.0mu}{}$, would yield
exactly the same predictions.

Notice that while the standard risk $R$ for this new, rescaled, model is
exactly the same as the first, the norm of the estimated parameter
$\|\tilde{\beta}\|_{q}$ is $\eta$ times larger. The adversarial risk is not
the same for the two models, as an inspection of Eq. (16) reveals. The
difference is because the relative magnitude of the adversarial disturbance is
larger in the second model (even though it is the same in absolute value).

Since we are interested in the impact that the number of parameters $m$ has on
adversarial robustness, we will let the scaling factor depend on this
parameter, i.e. $\eta=\eta(m)$. The next proposition motivates two choices of
scaling. The proof is provided in the Supplementary Material.

######  Proposition 12.

Let $x$ be an isotropic random vector,
$\mathbb{E}\left[{\|x\|_{2}^{2}}\right]=m$. Additionally, if $x$ is a sub-
Gaussian random vector, then
$\mathbb{E}\left[{\|x\|_{\infty}}\right]=\Theta(\sqrt{\log(m)})$.

Hence, either $\eta(m)=\sqrt{m}$ or $\eta(m)=\sqrt{\log{m}}$ are quite natural
choices of the scaling factor. They render, respectively, the expected
$\ell_{2}$ and $\ell_{\infty}$ norms of the input vector constant as the
number of features $m$ varies.

Assume that the inputs are redefined as
$\tilde{x}_{i}=\frac{1}{\eta(m)}x_{i}$. A quick inspection of Eq. (12) reveals
that the estimated parameter is $\tilde{\beta}=\eta(m){\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{}$. The risk $R({\hat{\beta\mkern 1.0mu}\mkern-1.0mu}{})$
does not change by the transformation, but the expected squared norm of the
parameter does,
${\|\tilde{\beta}\|_{2}=\left(\eta(m)\right)^{2}\|\hat{\beta}\|_{2}}$. Hence,
when $\eta(m)=\sqrt{\log{m}}$, it follows from Eq. (19) that

$\|\tilde{\beta}\|_{2}^{2}\approx\log
m\left(r^{2}\frac{1}{m/n}+\sigma^{2}\frac{1}{m/n-1}\right).$ (27)

Here, the logarithmic term changes slowly compared to the linear term in the
denominator. Hence, the result is similar to what was obtained without any
scaling. On the other hand, the square root scaling $\eta(m)=\sqrt{m}$ yields:

$\|\tilde{\beta}\|_{2}^{2}\approx r^{2}n+\sigma^{2}\frac{1}{1/n-1/m}.$ (28)

Here, the parameter norm does not go to zero. Instead, it approaches a
constant as $m\rightarrow\infty$. The behavior is illustrated in Figure S.1 in
the Supplementary material. One interesting consequence of Eq. (28) is that
$\|\tilde{\beta}\|_{2}$ grows with the number of training datapoints. Hence,
the $\ell_{2}$ adversarial performance degrades as we add more training data
points.

The situation is even more pathological in the case of $\ell_{\infty}$
adversarial attacks. In Figure 5, we show the $\ell_{\infty}$ adversarial risk
as a function of $m$ when the input is scaled by $\eta(m)=\sqrt{m}$ and
$\eta(m)=\sqrt{\log(m)}$. We also provide the upper bound obtained from Lemma
5 and inequality (24). The behavior of $\ell_{\infty}$ adversarial attacks is
governed by $\|\tilde{\beta}\|_{1}$ (see Eq. (10)) and we have
$\|\tilde{\beta}\|_{1}=\Theta(\sqrt{m})\|\tilde{\beta}\|_{2}$ (recall Section
IV-E). Hence, (28) and (27) yield, respectively,
$\|\tilde{\beta}\|_{1}=\Theta(\sqrt{m})$ and
$\|\tilde{\beta}\|_{1}=\Theta(\sqrt{\log m})$, which explain the behavior we
observe in the figure.

Figure 5: Adversarial $\ell_{\infty}$ risk, isotropic features. The asymptotic
upper bound is indicated by the full trace. The error bars give the median and
the 0.25 and 0.75 quantiles obtained from numerical experiments (10
realizations). The analysis is performed for a fixed training dataset of size
$n=100$ and for adversarial disturbances of magnitude $\delta=0.1$. The
results are for $r^{2}=1$, $\sigma^{2}=1$. We show the results for two
different scalings: $\eta(m)=\sqrt{m}$ and $\eta(m)=\sqrt{\log(m)}$.

###  IV-G Latent space model

For the model studied in the previous section it is in general possible to
achieve models with smaller test error in the underparameterized than in the
overparameterized region. Thus, it could be argued that the lack of
$\ell_{\infty}$ adversarial robustness in the overparameterized region should
not be a problem in practice. Let us now illustrate a different data
generation procedure for which we have better performance in the
overparameterized regime and, as we add more features, the performance is
continuously improved. It is still, however, possible to observe that the
$\ell_{\infty}$ adversarial robustness degrades indefinitetly with the number
of features (recall Figure 1).

(a) $\ell_{2}$ attacks

(b) $\ell_{\infty}$ attacks

Figure 6: Adversarial risk for a latent model. The median and interquartile
range of the adversarial risk is obtained from numerical experiments (10
realizations) and indicated by error bars. Unlike the other plots, here the
shaded region indicates the upper and lower bounds obtained empirically from
Eq. (10). Where the empirical risk in the test and the parameter norm are
obtained from the experiments. The analysis is performed for adversarial
disturbances of magnitude $\delta=0.1$ and for a training dataset with size
$n=200$. The results are for $\sigma_{\xi}^{2}=0.1$ and for a latent space
with constant dimension $d=20$. We show the results for two different
scalings: $\eta(m)=\sqrt{m}$ and $\eta(m)=\sqrt{\log(m)}$.

We consider a data model where the features $x$ are noisy observations of a
lower-dimensional subspace of dimension $d$. A vector in this latent space is
represented by $z\in\mathbb{R}^{d}$. This vector is indirectly observed via
the features $x\in\mathbb{R}^{m}$ according to

$x=Wz+u,$ (29)

where $W$ is a $m\times d$ matrix, for $m\leq d$. We assume that the responses
are described by a linear model in this latent space

$y=\theta^{\mathsf{T}}z+\xi,$ (30)

where $\xi\in\mathbb{R}$ and $u\in\mathbb{R}^{m}$ are mutually independent
noise variables. Moreover, $\xi\sim\mathcal{N}(0,\sigma_{\xi}^{2})$ and
$u\sim\mathcal{N}\left(0,I_{m}\right)$. We consider the features in the latent
space to be isotropic and normal $z_{i}=\mathcal{N}\left(0,I_{d}\right)$. To
facilitate the analysis, we choose $W$ such that its columns are orthogonal,
$W^{\mathsf{T}}W=\frac{m}{d}I_{d}$, where the factor $\frac{m}{d}$ is
introduced to guarantee that the signal-to-noise ratio of the feature vector
$x$ (i.e. $\frac{\|Wz_{i}\|_{2}^{2}}{\|u_{i}\|_{2}^{2}}$) is kept constant.

This model is related to the other setups we have presented so far. The weak
feature example (Section IV-A) is a special case of this model class with
$\theta=1$, $\sigma_{\xi}=0$, and $W~{}=~{}1$. Moreover, this latent model can
actually be written as in Eq. (11), as we show in the Supplementary Material
Section D.

Assume a training dataset $\\{(x_{i},y_{i})\\}_{i=1}^{n}$ generated using the
above procedure. To this data we fit a linear model $\hat{\beta}x_{i}$ using
the minimum-norm solution. Most of the arguments we presented for the
isotropic case can be reused here. Asymptotics from [7] are available in the
Supplementary Material. From our non-asymptotic analysis in the isotropic case
we obtained
$\|\hat{\beta}\|_{2}=\mathcal{O}\left(\frac{1}{\sqrt{m/n}}\right)$, the same
rate is obtained here. See Supplementary Material Section D.

If again, we allow the input to be scaled, i.e.
$\tilde{x}_{i}=\frac{1}{\eta(m)}x_{i}$, a similar analysis shows that the
factors $\eta(m)=\sqrt{m}$ and $\eta(m)=\sqrt{\log(m)}$ would correspond to
keeping $\mathbb{E}_{{x}}\left[{\|x\|_{2}}\right]$ and
$\mathbb{E}_{{x}}\left[{\|x\|_{\infty}}\right]$ constant, respectively. In
Figure 6 we illustrate the results for the two scalings and a fixed latent
dimension $d=20$. We observe that the adversarial $\ell_{2}$ risk, for both
input scalings, continuously decrease in the overparameterized region and
achieve better results there than in the underparameterized region. The
adversarial $\ell_{\infty}$ risk, on the other hand, presents quite a
different behavior depending on the scaling. For $\eta(m)=\sqrt{m}$ it
displays a linear growth with the number of parameters in the
overparameterized region, while it remains basically constant in the case
$\eta(m)=\sqrt{\log(m)}$. Figure 1 is an illustration of this same setting
where we also include the standard risk in the same plot (scaling
$\eta(m)=\sqrt{m}$). Additional results are presented in Supplementary
Material Section D.

##  V Adversarial training and regularization

Empirical risk minimization (ERM) has been tremendously successful in finding
predictors with good performance. In the last section, the model was trained
to minimize the empirical risk $\hat{R}(\beta)$ but evaluated according to an
adversarial criteria. One natural idea to obtain models that are more robust
to adversarial attacks is to instead minimize the empirical adversarial risk,

${\hat{R\mkern 1.0mu}\mkern-1.0mu}{}_{p}^{\text{adv}}({\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{})=\frac{1}{n}\sum_{i=1}^{n}{\max_{\|\Delta
x_{i}\|_{p}\leq\delta}(y_{i}-(x_{i}+\Delta
x_{i})^{\mathsf{T}}{\hat{\beta\mkern 1.0mu}\mkern-1.0mu}{})^{2}}.$ (31)

This method is commonly called adversarial training [8].

In this section, we use Lemma 2 to develop a convex formulation of adversarial
training for linear regression problems. With this tool in hand, we explore
the effect of adversarial training on how the model robustness changes the
number of features. We also compare it to ridge regression,

${\hat{R\mkern 1.0mu}\mkern-1.0mu}{}_{\text{ridge}}({\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{})=\frac{1}{n}\sum_{i=1}^{n}{(y_{i}-x_{i}^{\mathsf{T}}{\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{})^{2}}+\delta\|{\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{}\|_{2}^{2},$ (32)

and lasso,

${\hat{R\mkern 1.0mu}\mkern-1.0mu}{}_{\text{lasso}}({\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{})=\frac{1}{n}\sum_{i=1}^{n}{(y_{i}-x_{i}^{\mathsf{T}}{\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{})^{2}}+\delta\|{\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{}\|_{1}.$ (33)

###  V-A Adversarial training using convex programming

Using Lemma 2 it is easy to show the convexity of the adversarial risk
(defined in Eq. (2)).

######  Proposition 13.

For $p\in[1,\infty]$, $R_{p}^{\text{adv}}({\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{})$ is convex in $\beta$.

###### Proof.

Let $\gamma\in[0,1]$, for $q\in[1,\infty]$, $\|{\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{}\|_{q}$ is a norm and from the triangular inequality, we
have that:

$\|\gamma{\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{}_{1}+(1-\gamma){\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{}_{1}\|_{q},\leq\gamma\|{\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{}_{1}\|_{q}+(1-\gamma)\|{\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{}_{2}\|_{q}$ (34)

Moreover,

$|y_{0}-x_{0}^{\mathsf{T}}(\gamma{\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{}_{1}+(1-\gamma){\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{}_{1})|\leq\gamma|y_{0}-x_{0}^{\mathsf{T}}{\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{}_{1}|+(1-\gamma)|y_{0}-x_{0}^{\mathsf{T}}{\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{}_{2}|.$

Hence, $h({\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{})=|y_{0}-x_{0}^{\mathsf{T}}{\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{}|+\|{\hat{\beta\mkern 1.0mu}\mkern-1.0mu}{}\|_{q}$ is
convex and, also, $h({\hat{\beta\mkern 1.0mu}\mkern-1.0mu}{})\geq 0$ for all
${\hat{\beta\mkern 1.0mu}\mkern-1.0mu}{}$. Now, since $g(x)=x^{2}$ is convex
and non-decresing for $x\geq 0$, the composition $g\circ h$ is convex – See
[42, Section 3.2.4 ]; moreover, the expected value of a convex function is
also convex [42, Section 3.2.1] and it follows that the right-hand side of Eq.
(5) is convex. ∎

The results obtained for the adversarial risk are also valid for the empirical
adversarial risk. Hence, it follows from Lemma 2 that:

$\hat{R}_{p}^{\text{adv}}({\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{})=\frac{1}{n}\sum_{i=1}^{n}\left(|y_{i}-x_{i}^{\mathsf{T}}{\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{}|+\delta\|{\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{}\|_{q}\right)^{2},$ (35)

and that it is convex. The above expression can be entered in a standard
convex modeling language to obtain the adversarial training solution. In the
numerical examples that follows we use CVXPY [43] to train the model.

###  V-B Overparameterized models: Latent space feature model

In this example, we consider artificially generated data from the latent space
feature model described in Section IV. The same experiment for the isotropic
feature model is provided in the Supplementary Material Section E. In Section
IV, we saw the unfortunate effect that if the input variables scale with
$\eta(m)=\sqrt{m}$ (which corresponds to keeping
$\mathbb{E}\left[{\|x\|_{2}}\right]$ constant as we vary the number of
features $m$) we observe that $\|\hat{\beta}\|_{1}$ grows indefinitely with
$m$ when $\hat{\beta}$ was estimated using the minimum-norm solution. We also
showed how this makes the $\ell_{\infty}$ adversarial risk grow indefinitely
with the number of features (i.e., Fig. 1).

Let us now investigate if the same effect can be observed for models trained
with ridge regression, lasso and adversarial training. In Fig. 7 we show the
norm $\|\hat{\beta}\|_{1}$ in these cases. Ridge regression displays the
parameter norm growing with $\mathcal{O}(m)$ regardless of how large the
regularization parameter $\delta$ is. We notice that $\ell_{2}$ adversarial
training has a similar behavior for $\delta$ smaller then a certain threshold,
in these cases it displays curves similar to ridge regression that grow with
$\mathcal{O}(m)$. However, for sufficiently large values of the regularization
parameter, the parameter norm of the solution is zero for all values of $m$.

For lasso, we see that the parameter norm goes to zero for overparameterized
models with sufficiently large $m$. Looking at lasso as a bi-objective
optimization problem helps interpreting this behavior: as the number of
features $m$ increases, the scaling affects the two objectives differently and
the objective of keeping $\|\hat{\beta}\|_{1}$ starts to be prioritized over
the objective of keeping the square training error low the more $m$ is
increased. Interestingly, the $\ell_{\infty}$ adversarial training seems to
behave in a very similar way.

In Fig. 8 we provide the adversarial test error for models trained with ridge
regression, lasso and adversarial training, respectively. As expected by our
analysis of $\|{\hat{\beta\mkern 1.0mu}\mkern-1.0mu}{}\|_{1}$, lasso and
$\ell_{\infty}$ adversarial training yield solutions that do not deteriorate
indefinitely. We believe this observation adds to our discussion about the
role of the scaling. It highlights the fact that, even in the case of a
mismatch between disturbance and how the input scales with the number of
variables (i.e., $\mathbb{E}_{{x}}\left[{\|x\|_{2}^{2}}\right]$ constant while
we evaluate it under an $\ell_{\infty}$ adversary) it is still possible to
avoid brittleness by considering a type of regularization that acts under the
right norm.

(a) Ridge regression

(b) Adversarial training $\ell_{2}$

(c) Lasso regression

(d) Adversarial training $\ell_{\infty}$

Figure 7: Parameter norm $\|\hat{\beta}\|_{1}$. The input variables are scaled
with $\eta(m)=\sqrt{m}$. The error bars give the median and the 0.25 and 0.75
quantiles obtained from numerical experiments (6 realizations) for a fixed
training dataset of size $n=100$. We repeat the experiment for different
amounts of regularization. The regularization parameter $\delta$ defined in
Eq. (31) for the adversarial training and in Eq. (32) and (33) for ridge
regression and lasso. It is indicated in the plot by the different colors.
Figure 8: Adversarial $\ell_{\infty}$ risk. On the $y$-axis we show the
$\ell_{\infty}$ adversarial risk for models obtained by different training
methods. On the $x$-axis we have the ratio between the number of features $m$
and the number of training datapoints $n$. The error bars give the median and
the 0.25 and 0.75 quantiles obtained from numerical experiments (6
realizations). We use $\delta=0.01$ both during inference (to compute the
adversarial risk) and during the adversarial training, as in Eq. (31). We also
use $\delta=0.01$ for lasso and ridge regression, see Eq. (32) and (33).

##  VI Discussion and conclusion

A question that naturally comes to mind is if parts of this analysis can be
generalized to nonlinear settings. Let us define the adversarial risk
associated with a given function $f$ by:

$R^{\text{adv}}_{p}(f)=\mathbb{E}_{{x_{0},y_{0}}}\left[{\max_{\|\Delta
x_{0}\|_{p}\leq\delta}(y_{0}-f(x_{0}+\Delta x_{0}))^{2}}\right].$ (36)

It is possible to obtain an upper bound similar to the one in Eq. (10). Let
$L(f)$ be the Lipschitz constant of $f$, i.e. $|f(x_{1})-f(x_{2})|\leq
L(f)\|x_{1}-x_{2}\|$ for all $x_{1},x_{2}$. An analysis equivalent to the one
used in the proof of Lemma 2 yields

$R^{\text{adv}}_{p}(f)\leq\mathbb{E}_{{x_{0},y_{0}}}\left[{\left(|y_{0}-f(x_{0})|+\delta
L(f)\right)^{2}}\right].$ (37)

In this case, equality does not necessarily hold. Proposition 3 was used in
the proof for the linear case, but there is not an obvious equivalent in the
nonlinear case. Hence, instead of the approximation (8) we would only have
${R^{\text{adv}}_{p}(f)\lessapprox R(f)+\delta^{2}L(f)^{2}}$. Indeed, the idea
of using the Lipschitz constant as a proxy for robustness is quite standard
and a common procedure to obtain robust models is to jointly optimize the risk
$R(f)$ and the Lipschitz constant $L(f)$, see e.g. [44]. However, studying the
linear case still clarifies facts that are not obvious.

Indeed, we show in this paper that different definitions of the metrics used
in the input space might results in completely different assessments of the
robustness. For instance, we provided examples of models that are robust to
$\ell_{2}$ attacks, but can be made completely vulnerable to $\ell_{\infty}$
as we grow the number of features. While one could think of it as an aspect of
the curse of dimensionality, we would like to stress that it does not reveal
the full story, there are more aspects to be considered. The most pathological
results are obtained in a mismatched setup, where we keep
$\mathbb{E}_{{x}}\left[{\|x\|_{2}^{2}}\right]$ but apply an adversarial attack
constrained by the $\ell_{\infty}$ norm: $\|\Delta x\|_{\infty}\leq\delta$. In
this case, we have shown that the adversarial risk can be made arbitrarily
large (i.e., the model is arbitrarily vulnerable to an adversary) as the
number of features grows.

The idea that brittleness to adversarial examples is reproducible in linear
models is highly influential, the mismatched setup resulting in brittleness is
something that usually appears hidden in the argument but is present in many
examples found in the literature. In Section IV-A we show one example inspired
by [13]. We cite [5, Section 3 ] as another example of a highly influential
work where an $\ell_{\infty}$ attack is considered while implicitly assuming
the input $\ell_{2}$-norm is kept constant.

We also provided a convex optimization formulation for adversarial training
and showed that there are similarities for the high-dimensional setup between
$\ell_{\infty}$ adversarial training and lasso, and between $\ell_{2}$
adversarial training and ridge regression. We intend to further explore the
similarities and differences between these methods in future work. We also
intend to further evaluate the effectiveness of adversarial training as a
robust regression method.

## Acknowledgement

The authors would like to thank Dave Zachariah for very fruitful discussions
throughout the work with this research. This research was financially
supported by the project _Deep probabilistic regression – new models and
learning algorithms_ (contract number: 2021-04301), funded by the Swedish
Research Council and by _Kjell och Märta Beijer Foundation_.

## References

  * [1] Mikhail Belkin, Daniel Hsu, Siyuan Ma and Soumik Mandal  “Reconciling Modern Machine-Learning Practice and the Classical Bias–Variance Trade-Off”  In _Proceedings of the National Academy of Sciences_ 116.32, 2019, pp. 15849–15854  DOI: 10.1073/pnas.1903070116
  * [2] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht and Oriol Vinyals  “Understanding Deep Learning Requires Rethinking Generalization”  In _Proceedings of the 5th International Conference on Learning Representations (ICLR)_ , 2017  arXiv:1611.03530
  * [3] Sébastien Bubeck and Mark Sellke  “A Universal Law of Robustness via Isoperimetry”  In _Advances in Neural Information Processing Systems_ , 2021  arXiv:2105.12806
  * [4] Joan Bruna, Christian Szegedy, Ilya Sutskever, Ian Goodfellow, Wojciech Zaremba, Rob Fergus and Dumitru Erhan  “Intriguing Properties of Neural Networks”  In _Proceedings of the 2nd International Conference on Learning Representations (ICLR)_ , 2014
  * [5] Ian J. Goodfellow, Jonathon Shlens and Christian Szegedy  “Explaining and Harnessing Adversarial Examples”  In _Proceedings of the 3rd International Conference on Learning Representations (ICLR)_ , 2015  arXiv:1412.6572
  * [6] Peter L. Bartlett, Philip M. Long, Gábor Lugosi and Alexander Tsigler  “Benign Overfitting in Linear Regression”  In _Proceedings of the National Academy of Sciences_ 117.48, 2020, pp. 30063–30070  DOI: 10.1073/pnas.1907378117
  * [7] Trevor Hastie, Andrea Montanari, Saharon Rosset and Ryan J. Tibshirani  “Surprises in High-Dimensional Ridgeless Least Squares Interpolation”  In _arXiv:1903.08560_ , 2019  arXiv:1903.08560
  * [8] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras and Adrian Vladu  “Towards Deep Learning Models Resistant to Adversarial Attacks”  In _Proceedings of the International Conference for Learning Representations (ICLR)_ , 2018  arXiv:1706.06083
  * [9] Robert Tibshirani  “Regression Shrinkage and Selection via the LASSO”  In _Journal of the Royal Statistical Society. Series B (Methodological)_ , 1996, pp. 267–288
  * [10] Nilesh Dalvi, Pedro Domingos, Mausam, Sumit Sanghai and Deepak Verma  “Adversarial Classification”  In _Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , 2004  DOI: 10.1145/1014052.1014066
  * [11] Amir Globerson and Sam Roweis  “Nightmare at Test Time: Robust Learning by Feature Deletion”  In _Proceedings of the 23rd International Conference on Machine Learning (ICML)_ , 2006, pp. 353–360  DOI: 10.1145/1143844.1143889
  * [12] Battista Biggio and Fabio Roli  “Wild Patterns: Ten Years after the Rise of Adversarial Machine Learning”  In _Pattern Recognition_ 84, 2018, pp. 317–331  DOI: 10.1016/j.patcog.2018.07.023
  * [13] Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner and Aleksander Ma  “Robustness May Be At Odds with Accuracy”  In _Proceedings of the International Conference for Learning Representations (ICLR)_ , 2019, pp. 23
  * [14] Andrew Ilyas, Shibani Santurkar, Dimitris Tsipras, Logan Engstrom, Brandon Tran and Aleksander Madry  “Adversarial Examples Are Not Bugs, They Are Features”  In _Advances in Neural Information Processing Systems_ 32, 2019  arXiv:1905.02175
  * [15] Justin Gilmer, Luke Metz, Fartash Faghri, Samuel S. Schoenholz, Maithra Raghu, Martin Wattenberg and Ian Goodfellow  “Adversarial Spheres”  In _arXiv:1801.02774_ , 2018  arXiv:1801.02774
  * [16] Dong Yin, Ramchandran Kannan and Peter Bartlett  “Rademacher Complexity for Adversarially Robust Generalization”  In _Proceedings of the 36th International Conference on Machine Learning_ PMLR, 2019, pp. 7085–7094
  * [17] Sébastien Bubeck, Yuanzhi Li and Dheeraj Nagaraj  “A Law of Robustness for Two-Layers Neural Networks”  In _134 of Proceedings of Machine Learning Research, Conference on Learning Theory (COLT)_ 134, 2021, pp. 804–820  arXiv:2009.14444
  * [18] Amit Daniely and Hadas Shacham  “Most ReLU Networks Suffer from Ell 2 Adversarial Perturbations”  In _Advances in Neural Information Processing Systems_ 33, 2020, pp. 6629–6636
  * [19] Peter L Bartlett, Sébastien Bubeck and Yeshwanth Cherapanamjeri  “Adversarial Examples in Multi-Layer Random ReLU Networks”  In _Neural Information Processing Systems (NeurIPS)_ , 2021
  * [20] Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak and Ilya Sutskever  “Deep Double Descent: Where Bigger Models and More Data Hurt”  In _Proceedings of the 8th International Conference on Learning Representations (ICLR)_ , 2020  arXiv:1912.02292
  * [21] Mario Geiger, Stefano Spigler, Stéphane d’Ascoli, Levent Sagun, Marco Baity-Jesi, Giulio Biroli and Matthieu Wyart  “Jamming Transition as a Paradigm to Understand the Loss Landscape of Deep Neural Networks”  In _Physical Review E_ 100.1 American Physical Society, 2019, pp. 012115  DOI: 10.1103/PhysRevE.100.012115
  * [22] Mario Geiger, Arthur Jacot, Stefano Spigler, Franck Gabriel, Levent Sagun, Stéphane d’Ascoli, Giulio Biroli, Clément Hongler and Matthieu Wyart  “Scaling Description of Generalization with Number of Parameters in Deep Learning”  In _Journal of Statistical Mechanics: Theory and Experiment_ 2020.2, 2020, pp. 023401  DOI: 10.1088/1742-5468/ab633c
  * [23] Antônio H. Ribeiro, Johannes N. Hendriks, Adrian G. Wills and Thomas B. Schön  “Beyond Occam’s Razor in System Identification: Double-Descent When Modeling Dynamics”  In _Proceedings of the 19th IFAC Symposium on System Identification (SYSID) - IFAC-PapersOnLine_ 54 Elsevier, 2021, pp. 97–102  DOI: 10.1016/j.ifacol.2021.08.341
  * [24] Zeyu Deng, Abla Kammoun and Christos Thrampoulidis  “A Model of Double Descent for High-Dimensional Logistic Regression”  In _ICASSP 2020 - 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2020, pp. 4267–4271  DOI: 10.1109/ICASSP40776.2020.9053524
  * [25] Vidya Muthukumar, Kailas Vodrahalli, Vignesh Subramanian and Anant Sahai  “Harmless Interpolation of Noisy Data in Regression”  In _IEEE Journal on Selected Areas in Information Theory_ 1.1, 2020, pp. 67–83  DOI: 10.1109/JSAIT.2020.2984716
  * [26] Alexander D’Amour et al.  “Underspecification Presents Challenges for Credibility in Modern Machine Learning”  In _arXiv:2011.03395_ , 2020  arXiv:2011.03395
  * [27] Song Mei and Andrea Montanari  “The Generalization Error of Random Features Regression: Precise Asymptotics and the Double Descent Curve”  In _Communications on Pure and Applied Mathematics_ 75.4, 2022, pp. 667–766  DOI: 10.1002/cpa.22008
  * [28] Jeffrey Pennington and Pratik Worah  “Nonlinear Random Matrix Theory for Deep Learning”  In _Advances in Neural Information Processing Systems_ , 2017, pp. 2637–2646
  * [29] Jeffrey Pennington, Samuel S. Schoenholz and Surya Ganguli  “The Emergence of Spectral Universality in Deep Networks”  In _21st International Conference on Artificial Intelligence and Statistics (AISTATS)_ , 2018
  * [30] Leonid Pastur  “On Random Matrices Arising in Deep Neural Networks. Gaussian Case”  In _arXiv:2001.06188_ , 2020  arXiv:2001.06188
  * [31] Mikhail Belkin, Daniel Hsu and Ji Xu  “Two Models of Double Descent for Weak Features”  In _SIAM Journal on Mathematics of Data Science_ 2.4, 2020, pp. 1167–1180  DOI: 10.1137/20M1336072
  * [32] Madhu S. Advani, Andrew M. Saxe and Haim Sompolinsky  “High-Dimensional Dynamics of Generalization Error in Neural Networks”  In _Neural Networks_ 132, 2020, pp. 428–446  DOI: 10.1016/j.neunet.2020.08.022
  * [33] Ben Adlam and Jeffrey Pennington  “The Neural Tangent Kernel in High Dimensions: Triple Descent and a Multi-Scale Theory of Generalization”  In _Proceedings of the 37 th International Conference on Machine Learning, PMLR 119_ , 2020
  * [34] Arjun Nitin Bhagoji, Daniel Cullina and Prateek Mittal  “Lower Bounds on Adversarial Robustness from Optimal Transport”  In _Advances in Neural Information Processing Systems_ 32, 2019
  * [35] Dimitrios Diochnos, Saeed Mahloujifar and Mohammad Mahmoody  “Adversarial Risk and Robustness: General Definitions and Implications for the Uniform Distribution”  In _Advances in Neural Information Processing Systems_ 31, 2018
  * [36] Hossein Taheri, Ramtin Pedarsani and Christos Thrampoulidis  “Asymptotic Behavior of Adversarial Training in Binary Classification”  In _arXiv:2010.13275_ , 2021  arXiv:2010.13275
  * [37] Adel Javanmard, Mahdi Soltanolkotabi and Hamed Hassani  “Precise Tradeoffs in Adversarial Training for Linear Regression”  In _Proceedings of 33rd Conference on Learning Theory_ 125 PMLR, 2020, pp. 2034–2078
  * [38] Adel Javanmard and Mahdi Soltanolkotabi  “Precise Statistical Analysis of Classification Accuracies for Adversarial Training”  In _arXiv:2010.11213_ , 2020  arXiv:2010.11213
  * [39] Hamed Hassani and Adel Javanmard  “The Curse of Overparametrization in Adversarial Training: Precise Analysis of Robust Generalization for Random Features Regression”  In _arXiv:2201.05149_ , 2022  arXiv:2201.05149
  * [40] Yifei Min, Lin Chen and Amin Karbasi  “The Curious Case of Adversarially Robust Models: More Data Can Help, Double Descend, or Hurt Generalization”  In _roceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence_ 161, 2021, pp. 129–139
  * [41] Roman Vershynin  “High-Dimensional Probability”, Cambridge Series in Statistical and Probabilistic Mathematics  Cambridge University Press, 2018
  * [42] Stephen P. Boyd and Lieven Vandenberghe  “Convex Optimization”  Cambridge University Press, 2004
  * [43] Steven Diamond and Stephen Boyd  “CVXPY: A Python-embedded Modeling Language for Convex Optimization”  In _Journal of Machine Learning Research_ 17.83, 2016, pp. 1–5
  * [44] Mahyar Fazlyab, Alexander Robey, Hamed Hassani, Manfred Morari and George J. Pappas  “Efficient and Accurate Estimation of Lipschitz Constants for Deep Neural Networks”  In _Advances in Neural Information Processing Systems (NeurIPS)_ , 2019  arXiv:1906.04893

Supplementary Material
Overparameterized Linear Regression
under Adversarial Attacks

##  Appendix A Proofs

###  A-A Inequalities (10) and (16)

The two inequalities (10) and (16) follow from (7). The first can be derived
by a direct application of Jensen’s inequality that yields
$0\leq\mathbb{E}_{{x_{0},y_{0}}}\left[{|e_{0}|}\right]\leq\sqrt{R({\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{})}$. The second inequality follows from a direct
application of the Cauchy-Schwartz inequality:
$0\leq\mathbb{E}_{{y,x_{0},y_{0}}}\left[{\|{\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{}\|_{q}|e_{0}|}\right]\leq\sqrt{L_{q}R}$.

###  A-B Proof of Lemma 4

The following decomposition is implicitly used through the paper. In Eq. (14)
below, the risk is decomposed into: a term that can be understood as the model
bias, another term that corresponds to the model variance, and the unavoidable
risk $\sigma^{2}$.

###### Proof.

Proof for $\|{\hat{\beta\mkern 1.0mu}\mkern-1.0mu}{}\|_{2}$: From Eq. (11) and
Eq. (12) it follows that:

$\hat{\beta}=\underbrace{(X^{\mathsf{T}}X)^{\dagger}X^{\mathsf{T}}X}_{\Phi}\beta+\underbrace{(X^{\mathsf{T}}X)^{\dagger}}_{\frac{1}{n}\hat{\Sigma}^{\dagger}}X^{\mathsf{T}}\epsilon.$
(S.1)

Hence, since $\hat{\Sigma}$ is symmetric:

$\hat{\beta}^{\mathsf{T}}\hat{\beta}=\beta^{\mathsf{T}}\Phi^{\mathsf{T}}\Phi\beta+\frac{1}{n}\beta^{\mathsf{T}}\Phi^{\mathsf{T}}\hat{\Sigma}^{\dagger}X^{\mathsf{T}}\epsilon+\frac{1}{n^{2}}\epsilon^{\mathsf{T}}X\hat{\Sigma}^{\dagger}\hat{\Sigma}^{\dagger}X^{\mathsf{T}}\epsilon,$
(S.2)

where the first term is equal to $\beta^{\mathsf{T}}\Phi\beta$ since, $\Phi$
is an orthogonal projector i.e., $\Phi^{\mathsf{T}}=\Phi$ and $\Phi\Phi=\Phi$.
Moreover, the middle term has zero expectation.

Now, since the second term is a scalar, it is equal to its trace. Using the
fact that the trace is invariant over cyclic permutations,

$\epsilon^{\mathsf{T}}X\hat{\Sigma}^{\dagger}\hat{\Sigma}^{\dagger}X^{\mathsf{T}}\epsilon=\text{tr}\left\\{\hat{\Sigma}^{\dagger}X^{\mathsf{T}}\epsilon\epsilon^{\mathsf{T}}X\hat{\Sigma}^{\dagger}\right\\}.$
(S.3)

From the assumption that the noise samples are independent and have variance
$\sigma^{2}$, we have
$\mathbb{E}_{{\epsilon}}\left[{\epsilon\epsilon^{\mathsf{T}}}\right]=\sigma^{2}I$,
where $I$ is the identity matrix. Since we can swap the trace and the
expectation operator we obtain

$\mathbb{E}_{{\epsilon}}\left[{\hat{\beta}^{\mathsf{T}}\hat{\beta}}\right]=\beta^{\mathsf{T}}\Phi\beta+\frac{1}{n^{2}}\text{tr}\left\\{\hat{\Sigma}^{\dagger}X^{\mathsf{T}}\underbrace{\mathbb{E}_{{\epsilon}}\left[{{\epsilon\epsilon^{\mathsf{T}}}}\right]}_{\sigma^{2}I}X\hat{\Sigma}^{\dagger}\right\\}.$

The results follow from the definition of $\hat{\Sigma}^{\dagger}$ and the
following property of pseudo-inverse
$\hat{\Sigma}^{\dagger}\hat{\Sigma}\hat{\Sigma}^{\dagger}=\hat{\Sigma}^{\dagger}$.

Proof for $R$: Now,

$R({\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{})=\mathbb{E}_{{x_{0},y_{0}}}\left[{(\beta^{\mathsf{T}}x_{0}-y_{0})^{2}}\right]=(\beta-{\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{})^{\mathsf{T}}\Sigma(\beta-{\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{})+\sigma^{2}.$ (S.4)

From (S.1) it follows that:

$\beta-\hat{\beta}=\underbrace{(I-\Phi)}_{\Pi}\beta+\frac{1}{n}\hat{\Sigma}^{\dagger}X^{\mathsf{T}}\epsilon,$

where $\Pi$ is again an orthogonal projector, i.e., $\Pi^{\mathsf{T}}=\Pi$ and
$\Pi\,\Pi=\Pi$. We can then compute a closed-form expression for
$\mathbb{E}_{{\epsilon}}\left[{R({\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{})}\right]$ using the same procedure.

∎

###  A-C Proof of Lemma 7

From the lemma statement: $x_{i}$ are independently sampled sub-Gaussian
vectors. Let $X$ be a matrix containing the vectors $x_{i}$ as its rows, i.e.,

$X=\begin{bmatrix}\makebox[20.00003pt]{$\smash{-}\mkern-7.0mu\cleaders\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}\hfill\mkern-7.0mu\smash{-}$}\kern-5.0pt&x_{1}&\kern-5.0pt\makebox[20.00003pt]{$\smash{-}\mkern-7.0mu\cleaders\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}\hfill\mkern-7.0mu\smash{-}$}\\\
&\vdots&\\\
\makebox[20.00003pt]{$\smash{-}\mkern-7.0mu\cleaders\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}\hfill\mkern-7.0mu\smash{-}$}\kern-5.0pt&x_{n}&\kern-5.0pt\makebox[20.00003pt]{$\smash{-}\mkern-7.0mu\cleaders\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}\hfill\mkern-7.0mu\smash{-}$}\\\
\end{bmatrix}.$

Let $s_{i}(X)$ denote the $i$-th sigular value of $X$. From [41, Theorem 4.6.1
] we have that there exist a constant $C$ such that with probability larger
then $1-2\exp(-t^{2})$,

$\sqrt{n}-C\left(\sqrt{m}+t\right)\leq
s_{i}(X)\leq\sqrt{n}+C\left(\sqrt{m}+t\right),\qquad\forall i=1,\dots,n$ (S.5)

Set $t=\sqrt{m}$ then, since
$\lambda_{i}(\hat{\Sigma})=\left(\frac{1}{\sqrt{n}}s_{(n-i)}(X)\right)^{-2}$
we obtain with probability greater than $1-2\exp(-m)$ that

$\frac{1}{(1+C\left(\sqrt{\frac{m}{n}}\right))^{2}}\leq\lambda_{i}(\hat{\Sigma})\leq\frac{1}{(1-C\left(\sqrt{\frac{m}{n}}\right))^{2}},\qquad\forall
i=1,\dots,n.$ (S.6)

Finally, since $m>n$, we have that $1-2\exp(-m)>1-2\exp(-n)$ and the result
follows.

###  A-D Proof of Lemma 9

From Eq. (13) and the triangular inequality:

$\left|\|\hat{\beta}\|_{2}-\|\Phi\beta\|_{2}\right|\leq\frac{1}{\sqrt{n}}\left\|\frac{1}{\sqrt{n}}\hat{\Sigma}^{\dagger}X^{\mathsf{T}}\epsilon\right\|_{2}$
(S.7)

In turn, we have that

$\left\|\frac{1}{n}\hat{\Sigma}^{\dagger}X^{\mathsf{T}}\epsilon\right\|_{2}\leq\left\|\frac{1}{\sqrt{n}}\hat{\Sigma}^{\dagger}X^{\mathsf{T}}\right\|_{2}\|\epsilon\|_{2}.$

Note that for a matrix $A\in\mathbb{R}^{m\times n}$ we use $\|A\|_{2}$ to
denote the operator norm. We have
$\|A\|_{2}=\max_{i}\sqrt{\lambda_{i}(A^{\mathsf{T}}A)}$. Hence:

$\left\|\frac{1}{n}\hat{\Sigma}^{\dagger}X^{\mathsf{T}}\right\|_{2}=\max_{i}\sqrt{\lambda_{i}(\hat{\Sigma}^{\dagger}\hat{\Sigma}\hat{\Sigma}^{\dagger})}=\sqrt{\|\hat{\Sigma}^{\dagger}\|_{2}},$

where the second equality follows by making direct use of the property
$\hat{\Sigma}^{\dagger}\hat{\Sigma}\hat{\Sigma}^{\dagger}=\hat{\Sigma}^{\dagger}$
and by using the fact that $\hat{\Sigma}^{\dagger}$ is positive semidefinite.

###  A-E (Partial) Proof of Proposition 12

Here $x\in\mathbb{R}^{m}$. To compute the expected $\ell_{2}$-norm of $x_{i}$
we use the fact that $\text{Cov}\left[x\right]=I_{m}$,

$\mathbb{E}_{{x}}\left[{\|x\|_{2}^{2}}\right]=\mathbb{E}_{{x}}\left[{\text{tr}\\{xx^{\mathsf{T}}\\}}\right]=\text{tr}\\{\mathbb{E}_{{x}}\left[{xx^{\mathsf{T}}}\right]\\}=\text{tr}\\{I_{m}\\}=m.$
(S.8)

Let us proceed by analyzing the $\ell_{\infty}$-norm. Let $t>0$ be an
arbitrary value to be chosen later. Via direct use of Jensen’s inequality we
obtain

$\exp(t\mathbb{E}_{{x}}\left[{\|x\|_{\infty}}\right])\leq\mathbb{E}\left[{\exp(t\|x\|_{\infty})}\right]=\mathbb{E}\left[{\max_{j}\exp(t|x^{j}|)}\right]\leq\sum_{j=1}^{m}\left(\mathbb{E}\left[{\exp(t|x^{j}|)}\right]\right).$
(S.9)

Using the fact that $x^{j}$ is sub-Gaussian (without loss of generality, we
assume unitary proxy variance), we have
$\mathbb{E}\left[{\exp(t|x^{j}|)}\right]\leq\exp(t^{2}/2)$. Therefore,

$\exp(t\mathbb{E}\left[{\|x\|_{\infty}}\right])\leq 2m\exp(t^{2}/2).$ (S.10)

Therefore,

$\mathbb{E}\left[{\|x\|_{\infty}}\right]\leq\frac{\log(2m)}{t}+\frac{t}{2}.$
(S.11)

Here, we can choose $t=2\sqrt{\log(2m)}$, which yields

$\mathbb{E}\left[{\|x\|_{\infty}}\right]\leq\sqrt{2\log(2m)}.$ (S.12)

We conclude that
$\mathbb{E}\left[{\|x\|_{\infty}}\right]=\mathcal{O}(\sqrt{\log(m)})$. It is
also possible to obtain
$\mathbb{E}\left[{\|x\|_{\infty}}\right]=\Omega(\sqrt{\log(m)})$ using a
similar argument to the one described in “Bounds on the Expectation of the
Maximum of Samples from a Gaussian” by Gautam Kamath
(www.gautamkamath.com/writings/gaussian_max.pdf [online accessed:
2021-10-11]). Hence,
$\mathbb{E}\left[{\|x\|_{\infty}}\right]=\Theta(\sqrt{\log(m)})$. The result
for is also provided in [41, Exercises 2.5.10 and 2.5.11 ].

##  Appendix B Isotropic feature model

The asymptotic behavior of $R$ and $L_{2}$ for isotropic features is described
in Lemma 5. In Figure S.1(a), we illustrate the behavior of the risk for
different values of $r^{2}$. Again, as in the main text, we refer to the “null
risk” as the quantity $r^{2}+\sigma^{2}$ that correspond to the risk of the
null estimator $\tilde{\beta}=0$. In the underparameterized region, the
prediction risk is smaller then the null risk iff
$\frac{m}{n}<\frac{r^{2}}{\sigma^{2}+r^{2}}$. In the overparameterized region,
when $r^{2}>\sigma^{2}$, as in the situation studied in the main text, the
prediction risk has a local minima at $\gamma=\frac{r}{r+\sigma}$.
Furthermore, it approaches the null risk from below as
$\gamma\rightarrow\infty$. If $r^{2}<\sigma^{2}$, the prediction risk
decreases monotonically, approaching the null risk from above as
$\gamma\rightarrow\infty$. As mentioned in the main text, the prediction risk
does not change as the inputs are rescaled. However, the parameter norm does
change. The parameter norm is shown for different scaling in Figure S.1(b). We
discuss the behavior for each case in the main text. We also illustrate the
effect of different input scalings on the adversarial risk in Figures 2.

(a) Prediction risk (b) $\ell_{2}$ parameter norm

Figure S.1: Isotropic features. In (a), we show the prediction risk for
$r^{2}\in\\{0.5,1,2,4\\}$. In (b), we show the the parameter norm for
$r^{2}=2$ and for different choices of scaling of the input. The remaining
parameters are the same as in Figure 2.

(a) $r^{2}=0.5$, $\eta(m)=1$ (b) $r^{2}=1$, $\eta(m)=1$ (c) $r^{2}=2$,
$\eta(m)=1$

(d) $r^{2}=0.5$, $\eta(m)=\sqrt{\log{m}}$ (e) $r^{2}=1$,
$\eta(m)=\sqrt{\log{m}}$ (f) $r^{2}=2$, $\eta(m)=\sqrt{\log{m}}$

(g) $r^{2}=0.5$, $\eta(m)=\sqrt{m}$ (h) $r^{2}=1$, $\eta(m)=\sqrt{m}$ (i)
$r^{2}=2$, $\eta(m)=\sqrt{m}$

Figure S.2: Adversarial $\ell_{2}$ risk, isotropic features. The setup is the
same as in Figure 2 but for a different scaling and different values of the
parameter norm $r^{2}$.

##  Appendix C Equicorrelated features model

Here, we consider the case where the features are $\rho$-equicorrelated. That
is, $\Sigma$ is such that its $(i,j)$-th entry is:

$\Sigma_{i,j}=\begin{cases}1&i=j,\\\ \rho&i\not=j,\end{cases}$ (S.13)

and $x=\Sigma^{1/2}z$ for $z$ composed of i.i.d. features with zero mean,
unitary variance, and bounded moments of order greater than 4 that is finite.
In this case, the following result holds:

######  Lemma 14.

Assume that $x_{i}$ is generated as described above. Also, assume that
$\beta\sim\mathcal{N}\left(0,\frac{r^{2}}{m}I\right)$. Then, as
$p,n\rightarrow\infty$ $p/n\rightarrow\gamma$, it holds almost surely that:

$\displaystyle\mathbb{E}_{{\beta}}\left[{R}\right]$ $\displaystyle\rightarrow$
$\displaystyle\begin{cases}\sigma^{2}\frac{\gamma}{1-\gamma},\gamma<1,\\\
r^{2}(1-\rho)(1-\frac{1}{\gamma})+\sigma^{2}\frac{1}{\gamma-1},\gamma>1.\end{cases}$
(S.14) $\displaystyle\mathbb{E}_{{\beta}}\left[{L_{2}}\right]$
$\displaystyle\rightarrow$
$\displaystyle\begin{cases}r^{2}+\sigma^{2}\frac{\gamma}{(1-\gamma)(1-\rho)},\gamma<1,\\\
r^{2}\frac{1}{\gamma}+\sigma^{2}\frac{1}{(\gamma-1)(1-\rho)},\gamma>1.\end{cases}$
(S.15)

The asymptotics for $R$ are presented in Corollary 7 from [7]. The proof for
the asymptotics of $L_{2}$ follows from Corollary 2 of the same paper and
relies on the nice properties of the equicorrelated matrix. The next
proposition gives the eigenvalues and eigenvectors of such a matrix. We use
$\vec{\mathbf{1}}$ to denote a vector of dimension $m$ with all its entries
equal to 1. Furthermore, $s_{i}$, $i=1,\dots,n$ denotes the eigenvalues of
$\Sigma$ and $v_{i}$ the corresponding eigenvectors.

######  Proposition 15.

Let $\Sigma\in\mathbb{R}^{m\times m}$ be an equicorrelated matrix with its
entries defined as in Eq. (S.13). Then $s_{1}=1+(m-1)\rho$ and
$s_{i}=(1-\rho)$ for every $i\not=1$. Moreover,
$v_{1}=\frac{1}{\sqrt{m}}\vec{\mathbf{1}}$ and $v_{i}$ for $i\not=1$ is such
that the sum of its entries is equal to zero, that is,
$v_{i}^{\mathsf{T}}\vec{\mathbf{1}}=0$.

Following [7], let us define:

$\widehat{H}_{n}(s)=\frac{1}{m}\sum_{i=1}^{m}I{\left\\{s\geq s_{i}\right\\}},$
(S.16)

where $I$ is the indicator function, and is equal to one when $s\geq s_{i}$
and equal to $0$ otherwise. For the equicorrelated matrix, we have that:

$\widehat{H}_{n}(s)=\frac{m-1}{m}I\left\\{s\geq\left(1-\rho\right)\right\\}+\frac{1}{m}I\left\\{s\geq\left(1+(m-1)\rho\right)\right\\}.$

Hence, $\widehat{H}_{n}(s)\rightarrow H(s)=I\left\\{s\geq 1-\rho\right\\}$ at
all continuity points. Hence, $dH=\delta_{1-\rho}$ and we have $\
c_{0}=\frac{1}{\gamma(\gamma-1)(1-\rho)}$ which when replaced in Corollary 2
establishes the result.333There is a small typo in Corollary 2 from [7]. The
term $r^{2}$ should have appeared multiplying the integral for the
overparameterized case.

We illustrate in Figure S.3 empirical experiments and asymptotic results for
equicorrelated feature models under $\ell_{2}$ adversarial attacks. In Figure
S.4 we illustrate it for $\ell_{p}$ attacks when $p\in\\{1.5,2,20\\}$ and in
Figure S.5, for $p=\infty$.

(a) $\eta(m)=1$ (b) $\eta(m)=\sqrt{\log{m}}$ (c) $\eta(m)=\sqrt{m}$

Figure S.3: Adversarial $\ell_{2}$ risk, equicorrelated features. The solid
line show the upper and lower bounds on the asymptotic risk obtained from
Lemma 14. The results are for equicorrelated features with $r^{2}=4$,
$\sigma^{2}=1$, $\rho=0.5$. The error bars give the median and the 0.25 and
0.75 quantiles obtained from numerical experiments (10 realizations) with a
fixed training dataset of size $n=300$. We show the results for different
scaling choices.

(a) $\eta(m)=1$ (b) $\eta(m)=\sqrt{\log{m}}$ (c) $\eta(m)=\sqrt{m}$

Figure S.4: Adversarial $\ell_{p}$ risk, equicorrelated features. The setup is
the same as in Figure S.3, but for $\ell_{p}$ adversarial attacks,
$p\in\\{1,2,\infty\\}$ and $\delta=2$. We show the results for different
scaling choices.

(a) $\ell_{\infty}$ Adversarial Risk (b) $\|{\hat{\beta\mkern
1.0mu}\mkern-1.0mu}{}\|_{1}$

Figure S.5: Adversarial $\ell_{\infty}$ risk and $\ell_{1}$ parameter norm,
equicorrelated features. The asymptotic upper bound is indicated by the full
trace. The error bars give the median and the 0.25 and 0.75 quantiles obtained
from numerical experiments (10 realizations). The analysis is performed for a
fixed training dataset of size $n=100$ and for adversarial disturbances of
magnitude $\delta=0.1$. The results are for $r^{2}=1$, $\sigma^{2}=1$,
$\rho=0.5$. We show the results for two different scalings: $\eta(m)=\sqrt{m}$
and $\eta(m)=\sqrt{\log(m)}$.

##  Appendix D Latent space model

Here we show that the latent model described in Equations (29) and (30) is
actually equivalent to a special case of the linear model described in Eq.
(11) for the case where the covariates and the noise are both normal, i.e.
$x_{i}\sim\mathcal{N}(0,\Sigma)$ and $\epsilon_{i}\sim\mathcal{N}(0,\sigma)$.
In both formulations, the pair $(x_{i},y_{i})\in\mathbb{R}^{m+1}$ is jointly a
multivariate Gaussian with zero mean. By matching the covariances, we obtain
the formulations are equivalent for

$\displaystyle\beta$ $\displaystyle=$ $\displaystyle
W(I_{d}+W^{\mathsf{T}}W)^{-1}\theta,$ $\displaystyle\Sigma$ $\displaystyle=$
$\displaystyle I_{p}+WW^{\mathsf{T}},$ (S.17) $\displaystyle\sigma^{2}$
$\displaystyle=$
$\displaystyle\sigma^{2}_{\xi}+\theta^{\mathsf{T}}(I_{d}+W^{\mathsf{T}}W)^{-1}\theta.$

That is, from Eq. (11) the covariance matrix of the joint Gaussian vector
$(x_{i},y_{i})\in\mathbb{R}^{m+1}$ is:

$\begin{bmatrix}\mathbb{E}\left[{x_{i}x_{i}^{\mathsf{T}}}\right]&\mathbb{E}\left[{y_{i}x_{i}}\right]\\\
\mathbb{E}\left[{y_{i}x_{i}^{\mathsf{T}}}\right]&\mathbb{E}\left[{y_{i}y_{i}}\right]\end{bmatrix}=\begin{bmatrix}\Sigma&\beta^{\mathsf{T}}\Sigma\\\
\Sigma\beta&\beta^{\mathsf{T}}\Sigma\beta+\sigma^{2}\end{bmatrix}.$ (S.18)

On the other hand, the latent model (29) and (30) implies the following
covariance matrix for this same vector

$\begin{bmatrix}\mathbb{E}\left[{Wz_{i}z_{i}^{\mathsf{T}}W^{\mathsf{T}}+u_{i}u_{i}^{\mathsf{T}}}\right]&\mathbb{E}\left[{\theta^{\mathsf{T}}z_{i}z_{i}^{\mathsf{T}}W+\xi_{i}u_{i}}\right]\\\
\mathbb{E}\left[{\theta^{\mathsf{T}}z_{i}z_{i}^{\mathsf{T}}W+\xi_{i}u_{i}^{\mathsf{T}}}\right]&\mathbb{E}\left[{\theta^{\mathsf{T}}z_{i}z_{i}^{\mathsf{T}}\theta+\xi_{i}\xi_{i}}\right]\end{bmatrix}=\begin{bmatrix}WW^{\mathsf{T}}+I_{d}&\theta^{\mathsf{T}}W^{\mathsf{T}}\\\
W\theta&\theta^{\mathsf{T}}\theta+\sigma_{\xi}^{2}\end{bmatrix}.$ (S.19)

Using the matrix inversion lemma
$(I_{d}+W^{\mathsf{T}}W)^{-1}=I_{d}+W^{\mathsf{T}}(I-WW^{\mathsf{T}})^{-1}W$
and the identity
$(I_{d}+W^{\mathsf{T}}W)^{-1}W^{\mathsf{T}}=W(I_{d}+WW^{\mathsf{T}})^{-1}$ it
is easy to check that (S.17) renders the two covariance matrices to be equal
and the two data generation procedures equivalent.

Now, the hypothesis that $W^{T}W=\nicefrac{{m}}{{d}}I_{d}$ makes the
calculation of the asymptotics easy. First notice that:
$\|\beta\|^{2}_{2}=\beta^{\mathsf{T}}\beta=\theta^{\mathsf{T}}(I_{d}+W^{\mathsf{T}}W)^{-1}W^{T}W(I_{d}+W^{\mathsf{T}}W)^{-1}\theta$
using the fact that $W^{T}W=\nicefrac{{m}}{{d}}I_{d}$ we obtain:
$\|\beta\|^{2}_{2}=\frac{\nicefrac{{m}}{{d}}}{(1+\nicefrac{{m}}{{d}})^{2}}\|\theta\|_{2}^{2}$.

Moreover, it is quite straight forward to compute the eigenvalues and
eigenvectors of $\Sigma=WW^{\mathsf{T}}+I_{p}$. From the hypothesis, it
follows that $\Sigma W=(1+\nicefrac{{m}}{{d}})W$. Hence, the first $d$
eigenvectors $v_{i}$ are the columns of $\sqrt{\nicefrac{{d}}{{m}}}W$ and the
first $d$ eigenvalues are equal to $s_{i}=(1+\nicefrac{{m}}{{d}})$. Now the
remaining eigenvectors are vectors orthogonal to the columns of $W$ such that
$W^{\mathsf{T}}v_{i}=0$ for $i>d$. The corresponding eigenvalues would be
$s_{i}=1$.

Following [7], let us define:

$\widehat{H}(s)=\frac{1}{m}\sum_{i=1}^{m}I{\left\\{s\geq
s_{i}\right\\}},~{}~{}\widehat{G}(s)=\frac{1}{\|\beta\|_{2}^{2}}\sum_{i=1}^{m}(\beta^{\mathsf{T}}v_{i})^{2}I{\left\\{s\geq
s_{i}\right\\}},$ (S.20)

Hence:

$\widehat{H}(s)=\frac{d}{m}I\left\\{s\geq(1+m/d)\right\\}+\left(1-\frac{d}{m}\right)I\left\\{s\geq
1\right\\}.$ (S.21)

Moreover, $v_{i}^{\mathsf{T}}\beta=0$ if $i>d$, i.e., $\beta$ is orthogonal to
the last $m-d$ eigenvectors. Hence, simple manipulation yields that:

$\widehat{G}(s)=\frac{\nicefrac{{d}}{{m}}\|W^{\mathsf{T}}\beta\|_{2}^{2}}{\|\beta\|_{2}^{2}}I\left\\{s\geq(1+m/d)\right\\}=I\left\\{s\geq(1+m/d)\right\\}.$
(S.22)

Let us define $\psi=\frac{d}{m}$.

######  Proposition 16.

Let $c_{0}=c_{0}(\psi,\gamma)$ be the unique non-negative solution of the
following second-order equation:

$1-\frac{1}{\gamma}=\frac{1-\psi}{1+c_{0}\gamma}+\frac{\psi}{1+c_{0}\left(1+\psi^{-1}\right)\gamma}.$
(S.23)

And define:444We define $\mathscr{B}(\psi,\gamma)$ and
$\mathscr{V}(\psi,\gamma)$ slightly different from [7]. The reason is to make
explicit the role of $r^{2}$ and $\sigma^{2}$. The formulas are equivalent.

$\displaystyle\mathscr{B}(\psi,\gamma)$ $\displaystyle=\left\\{1+\gamma
c_{0}\frac{\mathscr{E}_{1}(\psi,\gamma)}{\mathscr{E}_{2}(\psi,\gamma)}\right\\}\cdot\frac{\left(1+\psi^{-1}\right)}{\left(1+c_{0}\gamma\left(1+\psi^{-1}\right)\right)^{2}},$
(S.24) $\displaystyle\mathscr{V}(\psi,\gamma)$ $\displaystyle=\gamma
c_{0}\frac{\mathscr{E}_{1}(\psi,\gamma)}{\mathscr{E}_{2}(\psi,\gamma)},$
$\displaystyle\mathscr{E}_{1}(\psi,\gamma)$
$\displaystyle=\frac{1-\psi}{\left(1+c_{0}\gamma\right)^{2}}+\frac{\psi\left(1+\psi^{-1}\right)^{2}}{\left(1+c_{0}\gamma\right)^{2}},$
$\displaystyle\mathscr{E}_{2}(\psi,\gamma)$
$\displaystyle=\frac{1-\psi}{\left(1+c_{0}\gamma\right)^{2}}+\frac{1+\psi}{\left(1+c_{0}\left(1+\psi^{-1}\right)\gamma\right)^{2}},$

then:

$\displaystyle R$ $\displaystyle\rightarrow$
$\displaystyle\begin{cases}\sigma^{2}\frac{\gamma}{1-\gamma},\gamma<1,\\\
r^{2}\mathscr{B}(\psi,\gamma)+\sigma^{2}\mathscr{V}(\psi,\gamma),\gamma>1.\end{cases}$
(S.25) $\displaystyle L_{2}$ $\displaystyle\rightarrow$
$\displaystyle\begin{cases}r^{2}+\sigma^{2}\frac{\gamma}{(1-\gamma)(1+\psi)},\gamma<1,\\\
r^{2}\frac{c_{0}\gamma(1+\psi^{-1})}{1+c_{0}\gamma(1+\psi^{-1})}+\sigma^{2}c_{0}\gamma,\gamma>1.\end{cases}$
(S.26)

The proposition is (partially) provided by [7, Corollary 4 ] and extended here
to also state the asymptotic for $L_{2}$ and for $R$ in the underparameterized
region, both results actually follow from the developments in [7]. In the
overparameterized region, the proof follows from replacing $\widehat{G}$ and
$\widehat{H}$ from Eq. (S.21) and Eq. (S.22) in Definition 1 from [7] and from
further simplifying the expressions. It then follows from the (more general)
Theorem 2 in [7] that $R\rightarrow
r^{2}\mathscr{B}(\psi,\gamma)+\sigma^{2}\mathscr{V}(\psi,\gamma)$. In the
underparameterized region, the result can be obtained using Theorem 1 in [7].
The convergence of the $L_{2}$ follows from similar analysis using Corollary 3
in [7].

(a) $\ell_{2}$ adversarial attacks (b) $\ell_{\infty}$ adversarial attacks

Figure S.6: Adversarial $\ell_{p}$ risk, latent space model. The setup is the
same as in Figure 6, but we plot the asymptotics obtained from the above
proposition. In (a), we show the upper and lower bounds; in (b), we show only
the upper bound. The argument why the upper bound is followed closely for
$\ell_{\infty}$ adversarial attacks is provided in the main text.

(a) $p=2,\eta(m)=\sqrt{m}$ (b) $p=2,\eta(m)=\sqrt{\log(m)}$

(c) $p=\infty,\eta(m)=\sqrt{m}$ (d) $p=\infty,\eta(m)=\sqrt{\log(m)}$

Figure S.7: Adversarial risk, latent space model, different values of
$\sigma_{\xi}$. The setup is the same as in Figure S.6 but for different
values of noise $\sigma_{\xi}$.

(a) $p=2,\eta(m)=\sqrt{m}$ (b) $p=2,\eta(m)=\sqrt{\log(m)}$

(c) $p=\infty,\eta(m)=\sqrt{m}$ (d) $p=\infty,\eta(m)=\sqrt{\log(m)}$

Figure S.8: Adversarial risk, latent space model, different $\delta$. The
setup is the same as in Figure S.6 but for different values of$\delta$. Here
$\delta=0$ correspond to no adversarial attack.

##  Appendix E Comparison between regularization methods in isotropic features
model

(a) Ridge regression (b) Adversarial training $\ell_{2}$

(c) Lasso regression (d) Adversarial training $\ell_{\infty}$

Figure S.9: Parameter norm $\|\hat{\beta}\|_{1}$. The input variables are
scaled with $\eta(m)=\sqrt{m}$. The error bars give the median and the 0.25
and 0.75 quantiles obtained from the numerical experiment (4 realizations) for
a fixed training dataset of size $n=100$. The values of $\delta$ for each
experiment are indicated in the plot. We repeat the experiment for different
amounts of regularization. The regularization parameter $\delta$ defined in
Eq. (31) for the adversarial training and in Eq. (32) and (33) for ridge
regression and lasso. It is indicated in the plot by the different colors.

(a) $\ell_{\infty}$ adversarial risk (b) Standard risk

Figure S.10: Adversarial $\ell_{\infty}$ risk. On the $y$-axis we show the
risk for models obtained by different training methods. In (a), it is the
$\ell_{\infty}$ adversarial risk; and, in (b) the standard risk. On the
$x$-axis we have the ratio between the number of features $m$ and the number
of training datapoints $n$. The error bars give the median and the 0.25 and
0.75 quantiles obtained from numerical experiment (4 realizations). We use
$\delta=0.01$ during both inference (to compute the adversarial risk) and
adversarial training, as in Eq. (31). We also use $\delta=0.01$ for lasso and
ridge regression, see Eq. (32) and (33).