# Is Adversarial Training with Compressed Datasets Effective?

Tong Chen, Raghavendra Selvan
Department of Computer Science, University of Copenhagen, Denmark
<EMAIL_ADDRESS>
###### Abstract

Dataset Condensation (DC) refers to the recent class of dataset compression
methods that generate a smaller, synthetic, dataset from a larger dataset.
This synthetic dataset retains the essential information of the original
dataset, enabling models trained on it to achieve performance levels
comparable to those trained on the full dataset. Most current DC methods have
mainly concerned with achieving high test performance with limited data
budget, and have not directly addressed the question of adversarial
robustness. In this work, we investigate the impact of adversarial robustness
on models trained with compressed datasets. We show that the compressed
datasets obtained from DC methods are not effective in transferring
adversarial robustness to models. As a solution to improve dataset compression
efficiency and adversarial robustness simultaneously, we propose a novel
robustness-aware dataset compression method based on finding the Minimal
Finite Covering (MFC) of the dataset. The proposed method is (1) obtained by
one-time computation and is applicable for any model, (2) more effective than
DC methods when applying adversarial training over MFC, (3) provably robust by
minimizing the generalized adversarial loss. Additionally, empirical
evaluation on three datasets shows that the proposed method is able to achieve
better robustness and performance trade-off compared to DC methods such as
distribution matching.

##  1 Introduction

Deep learning (DL) has enabled large strides of progress across multiple
application domains LeCun et al. (2015); Schmidhuber (2015). Scaling up model
sizes and datasets have shown to be of import to make some of these
breakthroughs Kaplan et al. (2020); Alabdulmohsin et al. (2022). The energy
consumption, and the corresponding carbon footprint, of using these large
model sizes and datasets are also of a growing concern within the community
Strubell et al. (2020); Anthony et al. (2020).

Improving the environmental sustainability of DL, in particular by reducing
their energy consumption, has been primarily addressed with a focus on
improving the resource efficiency of DL models Bartoldson et al. (2023). For
instance, using a smaller model to condense a larger model with knowledge
distillation has shown to be quite effective in reducing the energy
consumption at inference Hinton et al. (2014). Similarly, a recent class of
methods has attempted to condense large datasets into smaller, synthetic,
datasets under the umbrella term of dataset distillation or dataset
condensation (DC) Zhao et al. (2021). These DC methods incur a one-time cost
for dataset compression, which can then be used to train multiple models or
perform iterative optimization efficiently Cui et al. (2022).

On the other hand, fairness, privacy, and robustness of DL models are also
important considerations. These factors can be viewed to constitute the social
sustainability axis Bender et al. (2021); Kaack et al. (2022). Consider
robustness as a case in point; DL models are known to be vulnerable to tiny
perturbations of inputs which was first investigated using adversarial
examples Goodfellow et al. (2015). Robustness to such adversarial attacks is
an important and desirable property of DL models, which otherwise makes them
unreliable and unsafe when applied in various real-life applications, such as
autonomous car and aerospace.

The interplay between performance, efficiency, and social sustainability
aspects, is not fully understood Wright et al. (2023). It has been shown that
there is first a trade-off between performance and optimizing for social
sustainability. For instance, adversarial robustness is achieved at the
expense of test performance Tsipras et al. (2019). Another level of trade-off
exists between optimizing for efficiency and performance Selvan et al. (2023).
Finally, there is also a trade-off between efficiency and social
sustainability, for instance, compressed models have shown to be less fair
Hooker et al. (2020); Stoychev and Gunes (2022).

In this work, we study the trade-off between using compressed datasets, that
can improve efficiency, and their impact on the robustness of models by
answering the question: Can we improve data efficiency and robustness
simultaneously? In particular, we will focus on the distribution matching (DM)
method Zhao and Bilen (2023) as the representative DC method, due to its
inherent efficiency and superior dataset distillation capabilities compared to
other DC methods. And to study robustness, we focus on adversarial training
using projected gradient descent (PGD) attack based on Madry et al. (2018),
where one minimizes the average of the worst-case loss instead of the average
loss as in the standard training, which leads to a non-convex min-max problem.

These choices result in us investigating the adversarial robustness of models
trained with compressed datasets obtained from the DM method. Based on our
observations, we propose a novel, robustness-aware dataset compression method
with provable guarantees, which ensures that adversarial training with the
compressed dataset is more effective than with DC methods. Our key
contributions in this work are summarized below:

  1. 1.

To the best of the authors knowledge, the first systematic study into the
effectiveness of adversarial training with synthetic, compressed datasets
obtained from DC methods.

  2. 2.

Propose a novel robustness-aware dataset compression method based on minimal
finite covering (MFC), which incurs a one-time computation cost, and can be
applied to any models and downstream tasks.

  3. 3.

Formulate MFC as a mixed integer linear programming (MILP), whose upper bound
or exact solution can be found using existing solvers and is better than the
$\varepsilon$-greedy algorithm in Sener and Savarese (2018).

  4. 4.

Present a general adversarial training framework when using a proper covering
of the dataset, such that the generalized adversarial loss over the coreset
serves as a provable upper bound of that over the original dataset.

  5. 5.

Using experiments on three datasets, we empirically show that the proposed MFC
method performs better than DM method in terms of robustness and is also
competitive in terms of test accuracy.

##  2 Related Works

#### Adversarial robustness:

With the emergence of adversarial attacks Goodfellow et al. (2015),
understanding and enhancing adversarial robustness have become challenging
open problems. Numerous strategies for neural networks to defend against
adversarial attacks have been proposed since the last decade, including
randomized smoothing Cohen et al. (2019), adversarial training Tramèr et al.
(2018), certified training Mirman et al. (2018), and gradient norm
regularization Finlay and Oberman (2021). RobustBench, a benchmarking
platform, offers a comprehensive overview of various adversarial training
methods tailored to diverse datasets and norm specifications Croce et al.
(2020).

While adversarial training has proven crucial for enhancing robustness, it
only provides an intuitive understanding of downstream performance.
Consequently, the research community is also seeking for methods that provide
a provable guarantee of robustness. These works are usually referred to as
_certified training_ , which are usually more computationally expensive than
adversarial training, but hold particular significance in specific
applications. Popular works include interval bound propagation Gowal et al.
(2018); Zhang et al. (2019a); Mueller et al. (2023), linear relaxation Zhang
et al. (2018), semidefinite relaxation Raghunathan et al. (2018), differential
privacy Lecuyer et al. (2019), and diffusion de-noised smoothing Carlini et
al. (2023).

#### Robustness-aware model compression:

The computational expense and inefficiency associated with solving non-convex
min-max problems, particularly given the large scale of datasets, pose
challenges for adversarial training. Currently, the primary methods of
improving the efficiency of adversarial robustness is in terms of compressed
models, as shown in works such as adversarial robust distillation Goldblum et
al. (2020) and robust model compression Ye et al. (2019); Gui et al. (2019).
These methods are based on jointly training a smaller model while preserving
the adversarial robustness.

#### Dataset compression:

At a high-level dataset compression methods can be categorized into two:
coreset selection, and DC. Coreset selection methods select a subset with
representative samples from the original dataset and include classic
techniques such as K-center selection Farahani and Hekmatfar (2009) and
herding Chen (2009); Chen et al. (2010).

DC methods are used to generate a smaller set of synthetic data from the
larger original dataset so that a model trained on the smaller dataset yields
the same performance as when trained with the original dataset. The original
DC method introduced in Wang et al. (2018) synthesized new data by matching
performance to a network trained with the original dataset. Further methods
have been developed for DC by matching gradients Zhao et al. (2021), training
trajectories Cazenavette et al. (2022), and intermediate feature-maps Wang et
al. (2022). While these DC methods match some form of performance based on
some explicit downstream task, distribution matching (DM) introduced in Zhao
and Bilen (2023) performs DC by matching the statistics of the original and
the synthetic distributions in a learnt embedding space (which implicitly
could correspond to the downstream task). An overview of more recent methods
is presented along with benchmarking in Cui et al. (2022).

##  3 Preliminaries and Notations

Consider the $n$-dimensional Euclidean space $\mathbb{R}^{n}$ with norm
$\|\cdot\|$. In particular, for $p>0$, the $\ell_{p}$-norm over
$\mathbb{R}^{n}$ is defined as
$\|\mathbf{x}\|_{p}=(\sum_{i=1}^{n}|x_{i}|^{p})^{1/p}$ if $p<\infty$ and
$\|\mathbf{x}\|_{p}=\max_{i}|x_{i}|$ if $p=\infty$. Define a distance metric
$d(\mathbf{x},\mathbf{y})=\|\mathbf{x}-\mathbf{y}\|$ for any two points
$\mathbf{x}$ and $\mathbf{y}$ in $\mathbb{R}^{n}$. Given a point $\mathbf{x}$
and a dataset $\mathcal{Y}$, the distance between $\mathbf{x}$ and
$\mathcal{Y}$ is the infimum of distances between $\mathbf{x}$ and all points
in $\mathcal{Y}$, which is given by
$d(\mathbf{x},\mathcal{Y}):=\inf_{\mathbf{y}\in\mathcal{Y}}d(\mathbf{x},\mathbf{y})$,
and the distance between two datasets is defined as
$d(\mathcal{X},\mathcal{Y}):=\inf_{\mathbf{x}\in\mathcal{X}}\inf_{\mathbf{y}\in\mathcal{Y}}d(\mathbf{x},\mathbf{y})$.
The (quasi)-distance from one dataset $\mathcal{X}$ to another dataset
$\mathcal{Y}$ is given by
$d(\mathcal{X}\to\mathcal{Y}):=\sup_{\mathbf{x}\in\mathcal{X}}d(\mathbf{x},\mathcal{Y})=\sup_{\mathbf{x}\in\mathcal{X}}\inf_{\mathbf{y}\in\mathcal{Y}}d(\mathbf{x},\mathbf{y})$.
The _Hausdorff distance_ between two datasets $\mathcal{X}$ and $\mathcal{Y}$
is defined as

