PaperlayerView exact revision on arXiv

Source-linked AI summary

Precise Tradeoffs in Adversarial Training for Linear Regression

Adel Javanmard, Mahdi Soltanolkotabi, Hamed Hassani

arXiv:2002.10477v1cs.LGmath.OCstat.ML

TL;DR

Adversarial training can improve robustness to perturbed inputs while reducing accuracy on unperturbed inputs, and the tradeoff's dependence on data and model size remains to be understood. The paper characterizes fundamental and algorithmic tradeoffs for linear regression with Gaussian features; as n/p grows, the algorithmic tradeoff curve approaches the fundamental Pareto-optimal curve.

  • Problem

    The paper asks how standard and adversarial performance trade off, and how the tradeoff depends on data size and quality and model size, amid incomplete understanding of adversarial training's role.

    Source: §1 · p. 2

  • Method

    The paper analyzes linear regression with Gaussian features, characterizing the algorithm-independent risk tradeoff and the standard and adversarial risks of a contemporary training algorithm in a proportional high-dimensional regime.

    Source: §1 · p. 2

  • Results

    As n/p grows, the algorithmic tradeoff curve approaches the fundamental Pareto-optimal curve; adversarial training improves standard risk when δ < 1 but hurts it as δ becomes large.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The characterizations support rigorous study of how data size and model overparametrization affect standard and adversarial risks, including double-descent behavior under adversarial training.

    Source: §1 · p. 3

    The presented analysis is for standard Gaussian features; extension to general Gaussian linear regression with covariance Σ is possible but its derivations are omitted from this version.

    Source: §2 · p. 4

Abstract

from arXiv · show

Despite breakthrough performance, modern learning models are known to be highly vulnerable to small adversarial perturbations in their inputs. While a wide variety of recent \emph{adversarial training} methods have been effective at improving robustness to perturbed inputs (robust accuracy), often this benefit is accompanied by a decrease in accuracy on benign inputs (standard accuracy), leading to a tradeoff between often competing objectives. Complicating matters further, recent empirical evidence suggest that a variety of other factors (size and quality of training data, model size, etc.) affect this tradeoff in somewhat surprising ways. In this paper we provide a precise and comprehensive understanding of the role of adversarial training in the context of linear regression with Gaussian features. In particular, we characterize the fundamental tradeoff between the accuracies achievable by any algorithm regardless of computational power or size of the training data. Furthermore, we precisely characterize the standard/robust accuracy and the corresponding tradeoff achieved by a contemporary mini-max adversarial training approach in a high-dimensional regime where the number of data points and the parameters of the model grow in proportion to each other. Our theory for adversarial training algorithms also facilitates the rigorous study of how a variety of factors (size and quality of training data, model overparametrization etc.) affect the tradeoff between these two competing accuracies.

1 Introduction

The paper studies adversarial training in linear regression to clarify the tradeoff between standard and adversarial performance and how data and model size affect it. It characterizes both an algorithm-independent fundamental tradeoff and the behavior of a contemporary adversarial training algorithm.

1 Introduction

  • Adversarial training can improve performance on perturbed inputs while decreasing performance on unperturbed inputs, motivating study of their tradeoff.The introduction also notes empirical evidence that data-related factors can alter this balance.Source: §1 · p. 2
  • The paper asks how the fundamental standard/adversarial accuracy tradeoff depends on finite versus infinite data, data size and quality, and model size.Overparametrization is given as an example of model size.Source: §1 · p. 2
  • The paper focuses on linear regression, where it characterizes risks rather than accuracies.The authors describe the setting as a simple yet foundational problem.Source: §1 · p. 2
  • The fundamental standard-risk/adversarial-risk tradeoff is non-trivial and applies to any algorithm, regardless of computational power or available training-data size.The analysis characterizes Pareto-optimal points among achievable risk pairs.Source: §1 · p. 2
  • As n/p grows, the contemporary algorithm's tradeoff curve approaches the fundamental Pareto-optimal curve.The paper also reports that adversarial training improves standard risk when δ < 1 but hurts it as δ becomes large.Source: §1 · p. 3

2 Problem formulation

This section formulates linear regression with adversarially perturbed inputs and defines standard and adversarial risk for evaluating estimators. It specifies a Gaussian-feature, quadratic-loss setting and introduces asymptotic analysis of the risks and their tradeoff.

