Precise Tradeoffs in Adversarial Training for Linear Regression

Introduction

Recent advances in machine learning and deep learning in particular, have led to trained models with breakthrough performance in a variety of applications spanning visual object classification to speech recognition and natural language processing. Despite wide empirical success, these modern learning models are known to be highly vulnerable to small adversarial perturbations to their inputs [BCM+13, SZS+14]. For instance, in the context of image classification even small perturbations of the image, which are imperceptible to a human, can lead to incorrect classification by these models. As these modern inferential techniques begin to be deployed in applications such as autonomous or recognition systems in which safety, reliability, and security are crucial, it is increasingly important to ensure trained models are robust against abrupt or adversarial perturbations to the input.

To mitigate the effect of adversarial perturbations, a wide variety of adversarial training methods have been developed [GSS15, KGB16, MMS+18, RSL18, WK18] which often involve augmenting the training loss so as to become more robust to input perturbations. While adversarial training methods have been rather successful at improving the accuracy of the trained model on adversarially perturbed inputs (robust accuracy), often this benefit comes at the cost of decreasing accuracy on natural unperturbed inputs (standard accuracy) [MMS+18]. Therefore, it is crucial to understand the tradeoff between robust and standard accuracy with adversarial training. Complicating matters further, recent empirical evidence suggest that a variety of other factors affect this tradeoff in somewhat surprising ways. For instance, experiments in [TSE+18] demonstrate that while adversarial training typically has a negative effect on standard accuracy, it outperforms non-adverserial training methods when there are only a few training samples. Perhaps surprisingly, the recent paper by [RXY+19] suggests that in some cases the tradeoff between standard and robust accuracy can be mitigated with additional unlabeled data. Towards demystifying these empirical phenomena, in this paper we aim to precisely characterize the role of adversarial training by focusing on the following key questions:

What is the fundamental tradeoff between robust and standard accuracies in both finite and infinite data limits? How can we algorithmically achieve this tradeoff and what is the role of adversarial training? What is the effect of the size/quality of the data on this tradeoff? How does the model size (e.g. overparametrization) change this tradeoff?

A few recent papers have begun to answer some of these questions in specific settings [TSE+18, ZYJ+19, RXY+19]. See Section 4 for a detailed discussion. Despite this interesting recent progress, a comprehensive understanding of the role of adversarial training and how it precisely affects the aforementioned tradeoffs remains largely mysterious. In this paper we aim to provide a precise characterization of the role of adversarial training by focusing on the simple yet foundational problem of linear regression.

Contributions. We formally introduce the linear regression problem with adversarially perturbed inputs in Section 2 and address the questions above in this setting.

We characterize the fundamental tradeoff between standard riskSince we focus on a regression problem henceforth we focus on risk in lieu of accuracy. (${\sf SR}$) and adversarial risk (${\sf AR}$) achievable by any algorithm regardless of the computational power and the size of the available training data (see Section 3.1). This is carried out by deriving the asymptotic expressions of standard and adversarial risks, and analysing the Pareto optimal points of a two dimensional region consisting of all the achievable $({\sf SR},{\sf AR})$ pairs. This analysis clearly demonstrates the existence of a non-trivial tradeoff between the two risks in linear regression as depicted in Figure 1.

In Section 3.2, we turn our attention to modern adversarial training algorithms and provide a precise characterizition of the standard and adversarial risks achieved by them. This is carried out in a high-dimensional regime where the size of the training data $n$ and the number of parameters $p$ grow proportional to each other with their ratio $n/p\to\delta$ for fixed $\delta\in(0,+\infty)$. A key ingredient of our analysis is a powerful extension of a classical Gaussian process inequality [Gor88] known as the Convex Gaussian Minimax Theorem developed in [TOH15] and further extended in [TAH18, DKT19].

Our precise characterization of the standard and robust risks for adversarial training algorithms allows us to rigorously study a variety of phenomena. First, we study the tradeoffs between standard and adversarial risks for a contemporary adversarial training algorithm and show that as the limiting ratio $n/p\to\delta$ between the number of training data $n$ and number of parameters $p$ grows, the algorithmic tradeoff curve approaches the fundamental (Pareto-optimal) tradeoff curve. These findings are manifested empirically in Figure 1. We also characterize the effect of the size of the training data and model overparametrization (see Section 3.3). We argue analytically and empirically that in the overparametrized regime (i.e. when $\delta<1$) adversarial training helps improve standard risk (compared to normal training). However, as the size of training data grows (i.e. $\delta$ becomes large) adversarial training effectively hurts standard risk. In short, adversarial training improves generalization in the overparametrized regime, but effectively hurts generalization in the sufficiently underparametrized regime. Finally, in Section 3.4 we demonstrate and prove the emergence of a phenomenon in adversarial training which is similar to the so-called double-descent phenomenon. When traditional training is used, the double-descent phenomena demonstrates that increasing the model complexity beyond a certain interpolation threshold always improves generalization. We show that the double-descent behavior continues to hold with adversarial training. However, for linear regression model considered in this paper, the global minimum of the risk is achieved under the interpolation threshold whose value changes with $\varepsilon$. Our theory also allows us to study how the adversarial training affects the interpolation threshold.

Problem formulation

In practice, many models trained by following this paradigm are often highly vulnerable to adversarial perturbations with many well documented examples in deep learning. This observation has given rise to a surge of interest in both, finding such perturbations (a.k.a adversarial attacks) and also learning models that are robust against such perturbations (a.k.a. adversarial training). A line of recent work [TSE+18, MMS+17] propose training approaches that demonstrate promising empirical performance against adversarial perturbations. Motivated by applications in image processing, these papers consider an adversarial attack model where for a predefined perturbation set $\mathcal{S}$, the adversary has the power of perturbing each data point $\bm{x}$ by adding an element of $\mathcal{S}$. Then an estimator ${\widehat{\bm{\theta}}}^{\mathcal{S}}$ is constructed by solving a saddle point problem that takes into account such manipulative power for the adversary:

To evaluate the performance of such an estimator, in this paper we consider two metrics of particular interest, standard risk and adversarial risk.