$\displaystyle
d_{H}(\mathcal{X},\mathcal{Y}):=\max\big{\\{}d(\mathcal{X}\to\mathcal{Y}),\;d(\mathcal{Y}\to\mathcal{X})\big{\\}}.$

For $\eta>0$, the _$\eta$ -ball_ of $\mathbf{x}$ is defined as
$\mathcal{B}_{\eta}(\mathbf{x}):=\\{\mathbf{z}:d(\mathbf{x},\mathbf{z})\leq\eta\\}$.
The _the $\eta$-fattening_ of a dataset $\mathcal{Y}$ is defined as

$\mathcal{B}_{\eta}(\mathcal{Y}):=\bigcup_{\mathbf{y}\in\mathcal{Y}}\mathcal{B}_{\eta}(\mathbf{y}).$

We say $\mathcal{Y}$ is a _finite covering_ of $\mathcal{X}$ with radius
$\eta$, or $\mathcal{X}$ is _finitely covered_ by $\mathcal{Y}$ with radius
$\eta$, if $\mathcal{Y}$ is a finite set and for all
$\mathbf{x}\in\mathcal{X}$, there exists $\mathbf{y}\in\mathcal{Y}$ such that
$d(\mathbf{x},\mathbf{y})\leq\eta$, i.e.,
$\mathcal{X}\subseteq\mathcal{B}_{\eta}(\mathcal{Y})$. Obviously,
$\mathcal{X}$ is an $\eta$-finite covering of itself for any $\eta>0$.

######  Remark 3.1.

(1) If $d(\mathcal{X}\to\mathcal{Y})=\eta$, then $\mathcal{Y}$ is an
$\eta$-finite covering of $\mathcal{X}$. If
$d_{H}(\mathcal{X},\mathcal{Y})=\eta$, then $\mathcal{Y}$ is an $\eta$-finite
covering of $\mathcal{X}$, and $\mathcal{X}$ is also an $\eta$-finite covering
of $\mathcal{Y}$;

(2) Any synthetic dataset obtained by coreset and DC methods is a finite
covering for some $\eta>0$.

##  4 Minimal Finite Covering (MFC)

In this section, we will connect coreset and DC methods using a unified
formulation by posing these dataset compression methods as instances of
minimal finite covering (MFC) methods.

Given a dataset
$\mathcal{T}=\\{\mathbf{x}_{i}\\}_{i=1}^{N}\subseteq\mathbb{R}^{n}$, the
trivial $0$-finite covering is the dataset itself, and a trivial
$\infty$-finite covering can be an arbitrary data. Similarly, there always
exists a finite covering of $\mathcal{T}$ with arbitrary size. Hence the
problem of interest is to find the finite covering with minimum radius
($\eta$) or size ($k$).

######  Definition 4.1.

For a finite set $\mathcal{S}\subseteq\mathbb{R}^{n}$.

(1) We say $\mathcal{S}^{*}$ is an _$\eta$ -Minimal Finite Covering
($\eta$-MFC)_ of $\mathcal{T}$, if $\mathcal{S}^{*}$ is a finite covering of
$\mathcal{T}$ with fixed radius $\eta$ and minimum size, i.e., $\mathcal{S}$
is one of the minimizers of problem

$\min_{\mathcal{S}}\\{k:d(\mathcal{T}\to\mathcal{S})=\eta,\;|\mathcal{S}|=k\\};$

(2) We say $\mathcal{S}^{*}$ is a _$k$ -Minimal Finite Covering ($k$-MFC)_ of
$\mathcal{T}$, if $\mathcal{S}^{*}$ is a finite covering of $\mathcal{T}$ with
fixed size $k$ and minimum radius, i.e., $\mathcal{S}$ is one of the
minimizers of problem

$\min_{\mathcal{S}}\\{\eta:d(\mathcal{T}\to\mathcal{S})=\eta,\;|\mathcal{S}|=k\\}.$

######  Remark 4.2.

(1) For any $\eta$ and $k$, the $\eta$-MFC and $k$-MFC always exist, but they
are not unique;

(2) We can replace the equality “=” in Definition 4.1 by inequality “$\leq$”.
Indeed, any finite covering of $\mathcal{T}$ with radius $\leq\eta$ is also a
finite covering with radius $\eta$. Similarly, any finite covering of
$\mathcal{T}$ with size $\leq k$ is also a finite covering with size $k$ by
taking repeated points.

Definition 4.1 gives a natural definition of MFC where the term “minimal” is
defined with respect to either radius $\eta$ or size $k$ of the finite
dataset. The following proposition shows that we can also define the MFC using
Hausdorff distance. We only take $\eta$-MFC as example, the case of $k$-MFC
can be similarly derived.

######  Proposition 4.3.

The following statements are equivalent:

(1) $\mathcal{S}^{*}$ is an $\eta$-MFC of $\mathcal{T}$;

(2)
$\mathcal{S}^{*}\in\arg\min_{\mathcal{S}}\\{k:d_{H}(\mathcal{T},\mathcal{S})=\eta,\;|\mathcal{S}|=k\\}$.

Proof for this proposition is outlined in Appendix A.1.

Notice that, if we assume $\mathcal{S}$ is a subset of $\mathcal{T}$, i.e., a
_coreset_ of $\mathcal{T}$, then the distance from $\mathcal{S}$ to
$\mathcal{T}$ is exactly 0. In this case, the Hausdorff distance between
$\mathcal{T}$ and $\mathcal{S}$ reduces to the distance from $\mathcal{T}$ to
$\mathcal{S}$, i.e.,
$d_{H}(\mathcal{T},\mathcal{S})=d(\mathcal{T}\rightarrow\mathcal{S})$, and
Proposition 4.3 becomes trivial. The corresponding MFC is called a _minimal
coreset (MCS)_ of $\mathcal{T}$. Any subset of $\mathcal{T}$ can be described
using a binary vector $\mathbf{s}\in[0,1]^{N}$, where $s_{i}=1$ means
$\mathbf{x}_{i}\in\mathcal{S}$ otherwise $\mathbf{x}_{i}\notin\mathcal{S}$. In
the next theorem, we provide a tractable optimization formulation for MCS.

######  Theorem 4.4.

For a given dataset $\mathcal{T}=\\{\mathbf{x}_{i}\\}_{i=1}^{N}$, define the
adjacency matrix of $\mathcal{T}$ w.r.t. radius $\eta$ as

$\mathbf{A}(\eta):=\begin{bmatrix}a_{ij}(\eta)\end{bmatrix},\;a_{ij}(\eta)=\begin{cases}1,&\text{if
}d(\mathbf{x}_{i},\mathbf{x}_{j})\leq\eta;\\\ 0,&\text{otherwise.}\end{cases}$

(1) The $\eta$-MCS of $\mathcal{T}$ is one of the minimizers of

$\displaystyle\min_{\mathbf{s}\in\\{0,1\\}^{N}}\;\\{\|\mathbf{s}\|_{1}:\mathbf{A}(\eta)\cdot\mathbf{s}\geq
1\\};$ ($\eta$-MCS)

(2) The $k$-MCS of $\mathcal{T}$ is one of the minimizers of

$\displaystyle\min_{\eta,\;\mathbf{s}\in\\{0,1\\}^{N}}\;\\{\eta:\mathbf{A}(\eta)\cdot\mathbf{s}\geq
1,\;\|\mathbf{s}\|_{1}=k\\}.$ ($k$-MCS)

The proof for this theorem is outlined in Appendix Theorem.

######  Remark 4.5.

(1) If we adapt the terminology from DC literature, then MFC can be considered
as a DC method, and MCS as a coreset selection method;

(2) Finding the $k$-MCS of a given dataset is exactly the _K-center_ approach
Sener and Savarese (2018) for coreset selection. In particular, the case of
$k=1$ is well-known as the _smallest bounding sphere_ problem Elzinga and
Hearn (1972), or the _minimal enclosing ball_ problem Kumar et al. (2004). The
_smallest circle_ problem in the plane is an example of a _facility location
problem_ Fallah et al. (2009). Both the smallest circle problem in the plane,
and the smallest bounding sphere problem in any higher-dimensional space of
bounded dimension are solvable in worst-case linear time Megiddo (1983); Dyer
(1986). However, the K-center problem is NP-hard Cook et al. (1998).

As we see, determining an $\eta$-MCS is equivalent to solving a _mixed integer
linear programming (MILP)_ problem, while finding a $k$-MCS involves
addressing a _mixed integer quadratically constrained programming (MIQCP)_
problem. Since solving a general MILP is already NP-hard, finding a $k$-MCS is
much more challenging than finding an $\eta$-MCS. Fortunately, we are able to
approach the solution of ($k$-MCS) by iteratively solving ($\eta$-MCS), as
shown in Algorithm 1. Indeed, if we fix the radius $\eta$ in ($k$-MCS), then
it reduces to a feasibility problem with mixed linear constraints, which gives
us an answer whether there exists a valid MCS with radius $\eta$ and size $k$.
If the answer is yes, this means we can further decrease the radius and re-
check the new feasibility. Otherwise, the radius should be increased until an
approximated MCS is found within a specified tolerance precision.

Algorithm 1 $k$-MCS

Input: dataset $\mathcal{T}$, size $k$

