\section{Appendix}

\subsection{Rigorous definition of transformation sets and choice of $\mathcal{S}$}
\label{sec:groups}



In the following we introduce the concepts that are needed to
rigorously define transformation sets that are subsets of the
finite-dimensional (sampled) image space $\mathcal{X} \subset \mathbb{R}^d$.  In particular, because
rotations of continuous angles are not well-defined for sampled images
we need to introduce the space of image functions $\mathcal{I}$ with
elements $I:\mathbb{R}^2 \to [0,255]^3$, i.e.\ $I$ maps Euclidean coordinates
in $\mathbb{R}^2$ to the RGB intensities of an image.  The observed
finite-dimensional vector is then a sampled version of an image
function $I$. Here we assume that the sampling operator is bijective,
with rigorous definitions later in the section.

Next we define subsets in the continuous function space and then
transfer the concept back to the finite-dimensional $\mathcal{X}$.
Let us define the
symmetric group $\mathbb{G}$ of all rotations and horizontal and vertical
translations acting on $\mathcal{I}$.
We denote the elements in the group by $g_\ensuremath{\Delta}$, uniquely parameterized
by $\ensuremath{\Delta} \in \mathbb{R}^3$ and can be represented by a coordinate transform
matrix $G_\ensuremath{\Delta}$, see e.g.~\cite{Cohen16}. Two of the three dimensions
represent the values for the translations and the third represents the
rotation.



The transformed image (function) $g_\ensuremath{\Delta}(I) \in \mathcal{I}$ can be
expressed by $g_\ensuremath{\Delta}(I)(v) = I(G_\ensuremath{\Delta}^{-1}v)$ for each $v\in \mathbb{R}^2$
where $G_\ensuremath{\Delta}$ is the coordinate transform matrix associated with
$\ensuremath{\Delta} \in \mathbb{R}^3$ as in \cite{Cohen16}. For each $I\in \mathcal{I}$, the
group orbit is $\Gorbit{I} := \{g_\ensuremath{\Delta}(I) :
g_\ensuremath{\Delta}\in \mathbb{G}\}$. By definition, the group orbits partition the
space $\mathcal{I}$ and every $I \in \mathcal{I}$ belongs to a unique orbit.
 
\vspace{-0.2in}
\paragraph{Subsets of orbits}
In our setting, requiring invariance in the entire orbit
(i.e.\ with respect to all translations and rotations) is too
restrictive. First of all, large transformations rarely occur in nature
because of physical laws and common human perspectives (an upside down
tower for example). Secondly, in image classification, robustness is
usually only required against adversarial attacks which would not fool
humans, i.e.\ lead them to mislabel the image. If the transformation
set is too large, this requirement is no longer fulfilled.
For this purpose we consider a closed subset
$\SubGroup{I}$ of each group orbit.
It follows from the group orbit definition that for every $I$ it
either belongs to one unique or no such set.


As described in the paragraph of Equation~\eqref{eq:advminapp}, when
observing a (sampled) image $I'$ in the training set, we do not know
where in its corresponding subset $\SubGroup{I'}$ it lies. At the same
time, for our augmentation-based methods, we do not want the set
$\mathcal{S}$ of transformations that we search over
(\emph{transformation search set} for short), to be image
dependent. Instead, in this construction we aim to find $\mathcal{S}$ to
be the smallest set of transformations such that~\eqref{eq:advminapp}
is satisfied. For this purpose, it suffices that the effective search
set of images $\searchset{I'}$ for any image $I' \in \SubGroup{I}$
covers the corresponding subset $\SubGroup{I}$ for all $I$, i.e.
\begin{equation*}
\searchset{I'} := \{g_{\ensuremath{\Delta}}(I'): \ensuremath{\Delta} \in \mathcal{S}\} \supset \SubGroup{I}.
\end{equation*}
Here we give an explicit construction of $\mathcal{S}$ using
the maximal transformation for each subset $\SubGroup{I}$ that is
needed to transform an image of the subset to another.
In particular, we define the maximal transformation vector $\Pert^{\star} \in \mathbb{R}^3$ by the element-wise maximum over all such maximum transformations
\begin{equation*}
(\Pert^{\star})_j := \ensuremath{\operatorname{max}}_{I\in\mathcal{I}} \ensuremath{\operatorname{max}}_{U,U' \in\SubGroup{I}} |(\ensuremath{\Delta})_j| \text{ s.t. } U' = g_{\ensuremath{\Delta}}(U)
\end{equation*}
for $j=1, \dots, 3$. Although the subsets themselves for each image are
not known, using prior knowledge in each application one can usually
estimate the largest possible range of transformations $\Pert^{\star}$
against which robustness is desired or required. For example for images,
one could use experiments with humans to determine for which range of angles
their reaction time to correctly label each image stays approximately constant.
The maximal vector $\Pert^{\star}$ can now be used to
determine the minimal set of transformations $\mathcal{S} =
(-\Pert^{\star}, \Pert^{\star})$.
A simplified illustration for when $\mathcal{I}$ consists of just one
orbit (corresponding for example to one image function and all its
rotated variants) can be found in Figure~\ref{fig:orbits}.

\begin{figure}[!htp]
\begin{center}
\begin{tabular}{ccc}
\hspace{-0.8cm}
\includegraphics[scale=0.42, keepaspectratio=true, trim={0 0 0 0}]{images/orbit1} &
\hspace{-0.8cm}
\includegraphics[scale=0.42, keepaspectratio=true, trim={0 0 0 0}, clip]{images/orbit2} \hspace{0cm}&
\includegraphics[scale=0.42, keepaspectratio=true, trim={0 0 0 0}, clip]{images/orbit3}
\\
(a) & (b) & (c)
\end{tabular}
\caption{Illustration of an example where one group orbit $\mathbb{G}(I) =: \mathcal{I}$ is the entire space of images and $I$ is an arbitrary image in the orbit $\mathbb{G}(I)$. We depict one subset of the orbit $\SubGroup{I}$ and the effective search sets $\searchset{I'}$ for different instantiations $I'\in\SubGroup{I}$ defined by the transformation search set $\mathcal{S}$: (a) $I_1$ on the left boundary of $\SubGroup{I}$, (b) $I_2$ in the interior of $\SubGroup{I}$ and (c) $I_3$ on the right boundary of $\SubGroup{I}$. The effective search sets are centered around each instantation $I_j$. The necessity of symmetry of the minimal set of transformations $\mathcal{S}$ arises from the requirement to cover $\SubGroup{I}$ from both boundary points and the maximum transformation vector $\Pert^{\star}$ that defines $\mathcal{S} = (-\Pert^{\star}, \Pert^{\star})$ is determined by the maximum transformation in $\SubGroup{I}$ (in blue). 
\label{fig:orbits}}
\end{center}
\end{figure}


\paragraph{Sampling issues}
In reality, the observed image is not a function on $\mathbb{R}^2$ but a
vector $z \in \mathbb{R}^{w\times h}$ that is the result of sampling an image
function $I \in \mathcal{I}$. We use $\Phi$ to denote the
sampling operator and hence $z = \Phi(I)$. Then the space of
observed finite dimensional images $\mathcal{X}$ is the range space of $\Phi$.
In order to counter the problem that the sampling operator is in
general not injective, we add another constraint to $\mathcal{I}$ by
requiring that $\Phi$ is bijective so that the quantity $I_z
= \Phi^{-1}(z)$ is well-defined. That is, for a finite-dimensional
image $z\in \mathcal{X}$, there exists exactly one possible continuous image
$I_z \in \mathcal{I}$.  As a consequence, if $z$ and a transformed version
$z'$ exist in $\mathcal{X}$, then $I_z = I_{z'}$.  This is a rather technical
assumption that is typically fulfilled in practice.
In the main text, we also refer to $\Trafo{z}{\ensuremath{\Delta}}
= \Phi(g_\ensuremath{\Delta}(I_z)) \in \mathcal{X}$ as the image corresponding to the sampled
image $z$ transformed by the group element $g_\ensuremath{\Delta}$.



We can now define specific $\SubGroup{I}$ to be the subsets of $\mathbb{G}(I)$ such
that with $z = \Phi^{-1}(I)$, the set $\SubGorbit{z} = \{\Phi(I): I \in \SubGroup{I_z}\}$ corresponds to the support of the marginal distribution $\P$ on $\{\Phi(I): I\in\mathbb{G}(I_z)\}$. We refer to $\SubGorbit{z}$ as transformation sets.
By definition of $\SubGroup{I}$ and bijectivity of $\Phi$, there is an
injective mapping from any $z \in \mathcal{X}$ to the set of transformation sets $\mathcal{G}$.















\subsection{Proof of Theorem~\ref{theo:1}}
\label{sec:theo1proof}
Please refer to Section~\ref{sec:groups} for the necessary notation for this section.
Furthermore, define  $\PopLoss{\text{nat}}(f):= \PopLoss{\text{nat}}(f; 0,0)$.

We prove the first statement of the theorem by contradiction. Let
$f^{\text{rob}}$ be the minimizer of $\PopLoss{\text{rob}}(f)$ and let us assume that
$f^{\text{rob}} \not \in \mathcal{V}$ and in particular that it is constant on all
transformation sets except $\SubGorbit{z} \in \mathcal{G}$ and the
marginal distribution over $\mathcal{G}$ that can be defined as
$P(\{\SubGorbit{X} = U\}) = P(\{X\in U\})$ for any $U\in\mathcal{G}$,
is discrete (for simplicity of presentation) and $\SubGorbit{z}$ has
non-zero probability.

Let's assume that there is at least one transformation set $\SubGorbit{z}$,
on which $f^{\text{rob}}$ is not constant and collect all different values in
the set $A = \{ f^{\text{rob}}(x): x\in \SubGorbit{z} \}$ (with cardinality
strictly bigger than $1$ since $f$ not constant) and denote the
distribution over $x\in\SubGorbit{z}$ by $P_z$.
Since there
is a unique mapping $\Psi$ that maps each $x\in \mathcal{X}$ to a unique
transformation (see Section~\ref{sec:groups}), we can lower bound of
the robust loss as follows for any $z\in\mathcal{X}$:

\begin{align}
& \mathbb{E}\:_{X,Y} \sup_{x' \in\SubGorbit{X}} \ell(f(x'),  Y)\nonumber \\
  = &\:\mathbb{E}\: [\sup_{x' \in \SubGorbit{X}} \ell(f(x'), Y)|X \not\in \SubGorbit{z}] \P(\{X\not\in\SubGorbit{z} \}) + \mathbb{E}\:_{Y|z}[ \sup_{x' \in \SubGorbit{z}} \ell(f(x'), Y)|\SubGorbit{z}] \P(\{X \in \SubGorbit{z}\}) \nonumber \\
  \geq &\:\mathbb{E}\: [\sup_{x' \in \SubGorbit{X}} \ell(f(x'), Y)|X \not \in \SubGorbit{z}] \P(\{X\not \in \SubGorbit{z}\}) + \sup_{a\in A} \int \mathbb{E}\:_{Y|x} \ell(a,Y) d P_z(x) \label{eq:prooflem}
\end{align}
where the inequality follows from
\begin{equation*}
\mathbb{E}\:_{X|z} \mathbb{E}\:_{Y|x} [\sup_{a\in A} \ell(a,Y) | X = x] |\SubGorbit{z} = \int \mathbb{E}\:_{Y|x} \sup_{a\in A}\ell(a,Y) dP_z(x) \geq \sup_{a\in A} \int \mathbb{E}\:_{Y|x} \ell(a,Y) dP_z(x).
\end{equation*}
The right hand side is minimized with respect to the set $A$ by
choosing $A = \{a^\star\}$ where $a^\star$ is defined as {$a^\star = \ensuremath{\operatorname{argmin}}_a \int  \mathbb{E}\:_{Y|x} \ell(a,Y) d
P_z(x)$} because setting $f^\star(x) = a^\star$ for all $x\in \SubGorbit{z}$ and
$f^\star(x) = f^{\text{rob}}(x)$ else leads to equality in equation~\eqref{eq:prooflem} and $f^\star \in \mathcal{F}$ by assumption that $\mathcal{V} \subseteq \mathcal{F}$. 
Morever, since $\P(\{X\in\SubGorbit{z}\}) > 0$ by assumption, choosing $f^\star(x)
= a^\star$ for all $x\in\SubGorbit{z}$ implies
$\PopLoss{\text{rob}}(f^\star)< \PopLoss{\text{rob}}(f^{\text{rob}})$ which contradicts
optimality of $f^{\text{rob}}$ and thus proves the first statement of the
theorem.