Standard risk. This is the expected prediction loss of an estimator ${\widehat{\bm{\theta}}}$ on an uncorrupted test data point that is generated from the same distribution as the training data. Namely,

Adversarial risk. This is the expected prediction loss of an estimator ${\widehat{\bm{\theta}}}$ on an adversarially corrupted test data point according to the attack model (2.2). Namely,

Stated differently, the adversarial risk measures how well the estimator ${\widehat{\bm{\theta}}}$ performs in predicting the true label when it is fed with an adversarially corrupted test data point. We note that the factor $1/p$ is the proper scaling so the risk has a finite limit under our asymptotic regime.

Focusing on linear regression, in this paper we aim to derive asymptotically exact characterizations of these two metrics and study the tradeoff achieved by the class of estimators ${\widehat{\bm{\theta}}}^{\mathcal{S}}$ of the form (2.2). These characterizations will also enable us to study the effect of various quantities (e.g. size and quality of the training data, model size, etc.) on the trade-off between statistical and adversarial risk. Specifically, we consider the linear regression model below.

Next we formally introduce the asymptotic regime of interest in this paper.

We have $\frac{n}{p}\to\delta\in(0,\infty)$ and $\frac{\sigma_{0}^{2}(n)}{p}\to\sigma^{2}$ as $n\to\infty$.

Empirical second moment of the signal converges, i.e., $\frac{1}{p}\sum_{i=1}^{p}\theta_{0,i}(n)^{2}\to V^{2}<\infty$, as $n\to\infty$.

In summary, we have introduced the following notations and terms which will be used throughout the paper: the dimension $p$, number of training data points $n$, overparametrization parameter $\delta=n/p$, normalized noise power $\sigma^{2}$, normalized norm of the true model $V^{2}$, and the adversary’s power $\varepsilon$.

Main Results

In this paper we wish to understand fundamental tradeoffs between standard and adversarial risks as well as what can be achieved by modern adversarial training approaches. In Section 3.1 we characterize the fundamental tradeoff between standard and adversarial risk achievable by any algorithm regardless of the computational power and the size of the available training data. Then in Section 3.2 we turn our attention to precisely characterizing the standard and adversarial accuracy tradeoffs achieved by modern adversarial training algorithms of the form (2.2). This is carried out in a high-dimensional regime where the size of the training data $n$ and the number of parameters $p$ grow proportional to each other with their ratio $n/p\to\delta$ for fixed $\delta\in(0,+\infty)$. Next, in Section 3.3 we focus on studying the role of that the size of the training data plays and how it affects the standard accuracy. Finally, in Section 3.4 we prove the emergence of a phenomena in adversarial training similar to the so-called double-descent phenomena without adversarial training.

Motivated by the conflict observed between standard and adversarial risk in modern adversarial training [MMS+18], we first wish to understand the fundamental tradeoffs that can be achieved between the two objectives. That is, the optimal tradeoff that can be achieved between standard and adversarial risk objectives for any estimator ${\widehat{\bm{\theta}}}$ even with access to infinite computational power and infinite training data. We discuss the tradeoffs achievable by specific algorithms with finite training data in the next section.

In the linear regression setting of this paper the expressions of standard accuracy (2.3) and adversarial accuracy (2.4) are convex functions of ${\bm{\theta}}$. Therefore, using standard results in multi-objective optimization we can derive all the Pareto optimal points of the $({\sf SR},{\sf AR})$ region, by minimizing a weighted combination of these two accuracies for different weights $\lambda$.