Initialize $\eta_{l}\leftarrow 0,\;\eta_{u}\leftarrow
R,\;r\leftarrow\eta_{u}-\eta_{l},\;\delta\leftarrow 10^{-5}$

repeat

$\eta_{new}\leftarrow(\eta_{l}+\eta_{u})/2$

$v\leftarrow$ feasibility of ($k$-MCS) with radius $\eta_{new}$

if $v$ = TRUE then

$\eta_{l}\leftarrow\eta_{l},\;\eta_{u}\leftarrow\eta_{new}$

else

$\eta_{l}\leftarrow\eta_{new},\;\eta_{u}\leftarrow\eta_{u}$

end if

$r\leftarrow\eta_{u}-\eta_{l}$

until $r\leq\delta$

Output: MCS with given size $k$ and minimum radius $\eta_{u}$

##  5 Adversarial Training over $\eta$-MCS

In this section, we will apply standard- and adversarial- training over the
MCS we obtained in the previous section, resulting in the robustness-aware
dataset compression method.

Given a probability measure $\nu$ and a finite dataset
$\mathcal{T}\subseteq\mathbb{R}^{n+1}$, we assume each data point
$(\mathbf{x},y)\in\mathcal{T}$ is i.i.d. sampled from $\nu$. Each finite
sampling $\mathcal{T}$ defines an empirical distribution
$\hat{\nu}_{\mathcal{T}}=\frac{1}{|\mathcal{T}|}\sum_{(\mathbf{x},y)\in\mathcal{T}}\delta_{(\mathbf{x},y)}$,
where $\delta_{(\mathbf{x},y)}$ is the Dirac measure over point
$(\mathbf{x},y)$. For a loss function
$l:\mathbb{R}^{2}\rightarrow\mathbb{R}_{+}$, the standard training aims to
learn a model parameterized by $\theta$ that minimizes the standard loss:

$L^{std}(\theta)=\mathbb{E}_{(\mathbf{x},y)\sim\nu}[l(f_{\theta}(\mathbf{x}),y)],$

with its empirical estimation

$\hat{L}^{std}(\theta,\mathcal{T})=\mathbb{E}_{(\mathbf{x},y)\sim\hat{\nu}_{\mathcal{T}}}[l(f_{\theta}(\mathbf{x}),y)].$

On the other hand, adversarial training aims to learn a model that minimizes
the adversarial loss w.r.t. some perturbation $\varepsilon>0$:

$\displaystyle
L^{adv}_{\varepsilon}(\theta)=\mathbb{E}_{(\mathbf{x},y)\sim\nu}\bigg{[}\max_{\|\delta\|\leq\varepsilon}l(f_{\theta}(\mathbf{x}+\delta),y)\bigg{]},$
(1)

with its empirical estimation

$\displaystyle\hat{L}^{adv}_{\varepsilon}(\theta,\mathcal{T})=\mathbb{E}_{(\mathbf{x},y)\sim\hat{\nu}_{\mathcal{T}}}\bigg{[}\max_{\|\delta\|\leq\varepsilon}l(f_{\theta}(\mathbf{x}+\delta),y)\bigg{]}.$
(2)

In the following discussion, we will focus on classification task, i.e.,
$y\in\\{1,\ldots,K\\}$. For a probability measure $\nu$ and a fixed label $i$,
we denote by $\mathcal{T}_{i}\subseteq\mathbb{R}^{n}$ an i.i.d sampling from
the conditional probability measure $\nu(\cdot|y=i)$. We assume that
$\mathcal{T}_{i}\cap\mathcal{T}_{j}=\varnothing$ for all $i\neq j$, since one
single point cannot share two different labels. In adversarial training, we
are also searching around the ball of radius $\varepsilon$ for each point,
which is exactly the $\varepsilon$-fattening of dataset $\mathcal{T}$.
Therefore, we also need to make sure that the two fattening balls of different
labels do not overlap.

######  Definition 5.1.

We say that $\\{\mathcal{T}_{i}\\}$ satisfy the _Running Isolation Property
(RIP)_ if for all $i\neq j$, the sets $\mathcal{T}_{i}$ and $\mathcal{T}_{j}$
do not overlap, i.e., $\mathcal{T}_{i}\cap\mathcal{T}_{j}=\varnothing$.

######  Assumption 5.2.

In standard training, we assume $\\{\mathcal{T}_{i}\\}$ satisfies RIP. In
adversarial training, we assume $\varepsilon$ is such that
$\\{\mathcal{B}_{\varepsilon}(\mathcal{T}_{i})\\}$ satisfies RIP. In this
case, we also say that $\mathcal{T}$ is _$\varepsilon$ -separated_ borrowing
the terminology in Yang et al. (2020); Li et al. (2022).

######  Remark 5.3.

5.2 is easily satisfied by setting $\varepsilon<\min_{j\neq
k}d(\mathcal{T}_{j},\mathcal{T}_{k})/2$.

While performing adversarial training over MCS, we can simply use the
classical definition of adversarial loss in Equation 1 and Equation 2, i.e.,
set equal weights to each individual Dirac measure in the empirical
distribution $\hat{\nu}_{\mathcal{T}}$. However, by doing this, we are unable
to derive any provable relation between the empirical adversarial loss over
the compressed dataset and the original one. Fortunately, for MCS, we can
define the generalized adversarial loss to provide a provable guarantee
compared to the classical loss.

######  Definition 5.4.

Let $\mathcal{T}=\cup_{i}\mathcal{T}_{i}$ be a finite sampling from $\nu$
where each $\mathcal{T}_{i}$ is the conditional sampling from
$\nu(\cdot|y=i)$. Suppose $\mathcal{S}=\cup_{i}\mathcal{S}_{i}$ is an
$\eta$-MCS of $\mathcal{T}$ such that
$\\{\mathcal{B}_{\varepsilon+\eta}(\mathcal{S}_{i})\\}$ satisfies RIP,

(1) The _generalized empirical distribution_ over $\mathcal{S}$ is defined:

$\hat{\mu}_{\mathcal{S}}=\frac{1}{|\mathcal{T}|}\sum_{(\mathbf{x},y)\in\mathcal{S}}q_{(\mathbf{x},y)}\delta_{(\mathbf{x},y)},$

where $q_{(\mathbf{x},y)}$ is the number of points in $\mathcal{T}$ that
belongs to the ball $\mathcal{B}_{\eta}(\mathbf{x})$;

(2) The _generalized adversarial loss_ over $\mathcal{S}$ is defined as

$\hat{G}^{adv}_{\varepsilon+\eta}(\theta,\mathcal{S}):=\mathbb{E}_{(\mathbf{x},y)\sim\hat{\mu}_{\mathcal{S}}}\bigg{[}\max_{\|\delta\|\leq\varepsilon+\eta}l(f_{\theta}(\mathbf{x}+\delta),y)\bigg{]}.$

By adding non-trivial weights to the classical adversarial loss, we are able
to derive a provable guarantee of the generalized adversarial loss.

######  Theorem 5.5.

Let $\mathcal{T}$ and $\mathcal{S}$ be as defined in Definition 5.4. Then
$\hat{L}^{adv}_{\varepsilon}(\theta,\mathcal{T})\leq\hat{G}^{adv}_{\varepsilon+\eta}(\theta,\mathcal{S})$.

Proof for this theorem is outlined in Appendix Theorem.

From Theorem 5.5, we are glad to see that, minimizing the generalized
adversarial loss over MCS provides a valid upper bound of minimizing the
classical adversarial loss over the original dataset. Note that if $\eta=0$,
the generalized adversarial loss reduces to the classical one.

######  Corollary 5.6.

Let $\mathcal{T}$ and $\mathcal{S}$ be as defined in Definition 5.4, then the
robust model obtained by minimizing the generalized adversarial loss
$\hat{G}^{adv}_{\varepsilon+\eta}(\theta,\mathcal{S})$ is robust over the
original dataset $\mathcal{T}$ w.r.t. radius $\varepsilon$.

##  6 Revisiting the Trade-off between Accuracy and Robustness

Before going into the experimental results, we discuss some well-known results
of accuracy and robustness of models, and how they behave for different
datasets. We first give the formal definition of test accuracy and robust
accuracy, which are the core concepts throughout the following discussion.

######  Definition 6.1.

Given a probability measure $\nu$, an i.i.d. sampling $\mathcal{T}$ from $\nu$
with its associated empirical measure $\hat{\nu}_{\mathcal{T}}$, and a
hypothesis space $\mathcal{H}$. For $\theta\in\mathcal{H}$,

(1) The _test accuracy_ of $\theta$ is defined as

$TA(\theta):=\mathbf{Pr}_{(\mathbf{x},y)\sim\nu}[f_{\theta}(\mathbf{x})=y],$

with its empirical version

$\widehat{TA}(\theta,\mathcal{T}):=\mathbf{Pr}_{(\mathbf{x},y)\sim\hat{\nu}_{\mathcal{T}}}[f_{\theta}(\mathbf{x})=y];$

(2) The _robust accuracy_ of $\theta$ w.r.t. perturbation $\varepsilon$ is
defined:

$RA(\varepsilon,\theta):=\mathbf{Pr}_{(\mathbf{x},y)\sim\nu}[f_{\theta}(\mathbf{x}+\delta)=y,\;\forall\;\|\delta\|\leq\varepsilon],$

with its empirical version

$\widehat{RA}(\varepsilon,\theta,\mathcal{T}):=\mathbf{Pr}_{(\mathbf{x},y)\sim\hat{\nu}_{\mathcal{T}}}[f_{\theta}(\mathbf{x}+\delta)=y,\;\forall\;\|\delta\|\leq\varepsilon].$