For the second statement let us  rewrite
\begin{align*}
\PopLoss{\text{rob}}(f) &= \PopLoss{\text{nat}}(f) + [\PopLoss{\text{rob}}(f) - \PopLoss{\text{nat}}(f)] \\
&=  \mathbb{E}\: \ell(f(X,\ensuremath{Y}) +  \underbrace{\mathbb{E}\: [\ensuremath{\operatorname{max}}_{\ensuremath{\Delta}' \in \mathcal{S}} \ell(f(\Trafo{X}{\ensuremath{\Delta}'}),\ensuremath{Y}) - \ell(f(X),\ensuremath{Y})]}_{\tilde{R}(f)}
\end{align*}
By the first statement we know that the set of invariant functions that minimize the robust loss
\begin{equation*}
F^{\text{rob}} := \{f \in \mathcal{V}: \PopLoss{\text{rob}}(f) \leq \PopLoss{\text{rob}}(f') \quad \forall f' \in \mathcal{F}\}
\end{equation*}
is non-empty.
For all $f\in F^{\text{rob}}$, it holds by definition of $\mathcal{V}$ that 
$\tilde{R}(f) = 0$.

Since $\mathcal{V}(\ensuremath{R}) \subseteq \mathcal{V}$, the minimizers $f^{\min}$
of~\eqref{eq:regnat} satisfy
$\PopLoss{\text{nat}}(f^{\min}) \leq \PopLoss{\text{nat}}(f)$ for all
$f\in \mathcal{V}$. But because $f^{\min}$ in $\mathcal{V}$ we have $\PopLoss{\text{rob}}(f)
= \PopLoss{\text{nat}}(f)$ and it directly follows that $f^{\min} \in F^{\text{rob}}$.  The
same argument goes through for~\eqref{eq:regadv} since for all
$f \in \mathcal{V}$, we have $\PopLoss{\text{rob}}(f) = \PopLoss{\text{nat}}(f)$. This
concludes the proof of the theorem.



























\subsection{Proof of Theorem~\ref{theo:tradeoff}}
\label{sec:proofcor}

On a high level, similar to the proof of Theorem~\ref{theo:1}, we can
construct a minimizer of the natural loss $f^\star \mathcal{V}$ given the
assumption that $Y \perp \!\!\! \perp  X|\SubGorbit{z}$.
Since on $\mathcal{V}$ both losses are equivalent, together with
Theorem~\ref{theo:1} this shows that the robust minimizer also minimizes the
unconstrained natural loss.


Assume $\ensuremath{f^{\text{nat}}} \not \in \mathcal{V}$ minimizes $\PopLoss{\text{nat}}(f)$, and in
particular, it is constant on all transformation sets except
$\SubGorbit{z}$ for some $z\in\mathcal{X}$.  Again by existence of a mapping
$\Psi$ and by assumption  $Y \perp \!\!\! \perp  X|\SubGorbit{z}$
we can write for any $f$
\begin{align}
\PopLoss{\text{nat}}(f) &= \mathbb{E}\:_{X, Y} \ell(f(X), Y) \label{eq:lnat}\\
&= \mathbb{E}\:[\ell(f(X),Y) | X\not\in\SubGorbit{z}]\P(\{X\not \in \SubGorbit{z}\}) + \mathbb{E}\:[\ell(f(X),Y) | \SubGorbit{z} ] \P(\{X \in \SubGorbit{z}\}) \nonumber\\
&= \mathbb{E}\:[\ell(f(X),Y) | X\not\in\SubGorbit{z}]\P(\{X\not \in \SubGorbit{z}\}) +   \mathbb{E}\: \big[ \mathbb{E}\:_Y [\ell(f(X),Y)] | \SubGorbit{z} \big] \P(\{X \in \SubGorbit{z}\}).\nonumber
\end{align}
We then obtain 
\begin{align}
\mathbb{E}\: \big[ \mathbb{E}\:_Y [\ell(f(X),Y)] | \SubGorbit{z}\big] &= \int \mathbb{E}\:[\ell(f(x),Y)|x] d P_z(x) \nonumber\\
&\geq \int \ensuremath{\operatorname{min}}_{x'\in\SubGorbit{z}} \mathbb{E}\:[\ell(f(x'),Y)|x']  d P_z(x) = \mathbb{E}\: \big[ \mathbb{E}\:_Y [\ell (f^\star(X), Y)] | \SubGorbit{z}\big] \label{eq:ineq}
\end{align}
when setting
$f^\star(x)= \ensuremath{\operatorname{min}}_{x\in\SubGorbit{z}} \mathbb{E}\:_Y\ell(\ensuremath{f^{\text{nat}}}(x),Y)
| \SubGorbit{z}$ for all $x\in\SubGorbit{z}$ and $f^\star(x)
= \ensuremath{f^{\text{nat}}}(x)$ otherwise. Together with equation~\eqref{eq:lnat},
we thus have that $\PopLoss{\text{nat}}(f^\star)
= \PopLoss{\text{nat}}(\ensuremath{f^{\text{nat}}}) \leq \PopLoss{\text{nat}}(f)$ for all $f\in\mathcal{F}$
by definition of $\ensuremath{f^{\text{nat}}}$.



If additionally the support of $P_z$ is equal to $\SubGorbit{z}$ and $\ell$ is injective,
the inequality~\eqref{eq:ineq} becomes a strict inequality for $\ensuremath{f^{\text{nat}}}\not \in \mathcal{F}$
and hence we have $\PopLoss{\text{nat}}(f^\star) < \PopLoss{\text{nat}}(\ensuremath{f^{\text{nat}}})$ which contradicts
the definition of $\ensuremath{f^{\text{nat}}}$ being the minimizer of the natural loss.




 
 
 
 
 
 
 
 
 
 
 
 
 
 









\section{Two-stage STN}
\label{sec:twostage}

Since STNs are known to be sensitive to hyperparameter settings and thus
 difficult to train 
end-to-end~\cite{Tai19}, we apply the following two-stage
procedure to simulate its functionality: (1) we first train a ResNet-32 as a localization regression
network (LocNet) to predict the attack perturbation separately
by learning from a training set, which contains perturbed images and uses the
transformations as the prediction targets; (2) at the same time we train a
ResNet-32 classifier with data augmentation, namely random translations and 
rotations; (3) during the test phase, the output of the LocNet is used by a
spatial transformer module that transforms the image before entering
the pretrained classifier. We refer to this two-stage STN as \text{STN+}.

\paragraph{LocNet and Classifier} For the classifiers, we take the two models trained on CIFAR-10 and
SVHN using standard data augmentation and random rotations from our
previous experiments. Since we do not expect the regressors (or
LocNets) to be perfect in terms of prediction capability, there will
still be some transformation left after the regression stage.  Thus,
the classifiers should effectively see a smaller range of
transformations than without the inclusion of a LocNet and transformer module.
The training procedure used to train the classifiers is described in Section~\ref{sec:exp_details}.

\paragraph{Effect of rendering edges on LocNet} The LocNet is trained on zero padded
-- suffix $(c)$ -- as well as reflect padded inputs -- suffix $(r)$
-- for comparison.
 The former possibly yields an unfair advantage of this approach compared to other methods as the neural network can exploit the edges (induced through zero padding) to learn the transformation parameters.
Therefore, we also consider reflection padding to assess the effect of the different paddings on final performance.  
Nonetheless, zero padding is consistent with the augmentation
setting for the end-to-end trained networks and regularized methods
and was also the choice considered by~\cite{Engstrom17}.
For completeness we also show results when using reflection padding for
training LocNet although it lacks comparability with the other
methods since attacks should be reflection-padded as well.



\paragraph{Minimizing loss of information in the prediction transformation process} In the spatial transformer module we compare two variants of handling the
labels predicted by the LocNet. We can either back-transform the
transformed image with the negative predicted labels, which
will, under the assumption that the regressor successfully learnt
object orientations, turn back the image but potentially result in
extra padding space before we feed the images into the
classifier. Alternatively, we can subtract the predicted
transformation from the attack transformation, then use the remaining
transformation as the new ``attack transformation''.  The latter will
result in much smaller padding areas, if the LocNet is performing
well. From the experimental results we do see a big drop if we naively
transform images twice.  We denote the former method as ``naive'' and
latter as ``trick''.

\paragraph{Observed results}
For CIFAR-10, this two-stage classifier achieved relatively high grid
accuracies. However, the obtained accuracies are still lower than
expected, given that the LocNet is allowed to learn rotations with a
separately trained regressor on the transformed training set. For SVHN
we also see a gain compared to adversarial training without
regularizer. However, the performance still lags behind the accuracies
obtained by the regularizers. The results are summarized in
Table~\ref{tab:two-stage-eval}.


\begin{table}[htbp]
    \caption{Accuracies of two-stage \text{STN}\, (\text{STN+}) under different settings. Details are provided in Section~\ref{sec:twostage}. \label{tab:two-stage-eval}}
\begin{center}
\vskip 0.15in
 
 {\setlength{\tabcolsep}{4pt}
   \begin{tabular}{c c c c c }
Dataset & \text{STN+}(c) trick & \text{STN+}(r) trick & \text{STN+}(c) naive & \text{STN+}(r) naive\\
\hline
SVHN (nat) &94.92 & 95.51 & 94.92 & 95.51\\
 \qquad\quad (rob) &90.95 & 90.28 & 64.91 & 59.68\\
\hdashline
CIFAR10 (nat) &91.29 & 90.99 & 91.29 & 90.99\\
 \qquad\quad (rob) &83.05 & 84.31 & 44.88 & 42.84\\
\hline
    \end{tabular}}
  \end{center}
\end{table}


\section{More experimental results}
In this section we discuss additional experimental results that we collected and and analyzed.

\subsection{Stability to selection of regularization parameter $\lambda$}

\input{lambda_plots}
Figures~\ref{fig:grid_nat_overlambda_rnd} and~\ref{fig:grid_nat_overlambda_wo} show the test grid and test natural accuracy as a function of the regularization parameter $\lambda$. We observe that the regularization methods outperform unregularized methods in terms of grid accuracy in a large range of $\lambda$ values. 










\subsection{Additional experimental results}
\label{sec:moreresults}




\begin{table}[H]
  \caption{Mean accuracies of models trained \textit{without} regularized adversarial training. Standard errors are shown in parentheses. \label{tab:compareadv1}}
\begin{center}
 
 {\setlength{\tabcolsep}{4pt}
   \begin{tabular}{c c c c c}
   & std & std* & AT(rob, Wo-10) & AT(mix, \woabb{10})\\
  \hline
  SVHN (nat) & 95.48 (0.15) & 93.97 (0.09) &96.03 (0.03) & 96.56 (0.07)\\
   \qquad\quad(rob) & 18.85 (1.27) & 82.60 (0.23) & 90.35 (0.27) & 88.83 (0.10)\\
  \hdashline
  CIFAR-10 (nat) & 92.11 (0.18) & 89.93 (0.18) & 91.76 (0.23) & 93.44 (0.19)\\
   \qquad\quad\quad(rob) & 9.52 (0.66) & 58.29 (0.60) & 71.17 (0.26) & 68.14 (0.48) \\
    \hdashline
  CIFAR-100 (nat) & 70.23 (0.18) & 66.62 (0.37) & 68.79 (0.34) & 73.03 (0.13)\\
   \qquad\quad\quad(rob) & 5.09 (0.25) & 28.53 (0.25) & 38.21 (0.10) & 35.93 (0.24)\\
  \hline

 \end{tabular}}
\end{center}
\end{table}
\vspace{-0.2in}

\paragraph{Mixed batch experiments} 
In addition to the results reported in the main text, in this section we also report results on more experiments that use the ``mixed batch'' setting, meaning that the gradient of the loss is taken with respect to both the adversarial and natural examples. This is common practice in the $\ell_p$ adversarial example literature \cite{Kannan18} and we denote this approach by ``mix''. As can be seen in Table~\ref{tab:compareadv1}, for adversarial training a mixed batch improves natural accuracy at the expense of test grid performance. For the regularization methods, we observe a much small, and not consistent, effect of the batch type as can be seen in Table~\ref{tab:compareadv3}. For example, comparing ALP(\text{rob}, $\cdot$) vs.\ ALP(\text{mix}, $\cdot$) shows that the performance differences are mostly not significant.

\begin{table}[H]
  \caption{Mean accuracies of models trained with various forms of
  regularized adversarial training, using the \text{KL}\, regularization
  function. Standard errors are shown in
  parentheses. \label{tab:compareadv2}}
\begin{center}
\vskip 0.15in
 
 {\setlength{\tabcolsep}{3pt}
   \begin{tabular}{c c c c c c }
   & \makecell{\text{KL}(\text{nat}, \\text{rnd})} & \makecell{\text{KL}(\text{nat},\\ Wo-10)} & \makecell{\text{KL}(rob,\\ Wo-10)} & \makecell{\text{KL-C}(mix,\\ S-PGD)} & \makecell{KL(nat,\\ S-PGD)}  \\
  \hline
  SVHN (nat) &  96.16 (0.10) & 96.00 (0.02) & 96.13 (0.07) & 96.14 (0.04) & 96.54 (0.01) \\
   \qquad\quad (rob) &  90.69 (0.05) & 92.27 (0.09) & 92.71 (0.09) & 92.42 (0.03) &{\bf 92.62} (0.03) \\
  \hdashline
  CIFAR-10 (nat) &  89.33 (0.16) & 90.83 (0.18) & 90.41 (0.05) & 89.98 (0.21) & 89.82 (0.13) \\
   \qquad\quad\quad (rob) &  73.50 (0.19) & 77.34 (0.19) & 77.47 (0.28) & {\bf 78.93} (0.23) & 78.89 (0.07)\\
  \hline

 \end{tabular}}
\end{center}
\end{table}

\begin{table}[H]
  \caption{Mean accuracies of models trained with various forms of regularized adversarial training, using the \ensuremath{\ell_2}\, and \text{ALP}\, regularization functions. Standard errors are shown in parentheses. \label{tab:compareadv3}}
