Regularization properties of adversarially-trained linear regression
Antônio H. Ribeiro Dave Zachariah Francis Bach Thomas B. Schön
State-of-the-art machine learning models can be vulnerable to very small
input perturbations that are adversarially constructed. Adversarial training is
an effective approach to defend against it. Formulated as a min-max problem, it
searches for the best solution when the training data were corrupted by the
worst-case attacks. Linear models are among the simple models where
vulnerabilities can be observed and are the focus of our study. In this case,
adversarial training leads to a convex optimization problem which can be
formulated as the minimization of a finite sum. We provide a comparative
analysis between the solution of adversarial training in linear regression and
other regularization methods. Our main findings are that: (A) Adversarial
training yields the minimum-norm interpolating solution in the
overparameterized regime (more parameters than data), as long as the maximum
disturbance radius is smaller than a threshold. And, conversely, the
minimum-norm interpolator is the solution to adversarial training with a given
radius. (B) Adversarial training can be equivalent to parameter shrinking
methods (ridge regression and Lasso). This happens in the underparametrized
region, for an appropriate choice of adversarial radius and zero-mean
symmetrically distributed covariates. (C) For $\ell_\infty$-adversarial
training -- as in square-root Lasso -- the choice of adversarial radius for
optimal bounds does not depend on the additive noise variance. We confirm our
theoretical findings with numerical examples.