It is well known that there is a trade-off between test accuracy and
robustness Tsipras et al. (2019); Zhang et al. (2019b); Yang et al. (2020);
Raghunathan et al. (2020) for deep neural networks. This is to say that, if
the test accuracy of a model $TA(\theta)$ is high (which can be achieved by
standard training), then its robust accuracy $RA(\varepsilon,\theta)$ is
usually low, i.e., any classifier that is very accurate will necessarily be
non-robust. Identically, if the robust accuracy of a model
$RA(\varepsilon,\theta)$ is high (which can be achieved by adversarial
training), then its test accuracy $TA(\theta)$ is usually low. In one
sentence:

_It is usually difficult for a classifier to be both accurate and robust._

The accuracy-robustness trade-off we described above is about the performance
of classifiers in $\mathcal{H}$ over a fixed probability measure $\nu$ or
$\hat{\nu}_{\mathcal{T}}$. For every dataset $\mathcal{T}$, we define the
_standard classifier_ as
$\theta^{std}_{\mathcal{T}}=\arg\min_{\theta\in\mathcal{H}}\widehat{TA}(\theta,\mathcal{T})$,
and the _robust classifier_ as
$\theta^{adv}_{\varepsilon,\mathcal{T}}=\arg\min_{\theta\in\mathcal{H}}\widehat{RA}(\varepsilon,\theta,\mathcal{T})$.
If we focus on the optimal classifiers
$\theta^{std}_{\mathcal{T}},\theta^{adv}_{\varepsilon,\mathcal{T}}$ depending
only on $\mathcal{T}$, then we can also discuss about the accuracy and
robustness of different datasets $\mathcal{T}$.

######  Definition 6.2.

Given a finite dataset $\mathcal{T}$.

(1) The _test score_ of $\mathcal{T}$ is defined as the test accuracy of the
standard classifier $\theta^{std}_{\mathcal{T}}$, i.e.,
$TS(\mathcal{T})=TA(\theta^{std}_{\mathcal{T}})$;

(2) The _robust score_ of $\mathcal{T}$ w.r.t. perturbation $\varepsilon$ is
defined as the robust accuracy of the robust classifier
$\theta^{adv}_{\varepsilon,\mathcal{T}}$, i.e.,
$RS(\varepsilon,\mathcal{T})=RA(\varepsilon,\theta^{adv}_{\varepsilon,\mathcal{T}})$.

In the current DC literature, most of the methods are proposed to maximize the
test score of dataset $\mathcal{T}$, resulting in solving the optimization
problem: $\max_{\mathcal{T}}TS(\mathcal{T})$. This has shown excellent
performance even for extreme dataset compression, despite the expensive
computation and heavy memory burden Cui et al. (2022). Take the CIFAR10
dataset Krizhevsky et al. (2009), for example, we are able to achieve $71.6$%
test accuracy over a synthetic dataset with only $50$ images per class v.s.
$84.8$% over the original dataset with $50000$ images in total, according to
Cazenavette et al. (2022).

However, to the best of the authors’ knowledge, there are no existing works
concerned about the robustness of models trained with these synthetic,
compressed, datasets. In this work, we re-observed the accuracy-robustness
trade-off for compressed datasets: if the test score of a dataset
$TS(\mathcal{T})$ is high (which can be achieved by DC mehtods), then their
robust score $RS(\varepsilon,\mathcal{T})$ is usually low, which means
adversarial training over $\mathcal{T}$ is not effective. We therefore propose
the following conjecture:

_It is usually difficult for a compressed dataset to be both accurate and
robust._

Similar to Tsipras et al. (2019), we give an explicit example to illustrate
the above conjecture.

######  Example 6.3.

_(Robustness-accuracy trade-off for compressed dataset)_. Consider a binary
classification task for data $(\mathbf{x},y)\in\mathbb{R}^{n+1}\times\\{\pm
1\\}$ sampled from distribution $\nu(p)$ defined as follows:

$\displaystyle y\sim\mathcal{U}(\\{\pm 1\\}),$ $\displaystyle
x_{1}=\begin{cases}+y,&\text{w.p. }p,\\\ -y,&\text{w.p. }1-p,\\\ \end{cases}$
$\displaystyle
x_{2},\ldots,x_{n+1}\overset{i.i.d.}{\sim}\mathcal{U}([(y-1)/2,(y+1)/2]).$

Let the hypothesis space $\mathcal{H}$ be the space of linear classifiers
$\text{sign}(\mathbf{w}^{T}\mathbf{x})$, and consider
$\ell_{\infty}$-adversarial robustness with perturbation $\varepsilon=1$.
Then, for any $p\in[0.5,1]$,

(1) Any classifier
$f_{a}(\mathbf{x})=\text{sign}(w_{2}x_{2}+\cdots+w_{n+1}x_{n+1})$ with
$w_{i}>0$ is perfect, i.e., $TA(f)=100\%$, but has robust accuracy 0%;

(2) The most robust classifier is $f_{r}(\mathbf{x})=\text{sign}(x_{1})$, with
test and robust accuracy both equal to $p$.

Example 6.3 indicates that, on the one hand, we always have perfect but non-
robust classifiers $f_{a}$ for any distribution $\nu(p)$. On the other hand,
the robust accuracy of any classifier cannot be higher than $p$. In this case,
DC methods can easily achieve the best test performance. However, the
compressed datasets might not follow the original data distribution. For the
synthetic datasets sampled from distribution $\nu(p)$ with $p\approx 0.5$, it
is impossible to improve the robust accuracy of the classifiers to a
satisfactory level.

##  7 Experiments

In this section, we provide additional evidence supporting the trade-off
between robustness and accuracy for compressed dataset, as previously
discussed. Our experiments are conducted on a toy dataset with four classes:
[I,C,M,L], and two benchmark datasets (MNIST and CIFAR10). We explore three
dataset compression methods:

  * •

RAW: original full dataset;

  * •

RAND-$k$: random coreset selection of size $k$;

  * •

DM-$k$: distribution matching of size $k$;

  * •

MCS-$\varepsilon$: MCS of radius $\varepsilon$ by solving problem
($\eta$-MCS);

  * •

MCS-$k$: MCS of size $k$ using Algorithm 1.

We mainly consider DM from Zhao and Bilen (2023) as the baseline DC method due
to the considerable computational costs associated with obtaining the
compressed datasets from other DC methods involving bi-level optimizations;
particularly when scaling up the size, such as with $k=500$. We choose the
computationally cheaper DM method, as the baseline which also shows
competetive performance compared to other DC methods Cui et al. (2022). For
each compressed dataset, we consider a multilayer perceptron (MLP) for the
toy- and MNIST- datasets, and convolutional neural networks (ConvNet) for
CIFAR10 dataset. Specifically, the MLP architecture consists of two hidden
layers, each comprising 128 neurons. The ConvNet architecture includes 3
blocks, each containing 128 filters of size $3\times 3$, followed by instance
norm Ulyanov et al. (2016), ReLU activation and average pooling layers. We
perform generalized adversarial training over the MCS, and classical
adversarial training over other compressed dataset.

For all datasets, we focus on MCS w.r.t. $\ell_{2}$-norm, and perform
adversarial training over them for both $\ell_{\infty}$\- and $\ell_{2}$\-
norms. This is because MNIST and CIFAR10 data are distributed very closely to
the boundary of $\ell_{\infty}$-balls, resulting in similar
$\ell_{\infty}$-distances between data points within the same class. All the
MCS are obtained using the existing MILP solver in GUROBI by solving
($\eta$-MCS). Experimental results for MCS with respect to
$\ell_{\infty}$-norm are presented in Section B.4. We use PGD-$\ell_{\infty}$
and PGD-$\ell_{2}$ attack to perform adversarial training and compute the
robust accuracy. Following the common setting in the robustness literature
Croce et al. (2020), we set the adversarial perturbation to
$\varepsilon_{\infty}=0.1$ for MNIST dataset and $\varepsilon_{\infty}=8/255$
for CIFAR10 dataset, for $\ell_{\infty}$-norm. For $\ell_{2}$-norm, in order
to keep the volume of $\ell_{\infty}$-ball and $\ell_{2}$-ball be similar, we
set $\varepsilon_{2}=\sqrt{\frac{2n}{\pi e}}\varepsilon_{\infty}$, where $n$
is the (flattened) dimension of input images. All the experiments are run with
5 repeats using an NVIDIA A100 40GB GPU. Source code will be made available at
https://github.com/saintslab/pytoch.

Table 1: Comparison of test and robust accuracy of models trained over DIKU dataset. The coresets we consider are RAW and MCS-$\eta$ of fixed radius $\eta=0.05$ and minimum size $k=75$. The perturbation of $\ell_{\infty}$-adversarial robustness is 0.05. coreset | train | test acc. |  $\ell_{\infty}$ acc.
---|---|---|---
RAW | STD | 100 | 88.20
$\ell_{\infty}$-ADV | 100 | 91.65
MCS-$\eta$ | STD | 100 | 89.09
$\ell_{\infty}$-ADV | 99.89 | 90.53
GEN. $\ell_{\infty}$-ADV | 100 | 95.43

###  7.1 “DIKU”111The Danish abbreviation of Dept. of Computer Science at
University of Copenhagen ends up being DIKU dataset

