# CTL++: Evaluating Generalization on Never-Seen Compositional Patterns of
Known Functions, and Compatibility of Neural Representations

Róbert Csordás1 Kazuki Irie1 Jürgen Schmidhuber1,2
1The Swiss AI Lab IDSIA, USI & SUPSI, Lugano, Switzerland
2AI Initiative, KAUST, Thuwal, Saudi Arabia
{robert, kazuki<EMAIL_ADDRESS>
###### Abstract

Well-designed diagnostic tasks have played a key role in studying the failure
of neural nets (NNs) to generalize systematically. Famous examples include
SCAN and Compositional Table Lookup (CTL). Here we introduce CTL++, a new
diagnostic dataset based on compositions of unary symbolic functions. While
the original CTL is used to test length generalization or productivity, CTL++
is designed to test systematicity of NNs, that is, their capability to
generalize to unseen compositions of known functions. CTL++ splits functions
into groups and tests performance on group elements composed in a way not seen
during training. We show that recent CTL-solving Transformer variants fail on
CTL++. The simplicity of the task design allows for fine-grained control of
task difficulty, as well as many insightful analyses. For example, we measure
how much overlap between groups is needed by tested NNs for learning to
compose. We also visualize how learned symbol representations in outputs of
functions from different groups are compatible in case of success but not in
case of failure. These results provide insights into failure cases reported on
more complex compositions in the natural language domain. Our code is
public.111https://github.com/robertcsordas/ctlpp

##  1 Introduction

Neural networks (NNs) should ideally learn from training data to generalize
systematically (Fodor et al., 1988), by learning generally applicable rules
instead of pure pattern matching. Existing NNs, however, typically don’t. For
example, in the context of sequence processing NNs, superficial differences
between training and test distributions, e.g., with respect to input sequence
length or unseen input/word combinations, are enough to prevent current NNs
from generalizing (Lake and Baroni, 2018). Training on a large amounts of data
might alleviate the problem, but it is infeasible to cover all possible
lengths and combinations.

Indeed, while large language models trained on a large amounts of data have
obtained impressive results (Brown et al., 2020), they often fail on tasks
requiring simple algorithmic reasoning, e.g., simple arithmetics (Rae et al.,
2021). A promising way to achieve systematic generalization is to make NNs
more compositional (Schmidhuber, 1990), by reflecting and exploiting the
hierarchical structure of many problems either within some NN’s learned
weights, or through tailored NN architectures. For example, recent work by
Csordás et al. (2022) proposes architectural modifications to the standard
Transformer (Vaswani et al., 2017) motivated by the principles of
compositionality. The resulting Neural Data Router (NDR) exhibits strong
length generalization or productivity on representative datasets such as
Compositional Table Lookup (CTL; Liska et al. (2018); Hupkes et al. (2019)).

The focus of the present work is on systematicity: the capability to
generalize to unseen compositions of known functions/words. That is crucial
for learning to process natural language or to reason on algorithmic problems
without an excessive amount of training examples. Some of the existing
benchmarks (such as COGS (Kim and Linzen, 2020) and PCFG (Hupkes et al.,
2020)) are almost solvable by plain NNs with careful tuning (Csordás et al.,
2021), while others, such as CFQ (Keysers et al., 2020), are much harder. A
recent analysis of CFQ by Bogin et al. (2022) suggests that the difficult
examples have a common characteristic: they contain some local structures
(describable by parse trees) which are not present in the training examples.
These findings provide hints for constructing both challenging and intuitive
(simple to define and analyze) diagnostic tasks for testing systematicity. We
propose CTL++, a new diagnostic dataset building upon CTL. CTL++ is basically
as simple as the original CTL in terms of task definition, but adds the core
challenge of compositional generalization absent in CTL. Such simplicity
allows for insightful analyses: one low-level reason for the failure to
generalize compositionally appears to be the failure to learn functions whose
outputs are symbol representations compatible with inputs of other learned
neural functions. We will visualize this.

Well-designed diagnostic datasets have historically contributed to studies of
systematic generalization in NNs. Our CTL++ strives to continue this
tradition.

##  2 Original CTL

Our new task (Sec. 3) is based on the CTL task (Liska et al., 2018; Hupkes et
al., 2019; Dubois et al., 2020) whose examples consist of compositions of
bijective unary functions defined over a set of symbols. Each example in the
original CTL is defined by one input symbol and a list of functions to be
applied sequentially, i.e., the first function is applied to the input symbol
and the resulting output becomes the input to the second function, and so
forth. The functions are bijective and randomly generated. The original CTL
uses eight different symbols. We represent each symbol by a natural number,
and each function by a letter. For example, ‘d a b 3’ corresponds to the
expression $d(a(b(3)))$. The model has to predict the corresponding output
symbol (this can be viewed as a sequence classification task). When the
train/test distributions are independent and identically distributed (IID),
even the basic Transformer achieves perfect test accuracy (Csordás et al.,
2022). The task becomes more interesting when test examples are longer than
training examples. In such a productivity split, which is the common setting
of the original CTL (Dubois et al., 2020; Csordás et al., 2022), standard
Transformers fail, while NDR and bi-directional LSTM work perfectly.

##  3 Extensions for Systematicity: CTL++

To introduce a systematicity split to the CTL framework, we divide the set of
functions into disjoint groups and restrict the sampling process such that
some patterns of compositions between group elements are never sampled for
training, only for testing. Based on this simple principle, we derive three
variations of CTL++. They differ from each other in terms of compositional
patterns used for testing (excluded from training) as described below. We’ll
also visualize the difference using sampling graphs in which the nodes
represent the groups, and the edges specify possible compositional patterns.
The colors of the edges reflect when the edges are used: black for both
training and testing,  blue for training, and  red only for testing.

#### Variation ‘A’ (as in ‘Alternating’).

Here functions are divided in groups $G_{a}$ and $G_{b}$. During training,
successively composed functions are sampled from different groups in an
alternating way—i.e., successive functions cannot be from the same group.
During testing, however, only functions from the same group can be composed.
The sampling graph is shown in Fig. 1. Importantly, the single function
applications are part of the training set, to allow the model to learn common
input/output symbol representations for the interface between different
groups.

IN$G_{a}$$G_{b}$OUT Figure 1: Sampling graph for variant ‘A.’

#### Variation ‘R’ (as in ‘Repeating’).

This variant is the complement of variation ‘A’ above. To get a training
example, either $G_{a}$ or $G_{b}$ is sampled, and all functions in that
example are sampled from that same group for the whole sequence. In test
examples, functions are sampled in an alternating way. There is thus no
exchange of information between the groups, except for the shared input
embeddings and the output classification weight matrix. The sampling graph is
like in Fig. 1 for ‘A’ except that blue edges should become red and vice versa
(see Fig. 5 in the appendix).

#### Variation ‘S’ (as in ‘Staged’).

In this variant, functions are divided into five disjoint groups: $G_{a1}$,
$G_{a2}$, $G_{b1}$, $G_{b2}$ and $G_{o}$. As indicated by the indices, each
group belongs to one of the two paths (‘a’ or ‘b’) and one of the two stages
(‘1’ or ‘2’), except for $G_{o}$ which only belongs to stage ‘2’ shared
between paths ‘a’ and ‘b’ during training. The corresponding sampling graph is
shown in Fig. 2. To get a training example, we sample an integer $K$ which
defines the sequence length as $2K+1$, and iterate the following process for
$k\in[0,..,K]$ and $i=2k$: we first sample a path $p\in\\{a,b\\}$ and then a
function $f_{i}$ from $G_{p1}$ and a function $f_{i+1}$ from $G_{p2}\cup
G_{o}$. Each example always contains an even number of functions, and no
isolated single function application is part of training, unlike in the
previous two variants. For testing, we sample a path $p\in\\{a,b\\}$ and a
function $f_{i}$ from $G_{p1}$, but then sample a function $f_{i+1}$ from
$G_{\\{a,b\\}\setminus\\{p\\}2}$, which results in a compositional pattern
never seen during training.

The unique feature of this variant is the use of two stages: as can be seen in
Fig. 2, during training, given a path $p\in\\{a,b\\}$, outputs of any
functions belonging to $G_{p1}$ are only observed by the functions belonging
to $G_{p2}$, i.e., the stage ‘2’ group belonging to the same path $p$, or
$G_{o}$. Hence, if $G_{o}=\emptyset$, the model has no incentive to learn
common representations for the interface between $G_{a1}$ and $G_{b1}$: to
solve the training examples, it suffices to learn output representations of
$G_{a1}$ which are ‘compatible’ with the input representations of $G_{a2}$;
similarly for $G_{b1}$ and $G_{b2}$. There is no reason for outputs of
$G_{a1}$ to be compatible with the inputs of $G_{b2}$ (analogously for
$G_{b1}$ and $G_{a2}$) which is required at test time. The size of $G_{o}$ is
our first parameter for controlling task difficulty (the y-axis of Fig. 4
which we will present later).

We introduce further restrictions: for each function $f\in G_{o}$, we define a
set of symbols $S^{f}_{a}$ for $G_{a1}$ (and $S^{f}_{b}$ for $G_{b1}$), and we
only allow for sampling $f$ if the output symbol of function from $G_{a1}$ (or
$G_{b1}$) belongs to $S^{f}_{a}$ (or $S^{f}_{b}$). This allows for defining
another control parameter: the number of overlapping symbols between
$S^{f}_{a}$ and $S^{f}_{b}$ (same for all $f$; the x-axis of Fig. 4). Note
that we ensure that the union of shared symbols defined for functions in
$G_{o}$ cover all possible symbols. This might not be the case in a more
realistic scenario, but as we’ll see, the standard models already struggle in
this setting. By controlling these two parameters, we precisely control the
degree of overlap offered by $G_{o}$ in terms of both the number of functions
and symbols. Ideal models should be “sample efficient” in terms of this
overlap, since we cannot expect the training set to contain all combinations
of such overlaps in a practical scenario with semantically rich domains such
as natural language.

IN•$G_{a1}$$G_{b1}$$G_{a2}$$G_{o}$$G_{b2}$•OUT Figure 2: Sampling graph for
Variant ‘S’

##  4 Results

We evaluate standard CTL-tested models on the new CTL++ task, including: the
Transformer (Vaswani et al., 2017) with shared layers (Dehghani et al., 2019),
the neural data router (NDR) (Csordás et al., 2022), and the bi-directional
LSTM (Hochreiter and Schmidhuber, 1997; Schuster and Paliwal, 1997; Graves et
al., 2005). Recall that both NDR and bi-directional LSTM are reported to
perfectly solve the original CTL’s length generalization split (Csordás et
al., 2022), unlike the Transformer. Further experimental details can be found
in Appendix A.

Table 1: Results on the task variants ‘A’ and ‘R.’ Mean and standard deviation are computed using 25 seeds. Model | Dataset | Accuracy
---|---|---
IID | OOD
Bi-LSTM | A | $1.00\pm 0.00$ | $0.95\pm 0.03$
R | $1.00\pm 0.00$ | $1.00\pm 0.00$
Transformer | A | $1.00\pm 0.00$ | $0.21\pm 0.09$
R | $1.00\pm 0.00$ | $0.75\pm 0.25$
NDR | A | $1.00\pm 0.00$ | $0.34\pm 0.26$
R | $1.00\pm 0.01$ | $0.75\pm 0.27$

###  4.1 Results on Variants ‘A’ and ‘R’

Table 1 shows the performance overview for ‘A’ and ‘R.’ The OOD (out-of-
distribution) column indicates the train/test data sampling processes
described above. As a reference, we also report the IID cases where the
training example sampling graph is also used for testing. Our initial
expectation was that the pressure from shared input/output embeddings is
sufficient for these models to learn common symbol representations for all
functions. However, we observe that only the bi-LSTM solves these tasks
consistently across seeds. Interestingly, the NDR, which perfectly performs on
the length generalization split of CTL and beyond (Csordás et al., 2022),
performs poorly on both the ‘A’ and ‘R’ variants of CTL++. Tested with 25
seeds, only 32% of the seeds (out of 25) achieve over 95% accuracy for NDR on
‘R’ (20% for the standard Transformer). The success rate is 0% for the ‘A’
variant222‘A’ turns out to be harder than ‘R.’ We speculate that in both ‘A’
and ‘R’, given that the training set contains single function applications
with shared input/ouput embeddings, the learned symbol representation of all
functions should be compatible with each other to some extent, but with some
“deviation” from perfect compatibility in case of failure. Such “deviations”
might accumulate in case of ‘A’ where we sample all functions in each sequence
from a single group at test time.. These simple tasks thus turn out to be good
first diagnostic tasks for testing systematicity.

(a) Example for symbol ‘6’. Perfect clustering w.r.t. the function groups is
observed.

(b) Example for symbol ‘3’. Partial clustering w.r.t. the function groups is
observed.

Figure 3: Cosine similarity of output representations of different functions
representing the same symbol for the NDR with a seed that fails on ‘R.’

#### Analysis.

The small input/output space of this task allows for an exhaustive analysis of
the learned symbol representations. Specifically, given an output symbol
$s^{\prime}$, for each function $f\in G_{a}\cup G_{b}$, we can find a unique
input symbol $s$ such that $s^{\prime}=f(s)$ (because all functions defined
for this task are bijective). Hence, for a fixed symbol $s^{\prime}$, for all
functions $f$, we can extract the learned vector representation of this symbol
$s^{\prime}$ at the output of $f$ as the vector of the layer beneath the final
classification layer when we feed ‘$f$ $s$’ to the network. Then we can
compare the extracted representations (of a fixed symbol for different
functions) by computing their cosine similarities.

Here we compare representations learned with successful/failed seeds for NDR
in variation ‘R.’ Fig. 3a and 3b show the results for two different (output)
symbols ‘6’ and ‘3’ from the same failed seed. In both cases we observe two
clusters ($C_{1}$ and $C_{2}$): two separate/different representations are
learned for the same symbol (by abuse of notation, we also refer to the
corresponding representations as $C_{1}$ and $C_{2}$). In the case of symbol
‘6’ in Fig. 3a, we observe perfect/strict clustering in line with the group of
the applied function; $C_{1}$ and $C_{2}$ are representations of symbol ‘6‘
learned by functions belonging to $G_{a}$ and $G_{b}$ respectively. This is
problematic since functions in $G_{a}$ never see symbol ‘6’ represented as
$C_{2}$ during training (analogously for functions in $G_{b}$ with
representation $C_{1}$). As a consequence, during testing, when a function
$f_{a}\in G_{a}$ is applied after a function $f_{b}\in G_{b}$, $f_{b}$ may
output symbol ‘6’ represented as $C_{2}$, and pass it to $f_{a}$, but in
principle, $f_{a}$ can not “understand/interpret” $C_{2}$ as representing
symbol ‘6.’ This naturally prevents cross-group generalization. In the case of
symbol ‘3’ shown in Fig. 3b, some of the functions yield the same symbol
representations as certain functions from the other group (see the cluster
$C_{2}$ at the lower right: a good trend), but we still have a small cluster
($C_{1}$ at the upper left) consistent only among elements of $G_{a}$. Hence,
cross-group generalization can still fail because the functions in $G_{b}$
never see symbol ‘3’ represented as $C_{1}$ during training but only during
testing. In contrast, for successful seeds, we do not observe any of these
clusters for any symbols (see Fig. 9 in the appendix). A single representation
shared across all functions is learned for each symbol. Further quantitative
analysis can be found in Appendix B.

Figure 4: Test accuracy of NDR on the ‘S’ variant. The total number of symbols
is 8, and the number of functions is 32. The y-axis shows the number of
overlapping functions, while the x-axis shows the number of symbols shared
between two groups for each function in $G_{o}$ during training (Sec. 3).
Results for the Transformer and LSTM are reported in the appendix (Figs. 7 and
8).

###  4.2 Results of Staged Variant ‘S’

As described in Sec. 3, variant ‘S’ is designed to evaluate models at
different task difficulty levels determined by the number of overlapping
functions and symbols during training. Fig. 4 shows the corresponding
performance overview for NDR. The overall picture is similar for bi-LSTM and
Transformer (see Figs. 7 and 8 in the appendix). We observe that to achieve
100% accuracy, half of the possible functions should overlap (16/32), as well
as most of the possible symbols seen for each function (6/8). This implies an
unrealistically large amount of data for real world scenarios, where the
“functions” might correspond to more complex operations with multiple input
arguments (as in the CFQ case). This calls for developing approaches that
achieve higher accuracy in the upper left part of Fig. 4.

##  5 Conclusion

Motivated by the historically crucial role of diagnostic datasets for research
on systematic generalization of NNs, we propose a new dataset called CTL++.
Unlike the classic CTL dataset, typically used for testing productivity, CTL++
is designed for testing systematicity. We propose three variants, ‘A,’ ‘R,’
and ‘S.’ Despite their simplicity, even the CTL-solving Transformer variant
fails on ‘A’ and ‘R.’ Using ‘S,’ we show that existing approaches require
impractically large amounts of examples to achieve perfect compositional
generalization. The small task size allows for conducting exhaustive
visualizations of (in)compatibility of learned symbol representations in
outputs of functions with inputs of subsequent functions. Of course, the
ultimate goal is to go beyond just solving CTL++. Nevertheless, we hope CTL++
will become one of the standard diagnostic datasets for testing systematicity
of NNs.

## Limitations

Achieving 100% on this dataset may be a necessary condition for NNs capable of
systematic generalization, but certainly not a sufficient one. In practice,
there may be many reasons which prevent NNs from generalizing systematically
in other tasks or more generally on real world data. Compare the original CTL
dataset for evaluating productivity: Csordás et al. (2022) show that some
models that achieve 100% on CTL still fail in other tasks such as ListOps.
This is why we refer to CTL++ as a simple diagnostic dataset for testing
systematicity of NNs. Nevertheless, it allows for uncovering certain important
failure modes of NNs.

## Acknowledgments

This research was partially funded by ERC Advanced grant no: 742870, project
AlgoRNN, and by Swiss National Science Foundation grant no: 200021_192356,
project NEUSYM. We are thankful for hardware donations from NVIDIA and IBM.
The resources used for this work were partially provided by Swiss National
Supercomputing Centre (CSCS) project s1154.

## References

  * Ba et al. (2016) Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. 2016.  Layer normalization.  _Preprint arXiv:1607.06450_.
  * Bogin et al. (2022) Ben Bogin, Shivanshu Gupta, and Jonathan Berant. 2022.  Unobserved local structures make compositional generalization hard.  _Preprint arXiv:2201.05899_.
  * Brown et al. (2020) Tom B Brown et al. 2020.  Language models are few-shot learners.  In _Proc. Advances in Neural Information Processing Systems (NeurIPS)_ , Virtual only.
  * Csordás et al. (2021) Róbert Csordás, Kazuki Irie, and Jürgen Schmidhuber. 2021.  The devil is in the detail: Simple tricks improve systematic generalization of Transformers.  In _Proc. Conf. on Empirical Methods in Natural Language Processing (EMNLP)_ , Punta Cana, Dominican Republic.
  * Csordás et al. (2022) Róbert Csordás, Kazuki Irie, and Jürgen Schmidhuber. 2022.  The neural data router: Adaptive control flow in transformers improves systematic generalization.  In _Int. Conf. on Learning Representations (ICLR)_ , Virtual only.
  * Dai et al. (2019) Zihang Dai, Zhilin Yang, Yiming Yang, Jaime G Carbonell, Quoc Le, and Ruslan Salakhutdinov. 2019.  Transformer-XL: Attentive language models beyond a fixed-length context.  In _Proc. Association for Computational Linguistics (ACL)_ , pages 2978–2988, Florence, Italy.
  * Dehghani et al. (2019) Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Lukasz Kaiser. 2019.  Universal Transformers.  In _Int. Conf. on Learning Representations (ICLR)_ , New Orleans, LA, USA.
  * Dubois et al. (2020) Yann Dubois, Gautier Dagan, Dieuwke Hupkes, and Elia Bruni. 2020.  Location attention for extrapolation to longer sequences.  In _Proc. Association for Computational Linguistics (ACL)_ , pages 403–413, Virtual only.
  * Fodor et al. (1988) Jerry A Fodor, Zenon W Pylyshyn, et al. 1988.  Connectionism and cognitive architecture: A critical analysis.  _Cognition_ , 28(1-2):3–71.
  * Graves et al. (2005) Alex Graves, Santiago Fernández, and Jürgen Schmidhuber. 2005.  Bidirectional LSTM networks for improved phoneme classification and recognition.  In _Proc. Int. Conf. on Artificial Neural Networks (ICANN)_ , pages 799–804, Warsaw, Poland.
  * Hanson (1990) Stephen José Hanson. 1990.  A stochastic version of the delta rule.  _Physica D: Nonlinear Phenomena_ , 42(1-3):265–272.
  * Hendrycks and Gimpel (2016) Dan Hendrycks and Kevin Gimpel. 2016.  Gaussian error linear units (GELUs).  _Preprint arXiv:1606.08415_.
  * Hochreiter and Schmidhuber (1997) Sepp Hochreiter and Jürgen Schmidhuber. 1997.  Long short-term memory.  _Neural computation_ , pages 1735–1780.
  * Hupkes et al. (2020) Dieuwke Hupkes, Verna Dankers, Mathijs Mul, and Elia Bruni. 2020.  Compositionality decomposed: How do neural networks generalise?  _Journal of Artificial Intelligence Research_ , pages 757–795.
  * Hupkes et al. (2019) Dieuwke Hupkes, Anand Singh, Kris Korrel, German Kruszewski, and Elia Bruni. 2019\.  Learning compositionally through attentive guidance.  In _Proc. Int. Conf. on Computational Linguistics and Intelligent Text Processing_ , La Rochelle, France.
  * Keysers et al. (2020) Daniel Keysers, Nathanael Schärli, Nathan Scales, Hylke Buisman, Daniel Furrer, Sergii Kashubin, Nikola Momchev, Danila Sinopalnikov, Lukasz Stafiniak, Tibor Tihon, Dmitry Tsarkov, Xiao Wang, Marc van Zee, and Olivier Bousquet. 2020.  Measuring compositional generalization: A comprehensive method on realistic data.  In _Int. Conf. on Learning Representations (ICLR)_ , Addis Ababa, Ethiopia.
  * Kim and Linzen (2020) Najoung Kim and Tal Linzen. 2020.  COGS: A compositional generalization challenge based on semantic interpretation.  In _Proc. Conf. on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 9087–9105, Virtual only.
  * Lake and Baroni (2018) Brenden M. Lake and Marco Baroni. 2018.  Generalization without systematicity: On the compositional skills of sequence-to-sequence recurrent networks.  In _Proc. Int. Conf. on Machine Learning (ICML)_ , pages 2873–2882, Stockholm, Sweden.
  * Liska et al. (2018) Adam Liska, Germán Kruszewski, and Marco Baroni. 2018.  Memorize or generalize? Searching for a compositional RNN in a haystack.  In _AEGAP Workshop ICML_ , Stockholm, Sweden.
  * Loshchilov and Hutter (2019) Ilya Loshchilov and Frank Hutter. 2019.  Decoupled weight decay regularization.  In _Int. Conf. on Learning Representations (ICLR)_ , New Orleans, LA, USA.
  * Paszke et al. (2019) Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. 2019.  Pytorch: An imperative style, high-performance deep learning library.  In _Proc. Advances in Neural Information Processing Systems (NeurIPS)_ , pages 8024–8035, Vancouver, Canada.
  * Rae et al. (2021) Jack W Rae, Sebastian Borgeaud, Trevor Cai, Katie Millican, Jordan Hoffmann, Francis Song, John Aslanides, Sarah Henderson, Roman Ring, Susannah Young, et al. 2021.  Scaling language models: Methods, analysis & insights from training gopher.  _Preprint arXiv:2112.11446_.
  * Schmidhuber (1990) Jürgen Schmidhuber. 1990.  Towards compositional learning in dynamic networks.  Technical Report FKI-129-90, Institut für Informatik, Technische Universität München.
  * Schuster and Paliwal (1997) Mike Schuster and Kuldip K Paliwal. 1997.  Bidirectional recurrent neural networks.  _IEEE Transactions on Signal Processing_ , 45(11):2673–2681.
  * Srivastava et al. (2014) Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. 2014.  Dropout: a simple way to prevent neural networks from overfitting.  _The Journal of Machine Learning Research_ , 15(1):1929–1958.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  In _Proc. Advances in Neural Information Processing Systems (NIPS)_ , pages 5998–6008, Long Beach, CA, USA.

IN$G_{a}$$G_{b}$OUT Figure 5: Sampling graph for variant ‘R.’

##  Appendix A Experimental Details

###  A.1 Modified NDR architecture

We experimentally found some architectural modifications to the original NDR
(Csordás et al., 2022) that yield faster convergence and produce more stable
results than the original architecture. Here we describe our modifications. We
use the GELU activation function (Hendrycks and Gimpel, 2016) instead of ReLU,
and a residual connection in the feedforward data path. Concretely, Eq. 5 in
Csordás et al. (2022) is replaced by Eq. 1 below, while Eq. 2 is replaced by
Eq. 2 below. We do not use any dropout in Eq. 1.

$\displaystyle\operatorname{FFN}({\bm{x}})$
$\displaystyle={\bm{W}}_{2}\operatorname{GELU}({\bm{W}}_{1}{\bm{x}}+{\bm{b}}_{1})+{\bm{b}}_{2}$
(1) $\displaystyle{\bm{u}}^{(i,t+1)}$
$\displaystyle=\operatorname{LN}(\operatorname{FFN}^{\textrm{data}}({\bm{a}}^{(i,t+1)})+{\bm{a}}^{(i,t+1)})$
(2)

where $\operatorname{LN}$ denotes layer normalization (Ba et al., 2016).

###  A.2 Hyperparameters

#### Dataset.

The train set in all of our experiments consists of 300k examples. The maximum
number of composed functions is 6. We make sure that we obtain an equal number
of samples for different lengths whenever possible (in some cases this is
impossible because by construction, there are fewer short examples than long
ones). In ‘A’ and ‘R’ variants, single functions are always part of the
training set with all possible symbols. There are in total 8 symbols and 32
functions. All samples are presented in a right-to-left manner (e.g. “c b a
3”). The IID and OOD test sets contain 1000 examples in all cases. Our code
generates the data for given dataset specifications (number of functions etc).
The seed for data generation is fixed.

#### Training.

Unless noted otherwise, for all of our models, we use a batch size of 512, a
learning rate of 0.00015, and a dropout rate (Hanson, 1990; Srivastava et al.,
2014) of 0.5. We also use a linear learning rate warmup for the first 500
iterations. We use PyTorch’s (Paszke et al., 2019) adaptive mixed precision
and bin the batches by length for greater efficiency. We use the AdamW
optimizer (Loshchilov and Hutter, 2019). The NDR and bi-LSTM is trained for
80k and the Transformers for 300k iterations. We find the standard Transformer
to be very unstable even in the IID setting. In fact, for Table 1, unlike
other models trained for 25 seeds, we train the Transformer for 50 seeds: the
25 seeds used to report mean and std in Table 1 are those among 50 which
converged within 300k training iterations. For Figs. 4, 7 and 8, five seeds
were used for each configuration. All of our models are trained on a single
P100 GPU. The corresponding number of parameters, training steps and average
wall-clock time is shown in Table 2.

Table 2: Training details for different models. Runtime is in hour:min. Model | Num. params | Num. steps | Runtime
---|---|---|---
Bi-LSTM | 408k | 80k | 0:18
Transformer | 672k | 300k | 3:37
NDR | 679k | 80k | 1:22

#### Models.

For Transformer and NDR, we use 8 layers, and 4 heads. NDR uses a gate dropout
of 0.1, state size of 256, feedforward size of 1024. Transformers use a state
size of 128 and feedforward size of 512, layer sharing (Dehghani et al.,
2019), and Transformer-XL-style (Dai et al., 2019) relative positional
encoding. For bidirectional LSTM, we use 1 layer with 256 units (128 per
direction). The gradient is clipped to max norm of 1 for NDR and 5 for
Transformer and LSTM. Transformers use a weight decay of $0.0025$.

##  Appendix B More Analyses and Plots

###  B.1 Quantitative Analysis of Incompatibility

Here we provide additional results on the analysis of Sec. 4.1 conducted for
variant ‘R.’ To quantify the correlation between the clusters ($C_{1}$ and
$C_{2}$) identified in Fig. 3b and the compatibility of representations, we
measured the proportion of correct output classifications, by taking the first
function from a given cluster and the second one from a given group, for all
pairs of functions for each pair of the form (cluster, group). The results are
shown in Fig. 6. Fig. 6a shows that the first cluster $C_{1}$ is effectively
compatible only with functions from $G_{a}$, while the second one $C_{2}$
works with both $G_{a}$ and $G_{b}$, as predicted by Fig. 3b. Fig. 6b shows
the same analysis, but uses the groups to define the cluster. As predicted by
Fig. 3b, only roughly half of the functions from $G_{a}$ generate
representations compatible with $G_{b}$, while all representations generated
by functions in $G_{b}$ are compatible with all in $G_{a}$.

(a) Performance of each cluster vs. each group

(b) Performance for each pair of groups

Figure 6: Accuracy measured after two successive function applications, for
the symbol corresponding to Fig. 3b. (a) shows the proportion of correct
outputs when the first function is taken from a given cluster (y-axis), and
the second from a given group (x-axis). Clusters are shown in the main
diagonal of Fig. 3b. (b) is analogous to (a) but using groups as clusters.

###  B.2 Representative Cosine Similarities

Here we show additional visualizations similar to those of Fig. 3. In Fig. 9
and 10, we plot cosine similarities of functional outputs for all possible
symbols for successful and failed seeds of NDR on variant ‘R.’ The symbol
representations are taken from the layer right below the final classification
layer. They are representative examples; the observation holds over all seeds
we inspected. Fig. 11 shows a similar example for variant ‘A.’

Figure 7: Final test performance of the Transformer on variant ‘S.’ The
behavior is similar to the one shown in Fig. 4. For lower numbers of shared
functions, performance is worse. Interestingly, however, with 16 shared
functions, it outperforms NDR. Figure 8: Final test performance of bi-
directional LSTM on variant ‘S.’ The behavior is similar to the one shown in
Fig. 4. For lower numbers of shared functions, the performance is worse.
Interestingly, however, with 16 shared functions, it significantly
underperforms NDR. Figure 9: Symbol cosine similarity between different
functions for NDR on variant ‘R.’ A representative example from a seed that
performs perfectly on unseen compositions. Functions indicated by red belong
to $G_{a}$, by blue to $G_{b}$. Figure 10: Symbol cosine similarity between
different functions for NDR on variant ‘R.’ A representative example from a
seed that performs poorly on unseen compositions. Functions indicated by red
belong to $G_{a}$, by blue to $G_{b}$. Figure 11: Symbol cosine similarity
between different functions for NDR on variant ‘A.’ A representative example
from a seed that performs poorly on unseen compositions. Functions indicated
by red belong to $G_{a}$, by blue to $G_{b}$.


Surprises in adversarially-trained linear regression

Antônio H. Ribeiro Dave Zachariah Thomas B. Schön

Uppsala University Uppsala University Uppsala University

###### Abstract

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 such examples. It is formulated as a min-
max problem, searching for the best solution when the training data was
corrupted by the worst-case attacks. For linear regression problems,
adversarial training can be formulated as a convex problem. We use this
reformulation to make two technical contributions: First, we formulate the
training problem as an instance of robust regression to reveal its connection
to parameter-shrinking methods, specifically that $\ell_{\infty}$-adversarial
training produces sparse solutions. Secondly, we study adversarial training in
the overparameterized regime, i.e. when there are more parameters than data.
We prove that adversarial training with small disturbances gives the solution
with the minimum-norm that interpolates the training data. Ridge regression
and lasso approximate such interpolating solutions as their regularization
parameter vanishes. By contrast, for adversarial training, the transition into
the interpolation regime is abrupt and for non-zero values of disturbance.
This result is proved and illustrated with numerical examples.

##  1 Introduction

Robustness is a fundamental goal in machine learning that often surpasses that
of achieving high performance in a controlled scenario. Indeed, the
brittleness of modern machine learning models presents a challenge to their
deployment in critical situations. The framework of adversarial attacks has
generated striking examples of their vulnerability, where very small input
perturbations can cause a substantial performance drop in otherwise state-of-
the-art models, see for instance [1, 2, 3, 4, 5, 6]. It considers inputs
contaminated with disturbances deliberately chosen to maximize the model
error.

While a lot of current research focuses on adversarial examples for deep
learning models, there is a growing body of work [7, 8, 9, 10, 11] that study
fundamental properties of adversarial attacks in simpler, linear models. There
is a sound reason for this focus: linear models allow for analytical analysis
while still reproducing phenomena of interest. Indeed, while there was initial
speculation that the highly nonlinear nature of deep neural networks was the
cause of its vulnerabilities to adversarial attacks [1] the idea was later
dismissed and the vulnerabilities can be observed in purely linear settings
[2, 12].

Adversarial training [13] is one of the most effective approaches for deep
learning models to defend against adversarial attacks. The topic has been
extensively studied by the research community, see e.g. [14, 13, 15]. The idea
is straightforward: It considers the situation where the model is trained
training on samples that have been modified by an adversary. The hope is that
the model will be more robust when faced with new adversarially perturbed
samples.

Mathematically, adversarial training is formulated as a min-max problem,
searching for the best solution to the worst-case attacks. In the case of
linear regression, consider a training dataset
$\\{(\boldsymbol{x}_{i},y_{i})\\}_{i=1}^{n}$ consisting of $n$ datapoints of
dimension $\mathbb{R}^{m}\times\mathbb{R}$. Let $\boldsymbol{\beta}$ denote
the unknown parameters. Adversarial training now corresponds to solving the
optimization problem

$\min_{\boldsymbol{\beta}}~{}\frac{1}{n}\sum_{i=1}^{n}{\max_{\|\boldsymbol{\Delta
x}_{i}\|_{\infty}\leq\delta}(y_{i}-(\boldsymbol{x}_{i}+\boldsymbol{\Delta
x}_{i})^{\mathsf{T}}\boldsymbol{\beta})^{2}}$ (1)

(a) lasso regression (b) $\ell_{\infty}$-adversarial training

(c) ridge regression (d) $\ell_{2}$-adversarial training

Figure 1: Regularization paths. On the horizontal axis, we give the inverse of
the regularization parameter (in log scale). On the vertical axis we show the
coefficients of the learned linear model.

Restricting the analysis to regression allows for some important
simplifications. Indeed, it was recently noted [12, 16, 8] that for linear
regression, adversarial training can be formulated as a quadratic problem. We
will refer to this as the dual formulation,

$\min_{\boldsymbol{\beta}}~{}\frac{1}{n}\sum_{i=1}^{n}\left(|y_{i}-\boldsymbol{x}_{i}^{\mathsf{T}}\boldsymbol{\beta}|+\delta\|\boldsymbol{\beta}\|_{1}\right)^{2}.$

The function minimized in the above problem is equivalent to (1) and is easily
shown to convex. This fact enables us to connect it to other well-known
parameter-shrinking regularization methods. For instance, it hints at
similarities between adversarial training constrained to the region
$\\{\boldsymbol{\Delta x}:\|\boldsymbol{\Delta x}\|_{\infty}\leq\delta\\}$ and
lasso. Fig.1 (a)-(b) show experiments comparing the solutions and suggest that
this similarity indeed exists.

The dual formulation above is presented in [12, 16, 8] with the focus of
analysing the generalization properties of adversarial attacks. This paper has
a different focus: we are interested in the study of the solution to the
adversarial training problem from an _optimization perspective_. We show that
significant insight can be gained into the problem from such a perspective.

###  1.1 Setup

More generally, we consider the case where the adversarial disturbance is
bounded to a region that can be written as $\\{\boldsymbol{\Delta
x}:\|\boldsymbol{\Delta x}\|_{p}\leq\delta\\}$. Here $\|\cdot\|_{p}$ denotes
the $\ell_{p}$ norm.111if $\boldsymbol{a}\in\mathbb{R}^{n}$ $p>1$ then
$\|\boldsymbol{a}\|_{p}=\left(\sum_{i=1}^{n}|\boldsymbol{a}_{i}|^{p}\right)^{\frac{1}{p}}$
and, for $p=\infty$, we define $\|\boldsymbol{a}\|_{\infty}=\max_{1\leq i\leq
n}{|a_{i}|}$. Let us define the empirical adversarial risk as

$R_{p}^{\text{adv}}(\boldsymbol{\beta};\delta)=\frac{1}{n}\sum_{i=1}^{n}{\max_{\|\boldsymbol{\Delta
x}_{i}\|_{p}\leq\delta}(y_{i}-(\boldsymbol{x}_{i}+\boldsymbol{\Delta
x}_{i})^{\mathsf{T}}\boldsymbol{\beta})^{2}}.$ (2)

The problem of finding the parameter $\boldsymbol{\beta}$ that minimizes the
empirical adversarial risk $R_{p}^{\text{adv}}(\boldsymbol{\beta};\delta)$ is
referred to as the _$\ell_{p}$ -adversarial training_ problem, which for
linear regression can be simplified to the minimization of a sum of quadratic
terms. We will rely on this result, which is stated in the next lemma and was
proved in [12].

######  Lemma 1 (Dual formulation adversarial risk).

Let $p\in[1,\infty]$ and $\frac{1}{p}+\frac{1}{q}=1$, then

$R_{p}^{\text{adv}}(\boldsymbol{\beta};\delta)=\frac{1}{n}\sum_{i=1}^{n}\left(|y_{i}-\boldsymbol{x}_{i}^{\mathsf{T}}\boldsymbol{\beta}|+\delta\|\boldsymbol{\beta}\|_{q}\right)^{2}$
(3)

An immediate consequence of this result is that for $p\in[1,\infty]$,
$R_{p}^{\text{adv}}(\boldsymbol{\beta};\delta)$ is convex in
$\boldsymbol{\beta}$. The result holds for any pair of complementary norms
$(p,q)$. We note that this includes the values ${(p,q)=(1,\infty)}$ and
${(\infty,1)}$. We also highlight that not only is the right-hand-side of (2)
exactly the same as that of (3), but also the parameter $\delta$ is exactly
the same, i.e., upper bound of the adversarial disturbance.

The proof provided in [12] is based on Hölder’s inequality
${|\boldsymbol{\beta}^{\mathsf{T}}\boldsymbol{\Delta
x}|\leq\|\boldsymbol{\beta}\|_{p}\|\boldsymbol{\Delta x}\|_{q}}$ and on the
fact that, given $\boldsymbol{\beta}$, we can construct $\boldsymbol{\Delta
x}$ such that the equality holds. The result also appear in other recent work
in slightly less general settings: [16] presents it for a Gaussian
distribution, and [8] presents it for $\ell_{2}$ attacks.

###  1.2 Summary of the contributions

We study the optimization problems that arise in adversarial training for
linear regression. We will in Section 2 start by analysing the similarity
between $\ell_{\infty}$-adversarial training and lasso. One interesting result
we observed is that _$\ell_{\infty}$ -adversarial training produces sparse
solutions_—see Fig. 1(b). This fact is interesting but not clearly stated in
the literature. Hence, our first contribution is a way to justify this
observation.

  1. C-1

We _show that adversarial training is an instance of robust regression_. We
use this to connect it with square-root lasso, which is also an instance of
robust regression [17]. Several examples are then used to illustrate the
similarities between the methods.

Note that the dual formulation hold for any pair $(p,q)$ of complementary
norms. Another possible pair would be $(p=2,q=2)$ and a similar argument can
be used to point towards similarities between ridge regression and
$\ell_{2}$-adversarial training. Such similarities can be observed in Fig.1
(c)-(d).

The second contribution of this work is to study the behavior of adversarial
training in overparameterized models, where there are more parameters than
data ($m>n$).

  1. C-2

We _prove that the minimum-norm interpolators are the solution to adversarial
training for all values of $\delta$ below a threshold._

Here, we refer to the interpolators
$\widehat{\boldsymbol{\beta}}^{\text{min-}\ell_{1}}$ and
$\widehat{\boldsymbol{\beta}}^{\text{min-}\ell_{2}}$, which are the solution
that minimize, respectively, $\|\boldsymbol{\beta}\|_{1}$ and
$\|\boldsymbol{\beta}\|_{2}$ and satisfy
$y_{i}=\boldsymbol{x}_{i}^{\mathsf{T}}\boldsymbol{\beta}$ for $i=1,\dots n$.
Both lasso and ridge with the regularization parameter approach the minimum
$\ell_{1}$ and $\ell_{2}$-norm interpolators as the penalization on the norm
goes to zero. We show that such connections also exist for adversarial
training as expressed in the next theorem.

######  Theorem 2.

Assume that the matrix $\boldsymbol{X}\in\mathbb{R}^{n\times m}$ has full row
rank (i.e, $\text{rank}(\boldsymbol{X})=n$). There exists $\bar{\delta}>0$
such that:

  1. 1.

$\widehat{\boldsymbol{\beta}}^{\text{min-}\ell_{1}}$ minimizes
$R_{\infty}^{\text{adv}}(\boldsymbol{\beta},\delta)$, for all
${0<\delta<\bar{\delta}}$;

  2. 2.

$\widehat{\boldsymbol{\beta}}^{\text{min-}\ell_{2}}$ minimizes
$R_{2}^{\text{adv}}(\boldsymbol{\beta},\delta)$, for all
${0<\delta<\bar{\delta}}$.

Interestingly, for adversarial training the interpolation does not occur only
in the limit, but rather for all values $\delta$ smaller than a certain
threshold. We prove the Theorem and discuss its consequences in Section 3.

###  1.3 Related work

##### Adversarial training in linear models.

Gaining insight about adversarial attacks through the analysis of its behavior
in linear models is now commonplace: for instance, [18] and [5] use linear
models to explain the conflict between robustness and high-performance models
observed in neural networks; [12] uses these models to show how
overparameterization affects robustness to perturbations; [7] derives
asymptotics for adversarial training in binary classification. [8] provides
asymptotics for adversarial training in linear regression, [19] studies
classification settings and [9] for random feature regressions. [10]
investigates how the dataset size affects adversarial performance. [11]
provides an analysis of $\ell_{\infty}$-attack on linear classifiers based on
the Rademacher complexity.

##### Adversarial training and sparsity.

In this paper, we establish that, in linear regression,
$\ell_{\infty}$-adversarial attacks yield a sparse solution. We found this
fact quite intriguing and were unable to find a clear reference for it,
although several researchers in correspondence seem to intuitively expect it.
Related facts have since long been established for robust regression [17] and
in Section 2.1 we show how adversarial training differs. Framing adversarial
training as a robust optimization problem is also commonplace [20, 13]. There
are studies highlighting that sparse models can be more robust to adversarial
attacks [21, 22]. [16] propose to add an $\ell_{1}$-penalty to the adversarial
loss to improve generalization, and [23] proposes to add it as part of two-
stage training with $\ell_{1}$ penalty being applied to the first stage and
adversarial training in the second stage. [16] points to the resemblance
between the dual formulation of $\ell_{\infty}$-adversarial training and Lasso
as a concluding remark but does not explore the connection in detail.

##  2 Adversarial training and regularization

In this section, we explore the relationship between adversarial training and
parameter shrinking regularization methods. Indeed, the dual form above yields
a cost function that is remarkably similar to some of the traditional
parameter shrinking regularization methods. For $\ell_{\infty}$ adversarial
attacks (i.e. $q=1$), the cost function
$R^{\text{adv}}_{\infty}(\beta;\delta)$ in its dual form is similar to lasso
regression [24]:

$R^{\text{lasso}}(\boldsymbol{\beta};\delta)=\frac{1}{n}\sum_{i=1}^{n}|y_{i}-\boldsymbol{x}_{i}^{\mathsf{T}}\boldsymbol{\beta}|^{2}+\delta\|\boldsymbol{\beta}\|_{1}.$

Both cost functions penalize the $\ell_{1}$ norm and the error between
observation and predictions. We used $\delta$ to denote the lasso
regularization parameter in order to highlight the similarity with the dual
form.

We study the methods from two angles: First, we analyze
$\ell_{\infty}$-adversarial attacks and lasso through the lens of robust
regression; Secondly, we compare the regularization paths of the methods in an
experimental setup, i.e., the path described by the solution as a function of
the parameter $\delta$.

###  2.1 Robust regression

In robust linear regression, the cost function being minimized during training
is

$R^{\text{robust}}(\boldsymbol{\beta};\mathcal{S})=\max_{\boldsymbol{\Delta}\in\mathcal{S}}\|\boldsymbol{y}-(\boldsymbol{X}+\boldsymbol{\Delta})\boldsymbol{\beta}\|_{2},$
(4)

where $\boldsymbol{X}\in\mathbb{R}^{n\times m}$ denotes the matrix for which
the $i^{\text{th}}$ row is $\boldsymbol{x}_{i}^{\mathsf{T}}$ and
$\boldsymbol{y}\in\mathbb{R}^{n}$ denotes the vector of outputs. Here, the
disturbance matrix $\boldsymbol{\Delta}$ is constrained to belong to the
‘uncertainty set’ $\mathcal{S}$ .

The robust regression framework allows us to establish interesting
connections. On the one hand, robust regression is equivalent to square-root
lasso for ‘feature-wise’ uncertainty sets,

$\mathcal{C}_{2}(\delta)=\left\\{\begin{bmatrix}\bigl{|}&&\bigl{|}\\\
\boldsymbol{\zeta}_{1}&\cdots&\boldsymbol{\zeta}_{m}\\\
\bigl{|}&&\bigl{|}\end{bmatrix}:\|\boldsymbol{\zeta}_{i}\|_{2}\leq\delta\text{
for }i=1,\cdots,m\right\\}.$

On the other hand, robust regression is equivalent to adversarial training for
‘sample-wise’ uncertainty sets,

$\mathcal{R}_{p}(\delta)=\left\\{\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&\boldsymbol{\Delta
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&\boldsymbol{\Delta
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}:\|\boldsymbol{\Delta x}_{i}\|_{p}\leq\delta\text{ for
}i=1,\cdots,n\right\\}.$

This result is summarized in the next proposition.

######  Proposition 3.

We have that for any $\delta$

$\displaystyle\text{\rm
arg}\min_{\boldsymbol{\beta}}R^{\text{robust}}(\boldsymbol{\beta};\mathcal{C}_{2}(\delta))$
$\displaystyle=\text{\rm
arg}\min_{\boldsymbol{\beta}}R^{\sqrt{\text{lasso}}}(\boldsymbol{\beta},\delta);$
(5a) $\displaystyle\text{\rm
arg}\min_{\boldsymbol{\beta}}R^{\text{robust}}(\boldsymbol{\beta},\mathcal{R}_{p}(\delta))$
$\displaystyle=\text{\rm
arg}\min_{\boldsymbol{\beta}}R_{p}^{\text{adv}}(\boldsymbol{\beta},\delta).$
(5b)

Square-root lasso is the estimator minimizing,

$R^{\sqrt{\text{lasso}}}(\boldsymbol{\beta},\delta)=\|\boldsymbol{y}-\boldsymbol{X}\boldsymbol{\beta}\|_{2}+\delta\|\boldsymbol{\beta}\|_{1}.$

It optimizes a Lagrangian formulation of the same constrained problem as
lasso. They have different properties however and the square-root lasso is
pivotal and attain near-oracle performance without knowledge of the variance
levels [25]. Similarly, $\ell_{\infty}$-adversarial training has different
high-dimensional properties when compared to lasso, see [16] for an analysis
of some of these properties.

The first statement about robust regression is proved in [17, theorem 1 ]. The
second part follows by noting that

$\displaystyle R_{p}^{\text{adv}}(\boldsymbol{\beta};\delta)$
$\displaystyle=\frac{1}{n}\max_{\boldsymbol{\Delta}\in\mathcal{R}_{p}(\delta)}\|\boldsymbol{y}-(\boldsymbol{X}+\boldsymbol{\Delta})\boldsymbol{\beta}\|^{2}_{2}$
$\displaystyle=\frac{1}{n}\left(\max_{\boldsymbol{\Delta}\in\mathcal{R}_{p}(\delta)}\|\boldsymbol{y}-(\boldsymbol{X}+\boldsymbol{\Delta})\boldsymbol{\beta}\|_{2}\right)^{2}.$

Where the first equality follows from the definition of adversarial training
and the last equality from the fact that the function $h(z)=\tfrac{1}{n}z^{2}$
is monotonically increasing for $z\geq 0$. Repeating the same argument, but
now for the minimization, implies that
$R_{p}^{\text{adv}}(\boldsymbol{\beta};\delta)$ has the same minimizer as
$\max_{\boldsymbol{\Delta}\in\mathcal{R}_{p}}\|y-(\boldsymbol{X}+\boldsymbol{\Delta})\boldsymbol{\beta}\|_{2}$.

###  2.2 Example: diabetes progression

Regularization paths are plots that show the value of the coefficient
estimates as the regularization parameter $\delta$ is varied. Say, for lasso,
we would define the solution

$\widehat{\boldsymbol{\beta}}^{\text{lasso}}(\delta)=\text{arg}\min_{\boldsymbol{\beta}}R^{\text{lasso}}(\boldsymbol{\beta};\delta)$
(6)

i.e., the optimal parameter as a function of $\delta$. Such a function is
visualized in a plot like the one in Fig. 1, with each one of the coefficients
of $\widehat{\boldsymbol{\beta}}$ being displayed as a function of $\delta$.
Let us now study the regularization paths for $\ell_{2}$ and
$\ell_{\infty}$-adversarial training, ridge regression and lasso regression.

In Fig. 1 we show the so-called regularization paths for the above methods in
the Diabetes dataset [26]. The dataset has $m=10$ baseline variables (age,
sex, body mass index, average blood pressure, and six blood serum
measurements), which were obtained for $n=442$ diabetes patients. The model
output is a quantitative measure of the disease progression one year after the
baseline variables were measured. The dataset was introduced in the context of
the study of lasso solutions.

A visual inspection of the regularization paths in panel (a) and (b)
illustrate the similarities between lasso and $\ell_{\infty}$-adversarial
training. It also illustrates the fact that _$\ell_{\infty}$ -adversarial
training yields sparse solutions_. Moreover, comparing panel (c) and (d)
highlights the similarities between $\ell_{2}$ adversarial attacks (i.e.
$q=2$) and ridge regression, which minimizes

$R^{\text{ridge}}(\boldsymbol{\beta};\delta)=\frac{1}{n}\sum_{i=1}^{n}|y_{i}-\boldsymbol{x}_{i}^{\mathsf{T}}\beta|^{2}+\delta\|\boldsymbol{\beta}\|_{2}^{2}.$

One interesting difference is that while ridge regression coefficients slowly
decay to zero as the amount of regularization is increased, the transition is
more abrupt in the case of $\ell_{2}$-adversarial training. At $\delta\approx
10^{-0.5}$, we see all coefficients collapsing to zero.

We compute the regularization path of ridge regression and adversarial
training by solving the optimization problem for a grid of $200$ values of
$\delta$ equally spaced in the logarithmic space. For lasso, we use the
coordinate descent algorithm proposed by [27]. In this and all our numerical
examples, the adversarial training solution is implemented by minimizing (3)
using CVXPY [28]. The result is displayed for the different methods and, as
$\delta\rightarrow\infty$, the coefficients should approach zero for all
methods. On the other hand, as $\delta\rightarrow 0$, the coefficients should
approach the least-squares solution.

##  3 Overparameterized models

When there are more parameters than data-point ($m>n$) there are multiple
solutions to $\boldsymbol{X}\boldsymbol{\beta}=\boldsymbol{y}$. Among these
solutions, we highlight the solutions with the smallest $\ell_{2}$ and
$\ell_{1}$ norm, respectively. That is, the minimum $\ell_{2}$-norm
interpolator,

$\widehat{\boldsymbol{\beta}}^{\text{min}-\ell_{2}}=\text{arg}\min_{\boldsymbol{\beta}}\|\boldsymbol{\beta}\|_{2}\mathrm{~{}~{}~{}subject~{}to~{}~{}~{}}\boldsymbol{X}\boldsymbol{\beta}=\boldsymbol{y},$

and the minimum $\ell_{1}$-norm interpolator,

$\widehat{\boldsymbol{\beta}}^{\text{min}-\ell_{1}}=\text{arg}\min_{\boldsymbol{\beta}}\|\boldsymbol{\beta}\|_{1}\mathrm{~{}~{}~{}subject~{}to~{}~{}~{}}\boldsymbol{X}\boldsymbol{\beta}=\boldsymbol{y}.$

These solutions are interesting for several reasons: The minimum
$\ell_{1}$-norm interpolator is well studied in the context of ‘basis pursuit’
and allows the recovery of low dimensional representations of sparse signals
[29]. The interest in the minimum $\ell_{2}$ norm is more recent: such a
solution is used in many recent papers where the double descent [30, 31] and
the benign overfitting phenomena [32] are observed. Such studies shed light on
the generalization of state-of-the-art models such as deep neural networks
that (almost) perfectly fit the training data and still generalize well. Many
of the empirical observations for state-of-the-art models can indeed be
illustrated in simpler settings such as linear regression, see e.g. [31, 32].
We point out that the minimum $\ell_{1}$-norm interpolator has also been
studied in connection to the ‘benign-overfitting’ phenomena in [33].

Not only are such solutions interesting from an application point of view,
there is also a connection between ridge regression and the minimum
$\ell_{2}$-norm interpolator, namely the solution of ridge regression
converges to the minimum norm solution as the parameter vanishes.
$\widehat{\boldsymbol{\beta}}^{\text{ridge}}(\delta)\rightarrow\widehat{\boldsymbol{\beta}}^{\text{min}-\ell_{2}}$
as $\delta\rightarrow 0^{+}$. Similarly, there is a relation between the
minimum $\ell_{1}$ norm solution and lasso. The relation requires additional
constraints because, for the overparameterized case, lasso does not
necessarily has a unique solution. Nonetheless, it is proved in [34, Lemma 7]
that the lasso solution by the LARS algorithm satisfy
$\widehat{\boldsymbol{\beta}}^{\text{lasso}}(\delta)\rightarrow\widehat{\boldsymbol{\beta}}^{\text{min}-\ell_{1}}$
as $\delta\rightarrow 0^{+}$.

Interestingly, there is also a connection between adversarial training and
such solutions. As we stated in Section 1.2, for a sufficiently small
$\delta$, the solution of $\ell_{2}$ adversarial training equals the minimum
$\ell_{2}$ norm solution; and, the solution of $\ell_{\infty}$-adversarial
training equals the minimum $\ell_{1}$ norm solution. There is a notable
difference though, while this happens only on the limit for ridge regression
and lasso, for adversarial training this happens for all values $\delta$
smaller than a threshold, which we denote $\bar{\delta}$. Theorem 2 (in the
introduction) establishes this connection and follows from the propositions
below.

######  Proposition 4.

For $0<\delta<\gamma_{\min{}}(\boldsymbol{X})$, a minima of
$R_{p}^{\text{adv}}(\boldsymbol{\beta};\delta)$ lies in the set
$\\{\boldsymbol{\beta}\in\mathbb{R}^{m}|\boldsymbol{X}\boldsymbol{\beta}=\boldsymbol{y}\\}$,
where ${\gamma_{\min{}}(\bullet)}$ denotes the smallest (in magnitude) nonzero
entry of a matrix, i.e.,
$\gamma_{\min{}}(\boldsymbol{X})=\min_{i,j,|x_{i,j}|>0}|x_{i,j}|.$

###### Proof of Theorem 2.

Full row rank guarantees that the set
$\\{\boldsymbol{\beta}\in\mathbb{R}^{m}|\boldsymbol{X}\boldsymbol{\beta}=\boldsymbol{y}\\}$
is not empty. Along this set,
$R_{p}^{\text{adv}}(\boldsymbol{\beta};\delta)=\delta^{2}\|\boldsymbol{\beta}\|_{q}^{2}$
by the dual formula (3). Hence, it follows from the proposition that for
$0<\delta<\gamma_{\min{}}(\boldsymbol{X})$,

$\min_{\beta}R_{p}^{\text{adv}}(\boldsymbol{\beta};\delta)=\min_{\boldsymbol{X}\boldsymbol{\beta}=\boldsymbol{y}}R_{p}^{\text{adv}}(\boldsymbol{\beta};\delta)=\min_{\boldsymbol{X}\boldsymbol{\beta}=\boldsymbol{y}}\|\boldsymbol{\beta}\|_{q}\vspace{-5pt}$

which is minimized by $\widehat{\boldsymbol{\beta}}^{\min-{\ell_{1}}}$ and
$\widehat{\boldsymbol{\beta}}^{\min-{\ell_{2}}}$ for, respectively, for $q=1$
and $q=2$. ∎

###  3.1 Examples

Before proving the proposition we give examples of its consequence. Unlike
ridge regression and lasso that converges towards the interpolation solution,
adversarial training goes through abrupt transitions and suddenly starts to
interpolate the data.

##### Isotropic data model

Figure 2 illustrates this phenomena in synthetically generated data. In this
case, we consider Gaussian noise and covariates:
$\epsilon_{i}\sim\mathcal{N}(0,\sigma^{2})$ and
$\boldsymbol{x}_{i}\sim\mathcal{N}(0,r^{2}\boldsymbol{I}_{m})$ and the output
is computed as a linear combination of the features contaminated with additive
noise: $y_{i}=\boldsymbol{x}_{i}^{\mathsf{T}}\boldsymbol{\beta}+\epsilon_{i}$.
We fix $m=200$ and $n=60$ and in Figure 2 we show what happens as we vary
$\delta$ for models estimated using lasso, ridge and $\ell_{\infty}$ and
$\ell_{2}$-adversarial training. In the Supplementary Material Section A we
consider a different synthetic set that uses features that are noisy
observations of a lower-dimensional subspace, similar to [31, Section 5.4].
The same abrupt transition into interpolation can be observed.

Figure 2: Training MSE vs regularization parameter. _Top:_ for ridge and
$\ell_{2}$-adversarial training. _Bottom:_ for lasso and
$\ell_{\infty}$-adversarial training The error bars give the median and the
0.25 and 0.75 quantiles obtained from numerical experiment (5 realizations).
Vertical black lines give $\gamma_{\min{}}(\boldsymbol{X})$ and, on the top
figure, $\gamma_{\min}(\boldsymbol{Q}\boldsymbol{X})$ obtained from
Propositions 4 and 5.

##### Phenotype prediction from genotype

Figure 3: The normalized MSE (NMSE) on MAGIC dataset. _Top:_ on the test set.
With the best available regularization parameter $\delta$ obtained via grid
search. _Bottom:_ on training as a function of $1/\delta$ for $m=16000$. We
repeat the same experiment $5$ times with independently sampled features to
obtain the median and inter-quartile range represented in the box plot on the
top, and by the full line and colored region on the bottom.

We illustrate our method on the Diverse MAGIC wheat dataset [35] from the
National Institute for Applied Botany. The dataset contains the whole genome
sequence data and multiple phenotypes for a population of 504 wheat lines.
Here, we use a subset of the genotype to predict one of the continuous
phenotypes. We use half of the individuals ($n=252$) for training and the
remaining $252$ samples for testing. We have a binary input with values
indicating whether each one of the 1.1 million nucleotides differs or not from
the reference value. Closely located nucleotides tend to be correlated and we
use only a pruned version of the genome as input to the model. We consider
$m\in\\{1000,2000,4000,8000,16000\\}$ features, where $m$ is a (uniformly
sampled) subset of the genome.

Figure 3 (_top_) gives the test error of each of the methods for different
choices of $m$. For lasso, ridge and adversarial training, we use the best
$\delta$ available for each method (obtained via grid search). We note that
while for $m=1000$ optimally tuned lasso and $\ell_{\infty}$-adversarial
training significantly outperform the corresponding minimum $\ell_{1}$-norm
interpolator. As $m$ increases, the performance of the three different methods
becomes quite similar. The same apply to ridge, $\ell_{2}$-adversarial
training and the minimum $\ell_{2}$-norm interpolator.

Interestingly, for $m=1000$, the minimum $\ell_{2}$-norm has the best
performance, but as $m$ increases, the minimum $\ell_{1}$-norm interpolator
outperforms it. This is an interesting natural example where the
$\widehat{\boldsymbol{\beta}}^{\text{min}-\ell_{1}}$ can outperform the
$\widehat{\boldsymbol{\beta}}^{\text{min}-\ell_{2}}$: the first seems to be
better at incorporating more features without worsening the generalization
capability of the model and it is an interesting counterpoint to [36]. Figure
3 (_bottom_) shows training error as a function of the regularization
parameter $\delta$ (for $m=16000$). While the training error decays slowly as
we vary the amount of regularization $\delta$ for lasso and ridge regression.
For adversarial training, we see again an abrupt drop in the training error.
And after this abrupt drop the model starts to interpolate the training
dataset (up to numerical precision).

###  3.2 The dependency of $\bar{\delta}$ on $m$

(a) ridge regression (b) $\ell_{2}$-adversarial training

(c) lasso regression (d) $\ell_{\infty}$-adversarial training

Figure 4: Mean square error in training data. The error bars give the median
and the 0.25 and 0.75 quantiles obtained from numerical experiment (10
realizations) and for regularization parameter
$\delta=\\{0.5,0.1,0.05,0.01\\}$ with the colors corresponding to each case
indicated in the legend. We use $r^{2}=4$, $\sigma^{2}=1$ and $n=100$.

We observed in our experiment that there exists a threshold $\bar{\delta}$,
such that for $0<\delta<\bar{\delta}$ the solution to adversarial training is
the minimum-norm solution that interpolates the data. In this sense, Theorem 2
cast new light into minimum-norm interpolators: they are solutions minimizing
the empirical adversarial risk for a disturbance $\bar{\delta}>0$. Hence,
studying how $\bar{\delta}$ changes with $\boldsymbol{X}$ provides insight
into the robustness of such solutions.

Note that Proposition 4 only provides a sufficient condition and that there
could be less conservative bounds on $\bar{\delta}$. Indeed, we observe
empirically that often $\bar{\delta}>\gamma_{\min{}}(\boldsymbol{X})$, e.g.,
the vertical black lines in Figure 2. The next proposition gives a tighter
bound that holds for $\ell_{2}$-adversarial attacks.

######  Proposition 5.

For $0<\delta<\gamma_{\min{}}(\boldsymbol{X}\boldsymbol{Q}^{\mathsf{T}})$,
$\boldsymbol{Q}\in\mathbb{R}^{n\times m}$ any matrix with orthogonal rows that
span the rows of $\boldsymbol{X}$, a minima of
$R_{2}^{\text{adv}}(\boldsymbol{\beta};\delta)$ lies in the set
$\\{\boldsymbol{\beta}\in\mathbb{R}^{m}|\boldsymbol{X}\boldsymbol{\beta}=\boldsymbol{y}\\}$.

Figure 5 illustrates the bounds on the threshold obtained from both
propositions for the same isotropic data. We obtain
$\boldsymbol{Q}^{\mathsf{T}}$ by the reduced $QR$ decomposition of
$\boldsymbol{X}^{\mathsf{T}}$ (as hinted by the notation). The bound
$\gamma_{\min{}}(\boldsymbol{X})$ decreases with $m$, while the bound
$\gamma_{\min{}}(\boldsymbol{X}\boldsymbol{Q}^{\mathsf{T}})$ remains constant
with it.

However, we still believe that these bounds could be strengthened in future
work. The reason is shown in Figure 4. There we keep $\delta$ constant and
vary the number of features for the isotropic data model described in Section
3.1. Adversarial training produces abrupt transitions in behavior by
increasing $m$ with $\delta$ constant: giving us reason to believe
$\bar{\delta}$ increases with $m$ in order to explain this observation.

Figure 5: Threshold vs number of features. Here the features $\boldsymbol{X}$
are generated as in the isotropic data model described in Section 3.1.

###  3.3 Proof of Proposition 5

(a) $\boldsymbol{\beta}_{\perp}=\boldsymbol{0}$, variable $\delta$ (b)
$\delta=0.5$, variable $\boldsymbol{\beta}_{\perp}$

Figure 6: Function $f_{i}$. The plot was generated for
$|y_{i}|=\|x_{i}\|_{2}=1$. In (a), we consider
$\boldsymbol{\beta}_{\perp}=\boldsymbol{0}$ and vary $\delta$. For
$\delta<\|x_{i}\|_{2}$ the function has a minima at
$\alpha=|y_{i}|/\|x_{i}\|_{2}$. For, $\delta>\|x_{i}\|_{2}$ it has a minima at
$\alpha=0$. For $\delta=\|x_{i}\|_{2}$ the function has a segment with slope 0
and is minimized at all the points in this segment. In (b), we consider
$\delta=0.5$ and vary $\|\boldsymbol{\beta}_{\perp}\|_{2}$. It has a minima at
$\alpha=|y_{i}|/\|x_{i}\|_{2}$

We use Equation (3) as starting point for the proof. We will analyse the
components that are being summed up. For convenience, let us denote the
components:

$f_{i}(\boldsymbol{\beta})=|y_{i}-\boldsymbol{x}_{i}^{\mathsf{T}}\boldsymbol{\beta}|+\delta\|\boldsymbol{\beta}\|_{2}.$

such that
$R_{2}^{\text{adv}}(\boldsymbol{\beta};\delta)=\frac{1}{n}\sum_{i=1}^{n}\left(f_{i}(\boldsymbol{\beta})\right)^{2}$.
We dropped $\delta$ and $p$ when referring to $f_{i}$ to make the notation
more compact. We present first the case where there is a $n=1$ (i.e., a single
data point). This case gives insight into the proof and why abrupt transitions
occur.

###### Proof of Proposition 5 (n = 1).

Given an arbitrary point $\boldsymbol{x}_{1}\not=\boldsymbol{0}$,
$\boldsymbol{\beta}$ can be decomposed in two parts, one perpendicular to
$\boldsymbol{x}_{1}$ and another one parallel to it. For instance, if we let
$\boldsymbol{q}_{1}=\text{sign}{(y_{1})}\frac{\boldsymbol{x}_{1}}{\|\boldsymbol{x}_{1}\|_{2}}$,
then we can write
$\boldsymbol{\beta}=\alpha_{1}\boldsymbol{q}_{1}+\boldsymbol{\beta}_{\perp}$,
where we denoted the perpendicular component as $\boldsymbol{\beta}_{\perp}$.
Since the two components are perpendicular we have that
$\|\boldsymbol{\beta}\|_{2}>\alpha_{1}$ as long as
$\boldsymbol{\beta}_{\perp}\not=\boldsymbol{0}$ and
$f_{1}(\alpha_{1}\boldsymbol{q}_{1})\leq f_{1}(\boldsymbol{\beta})$. Hence the
function is necessarily minimized along the subspace spanned by the vector
$\boldsymbol{q}_{i}$. Now, along this line, the function $f_{1}$ is piecewise
linear with three segments. We show the function in Fig. 6(a) for different
values of $\delta$. For
$\delta<|\boldsymbol{x}_{1}^{\mathsf{T}}\boldsymbol{q}_{1}|=\|\boldsymbol{x}_{1}\|_{2}$,
we have a minimum at $\alpha_{1}=|y_{1}|/\|\boldsymbol{x}_{1}\|_{2}$. Hence,
$\widehat{\boldsymbol{\beta}}=\text{arg}\min_{\boldsymbol{\beta}}f_{1}(\boldsymbol{\beta})=\alpha_{1}\boldsymbol{q}_{1}=y_{1}\frac{\boldsymbol{x}_{1}}{\|\boldsymbol{x}_{1}\|_{2}^{2}}$
and $\boldsymbol{x}_{1}^{\mathsf{T}}\widehat{\boldsymbol{\beta}}=y_{1}$. And
this conclude the proof for $n=1$. ∎

It is easy to understand why abrupt transition occur by looking at the
function displayed in Fig. 6(a). One of the three segments changes the slope
sign as we change $\delta$ and the minimum of the function changes abruptly.
Considering that $\boldsymbol{\beta}_{\perp}\not=0$ is also instructive and
gives the intuition why the result holds for $n\geq 1$. If
$\boldsymbol{\beta}_{\perp}\not=0$, then

$f_{1}(\alpha_{1}\boldsymbol{q}_{1}+\boldsymbol{\beta}_{\perp})=|y_{1}-\alpha_{1}\boldsymbol{x}_{1}^{\mathsf{T}}\boldsymbol{q}_{1}|+\delta\sqrt{\alpha_{1}^{2}+\|\boldsymbol{\beta}_{\perp}\|^{2}_{2}}.$

Figure 6(b) display the value of $f_{i}$ as a function of $\alpha_{1}$ for
different choices of $\|\boldsymbol{\beta}_{\perp}\|_{2}$. The minimum will
still occur for
$\boldsymbol{x}_{1}^{\mathsf{T}}\boldsymbol{q}_{1}\alpha_{1}=y_{1}$, as long
as $\delta<|\boldsymbol{x}_{1}^{\mathsf{T}}\boldsymbol{q}_{1}|$. The idea why
the result holds for $n>1$ is that, while we might have to adjust for more
than one coefficient $\alpha$, the coefficients can still be adjusted
‘independently’, because adjusting the other coefficients will not really
alter the minimum of the function $f_{1}$.

This intuition can be formalized using subderivatives. The subderivatives of a
function $h:\mathbb{R}^{m}\rightarrow\mathbb{R}$ is the set

$\partial
h(\boldsymbol{x}_{0})=\\{\boldsymbol{v}\in\mathbb{R}^{m}|h(\boldsymbol{x})-h(\boldsymbol{x}_{0})\geq\boldsymbol{v}(\boldsymbol{x}-\boldsymbol{x}_{0})\forall\boldsymbol{x}\in\mathbb{R}^{m}\\}.$

The properties of subderivatives used here can be found on standard convex
analysis textbooks, see for instance [37, chapter 4 ] or [38, 39].

###### Proof of Proposition 5 (general case).

Let $\\{\boldsymbol{q}_{i}\\}_{i=1}^{n}$ be the rows of $\boldsymbol{Q}$,
i.e., a set of unitary mutually orthogonal vectors that span the set of
vectors $\\{\boldsymbol{x}_{i}\\}_{i=1}^{n}$. If we denote
$\boldsymbol{r}_{i}=\boldsymbol{x}_{i}^{\mathsf{T}}\boldsymbol{Q}$, any vector
$\boldsymbol{x}_{i}$ can be written as
$\boldsymbol{x}_{i}=\boldsymbol{Q}\boldsymbol{r}_{i}$.Moreover, we can write
$\boldsymbol{\beta}=\boldsymbol{Q}^{\mathsf{T}}\boldsymbol{\alpha}+\boldsymbol{\beta}_{\perp}$
where $\boldsymbol{\beta}_{\perp}$ is perpendicular to all
$\boldsymbol{x}_{i}$. The same argument as before yields that the minimizer of
$f_{i}$ always occurs for $\boldsymbol{\beta}_{\perp}=\boldsymbol{0}$. Hence,
without loss of generality we can assume
$\boldsymbol{\beta}=\boldsymbol{Q}^{\mathsf{T}}\boldsymbol{\alpha}$. Hence

$f_{i}\left(\boldsymbol{Q}^{\mathsf{T}}\boldsymbol{\alpha}\right)=\left|y_{i}-\boldsymbol{r}_{i}^{\mathsf{T}}\boldsymbol{\alpha}\right|+\delta\|\boldsymbol{\alpha}\|_{2}.$

Now, the subderivative of the above is given by following set $\partial
f_{i}(\boldsymbol{Q}^{\mathsf{T}}\boldsymbol{\alpha})\subset\mathbb{R}^{n}$,

$\partial
f_{i}(\boldsymbol{Q}^{\mathsf{T}}\boldsymbol{\alpha})=\boldsymbol{r}_{i}\partial|y_{i}-\boldsymbol{r}_{i}^{\mathsf{T}}\boldsymbol{\alpha}|+\delta\partial\|\boldsymbol{\alpha}\|_{2}$

where
$\partial\|\boldsymbol{\alpha}\|_{2}=\left\\{\frac{\boldsymbol{\alpha}}{\|\boldsymbol{\alpha}\|_{2}}\right\\}$
if $\boldsymbol{\alpha}\not=0$ and
$\\{\boldsymbol{v}:\|\boldsymbol{v}\|_{2}\leq 1\\}$ otherwise. And

$\partial|y_{i}-\boldsymbol{r}_{i}^{\mathsf{T}}\boldsymbol{\alpha}|=\begin{cases}\\{1\\}\text{
if }y_{i}>\boldsymbol{r}_{i}^{\mathsf{T}}\boldsymbol{\alpha}\\\ \
\\{-1\\}\text{ if }y_{i}<\boldsymbol{r}_{i}^{\mathsf{T}}\boldsymbol{\alpha}\\\
\\{\gamma:\gamma\in[-1,1]\\}\text{ if
}y_{i}=\boldsymbol{r}_{i}^{\mathsf{T}}\boldsymbol{\alpha}\end{cases}$

Let $r_{i,j}$ be the $j^{\text{th}}$ component of $\boldsymbol{r}_{j}$. Notice
that, if $\delta\leq|r_{i,j}|$ for all $j$ for which $|r_{i,j}|>0$, then
$\boldsymbol{0}\in\partial
f_{i}(\boldsymbol{Q}^{\mathsf{T}}\boldsymbol{\alpha})$ if and only if
$y_{i}=\boldsymbol{r}_{i}^{\mathsf{T}}\boldsymbol{\alpha}$. Notice that any
$\delta$ satisfying the hypothesis of the theorem satisfies such inequality.
Now, using the chain rule and additivity of subderivatives:

$\partial
R_{2}^{\text{adv}}(\boldsymbol{Q}^{\mathsf{T}}\boldsymbol{\alpha})=\frac{2}{n}\sum_{i=1}^{n}f_{i}(\boldsymbol{Q}^{\mathsf{T}}\boldsymbol{\alpha})\partial
f_{i}(\boldsymbol{Q}^{\mathsf{T}}\boldsymbol{\alpha}).$ (7)

Hence for $\delta$ satisfy the hypothesis of the theorem and
$y_{i}=\boldsymbol{r}_{i}^{\mathsf{T}}\boldsymbol{\alpha}$ than
$\boldsymbol{0}\in\partial
f_{i}(\boldsymbol{Q}^{\mathsf{T}}\boldsymbol{\alpha})$. If this hold for all
$i$, then $\boldsymbol{0}\in\partial
R_{2}^{\text{adv}}(\boldsymbol{Q}^{\mathsf{T}}\boldsymbol{\alpha})$. By the
optimality condition for subderivatives, a point where this is satisfied local
minima, and, since the function is convex, a global minimum. Hence, any point
in the set
$\\{\boldsymbol{Q}^{\mathsf{T}}\boldsymbol{\alpha}|\boldsymbol{r}_{i}\boldsymbol{\alpha}=y_{i},\forall
i\\}$ will be a minima. Now,
$\boldsymbol{r}_{i}=\boldsymbol{Q}\boldsymbol{x}_{i}$ and this set is the same
as the set
$\\{\boldsymbol{\beta}|\boldsymbol{X}\boldsymbol{\beta}=\boldsymbol{y}\\}$.
The theorem follows. ∎

###  3.4 Proof of Proposition 4

The proof follows a similar outline. Let us denote:

$g_{i}\left(\boldsymbol{\beta}\right)=\left|y_{i}-\boldsymbol{x}_{i}^{\mathsf{T}}\boldsymbol{\beta}\right|+\delta\|\boldsymbol{\beta}\|_{q}.$

such that
$R_{p}^{\text{adv}}(\boldsymbol{\beta};\delta)=\frac{1}{n}\sum_{i=1}^{n}\left(g_{i}(\boldsymbol{\beta})\right)^{2}$.
Now, the subderivative of $g_{i}$ is given by following set $\partial
g_{i}(\boldsymbol{\beta})\subset\mathbb{R}^{m}$,

$\partial
g_{i}(\boldsymbol{\beta})=\boldsymbol{x}_{i}\partial|y_{i}-\boldsymbol{x}_{i}^{\mathsf{T}}\boldsymbol{\beta}|+\delta\partial\|\boldsymbol{\beta}\|_{q}$

where

$\partial\|\boldsymbol{\beta}\|_{q}=\left\\{\boldsymbol{g}~{}|~{}\|\boldsymbol{g}\|_{p}\leq
1,\boldsymbol{g}^{\mathsf{T}}\boldsymbol{\beta}\right\\}$

Note that, by the above definition for any
$\boldsymbol{g}\in\partial\|\boldsymbol{\beta}\|_{q}$, ${g_{i}\leq 1}$. Hence,
if $\delta\leq|x_{i,j}|$ for every $j$, then $\boldsymbol{0}\in\partial
g_{i}(\boldsymbol{\beta})$ if and only if
$y_{i}=\boldsymbol{x}_{i}^{\mathsf{T}}\boldsymbol{\beta}$. And the rest of the
argument follows exactly the same

##  4 Conclusion

In this work, we have studied adversarial training for linear regression from
an optimization perspective. By viewing the method as an instance of robust
regression we have established a connection to parameter-shrinkage methods and
minimum-norm interpolators. These properties in linear regression may also be
relevant in many nonlinear cases. At the moment, neural networks are still
where most research on adversarial training is conducted. Nonetheless, we
believe understanding adversarial training in linear settings is an important
milestone. Moreover, adversarial training in linear regression is an
interesting method in its own right. Linear models are still among the most
commonly used techniques and the method is a practical solution that can be of
interest. The method has a clear interpretation and addresses worst-case
scenarios. Still, a thorough theoretical characterization of the method and
more technical developments are needed to make it competitive. For instance,
while convex, the optimization is still quite inefficient. Coordinate descent
[40, 27] and LARS [26] are clever solutions that allow the entire
regularization path to be efficiently estimated for lasso and elastic net.
Having tailored solvers for linear adversarial training could make the method
more computationally attractive and useful.

#### Acknowledgments

The authors would like to thank Carl Nettelblad for very fruitful discussions
throughout the work with this research. This research was financially
supported by the _Kjell och Märta Beijer Foundation_ and by the Swedish
Research Council through the projects: _Deep probabilistic regression – new
models and learning algorithms_(contract number: 2021-04301) and
_Counterfactual Prediction Methods for Heterogeneous Populations_ (contract
number: 2018-05040).

## References

  * [1] 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
  * [2] Ian J. Goodfellow, Jonathon Shlens and Christian Szegedy  “Explaining and Harnessing Adversarial Examples” arXiv: 1412.6572  In _Proceedings of the 3rd International Conference on Learning Representations (ICLR)_ , 2015
  * [3] Alexey Kurakin et al.  “Adversarial Attacks and Defences Competition” arXiv: 1804.00097  In _arXiv:1804.00097_ , 2018  URL: http://arxiv.org/abs/1804.00097
  * [4] Alhussein Fawzi, Omar Fawzi and Pascal Frossard  “Analysis of classifiers’ robustness to adversarial perturbations”  In _Machine Learning_ 107.3, 2018, pp. 481–508  DOI: 10.1007/s10994-017-5663-3
  * [5] Andrew Ilyas, Shibani Santurkar, Dimitris Tsipras, Logan Engstrom, Brandon Tran and Aleksander Madry  “Adversarial Examples Are Not Bugs, They Are Features” arXiv: 1905.02175  In _Advances in Neural Information Processing Systems_ 32, 2019  URL: http://arxiv.org/abs/1905.02175
  * [6] Xiaoyong Yuan, Pan He, Qile Zhu and Xiaolin Li  “Adversarial examples: Attacks and defenses for deep learning” Publisher: IEEE  In _IEEE transactions on neural networks and learning systems_ 30.9, 2019, pp. 2805–2824
  * [7] Hossein Taheri, Ramtin Pedarsani and Christos Thrampoulidis  “Asymptotic Behavior of Adversarial Training in Binary Classification” arXiv: 2010.13275  In _arXiv:2010.13275_ , 2021  URL: http://arxiv.org/abs/2010.13275
  * [8] 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  URL: http://proceedings.mlr.press/v125/javanmard20a.html
  * [9] Hamed Hassani and Adel Javanmard  “The curse of overparametrization in adversarial training: Precise analysis of robust generalization for random features regression” arXiv: 2201.05149  In _arXiv:2201.05149_ , 2022  URL: http://arxiv.org/abs/2201.05149
  * [10] Yifei Min, Lin Chen and Amin Karbasi  “The Curious Case of Adversarially Robust Models: More Data Can Help, Double Descend, or Hurt Generalization”  In _Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence_ 161, 2021, pp. 129–139  URL: http://arxiv.org/abs/2002.11080
  * [11] Dong Yin, Ramchandran Kannan and Peter Bartlett  “Rademacher Complexity for Adversarially Robust Generalization” ISSN: 2640-3498  In _Proceedings of the 36th International Conference on Machine Learning_ PMLR, 2019, pp. 7085–7094  URL: https://proceedings.mlr.press/v97/yin19b.html
  * [12] Antônio H. Ribeiro and Thomas B. Schön  “Overparameterized Linear Regression under Adversarial Attacks” arXiv: 2204.06274  In _arXiv:2204.06274_ , 2022  URL: http://arxiv.org/abs/2204.06274
  * [13] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras and Adrian Vladu  “Towards Deep Learning Models Resistant to Adversarial Attacks” arXiv: 1706.06083  In _Proceedings of the International Conference for Learning Representations (ICLR)_ , 2018
  * [14] Ruitong Huang, Bing Xu, Dale Schuurmans and Csaba Szepesvari  “Learning with a Strong Adversary” arXiv: 1511.03034  In _arXiv:1511.03034_ , 2016  URL: http://arxiv.org/abs/1511.03034
  * [15] Tao Bai, Jinqi Luo, Jun Zhao, Bihan Wen and Qian Wang  “Recent Advances in Adversarial Training for Adversarial Robustness” arXiv: 2102.01356  In _arXiv:2102.01356_ , 2021  URL: http://arxiv.org/abs/2102.01356
  * [16] Yue Xing, Qifan Song and Guang Cheng  “On the Generalization Properties of Adversarial Training” ISSN: 2640-3498  In _Proceedings of The 24th International Conference on Artificial Intelligence and Statistics_ PMLR, 2021, pp. 505–513  URL: https://proceedings.mlr.press/v130/xing21b.html
  * [17] Huan Xu, Constantine Caramanis and Shie Mannor  “Robust regression and lasso”  In _Advances in neural information processing systems_ 21, 2008
  * [18] 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
  * [19] Adel Javanmard and Mahdi Soltanolkotabi  “Precise Statistical Analysis of Classification Accuracies for Adversarial Training” arXiv: 2010.11213  In _arXiv:2010.11213_ , 2020  URL: http://arxiv.org/abs/2010.11213
  * [20] Uri Shaham, Yutaro Yamada and Sahand Negahban  “Understanding adversarial training: Increasing local stability of supervised models through robust optimization” Publisher: Elsevier  In _Neurocomputing_ 307, 2018, pp. 195–204
  * [21] Yiwen Guo, Chao Zhang, Changshui Zhang and Yurong Chen  “Sparse DNNs with Improved Adversarial Robustness”  In _Advances in Neural Information Processing Systems_ 31, 2018  URL: https://proceedings.neurips.cc/paper/2018/hash/4c5bde74a8f110656874902f07378009-Abstract.html
  * [22] Soorya Gopalakrishnan, Zhinus Marzi, Upamanyu Madhow and Ramtin Pedarsani  “Combating Adversarial Attacks Using Sparse Representations” arXiv: 1803.03880  In _arXiv:1803.03880_ , 2018  URL: http://arxiv.org/abs/1803.03880
  * [23] Yue Xing, Ruizhi Zhang and Guang Cheng  “Adversarially robust estimate and risk analysis in linear regression” tex.pdf: http://proceedings.mlr.press/v130/xing21c/xing21c.pdf  In _Proceedings of the 24th international conference on artificial intelligence and statistics_ 130, Proceedings of machine learning research  PMLR, 2021, pp. 514–522  URL: https://proceedings.mlr.press/v130/xing21c.html
  * [24] Robert Tibshirani  “Regression shrinkage and selection via the LASSO” 00000  In _Journal of the Royal Statistical Society. Series B (Methodological)_ , 1996, pp. 267–288
  * [25] Alexandre Belloni, Victor Chernozhukov and Lie Wang  “Square-Root Lasso: Pivotal Recovery of Sparse Signals via Conic Programming” arXiv:1009.5689 [math, stat]  In _Biometrika_ 98.4, 2011, pp. 791–806  DOI: 10.1093/biomet/asr043
  * [26] Bradley Efron, Trevor Hastie, Iain Johnstone and Robert Tibshirani  “Least angle regression”  In _The Annals of Statistics_ 32.2, 2004, pp. 407–499  DOI: 10.1214/009053604000000067
  * [27] Jerome Friedman, Trevor Hastie and Rob Tibshirani  “Regularization paths for generalized linear models via coordinate descent”  In _Journal of statistical software_ 33.1, 2010, pp. 1  DOI: 10.18637/jss.v033.i01
  * [28] 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
  * [29] Scott Shaobing Chen, David L. Donoho and Michael A. Saunders  “Atomic decomposition by basis pursuit” tex.eprint: https://doi.org/10.1137/S1064827596304010  In _SIAM Journal on Scientific Computing_ 20.1, 1998, pp. 33–61  DOI: 10.1137/S1064827596304010
  * [30] 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
  * [31] Trevor Hastie, Andrea Montanari, Saharon Rosset and Ryan J. Tibshirani  “Surprises in High-Dimensional Ridgeless Least Squares Interpolation” arXiv: 1903.08560  In _arXiv:1903.08560_ , 2019  URL: http://arxiv.org/abs/1903.08560
  * [32] 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
  * [33] Guillaume Wang, Konstantin Donhauser and Fanny Yang  “Tight bounds for minimum l1-norm interpolation of noisy data” arXiv: 2111.05987  In _arXiv:2111.05987_ , 2022  URL: http://arxiv.org/abs/2111.05987
  * [34] Ryan J Tibshirani  “The Lasso Problem and Uniqueness”  In _Electronic Journal of statistics_ 7, 2013, pp. 1456–1490
  * [35] Michael F. Scott et al.  “Limited haplotype diversity underlies polygenic trait architecture across 70 years of wheat breeding”  In _Genome Biology_ 22.1, 2021, pp. 137  DOI: 10.1186/s13059-021-02354-7
  * [36] Niladri S. Chatterji and Philip M. Long  “Foolish Crowds Support Benign Overfitting” arXiv: 2110.02914  In _arXiv:2110.02914_ , 2022  URL: http://arxiv.org/abs/2110.02914
  * [37] Dimitri P Bertsekas, Angelia Nedi and Asuman E Ozdaglar  “Convex analysis and optimization”, 2003
  * [38] Frank H. Clarke  “Optimization and nonsmooth analysis” tex.eprint: https://epubs.siam.org/doi/pdf/10.1137/1.9781611971309  Society for IndustrialApplied Mathematics, 1990  DOI: 10.1137/1.9781611971309
  * [39] S. Boyd, J. Duchi, M. Pilanci and L. Vandenberghe  “Subgradients (Lecture Notes)”, 2022
  * [40] Jerome Friedman, Trevor Hastie, Holger Höfling and Robert Tibshirani  “Pathwise coordinate optimization”  In _The Annals of Applied Statistics_ 1.2, 2007, pp. 302–332  DOI: 10.1214/07-AOAS131

Surprises in adversarially-trained linear regression:
Supplementary Material

##  Appendix A Latent feature models

We include here results for a different synthetic dataset: the “latent space”
feature model described in [31, Section 5.4 ]. 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,$ (S.1)

where $W$ is an $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,$ (S.2)

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)$. As in [31], we consider the features
in the latent space to be isotropic and normal
$z_{i}=\mathcal{N}\left(0,I_{d}\right)$ and 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.

Here we show experiments for $\sigma_{\xi}=0.1$ and $d=20$. All the
experiments are analogous to the experiments performed for the isotropic case.
Fig. S.1 shows the training mean square error (MSE) for $m=200$ and $n=60$
fixed as we vary $\delta$. It also shows the thresholds for interpolation
obtained from Propositions 4 and 5. Fig. S.2 shows the training mean square
error (MSE) of the learned predictors as we keep $\delta$ and $n$ constant and
vary the number of features $m$.

Figure S.1: Training MSE vs regularization parameter (Latent model). _Left:_
for ridge and $\ell_{2}$-adversarial training. _Right:_ for lasso and
$\ell_{\infty}$-adversarial training The error bars give the median and the
0.25 and 0.75 quantiles obtained from numerical experiment (5 realizations).
Vertical black lines give $\gamma_{\min{}}(\boldsymbol{X})$ and, on the figure
to the left, $\gamma_{\min}(\boldsymbol{Q}\boldsymbol{X})$. I.e., the
thresholds obtained from Propositions 4 and 5.

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

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

Figure S.2: Mean square error in training data: latent features. The plot is
equivalent to Fig. 4 but with a different data generation procedure. The error
bars give the median and the 0.25 and 0.75 quantiles obtained from numerical
experiments (6 realizations) and for regularization parameter
$\delta=\\{0.5,0.1,0.05,0.01\\}$ with the colors corresponding to each case
indicated in the legend. In (d), we omit the plot for $\delta=0.5$, that is
because for this high regularization the solver becomes ill-conditioned.

##  Appendix B Additional plots: test MSE and parameter norm

Here we include additional plots related to the experiments, Fig. S.3 show the
parameter $\ell_{2}$-norm and Fig. S.4 show the performance on a hold-out test
set for experiments in the isotropic generated data. Fig. S.5 and Fig. S.6
show the same quantities for experiments in data generated with the latent
model. In these plots, we keep $\delta$ and $n$ constant and vary the number
of features $m$.

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

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

Figure S.3: Parameter $\ell_{2}$-norm: isotropic case. We plot
$\|\widehat{\beta}\|_{2}$ for the parameters estimated by the different
methods. The setup is exactly the same as Fig. 4. In (d), the norm for
$\delta=0.5$ becomes very close to zero $\approx 10^{-10}$, we let it leave
the region in the plot so it is possible to better visualize the curves for
the other regularization parameters.

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

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

Figure S.4: Test MSE: isotropic case. We plot the MSE in a test dataset of
size $n_{\text{test}}=100$ for the parameters estimated by the different
methods. The setup is exactly the same as in Fig. 4.

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

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

Figure S.5: Parameter $\ell_{2}$-norm: latent feature model. We plot
$\|\widehat{\beta}\|_{2}$ for the parameters estimated by the different
methods. The setup is exactly the same as Fig. S.2.

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

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

Figure S.6: Test MSE: latent feature model. We plot the MSE in a test dataset
of size $n_{\text{test}}=100$ for the parameters estimated by the different
methods. The setup is exactly the same as Fig. S.2.