2 Problem formulation

  • Training uses a saddle-point estimator that accounts for an adversary perturbing each input within a predefined set.The paper describes this attack model in motivating adversarial training approaches.Source: §2 · p. 3
  • Standard risk is expected prediction loss on uncorrupted test data from the training distribution, while adversarial risk evaluates loss on adversarially corrupted test data.Adversarial risk measures prediction of the true label under the specified attack model.Source: §2 · p. 4
  • The analysis seeks asymptotically exact characterizations of both risks and the tradeoff achieved by the considered estimators.These characterizations are used to study effects of data size and quality and model size.Source: §2 · p. 4
  • The analysis is presented for standard Gaussian linear regression; extension to general Gaussian features with covariance Σ is noted but its derivations are not included in this version.The authors state that the extension requires more involved derivations.Source: §2 · p. 4
  • The paper studies linear models with quadratic loss and adversarial perturbations constrained to an ℓ2 ball of radius ε.The adversary's power is represented by ε.Source: §2 · p. 4

3 Main Results

The paper characterizes fundamental standard–adversarial risk tradeoffs and those achieved by adversarial training in Gaussian linear regression. It also studies how training-data size and model complexity shape these tradeoffs, including a double-descent pattern under adversarial training.

3.1 Fundamental tradeoffs between standard and adversarial risk

  • The fundamental Pareto-optimal curve bounds achievable standard and adversarial risks for any estimator, and the risks have analytical expressions in the Gaussian linear-regression setting.The curve consists of the risk pairs associated with solutions to a weighted optimization over the two risks.Source: §3.1 · pp. 5–6

3.2 Algorithmic tradeoffs between standard and adversarial risks

  • The algorithmic risks are characterized in a high-dimensional regime where n and p grow proportionally, using a five-dimensional convex-concave minimax optimization.Combining its characterization with the risk formulas yields the asymptotic standard and adversarial risks for the saddle-point estimators.Source: §3.2 · p. 8
  • In the infinite-data limit, a commonly used adversarial-training algorithm achieves the optimal tradeoff between standard and robust accuracies.As the data-to-parameter ratio grows, its algorithmic tradeoff curve approaches the fundamental Pareto-optimal curve.Source: §3.2 · p. 9

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

  • For δ < 1, standard risk decreases with adversarial training, with a steeper decline as δ approaches one; for δ = 10, it starts increasing at smaller ε.The reported behavior is consistent with empirical observations in neural networks [TSE+18].Source: §3.3 · p. 10

3.4 Double-descent in adversarial training

  • Under adversarial training, standard risk retains double descent, but increasing ε shifts the interpolation peak toward higher model complexity 1/δ = p/n.The paper reports the shift for its theoretical and empirical curves.Source: §3.4 · p. 11, Figure 4 · p. 11

4 Further Related Work

Prior work studies whether standard and robust accuracy conflict, including how sample sufficiency and model capacity affect the tradeoff. This paper reports a fundamental tradeoff in linear regression even with limited samples.

4 Further Related Work

  • Prior work asks whether a predictor can attain optimal standard and robust accuracy with enough data; [TSE+18] give settings where it cannot, even with infinite data.Source: §4 · p. 11
  • The paper finds a fundamental standard–adversarial accuracy tradeoff in linear regression even with limited samples, contrasting with sample-insufficiency explanations [RXY+19].Earlier work constructed settings with a conflict even in the infinite-data limit [TSE+18, ZYJ+19], while [RXY+19] suggested insufficient samples may explain inconsistency.Source: §4 · p. 12
  • Other studies consider how model capacity affects the tradeoff; [Nak19] gives classification problems where more complex classifiers can provide high robust accuracy.The section also notes robust learnability and vulnerability results for classification, while distinguishing this regression setting by its smoothly varying loss [GMF+18].Source: §4 · p. 12

5 Sketch and roadmap of the proof

The proof roadmap simplifies the adversarial loss, reformulates its optimization for asymptotic analysis, and reduces it to a scalar problem. The resulting scalar characterization supports the paper’s theorems.