We first construct a two-dimensional toy dataset with four labels: “D”, “I”,
“K” and “U” and consisting of 898 points. By computing the minimum distance of
subset with different labels, we get that this dataset is $0.2$-separated.
Therefore we consider $\ell_{\infty}$-adversarial robustness with perturbation
$\varepsilon=0.05$, and the maximum radius of finite covering that satisfies
Theorem 5.5 is $\eta=0.05$. By solving problem ($\eta$-MCS), we obtain a
$0.05$-MCS with minimum size $k=75$. Figure 4 in Section B.1 is the
visualization of “DIKU” dataset and its $\eta$-MCS. We first apply standard
training and adversarial training (with perturbation $\varepsilon$) over the
full dataset as a baseline. For $\eta$-MCS, we use perturbation
$\varepsilon+\eta$ instead of $\varepsilon$ for (generalized) adversarial
training.

Table 1 shows the downstream performance of models trained over the original
dataset and compressed dataset. We see that adversarial training is essential
to improve robustness, and there is no remarkable discrepancy between the test
accuracy of standardly trained models (98.97% v.s. 97.66%) and the robust
accuracy of adversarially trained models (78.85% v.s. 75.82%). These
experimental results give strong evidennce to the statement in Theorem 5.5.
Figure 1 shows the visualization of the decision boundaries of models trained
with the original- and compressed datasets. Figure 5 in Section B.2
additionally shows the visual comparison of classical and generalized
adversarial training over MCS of DIKU dataset.

(a) Std. training over RAW.

(b) $\ell_{\infty}$-Adv. training over RAW.

(c) Std. training over MCS.

(d) $\ell_{\infty}$-Adv. training over MCS.

Figure 1: Visualization of the DIKU toy dataset and decision boundaries of
models trained using various coresets. Figures in the first and second rows
are results for standard training and $\ell_{\infty}$-adversarial training
respectively. Figures in the first and second columns are results for coresets
RAW and MCS respectively. The black solid lines are the decision boundaries of
each model. The decision boundary between ”K” and ”U” (the right vertical
line) clearly exemplifies the influence of robustness-aware training, as the
margin between the classes is the largest for $\ell_{\infty}$-adversarial
training in (b) and (d) compared to the other two settings.

###  7.2 MNIST and CIFAR10 dataset

For convenience of comparison, we consider $k$-MCS for both MNIST and CIFAR10
dataset with $k=[50,100,200,300,400,500]$. However, for these considered
sizes, their corresponding radius $\eta$ is quite large and the
$(\varepsilon+\eta)$-fattening of the MCS does not satisfy RIP. Thus Theorem
5.5 is not applicable here anymore. Nevertheless, we can still perform
generalized adversarial training over MCS, with perturbation $\varepsilon$
instead of $\varepsilon+\eta$. We will see later that it actually shows
excellent empirical downstream performance. Table 3 in Section B.3 shows the
hyperparameters for standard and adversarial training for MNIST and CIFAR10
dataset.

Figure 2 shows the test, $\ell_{\infty}$\- and $\ell_{2}$\- robust accuracy of
models obtained by standard, $\ell_{\infty}$\- and $\ell_{2}$\- adversarial
training over the original MNIST and compressed dataset. Notice that for
RAND-$k$ and MCS-$k$, the coresets becomes exactly the original dataset if
$k=N$. However, even though $k=N$, DM-$k$ is still different from the original
dataset. We compute DM-$k$ with $k=5000$ for MNIST dataset. We see that, when
applying standard training, all models show similar performance in terms of
test accuracy and robust accuracy. However, adversarial training over DM-$k$
does not seem to be more effective, while RAND-$k$ and MCS-$k$ have large
improvement in robustness. Even if the size of DM increases to $k=5000$, the
robust accuracy after adversarial training is still _much_ lower than when
using the original dataset. This behavior coincides with the conjecture we
propose in Section 6: DC methods breaks the distribution of the original data.

Figure 2: Performance of standard and robust models trained with different
compressed datasets from MNIST. The figures from left to right are standard
training, $\ell_{\infty}$-adversarial training and $\ell_{2}$-adversarial
training. The blue, orange and green lines stand for MCS, RAND, and DM
respectively. The solid, dashed and dotted lines stand for test,
$\ell_{\infty}$ and $\ell_{2}$ robust accuracy respectively. In the horizontal
axis, “full” means the original dataset for MCS and RAND, and $k=5000$ for DM.

Figure 3: Performance of standard and robust models trained over different
compressed dataset from CIFAR10. The figures from left to right are standard
training, $\ell_{\infty}$-adversarial training and $\ell_{2}$-adversarial
training. The blue, orange and green lines stand for MCS, RAND, and DM
respectively. The solid, dashed and dotted lines stand for test,
$\ell_{\infty}$ and $\ell_{2}$ robust accuracy respectively. In the horizontal
axis, “full” means the original dataset for MCS and RAND, and $k=4000$ for DM.

Figure 3 shows exactly the same behavior for CIFAR10 dataset. Due to memory
issue, we only have access to DM-$k$ with $k=4000$. As the size of compressed
dataset increases, the robust accuracy of both MCS and RAND are both
increasing. However, the robustness of DM does not seem to improve. Especially
if we increase the size $k$ of DM to $4000$, the test accuracy of
$\ell_{\infty}$-robustly trained model slightly outperforms the original
CIFAR10 data (68.86% v.s. 64.59%), whereas the robust score of the former is
_much_ smaller than the latter (12.98% v.s. 36.21%), which is actually at the
same level as $k=50$.

Table 2 provides an overview of all the numerical results evaluated over
different models and different datasets. All the results are computed by the
mean of 5 repeats and their standard deviation. Surprisingly, the poor
behavior of DM is expected, but RAND performs even better than MCS in most
cases, both for test and robust accuracy. This makes sense because RIP
condition does not hold either for MNIST or CIFAR10, whereas the random
coreset might capture the distribution of the original data better.

Table 2: Downstream performance of models trained over original and compressed dataset of MNIST and CIFAR10. The considered coresets are RAW, MCS-$k$, RAND-$k$ with $k=500$, and DM-$k$ with $k=500$. To compare DM with RAW, we set the size of DM to be 5000 and 4000 for MNIST and CIFAR10 respectively. The $\ell_{\infty}$ perturbation radius of MNIST and CIFAR10 is 0.1 and 8/255 respectively. The $\ell_{2}$ perturbation radius of MNIST and CIFAR10 is 1.36 and 0.84. dataset | coreset | test score |  $\ell_{\infty}$-score |  $\ell_{2}$-score
---|---|---|---|---
MNIST | RAW |  98.08$\pm$0.06 |  88.75$\pm$0.23 |  83.29$\pm$0.19
MCS-500 |  96.10$\pm$0.15 |  70.69$\pm$1.44 |  65.46$\pm$3.31
RAND-500 |  95.47$\pm$0.02 |  78.69$\pm$0.28 |  75.23$\pm$0.20
DM-500 |  94.51$\pm$0.28 |  45.72$\pm$2.11 |  35.50$\pm$0.57
DM-5000 |  96.04$\pm$0.40 |  53.37$\pm$2.19 |  45.34$\pm$1.19
CIFAR10 | RAW |  81.64$\pm$0.15 |  36.21$\pm$0.23 |  32.50$\pm$0.27
MCS-500 |  62.89$\pm$0.54 |  23.09$\pm$5.01 |  18.59$\pm$0.49
RAND-500 |  65.42$\pm$0.18 |  28.30$\pm$7.31 |  24.42$\pm$0.27
DM-500 |  63.76$\pm$0.38 |  12.61$\pm$0.46 |  8.50$\pm$0.89
DM-4000 |  72.91$\pm$0.36 |  12.98$\pm$0.56 |  4.81$\pm$0.90

##  8 Conclusion and Future Works

In this paper, we stress the accuracy-robustness trade-off in terms of
compressed datasets, which is rarely discussed in the robustness and DC
communities. We claim that improving both the test score and robust score of a
dataset is difficult, because DC methods force the dataset to only maximize
the test performance and breaks the data distribution. We construct a
probabilistic example and show several numerical experiments to support our
arguments.

Moreover, in order to perform adversarial training with compressed datasets
with provable guarantee, we propose MCS and generalized adversarial loss over
MCS. We proved that the generalized adversarial loss over MCS provides a valid
upper bound of the classical adversarial loss over the original dataset. This
means if the data satisfies RIP condition, i.e.,
$(\varepsilon+\eta)$-separated, then there exists a robust classifier over MCS
w.r.t. radius $\varepsilon+\eta$ which is also robust over the original
dataset w.r.t. radius $\varepsilon$. Even though this condition does not hold
for MNIST and CIFAR10, there is empirical improvement compared to the DC
method.

Finally, we propose an MILP formulation to obtain MCS with fixed radius or
size. The advantage of MCS is three folds: firstly, it is a one-time
computation, which means the MCS can be applied to any models for any tasks;
secondly, the MCS can be adapted to different distance metrics; lastly, the
size of MILP only depends on the number of data, not on the dimension of data.

There are many interesting future works regarding DC and robustness. For
example, we showed that compressed datasets obtained by DC methods have poor
robustness scores. Investigations into enabling robust DC methods will be of
interest. Further proving the accuracy-robustness trade-off in a more general
setting will also be interesting.

## Broader Impact

This paper presents work whose goal is to advance the field of Machine
Learning. However, the work here could raise awareness about the trade-off
between performance, efficiency, and robustness, of a small class of ML
methods. There are many potential societal consequences of our work, none
which we feel must be further highlighted here.

## Acknowledgements

The authors acknowledge funding received under European Union’s Horizon Europe
Research and Innovation programme under grant agreements No. 101070284 and No.
101070408. The authors thank Julian E Schön for useful discussions during the
early development of the work.