\begin{center}
\vskip 0.15in
 
 {\setlength{\tabcolsep}{3pt}
   \begin{tabular}{c c c c c c c c}
   & \makecell{\ensuremath{\ell_2}(\text{nat}, \\ \woabb{10})} & \makecell{\ensuremath{\ell_2}(\text{rob},\\ Wo-10)} & \makecell{ALP(mix,\\ Wo-10)}  & \makecell{ALP(\text{rob},\\ Wo-10)} & \makecell{ALP(mix,\\ Wo-20)} & \makecell{ALP(\text{rob},\\ S-PGD)} & \makecell{ALP(mix,\\ S-PGD)} \\
  \hline
  SVHN (nat) &  96.05 (0.04) &96.53 (0.03) & 96.41 (0.07) & 96.3 (0.09) & 96.39 (0.04) & 96.11 (0.08)   & 96.30 (0.09)\\
   \qquad\quad (rob) & 92.16 (0.05) &92.55 (0.08) & 92.17 (0.11) & 92.04 (0.19) & 92.48 (0.05) &92.32 (0.17)& 92.42 (0.20)\\
  \hdashline
  CIFAR-10 (nat) &  88.32 (0.13) & 90.53 (0.16) & 91.13 (0.13) & 90.11 (0.25) & 90.67 (0.12) & 89.85 (0.27) & 89.70 (0.10)\\
   \qquad\quad\quad (rob) &  75.46 (0.25) & 77.06 (0.16)& 75.89 (0.23)	& 75.90 (0.31) & 76.72 (0.21)	& 77.80 (0.17) & 77.72 (0.35)\\
   \hdashline
   CIFAR-100 (nat) &  - & - & 68.54 (0.27) & - & 68.04 (0.27) & 89.82 (0.13) & 68.44 (0.39)\\
   \qquad\quad\quad (rob) &  - & - & 49.30 (0.33) & - & 49.98 (0.31) & 78.89 (0.07) & 52.58 (0.20)\\
  \hline

 \end{tabular}}
\end{center}
\end{table}

\begin{table}[H]
  \caption{Mean standard and grid (\text{rob}) accuracies of models trained with various forms of regularized adversarial training, using the \text{rnd}\:(equivalent to Wo-1), Wo-10 and Wo-20 defense mechanisms for \text{KL}\:(left) and \text{ALP}\:(right). Standard errors are shown in parentheses. \label{tab:wok_diffk}}
  \begin{center}
\vskip 0.15in
 
 {\setlength{\tabcolsep}{3pt}
   \begin{tabular}{c c c c : c c c }
   & \makecell{\text{KL}(\text{nat},\\ \woabb{1})} & \makecell{\text{KL}(\text{nat}, \\ \woabb{10})} & \makecell{\text{KL}(\text{nat},\\ \woabb{20})}  & \makecell{ALP(\text{rob},\\ \woabb{1})} & \makecell{ALP(\text{rob},\\ \woabb{10})} & \makecell{ALP (\text{rob},\\ \woabb{20})} \\
  \hline
  CIFAR-10 (nat) &  89.34 (0.16) & 90.83 (0.18) & 89.33 (0.22) & 89.47 (0.04) & 90.11 (0.25) & 90.62 (0.07)\\
   \qquad\quad (rob) & 73.40 (0.19) & 77.34 (0.19) & 77.52 (0.16) & 73.22 (0.14) & 75.90 (0.31) & 76.78 (0.15)\\
  \hline
 \end{tabular}}
\end{center}
\end{table}



\begin{table}[H]
  \caption{Mean accuracies of models trained with various forms of augmented training, i.e.\ unregularized and regularized data augmentation. Standard errors are shown in parentheses. \label{tab:compareadv4}}
\begin{center}
\vskip 0.15in
 
 {\setlength{\tabcolsep}{3pt}
   \begin{tabular}{c c c c c c c}
   &  std* &  \ensuremath{\ell_2}(nat, rnd) & KL(nat, rnd) & ALP(rob, rnd) & KL(rob, rnd) & ALP(mix, rnd) \\
  \hline
  SVHN (nat) &  93.97 (0.09)&96.34 (0.08)&96.16 (0.10)&96.09 (0.06)&96.23 (0.08)&96.19 (0.07)   \\
   \qquad\quad (rob) & 82.60 (0.23)&90.51 (0.15)&90.69 (0.05)&90.48 (0.16)&90.92 (0.17)&90.48 (0.15)\\
  \hdashline
  CIFAR-10 (nat) & 89.93 (0.18)&87.80 (0.11)&89.34 (0.16)&88.75 (0.18)&89.47 (0.04)&89.43 (0.28) \\
   \qquad\quad\quad (rob) &  58.29 (0.60)&71.60 (0.27)&73.50 (0.19)&71.49 (0.30)&73.22 (0.14)&71.97 (0.11)\\
  \hline
 \end{tabular}}
\end{center}
\end{table}

\vspace{-0.2in}
\begin{table}[H]
  \caption{Mean accuracies of models trained with various forms of regularized adversarial training. Standard errors are shown in parentheses. \label{tab:compareadv5}}
\begin{center}
\vskip 0.15in
 
 {\setlength{\tabcolsep}{4pt}
   \begin{tabular}{c c c c c c}
   & \text{ALP}(\text{nat}, \woabb{10})& \ensuremath{\ell_2}(\text{nat}, \woabb{10})&	\text{KL-C}(nat, \woabb{10}) &	\text{KL}(\text{nat}, \woabb{10}) \\
  \hline
  SVHN (nat) &  96.39 (0.03)&	96.05 (0.04) &96.18 (0.06)&	96.00 (0.02)   \\
   \qquad\quad (rob) & 91.98 (0.13)	&92.16 (0.05)	&91.99 (0.12)&	92.27 (0.09)\\
  \hdashline
  CIFAR10 (nat) & 88.78 (0.11) &	88.32 (0.13)&	89.61 (0.09)&	90.83 (0.18) \\
   \qquad\quad\quad (rob) &  75.43 (0.13)&	75.46 (0.25)&	76.15 (0.23)&	77.34 (0.19)\\
  \hline
 \end{tabular}}
\end{center}
\end{table}





\input{tables/core_table.tex}



\clearpage
\newpage
\subsection{Regularization effect on range of incorrect angles}
\vspace{-0.2in}
\begin{figure*}[ht]
\begin{center}
\begin{tabular}{cccc}
\hspace{-.2cm}
\includegraphics[scale=0.45, keepaspectratio=true, trim={0 0 0 0}, clip]{figures/cifar10/angles/CIFAR-10_test_misclassified_angles_standard_k1_7KcLK6b65F_1060253} &
\hspace{-0cm}
\includegraphics[scale=0.45, keepaspectratio=true, trim={0 0 0 0}, clip]{figures/cifar10/angles/CIFAR-10_test_misclassified_angles_rob50_k1_7uDN6eqCvd_1058256} &
\hspace{-.4cm}
\includegraphics[scale=0.45, keepaspectratio=true, trim={0 0 0 0}, clip]{figures/cifar10/angles/CIFAR-10_test_misclassified_angles_rob100_k1_EJRsnFcNuu_1059068} &
\hspace{-.5cm}
\includegraphics[scale=0.45, keepaspectratio=true, trim={0 0 0 0}, clip]{figures/cifar10/angles/CIFAR-10_test_misclassified_angles_core_k1_4hbWroJkyE_1058258} \\
{\small Standard} & {\small$\text{AT}(\text{mix},\text{rnd})$} & {\small$\text{AT}(\text{rob},\text{rnd})$} &  {\small$\text{ALP}(\text{mix},\text{rnd})$}
\end{tabular}
\begin{tabular}{cccc}
\hspace{3.4cm}
&
\hspace{-0cm}
\includegraphics[scale=0.45, keepaspectratio=true, trim={0 0 0 0}, clip]{figures/cifar10/angles/CIFAR-10_test_misclassified_angles_rob50_k10_CBD4EK3fGB_1058325} &
\hspace{-.4cm}
\includegraphics[scale=0.45, keepaspectratio=true, trim={0 0 0 0}, clip]{figures/cifar10/angles/CIFAR-10_test_misclassified_angles_rob100_k10_7RP3kP6xvz_1059077} &
\hspace{-.5cm}
\includegraphics[scale=0.45, keepaspectratio=true, trim={0 0 0 0}, clip]{figures/cifar10/angles/CIFAR-10_test_misclassified_angles_core_k10_KFXdX5dQUG_1058343} \\
{  }& {\small$\text{AT}(\text{mix},{\woabb{10}})$} & {\small$\text{AT}(\text{rob},{\woabb{10}})$} & {\small$\text{ALP}(\text{mix},{\woabb{10}})$}
\end{tabular}
\caption{For 100 randomly chosen examples from the CIFAR-10 dataset, we show which rotations lead to a misclassification by various models. Each row corresponds to one example and each column to one angle in the interval $[-30^\circ, 30^\circ]$. A dark red square indicates that the corresponding example was misclassified after being rotated by the corresponding angle. The visualization for $\text{AT}(\text{mix},\text{rnd})$ is more fragmented than for $\text{AT}(\text{rob},\text{rnd})$ and $\text{ALP}(\text{mix},\text{rnd})$ and the visualization for $\text{AT}(\text{mix},{\woabb{10}})$ is more fragmented than for $\text{AT}(\text{rob},{\woabb{10}})$ and $\text{ALP}(\text{mix},{\woabb{10}})$.}
\label{fig:angles_k10}
\end{center}
\end{figure*}

\section{Acknowledgements}
We thank Ludwig Schmidt for helpful discussion, Nicolai Meinshausen
for valuable feedback on the manuscript and Luzius Brogli for initial
experiments.  FY was supported by the Institute for Theoretical
Studies ETH Zurich, the Dr. Max R\"ossler and Walter Haefner
Foundation and the Office of Naval Research Young Investigator Award
N00014-19-1-2288.





\section{Conclusion}
In this work, we have explored how regularized augmentation-based
methods compare against specialized spatial equivariant networks in
terms of robustness against small translations and
rotations. Strikingly, even though augmentation can be applied to
encourage \emph{any} desired invariance, the regularized methods adapt
well and perform similarly or better than specialized networks.
Furthermore, we have introduced a theoretical framework incorporating
many forms of regularization techniques that have been proposed in the
literature. Both theoretically and empirically, we showed that for
transformation invariances and under certain practical assumptions on
the distribution, there is no trade-off between natural and
adversarial accuracy which stands in contrast to the debate around
$\ell_p$-perturbation sets. In summary, it is advantageous to replace
unregularized with regularized training for both augmentation
and adversarial defense methods. With regard to the regularization
parameter choice we have seen that improvements can be
obtained for a large range of $\lambda$ values, indicating that this
additional hyperparameter is not difficult to tune in practice.  In
future work, we aim to explore whether specialized
architectures can be combined with regularized adversarial training to
improve upon the best results reported in this work.














\section{Experimental setup}\label{sec:experimental_setup}

In our experiments, we compare invariance-inducing regularization
incorporated via various augmentation-based methods (as described in
Section~\ref{sec:diffreg}) used on standard networks and
representative spatial equivariant networks trained using standard
optimization procedures.


 
 
 
 




  




\subsection{Spatial equivariant networks}
\label{sec:spatnet}
We compare the robust prediction accuracies from
networks trained with the regularizers with three specialized architectures, designed to be
equivariant against spatial transformations and translations:
(a) \text{G-ResNet44}\:\:(\text{GRN}) \cite{Cohen16} using p4m convolutional layers (90 degree rotations, translations and mirror reflections) on CIFAR-10;
(b) Equivariant Transformer Networks (ETN) \cite{Tai19}, a generalization of Polar Transformer Networks (PTN) \cite{Esteves18}, on SVHN;
and (c) Spatial Transformer Networks (STN) \cite{Jaderberg15} on SVHN.
A more comprehensive discussion of the literature on equivariant
networks can be found in
Sec.~\ref{sec:related}.
We choose the architectures listed above based on
availability of reproducible code and previously reported state-of-the art
standard accuracies on SVHN and CIFAR10.

We train \text{GRN}, \text{STN}\,and \text{ETN}\, using standard augmentation as described in
Sec.~\ref{sec:exp_details} (\ensuremath{\text{std}}) and random rotations in addition (\aug{\ensuremath{\text{std}}}). 
Out of curiosity we also trained a ``two-stage'' STN where we train
the localization network separately in a supervised fashion. Specifically, we use a randomly transformed version of the training data, treating the transformation parameters as prediction targets. 
Details about the implementation and results can be found in Sec.~\ref{sec:twostage} in the Appendix.

 


\subsection{Transformations}
The transformations that we
consider in Sec.~\ref{sec:results} are small rotations (of up to
$30^\circ$) and translations in two dimensions of up to 3 px
corresponding to approx.\ 10\% of the image size.  For augmentation
based methods we need to generate such small transformations for a
given test image.  Although the definition of a transformation
$\Trafo{X}{\ensuremath{\Delta}}$ in the theoretical section using the corresponding
continuous image functions is clean, we do not have acccess to the
continuous function in practice since the mapping is in general not
bijective.  Instead, we use bilinear interpolation, as implemented in
TensorFlow and in a differentiable version of a transformer \cite{Jaderberg15}
for first order attack and defense methods.