5 Sketch and roadmap of the proof

  • The adversary’s maximizing perturbation points along the parameter vector, has magnitude ε, and takes the sign of each training point’s misfit.The authors connect this choice to the trust-region subproblem to obtain a closed-form adversarial loss.Source: §5 · p. 12
  • The proof reformulates the simplified loss as an equivalent primal optimization problem to make its dependence on the random data matrix more amenable to asymptotic analysis.It rescales the loss, changes variables, adds equality constraints, and uses duality to reach a minimax form.Source: §5 · pp. 12–13
  • The primal problem’s affine dependence on the Gaussian data matrix permits CGMT analysis through an auxiliary optimization problem.The relationship between the primal and auxiliary problems is technical and is deferred to Section 6.3.Source: §5 · p. 13
  • The auxiliary optimization’s asymptotic behavior is characterized by a five-variable scalar optimization problem.The problem is convex in minimization parameters and concave in maximization parameters, allowing its solutions to be found with low-dimensional gradient descent.Source: §5 · pp. 13–14
  • The authors derive the stated theorems by relating quantities of interest to optimal solutions of the scalar problem.The detailed calculations are given in Sections 6.7 and 6.8.Source: §5 · p. 14

6 Proofs

The proofs simplify the adversarial loss and use optimization identities and a scalar auxiliary optimization to derive uniqueness and a Gaussian expression for adversarial risk. They apply these results to begin the proof of Proposition 3.2 and establish a parameter correspondence for Theorem 3.5.

6.1 Notations

  • The notation section defines the feature data matrix and introduces Fenchel conjugates and Moreau envelopes for convex functions.These definitions support the subsequent loss simplification and auxiliary-optimization derivations.Source: §6.1 · p. 14

6.2 Simplification of the loss

  • The adversarial loss is simplified by decoupling the maximization across observations and solving each resulting trust-region problem.The proof uses the active perturbation constraint, ∥δ_i∥_2 = ε, to identify the multiplier and substitute it back into the loss.Source: §6.2 · pp. 14–15

6.3 Reduction to an auxiliary optimization problem via CGMT

  • Under compact constraints, CGMT relates a primary optimization with bilinear term uᵀXz, convex in z and concave in u, to an auxiliary optimization containing g and h terms.Source: §6.3 · pp. 16–17

6.4 Scalarization of the auxilary optimization problem

  • The scalarization reduces the AO to a limiting objective D in (6.23), using duality, conjugacy, norm-direction optimization, and a Moreau-envelope calculation.The proof notes that pointwise convergence alone is insufficient and invokes local uniform convergence on compact sets to transfer minimax solutions.Source: §6.4 · pp. 17, 20, 22

6.6 Uniqueness of the solution of the AO problem

  • The AO minimizer is unique because its limiting objective is strictly convex in the scalar parameter α after optimization over the remaining variables.The proof obtains strict convexity from the expected Moreau envelope of a convex function, without requiring that function itself to be strictly or strongly convex.Source: §6.6 · p. 22

6.7.1 Proof of Lemma 3.1

  • The adversarial risk is expressed through the estimator’s squared distance from θ0 and noise variance, using Gaussianity and estimator independence from test data.The proof identifies the test prediction error as Gaussian with variance σ^2 + ∥θ̂ − θ0∥_2^2.Source: §6.7.1 · p. 23

6.7.2 Proof of Proposition 3.2

  • The proof of Proposition 3.2 substitutes the standard- and adversarial-risk expressions from Lemma 6.7.1 and scales the objective by p.The supplied passage gives this proof step but no further result.Source: §6.7.2 · p. 23
  • For Proposition 3.2, setting the derivative to zero and rearranging yields the claimed identity.Source: §6.7.2 · pp. 23–24

6.8.1 Proof of Theorem 3.3

  • The proof uses the same auxiliary optimization (AO) to characterize the estimator norm and its asymptotic value.It expresses the norm through the AO-optimal v and γ = ∥q∥ℓ2, then concludes by squaring the resulting relation.Source: §6.8.1 · pp. 25–26

6.8.2 Proof of Corollary 3.4

  • Corollary 3.4 follows from Lemma 3.1 and Theorem 3.3, parts (b) and (c).Source: §6.8.2 · p. 26

6.8.3 Proof of Theorem 3.5

  • A positive ε as a function of λ matches the fixed-point quantities γε and γλ, completing the proof of Theorem 3.5.Matching γε and γλ also matches Aε and Aλ; the equation for ε is quadratic and always has a positive solution.Source: §6.8.3 · p. 29

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