## References

  * Alabdulmohsin et al. [2022] I. M. Alabdulmohsin, B. Neyshabur, and X. Zhai.  Revisiting neural scaling laws in language and vision.  _Advances in Neural Information Processing Systems (NeurIPS)_ , 35:22300–22312, 2022.
  * Anthony et al. [2020] L. F. W. Anthony, B. Kanding, and R. Selvan.  Carbontracker: Tracking and Predicting the Carbon Footprint of Training Deep Learning Models.  ICML Workshop on Challenges in Deploying and monitoring Machine Learning Systems, 2020.
  * Bartoldson et al. [2023] B. R. Bartoldson, B. Kailkhura, and D. Blalock.  Compute-efficient deep learning: Algorithmic trends and opportunities.  _Journal of Machine Learning Research_ , 24:1–77, 2023\.
  * Bender et al. [2021] E. M. Bender, T. Gebru, A. McMillan-Major, and S. Shmitchell.  On the dangers of stochastic parrots: Can language models be too big?  In _Proceedings of the 2021 ACM conference on fairness, accountability, and transparency (FaCCT)_ , 2021.
  * Carlini et al. [2023] N. Carlini, F. Tramer, K. D. Dvijotham, L. Rice, M. Sun, and J. Z. Kolter.  (certified!!) adversarial robustness for free!  In _The Eleventh International Conference on Learning Representations_ , 2023.
  * Cazenavette et al. [2022] G. Cazenavette, T. Wang, A. Torralba, A. A. Efros, and J.-Y. Zhu.  Dataset distillation by matching training trajectories.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2022.
  * Chen [2009] K. Chen.  On coresets for k-median and k-means clustering in metric and euclidean spaces and their applications.  _SIAM Journal on Computing_ , 39(3):923–947, 2009\.  doi: 10.1137/070699007.
  * Chen et al. [2010] Y. Chen, M. Welling, and A. Smola.  Super-samples from kernel herding.  In _Proceedings of the Twenty-Sixth Conference on Uncertainty in Artificial Intelligence_ , pages 109–116, 2010.
  * Cohen et al. [2019] J. Cohen, E. Rosenfeld, and Z. Kolter.  Certified adversarial robustness via randomized smoothing.  In K. Chaudhuri and R. Salakhutdinov, editors, _Proceedings of the 36th International Conference on Machine Learning_ , volume 97 of _Proceedings of Machine Learning Research_ , pages 1310–1320. PMLR, 09–15 Jun 2019.
  * Cook et al. [1998] W. J. Cook, W. H. Cunningham, W. R. Pulleyblank, and A. Schrijver.  _Combinatorial Optimization_.  John Wiley & Sons, Inc., USA, 1998.  ISBN 047155894X.
  * Croce et al. [2020] F. Croce, M. Andriushchenko, V. Sehwag, E. Debenedetti, N. Flammarion, M. Chiang, P. Mittal, and M. Hein.  Robustbench: a standardized adversarial robustness benchmark.  _arXiv preprint arXiv:2010.09670_ , 2020.
  * Cui et al. [2022] J. Cui, R. Wang, S. Si, and C.-J. Hsieh.  Dc-bench: Dataset condensation benchmark.  _arXiv preprint arXiv:2207.09639_ , 2022.
  * Dyer [1986] M. E. Dyer.  On a multidimensional search technique and its application to the euclidean one-centre problem.  _SIAM Journal on Computing_ , 15(3):725–738, 1986\.  doi: 10.1137/0215052.
  * Elzinga and Hearn [1972] D. J. Elzinga and D. W. Hearn.  The minimum covering sphere problem.  _Management Science_ , 19(1):96–104, 1972.  ISSN 00251909, 15265501.
  * Fallah et al. [2009] H. Fallah, A. N. Sadigh, and M. Aslanzadeh.  _Covering Problem_ , pages 145–176.  Physica-Verlag HD, Heidelberg, 2009.  ISBN 978-3-7908-2151-2.  doi: 10.1007/978-3-7908-2151-2˙7.
  * Farahani and Hekmatfar [2009] R. Z. Farahani and M. Hekmatfar.  _Facility location: concepts, models, algorithms and case studies_.  Springer Science & Business Media, 2009.
  * Finlay and Oberman [2021] C. Finlay and A. M. Oberman.  Scaleable input gradient regularization for adversarial robustness.  _Machine Learning with Applications_ , 3:100017, 2021.  ISSN 2666-8270.  doi: https://doi.org/10.1016/j.mlwa.2020.100017.
  * Goldblum et al. [2020] M. Goldblum, L. Fowl, S. Feizi, and T. Goldstein.  Adversarially robust distillation.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 34(04):3996–4003, Apr. 2020.  doi: 10.1609/aaai.v34i04.5816.
  * Goodfellow et al. [2015] I. Goodfellow, J. Shlens, and C. Szegedy.  Explaining and harnessing adversarial examples.  In _International Conference on Learning Representations_ , 2015.
  * Gowal et al. [2018] S. Gowal, K. Dvijotham, R. Stanforth, R. Bunel, C. Qin, J. Uesato, R. Arandjelovic, T. Mann, and P. Kohli.  On the effectiveness of interval bound propagation for training verifiably robust models.  _arXiv preprint arXiv:1810.12715_ , 2018.
  * Gui et al. [2019] S. Gui, H. Wang, H. Yang, C. Yu, Z. Wang, and J. Liu.  Model compression with adversarial robustness: A unified optimization framework.  In _Proceedings of the 33rd Conference on Neural Information Processing Systems_ , 2019.
  * Hinton et al. [2014] G. Hinton, O. Vinyals, and J. Dean.  Distilling the knowledge in a neural network.  _Advances in Neural Information Processing Systems (NeurIPS)_ , 2014\.
  * Hooker et al. [2020] S. Hooker, N. Moorosi, G. Clark, S. Bengio, and E. Denton.  Characterising bias in compressed models.  _Arxiv_ , 2020.
  * Kaack et al. [2022] L. H. Kaack, P. L. Donti, E. Strubell, G. Kamiya, F. Creutzig, and D. Rolnick.  Aligning artificial intelligence with climate change mitigation.  _Nature Climate Change_ , 2022.
  * Kaplan et al. [2020] J. Kaplan, S. McCandlish, T. Henighan, T. B. Brown, B. Chess, R. Child, S. Gray, A. Radford, J. Wu, and D. Amodei.  Scaling laws for neural language models.  _arXiv preprint arXiv:2001.08361_ , 2020.
  * Krizhevsky et al. [2009] A. Krizhevsky, G. Hinton, et al.  Learning multiple layers of features from tiny images.  2009\.
  * Kumar et al. [2004] P. Kumar, J. S. B. Mitchell, and E. A. Yildirim.  Approximate minimum enclosing balls in high dimensions using core-sets.  _ACM J. Exp. Algorithmics_ , 8:1.1–es, dec 2004.  ISSN 1084-6654.  doi: 10.1145/996546.996548.
  * LeCun et al. [2015] Y. LeCun, Y. Bengio, and G. Hinton.  Deep learning.  _nature_ , 521(7553):436–444, 2015.
  * Lecuyer et al. [2019] M. Lecuyer, V. Atlidakis, R. Geambasu, D. Hsu, and S. Jana.  Certified robustness to adversarial examples with differential privacy.  In _2019 IEEE Symposium on Security and Privacy (SP)_ , pages 656–672, 2019.  doi: 10.1109/SP.2019.00044.
  * Li et al. [2022] B. Li, J. Jin, H. Zhong, J. Hopcroft, and L. Wang.  Why robust generalization in deep learning is difficult: Perspective of expressive power.  In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, _Advances in Neural Information Processing Systems_ , volume 35, pages 4370–4384. Curran Associates, Inc., 2022.
  * Madry et al. [2018] A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu.  Towards deep learning models resistant to adversarial attacks.  In _International Conference on Learning Representations (ICLR)_ , 2018.
  * Megiddo [1983] N. Megiddo.  Linear-time algorithms for linear programming in r3 and related problems.  _SIAM Journal on Computing_ , 12(4):759–776, 1983\.  doi: 10.1137/0212052.
  * Mirman et al. [2018] M. Mirman, T. Gehr, and M. Vechev.  Differentiable abstract interpretation for provably robust neural networks.  In J. Dy and A. Krause, editors, _Proceedings of the 35th International Conference on Machine Learning_ , volume 80 of _Proceedings of Machine Learning Research_ , pages 3578–3586. PMLR, 10–15 Jul 2018.
  * Mueller et al. [2023] M. N. Mueller, F. Eckert, M. Fischer, and M. Vechev.  Certified training: Small boxes are all you need.  In _The Eleventh International Conference on Learning Representations_ , 2023.
  * Raghunathan et al. [2018] A. Raghunathan, J. Steinhardt, and P. Liang.  Certified defenses against adversarial examples.  _arXiv preprint arXiv:1801.09344_ , 2018.
  * Raghunathan et al. [2020] A. Raghunathan, S. M. Xie, F. Yang, J. Duchi, and P. Liang.  Understanding and mitigating the tradeoff between robustness and accuracy.  In H. D. III and A. Singh, editors, _Proceedings of the 37th International Conference on Machine Learning_ , volume 119 of _Proceedings of Machine Learning Research_ , pages 7909–7919. PMLR, 13–18 Jul 2020.
  * Schmidhuber [2015] J. Schmidhuber.  Deep learning in neural networks: An overview.  _Neural networks_ , 61:85–117, 2015.
  * Selvan et al. [2023] R. Selvan, J. Schön, and E. B. Dam.  Operating critical machine learning models in resource constrained regimes.  In _MICCAI Workshop on Resource-Efficient Medical Image Analysis_. Springer, 2023.
  * Sener and Savarese [2018] O. Sener and S. Savarese.  Active learning for convolutional neural networks: A core-set approach.  In _International Conference on Learning Representations_ , 2018.
  * Stoychev and Gunes [2022] S. Stoychev and H. Gunes.  The effect of model compression on fairness in facial expression recognition.  _Arxiv_ , 2022.
  * Strubell et al. [2020] E. Strubell, A. Ganesh, and A. McCallum.  Energy and policy considerations for modern deep learning research.  In _Proceedings of the AAAI conference on artificial intelligence_ , volume 34, pages 13693–13696, 2020.
  * Tramèr et al. [2018] F. Tramèr, A. Kurakin, N. Papernot, I. Goodfellow, D. Boneh, and P. McDaniel.  Ensemble adversarial training: Attacks and defenses.  In _International Conference on Learning Representations_ , 2018.
  * Tsipras et al. [2019] D. Tsipras, S. Santurkar, L. Engstrom, A. Turner, and A. Madry.  Robustness may be at odds with accuracy.  In _International Conference on Learning Representations_ , 2019.
  * Ulyanov et al. [2016] D. Ulyanov, A. Vedaldi, and V. Lempitsky.  Instance normalization: The missing ingredient for fast stylization.  _arXiv preprint arXiv:1607.08022_ , 2016.
  * Wang et al. [2022] K. Wang, B. Zhao, X. Peng, Z. Zhu, S. Yang, S. Wang, G. Huang, H. Bilen, X. Wang, and Y. You.  Cafe: Learning to condense dataset by aligning features.  In _2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 12186–12195, 2022.  doi: 10.1109/CVPR52688.2022.01188.
  * Wang et al. [2018] T. Wang, J.-Y. Zhu, A. Torralba, and A. A. Efros.  Dataset distillation.  _arXiv preprint arXiv:1811.10959_ , 2018.
  * Wright et al. [2023] D. Wright, C. Igel, G. Samuel, and R. Selvan.  Efficiency is not enough: A critical perspective of environmentally sustainable ai.  _Arxiv_ , 2023.
  * Yang et al. [2020] Y.-Y. Yang, C. Rashtchian, H. Zhang, R. R. Salakhutdinov, and K. Chaudhuri.  A closer look at accuracy vs. robustness.  In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, _Advances in Neural Information Processing Systems_ , volume 33, pages 8588–8601. Curran Associates, Inc., 2020.
  * Ye et al. [2019] S. Ye, K. Xu, S. Liu, J.-H. Lambrechts, H. Zhang, A. Zhou, K. Ma, Y. Wang, and X. Lin.  Adversarial robustness vs. model compression, or both?  In _The IEEE International Conference on Computer Vision (ICCV)_ , October 2019.
  * Zhang et al. [2018] H. Zhang, T.-W. Weng, P.-Y. Chen, C.-J. Hsieh, and L. Daniel.  Efficient neural network robustness certification with general activation functions.  In _Advances in Neural Information Processing Systems (NuerIPS)_ , dec 2018.
  * Zhang et al. [2019a] H. Zhang, H. Chen, C. Xiao, S. Gowal, R. Stanforth, B. Li, D. Boning, and C.-J. Hsieh.  Towards stable and efficient training of verifiably robust neural networks.  _arXiv preprint arXiv:1906.06316_ , 2019a.
  * Zhang et al. [2019b] H. Zhang, Y. Yu, J. Jiao, E. Xing, L. E. Ghaoui, and M. Jordan.  Theoretically principled trade-off between robustness and accuracy.  In K. Chaudhuri and R. Salakhutdinov, editors, _Proceedings of the 36th International Conference on Machine Learning_ , volume 97 of _Proceedings of Machine Learning Research_ , pages 7472–7482. PMLR, 09–15 Jun 2019b.
  * Zhao and Bilen [2023] B. Zhao and H. Bilen.  Dataset condensation with distribution matching.  In _2023 IEEE/CVF Winter Conference on Applications of Computer Vision (WACV)_ , pages 6503–6512, 2023.  doi: 10.1109/WACV56688.2023.00645.
  * Zhao et al. [2021] B. Zhao, K. R. Mopuri, and H. Bilen.  Dataset condensation with gradient matching.  In _International Conference on Learning Representations_ , 2021.