\begin{figure}[htbp]
\begin{minipage}[c]{0.45\textwidth}
  \begin{center}
    \begin{minipage}[t]{0.3\hsize}
      \vspace{0pt}
      \includegraphics[width=\textwidth]{figures/example_first_page/CIFAR-10_test_correct_almost_all_angles_standard_k1_0}
    \end{minipage}
    \begin{minipage}[t]{0.3\hsize}
      \vspace{0pt}
      \includegraphics[width=\textwidth]{figures/example_first_page/CIFAR-10_test_correct_almost_all_angles_standard_k1_pert_0}
    \end{minipage}

    \begin{minipage}[t]{0.3\hsize}
      \begin{center}
        \small (a)
      \end{center}
    \end{minipage}
    \begin{minipage}[t]{0.3\hsize}
      \begin{center}
        \small (b)
      \end{center}
    \end{minipage}
  \end{center}
\end{minipage}
\begin{minipage}[c]{0.55\textwidth}
 
 
\vskip -0.1in
\caption{\small Example images and classifications by the Standard model.
 
(a) An image that is correctly classified for most of the rotations in the considered grid.
  (b) One rotation for which the image shown in (b) is misclassified as ``airplane''. \label{fig:ex_trafo}
}\end{minipage}
\end{figure}



On top of interpolation, rotation also creates edge artifacts at
the boundaries, as the image is only sampled in a bounded set.

The empty space that
results from translating and rotating an image is filled with black
pixels (\emph{constant padding}) if not noted otherwise. Fig.~\ref{fig:ex_trafo} (b) shows an example.
\cite{Engstrom17} additionally
analyze a ``black canvas`` setting where the images are padded with
zeros prior to applying the transformation, ensuring that no
information is lost due to cropping. Their experiments show that the
reduced accuracy of the models cannot be attributed to this
effect. Since both versions yield similar results, we report results
on the first version of pad and crop choices, having input images of the same size as the
original.


\subsection{Attacks and defenses}\label{sec:attacks_defenses} 

The attacks and defenses we choose essentially follow the setup in
\cite{Engstrom17}. The \textit{defense} refers to the procedure at
training time which aims to make the resulting model robust to
adversarial examples. It generally differs from the (extensive)
\textit{attack} mechanism performed at evaluation time to assess the
model's robustness due to computational constraints.

\textbf{Considered attacks} First order methods such as projected
gradient descent that have proven to be most effective for
$\ell_\infty$ transformations are not optimal for finding adversarial
examples with respect to rotations and translations. In particular,
our experiments confirm the observations reported in~\cite{Engstrom17}
that the most adversarial examples can be found through a {\bf grid
  search}.
For the grid search attack, the compact
perturbation set $\mathcal{S}$ is discretized to find the transformation
resulting in a misclassification with the largest loss $\ell$. In contrast to the case of
$\ell_\infty$-adversarial examples, this method is computationally
feasible for the 3-dimensional spatial parameters.
 
 
 
We consider a default grid of 5 values per translation direction and
31 values for rotation, yielding 775 transformed examples that are
evaluated for each $X_i$. We refer to the accuracy attained under this
attack as \textit{grid accuracy}. How did we ensure the number of
transformations in the grid are sufficient? Considering
with a finer grid of 7500 transformations for a subset of the experiments, summarized in Table~\ref{tab:finer_grid}, showed only  minor reductions
in accuracy compared to the coarser grid. Therefore, we chose the latter for computational reasons.

\textbf{Considered defenses} 
For the adversarial example which maximizes
either the loss or regularization function, we use the following
defense mechanisms:

\begin{itemize}

\item \textbf{$\text{worst-of-$k$}$:}
  At every iteration $t$, we sample $k$ different perturbations for
  each image in the batch. The one resulting in the highest function
  value is used as the maximizer.  Most of our experiments are
  conducted with $k=10$ consistent with~\cite{Engstrom17} as a higher
  $k$ only improved performance minimally (see Table~\ref{tab:compareadv3}).

\item \textbf{Spatial PGD:} In analogy to
common practice for $\ell_p$ adversarial training as in
e.g.~\cite{Szegedy13, Madry18}, 
the \text{S-PGD}\, mechanism uses projected gradient descent with respect
to the translation and rotation parameters with projection
on the constrained set $\mathcal{S}$ of transformations.
We consider 5 steps of PGD, starting from a random initialization,
with step sizes of $[0.03, 0.03, 0.3]$ (following \cite{Engstrom17})
for horizontal-, vertical translation and rotation respectively. A
discussion on the discrepancy between S-PGD as a defense and attack
mechanism can be found in Section~\ref{sec:moreresults}.

\item \textbf{Random:} Data augmentation with a distinct random perturbation per image and iteration. This can be seen as the most naive ``adversarial'' example as it corresponds to $\text{worst-of-$k$}$ with $k=1$.
\end{itemize}


\subsection{Training details}\label{sec:exp_details}



The experiments are conducted with deep
neural networks as the function space $\mathcal{F}$ and $\ell$ is the cross-entropy loss.  
In the main paper we consider the datasets SVHN \cite{Netzer11} and
CIFAR-10 \cite{Krizhevsky09}. For the non-specialized architectures,
we train a ResNet-32 \cite{He16}, implemented in TensorFlow
\cite{Abadi2015}. For the Transformer networks STN and ETN
we use a 3-layer CNN as localization according to the default settings in the provided code of
both networks for SVHN and rot-MNIST.
For a subset of the experiments we also report
results for CIFAR-100 \cite{Krizhevsky09}
in the Appendix.

We train the baseline models with standard data augmentation:
random left-right flips and random translations of $\pm 4\textrm{px}$ followed
by normalization.  Below we refer to the models trained in this
fashion as ``\ensuremath{\text{std}}''.  For the models trained with one of the defenses
described in Sec.~\ref{sec:attacks_defenses}, we only apply random
left-right flipping since translations are part of the adversarial
search. The special case of data augmentation (with translations and
rotations, i.e.\ the defense ``random'') without regularization is
refered to as $\aug{\ensuremath{\text{std}}}$. 

For optimization of the empirical training loss, we run standard
minibatch SGD with a momentum term with parameter $0.9$ and weight
decay parameter $0.0002$.  We use an initial learning rate of $0.1$
which is divided by $10$ after half and three-quarters of the training
steps. Independent of the defense method, we fix the number of
iterations to $80000$ for SVHN and CIFAR-10, and to $120000$ for
CIFAR-100. For comparability across all methods, the number of unique
original images in each iteration is $64$ in all cases. For the
baselines $\ensuremath{\text{std}}, \aug{\ensuremath{\text{std}}}$ and $\text{Adversarial training}$, we additionally trained with a
conventional batch size of $128$ and report the higher accuracy of
both versions. For the regularized methods, the value of
  $\lambda$ is chosen based on the test grid accuracy. All models are
trained using a single GPU on a node equipped with an NVIDIA GeForce
GTX 1080 Ti and two 10-core Xeon E5-2630v4 processors.



\begin{figure}[htbp]
   \begin{center}


       \includegraphics[width=.45\textwidth]{figures/cifar10_new/test_grid_accuracy_runtime_pruned.pdf}





   \end{center}
     \caption{\small Mean runtime for different methods on CIFAR-10. The connected points correspond to \text{Wo-$k$}\, defenses with $k \in \{1, 10, 20\}$.  \label{fig:runtime}
     }
\end{figure}


\section{Empirical Results}
\label{sec:results}


We now compare the {natural test accuracy} (standard accuracy on the
test set, abbreviated as \emph{nat}) and test grid accuracy (as
defined in Sec.~\ref{sec:attacks_defenses}, abbreviated as \emph{rob})
achieved by standard and regularized (adversarial) training techniques
as well as specialized spatial equivariant architectures described in
Sec.~\ref{sec:spatnet}.  For clarity of presentation, the naming
convention we use in the rest of the paper consists of the following
components: (a) \texttt{Reg}\:: refers to what regularizer was used (\text{AT},
\text{ALP}, \ensuremath{\ell_2}, \text{KL}, or \text{KL-C} \: as defined in
Section~\ref{sec:diffreg}); (b) \texttt{batch}: indicates whether the
gradient of the loss is taken with respect to the adversarial examples
(\text{rob}), natural examples (\text{nat}) or both (\text{mix}), and (c) \texttt{def}: the
mechanism used to find the adversarial example, including random
(\text{rnd}), \wo{k} (\woabb{k}) and spatial PGD (\text{S-PGD}) as described in
Sec.~\ref{sec:attacks_defenses}.  Thus, \texttt{Reg}\: (\texttt{batch}, \texttt{def})
corresponds to using \texttt{Reg}\: as the regularization function, the
examples defined by \texttt{batch}\; in the gradient of the loss and the
defense mechanism \texttt{def}\, to find the augmented or adversarial
examples.

In Table~\ref{tab:regspat}, we report results for a subset of the \texttt{Reg}\: (\texttt{batch}, \texttt{def}) combinations to facilitate comparisons. Tables with many more combinations can be found Tables~\ref{tab:compareadv1}--\ref{tab:compareadv5} in the Appendix.
We report averages (standard errors are contained in Tables~\ref{tab:compareadv1}--\ref{tab:compareadv5}) computed over five training runs with identical
hyperparameter settings.  
We compare all
methods by computing absolute and relative error reductions (defined
as $\frac{\text{absolute error drop}}{\text{prior error}}$). It is
insightful to present both numbers since the absolute values vary
drastically between datasets. 







\input{table_rat}
\input{table2_main}

\textbf{Effectiveness of augmentation-based invariance-inducing
  regularization} In Table~\ref{tab:regspat} (top), the three leftmost
columns represent unregularized methods which all perform worse in
grid accuracy than regularized methods and the two right-most columns
represent adversarial examples with respect to the classification
cross entropy loss found via S-PGD. When considering the three
regularizers (\text{KL}, \ensuremath{\ell_2}, \text{ALP}) with the same \texttt{batch}\, and
\texttt{def}\, (here chosen to be ``\text{rob}'' and \woabb{10}) regularized
adversarial training improves the grid accuracy from $71.17\%$ to
$77.47\%$ on CIFAR-10 and $90.35\%$ to $92.71\%$ on SVHN,
corresponding to a relative error reduction of $22\%$ and $24\%$
respectively. The same can be observed when comparing data
augmentation $\ensuremath{\std^\star}$ and its
regularized variants $\ensuremath{\ell_2}(\cdot,\text{rnd}), \text{KL}(\cdot,\text{rnd})$ in
Table~\ref{tab:comparereg}. Together with Tables~\ref{tab:compareadv2}
and \ref{tab:compareadv3}, S-PGD seems to be the more efficient
defense mechanism compared to $\text{worst-of-$k$}$ even when $k$ is raised to $20$,
with comparable computation time.



\textbf{Computational considerations}
In Figure~\ref{fig:runtime}, we plot the grid accuracy vs.\ the
runtime (in hours) for a subset of regularizers and defense mechanisms
on CIFAR-10 for clarity of presentation.  How much overhead is needed
to obtain the reported gains?  Comparing \text{AT}(\text{rob}, \text{Wo-$k$}) (green line) and
\text{ALP}(\text{rob}, \text{Wo-$k$}) (red line) shows that significant improvements in grid
accuracy can be achieved by regularization with only a small
computational overhead.
What if we make the defense stronger?
While the leap in robust accuracy from $\woabb{1}$ (also referred to as
\text{rnd}) to \woabb{10} is quite large, increasing $k$ to 20 only gives
diminishing returns while requiring $\sim 3\times$ more training time.
This observation is summarized exemplarily for both \text{KL}\ and ALP\ 
regularizer on CIFAR-10 in Table~\ref{tab:wok_diffk}.
Furthermore, for any fixed training
time, regularized methods exhibit higher robust accuracies where the
gap varies with the particular choice of regularizer and defense mechanism.



 





\textbf{Comparison with spatial equivariant networks} Although the
rotation-augmented \text{G-ResNet44}\, obtains higher grid (SVHN: $84.9\%$,
CIFAR-10: $71.64\%$) and natural accuracies (SVHN: $95\%$, CIFAR-10:
$93.08\%$) than the rotation-augmented Resnet-32 on both SVHN (grid:
$82.60\%$, nat: $93.97\%$) and CIFAR10 (grid: $58.29\%$, nat:
$89.93\%$), regularizing standard data augmentation
(i.e.\ regularizers with ``rnd'', see Table~\ref{tab:comparereg}
(right)) using both the $\ensuremath{\ell_2}$ distance and the $\text{KL}$ divergence
matches the \text{G-ResNet44}\, on CIFAR10 (\ensuremath{\ell_2}: $71.60\%$, \text{KL}: $73.50\%$)
and surpasses it on SVHN on grid (\ensuremath{\ell_2}: $90.51\%$, \text{KL}: $90.69\%$)
and natural accuracies by a relative grid error reduction of
$\sim37\%$. The same phenomenon is observed for the augmented
\text{ETN}\,and \text{STN}\,on SVHN.\footnote{We had difficulties to train both
  \text{ETN}\,and \text{STN}\,to higher than $86\%$ natural accuracy for CIFAR10
  even after an extensive learning rate and schedule search so we do
  not report the numbers here.}  In conclusion, regularized
augmentation based methods match or outperform representative
end-to-end networks handcrafted to be equivariant to spatial
transformations.
 
 
 
 