Adversarial training acts as regularization in linear regression, with its effect on standard risk depending on the sample-to-dimension ratio δ. Near the interpolation threshold, regularization is especially important, while for δ > 1 its benefit weakens as ε grows.

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

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

The proof restricts the optimization variables to compact sets to support its analysis. It bounds the estimator's normalized distance from the true parameter and the auxiliary optimizer's norm with high probability.

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

  • The analysis targets the asymptotic distance between the optimal estimator and θ0 by representing the normalized estimator difference as z.The set Sz bounds ∥z∥ℓ2 by a constant chosen above its asymptotic limit.Source: B Proofs that the minimization and… · p. 38
  • The optimization is related asymptotically to a CGMT problem, with the optimal solution norm converging in probability to the same value.The equivalent formulation is identified as (6.6).Source: B Proofs that the minimization and… · p. 38
  • The auxiliary optimizer u* has norm at most Kβ with probability at least 1 − 2e^−cn, for sufficiently large Kβ.This bound supplies the compact restriction on u needed for applying CGMT.Source: B Proofs that the minimization and… · p. 38

C.1 Proof of Lemma 6.1

This proof establishes the conjugate of the function in Lemma 6.1 with respect to z. It proceeds by simplifying the function and applying a conjugate transformation.

C.1 Proof of Lemma 6.1

  • Lemma 6.1 gives the conjugate of the specified function with respect to z.The displayed expression includes terms involving v, ε, and θ0.Source: §C.1 · p. 39
  • The proof first computes the conjugate of a simpler function, then uses the conjugate rule for a composition g(Ax + x0).It applies that rule with x0 = θ0 and A = √p.Source: §C.1 · pp. 39–40
  • The two cases in the proof are combined using z+ = max(z,0).Source: §C.1 · p. 40

C.2 Proof of Lemma 6.2

The proof establishes joint convexity for the function in Lemma 6.2 and for a related perspective function. These properties are shown across the stated parameter groups.

C.2 Proof of Lemma 6.2

  • The function in Lemma 6.2 is jointly convex in (γ, β, τh).Source: §C.2 · p. 41
  • The determinant is computed as an intermediate step in the convexity proof.Source: §C.2 · p. 41
  • The proof also establishes joint convexity of the perspective function in (γ, β, τh).It first identifies joint convexity in (γ, β).Source: §C.2 · p. 41

C.3 Proof of Lemma 6.3

The proof reduces the optimization in Lemma C.3 to a scalar threshold parameter, with the minimizer lying among soft-thresholded versions of the input. It also uses convexity to establish strict convexity of the Moreau envelope in the proof of Lemma 6.3.

C.3 Proof of Lemma 6.3

  • The vector optimization in Lemma C.3 is transformed into an optimization over scalar τ, with a minimizer of the form ST(x;τ) for τ ≥ 0.The passage identifies ST as the soft-thresholding function.Source: §C.3 · p. 42
  • For λ > 1, the objective is convex, so optimality is characterized by zero being a subgradient.Source: §C.3 · p. 42
  • The proof establishes strict convexity of the Moreau envelope in x by combining joint strict convexity with preservation of convexity under partial minimization.It cites [TAH15, Lemma C.5] for the partial-minimization step.Source: §C.3 · p. 43

C.4 Proof of Lemma 6.4

The proof of Lemma 6.4 evaluates expressions for a Gaussian vector and analyzes their dependence on a scalar threshold τ. It identifies τ = 0 as the minimum in one case and locates the minimum at a turning point in another.

C.4 Proof of Lemma 6.4

  • For a Gaussian vector w distributed as N(0,ω²I_n), the lemma states identities under additional assumptions not reproduced in the passage.Source: §C.4 · p. 43
  • The proof invokes the law of large numbers for the first identity and rewrites an expression using erf = 1 − erfc.Source: §C.4 · pp. 44–45
  • The derivative analysis treats separately the cases where only the first term is active and where both terms are active.Source: §C.4 · p. 45
  • When the function is increasing for τ ∈ [0,+∞), its minimum occurs at τ = 0.Source: §C.4 · p. 45
  • In the other case, the function first decreases and then increases, so its minimum occurs at a turning point.The passage introduces a condition for that point but does not state it here.Source: §C.4 · p. 45

Related papers

Loading 2002.10477v1…