##  Appendix A Proofs

We restate the proposition and theorems before presenting the proof for
convenience.

###  A.1 Proof for Proposition 4.3

######  Proposition.

The following statements are equivalent:

(1) $\mathcal{S}^{*}$ is an $\eta$-MFC of $\mathcal{T}$;

(2)
$\mathcal{S}^{*}\in\arg\min_{\mathcal{S}}\\{k:d_{H}(\mathcal{T},\mathcal{S})=\eta,\;|\mathcal{S}|=k\\}$.

###### Proof.

Suppose $\mathcal{S}^{*}$ is an $\eta$-MFC of $\mathcal{T}$, and
$\mathcal{S}_{H}^{*}$ is a minimizer of
$\min_{\mathcal{S}}\\{k:d_{H}(\mathcal{T},\mathcal{S})=\eta,\;|\mathcal{S}|=k\\}$.
We only need to prove $|\mathcal{S}^{*}|=|\mathcal{S}_{H}^{*}|$. Indeed, any
dataset $\mathcal{S}$ satisfying $d_{H}(\mathcal{T},\mathcal{S})=\eta$ also
satisfies $d(\mathcal{T}\rightarrow\mathcal{S})\leq\eta$, hence
$|\mathcal{S}^{*}|\leq|\mathcal{S}_{H}^{*}|$. If
$|\mathcal{S}^{*}|<|\mathcal{S}_{H}^{*}|$, then we have
$d(\mathcal{S}^{*}\rightarrow\mathcal{T})>\eta$. By definition, there exists
$\mathbf{x}^{*}\in\mathcal{S}^{*}$ such that
$d(\mathbf{x}^{*},\mathbf{y})>\eta$ for all $\mathbf{y}\in\mathcal{T}$.
However, this means by removing point $\mathbf{x}^{*}$ from $\mathcal{S}^{*}$,
the set $\mathcal{S}^{*}\setminus\\{\mathbf{x}^{*}\\}$ is also a finite
covering of $\mathcal{T}$ with radius $\eta$ and size $|\mathcal{S}^{*}|-1$,
which contradicts the minimality of $|\mathcal{S}^{*}|$. ∎

###  A.2 Proof for Theorem 4.4

######  Theorem.

For a given dataset $\mathcal{T}=\\{\mathbf{x}_{i}\\}_{i=1}^{N}$, define the
adjacency matrix of $\mathcal{T}$ w.r.t. radius $\eta$ as

$\mathbf{A}(\eta):=\begin{bmatrix}a_{ij}(\eta)\end{bmatrix},\;a_{ij}(\eta)=\begin{cases}1,&\text{if
}d(\mathbf{x}_{i},\mathbf{x}_{j})\leq\eta;\\\ 0,&\text{otherwise.}\end{cases}$

(1) The $\eta$-MCS of $\mathcal{T}$ is one of the minimizers of

$\displaystyle\min_{\mathbf{s}\in\\{0,1\\}^{N}}\;\\{\|\mathbf{s}\|_{1}:\mathbf{A}(\eta)\cdot\mathbf{s}\geq
1\\};$ ($\eta$-MCS)

(2) The $k$-MCS of $\mathcal{T}$ is one of the minimizers of

$\displaystyle\min_{\eta,\;\mathbf{s}\in\\{0,1\\}^{N}}\;\\{\eta:\mathbf{A}(\eta)\cdot\mathbf{s}\geq
1,\;\|\mathbf{s}\|_{1}=k\\}.$ ($k$-MCS)

###### Proof.

(1) By the first part of Definition 4.1, an $\eta$-MFC of $\mathcal{T}$ is one
of the minimizers of

$\displaystyle\min_{\mathcal{S}}\\{k:d(\mathcal{T}\to\mathcal{S})=\eta,\;|\mathcal{S}|=k\\}$
$\displaystyle=$
$\displaystyle\min_{\mathcal{S}}\\{|\mathcal{S}|:\sup_{\mathbf{x}\in\mathcal{T}}\inf_{\mathbf{y}\in\mathcal{S}}d(\mathbf{x},\mathbf{y})=\eta\\}$
$\displaystyle=$
$\displaystyle\min_{\mathcal{S}}\\{|\mathcal{S}|:\forall\mathbf{x}\in\mathcal{T},\;\exists\mathbf{y}\in\mathcal{S},\;d(\mathbf{x},\mathbf{y})\leq\eta\\}$
$\displaystyle=$
$\displaystyle\min_{\mathcal{S}}\\{|\mathcal{S}|:\forall\mathbf{x}\in\mathcal{T},\;|\mathcal{S}_{\mathbf{x}}|\geq
1\\}$ (3)

where
$\mathcal{S}_{\mathbf{x}}=\\{\mathbf{y}\in\mathcal{S}:d(\mathbf{x},\mathbf{y})\leq\eta\\}\subseteq\mathcal{S}$
for $\mathbf{x}\in\mathcal{T}$. Denote by
$\mathbf{A}_{\mathcal{T},\mathcal{S}}(\eta)$ the adjacency matrix

$\mathbf{A}_{\mathcal{T},\mathcal{S}}(\eta):=\begin{bmatrix}a_{\mathbf{x},\mathbf{y}}(\eta)\end{bmatrix},\;a_{\mathbf{x},\mathbf{y}}(\eta)=\begin{cases}1,&\text{if
}d(\mathbf{x},\mathbf{y})\leq\eta;\\\ 0,&\text{otherwise.}\end{cases}$

Then Section A.2 is equivalent to