\textbf{Trade-off natural vs. adversarial accuracy} SVHN is one of the
main datasets (without artificial augmentation like in
rot-MNIST~\cite{larochelle07}) where spatial equivariant networks have
reported improvements on natural accuracy.  This is due to the
inherent orientation variance in the data.  In our mathematical
framework, this corresponds to the assumption in
Theorem~\ref{theo:tradeoff} of the distribution on the transformation
sets having support $\SubGorbit{z}$.  Furthermore, as all numbers in
SVHN have the same label irrespective of small rotations of at most 30
degrees, the first assumption in Theorem~\ref{theo:tradeoff} is also
fulfilled. Table~\ref{tab:regspat} and ~\ref{tab:comparereg} confirm
the statement in the Theorem that improving robust accuracy may not
hurt natural accuracy or even improve it: For SVHN, adding
regularization to samples obtained both via $\woabb{10}$ adversarial search or random transformation (\text{rnd}) consistently not only helps robust but also standard
accuracy.

\textbf{Comparing the effects of different regularization parameters
  on test grid accuracy}
We study Tables~\ref{tab:regspat} and~\ref{tab:comparereg} and attempt
to disentangle the effects by varying only one parameter.  For example
we can observe that, computational cost aside, fixing any regularizer
defense to $\woabb{10}$, the robust regularized loss \texttt{Reg}\:(\text{rob},
$\woabb{10}$) (i.e., $\PopLoss{\text{rob}}(f;\ensuremath{R})$) does better (or not
statistically significantly worse) than \texttt{Reg}\:(\text{nat}, $\woabb{10}$)
(i.e., $\PopLoss{\text{nat}}(f;R)$). Furthermore, the KL regularizer
generally performs better than $\ensuremath{\ell_2}$ for a large number of
settings. A possible explanation for the latter could be that $\text{D}_{\text{KL}}$
upper bounds the squared $\ell_2$ loss on the probability simplex and
is hence more restrictive.













\textbf{Choice of $\lambda$}
The different regularization methods peak at
different $\lambda$ in terms of grid accuracy. However, they outperform unregularized methods in a large range of $\lambda$ values, suggesting that
well-performing values of $\lambda$ are not difficult to find in
practice. These can be seen in Figures~\ref{fig:grid_nat_overlambda_rnd} and~\ref{fig:grid_nat_overlambda_wo} in the Appendix.
 


There are many more interesting experiments we have conducted for
subsets of the defenses and datasets illustrating different
phenomena that we observe. For example we have analyzed a finer grid for the grid search attack and evaluated $\text{S-PGD}$ as an attack mechanism. A detailed
discussion of these experiments can be found in
Sec.~\ref{sec:moreresults}.

\section{Introduction}
\label{sec:intro}

As deployment of machine learning systems in the real world has
steadily increased over recent years, the trustworthiness of these systems is of crucial importance.  This is particularly the case for safety-critical
applications. For example, the vision system in a self-driving car should correctly
classify an obstacle or human irrespective of their orientation.
Besides being relevant from a security perspective,
a measure for spatial invariance also helps to
gauge interpretability and reliability of a model. If an image of
a child rotated by $10^{\circ}$ is classified as a trash can, can we
really trust the system in the wild?


As neural networks have been shown to be expressive both theoretically
\cite{Hornik89,Barron93,Hanin17} and empirically \cite{Zhang16}, in
this work we study to what extent standard neural networks predictors
can be made invariant to small rotations and translations. In contrast
to enforcing conventional invariance on entire group orbits, we weaken
the goal to invariance on smaller so-called \emph{transformation
  sets}.
This requirement reflects the aim to be invariant to transformations
that do not affect the labeling by a human.  During test time we
assess transformation set invariance by computing the prediction
accuracy on the worst-case (\emph{adversarial}) transformation in the
(small) transformation set of each image in the test data.
The higher this worst-case prediction accuracy of a model is, the more
\emph{spatially robust} we say it is. 
Importantly, we use the same
terminology as in the very active field of adversarially robust
learning \cite{Szegedy13, Moosavi16, Kurakin16,
  Papernot17,Carlini17,Madry18, Samangouei18, Sinha18,
  Ragunathan18,Wong18,Mirman18}, but we consider adversarial examples
with respect to \emph{spatial} instead of $\ell_p$-transformations of
an image.





Recently, it was observed in \cite{Engstrom17,Fawzi15, Pei17,Kanbak18, Geirhos18, Alcorn18} that worst-case prediction performance 
drops dramatically for neural network classifiers obtained
using standard training, even for rather small transformation sets.
In this context, we examine the effectiveness of regularization that
explicitly encourages the predictor to be constant for transformed
versions of the same image, which we refer to as being \emph{invariant} on
the transformation sets.  Broadly speaking, there are two approaches
to encourage invariance of neural network predictors. On the one hand,
the relative simplicity of the mathematical model for rotations and
translations has led to carefully hand-engineered architectures that
incorporate spatial invariance directly \cite{Jaderberg15,
  Pollefeys16, Cohen16, Marcos17, Worrall17, Weiler18, Esteves18,
  Tai19}.
On the other hand, augmentation-based methods \cite{Baird92, Yaeger97}
constitute an alternative approach to encourage desired invariances on
transformation sets.  Specifically, the idea is to augment the
training data by a random or smartly chosen transformation of every
image for which the predictor output is enforced to be close to the
output of the original image. This \emph{invariance-inducing}
regularization term is then added to the cross entropy loss 
for back-propagation.


While augmentation-based methods can be used out of the box whenever
it is possible to generate samples in the transformation set of
interest, it is unclear how they compare to architectures that are
tuned for the \emph{particular} type of transformation using prior
knowledge. Studying robustness against spatial transformations in
particular allows us to compare the robust performance of these two
approaches, as spatial-equivariant networks have been somewhat
successful in enforcing invariance. In contrast, this cannot be claimed for
higher-dimensional $\ell_p$-type perturbations.
In the empirical sections of
this paper, we hence want to explore the following questions:
\begin{enumerate}
\item To what extent can augmentation and regularization based methods improve spatial robustness of common deep neural networks?
\item How does augmentation-based invariance-inducing regularization perform in case of small spatial transformations compared to representative specialized architectures designed to achieve invariance against entire transformation groups?
\end{enumerate}







As a justification for employing this form of \emph{invariance-inducing}
regularization, we prove in our theoretical section~\ref{sec:theory} that when
perturbations come from transformation groups, predictors that
optimize the robust loss are in fact invariant on the set of
transformed images.  Although recent works show a fundamental
trade-off between robust and standard accuracy in constructed $\ell_p$
perturbation settings \cite{Tsipras18, Zhang19, RXYDL19}, we
additionally show that this is fundamentally different for spatial
transformations due to their group structure.

For the empirical study, we implemented various
augmentation based training methods as described in
Sec.~\ref{sec:experimental_setup}.  In Sec.~\ref{sec:results}, we
compare spatial robustness for augmentation-based methods and
specialized neural network architectures on CIFAR-10 and SVHN.
Although group-invariance should automatically imply robust
predictions against \textit{all} transformations in the group,
group-equivariant networks have not been extensively evaluated using
adversarially chosen, but rather random transformations.
In experiments with CIFAR-10 and SVHN, we find that regularized
methods can achieve $\sim20\%$ relative adversarial error reduction
compared to previously proposed augmentation-based methods (including
adversarial training) without requiring additional computational
resources. Furthermore, they even
outperform representative handcrated networks that were
explicitly designed for invariance.

    



\section{Theoretical results for invariance-inducing regularization}
\label{sec:theory}

In this section, we first introduce our notion of transformation sets
and formalize robustness against a small range of translations and
rotations.  We then prove that, on a population level, constraining or
regularizing for transformation set invariance yields models that
minimize the robust loss.  Moreover, when the label distribution is
constant on each transformation set, we show that the set of robust
minimizers not only minimizes the natural loss but, under mild
conditions on the distribution over the transformations, is even
equivalent to the set of natural minimizers.

Although the framework can be applied to general problems and
transformation groups, we consider image classification for
concreteness.  In the following, $X \in \mathcal{X} \subset \mathbb{R}^d$ are the observed images,
 $Y\in\mathbb{R}^p$ is the one-hot vector for multiclass labels and both are
random variables from a joint distribution $\P$. The function $f:\mathbb{R}^d
\to \mathbb{R}^p$ in function space $\mathcal{F}$ (e.g. deep neural network in
experiments) maps the input image to a logit vector that is then
used for prediction via a softmax layer.

\subsection{Transformation sets}
Invariance with respect to spatial transformations is often thought of in terms of group
equivariance of the representation and prediction.  Instead of
invariance with respect to all spatial transformations in a group, we
impose a weaker requirement, that is invariance against transformation
sets, defined as follows.  We denote by $\SubGorbit{z}$ a compact
subset of images in the support of $\P$ that can be obtained by
transformation of an image $z \in \mathcal{X}$.  $\SubGorbit{z}$ is called a
\emph{transformation set}. For example in the case of rotations, the
transformation set $\SubGorbit{z}$ corresponds to the set of observed
images in a dataset that are different versions of the same image $z$,
that can be obtained by small rotations of one another.

By the technical assumption on the space
of real images that the sampling operator is bijective, the mapping $z
\to \SubGorbit{z}$ is bijective.  We can hence define
$\mathcal{G}$, a set of transformation sets, by $\mathcal{G} =
\cup_{z\in\mathcal{X}} \SubGorbit{z}$ for a given transformation group. Importantly,
the bijectivity assumption also leads to $\SubGorbit{z}$ being
disjoint for different
images $z\in \mathcal{X}$. The above definition is distribution dependent and
$\mathcal{G}$ partitions the support $\widetilde{\X}$ of the distribution.
More details on the aforementioned concepts and
definitions can be found in Sec.~\ref{sec:groups} in the Appendix.


We say that a function $f$ is \emph{(transformation-)invariant} if
$f(x) = f(x')$ for all $x,x'\in U$ for all $U \in \mathcal{G}$ and
denote the class of all such functions by $\mathcal{V}$.
Using this notation, fitting a model with high accuracy under worst-case
``small'' transformations of the input can be mathematically captured
by the robust optimization formulation~\cite{BenTal09} of minimizing
the \emph{robust loss}
\begin{equation}
  \label{eq:advmin}
  \PopLoss{\text{rob}}(f) :=  \mathbb{E}\:_{X,Y} \sup_{x' \in\SubGorbit{X}} \ell(f(x'), Y)
\end{equation}
in some function space $\mathcal{F}$.
We call the solution of this problem the (spatially) \emph{robust} minimizer.
While adversarial training aims to optimize the empirical version of
Eq.~\eqref{eq:advmin}, the converged predictor might be far from the
global population minimum, in particular in the case of nonconvex optimization 
landscapes encountered when training neural networks. Furthermore, we show in the following
section that for robustness over transformation sets, constraining
the model class to invariant functions leads to the same optimizer of
the robust loss.
These facts motivate invariance-inducing regularization which we then show to
exhibit improved robust test accuracy in practice.

\subsection{Regularization to encourage invariance}

For any regularizer $\ensuremath{R}$, we define the corresponding constrained set of functions $\mathcal{V}(\ensuremath{R})$ as
\begin{equation*}
  \mathcal{V}(\ensuremath{R}) := \{f: \ensuremath{R}(f, x, y) = 0 \quad \forall (x,y) \in \text{supp}(\P)\},
\end{equation*}
where $\text{supp}(\P)$ denotes the support of $\P$.  When $\ensuremath{R}(f, x,
y) = \sup_{x'\in \SubGorbit{x}} h(f(x), f'(x))$ and $h$
is a semimetric\footnote{The weaker notion of a semimetric satisfies
  almost all conditions for a metric without having to satisfy the
  triangle inequality.} on $\mathbb{R}^p$, we have $\mathcal{V}(\ensuremath{R}) = \mathcal{V}$.
We now consider constrained optimization problems of the form
\begin{align}
  &\ensuremath{\operatorname{min}}_{f\in\mathcal{F}} \mathbb{E}\: \ell(f(X), Y) \text{ s.t. }  f\in \mathcal{V}(\ensuremath{R}), \tag{O1}  \label{eq:regnat} \\
  &\ensuremath{\operatorname{min}}_{f\in\mathcal{F}} \mathbb{E}\:  \sup_{x' \in\SubGorbit{X}} \ell(f(x'), Y) \text{ s.t. }  f\in \mathcal{V}(\ensuremath{R}) \tag{O2} \label{eq:regadv}.
\end{align}
The following theorem shows that~\eqref{eq:regnat}, \eqref{eq:regadv}
are equivalent to~\eqref{eq:advmin} if the set of all invariant
functions $\mathcal{V}$ is a subset of the function space $\mathcal{F}$.
\begin{theo}
  \label{theo:1}
  If $\mathcal{V} \subseteq \mathcal{F}$,
 
  all minimizers of the adversarial
  loss~\eqref{eq:advmin} are in $\mathcal{V}$.  If
  furthermore $\mathcal{V}(\ensuremath{R}) \subseteq \mathcal{V}$, any solution of the
  optimization problems~\eqref{eq:regnat}, \eqref{eq:regadv} minimizes the adversarial loss.