The Pareto-optimal curve is then given by $\{({\sf SR}({\bm{\theta}}^{\lambda}),{\sf AR}({\bm{\theta}}^{\lambda}):\;\lambda\geq 0\}$.

Analytical Expression of the Optimal Tradeoffs: Before we proceed to calculate ${\bm{\theta}}^{\lambda}$, we derive the standard and adversarial risks (${\sf SR}({\widehat{\bm{\theta}}})$ and ${\sf AR}({\widehat{\bm{\theta}}})$) as a functions of ${\bm{\theta}}_{0}$ and $\sigma_{0}^{2}$ in the Gaussian linear regression model. We defer the proof of this Lemma to Section 6.7.1.

Consider the linear regression setting of Definition 2.1. For a given estimator ${\widehat{\bm{\theta}}}$ the standard risk (2.3) is equal to

Furthermore, the adversarial risk (2.4) with a corruption level of $\varepsilon_{{\rm test}}$ is equal to

With a precise expression of the standard and adversarial risk in hand our next theorem characterizes the solution ${\bm{\theta}}^{\lambda}$ of the optimization problem (3.1) which in conjunction with Lemma 3.1 determines the Pareto-optimal tradeoff curve. We defer the proof of this result to Section 6.7.2.

Under the linear regression setting of Definition 2.1, the solution ${\bm{\theta}}^{\lambda}$ of the optimization problem (3.1) is given by

with $\gamma_{0}^{\lambda}$ the fixed point of the following two equations:

In Figure 1 we plot the Pareto optimal curve in the $({\sf SR},{\sf AR})$ plane in black for an instance where $\varepsilon_{{\rm test}}=0.5$ and the normalized norm of the true model and the noise power are both equal to one ($\sigma=V=1$). This curve serves as a fundamental limit on the performance of any algorithm even with access to infinite data and computational power. This figure also contains algorithmic tradeoffs which we discuss in further detail in the next section. In particular, in the next section we precisely characterize the SR-AR tradeoff achieved by a specific adversarial training algorithm.

2 Algorithmic tradeoffs between standard and adversarial risks

Given the fundamental tradeoff of the previous section, the natural question that arises is whether it is possible to achieve this tradeoff algorithmically with only finite data and computational power? Specifically, what is the tradeoff achieved by common adversarial training algorithms? In this section we consider the class of estimators ${\widehat{\bm{\theta}}}^{\varepsilon}$ constructed through the saddle point problem (2.6) for various values $\varepsilon$ at training i.e. $\{{\widehat{\bm{\theta}}}^{\varepsilon}:\,\varepsilon\geq 0\}$. We wish to precisely derive the tradeoff curve between the standard and the adversarial risks achieved by this class of estimators. We refer to such curve as algorithmic tradeoff curve since it corresponds to the specific class of saddle point estimators as opposed to the Pareto optimal trade off curves studied in Section 3.1 which serve as lowerbound for any estimator. To avoid any confusion about the tradeoffs discussed we would like to emphasize that:

In the training phase, we are varying the adversarial power $\varepsilon$, and accordingly, obtain a range of estimators ${\widehat{\bm{\theta}}}^{\varepsilon}$ by solving (2.6).

At test time, the adversarial power is fixed to a given value $\varepsilon_{{\rm test}}$ and we will measure the (expected) standard and adversarial risks of the trained estimators ${\widehat{\bm{\theta}}}^{\varepsilon}$ with respect to the true adversarial power $\varepsilon_{{\rm test}}$. By varying $\varepsilon$ at training time, we expect to sweep a tradeoff between standard and adversarial risks, i.e. estimators ${\widehat{\bm{\theta}}}^{\varepsilon}$ with large $\varepsilon$ should have a smaller adversarial risk but higher standard risk, and estimators with smaller $\varepsilon$ should behave the opposite.

The following convex-concave minimax scalar optimization has a unique solution $(\alpha_{*},\beta_{*},\gamma_{*},\tau_{h*},\tau_{g*})$:

We note that the loss (2.6) and its optimal solution are a rather complicated and high-dimensional function of the features/label pairs $\{(\bm{x}_{i},y_{i})\}_{i=1}^{n}$. Nevertheless the Theorem above provides a precise characterization of its properties using a 5 dimensional convex-concave mini-max optimization problem! Such a precise characterization allows us to provide a precise understanding of the standard and adversarial accuracies. In particular, combining Theorem 3.3 (parts (b)-(c)) with Lemma 3.1 we can obtain the asymptotic values of ${\sf SR}({\widehat{\bm{\theta}}}^{\varepsilon})$ and ${\sf AR}({\widehat{\bm{\theta}}}^{\varepsilon})$, and derive the algorithmic tradeoff curve achieved by the class $\{{\widehat{\bm{\theta}}}^{\varepsilon}:\,\varepsilon\geq 0\}$ as $\varepsilon$ varies (discussed in the next corollary proven in Section 6.8.2).

The corollary above provides a precise characterization of the standard and adversarial accuracy achieved by the adversarial training algorithm consisting of running gradient descent on the saddle point problem (2.6). In Figure 1, we plot the algorithmic tradeoff curve for several values of $\delta$ as well as the empirical values obtained by running gradient descent. As we observe, our theoretical prediction and the empirical values are rather close match even for moderately large parameter values ($p=1000$). Such a precise characterization allows us to rigorously study a variety of phenomena. We mention one such phenomena below and discuss others in the coming sections. The plots in Figure 1 clearly show that when $\delta$ grows the algorithmic tradeoff curve approaches the Pareto-optimal tradeoff curve. In other words, one can achieve optimal tradeoff of standard and adversarial risks by the specific class of estimators ${\widehat{\bm{\theta}}}^{\varepsilon}$ constructed by the saddle point problem (2.6). This observation is formally stated in the next theorem with the proof deferred to Section 6.8.3.

The theorem above formally proves that in the infinite data limit ($\delta\rightarrow+\infty$) one of the commonly used adversarial training algorithms achieves the optimal tradeoff between standard and robust accuracies.

3 The role of the size of the training data and overparameterization

As discussed, our precise understanding of the optimal solution of adversarial training allows us to precisely characterize the effect of various phenomena. In particular in this section we focus on the role of the size of the training data. We begin by considering the common scenario in modern learning where trained models often consist of more parameters than the training data set. In Figure 2-(a) we plot the standard risk, using Theorem 3.3 Part (b), versus $\varepsilon$ for different values of $\delta<1$. As we observe for small to moderate values of $\varepsilon$, this curve is decreasing in $\varepsilon$, which implies that adversarial training helps with improving standard accuracy. The standard risk falls steeper as $\delta$ becomes closer to one. In Figure 3-(a) we observe a similar trend for $\delta>1$. However, as $\delta$ grows larger than one, the positive effect of the adversarial training on the standard risk falters and we see a lower decline. When $\delta=10$, the curve almost levels at $\varepsilon=0$ and then starts to becomes increasing with $\varepsilon$. In other words, for larger $\delta$ we start to see that adversarial training has a negative effect on standard risk starting from smaller values of $\varepsilon$. Our theoretical prediction are in line with recent empirical observations of a similar flavor [TSE+18] observed in neural networks. Therefore, our theoretical results formally proves the emergence of such a behavior. We provide further insight into the emergence of this phenomena a long with some more rigorous theoretical guarantees in Appendix A.

4 Double-descent in adversarial training

When $\varepsilon=0$, the estimator ${\widehat{\bm{\theta}}}^{\varepsilon}$ given by (2.6) reduces to the least-squares estimator. It is known that the plot of standard risk as a function of number of model complexity ($1/\delta=p/n$) exhibits a so-called ‘double-descent’ behavior [BMM18, BHMM18, HMRT19]. Namely, (1) up to the interpolation threshold $\delta=1$ (beyond which the estimator achieves zero training error and the model interpolates the training data) the risk curve follows a U-shape; the risk first decreases as $p$ increases because the model becomes less biased but then starts to increase because of the inflated variance of the estimator. (2) After the peak at the interpolation threshold, the risk decreases and essentially attains its global minimum at ‘infinite’ model complexity (extremely overparametrized regime).

The double-descent phenomenon is not limited to neural networks and have been empirically observed in a variety of models including random features and random forest models. Recently, analytical derivation of this phenomenon has been developed for least square regression and random features model [TSE+18, MM19]. For least square regression with Gaussian covariates, it is shown that the global minimum of the risk is achieved in the underparametrized setting $\delta>1$ (unless miss-specified structures are assumed). Nonetheless, these work are focused on training with unperturbed features.

In Figure 4 (a), we plot the standard risk (theoretical predictions from Theorem 3.3) versus $1/\delta=p/n$, for several values of adversarial power $\varepsilon$. We also depict the empirical version of these curves in Figure Figure 4 (b). These plots demonstrate that the double-descent phenomena continues to hold even with adversarial training. Interestingly however the interpolation threshold changes with $\varepsilon$. For small $\varepsilon$, we observe double-descent behavior with the interpolation threshold $\delta\approx 1$. However, as $\varepsilon$ increases the location of the peak shifts to higher values of $1/\delta$.

Further Related Work

The trade-off between standard and adversarial accuracy has been studied recently in [MMS+18, SST+18, TSE+18, RXY+19, ZYJ+19, PJ19]. An central question is whether standard and robust objectives are fundamentally at conflict? In other words, is there a predictor that can achieve both optimal standard accuracy and robust accuracy when the number of training data samples is sufficiently large? In this regard, [TSE+18, ZYJ+19] construct learning problems where the optimal robust accuracy is fundamentally at conflict with the standard accuracy, i.e. no predictor can achieve both optimal standard accuracy and robust accuracy even in the infinite data limit. However, there are clearly many natural learning problems in which a predictor with optimal standard and high robust accuracy exists (hence the two objectives are not at conflict). An instance of such cases has been studied in [RXY+19] suggesting that the inconsistency between adversarial accuracy and standard accuracy may be due to insufficient number of training samples. In contrast, in this paper we have shown that a fundamental tradeoff exists between the two accuracies in linear regression even with limited samples.

Sketch and roadmap of the proof

To be able to provide a precise characterization of the various tradeoffs we need to develop a precise understanding of the adversarial training objective

Step I: Simplification of the loss (Section 6.2). The maximization objective is equal to the optimal value of a maximization problem and hence characterizing its properties directly is challenging. In the first step of our proof we show that one can in-fact solve this maximization problem and derive an expression for the loss in closed form. Specifically, we show

The main intuition behind this derivation is that one can think of the min-max optimization problem above as a game between a learner and an adversary where the learner first chooses a parameter $\bm{\theta}$ and then the adversary changes each feature $\bm{x}_{i}$ given the label $y_{i}$ and the learner’s choice of $\bm{\theta}$. We show that the best choice for the adversary to maximize the error is to pick $\bm{\delta}_{i}$ in the direction of $\bm{\theta}$ with a magnitude of $\varepsilon$ (maximum power of the adversary) and with the sign of the misfit on the $i$ the training data point ($\textrm{sgn}(\langle\bm{x}_{i},\bm{\theta}\rangle-y_{i})$). We formally prove this result by connecting it to the well-known trust region subproblem in optimization.

Step II: Reduction to an Auxiliary Optimization (AO) problem (Section 6.3). The loss (5.1), while significantly simplified, is still rather complicated and it is completely unclear how to precisely characterize its behavior and the quality of its optimal solution. In particular, the dependence on the random data matrix $\bm{X}$ is still rather complex hindering statistical analysis even in an asymptotic setting. To bring the optimization problem into a form more amenable to precise asymptotic analysis we carry out a series of reformulations of the optimization problem. First, we rescale the loss. Next we consider a change of variable of the form $\bm{z}=\frac{1}{\sqrt{p}}(\bm{\theta}-\bm{\theta}_{0})$ and add new variables by adding equality constraints. Finally, we use duality to cast the problem into a mini-max form. Combining these steps we arrive at the following equivalent Primal Optimization (PO) problem

This equivalent form may be counter-intuitive as we started by simplifying a different mini-max optimization problem and we have now again introduced a new maximization! The main advantage of this new form is that it is in fact affine in the data matrix $\bm{X}$. This particular form allows us to use a powerful extension of a classical Gaussian process inequality due to [Gor88] known as Convex Gaussian Minimax Theorem (CGMT) [TOH15] which focuses on characterizing the asymptotic behavior of mini-max optimization problems that are affine in a Gaussian matrix $\bm{X}$. This result enables us to characterize the properties of (5.2) by studying the asymptotic behavior of the following, arguable simpler, Auxiliary Optimization (AO) problem instead

We emphasize that the relationship between the above AO problem (5.3) and how it is exactly related to the PO problem (5.2) is much more intricate and technical. See Section 6.3 for details.

Step III: Scalarization of the Auxiliary Optimization (AO) problem (Section 6.4). In this step we further simplify the AO problem in (5.3). In particular we show the asymptotic behavior of the AO can be characterized rather precisely via the following scalar optimization problem involving five variables:

In particular a variety of conclusions can be derived based on the optimal solutions of the above optimization problem as we discuss in the next step. We note that while the expressions may look complicated we prove that this optimization problem is in fact convex in the minimization parameters $(\alpha,\tau_{g})$ and concave in the maximization parameters $(\beta,\gamma,\tau_{h})$ so that its optimal solutions can be easily derived via a simple low-dimensional gradient descent rather quickly and accurately. We also note that this proof is quite intricate and involved, so it is not possible to give an intuitive sketch of the arguments here. We refer to Section 6.4 for details.

Proofs

2 Simplification of the loss

As discussed earlier in this section we wish to derive a closed form for the loss

To this aim first note that the maximization in (6.1) decouples over $i$ so that we can write

To continue further define $\widetilde{y}_{i}:=y_{i}-\langle\bm{x}_{i},{\bm{\theta}}\rangle$. By expanding the square the optimization over $\bm{\delta}_{i}$ can be rewritten in the form

Substituting the latter into (6.1) we arrive at (6.2) to complete our simplification of the loss.

3 Reduction to an auxiliary optimization problem via CGMT

We are interested in characterizing the properties of the optimal paramter ${\widehat{\bm{\theta}}}^{\varepsilon}$ and thus it shall be convenient to work with a scaled version of the loss (6.2). This scaling of course does not affect the optimal solution ${\widehat{\bm{\theta}}}^{\varepsilon}$. Thus hence forth we focus on the following objective

To continue further it is convenient to consider a change of variable of the form $\bm{z}=\frac{1}{\sqrt{p}}(\bm{\theta}-\bm{\theta}_{0})$ and note that

Equivalently we can rewrite this optimization problem in the form

We note that the scaling of $\bm{v}$ is arbitrary but serves the purpose of simplifying the exposition later on. The loss above is still rather complicated and it is unclear how to study and characterize the properties of its optimal solution in an asymptotic regime where the size of the training data and the number of parameters grow in proportion with each other. To study this loss in an asymptotic fashion we first cast it as a different mini-max optimization using duality. In particular by associating a dual variable $\frac{\bm{u}}{p}$ with the equality constraint, we obtain

At first this may be counter-intuitive as we started by simplifying a different mini-max optimization problem and now we are again introducing a new maximization! The main advantage of this new form is that (6.3) is in fact affine in the matrix. This particular form allows us to use a powerful extension of a classical Gaussian process inequality due to Gordon [Gor88] known as Convex Gaussian Minimax Theorem (CGMT) [TOH15] which focuses on characterizing the asymptotic behavior of mini-max optimization problems that are affine in a Gaussian matrix $\bm{X}$. Formally, the CGMT framework shows that a problem of the form

with $\bm{X}$ a matrix with $\mathcal{N}(0,1)$ entries can be replaced asymptotically with

where $\bm{g}$ and $\bm{h}$ are independent Gaussian vectors with i.i.d. $\mathcal{N}(0,1)$ entries and $\psi(\bm{z},\bm{u})$ is convex in $\bm{z}$ and concave in $\bm{u}$. In the above $\mathcal{S}_{\bm{z}}$ and $\mathcal{S}_{\bm{u}}$ are compact sets. We refer to [TOH15, Theorem 3] for precise statements. Following [TOH15] we shall refer to problems of the form (6.7) and (6.8) as the Primal Problem (PO) and the Auxiliary Problem (AO).

With these compact constraints in place we can now apply the CGMT result. To this aim note that this optimization is in the desired form of a Primary Optimization (PO): it has a bilinear term $\bm{u}^{T}\bm{X}{\bm{z}}$ plus a function

which is convex in $\bm{z}$Note that the prior to the minimization over $\bm{v}$ the problem is trivially jointly convex in $(\bm{z},\bm{v})$ and partial minimization preserves convexity. and concave in $\bm{u}$. The corresponding Auxiliary Optimization (AO) thus takes the form

4 Scalarization of the auxilary optimization problem

In this section we continue our proof by significantly simplifying the AO problem. In particular we show that the behavior of the AO and hence the PO can be completely characterized by (6.4). This is arguably the most intricate part of our proofs.

Plugging the latter into (6.3) the AO reduces to

To proceed it would be convenient to flip the order of minimum and maximum in the above. However, for this to be allowed the mini-max problem typically has to be convex/concave in the min/max parameters (e.g. via the celebrated Sion’s min-max Theorem [S+58]). It is not clear that the above objective has this form so that the flipping of the order of the min and max is justified. However, since the original PO problem is convex/concave in the min/max parameters one can justify such a flipping of the min and max in the AO based on the PO. We note that this is justified for asymptotic calculations and refer to [TAH15, Appendix A.2.4] for precise details on this derivation. Thus, we will instead consider the following problem as the (AO) which is asymptotically equivalent to (6.11)

with respect to the variable $\bm{z}$ is given by

To simplify further we next focus on the maximization over $\bm{q}$ or equivalently the following minimization problem

Plugging the latter into (6.4) the AO reduces to

To continue we state a lemma with the proof deferred to Appendix C.2

is jointly convex in the parameters $(\gamma,\beta,\tau_{h})$.

We now focus on minimization over $\bm{v}$. To this aim note that

Recall the definition of the Moreau envelope function of a function $f$ at a point $\bm{x}$ with parameter $\mu$,

In our next lemma we compute $e_{f}$. We defer the proof to Appendix C.3.

Consider the function $f$ given by (6.18). Then,

Furthermore, $e_{f}(\bm{x};\tau)$ is strictly convex in $\bm{x}$.

Plugging this in (6.4) the AO problem reduces to

We note that since the problem (6.4) was jointly convex in $(\bm{v},\alpha,\tau_{g})$ and (6.4) jointly concave in $(\beta,\gamma,\tau_{h})$ and partial minimization preserves convexity we thus conclude that the objective is jointly convex in $(\alpha,\tau_{g})$ and jointly concave in $(\beta,\gamma,\tau_{h})$ (after the minimization over $\tau\geq 0$ has been carried out). Note that trivially in an asymptotic regime

Also using concentration of Lipschitz functions of Gaussian we have

Plugging all of the above in (6.4) we arrive at

To simplify further we also need an asymptotic characterization of $\frac{1}{p}G\left(\alpha\bm{g}-\bm{\omega};\frac{\tau_{g}}{\beta},\tau\right)$. To this aim we prove the following lemma with the proof deferred to Appendix C.4.

where $\tau^{*}(a,\mu)$ is the unique solution to

Plugging the above lemma in (6.4) we arrive at

This completes the scalarization of the AO.

(Convergence analysis). In above we showed the point wise convergence of the objective function in (6.4) to function D given by (6.4). However, what is required in this framework, is (local) uniform convergence so we get that the minimax solution of the objective function in (6.4) also converges to the minimax solution of the AO problem (6.4). This can be shown by following similar arguments as in [TAH18, Lemma A.5] that is essentially based on a result known as “convexity lemma” in the literature (see e.g. [LM08, Lemma 7.75]) by which point wise convergence of convex functions implies uniform convergence in compact subsets.

6 Uniqueness of the solution of the AO problem

As we discussed after Equation (6.18), the function $f(\bm{v};\gamma)$ is convex in $\bm{v}$. Furthermore, we wrote (6.4) (part of the objective that depends on $\bm{v}$) in terms of the Moreau envelope $\frac{1}{p}e_{f}(\bm{\omega}-\alpha\bm{g};\tfrac{\tau_{g}}{\beta})$ and as $n\to\infty$, its limit goes to the expected Moreau envelope. Now by using the result of [TAH18, Lemma 4.4] the expected Moreau envelope of a convex function is strictly convex ( without requiring any strong or strict convexity assumption on the function itself). Therefore, the convexity-concavity property discussed after (6.4) is preserved after taking the limit and the AO objective $D(\alpha,\beta,\gamma,\tau_{h},\tau_{g})$ is jointly strictly convex in $(\alpha,\tau_{g})$ and jointly concave in $(\beta,\gamma,\tau_{h})$.

We next note that $\sup_{\beta,\gamma,\tau_{h}}D(\alpha,\beta,\gamma,\tau_{h},\tau_{g})$ is strictly convex in $(\alpha,\tau_{g})$. This follows from the fact that if $f(\bm{x},\bm{y})$ is strictly convex in $\bm{x}$, then $\sup_{\bm{y}}f(\bm{x},\bm{y})$ is also strictly convex in $\bm{x}$. We next use [TAH18, Lemma C.5] to conclude that $\inf_{\tau_{g}}\sup_{\beta,\gamma,\tau_{h}}D(\alpha,\beta,\gamma,\tau_{h},\tau_{g})$ is strictly convex in $\alpha>0$.Therefore, its minimizer over $\alpha\geq 0$ is unique, which completes the proof.

7 Proofs for fundamental tradeoffs

To characterize ${\sf AR}({\widehat{\bm{\theta}}})$, note that by following a similar argument as in Section 6.2, the solution of the problem

Therefore the adversarial risk can be written as

By substituting for $y=\langle\bm{x},{\bm{\theta}}_{0}\rangle+w$ and expanding the terms, we get

7.2 Proof of Proposition 3.2

Substituting for ${\sf SR}({\bm{\theta}})$ and ${\sf AR}({\bm{\theta}})$ from Lemma 6.7.1 and scaling the objective by a factor $p$, we get

Now by setting the derivative to zero we arrive at the following identity for ${\bm{\theta}}^{\lambda}$:

which is the desired claim. The proof is complete by noting that

8 Proofs for algorithmic tradeoffs

We have already prove part (a) in the previous sections. Part (b) is also trivial from (6.4) as

As discussed in Section 6.3 the conjugate function takes the form

and the AO problem can therefore be written as (same as (6.12))

Setting derivative w.r.t $\bm{z}$ to zero we arrive at

Thus taking Euclidean norm of both sides of the identity we have

with $\omega=\sqrt{\alpha^{2}+\sigma^{2}}$, $\mu=\frac{\tau_{g}}{\beta}$, $\tau^{*}:=\tau^{*}\left(\frac{\gamma(\mu+1)}{\delta\varepsilon\omega},\mu\right)$ and $\tau^{*}(a,\mu)$ is the unique solution to

Therefore, squaring (6.30) and plugging in (6.31) we conclude that

8.2 Proof of Corollary 3.4

The result follows readily from Lemma 3.1 along with Theorem 3.3 (Parts (b) and (c)).

8.3 Proof of Theorem 3.5

We start by analyzing $\lim_{p\to\infty}{\sf SR}({\bm{\theta}}^{\lambda})$ and $\lim_{p\to\infty}{\sf AR}({\bm{\theta}}^{\lambda})$. Using Lemma 3.1, we have

with $\gamma_{0}^{\lambda}$ the fixed point of the following two equations:

We next analyze $\lim_{\delta\to\infty}\lim_{n\to\infty}{\sf SR}({\widehat{\bm{\theta}}}^{\varepsilon})$ and $\lim_{\delta\to\infty}\lim_{n\to\infty}{\sf AR}({\widehat{\bm{\theta}}}^{\varepsilon})$. By using Corollary 3.4, we have

Therefore, we need to study the solution of the convex-concave minimax optimization (6.4) at the limits $\delta\to\infty$. It is straightforward to see that as $\delta\to\infty$, the indicator in (6.4) is active and hence it reduces to

Since $\gamma(\tau_{g}+\beta)>\sqrt{\frac{2}{\pi}}\delta\varepsilon\beta\sqrt{\alpha^{2}+\sigma^{2}}$, we have $\gamma\to\infty$ as $\delta\to\infty$, and by the above equation for $\gamma_{*}$, we obtain that $\tau_{h}\to\infty$. Therefore,

In addition, $\tau_{*}\to 0$ as $\delta\to\infty$. Writing the Taylor expansion of the characteristic equation of $\tau_{*}$ as per (6.24), we get

We adopt the shorthands $\omega:=\sqrt{\alpha^{2}+\sigma^{2}}$ and $\mu:=\frac{\tau_{g}}{\beta}$. Combining (6.40) with (6.39) yields

Writing the objective $D$ given by (6.38) in terms of $\omega$, $\mu$, $\eta$ and after substituting for $\gamma_{*}$ we arrive at

Since $\delta,\tau_{h}\to\infty$, keeping only the dominant terms results in

and by keeping only terms of $O(\tau_{*}^{2})$ we have

Setting the derivative of $D$, with respect to $\tau_{h}$, to zero, we get

We next set the derivative of $D$, with respect to $\alpha$, to zero, which implies

Plugging in for $\alpha$ from (6.44) we obtain

Defining $A^{\varepsilon}:=\frac{\varepsilon\mu}{\tau_{*}}$ and $\gamma_{0}^{\varepsilon}:=\frac{\varepsilon\mu V}{\tau_{*}\omega}-1$, the above two equations (6.44), (6.45) imply that

In addition, from (6.46) and (6.47) we have

Combining equations (6.48) and (6.49), we have that $\gamma_{0}^{\varepsilon}$ is the fixed point of the following two equations:

Now consider a fixed $\lambda\geq 0$ and let $\gamma_{0}^{\lambda},A^{\lambda}$ be defined by (6.35). Comparing equations (6.33) and (6.34) with (6.36) and (6.37), we see that in order to prove the statement, it suffices to find corresponding $\varepsilon\geq 0$ such that $\gamma_{0}^{\varepsilon}=\gamma_{0}^{\lambda}$ (Note that the statement $\gamma_{0}^{\varepsilon}=\gamma_{0}^{\lambda}$ implies that $A^{\varepsilon}=A^{\lambda}$ as well). Such value of $\varepsilon$ is hence found from the following equation (which equates $\gamma_{0}^{\varepsilon}=\gamma_{0}^{\lambda}$ and $A^{\lambda}=A^{\varepsilon}$):

The thesis now follows by noting that the above equation is a quadratic form in $\varepsilon$ and has always a positive solution, which gives the value of $\varepsilon$ in terms of $\lambda$.

Acknowledgements

A. Javanmard is partially supported by a Google Faculty Research Award and the NSF CAREER Award DMS-1844481. M. Soltanolkotabi is supported by the Packard Fellowship in Science and Engineering, a Sloan Research Fellowship in Mathematics, an NSF-CAREER under award $\#1846369$, the Air Force Office of Scientific Research Young Investigator Program (AFOSR-YIP) under award $\#$FA$9550-18-1-0078$, Darpa Learning with Less Labels (LwLL) program, an NSF-CIF award $\#1813877$, and a Google faculty research award. This work was done in part while M.S. was visiting the Simons Institute for the Theory of Computing. The research of H. Hassani is supported by NSF HDR TRIPODS award 1934876, NSF award CPS-1837253, NSF award CIF-1910056, and NSF CAREER award CIF-1943064.

References

Appendix A Further insights and guarantees into the effect of the size of the training data

To provide further insight into the role of the size of the training data on adversarial training we note that we have already shown in our proofs (See Section 6.2 and equation (6.2)) that the inner maximization in the saddle point problem (2.6) has a closed form solution and the estimator ${\widehat{\bm{\theta}}}^{\varepsilon}$ can be equivalently defined by

Therefore for linear regression, adversarial training by the saddle point optimization (2.2) amounts to a regularized estimator. When $\delta<1$, we are in the overparametrized regime and regularization helps with standard accuracy. In particular, when $\delta\to 1$, the condition number of the covariate matrix diverges (a.k.a interpolation threshold [BMM18, BHMM18, HMRT19]) and the role of regularization becomes crucial, without which the standard risk would diverge. This is reflected in Figure 2 in that the standard risk diverges at $\varepsilon=0$ as $\delta\to 1$, and also the statistical risk plummets quickly with $\varepsilon$ ; See also Proposition A.1 below.

Nonetheless, in the $\delta>1$ regime the effect of regularization starts to weaken. To see why, note that as $\delta$ grows, the ratio of sample size $n$ to the dimension $p$ increases, and the reduction in the variance of the estimator due to regularization becomes comparative to the increase in the bias caused by this term. As a result the overall positive effect of regularization on standard risk lessens and we see in Figure 3, the negative slope at $\varepsilon=0$ decreases as $\delta$ increases. In addition, at large $\delta$, the standard risk will start to quickly becomes increasing with $\varepsilon$. In other words, for larger $\delta$, the negative effect of adversarial training on standard risk starts to emerge at smaller values of $\varepsilon$. (For example at $\delta=10$, this effect kicks in at $\varepsilon=0.15$.)

Our next proposition describes the standard risk at small values of $\varepsilon$.

Under the assumptions of Theorem 3.3 and for $\delta\geq 1$ and $\varepsilon\leq 1$, we have

As a result of Proposition A.1, for $\varepsilon$ small and $\delta\geq 1$: (i) standard risk $\alpha_{*}$ falls with $\varepsilon$ at vicinity of $\varepsilon=0$ (ii) the risk falls slower at larger $\delta$ (iii) as $\delta\to 1$, the slope diverges and the risk plummets rapidly. These observations corroborates our justification and insights provided above.

We finish this appendix by the proof of Proposition A.1.

Define $\bm{x}=(\alpha,\beta,\tau_{h},\tau_{g},\gamma)$. We can write the objective of the convex-concave minimax problem (6.22) as

where $\bar{D}$ does not depend on $\varepsilon$. It is easy to see that when $\varepsilon=0$, then $\gamma=0$. Otherwise $\tau^{*}=\infty$ and $\widetilde{D}=-\infty$ which implies that the maximum of $D$ over $\gamma$ is achieved at $\gamma=0$. Therefore at $\varepsilon=0$, we get

The stationary point is given by $(\tau_{g}+\beta)^{2}=\delta(\alpha^{2}+\sigma^{2})$, $\tau_{h}=\beta$ and $\delta\alpha=\tau_{g}+\beta$, $\tau_{g}=\alpha$ (derivative with respect to $\beta$). Putting things together we have

We next study the behavior of the convex-concave minimax problem 6.22 at infinitesimal $\varepsilon$. Rewriting the expressions for $\bar{D}$ and $\widetilde{D}$, we have

Let $\gamma_{0}:=\sqrt{\frac{2}{\pi}}\frac{\delta\varepsilon\beta\sqrt{\alpha^{2}+\sigma^{2}}}{\tau_{g}+\beta}$. If $\gamma\geq\gamma_{0}$, then $D$ is a quadratic function of $\gamma$ with the peak location at

If $\gamma<\gamma_{0}$, then $D=\bar{D}$ is quadratic in $\gamma$ with the peak location at

Therefore, to find the optimal $\gamma$ we need to consider three different cases, giving us

As $\varepsilon\to 0$, we have $\gamma_{0}\to 0$. However, using (A.3) we get $\gamma_{2}\to\sqrt{\sigma^{2}(\delta-1)+(\delta-1)^{2}V^{2}}>0$. By continuity, at infinitesimal $\varepsilon$ we get $\gamma_{0}<\gamma_{2}$. Hence, in (A.5) only the first two cases may happen. Suppose that the first case occurs. Then, $0\leq\gamma_{0}\leq\gamma_{1}$ and by definition of $\gamma_{1}$ we obtain that $\tau_{*}=O(\varepsilon)$. Invoking the characterization equation of $\tau_{*}$ as per (6.24), we get

If the second case in (A.5) happens, we have $\gamma_{*}=\gamma_{0}=\sqrt{\frac{2}{\pi}}\frac{\delta\varepsilon\beta\sqrt{\alpha^{2}+\sigma^{2}}}{\tau_{g}+\beta}$ and $\tau_{*}=0$. So this case is subsumed in (A.6) and henceforth we can proceed with (A.6).

By Taylor expansion of the ${{\rm erf}}$ function we have

which implies that $\widetilde{D}=O(\tau_{*}^{3})=O(\varepsilon^{3})$. Separating $O(\varepsilon^{2})$ terms from the lower order terms we get

Letting $\bm{x}=(\alpha,\beta,\tau_{g},\tau_{h})$, we then have

To get the stationary points, we need to solve for $\nabla D(\bm{x})=0$. However, to find the solution up to $O(\varepsilon)$ term we can instead solve for $\nabla D_{0}(\bm{x})+\varepsilon\nabla D_{1}(\bm{x})=0$. To see why, suppose that $\nabla D(\bm{x}_{*})=0$ and write $\bm{x}_{*}=\bm{x}_{0}+\varepsilon\bm{x}_{1}+O(\varepsilon^{2})$. Hence,

This implies that $\bm{x}_{0}$ and $\bm{x}_{1}$ should satisfy

We proceed by computing the stationary points of $D_{0}(\bm{x})+\varepsilon D_{1}(\bm{x})$. Writing KKT conditions with respect to $\alpha$, $\beta$, $\tau_{g}$, $\tau_{h}$ we have

Second equation can be simplified using other equations as

Define $\eta=\beta/\tau_{h}>1$ (since $\varepsilon>0$). The second equation gives $\tau_{g}=\alpha/2(\eta+1/\eta)$. While this becomes useful in finding optimal $\tau_{g}$ it does not matter with our goal of finding $\alpha$ as everywhere $\tau_{g}$ appears in form $\beta+\tau_{g}$. The first equation though gives

We now proceed by taking derivatives of both equations implicitly with respect to $\varepsilon$ and evaluate them at

Note that the derivative of the first equation yields

Setting $\varepsilon=0$ in the above yields

Plugging in for $\beta_{*},\tau_{g*},\alpha_{*}$ the coefficient of $\frac{{\rm d}}{{\rm d}\varepsilon}(\beta+\tau_{g})$ vanishes and we arrive at

Now, invoking the definition of statistical risk we have

Appendix B Proofs that the minimization and maximization primal problems can be restricted to a compact set

The optimization problem above is still not in a form where CGMT can be applied as there are no compact restriction on $\bm{u}$. This is the subject of the next lemma.

Writing the KKT conditions for (B.1) we have

From the first equation we have that $\bm{v}=\frac{\bm{w}}{\sqrt{p}}-\bm{X}\bm{z}$. Thus,

Appendix C Proofs for scalarization of Auxilary Optimization (AO)

We restate the lemma for the convenience of the reader.

[Restatement of Lemma 6.1] The conjugate of

with respect to the variable $\bm{z}$ is given by

We begin by calculating the conjugate of a slightly simpler function

Setting derivative w.r.t $\bm{\theta}$ to zero, we get

Taking the Euclidean norm from both sides we conclude that

We can put the two cases together using the notation $z_{+}=\max(z,0)$.

To continue note that if we have $f(\bm{x})=g(\bm{A}\bm{x}+\bm{x}_{0})$ the conjugate is given by

Thus using above with $\bm{x}_{0}=\bm{\theta}_{0}$ and $\bm{A}=\sqrt{p}$ we arrive at

C.2 Proof of Lemma 6.2

is jointly convex in the parameters $(\gamma,\beta,\tau_{h})$.

with the Hessian with respect to $(\gamma,\beta)$ equal to

is jointly convex in $(\gamma,\beta)$. Therefore the perspective function

is jointly convex in $(\gamma,\beta,\tau_{h})$. ∎

C.3 Proof of Lemma 6.3

We begin by stating and proving the following lemma.

The value of the following problem (with $\lambda>1$)

where ${\sf ST}(\bm{x};\tau)$ is the soft-thresholding function.

Notably the lemma above transforms the first optimization (on vector $\bm{v}$) to an optimization over scalar $\tau$.

where in the penultimum Since ${\sf ST}(\bm{x};0)=\bm{x}$ and we showed that it is the optimal $\bm{v}$, the claim holds in this case. Namely, the minimizer is achieved at a point in $\{{\sf ST}(\bm{x};\tau):\;\tau\geq 0\}$.

Using Lemma C.3 with $\lambda=\frac{1+\mu}{\mu}>1$, we arrive at

The result follows by a change of variable $\tau(\mu+1)\to\tau$.

C.4 Proof of Lemma 6.4

We begin by restating the lemma for the convenience of the reader.

where $\tau^{*}(a,\mu)$ is the unique solution to

Alternatively using the fact that ${\rm erf}=1-{\rm erfc}$ we can rewrite this in the form

where $\tau^{*}(a,\mu)$ is the unique solution to

First note that by law-of large numbers we have

The proof of the first identity follows by combining the two summands.

To prove the second identity note that using a change of variable $\tau/\omega\rightarrow\tau$

To continue note that if only the first term is active the derivative is given by

and when both terms are active the derivative is given by

We note that the function $(\mu+1)\left(\frac{\gamma}{\delta\varepsilon\omega}-\frac{\tau}{\mu}\right)+\tau\cdot\text{erfc}\left(\frac{\tau}{\sqrt{2}}\right)-\sqrt{\frac{2}{\pi}}e^{-\frac{\tau^{2}}{2}}$ is always decreasing when $\tau\geq 0$ and its value at $\tau=0$ is given by $\frac{\gamma(\mu+1)}{\delta\varepsilon\omega}-\sqrt{\frac{2}{\pi}}$. To continue further consider two cases.

Case I: $\gamma(\mu+1)\leq\sqrt{\frac{2}{\pi}}\delta\varepsilon\omega$: In this case the function is always increasing in $\tau\in[0,+\infty)$ and thus the minimum is achieved at $\tau=0$ with the corresponding optimal value given by

Case II: $\gamma(\mu+1)>\sqrt{\frac{2}{\pi}}\delta\varepsilon\omega$: In this case the function is decreasing at the beginning and then increases. Therefore, the minimum is achieved at a point where