$\min_{\mathcal{S}}\\{|\mathcal{S}|:\mathbf{A}_{\mathcal{T},\mathcal{S}}(\eta)\cdot\mathbf{1}_{|\mathcal{S}|}\geq
1\\}$

where $\mathbf{1}_{|\mathcal{S}|}$ is the vector of all ones of dimension
$|\mathcal{S}|$, and the inequality is element-wise. This immediately
concludes the proof if $\mathcal{S}$ is a subset of $\mathcal{T}$.

(2) By the second part of Definition 4.1, a $k$-MFC of $\mathcal{T}$ is one of
the minimizers of

$\displaystyle\min_{\mathcal{S}}\\{\eta:d(\mathcal{T}\to\mathcal{S})=\eta,\;|\mathcal{S}|=k\\}$
$\displaystyle=$
$\displaystyle\min_{\mathcal{S}}\\{\eta:\mathbf{A}_{\mathcal{T},\mathcal{S}}(\eta)\cdot\mathbf{1}_{|\mathcal{S}|}\geq
1,\;|\mathcal{S}|=k\\}$ (4)

where the equality is directly derived from the previous part. ∎

###  A.3 Proof for Theorem 5.5

######  Theorem.

Let $\mathcal{T}$ and $\mathcal{S}$ be as defined in Definition 5.4. Then
$\hat{L}^{adv}_{\varepsilon}(\theta,\mathcal{T})\leq\hat{G}^{adv}_{\varepsilon+\eta}(\theta,\mathcal{S})$.

###### Proof.

Let $\mathcal{T}=\\{(\mathbf{x}_{i},y_{i})\\}_{i=1}^{N}$ and
$\mathcal{S}=\\{(\tilde{\mathbf{x}}_{j},\tilde{y}_{j})\\}_{j=1}^{M}$. Since
$\mathcal{S}$ is an $\eta$-MCS of $\mathcal{T}$, for every
$(\mathbf{x}_{i},y_{i})\in\mathcal{T}$, there exists
$(\tilde{\mathbf{x}}_{j},\tilde{y}_{j})\in\mathcal{S}$ such that
$y_{i}=\tilde{y}_{j}$ and
$\mathbf{x}_{i}\in\mathcal{B}_{\eta}(\tilde{\mathbf{x}}_{j})$, hence
$\mathcal{B}_{\varepsilon}(\mathbf{x}_{i})\subseteq\mathcal{B}_{\varepsilon+\eta}(\tilde{\mathbf{x}}_{j})$.
For each $j=1,\ldots,M$, define index set
$I_{j}=\\{i:\mathbf{x}_{i}\in\mathcal{B}_{\eta}(\tilde{\mathbf{x}}_{j})\\}\subseteq\\{1,\ldots,N\\}$.
By definition of adversarial loss over $\mathcal{T}$,

$\displaystyle\hat{L}^{adv}_{\varepsilon}(\theta,\mathcal{T})$
$\displaystyle=\mathbb{E}_{(\mathbf{x},y)\sim\hat{\nu}_{\mathcal{T}}}\bigg{[}\max_{\|\delta\|\leq\varepsilon}l(f_{\theta}(\mathbf{x}+\delta),y)\bigg{]}$
$\displaystyle=\frac{1}{N}\sum_{i=1}^{N}\max_{\|\delta\|\leq\varepsilon}l(f_{\theta}(\mathbf{x}_{i}+\delta),y_{i})$
$\displaystyle=\frac{1}{N}\sum_{j=1}^{M}\sum_{i\in
I_{j}}\max_{\|\delta\|\leq\varepsilon}l(f_{\theta}(\mathbf{x}_{i}+\delta),y_{i})$
$\displaystyle\leq\frac{1}{N}\sum_{j=1}^{M}\sum_{i\in
I_{j}}\max_{\|\delta\|\leq\varepsilon+\eta}l(f_{\theta}(\tilde{\mathbf{x}}_{j}+\delta),\tilde{y}_{j})$
$\displaystyle=\frac{1}{N}\sum_{j=1}^{M}|I_{j}|\cdot\max_{\|\delta\|\leq\varepsilon+\eta}l(f_{\theta}(\tilde{\mathbf{x}}_{j}+\delta),\tilde{y}_{j})$
$\displaystyle=\hat{G}^{adv}_{\varepsilon+\eta}(\theta,\mathcal{S}).$

We conclude the proof by letting $q_{(\mathbf{x}_{j},y_{j})}=|I_{j}|$. ∎

##  Appendix B Additional Results

###  B.1 Visualization of “DIKU” dataset and its finite covering

(a) $\eta=1$

(b) $\eta=0.5$

(c) $\eta=0.1$

(d) $\eta=0.05$

Figure 4: “DIKU” dataset and its $\eta$-MCS for different $\eta$ values.

###  B.2 Visualization of classical and generalized adversarial training over
MCS of “DIKU” dataset

(a) $\ell_{\infty}$-Adv. training.

(b) Generalized $\ell_{\infty}$-Adv. training.

Figure 5: Visualization of the DIKU toy dataset and decision boundaries of
models trained using $0.05$-MCS. Figures from left to right are classical and
generalized adversarial training respectively. The decision boundary between
”K” and ”U” (the right vertical line) clearly exemplifies the influence of
generalized adversarial training.

###  B.3 Training details

Table 3: Hyperparameters of standard and (generalized) adversarial training
over coresets of “DIKU”, MNIST and CIFAR10 datasets. The considered coresets
are RAW, MCS, RAND, and DM. The parameter $\alpha$ is the step size in PGD
attack. We see that the learning rate for MCS is much smaller than others,
which is a quite interesting for future work to explain it in theory.
dataset | coreset | std-lr | adv-lr | $\alpha$
---|---|---|---|---
“DIKU” | RAW | $10^{-3}$ | $10^{-1}$
MCS | $10^{-2}$ | $10^{-3}$
MNIST | RAW, RAND, DM | $10^{-1}$ | $10^{-1}$
MCS | $10^{-3}$ | $10^{-4}$
CIFAR10 | RAW, RAND, DM | $10^{-2}$ | $10^{-2}$
MCS | $10^{-4}$ | $10^{-5}$

###  B.4 Downstream performance of MCS w.r.t. $\ell_{\infty}$-norm

Figure 6: Performance of standard and robust models trained over different
compressed dataset from MNIST. The figures from left to right are standard
training, $\ell_{\infty}$\- and $\ell_{2}$\- adversarial training. The blue,
orange and green lines stand for MCS, RAND, and DM respectively. Here MCSs are
obtained by solving ($\eta$-MCS) w.r.t. $\ell_{\infty}$-norm. The solid,
dashed and dotted lines stand for test, $\ell_{\infty}$\- and $\ell_{2}$\-
robust accuracy respectively. In the horizontal axis, “full” means the
original dataset for MCS and RAND, and $k=5000$ for DM.

Figure 7: Performance of standard and robust models trained over different
compressed dataset from CIFAR10. The figures from left to right are standard
training, $\ell_{\infty}$\- and $\ell_{2}$\- adversarial training. The blue,
orange and green lines stand for MCS, RAND, and DM respectively. Here MCSs are
obtained by solving ($\eta$-MCS) w.r.t. $\ell_{\infty}$-norm. The solid,
dashed and dotted lines stand for test, $\ell_{\infty}$\- and $\ell_{2}$\-
robust accuracy respectively. In the horizontal axis, “full” means the
original dataset for MCS and RAND, and $k=4000$ for DM.

###  B.5 Comparison with classical and generalized adversarial training over
MCS w.r.t. $\ell_{\infty}$-norm

Figure 8: Comparison of classical and generalized adversarial training over
MCS of MNIST dataset. Here MCSs are obtained by solving ($\eta$-MCS) w.r.t.
$\ell_{\infty}$-norm. The figures from left to right are standard training,
$\ell_{\infty}$\- and $\ell_{2}$\- adversarial training. The blue and orange
lines stand for classical and generalized training respectively. The solid,
dashed and dotted lines stand for test, $\ell_{\infty}$\- and $\ell_{2}$\-
robust accuracy respectively.

Figure 9: Comparison of classical and generalized adversarial training over
MCS of CIFAR10 dataset. Here MCSs are obtained by solving ($\eta$-MCS) w.r.t.
$\ell_{\infty}$-norm. The figures from left to right are standard training,
$\ell_{\infty}$\- and $\ell_{2}$\- adversarial training. The blue and orange
lines stand for classical and generalized training respectively. The solid,
dashed and dotted lines stand for test, $\ell_{\infty}$\- and $\ell_{2}$\-
robust accuracy respectively.

###  B.6 Comparison with classical and generalized adversarial training w.r.t.
$\ell_{2}$-norm

Figure 10: Comparison of classical and generalized adversarial training over
MCS of MNIST dataset. Here MCSs are obtained by solving ($\eta$-MCS) w.r.t.
$\ell_{2}$-norm. The figures from left to right are standard training,
$\ell_{\infty}$\- and $\ell_{2}$\- adversarial training. The blue and orange
lines stand for classical and generalized training respectively. The solid,
dashed and dotted lines stand for test, $\ell_{\infty}$\- and $\ell_{2}$\-
robust accuracy respectively.

Figure 11: Comparison of classical and generalized adversarial training over
MCS of CIFAR10 dataset. Here MCSs are obtained by solving ($\eta$-MCS) w.r.t.
$\ell_{2}$-norm. The figures from left to right are standard training,
$\ell_{\infty}$\- and $\ell_{2}$\- adversarial training. The blue and orange
lines stand for classical and generalized training respectively. The solid,
dashed and dotted lines stand for test, $\ell_{\infty}$\- and $\ell_{2}$\-
robust accuracy respectively.