\end{theo}
The proof of Theorem~\ref{theo:1} can be found in the Appendix\,in
Sec.~\ref{sec:theo1proof}. 
Since exact projection onto the constrained set is in general not
achievable for neural networks,
an alternative method to induce invariance is to relax the constraints
by only requiring $f\in \{f: \ensuremath{R}(f, x, y) \leq \epsilon \quad \forall (x,
y) \in \text{supp}(\P)\}$. Using Lagrangian duality, \eqref{eq:regnat}
and \eqref{eq:regadv} can then be rewritten in penalized form for some
scalar $\lambda > 0$ as
\begin{align}
  &\ensuremath{\operatorname{min}}_{f\in\mathcal{F}} \PopLossReg{nat}(f; \ensuremath{R}, \lambda) := \ensuremath{\operatorname{min}}_{f\in\mathcal{F}} \mathbb{E}\: \ell(f(X),Y) + \lambda\ensuremath{R}(f, X, Y), \label{eq:natpen} \\
  &\ensuremath{\operatorname{min}}_{f\in\mathcal{F}} \PopLossReg{rob}(f; \ensuremath{R}, \lambda) := \ensuremath{\operatorname{min}}_{f\in\mathcal{F}} \mathbb{E}\: \sup_{x'\in\SubGorbit{X}}\ell(f(x'),Y) + \lambda\ensuremath{R}(f, X, Y).    \label{eq:advpen}
\end{align}

In Sec.~\ref{sec:diffreg} we discuss how ordinary adversarial
training, and modified variants that have been proposed thereafter, can
be viewed as special cases of Eqs.~\eqref{eq:natpen} and~\eqref{eq:advpen}. 
On the other hand, the constrained regularization formulation
corresponds to restricting the function space and is hence comparable
with hand-crafted network architecture design as described in
Sec.~\ref{sec:spatnet}. 




\subsection{Trade-off between natural and robust accuracy}

Even though high robust accuracy~\eqref{eq:advmin} might be the main
goal in some applications, one might wonder whether the robust
minimizer exhibits lower accuracy on untransformed images
(\emph{natural accuracy}) defined as $\PopLoss{\text{nat}}(f) := \mathbb{E}\:_{X,Y}
\ell(f(X),Y)$ \cite{Tsipras18, Zhang19}. In this section we address this question and identify the conditions for transformation set
perturbations under which minimizing the robust loss does not lead to
decreased natural accuracy. Notably, it even increases under mild assumptions.

One reason why adversarial examples have attracted a lot of interest
is because the prediction of a given classifier can change in a
perturbation set in which all images appear the same to the human eye.
Mathematically, in the case of transformation sets, the latter can be
modeled by a property of the true distribution. Namely, it translates into the
conditional distribution $Y$ given $x$, denoted by $\P_{\SubGorbit{x}}$, being constant for all $x$
belonging to the same subset $U\in\mathcal{G}$. In other words, $Y$ is conditionally
independent of $X$ given $\SubGorbit{X}$, i.e.\ $Y\perp \!\!\! \perp 
X|\SubGorbit{X}$. Under this assumption the next theorem shows that
there is no trade-off in natural accuracy for the transformation
robust minimizer.
\begin{theo}[Trade-off natural vs. robust accuracy]
  \label{theo:tradeoff}
 
 
 
  Under the assumption of Theorem~\ref{theo:1} and if $Y \perp \!\!\! \perp  X |
  \SubGorbit{X}$ holds, the adversarial minimizer also minimizes the
  natural loss. If moreover, $\P_{\SubGorbit{z}}$ has support
  $\SubGorbit{z}$ for every $z\in \widetilde{\X}$ and the loss $\ell$ is injective, then every
  minimizer of the natural loss also has to be invariant.
\end{theo}

As a consequence, minimizing the constrained optimization problem
\eqref{eq:regnat} could potentially help in finding the optimal
solution to minimize standard test error.  Practically, the
assumption on the distribution of the transformation sets
$\SubGorbit{z}$ corresponds to assuming non-zero inherent transformation variance in the
natural distribution of the dataset.
In practice, we indeed observe a boost in natural accuracy for robust
invariance-inducing methods in Sec.~\ref{sec:results} on SVHN, a
commonly used benchmark dataset for spatial-equivariant networks for
this reason.

One might wonder how this result relates to several recent publications such
as \cite{Tsipras18, Zhang19} that presented toy examples for
which the $\ell_\infty$ robust solution must have higher natural loss
than the Bayes optimal solution even in the infinite data limit.
On a fundamental level, $\ell_\infty$ perturbation sets are of different
nature compared to transformation sets on generic distributions of $\mathcal{X}$. 
In the distribution considered in \cite{Tsipras18, Zhang19}, there is no unique mapping
from $x\in \mathcal{X}$ to a perturbation set and thus the conditional independence
property does not hold in general. 

\subsection{Different regularizers and practical implementation}
\label{sec:diffreg}
 In order to improve robustness against spatial transformations we
 consider different choices of $\ensuremath{R}(f,x,y)$ in the regularized
 objectives~\eqref{eq:natpen} and~\eqref{eq:advpen} that we then compare empirically in
 Sec.~\ref{sec:results}.



 This allows us to view
 a number of variants of adversarial training in a unified
 framework. Broadly speaking, each approach listed below consists of
 first searching an adversarial example according to some mechanism
 which is then included in a \emph{regularizing function}, often some
 weak notion of distance between the prediction at $X$ and the new example.
The following choices of regularizers involve the maximization of a
regularizing function over the transformation set
\begin{align*}
  \ensuremath{R}_{\text{AT}}(f, X, Y) &= \sup_{x'\in\SubGorbit{X}} \ell(f(x'),Y) -\ell(f(X),Y) \text{ (equivalent to \cite{Szegedy13,Madry18} for $\PopLoss{\text{nat}}$)} \\
  \ensuremath{R}_{\ensuremath{\ell_2}}(f, X, Y) &= \sup_{x'\in\SubGorbit{X}} \|f(X)-f(x')\|^2_2 \\ 
  \ensuremath{R}_{\text{KL}}(f, X, Y) &= \sup_{x'\in\SubGorbit{X}} \text{D}_{\text{KL}}(f(x'), f(X)) \text{ (equivalent to \cite{Zhang19} for $\PopLoss{\text{nat}}$)\footnote{Notice that \cite{Zhang19} is actually using the KL divergence in their implementation, which is not the same as cross-entropy as claimed in the paper.}}
  \end{align*}
where $\text{D}_{\text{KL}}$ is the KL divergence on the softmax of the (logit) vectors
$f \in \mathbb{R}^p$. In all cases we refer to the maximizer as an
\emph{adversarial example} that is found using \emph{defense
  mechanisms} as discussed in Section~\ref{sec:attacks_defenses}. Note
that for $\ensuremath{R}_{\ensuremath{\ell_2}}$ and $\ensuremath{R}_{\text{KL}}$ the assumption $\mathcal{V}(\ensuremath{R})
\subseteq \mathcal{V}$ in Theorem~\ref{theo:1} is satisfied.

Instead of performing a maximization of the regularizing function to
find the adversarial example $x'$, we can also choose $x'$ in
alternative ways
The following variants are
explored in the paper, two of which are reminiscent of previous work
\begin{align*}
  \ensuremath{R}_{\text{ALP}}(f, X, Y) &= \|f(x')-f(X)\|_2^2 \:\: \text{ with } \:\: x' = \ensuremath{\operatorname{argmax}}_{u\in\SubGorbit{X}} \ell(f(u),Y) \text{  (equivalent to \cite{Kannan18})}\\
   \ensuremath{R}_{\text{KL-C}}(f, X, Y) &= \text{D}_{\text{KL}}(f(x'), f(X)) \:\: \text{ with }\:\: x' = \ensuremath{\operatorname{argmax}}_{u\in\SubGorbit{X}} \ell(f(u),Y)\\
  \ensuremath{R}_{h-DA}(f, X) &= \mathbb{E}\:_{x'\in\SubGorbit{X}} h(f,X,X') \text{ (similar to \cite{Heinze17})}
\end{align*}
The last regularizer suggests using an additive
penalty on top of data augmentation, with either one or even multiple
random draws, where the penalty can be any of the above semimetrics
$h$ between $f(X)$ and $f(x')$, such as the $\ell_2$ or $\text{D}_{\text{KL}}$ distance.
Albeit suboptimal, the experimental
results in Section~\ref{sec:results} suggest that simply adding the
additive regularization penalty on top of randomly drawn data matches
general adversarial training in terms of robust prediction at a
fraction of the computational cost.
In addition, Theorem~\ref{theo:tradeoff} suggests that even
when the goal is to \emph{improve standard accuracy} and one expects
inherent variance of nuisance factors in the data distribution
it is likely helpful to use regularized data augmentation with $\ensuremath{R}_{h-DA}$
instead of vanilla data augmentation. Empirically we observe this
on the SVHN dataset in Section~\ref{sec:results}.



{\bf Adversarial example for spatial transformation sets} Since
$\SubGorbit{X}$ is not a closed group and we do not even know whether
the observation $X$ lies at the boundary of $\SubGorbit{X}$ or in the
interior, we cannot solve the maximization constrained to
$\SubGorbit{X}$ in practice. However, for an appropriate choice of set
$\mathcal{S}$, we can instead
minimize an upper bound of \eqref{eq:advmin} which reads
\begin{equation}
  \label{eq:advminapp}
  \ensuremath{\operatorname{min}}_{f\in\mathcal{F}} \mathbb{E}\: \sup_{\ensuremath{\Delta} \in \mathcal{S}} \ell(f(\Trafo{X}{\ensuremath{\Delta}}), Y) \geq \ensuremath{\operatorname{min}}_{f\in\mathcal{F}} \mathbb{E}\: \sup_{x' \in\SubGorbit{X}} \ell(f(x'), Y)
\end{equation}
where $\mathcal{S}$ is the set of transformations that we search over and
$\Trafo{X}{\ensuremath{\Delta}}$ denotes the transformed image with transformation
$\ensuremath{\Delta}$ (see Sec.~\ref{sec:groups} in the Appendix\ for an explicit
construction of the transformation search set $\mathcal{S}$). The left hand side
in~\eqref{eq:advminapp} is hence what we aim to solve in practice
where the expectation is over the empirical joint distribution of
$X,Y$. The relaxation of $\SubGorbit{X}$ to a range of transformations
of $X$ that is $\{ \Trafo{X}{ \ensuremath{\Delta} }\ : \ensuremath{\Delta} \in \mathcal{S} \}$ is
also used for the maximization within the regularizers.

In Figure~\ref{fig:ex_trafo} one pair of example images is shown: the original image (panel~(a)) is
depicted along with a transformed version $\Trafo{\cdot}{\ensuremath{\Delta}}$ with
$\ensuremath{\Delta} \in\mathcal{S}$ (panel~(b)) and the respective predictions by a standard neural network classifier.

\section{Regularized for adversarially robust training (REGART)}
In this section we introduce a rigorous and unified framework for regularized
training for adversarial robustness. This framework includes theoretical justification for
many commonly used methods in adversarial training (mixed vs. all adv. batch, TRADES, ALP)
and includes new ones.

We then use these regularized estimators and compare with networks which are designed
to be ...


Although our framework can
be applied broadly, we focus on image
classification as the prediction task of interest.


In adversarial robustness, you want robustness against changes against
transformations in your input which do not change the nature of your input.
This allows the
practitioner to know that even the most adversarial perturbation
$\ensuremath{\Delta}$ would not have influenced the probability of correct classification.
In the next section we introduce mathematical notation to think about this.


\subsection{Setting up transformation sets}
\label{sec:core}

The classifier $f$ lies in a function space
$\theta \in \mathbb{R}^{p}$ and we denote the sample-wise loss
function on an observed pair $(X,Y)$ as $ \ell(f_\theta(X), Y)$
with examples being the 0-1 or cross entropy loss for classification.
We denote transformations of $X$ as $\Trafo{X}{\ensuremath{\Delta}}$ parameterized
by a perturbation vector $\ensuremath{\Delta} \in \mathcal{S} \subset \mathbb{R}^q$
such that the set of all possible transformations forms a
transformation group $\mathbb{G}$ (i.e. closed).
We assume that our observations $X \in \mathbb{R}^d$, $\ensuremath{\text{ID}} \in \mathbb{Z}$, \Christina{need to introduce}
class $Y \in \mathbb{R}$ are random variables drawn from a joint distribution
$\P$ over $(\ensuremath{\text{ID}}, X,Y)$

We have a group $\mathbb{G}$ of transformations $\Trafo{\cdot}{\ensuremath{\Delta}}$
of $\mathcal{X}$ onto itself. 
We denote by $\Gorbit{z}$ the $\mathbb{G}$-orbit of $z$, that is
\begin{equation*}
\Gorbit{z} := \{ \Trafo{z}{\ensuremath{\Delta}}: \Trafo{\cdot}{\ensuremath{\Delta}} \in \mathbb{G}\}.
\end{equation*}
\Christina{i.e. in words .. }
Note that for all $x, x'\in\Gorbit{z}$ we have $\Gorbit{x} =
\Gorbit{x'}$ by definition.  The random variable $X \in \Gorbit{z}$
for some $z$. Note that for $x' \not \in \Gorbit{z}$ we have
$\Gorbit{x} \cap \Gorbit{x'} = \emptyset$.  Therefore, for every $x$
there exists a unique $\Gorbit{z}$ such that $x\in \Gorbit{z}$. Thus
we abuse notation a little bit denote by $\Gorbit{X}$ the orbit
$\Gorbit{z}$ for which $X \in\Gorbit{z}$.  \Christina{At polishing stage: remove ``note that'' 's :-)} \Christina{Here: go through example where transformation is rotation only and describe what the notation corresponds to; below: pick up same example to illustrate $\SubGorbit{z}$; alternatively, consider moving generative model + DAG further up to illustrate ideas? }

\paragraph{Technicality for bounded subsets}
For our problem setting, transformations that form a closed group constitute too large a
set as adversarial attacks are
typically judged against the standard whether 
humans would misjudge an image. If the transformation is too large,
this restriction is not fulfilled anymore. \fycomment{hmm think...}
Mathematically this is similar to assuming a distribution on
$\Gorbit{z}$ for every $z$. It could have finite support. \Christina{connect this better to what follows or remove}

Hence, instead of transformation groups with $\mathbb{G}$-orbits, we
consider connected subsets of orbits $\SubGorbit{z} \subset \Gorbit{z}$.  We
assume that these correspond to a set of ``maximal'' transformations $\mathcal{S}_z$
defined by the diameter
\begin{equation}
  \label{eq:pertdiam}
  \Pert^{\star}_z = \ensuremath{\operatorname{max}}_{x',x\in\SubGorbit{z}} \|\ensuremath{\Delta}\|_2 \:\:\text{s.t. } x' = \Trafo{x}{\ensuremath{\Delta}}
\end{equation}
and $\mathcal{S}_z = (-\Pert^{\star}_z, \Pert^{\star}_z)$ \fycomment{Notation not
  rigorous for the general transformation case...}  We assume that
$\Pert^{\star}$ is constant for all orbits and hence omit the $z$. For
example for rotations it makes sense that the feasible rotation range
for an image to not confuse a human to be the same for each image.
\fycomment{add how l-p balls fit here} Note that furthermore,
$\SubGorbit{z}$ do not overlap \fycomment{assume that or they don't}
and hence can still define the random variable $\SubGorbit{X} =
\SubGorbit{z}$ for $X \in \SubGorbit{z}$.

\subsection{Theoretical justification for regularization on the natural loss}


In adversarial robustness, the goal is for each $z$ to achieve the
same 0-1 loss for all observable images $X \in \SubGorbit{z}$.
The following loss function, common in the robust optimization
literature~\cite{BenTal09}, captures this adversarial
  concept
\begin{equation}
  \label{eq:advmin}
  \ensuremath{\operatorname{min}}_{f\in\mathcal{F}} \mathbb{E}\:_{X,Y} \sup_{x' \in\SubGorbit{X}} \ell(f(x'), Y)
\end{equation}
\fycomment{note about 0-1 loss vs. others (TRADES fuzz)}



 

Let us denote as $\mathcal{V}$ the space of functions
which are constant on every $\SubGorbit{x}$ and define
a more general constraint
\begin{equation*}
  \mathcal{V}(\ensuremath{R}) := \{f \in\mathcal{F}: \ensuremath{R}(f) = 0\} 
\end{equation*}
where we denote $\mathcal{V} := \mathcal{V}(\ensuremath{R}_0)$ with $\ensuremath{R}_0(f) = \sup_{x'\in
  \SubGorbit{x}} \|f(x) - f(x')\|_2$. For this and next section the reader
should think of $\ensuremath{R}=\ensuremath{R}_0$. A longer list of concrete regularizers that map
previous work to this framework is listed in Section~\ref{sec:diffreg}

\begin{theo}
  \label{theo:1}
    If $\mathcal{V} \subset \mathcal{F}$, for every minimizer of adversarial loss~\eqref{eq:advmin} we have $f^{\text{rob}} \in \mathcal{V}$.
\end{theo}

\begin{proof}
  Proof by contradiction. Let us assume that $f^{\text{rob}} \not \in \mathcal{V}$. Let's denote the different values in the set $A = \{ f^{\text{rob}}(x): x\in \SubGorbit{x} \}$. Denote the distribution over $x\in\SubGorbit{x}$ by $P_x$ we can rewrite the robust loss.
  \begin{align}
    \label{eq:prooflem}
    \ensuremath{\operatorname{min}}_{f\in\mathcal{F}} \mathbb{E}\:_{X,Y} \sup_{x' \in\SubGorbit{X}} \ell(f(x'), Y) = \mathbb{E}\:_X [\mathbb{E}\:_{Y|X} \sup_{x' \in \SubGorbit{X}} \ell(f(x'), Y)|\SubGorbit{x}] &\geq \int \sup_{a\in A} H(x, a) d P_x
  \end{align}
  where the function $H$ is specific to $\SubGorbit{x}$ and defined as $H(x,a) = \mathbb{E}\:_{Y|x}\ell(a,Y)$. The right hand side is minimized by choosing $A = \{a^\star\}$ with $a^\star = \ensuremath{\operatorname{argmin}}_a \int H(x,a)d P_x$. Since setting $f(x) = a^\star$ for all $x\in \SubGorbit{x}$ leads to equality in equation~\eqref{eq:prooflem}, q.e.d.
\end{proof}

Constrained optimization
\begin{equation}
  \label{eq:regnat}
  \ensuremath{\operatorname{min}}_{f\in\mathcal{F}} \mathbb{E}\: \ell(f(X), Y) \text{ s.t. }  f\in \mathcal{V}(\ensuremath{R})
\end{equation}

\begin{as}
$\ensuremath{R}$ is such that   $\mathcal{V}(\ensuremath{R}) \subset \mathcal{V}$
  \end{as}

The following corollary shows that minimizing the natural loss with constraint
is equivalent to solving the adversarial loss~\eqref{eq:advmin}
\begin{cor}
  \label{cor:constr}
  Any solution of the optimization program~\eqref{eq:regnat} with $\ensuremath{R}$ satisfying (A1) is a minimizer of the adversarial loss.
\end{cor}
\begin{proof}
  Let us first write \fycomment{careful notation, $\PopLoss{\text{adv}}$ currently equal $\PopLossReg{\text{adv}}(\ensuremath{R})$}
  \begin{align*}
  \PopLoss{\text{adv}}(f) &= \PopLoss{}(f) + [\PopLoss{\text{adv}}(f) - \PopLoss{}(f)] \\
  &=  \mathbb{E}\: \ell(f_\theta(\Trafo{X}{\ensuremath{\Delta}'}),\ensuremath{Y}) +  \underbrace{\mathbb{E}\: [\ensuremath{\operatorname{max}}_{\ensuremath{\Delta}' \in \mathcal{S}} \ell(f(\Trafo{X}{\ensuremath{\Delta}'}),\ensuremath{Y}) - \ell(f(X),\ensuremath{Y})]}_{\tilde{R}(f)}
  \end{align*}
  By Theorem~\ref{theo:1} we know that $f^{\text{rob}} \in \mathcal{V}$ minimizes $\PopLoss{\text{adv}}(f)$. Hence, $\tilde{R}(f^{\text{rob}}) = 0$. This shows that the two optimization programs~\eqref{eq:advmin} and~\eqref{eq:regnat} are in fact equivalent.
\end{proof}
Note that both of these hold without assumption, i.e. even if $Y|X$ changes (but of course there will be a tradeoff, refer to tradeoff section).

\subsection{General penalized regularization framework}

Since minimizing in the set of feasible functions $f\in \mathcal{V}$ in the context of neural networks could be hard accomplish (i.e. simultaneously minimizing and feasibility could be hard), 
common practice is to relax the constraints by only requiring $f\in \mathcal{V}_\epsilon$, where we define
\begin{equation*}
  \mathcal{V}_{\epsilon} = \{f: \ensuremath{R}(f) \leq \epsilon \quad \forall z\}
\end{equation*}
Consequently, instead of constrained optimization we can also use penalization on the natural loss by Lagrangian duality, and rewrite~\eqref{eq:regnat} as
\begin{equation}
  \label{eq:natpen}
  \PopLossReg{nat}(\ensuremath{R}, \lambda) := \ensuremath{\operatorname{min}}_{f\in\mathcal{F}} \mathbb{E}\:_{X,Y} \ell(f(X),Y) + \lambda\ensuremath{R}(f, X, X', Y)
\end{equation}



In this paper we only consider regularizers $\ensuremath{R}$ that satisfy $f\in \mathcal{V} \implies
\ensuremath{R}(f) = 0$ (but not necessarily vice versa, i.e. TRADES). By Theorem~\ref{cor:constr} all robust
solutions $f^{\text{rob}} \in\mathcal{V}$, and hence adding any of the above constraints
$\ensuremath{R}_i(f,X) = 0$ to the robust loss would not change the minimizer of
the optimization problem since they are consequences of
$f\in\mathcal{V}$. Applying the same relaxation as above, yields penalized
adversarial training as follows
\begin{equation}
  \label{eq:advpen}
  \PopLossReg{rob}(\ensuremath{R}, \lambda) := \ensuremath{\operatorname{min}}_{f\in\mathcal{F}} \mathbb{E}\:_{X,Y} \sup_{x'\in\SubGorbit{X}}\ell(f(x'),Y) + \lambda\ensuremath{R}(f, X, X', Y)
\end{equation}
Compared to penalizing the natural loss, this optimization would
require searching two kind of adversarial examples: one that maximizes
$\ell(f(x'),Y)$ and one that solves the inner maximization in
the regularizer. ?? The regularizers which make sense in this setting are L2, TRADES, 

\paragraph{choosing two adversarial examples}


We may run the modified regularized adversarial training instead to save on computation time:
\begin{equation}
  \label{eq:advpen}
  \PopLossReg{rob}(h, \lambda) := \ensuremath{\operatorname{min}}_{f\in\mathcal{F}} \mathbb{E}\:_{X,Y} \sup_{x'\in\SubGorbit{X}}\ell(f(x'),Y) + \lambda\ensuremath{R}'(f, X, X^\star, Y)
\end{equation}
where now $\ensuremath{R}'(f,X, X^\star, Y) = h(X, X^\star, Y)$, where $X^\star =  \arg\sup_{x'\in\SubGorbit{X}}\ell(f(x'),Y)$.
That makes ALP adv $= \PopLossReg{\text{rob}}(h,\lambda)$.
\fycomment{maybe show some relation between $\PopLossReg{rob}(\ensuremath{R})$ vs. $\PopLossReg{rob}(h)$ under that assumption. It's an approximation }

We show in the appendix that empirically, it is best to choose
adversarial sample wrt. regularizer/loss and that it is as good as
choosing two adv. ex. 
\fycomment{to be seen}


\fycomment{Does Regul. on adv. loss generally do worse/better?}
\fycomment{Trades claims that the key is that they don't enforce $\ell(f(x'),Y)$
to be small. How does TRADES with adv. loss compare with natural loss?}


\subsection{Different choices of regularizers}
\label{sec:diffreg}

In this section we want to discuss the different regularizers $\ensuremath{R}(f)$
that we want to compare, most of them already empirically explored
in the $\ell_\infty$ literature.
In general, they can all be united under one hood and expressed as
$\ensuremath{R}_i(f,X,X',Y) = \sup_{x'\in\SubGorbit{X}} h_i(X, X', Y)$ for some $h$.
\begin{itemize}
\item $h_0(X,X',Y) =  \|f(X)-f(x')\|^2_2$ (L2, directly follows from theory)
\item $h_1(X, X', Y) = \ell(f(x'), f(X))$ (TRADES)
\end{itemize}
There is also non-adversarial $\ensuremath{R}_4(f, X) = \mathbb{E}\:_{x'\in\SubGorbit{X}}
\|f(x') -f(X)\|_2^2$ (CORE, not quite,) which is random augmentation -
but is not as effective \fycomment{have we tried?}

Note that regular adversarial training corresponds to $\lambda = 1$ and the following $\ensuremath{R}(f)$.
The following ``regularizers'' require finding adversarial examples using the data label
\begin{itemize}
  \item $\ensuremath{R}_2(f, X, Y) = \|f(x')-f(X)\|_2^2$ with $x' = \ensuremath{\operatorname{argmax}}_{u\in\Gorbit{X}} \ell(f(u),Y)$ (ALP plain)
  \item $h_3(f, X, X', Y) = \ell(f(x'),Y) - \ell(f(X),Y)$
(ordinary adv. Training with adv. batch with $\lambda=1$)
\item $h_4(f, X, X',Y) = \ell(f(x'),Y)$ (ordinary
  Adv. Training mixed batc h ($\lambda=1$)).
  \item $h_5(f, X, X', Y) = |\ell(f(x'),Y) - \ell(f(X),Y)|$ (modified adv. training) \fycomment{only diff is that it not always tries to find misclassified samples like Ord. ART, but actual ones with different loss (closer to regularization on function}
\end{itemize}
In fact all adversarial examples here are the same (maximizer of cross entropy loss for fixed $Y$).

Note that for $i=0, 3, 4$ that $\mathcal{V}(\ensuremath{R}_i) \subset \mathcal{V}$ and
hence the solution of the corresponding constrained
problem~\eqref{eq:regnat} is a minimizer of the adversarial loss
\fycomment{under which loss conditions can you show the same for trades? otherwise say
how it approximates}

\paragraph{Comparing different regularizers}

Each of the regularizers suggests choosing different adversarial examples.
These two groups are conceptually different: One that is trying
to match predictions for different $x$ within $\SubGorbit{x}$ and
another that depends on $Y$ and is matching the losses. I.e. if the
loss is currently big on $X$, find $X'$ that has small loss and if loss on $X'$ small,
find big loss/misclassified $X'$.

For fixed $\lambda$, we have $\PopLoss{nat}(\ensuremath{R}_1) \geq \PopLoss{nat}(\ensuremath{R}_0)$.
hence it is more restrictive to 


I'm guessing adversarial example wrt. CE or Reg. doesn't make a huge difference.
The reason is that they are closely related. In particular with unsigned ones
it depends on the loss satisfying regularity conditions
\fycomment{we can run experiment to verify this here} This entails
that the key is the actual regularizer, not necessarily the
regularizer we use to find $f$. In simulations we see that (at least for
wo-10, for FO, obviously they're going to wonder off in
$\ell_2$-distance), it picks similar sample -> can just choose the one
for CE.

\paragraph{Comparing $\PopLoss{adv}$ vs. $\PopLoss{nat}$ (falsifying TRADES ``explanation''?)}
There is a categorical difference between $x$ related regularizers and
$x, y$ related ones.  the $X$ ones are focusing on functional
``smoothness'' no matter where on or off the boundary.

Although all regularizers serve to make the predictions between adversarial
and regular example closer, 
it is hard to predict which regularizer would lead to the best practical
results for deep neural networks, but at least by Theorem 1, every minimizer of
the robust loss should be in the sets $\mathcal{V}_{\epsilon}(\ensuremath{R})$ for all of the regularizers above
and all $\epsilon \geq 0$ and vice versa. 

TRADES argue that whether one or the other prevails is somewhat dependent on
regularization.

\fycomment{Does the actual example or regularizer make the difference?? it should
be the regularizer itself}
\begin{itemize}
\item It is interesting to directly compare ALP plain against L2 
i.e. same regularizer for backprop but different adversarial example

\item Similarly interesting to compare TRADES with usual adv. training but
with different $\lambda$. Is it their tuning that made the difference
or combo of (1) adv. sample search wrt $Y$ and (2) asymmetric loss
\end{itemize}

My guess: sometimes these examples probably match (more so for wo-10 than FO)
in other cases when you use the wrong sample ($Y$ dependent) for the ``right''
regularizer, it is just not as strong for the regularizer


\subsection{Trade-off between nat. and robust accuracy}

\fycomment{put into perspective with TRADES}

Note that in natural applications such as classification, the goal to
obtain robustness is only meaningful when the conditional distribution
of $Y$ does not change too much with a transformation, that is
When $Y|X$ is the same within an orbit (and hence suborbit), or more formally
\begin{equation}
  \label{eq:robustsense}
  P(Y|\{X = x\}) = p_z \quad \forall x\in\SubGorbit{z}, z.
\end{equation}
When this assumption holds, we show in this section that there is no trade-off
between natural and robust accuracy.

First of all, we want to discuss the sensibility of property~\eqref{eq:robustsense}.
If this assumption does not hold for the combination of (transformation, distribution), then being
able to assign the same predicted value $Y$ to both $X$ and
$\Trafo{X}{\ensuremath{\Delta}}$ under arbitrary transformations $\ensuremath{\Delta} in \mathcal{S}$
is not interpretable nor meaningful. Why would it be desirable to have a model
which predicts a value for a transformation that has zero probability to occur in
the actual distribution?

Let us illustrate the sensibility of this assumption for image classification: Say we have two
features = (texture, shape). In the true distribution, elephant always
comes with this greyish skin texture and cat with
theirs. P(cat texture, elephant shape)=0. Now we can learn a
classifier that is "robust" against texture changes and only focuses
on shape. But what does it mean to classify (cat texture,
elephant shape) as elephant? I have a hard time understanding the
relevance of this. Now the texture work is interesting in its own
right, understand what imagenet features learn. But the robustness
question asked in this setting would be questionable in terms of
sensibility.

We now formally state the theorem that shows that under this
reasonable assumption there is no trade-off
\begin{theo}
  Under assumption~\eqref{eq:robustsense}, if
  $\mathcal{V} \subset \mathcal{F}$ and the loss is continuous in the first
  argument, then there exists $f^\star \in \mathcal{V}$ such that
  $\PopLoss{}(f^\star) \leq \PopLoss{}(f)$ for all
  $f\in \mathcal{F}$.   
\end{theo}

\begin{proof}
  \fycomment{Notationally not perfectly rigorous, but to illustrate the point}
  We prove existence by construction: Take any minimizer $\hat{f}$ of $\PopLoss{}(f)$ which is not in  $\mathcal{V}$.
  We can then construct an $f^\star$, such that $ \PopLoss{\text{adv}}(f^\star) = \PopLoss{\text{nat}}(f^\star) = \PopLoss{\text{nat}}(\hat{f})$.
  The construction is as follows: First note that because of measurability of $\mathbb{E}\:_Y [\ell(f(X), Y) | X ]$ ``wrt. $f(X)$'' conditioned on $\Gorbit{x}$ we have for any function $f$ that
  \begin{align*}
    \mathbb{E}\:_{\Gorbit{x}} \mathbb{E}\:_X [\mathbb{E}\:_Y [\ell(f(X), Y) | X ] | \Gorbit{x}] &=  \mathbb{E}\:_{\Gorbit{x}} \mathbb{E}\:_X [ \mathbb{E}\:_Y [\ell(f(X), Y) | f(X)] \Gorbit{x}]
  \end{align*}
  Given a fixed $\Gorbit{x}$, let us now define $f^\star$ on all $x' \in \Gorbit{x}$ as a constant, i.e. $f^\star(x') = c(\Gorbit{x})$ which satisfies:
  $\mathbb{E}\:_Y \ell(c(\Gorbit{x}), Y)| \Gorbit{x} = \mathbb{E}\:_{X,Y} \ell(\hat{f}(X), Y)| \Gorbit{x}$. Since we assume that $\ell$ is continuous, by Rolle's theorem
  such a $c(\Gorbit{x})$ exists. Now $f^\star \in \mathcal{V}$ and since $\mathcal{V} \in \mathcal{F}$ we have
  \begin{align*}
    \PopLoss{}(f^\star) = \mathbb{E}\: \ell(f^\star(X), Y)  &=  \mathbb{E}\:_{\Gorbit{x}} \mathbb{E}\:_X [ \mathbb{E}\:_Y [\ell(f^\star(X), Y) | f^\star(X)] \Gorbit{x}] \\
    &= \mathbb{E}\:_{\Gorbit{x}} \mathbb{E}\:_{X,Y} [\ell(\hat{f}(X), Y) | \Gorbit{x} ] = \PopLoss{}(\hat{f}).
  \end{align*}
  Since  $\hat{f}$ is a minimizer of the population loss, we also have $\PopLoss{}(f^\star) \leq \PopLoss{}(f)$ for all $f\in\mathcal{F}$ q.e.d. 
\end{proof}

This requirement is realistic in a practical data
generation setting described in the next section.



\paragraph{Example distribution}
\fycomment{have to carefully think whether notation is necessary}
The condition~\ref{eq:robustsense} is fulfilled for any model where $Y \perp \!\!\! \perp  X \big| \XID{\ensuremath{\text{ID}}}$, since we then have
\begin{align*}
Y|\{X=x\}, \XID{\ensuremath{\text{ID}}} \overset{d}{=} Y|\XID{\ensuremath{\text{ID}}} \implies Y | \{X=x\} \overset{d}{=} Y | \XID{\ensuremath{\text{ID}}}(x) \quad \forall x.
\end{align*}
An explicit example generative model that simulates the natural process
of image capturing is depicted in a probabilistic model like in Figure ~\ref{fig:dag}.

\fycomment{have to unify notation}
Let us go through the model in detail. Randomness comes from $\ensuremath{\text{ID}}$ and $\ensuremath{\Delta}$. We have a group $\mathbb{G}$ of transformations $\Trafo{\cdot}{\ensuremath{\Delta}}$
of $\mathcal{X}$ onto itself. 
We denote by $\XID{\ensuremath{\text{ID}}}$ the $\mathbb{G}$-orbit of $x$, that is
\begin{equation*}
\XID{\ensuremath{\text{ID}}} := \{ \Trafo{x}{\ensuremath{\Delta}}: \Trafo{\cdot}{\ensuremath{\Delta}} \in \mathbb{G}\}  
\end{equation*}
The parameter $\ensuremath{\Delta}$ then picks one sample from $\XID{\ensuremath{\text{ID}}}$ according to some distribution which becomes the random variable $X$. It is also assumed that there is a unique mapping $v : \mathcal{X} \to \mathcal{G}$ from the domain $\mathcal{X}$ to the space of orbits $\mathcal{G}$ (that is the orbits are disjoint subsets in $\mathcal{X}$).
Now note that in this model,
we have that $X, \Trafo{X}{\ensuremath{\Delta}'}$ follow the same distribution for any perturbation $\ensuremath{\Delta}'$ and furthermore because of conditional independence 


\fycomment{The $\ensuremath{\Delta}$ in the graphical model should now be $\SubGorbit{X}$, else it's confusing, generally figure needs revamp}

\begin{figure}[htbp]
\begin{center}
\centerline{\includegraphics[width=.6\columnwidth]{images/PP_DAG4.pdf}}
\caption{\small Generative model for observations $\ensuremath{\text{ID}}, X, Y$.
Here, the sources of randomness are the
perturbation $\ensuremath{\Delta}$ and the $\ensuremath{\text{ID}}$.
The generative probabilistic model is rooted in the intuition that the
process of collecting an observation always starts with randomly
picking an object with a certain $\ensuremath{\text{ID}}$ with associated attributes
$\ensuremath{Z} = [Z^{\text{style}},Z^{\text{core}}]$ (usually unobserved) which determine
its identity uniquely. The class $\ensuremath{Y}$ is a deterministic function of
the core attributes $Z^{\text{core}}$ and $\XID{\ensuremath{\text{ID}}} \in \mathbb{R}^d$ is an
arbitrary function of $\ensuremath{Z}$ and assumed to be deterministic as
well.  The observed image $X \in \mathbb{R}^d$
random transformation, defined by a perturbation $\ensuremath{\Delta} \in \mathcal{S}
\subset \mathbb{R}^q$, of $\XID{\ensuremath{\text{ID}}}$, i.e.\ $X =
\Trafo{\XID{\ensuremath{\text{ID}}}}{\ensuremath{\Delta}}$. For instance for images, the transformation
$\Trafo{\cdot}{\ensuremath{\Delta}}$ with perturbation $\ensuremath{\Delta}$ could consist of a
rotation with degree $\ensuremath{\Delta} \in [-30^{\circ},30^{\circ}]$, which arises
naturally from the image capturing process.
$\ensuremath{\text{ID}}$ is a unique identifier variable encoding the identity of the underlying object. $\Trafo{\XID{\ensuremath{\text{ID}}}}{\ensuremath{\Delta}}$ with perturbation $\ensuremath{\Delta}$ describes the transformation of $\XID{\ensuremath{\text{ID}}}$ arising in the measurement process recording $X$.}
\label{fig:dag}
\end{center}
\vskip -0.2in
\end{figure}




\section{Spatial-equivariant networks}

\subsection{Two-Stage predictor}




\section{Related work}
\label{sec:related}
\textbf{Group equivariant networks} There
are in general two types of approaches to incorporate spatial
invariance into the network. In one of the earlier works in the neural
net era, Spatial Transformer Networks were introduced
\cite{Jaderberg15} which includes a transformer module that
predicts transformation parameters followed by a transformer. Later
on, one line of work proposed multiple filters that are discrete group
transformations of each other \cite{Pollefeys16, Marcos17, Cohen16,
  Zhou17, Worrall17}.  For continuous transformations,
steerability \cite{Weiler18, Cohen18}
and coordinate transformation \cite{Esteves18, Tai19} based approaches
have been suggested. Although these approaches have resulted
in improved standard accuracy performances, it has not been
rigorously studied whether or by how much they improve upon
regular networks with respect to robust test accuracy.

\noindent \textbf{Regularized training} Using penalty regularization to
encourage robustness and invariance when training neural networks
has been studied in different contexts: for
distributional robustness \cite{Heinze17}, domain generalization
\cite{Motiian17}, $\ell_p$ adversarial training \cite{Na18, Kannan18,
  Zhang19}, robustness against simple transformations \cite{Cheng19}
and semi-supervised learning \cite{Zheng16, Xie19}.
These approaches are based on augmenting the training data either
\emph{statically} \cite{Heinze17, Motiian17, Cheng19, Xie19}, ie. before fitting the
model, or \emph{adaptively} in the sense of adversarial training, with different
augmented examples per training image generated in every
iteration \cite{Kannan18, Na18, Zhang19}.


 







\noindent \textbf{Robustness against  simple transformations}
Approaches targeting adversarial accuracy for
simple transformations have used attacks and defenses in the spirit
of PGD (either on transformation space \cite{Engstrom17} or on input
space projecting to transformation manifold \cite{Kanbak18}) and
simple random or grid search \cite{Engstrom17, Pei17}.
Recent work~\cite{Dumont18} has also evaluated some
rotation-equivariant networks with different training and attack
settings which reduces direct comparability with e.g. adversarial
based defenses~\cite{Engstrom17}.


















