We can also note that increasing the regularization leads to an increase in generalization and robustness.

Robustness against $\ell_\infty$ attacks for different classifiers trained with Adversarial Training given the number of iterations.

Robustness against $\ell_\infty$ attacks for different classifiers trained with Adversarial Training given the number of iterations.

Accuracy under attack on CIFAR10 test set with $\ell_\infty$ and $\ell_2$ attacks for several classifiers trained with Adversarial Training given the number of iterations.

Comparison of the distribution of the norm of the Jacobian of the baseline model against the model trained with Lipschitz regularization.

Comparison of the distribution of the norm of the Jacobian of the model trained with Adversarial training against the model trained with Adversarial training and Lipschitz regularization.

Distribution of the norm of the Jacobian matrix with respect to the CIFAR10 test set from a Wide ResNet trained with different schemes.

Finally, we also conducted an experiment to study the impact of the regularization on the gradients of the whole network by measuring the distributions of the norm of the Jacobian matrix with respect to the inputs from the test set.
The results of this experiment are presented in <Ref> and show more concentrated gradients with Lipschitz regularization.
Indeed, we can observe that while the median is higher, the regularization decreases the number of points with very high Lipschitz constant.

Although Lipschitz regularization is not a Jacobian regularization, we can observe a clear shift in the distribution.
This suggests that our method does not only work layer-wise, but also at the level of the entire network.
A second experiment, using Adversarial Training, presented in <Ref> demonstrates that the effect is even stronger when the two techniques are combined together.

It also demonstrates that Lipschitz regularization and Adversarial Training (or other Jacobian regularization techniques) are complementary.
Hence they offer an increased robustness to adversarial attacks as demonstrated above.

Model     2cAccuracy     2cPGD-$\ell_\infty$
2cC&W-$\ell_2$ 0.6     2cC&W-$\ell_2$ 0.8

Baseline     0.953     0.001     0.000     0.000     0.002     0.000     0.000     0.000

AT           0.864     0.001     0.426     0.000     0.477     0.000     0.334     0.000

AT+PM        0.788     0.010     0.434     0.007     0.521     0.005     0.419     0.003

AT+LipReg     0.808     0.022     0.457     0.002     0.547     0.022     0.438     0.020

Results on CIFAR10 dataset

Model     2cAccuracy     2cPGD-$\ell_\infty$
2cC&W-$\ell_2$ 0.6     2cC&W-$\ell_2$ 0.8

Baseline     0.792     0.000      0.000     0.000      0.001     0.000      0.000     0.000

AT     0.591     0.000      0.199     0.000      0.263     0.000      0.183     0.000

AT+LipReg     0.552     0.019      0.215     0.004      0.294     0.010      0.226     0.008

Results on CIFAR100 dataset

Accuracy under $\ell_2$ and $\ell_\infty$ attacks of different training schemes on CIFAR10/100 datasets.

1c2[4]*Model     1c2[4]*Natural
2cPGD-$\ell_\infty$           3cC&W-$\ell_2$

1c0.02     1c0.031           1c1.00     1c2.00     1c3.00

Baseline <cit.>     0.782         0.000     0.000         0.000     0.000     0.000

AT     0.509           0.251     0.118           0.307     0.168     0.099

AT+LipReg ($C_2 = 0.0006$)     0.515           0.255     0.121           0.316     0.177     0.105

AT+LipReg ($C_2 = 0.0010$)     0.519           0.259     0.123           0.338     0.204     0.129

Natural accuracy and accuracy under $\ell_2$ and $\ell_\infty$ attacks of different training schemes on the ImageNet dataset.

Experimental Settings CIFAR10/100 Dataset.
For all our experiments, we use the Wide ResNet architecture introduced by <cit.> to train our classifiers.
We use Wide ResNet networks with 28 layers and a width factor of 10.
We train our networks for 200 epochs with a batch size of $200$.
We use Stochastic Gradient Descent with a momentum of $0.9$, an initial learning rate of $0.1$ with exponential decay of 0.1 (MultiStepLR gamma = 0.1) after the epochs $60$, $120$ and $160$.
For Adversarial Training  <cit.>, we use Projected Gradient Descent with an $\epsilon = 8/255 (\approx 0.031)$, a step size of $\epsilon/5 (\approx 0.0062)$ and 10 iterations, we use a random initialization but run the attack only once.
To evaluate the robustness of our classifiers, we rigorously followed the experimental protocol proposed by <cit.>.
More precisely, as an $\ell_\infty$ attack, we use PGD with the same parameters ($\epsilon = 8/255$, a step size of $\epsilon/5$) but we increase the number of iterations up to 200 with 10 restarts.
For each image, we select the perturbation that maximizes the loss among all the iterations and the 10 restarts.
As $\ell_2$ attacks, we use a bounded version of the <cit.> attack.
We choose $0.6$ and $0.8$ as bounds for the $\ell_2$ perturbation.
Note that the $\ell_2$ ball with a radius of $0.8$ has approximately the same volume as the $\ell_\infty$ ball with a radius of $0.031$ for the dimensionality of CIFAR10/100.

Experimental Settings for ImageNet Dataset.
For all our experiments, we use the ResNet-101 architecture <cit.>.
We have used Stochastic Gradient Descent with a momentum of $0.9$, a weight decay of $0.0001$, label smoothing of $0.1$, an initial learning rate of $0.1$ with exponential decay of $0.1$ (MultiStepLR gamma = $0.1$) after the epochs $30$ and $60$.
We have used Exponential Moving Average over the weights with a decay of $0.999$.
We have trained our networks for 80 epochs with a batch size of $4096$.
For Adversarial Training, we have used PGD with 5 iterations, $\epsilon = 8/255 (\approx 0.031)$ and a step size of $\epsilon/5 (\approx 0.0062)$.
To evaluate the robustness of our classifiers on ImageNet Dataset, we have used an $\ell_\infty$ and an $\ell_2$ attacks.
More precisely, as an $\ell_\infty$ attack, we use PGD with an epsilon of 0.02 and 0.031, a step size of $\epsilon/5$) with a number of iterations to 30 with 5 restarts.
For each image, we select the perturbation that maximizes the loss among all the iterations and the 10 restarts.
As $\ell_2$ attacks, we use a bounded version of the <cit.> attack.
We have used $1$, $2$ and $3$ as bounds for the $\ell_2$ perturbation.

§ CONCLUDING REMARKS

In this chapter, we introduced a new bound on the Lipschitz constant of convolution layers that is both accurate and efficient to compute.
We used this bound to regularize the Lipschitz constant of neural networks and demonstrated its computational efficiency in training large neural networks with a regularized Lipschitz constant.
As an illustrative example, we combined our bound with adversarial training, and showed that this increases the robustness of the trained networks to  adversarial attacks.
The scope of our results goes beyond this application and can be used in a wide variety of settings, for example, to stabilize the training of Generative Adversarial Networks (GANs) and invertible networks, or to improve generalization capabilities of classifiers.

CHAPTER: CONCLUSION

§ SUMMARY OF THE CONTRIBUTIONS

State-of-the-art in a variety of domains, deep neural networks exhibit important limitations.
Indeed, current neural networks tend to be very large in terms of their number of parameters which make them difficult to train and to deploy in real-world applications.
Furthermore, they exhibit instability to small perturbations of their inputs which lead to adversarial attacks.

In this thesis, we have used structured matrices from the Toeplitz family to make contributions to the field of deep learning.
Our contributions are twofold.
First, we studied deep diagonal-circulant neural networks, which are deep neural networks in which weight matrices are the product of diagonal and circulant ones.
Using diagonal and circulant matrices instead of dense ones allows for an important reduction in the number of parameters which make them more efficient and cost-effective.
In addition to being more compact than fully connected neural networks, diagonal-circulant neural networks have a high expressivity that makes them useful for numerous use cases.
In order to characterize the expressive power of diagonal-circulant neural networks, we build upon the work of <cit.> which states that any matrix can be decomposed into a product of alternating diagonal and circulant matrices.
Based on this result, we have successfully demonstrated that neural networks with diagonal and circulant matrices are universal approximators and characterized their expressive power with respect to their depth.
We also demonstrated the effectiveness of this class of compact neural networks to video classification with a real-world dataset.

Secondly, we studied the properties of doubly-block Toeplitz matrices which are equivalent to the convolution operation.
Using the properties of this type of structured matrix and a Fourier representation introduced by <cit.>, we devised an upper-bound on the singular values of convolution layers leading to a new regularization scheme that improves the robustness of neural networks against adversarial attacks.
In order to use this upper-bound in a large-scale setting, we introduced the PolyGrid algorithm (see <Ref>) which efficiently and accurately computes an approximation of this upper-bound.

§ PERSPECTIVES AND FUTURE WORKS

§.§ Designing Compact Transformers for Natural Language Processing

In order to improve upon our work on compact neural networks, one idea follows naturally.
The race towards larger convolutional neural networks seemed to have slowed down following the work of <cit.> which devised compact state-of-the-art neural networks for image recognition.
However, other types of architecture, , Transformers which rely heavily on dense matrices, have seen their number of parameters exploding in recent years.
The latest model which was designed by <cit.> has 1 trillion parameters, 5.7 times than the second largest, proposed by <cit.>, which had 175 billion parameters.

In <Ref> and Appendix <ref>, we have used the diagonal-circulant decomposition for compressing embedded layers in the context of video classification.
This decomposition could also be used to compress attention layers of Transformers networks <cit.> where the attention layer is described as follows:

\begin{equation}
\text{Attention}(\Qmat, \Kmat, \Vmat) = \text{softmax} \left( \frac{\Qmat \Kmat^\top}{\sqrt{d_k}} \right) \Vmat \enspace,
\end{equation}

where $\Qmat, \Kmat$ and $\Vmat$ are dense matrices.
Taking this layer as a building block leads to large neural networks as demonstrated by the GPT-3 architecture with 96 attention layers and 175 billion parameters.
Although, the diagonal-circulant decomposition could successfully reduce the number of parameters of attention layers, it may have limited impact on multi-head attention layers which are a concatenation of small attention layers due to the reduced dimension of each matrix.

§.§ Regularization on the Condition Number of Convolution Layers

In <Ref>, we have proposed an upper-bound on the largest singular value of convolution layers which allow us to regularize the Lipschitz constant of the network thus improving the robustness.

However, an important reduction of the Lipschitz constant seems to prevent the network from learning correctly.
Indeed, as demonstrated by the work of <cit.>, accuracy and robustness are actually at odds, meaning that improving the robustness (in our case, reducing the expressivity) hurts the training and the natural accuracy of the network.
In our experiments, the phenomenon called rank collapse <cit.> where the rank of the weights matrices tend to decrease during training combined with a strong Lipschitz regularization would prevent convergence.

An interesting solution would be to regularize the largest singular value and promoting the smallest in order to enforce orthogonality.

The following bound on the condition number of general matrices <cit.> could be studied:

\begin{equation}
\kappa(\Wmat) \le \frac{2}{\abs{\det(\Wmat)}} \left(\frac{\norm{\Wmat}_\fro}{\sqrt{r}}\right)^r
\end{equation}

where $r$ is the rank of $\Wmat$.
As such, using the bound as a regularizer will enforce the orthogonality, just like a layer normalization.
Therefore, we could design some heuristic regularizers to encourage a smaller $\left(\frac{\norm{\Wmat}_\fro}{\sqrt{r}}\right)^r$ and larger $\abs{\det(\Wmat)}$ separately, as given by the following objective function:

\begin{align}
\min_{\Omega} \Ebb_{\xvec, y \sim \Dset} \left[ L(N_\Omega(\xvec), y)  + C_1 \sum_{i=1}^\depth \norm{\Wmat^{(i)}}_\fro + C_2 \sum_{i=1}^{\depth} \log \abs{\det(\Wmat^{(i)})} \right]
\end{align}

where the determinant of doubly-block Toeplitz matrices under some assumption could be expressed with the Szegö Theorem <cit.> and can be approximated with the help of Random Matrix Theory <cit.>.

§.§ Going Beyond the Lipschitz Constant

Finally, in order to better understand the behavior of neural networks and the transformation they perform, it would be interesting to go beyond the Lipschitz constant and consider their full spectrum.
Indeed, the spectrum of a linear map is a set that contains the eigenvalues and can be seen as a description of the properties and behavior of the operator.
For example, for a linear operator $\Lmat: \Xset \rightarrow \Xset$, the spectrum gives precise information on the solvability of the following linear equation

\begin{equation}
\lambda \xvec - \Lmat \xvec = \yvec
\end{equation}

It is natural to ask if we could define a spectrum that equivalently gives information on the following nonlinear equation

\begin{equation}
\lambda \xvec - \Fmat(\xvec) = \yvec \enspace.
\end{equation}

In this line of research, <cit.> have defined a spectrum for nonlinear continuous Lipschitz operators which share important properties with the spectrum of linear operators.
More precisely, let $\Fmat: \Xset \rightarrow \Xset$ be a nonlinear continuous Lipschitz map, the Kachurovskij spectrum of $\Fmat$ is given by

\begin{equation}
\sigma(\Fmat) \triangleq \left\{ \lambda \in \Cbb \mid \lambda \Imat - \Fmat \text{ is not a lipeomorphism} \right\}
\end{equation}

where a nonlinear Lipschitz continuous operator is a lipeomorphism if its inverse is also nonlinear Lipschitz continuous.
We can also define the complement of the spectrum, , the Kachurovskij resolvent set as follows:

\begin{equation}
\mu(\Fmat) \triangleq \Cbb \setminus \sigma(\Fmat)
\end{equation}

The resolvent set can be seen as the set of complex numbers for which the operator is well behaved.
The Kachurovskij spectrum is a compact subset of the complex plane but may be empty.
Kachurovskij have also shown that the emptiness of this spectrum can be prevented if we restrict ourselves to nonlinear continuous Lipschitz operators that admit a Fréchet-derivative $\Fmat'(\xvec_0)$ at some point $\xvec_0 \in \Xset$.
In this case, the Kachurovskij spectrum share all the properties of a linear operator which are: closed, compact, bounded and non-empty.

Neural networks with differentiable nonlinearities are differentiable nonlinear Lipschitz continuous functions, therefore the study of the Kachurovskij spectrum could give important insight on their stability, invertibility and robustness to adversarial examples.

§ DISCUSSION

Although our contributions offer concrete techniques for building compact and reliable neural networks, they also highlight some important difficulties in them.
First, if we discard techniques such as pruning or quantization for building compact neural networks due to the necessity of training a large neural network prior to compression, designing parameters-efficient neural networks that are compact by design requires rethinking the whole architecture.
For computer vision tasks, the convolution operation is a compact and powerful transform, however, we still haven't found such equivalent transforms for other use cases.
Although the multi-head attention layer is more efficient than the attention layer for NLP tasks, using this type of transform in a neural network is still very parameter-hungry as demonstrated by the recent state-of-the-art for language models <cit.>.

Secondly, defense techniques against adversarial attacks have shown great improvements in the last few years.
However, with current state-of-the-art techniques, it is still difficult to reach an accuracy higher than 60% on CIFAR10 (which is considered a small dataset) and the accuracy decreases further on datasets with a larger dimensionality.
Consequently, building robust neural networks still remain very much an open question.
We believe that further breakthroughs in this area will come as a by-product on research on understanding neural networks.
Accordingly, we hope that our contribution to the understanding of diagonal-circulant and convolution neural networks is a small step in this direction.

CHAPTER: DIAGONAL CIRCULANT NEURAL NETWORKS FOR VIDEO CLASSIFICATION

This Appendix reports some additional experiments on video classification with diagonal-circulant neural networks.
These experiments have been done in the context of the [https://www.kaggle.com/c/youtube8m] video classification challenge.
This work was recognized as one of the 5 original approaches by the Google AI team that organized the workshop <cit.>.

§ INTRODUCTION

Classification of unlabeled videos streams is one of the challenging tasks for machine learning algorithms.
Research in this field has been stimulated by the recent release of several large annotated video datasets such as Sports-1M <cit.>, FCVID <cit.> or the  <cit.> dataset.

The naive approach to achieve video classification is to perform frame-by-frame image recognition, and to average the results before the classification step.
However, it has been shown by <cit.> that better results can be obtained by building features across different frames and several deep learning architectures have been designed to learn embeddings for sets of frames.
For example Deep Bag-of-Frames (DBoF) <cit.>, NetVLAD <cit.> or architectures based on Fisher Vectors <cit.>.

The DBoF embedding layer processes videos in two steps.
First, a learned transformation projects all the frames together into a high dimensional space.
Then, a max (or average) pooling operation aggregates all the embedded frames into a single discriminative vector representation of the video.
The NetVLAD embedding layer is built on a technique called vector of locally aggregated descriptors (VLAD) <cit.>.
This technique that aggregates a large number of local frame descriptors into a compact representation using a codebook of visual words.
In NetVlad, the codebook is directly learned end-to-end during training.
Finally, NetFisherVector (NetFV) is inspired by <cit.> and uses first and second-order statistics as video descriptors also gathered in a codebook.
The technique can benefit from deep learning by using a deep neural network to learn the codebook <cit.>.

All the architectures mentioned above can be used to build video features in the sense of features that span across several frames, but they are not designed to exploit the sequential nature of videos and capture motion.
In order to truly learn spatio-temporal features and account for motion in videos, several researchers have looked into recurrent neural networks (LSTM <cit.>) and 3D convolutions <cit.> (in space and time).
However, these approaches do not outperform non-sequential models, and the single best model proposed by <cit.> (winner of the first competition) is based on NetVLAD.

The 2nd YouTube-8M Video Understanding Challenge includes a constraint on the model size and many competitors have been looking into building efficient memory models with high accuracy.
There are two kinds of techniques to reduce the memory required for training and/or inference in neural networks.
The first kind aims at compressing an existing neural network into a smaller one, (thus it only impacts the size of the model at inference time).
The second one aims at constructing models that are compact by design.

§ COMPACT ARCHITECTURE USING DIAGONAL AND CIRCULANT MATRICES

Building on the matrix decomposition presented in <Ref>, we introduce a compact neural network architecture for video classification where dense matrices have been replaced by products of circulant and diagonal matrices.

§.§ Base Model

Diagram of the architecture proposed by <cit.> and used for the experiments. The sample goes through an embedding layer and is reduced with a Fully Connected layer. The results are then concatenated and classified with a Mixture-of-Experts and Context Gating layer.

We demonstrate the benefit of the decomposition into diagonal and circulant matrices using a base model which has been proposed by <cit.>.
This architecture can be decomposed into three blocks of layers, as illustrated in <Ref>.
The first block of layers, composed of the Deep Bag-of-Frames embedding, is meant to process audio and video frames independently.
The DBoF layer computes two embeddings: one for the audio and one for the video.
In the next paragraph, we will only focus on describing the video embedding (The audio embedding is computed in a very similar way).
We represent a video $\Vmat$ as a set of $m$ frames $\{\vvec^{(1)}, \ldots, \vvec^{(m)}\}$ where each frame $\vvec^{(i)} \in \Rbb^k$ is a vector of visual features extracted from the frame image.
In the context of the competition, each $\vvec_i$ is a vector of 1024 visual features extracted using the last fully connected layer of an Inception network trained on ImageNet.
The DBoF layer then embeds a video $\Vmat$ into a vector $\vvec'$ drawn from a $\pvec$ dimensional vector space as follows:

\begin{equation}
\vvec' = \max \left\{\Wmat \vvec^{(i)} \mid \vvec^{(i)} \in \Vmat \right\}
\end{equation}

where $\Wmat$ is a matrix in $\Rbb^{p \times k}$ (learned) and max is the element-wise maximum operator.
We typically choose $p > k$, ($p = 8192$).
Note that because this formulation is framed in term of sets, it can process videos of different lengths (, a different value of $m$).
A second block of layers reduces the dimensionality of each embedding layer (audio and video), and merges the result into a single vector by using a simple concatenation operation.
We chose to reduce the dimensionality of each embedding layer separately before the concatenation operation to avoid the concatenation of two high dimensional vectors.

Finally, the classification block uses a combination of Mixtures-of-Experts (MoE) and Context Gating to calculate the final probabilities.
The Mixtures-of-Experts layer introduced by <cit.> and proposed for video classification by <cit.> is used to predict each label independently.
It consists of a gating and experts networks which are concurrently learned.
The gating network learns which experts to use for each label and the experts layers learn how to classify each label.
The context gating operation was introduced by <cit.> and captures dependencies among features and re-weight probabilities based on the correlation of the labels.
For example, it can capture the correlation of the labels ski and snow and re-adjust the probabilities accordingly.

§.§ Robust Deep Bag-of-Frames pooling method

We propose a technique to extract more performance from the base model with DBoF embedding.
The maximum pooling is sensitive to outliers and noise whereas the average pooling is more robust.
We propose a method which consists in taking several samples of frames, applying the upsampling followed by the maximum pooling to these samples, and then averaging over all samples.
More formally, assume a video contains $m$ frames $\vvec_1, \ldots, \vvec_m \in \Rbb^{1024}$.
We first draw $n$ random samples $\Smat^{(1)} \ldots \Smat^{(n)}$ of size $k$ from the set $\left\{ \vvec^{(1)}, \ldots, \vvec^{(m)} \right\}$.
The output of the robust-DBoF layer is:

\begin{equation}
\frac{1}{n} \sum_{i=1}^{n} \max \left\{ \Wmat \vvec :\vvec \in S_{i} \right\}
\end{equation}

Depending on $n$ and $k$, this pooling method is a trade-off between the max pooling and the average pooling.
Thus, it is more robust to noise, as will be shown in the experiments section.

§.§ Compact Representation of the Base Model

In order to build compact layers, we use the diagonal-circulant matrix decomposition.
The layers are represented as follows:

\begin{equation}
\phi(\xvec) = \rho\left(\left[\prod_{i=1}^{m} \Dmat^{(i)} \Cmat^{(i)} \right] \xvec + \bvec \right)
\end{equation}

where the parameters of each matrix $\Dmat^{(i)}$ and $\Cmat^{(i)}$ are trained using a gradient based optimization algorithm, and $m$ defines the number of factors.
Increasing the value of $m$ increases the number of trainable parameters and therefore the modeling capabilities of the layer.
In our experiments, we chose the number of factors $m$ empirically to achieve the best trade-off between model size and accuracy.

To measure the impact of the size of the model and its accuracy, we represent layers in their compact form independently.
Given that circulant and diagonal matrices are square, we use concatenation and slicing to achieve the desired dimension.
As such, with $m=1$, the weight matrix of size $1024 \times 8192$ of the video embedding is represented by a concatenation of 8 DC matrices and the weight matrix of size $8192 \times 512$ is represented by a single DC matrix with size $8192 \times 8192$ and the resulting output is sliced at the 512 dimension.
We denote layers in their classic form as “Dense” and layers represented with circulant and diagonal factors as “Compact”.

§.§ Leveraging Architectural Diversity

In order to benefit from architectural diversity, we also devise a single model architecture that combines different types of embedding layers.
As we can see in <Ref>, video and audio frames are processed by several embedding layers before being reduced by a series of compact fully connected layers.
The output of the compact fully connected layers are then averaged, concatenated and fed into the final classification block.
<Ref> shows the result of different models given the number of parameters.
The use of circulant matrices allow us to fit this model in GPU memory.
For example, the diversity model with a NetVLAD embedding (cluster size of 256) and NetFV embedding (cluster size of 128) has 160 millions parameters (600 Mo) in the compact version and 728M (2.7 Go) in the dense version.

Diagram of architecture with several embeddings devised to leverage the diversity of an Ensemble in a single model.

§ EXPERIMENTS

In this section, we first evaluate the pooling technique proposed in <Ref>.
Then, we conduct experiments to evaluate the accuracy of our compact models.
In particular, we investigate which layer benefits the most from a circulant representation and show that our approach where both the diagonal and the circulant is learned performs better than the approach from <cit.> for the video classification problem.
Finally, we compare all our models on a two dimensional size accuracy scale in order to evaluate the trade-off between size and accuracy of each one of our models.
All the figures of this section can be found at the end of the chapter.

Experimental Setup

All the experiments of this appendix have been done in the context of the 2nd YouTube-8M Video Understanding Challenge with the dataset.
We trained our models with the full training set and 70% of the validation set which corresponds to a total of 4822555 examples.
We used the data augmentation technique proposed by <cit.> to virtually double the number of inputs.
The method consists in splitting the videos into two equal parts.
This approach is motivated by the observation that a human could easily label the video by watching either the beginning or the ending of the video.
All our experiments are developed with TensorFlow Framework <cit.>.
We trained our models with the CrossEntropy loss and used Adam optimizer with a 0.0002 learning rate and a 0.8 exponential decay every 4 million examples.
All fully connected layers are composed of 512 units.
DBoF, NetVLAD and NetFV are respectively 8192, 64 and 64 of cluster size for video frames and 4096, 32, 32 for audio frames.
We used 4 mixtures for the MoE Layer.
We used all the available 150 frames and robust max pooling introduced in <Ref> for the DBoF embedding.
In order to stabilize and accelerate the training, we used batch normalization before each nonlinear activation and gradient clipping.
We used the GAP (Global Average Precision), as used in the 2nd YouTube-8M Video Understanding Challenge, to compare our experiments.
The GAP metric is defined as follows:

\begin{equation}
\text{GAP} = \sum_{i=1}^{P}p(i) \Delta r(i)
\end{equation}

where $P$ is the number of final predictions, $p(i)$ the precision, and $r(i)$ the recall.
We limit our evaluation to 20 predictions for each video.
All experiments have been realized on a cluster of 12 nodes. Each node has 160 POWER8 processor, 128 Go of RAM and 4 Nividia Titan P100.

Robust Deep Bag-of-Frames pooling method

We evaluate the performance of our Robust DBoF embedding.
In accordance with the work of <cit.>, we find that average pooling performs better than maximum pooling.
<Ref> shows that the proposed robust maximum pooling method outperforms both maximum and average pooling.

Impact of Circulant Matrices on Different Layers

Model     #Parameters     CR     GAP@20     Diff.

Dense Model      45M       –     0.846     –

Compact DBoF     36M     18.4     0.838     -0.008

Compact FC       41M      9.2     0.845     -0.001

Compact MoE      12M     72.0     0.805     -0.041

Effect of the compactness of different layers.

This series of experiments aims at understanding the effect of compactness over different layers.
<Ref> shows the result in terms of the number of weights, compression ratio (CR) with respect to the dense model and GAP score.
In these experiments, for speeding-up the training phase, we did not use the audio features and exploited only the video information.
The compact fully connected layer achieves a compression rate of 9.5 while having a very similar performance, whereas the compact DBoF and MoE achieve a higher compression rate at the expense of accuracy.
<Ref> shows that the model with a compact FC converges faster than the dense model.
The model with a compact DBoF shows a big variance over the validation GAP which can be associated with a difficulty to train.
The model with a compact MoE is more stable but at the expense of its performance.

Another series of experiments investigates the effect of adding factors of diagonal-circulant layers.
<Ref> shows that there is no gain in accuracy even if the number of weights increases.
It also shows that adding factors has an important effect on the speed of training.
On the basis of this result, given the performance and compression ratio, we can consider that representing the fully connected layer of the base model in a compact fashion can be a good trade-off.

2*#Factors     2cFC Layer     2*GAP@20

#Parameters     CR

–     6.29M     –     0.861

1     12K     99.8     0.861

3     73K     98.8     0.861

6     147K     97.6     0.859

Evolution of the number of parameters and accuracy according to the number of factors.

Comparison with Related Works

Circulant matrices have already been used in neural networks by <cit.>.
They proposed to replace fully connected layers by a circulant and diagonal matrices where the circulant matrix is learned by a gradient based optimization algorithm and the diagonal matrix is random with values in {-1, 1}.
We compare our more general framework with their approach.
<Ref> shows the validation GAP according to the number of epochs of the base model with a compact fully connected layer implemented with both approaches.

Compact Baseline Model with Different Embeddings

To compare the performance and the compression ratio we can expect, we consider different settings where the compact fully connected layer is used together with different embeddings.
Figures <ref>, <ref>,
<ref> and <Ref>
show the performance of the base model with DBoF, NetVLAD and NetFV embeddings with a Dense and Compact layer.
Notice that we can get a bigger compression rate with NetVLAD and NetFV due to the fact that the output of the embedding is in a higher dimensional space which implies a larger weight matrix for the fully connected layer.
Although the compression rate is higher, it is at the expense of accuracy.

Tradeoff Between Model Size and Accuracy

To conclude our experimental evaluation, we compare all our models in terms of size and accuracy.
The results are presented in <Ref>.
As we can see in this figure, the most compact models are obtained with the circulant NetVLAD and NetFV.
We can also see that the complex architectures described in <Ref> (DBoF + NetVLAD) achieve top performance but at the cost of a large number of weights.
Finally, the best trade-off between size and accuracy is obtained using the DBoF embedding layer and achieves a GAP of 0.861 for only 60 millions weights.

Embedding     Method     #Parameters     CR     GAP@20

2*DBoF     FC Dense     65M     –     0.861

FC Circulant     59M     9.56     0.861

2*NetVLAD     FC Dense     86M     –     0.864

FC Circulant     50M     41.1     0.851

2*NetFisher     FC Dense     122M     –     0.860

FC Circulant     51M     58.1     0.848

Impact of the compression of the fully connected layer of the model architecture with Audio and Video features vector and different types of embeddings.

§ CONCLUDING REMARKS

In this appendix, we demonstrated that circulant matrices and diagonal matrices can be a great tool to design compact neural network architectures for video classification tasks.
Our experiments demonstrate that the best trade-off between size and accuracy is obtained using circulant DBoF embedding layers.
We investigated a model with multiple embeddings to leverage the performance of an Ensemble but found it ineffective.
The good performance of Ensemble models, , why aggregating different distinct models performs better that incorporating all the diversity in a single architecture is still an open problem.
Our future work will be devoted to address this challenging question and to pursue our effort to devise compact models achieving the same accuracy as larger one, and to study their theoretical properties.

Impact of robust DBoF with $n=10$ and $k=15$ on the Deep Bag-of-Frames embedding compared to max and average pooling.

GAP score of models according to the number of epochs for different compact models.

GAP difference between the approach proposed by <cit.> where the diagonals from the decomposition are initialized from the set $\{-1, +1\}$ and kept fixed and our approach where the values of the diagonals are learned.

GAP score of models with compact DBoF embedding and dense fully connected layer.

GAP score of models with compact NetVLAD embedding and dense fully connected layer.

GAP score of models with compact NetFV embedding and dense fully connected layer.

Comparison between different models with compact fully connected layers.

CHAPTER: THEORETICAL EVIDENCE FOR ADVERSARIAL ROBUSTNESS THROUGH RANDOMIZATION

This Appendix concerns a collaboration with Rafael Pinot, Laurent Meunier, Hisashi Kashima, Florian Yger, Cédric Gouy-Pailler and Jamal Atif.
This work has been published at the Conference on Neural Information Processing Systems (NeurIPS) 2019.
It investigates the theory of robustness against adversarial attacks. It focuses on the family of randomization techniques that consist in injecting noise in the network at inference time.
All proofs of this appendix can be found in the long version of the paper.[https://arxiv.org/abs/1902.01148]
For simplification, we left the notation as in the original paper.

§ INTRODUCTION

Adversarial attacks are some of the most puzzling and burning issues in modern machine learning.
An adversarial attack refers to a small, imperceptible change of an input maliciously designed to fool the result of a machine learning algorithm.
Since the seminal work of <cit.> exhibiting this intriguing phenomenon in the context of deep learning, a wealth of results have been published on designing attacks <cit.> and defenses <cit.>), or on trying to understand the very nature of this phenomenon <cit.>.
Most methods remain unsuccessful to defend against powerful adversaries <cit.>.
Among the defense strategies, randomization has proven effective in some contexts.
It consists in injecting random noise (both during training and inference phases) inside the network architecture, , at a given layer of the network.
Noise can be drawn either from Gaussian <cit.>, Laplace <cit.>, Uniform <cit.>, or Multinomial <cit.> distributions.
Remarkably, most of the considered distributions belong to the Exponential family.
Albeit these significant efforts, several theoretical questions remain unanswered.
Among these, we tackle the following, for which we provide principled and theoretically-founded answers:

Q1: To what extent does a noise drawn from the Exponential family preserve robustness (in a sense to be defined) to adversarial attacks?

We introduce a definition of robustness to adversarial attacks that is suitable to the randomization defense mechanism.
As this mechanism can be  described as a non-deterministic querying process, called probabilistic mapping in the sequel, we propose a formal definition of robustness relying on a metric/divergence between probability measures.
A key question arises then about the appropriate metric/divergence for our context.
This requires tools for comparing divergences the introduced robustness definition.
Renyi divergence turned out to be a measure of choice, since it satisfies most of the desired properties  (coherence, strength, and computational tractability).
Finally, thanks to the existing links between the Renyi divergence and the Exponential family, we were able to prove  that methods based on noise injection from the Exponential family  ensures robustness to adversarial examples (cf. <Ref>).

Q2: Can we guarantee a good accuracy under attack for classifiers defended with this kind of noise?

We present an upper bound on the drop of accuracy (under attack) of the methods defended with noise drawn from the Exponential family (<Ref>).
Then, we illustrate this result by training different randomized models with Laplace and Gaussian distributions on CIFAR-10 dataset.
These experiments highlight the trade-off between accuracy and robustness that depends on the amount of noise one injects in the network.
Our theoretical and experimental conclusion is that randomized defenses are competitive (with the current state-of-the-art <cit.>) given the intensity of noise injected in the network.

Outline of the chapter:
We present in <Ref> the related work on randomized defenses to adversarial examples.
<Ref> introduces the definition of robustness relying on a metric/divergence between probability measures, and discusses the key role of the Renyi divergence.
We state in <Ref> our main results on the robustness and accuracy of Exponential family-based defenses.
<Ref> presents extensive experiments supporting our theoretical findings.
<Ref> provides concluding remarks.

§ RELATED WORKS

Injecting noise into algorithms to improve their robustness has been used for ages in detection and signal processing tasks <cit.>.
It has also been extensively studied in several machine learning and optimization fields, robust optimization <cit.> and data augmentation techniques <cit.>.
Recently, noise injection techniques have been adopted by the adversarial defense community, especially for neural networks, with very promising results.
Randomization techniques are generally oriented towards one of the following objectives: experimental robustness or provable robustness.

Experimental robustness:
The first technique explicitly using randomization at inference time as a defense appeared during the 2017 NeurIPS defense challenge <cit.>.
This method uniformly samples over geometric transformations of the image to select a substitute image to feed the network.
Then <cit.> proposed to use stochastic activation pruning based on a multinomial distribution for adversarial defense.
Several works <cit.> propose to inject Gaussian noise directly on the activation of selected layers both at training and inference time.
While these works hypothesize that noise injection makes the network robust to adversarial perturbations, they do not provide any formal justification on the nature of the noise they use or on the loss of accuracy/robustness of the  network.

Provable robustness:
<cit.> proposed a randomization method by exploiting the link between differential privacy <cit.> and adversarial robustness.
Their framework, called “randomized smoothing” [Name introduced by <cit.> after the work of <cit.>.], inherits some theoretical results from the differential privacy community allowing them to evaluate the level of accuracy under attack of their method.
Initial results by <cit.> have been refined by <cit.>, and by <cit.>.
Our work belongs to this line of research.
However, our framework does not treat exactly the same class of defenses.
Notably, we provide theoretical arguments supporting the defense strategy based on randomization techniques relying on the exponential family, and derive a new bound on the adversarial generalization gap, which completes the results obtained so far on certified robustness.
Furthermore, our focus is on the network randomized by noise injection, “randomized smoothing” instead uses this network to create a new classifier robust to attacks.

Since the initial discovery of adversarial examples, a wealth of non randomized defense approaches have also been proposed, inspired by various machine learning domains such as adversarial training <cit.>, image reconstruction <cit.> or robust learning <cit.>.
Even if these methods have their own merits, a thorough evaluation made by <cit.> shows that most defenses can be easily broken with known powerful attacks <cit.>.
Adversarial training, which consists in training a model directly on adversarial examples, came out as the best defense in average.
Defense based on randomization could be overcome by the Expectation Over Transformation technique proposed by <cit.> which consists in taking the expectation over the network to craft the perturbation.
In this chapter, to ensure that our results are not biased by obfuscated gradients, we follow the principles provided by <cit.> and evaluate our randomized networks with this technique.
We show that randomized defenses are still competitive given the intensity of noise injected in the network.

§ GENERAL DEFINITIONS OF RISK AND ROBUSTNESS

§.§ Risk, robustness and probabilistic mappings

Let us consider two spaces $\mathcal{X}$ (with norm $\norm{\ \cdot\ }_{\mathcal{X}}$), and $\mathcal{Y}$.
We consider the classification task that seeks a hypothesis (classifier) $h: \mathcal{X} \rightarrow \mathcal{Y}$ minimizing the risk of $h$ some ground-truth distribution $\mathcal{D}$ over $\mathcal{X}\times\mathcal{Y}$.
The risk of $h$ $\mathcal{D}$ is defined as

\begin{align*}
\Risk(h) \triangleq \mathbb{E}_{(x,y)\sim \mathcal{D}}\left[ \mathds{1} \left( h(x) \neq y \right)\right].
\end{align*}

Given a classifier $h: \mathcal{X} \rightarrow \mathcal{Y}$, and some input $x \in \mathcal{X}$ with true label $y_{true} \in \mathcal{Y}$, to generate an adversarial example, the adversary seeks a $\tau$ such that $h(x+\tau) \neq y_{true}$, with some budget $\alpha$ over the perturbation (, with $\norm{\tau}_{\mathcal{X}} \leq\alpha$).
$\alpha$ represents the maximum amount of perturbation one can add to $x$ without being spotted (the perturbation remains humanly imperceptible).
The overall goal of the adversary is to find a perturbation crafting strategy that both maximizes the risk of $h$, and keeps the values of $\norm{\tau}_{\mathcal{X}}$ small.
To measure this risk "under attack" we define the notion of adversarial $\alpha$-radius risk of $h$ $\mathcal{D}$ as follows

\begin{align}
\advRisk(h) \triangleq \mathbb{E}_{(x,y) \sim \mathcal{D}} \left[ \sup_{\norm{\tau}_{\mathcal{X}} \leq \alpha} \mathds{1}\left(h(x+\tau) \neq y\right) \right]\enspace.
\end{align}

In practice, the adversary does not have any access to the ground-truth distribution.
The literature proposed several surrogate versions of $\advRisk(h)$ (see <cit.> for more details) to overcome this issue.
We focus our analysis on the one used by <cit.> denoted $\alpha$-radius prediction-change risk of $h$ $\mathcal{D}_{\mathcal{X}}$ (marginal of $\mathcal{D}$ for $\mathcal{X}$), and defined as

\begin{align}
\PCadvRisk(h) \triangleq \mathbb{P}_{x\sim \mathcal{D}_{\mathcal{X}}}\left[\exists \tau \in \B \text{ s.t. } h(x+\tau)\neq h(x) \right]
\end{align}

where for any $\alpha \geq 0$,   $\B \triangleq \{\tau \in \mathcal{X} \text{ s.t. } \norm{\tau}_{\mathcal{X}} \leq \alpha\}\enspace.$

As we will inject some noise in our classifier in order to defend against adversarial attacks, we need to introduce the notion of “probabilistic mapping”. Let $\mathcal{Y}$ be the output space, and $\mathcal{F}_{\mathcal{Y}}$ a $\sigma$-$ algebra$ over $\mathcal{Y}$. Let us also denote $\mathcal{P}(\mathcal{Y})$ the set of probability measures over $(\mathcal{Y},\mathcal{F}_{\mathcal{Y}})$.

Let $\mathcal{X}$ be an arbitrary space, and $(\mathcal{Y},\mathcal{F}_{\mathcal{Y}})$ a measurable space. A probabilistic mapping from $\mathcal{X}$ to $\mathcal{Y}$ is a mapping $\probmap: \mathcal{X} \to \mathcal{P}(\mathcal{Y})$.
To obtain a numerical output out of this probabilistic mapping, one needs to sample $y$ according to $\probmap(x)$.

This definition does not depend on the nature of $\mathcal{Y}$ as long as $(\mathcal{Y},\mathcal{F}_{\mathcal{Y}})$ is measurable.
In that sense, $\mathcal{Y}$ could be either the label space or any intermediate space corresponding to the output of an arbitrary hidden layer of a neural network.
Moreover, any mapping can be considered as a probabilistic mapping, whether it explicitly injects noise (see <cit.>) or not.
In fact, any deterministic mapping can be considered as a probabilistic mapping, since it can be characterized by a Dirac measure.
Accordingly, the definition of a probabilistic mapping is fully general and equally treats networks with or without noise injection.
There exists no definition of robustness against adversarial attacks that comply with the notion of probabilistic mappings.
We settle that by generalizing the notion of prediction-change risk initially introduced by <cit.> for deterministic classifiers.
Let $\probmap$ be a probabilistic mapping from $\mathcal{X}$ to $\mathcal{Y}$, and $d_{\mathcal{P}(\mathcal{Y})}$ some metric/divergence on $\mathcal{P}(\mathcal{Y})$.
We define the $(\alpha,\epsilon)$-radius prediction-change risk of $\probmap$ $\mathcal{D}_{\mathcal{X}}$ and $d_{\mathcal{P}(\mathcal{Y})}$ as

\begin{equation}
\PCadvRisk(\probmap,\epsilon) \triangleq  \mathbb{P}_{x\sim \mathcal{D}_{\mathcal{X}}}\left[ \exists \tau \in B(\alpha) \text{ s.t. } d_{\mathcal{P}(\mathcal{Y})}(\probmap(x+\tau),\probmap(x)) > \epsilon \right] \enspace.
\end{equation}

These three generalized notions allow us to analyze noise injection defense mechanisms (Theorems <ref>, and <ref>).
We can also define adversarial robustness (and later adversarial gap) thanks to these notions.

Let $d_{\mathcal{P}(\mathcal{Y})}$ be a metric/divergence on $\mathcal{P}(\mathcal{Y})$.
The probabilistic mapping $\probmap$ is said to be $d_{\mathcal{P}(\mathcal{Y})}$-$(\alpha, \epsilon, \gamma)$ robust if

\begin{equation}
\PCadvRisk(\probmap,\epsilon) \leq \gamma \enspace.
\end{equation}

It is difficult in general to show that a classifier is $d_{\mathcal{P}(\mathcal{Y})}$-$(\alpha, \epsilon, \gamma)$ robust.
However, we can  derive some bounds for particular divergences that will ensure robustness up to a certain level (Theorem <ref>).
It is worth noting that our definition of robustness depends on the considered metric/divergence between probability measures.
Lemma <ref> gives some insights on the monotony of the robustness according to the parameters, and the probability metric/divergence at hand.

Let $\probmap$ be a probabilistic mapping, and let  $d_{1}$ and $d_{2}$ be two metrics on $\mathcal{P}(\mathcal{Y})$.
If there exists a non decreasing function $ \phi: \mathbb{R} \to \mathbb{R}$ such that $\forall \mu_1,\mu_2 \in \mathcal{P}(\mathcal{Y})$, $d_{1}(\mu_1,\mu_2) \leq \phi(d_{2}(\mu_1,\mu_2)) $, then the following assertion holds:

\begin{equation}
\probmap \text{ is } d_{2}\text{-}(\alpha, \epsilon, \gamma)\text{-robust} \implies \probmap \text{ is }d_{1}\text{-}(\alpha, \phi(\epsilon), \gamma)\text{-robust}
\end{equation}

As suggested in Definition <ref> and Lemma <ref>, any given choice of metric/divergence will instantiate a particular notion of adversarial robustness and it should be carefully selected.

§.§ On the choice of the metric/divergence for robustness

The aforementioned formulation naturally raises the question of the choice of the metric used to defend against adversarial attacks.
The main notions that govern the selection of an appropriate metric/divergence are  coherence, strength, and computational tractability.
A metric/divergence is said to be coherent if it naturally fits the task at hand (classification tasks are intrinsically linked to discrete/trivial metrics, conversely to regression tasks).
The strength of a metric/divergence refers to its ability to cover (dominate) a wide class of others in the sense of Lemma <ref>.
In the following, we will focus on both the total variation metric and the Renyi divergence, that we consider as respectively the most coherent with the classification task using probabilistic mappings, and the strongest divergence.
We first discuss how total variation metric is coherent with randomized classifiers but suffers from computational issues.
Hopefully, the Renyi divergence provides good guarantees about adversarial robustness, enjoys nice computational properties, in particular when considering  Exponential family distributions, and is strong enough to dominate a wide range of metrics/divergences including total variation.

Let  $\mu_1$ and $\mu_2$ be two measures in $\mathcal{P}(\mathcal{Y})$, both dominated by a third measure $\nu$.
The trivial distance $ d_{T}(\mu_1,\mu_ \triangleq \mathds{1}\left(\mu_1 \neq \mu_2\right)$ is the simplest distance one can define between $\mu_1$ and $\mu_2$.
In the deterministic case, it is straightforward to compute (since the numerical output of the algorithm characterizes its associated measure), but this is not the case in general.
In fact one might not have access to the true distribution of the mapping, but just to the numerical outputs.
Therefore, one needs to consider more sophisticated metrics/divergences, such as the total variation distance $d_{TV}(\mu_1,\mu_2) \triangleq \sup_{Y \in \mathcal{F}_{\mathcal{Y}}} |\mu_1 (Y) - \mu_2(Y)|$.
The total variation distance is one of the most broadly used probability metrics.
It admits several very simple interpretations, and is a very useful tool in many mathematical fields such as probability theory, Bayesian statistics, coupling or transportation theory.
In transportation theory, it can be rewritten as the solution of the Monge-Kantorovich problem with the cost function $c(y_1,y_2) =\mathds{1}\left(y_1 \neq y_2\right)$: $ \inf\int_{\mathcal{Y}^{2}}\mathds{1}\left(y_1 \neq y_2\right) \,\diff \pi(y_1,y_2)\, ,$ where the infimum is taken over all joint probability measures $\pi$ on $(\mathcal{Y}\times \mathcal{Y}, \mathcal{F}_{\mathcal{Y} } \otimes \mathcal{F}_{\mathcal{Y}})$ with marginals $\mu_1$ and $\mu_2$.
According to this interpretation, it seems quite natural to consider the total variation distance as a relaxation of the trivial distance on $[0,1]$ (see the book of <cit.> for details).
In the deterministic case, the total variation and the trivial distance coincides.
In general, the total variation allows a finer analysis of the probabilistic mappings than the trivial distance.
But it suffers from a high computational complexity.
In the following of the chapter we will show how to ensure robustness regarding TV distance.

Finally, denoting by $g_1$ and $g_2$ the respective probability distributions $\nu$, the Renyi divergence of order $\lambda$ <cit.> writes as

\begin{equation}
d_{R,\lambda}(\mu_1,\mu_2) \triangleq \frac{1}{\lambda -1}\log \int_{\mathcal{Y}} g_2(y)  \left(\frac{g_1(y)}{g_2(y)}\right)^{\lambda} \,\diff \nu(y).
\end{equation}

The Renyi divergence is a generalized measure defined on the interval $(1,\infty)$, where it equals the Kullback-Leibler divergence when $\lambda \rightarrow 1$ (that will be denoted $d_{KL}$), and the maximum divergence when $\lambda \rightarrow \infty$.
It also has the very special property of being non decreasing $\lambda$.
This divergence is very common in machine learning, especially in its Kullback-Leibler form as it is widely used as the loss function (cross entropy) of classification algorithms.
It enjoys the desired properties  since it bounds the TV distance, and is tractable.
Furthermore, Proposition <ref> proves that Renyi-robustness implies TV-robustness, making it a suitable surrogate for the trivial distance.

Let $\probmap$ be a probabilistic mapping, then $\forall\lambda\geq1$:

\begin{equation}
\probmap \text{ is }  d_{R,\lambda}\text{-}(\alpha, \epsilon, \gamma)\text{-robust} \implies \probmap \text{ is } d_{TV}\text{-}(\alpha, \epsilon', \gamma)\text{-robust}
\end{equation}

\begin{equation}
\textnormal{ with } \epsilon' = \min \left(\frac{3}{2}\left(\sqrt{1 + \frac{4\epsilon}{9}} - 1\right)^{1/2}, \frac{\exp(\epsilon +1) -1}{\exp(\epsilon +1) +1}\right) \enspace.
\end{equation}

A crucial property of Renyi-robustness is the Data processing inequality.
It is a well-known inequality from information theory which states that “post-processing cannot increase information” <cit.>.
In our case, if we consider a Renyi-robust probabilistic mapping, composing it with a deterministic mapping maintains Renyi-robustness with the same level.

Let us consider a probabilistic mapping $\probmap:\mathcal{X}\rightarrow\mathcal{P}(\mathcal{Y})$. Let us also denote $\rho:\mathcal{Y}\rightarrow\mathcal{Y}'$ a deterministic function.
If $U \sim \probmap(x)$ then the probability measure $M'(x)$ s.t $\rho(U) \sim M'(x)$ defines a probabilistic mapping $M':\mathcal{X}\rightarrow\mathcal{P}(\mathcal{Y}')$.
For any $\lambda>1$ if $\probmap$ is $d_{R,\lambda}$-$(\alpha,\epsilon,\gamma)$ robust then $M'$ is also is $d_{R,\lambda}$-$(\alpha,\epsilon,\gamma)$ robust.

Data processing inequality will allow us later to inject some additive noise in any layer of a neural network and to ensure Renyi-robustness.

§ DEFENSE MECHANISMS BASED ON  EXPONENTIAL FAMILY NOISE INJECTION

§.§ Robustness through Exponential family noise injection

For now, the question of which class of noise to add is treated ad hoc.
We choose here to investigate one particular class of noise closely linked to the Renyi divergence, namely Exponential family distributions, and demonstrate their interest.
Let us first recall what the Exponential family is.

Let $\Theta$ be an open convex set of $\mathbb{R}^{n}$, and $\theta \in \Theta$.
Let $\nu$ be a measure dominated by $\mu$ (either by the Lebesgue or counting measure), it is said to be part of the Exponential family of parameter $\theta$ (denoted $E_{F}(\theta,t,k)$) if it has the following probability density function

\begin{equation}
p_{F}(z,\theta)=\exp\left\{ \langle t(z),\theta \rangle -u(\theta) +k(z) \right\}
\end{equation}

where $t(z)$ is a sufficient statistic, $k$ a carrier measure (either for a Lebesgue or a counting measure) and $u(\theta) = \log \int_{z} \exp\left\{ <t(z),\theta> +k(z) \right\} \,\diff z $.

To show the robustness of randomized networks with noise injected from the Exponential family, one needs to define the notion of sensitivity for a given deterministic function:

For any $\alpha\geq0$ and for any $\norm{\ \cdot\ }_A$ and $\norm{\ \cdot\ }_B$ two norms, the $\alpha$-sensitivity of $f$ $\norm{\ \cdot\ }_A$ and $\norm{\ \cdot\ }_B$ is defined as

\begin{equation}
\Delta^{A,B}_\alpha(f) \triangleq \sup\limits_{ x,y \in \mathcal{X}, \norm{x-y}_{A} \leq \alpha} \norm{f(x) - f(y)}_B \enspace.
\end{equation}

Let us consider an  $n$-layer feedforward neural network  $\mathcal{N}(\ \cdot\ ) = \phi^n \circ \cdots \circ \phi^1(\ \cdot\ )$.
For any $i\in\left[n\right]$, we define $\mathcal{N}_{|i}(\ \cdot\ ) = \phi^i\circ \cdots \circ \phi^1(\ \cdot\ )$ the neural network truncated at layer $i$.
Theorem <ref> shows that, injecting noise drawn from an Exponential family distribution ensures robustness to adversarial example attacks in the sense of Definition <ref>.

Let us denote $\mathcal{N}_{X}^i(\ \cdot\ ) = \phi^n\circ \cdots \circ\phi^{i+1}(\mathcal{N}_{|i}(\ \cdot\ )+X)$ with $X$ a random variable.
Let us also consider two arbitrary norms $\norm{\ \cdot\ }_{A}$ and $\norm{\ \cdot\ }_{B}$  respectively on $\mathcal{X}$ and on the output space of $\mathcal{N}_{X}^i$.

* If $X\sim E_{F}(\theta,t,k)$ where $t$ and $k$ have non-decreasing modulus of continuity $\omega_t$ and $\omega_k$.
Then for any $\alpha \geq 0$, $\mathcal{N}_{X}^i(\ \cdot\ )$ defines a probabilistic mapping that is $d_{R,\lambda}$-$(\alpha,\epsilon)$ robust with $\epsilon = \norm{\theta}_2 \omega^{B,2}_t(\Delta^{A,B}_{\alpha}(\mathcal{N}_{|i})) +\omega_k^{B,1}(\Delta^{A,B}_{\alpha}(\mathcal{N}_{|i})) $ where $\norm{\ \cdot\ }_2$ is the norm corresponding to the scalar product in the definition of the exponential family density function and $\norm{\ \cdot\ }_1$ is the absolute value on $\mathbb{R}$.
[The notion of continuity modulus is defined in the arxiv version of this chapter: https://arxiv.org/abs/1902.01148.]

* If $X$ is a centered Gaussian random variable with a non degenerated matrix parameter $\Sigma$.
Then for any $\alpha \geq 0$, $\mathcal{N}_{X}^i(\ \cdot\ )$ defines a probabilistic mapping that is $d_{R,\lambda}$-$(\alpha,\epsilon)$ robust with $ \epsilon = \frac{\lambda \Delta^{A,2}_{\alpha}(\phi)^2 }{2 \sigma_{min}(\Sigma) } $ where $\norm{\ \cdot\ }_2$ is the canonical Euclidean norm on $\mathbb{R}^n$.

In simpler words, the previous theorem ensures stability in the neural network when injecting noise the distribution of the output.
Intuitively, if two inputs are close $\norm{\ \cdot\ }_{A}$, the output distributions of the network will be close in the sense of Renyi divergence.
It is well known that in the case of deterministic neural networks, the Lipschitz constant becomes bigger as the number of layers increases <cit.>.
By injecting noise at layer $i$, the notion of robustness only depends on the sensitivity of the first $i$ layers of the network and not the following ones.
In that sense, randomization provides a more precise control on the “continuity” of the neural network.
In the next section, we show that thanks to the notion of robustness probabilistic mappings, one can bound the loss of accuracy of a randomized neural network when it is attacked.

§.§ Bound on the generalization gap under attack

The notions of risk and adversarial risk can easily be generalized to encompass probabilistic mappings.

Let $\probmap$ be a probabilistic mapping from $\mathcal{X}$ to $\mathcal{Y}$, the risk and the $\alpha$-radius adversarial risk of $\probmap$ $\mathcal{D}$ are defined as

\begin{align}
\Risk(\probmap) &\triangleq \mathbb{E}_{(x,y) \sim \mathcal{D}} \left[ \mathbb{E}_{y'\sim \probmap(x)} \left[ \mathds{1} \left( y' \neq y \right)\right]\right] \\
\advRisk(\probmap) &\triangleq \mathbb{E}_{(x,y)\sim \mathcal{D}}\left[ \sup_{\norm{\tau}_{\mathcal{X}} \leq \alpha}\mathbb{E}_{y'\sim \probmap(x+\tau)} \left[ \mathds{1} \left( y' \neq y \right)\right]\right]\enspace.
\end{align}

The definition of adversarial risk for a probabilistic mapping can be matched with the concept of Expectation over Transformation (EoT) attacks <cit.>.
Indeed, EoT attacks aim at computing the best opponent in expectation for a given random transformation.
In the adversarial risk definition, the adversary chooses the perturbation which has the greatest probability to fool the model, which is a stronger objective than the EoT objective.
Theorem <ref> provides a bound on the gap between the adversarial risk and the regular risk:

Let $\probmap$ be the probabilistic mapping at hand.
Let us suppose that  $\probmap$ is $d_{R,\lambda}$-$(\alpha,\epsilon)$ robust for some $\lambda\geq1$ then:

\begin{equation}
|\advRisk(\probmap)-\Risk(\probmap)|\leq 1-e^{-\epsilon}\mathbb{E}_x\left[e^{-H(\probmap(x))}\right]
\end{equation}

where $H$ is the Shannon entropy $H(p)=-\sum_i p_i \log(p_i)\enspace.$

This theorem gives a control on the loss of accuracy under attack the robustness parameter $\epsilon$ and the entropy of the predictor.
It provides a trade-off between the quantity of noise added in the network and the accuracy under attack.
Intuitively, when the noise increases, for any input, the output distribution tends towards the uniform distribution, then, $\epsilon\rightarrow0$ and $H(\probmap(x))\rightarrow \log(K)$, and the risk and the adversarial risk both tends to $\frac{1}{K}$ where $K$ is the number of classes in the classification problem.
On the opposite, if no noise is injected, for any input, the output distribution is a  Dirac distribution, then, if the prediction for the adversarial example is not the same as for the regular one, $\epsilon\rightarrow\infty$ and $H(\probmap(x))\rightarrow 0$.
Hence, the noise needs to be designed both to preserve accuracy and robustness to adversarial attacks.
In the Section <ref>, we give an illustration of this bound when $\probmap$ is a neural network with noise injection at input level as presented in Theorem <ref>.

§ EXPERIMENTS

To illustrate our theoretical findings, we train randomized neural networks with a simple method which consists in injecting a noise drawn from an Exponential family distribution in the image during training and inference.
This section aims to answer Q2 stated in the introduction, by tackling the following sub-questions:

Q2.1: How does the randomization impact the accuracy of the network? And, how does the theoretical trade-off between accuracy and robustness apply in practice?

Q2.2: What is the accuracy under attack of randomized neural networks against powerful iterative attacks? And how does randomized neural networks compare to state-of-the-art defenses given the intensity of the injected noise?

Experimental setup

We present our results and analysis on CIFAR-10 <cit.>.
We used a Wide ResNet architecture <cit.> which is a variant of the ResNet model proposed by <cit.>.
We use 28 layers with a widen factor of 10.
We train all networks for 200 epochs, a batch size of 400, dropout 0.3 and Leaky Relu activation with a slope on $\mathbb{R}^-$ of 0.1.
We minimize the Cross Entropy Loss with Momentum 0.9 and use a piecewise constant learning rate of 0.1, 0.02, 0.004 and 0.00008 after respectively 7500, 15000 and 20000 steps.
The networks achieve for CIFAR10 and 100 a TOP-1 accuracy of 95.8% and 79.1% respectively on test images.

To transform these classical networks to probabilistic mappings, we inject noise drawn from Laplace and Gaussian distributions, each with various standard deviations.
While the noise could theoretically be injected anywhere in the network, we inject the noise on the image for simplicity.
More experiments with noise injected in the first layer of the network are presented in the supplementary material.
To evaluate our models under attack, we use three powerful iterative attacks with different norms: ElasticNet attack (EAD) <cit.> with $\ell_1$ distortion, Carlini&Wagner attack (C&W) <cit.> with $\ell_2$ distortion and Projected Gradient Descent attack (PGD) <cit.> with $\ell_\infty$ distortion.
All standard deviations and attack intensities are in between $-1$ and $1$.
Precise descriptions of our numerical experiments and of the attacks used for evaluation are deferred to the supplementary material.

Attacks against randomized defenses:
It has been pointed out by <cit.> that in a white box setting, an attacker with a complete knowledge of the system will know the distribution of the noise injected in the network.
As such, to create a stronger adversarial example, the attacker can take the expectation of the loss or the logits of the randomized network during the computation of the attack.
This technique is called Expectation Over Transformation ($\EoT$) and we use a Monte Carlo method with $80$ simulations to approximate the best perturbation for a randomized network.

Impact of the standard deviation of the injected noise on accuracy in a randomized model on CIFAR-10 dataset with a Wide ResNet architecture.

Illustration of the guaranteed accuracy of different randomized models with Gaussian noises given the norm of the adversarial perturbation.

Illustration of the guaranteed accuracy of different randomized models with Laplace noises given the norm of the adversarial perturbation.

Trade-off between accuracy and intensity of noise (Q2.1):

When injecting noise as a defense mechanism, regardless of the distribution it is drawn from, we observe (as in Figure <ref>) that the accuracy decreases when the noise intensity grows.
In that sense, noise needs to be calibrated to preserve both accuracy and robustness against adversarial attacks, , it needs to be large enough to preserve robustness and small enough to preserve accuracy.
Figure <ref> shows the loss of accuracy on CIFAR10 from $0.95$ to $0.82$ (respectively $0.95$ to $0.84$) with noise drawn from a Gaussian distribution (respectively Laplace) with a standard deviation from $0.01$ to $0.5$.
Figure <ref> and <ref> illustrate the theoretical lower bound on accuracy under attack of Theorem <ref> for different distributions and standard deviations.
The term in entropy of Theorem <ref> has been estimated using a Monte Carlo method with $10^4$ simulations.
The trade-off between accuracy and robustness from Theorem <ref> thus appears the noise intensity.
With small noises, the accuracy is high, but the guaranteed accuracy drops fast the magnitude of the adversarial perturbation.
Conversely, with bigger noises, the accuracy is lower but decreases slowly the magnitude of the adversarial perturbation.
These Figures also show that Theorem <ref> gives strong accuracy guarantees against small adversarial perturbations.
Next paragraph shows that in practice, randomized networks achieve much higher accuracy under attack than the theoretical bound, and keep this accuracy against much larger perturbations.

Performance of randomized networks under attacks and comparison to state of the art (Q2.2):

While Figure <ref> and <ref> illustrated a theoretical robustness against growing adversarial perturbations, Table <ref> illustrates this trade-off experimentally.
It compares the accuracy obtained under attack by a deterministic network with the one obtained by randomized networks with Gaussian and Laplace noises both with low ($0.01$) and high ($0.5$) standard deviations.
Randomized networks with a small noise lead to no loss in accuracy with a small robustness while high noise leads to a higher robustness at the expense of loss of accuracy ($\sim11$ points).

Distribution     Sd     Natural     $\ell_1$ EAD 60     $\ell_2$ C&W 60     $\ell_\infty$ PGD 20

1c–     –     0.958     0.035     0.034     0.384

2[0]*Normal     0.01     0.954     0.193     0.294     0.408

0.50     0.824     0.448     0.523     0.587

2[0]*Laplace     0.01     0.955     0.208     0.313     0.389

0.50     0.846     0.464     0.494     0.589

Accuracy under attack on the CIFAR-10 dataset with a randomized Wide ResNet architecture. We compare the accuracy on natural images and under attack with different noise over 3 iterative attacks (the number of steps is next to the name) made with 80 Monte Carlo simulations to compute EoT attacks. The first line is the baseline, no noise has been injected.

2*Attack     2*Steps         2[0]*Madry et al.            2cNormal          2cLaplace

6-7 9-10
0.32     0.5          0.32     0.5

–                        –         0.873         0.876     0.824         0.891     0.846

$\ell_\infty$ – PGD      20         0.456         0.566     0.587         0.576     0.589

$\ell_2$ – C&W          30         0.468         0.512     0.489         0.502     0.479

Accuracy under attack of randomized neural network with different distributions and standard deviations versus adversarial training by <cit.>. The PGD attack has been made with 20 step, an epsilon of 0.06 and a step size of 0.006 (input space between $-1$ and $+1$). The Carlini&Wagner attack uses 30 steps, 9 binary search steps and a 0.01 learning rate. The first line refers to the baseline without attack.

Finally, Table <ref> compares the accuracy and the accuracy under attack of randomized networks with Gaussian and Laplace distributions for different standard deviations against adversarial training from <cit.>.
We observe that the accuracy on natural images of both noise injection methods are similar to the one from <cit.>.
Moreover, both methods are more robust than adversarial training to PGD and C&W attacks.
As with all the experiments, to construct an EoT attack,  we use 80 Monte Carlo simulations at every step of PGD and C&W attacks.
These experiments show that randomized defenses can be competitive given the intensity of noise injected in the network.
Note that these experiments have been led with $\EoT$ of size 80.
For much bigger sizes of $\EoT$ these results would be mitigated.
Nevertheless, the accuracy would never drop under the bounds illustrated in the Figures <ref> and <ref>, since Theorem <ref> gives a bound that on the worst case attack strategy (including $\EoT$).

§ CONCLUDING REMARKS

This chapter brings new contributions to the field of provable defenses to adversarial attacks.
Principled answers have been provided to key questions on the interest of randomization techniques, and on their loss of accuracy under attack.
The obtained bounds have been illustrated in practice by conducting thorough experiments on baseline datasets such as CIFAR.
We show in particular that a simple method based on injecting noise drawn from the Exponential family is competitive compared to baseline approaches while leading to provable guarantees.
Future work will focus on investigating other noise distributions belonging or not to the Exponential family, combining randomization with more sophisticated defenses and on devising new tight bounds on the adversarial generalization gap.

CHAPTER: ADVOCATING FOR MULTIPLE DEFENSE STRATEGIES AGAINST ADVERSARIAL EXAMPLES

This Appendix concerns a collaboration with Rafael Pinot, Laurent Meunier and Benjamin Negrevergne.
This work has been published in the European Conference on Machine Learning Workshop for CyberSecurity.
It conducts a geometrical analysis of defense mechanisms designed to protect neural networks against.
This work shows that neural networks designed to be robust against one type of adversarial example offers poor robustness against other types of attacks.

§ INTRODUCTION

We have seen that deep neural networks are vulnerable to adversarial examples.
Because it is difficult to characterize the space of visually imperceptible variations of a natural image, existing adversarial attacks use surrogates that can differ from one attack to another.
For example, <cit.> use the $\linf$ norm to measure the distance between the original image and the adversarial image whereas <cit.> use the $\ltwo$ norm.
When the input dimension is low, the choice of the norm is of little importance because the $\linf$ and $\ltwo$ balls overlap by a large margin, and the adversarial examples lie in the same space.
An important insight in this chapter is to observe that the overlap between the two balls diminishes exponentially quickly as the dimensionality of the input space increases.
For typical image datasets with large dimensionality, the two balls are mostly disjoint.
As a consequence, the $\linf$ and the $\ltwo$ adversarial examples lie in different areas of the space, and it explains why $\linf$ defense mechanisms perform poorly against $\ltwo$ attacks and vice versa.

Building on this insight, we advocate for designing models that incorporate defense mechanisms against both $\linf$ and $\ltwo$ attacks and review several ways of mixing existing defense mechanisms.
In particular, we evaluate the performance of Mixed Adversarial Training (MAT) <cit.> which consists of  augmenting training batches using both $\linf$ and $\ltwo$ adversarial examples, and Randomized Adversarial Training (RAT) <cit.>, a solution to benefit from the advantages of both $\linf$ adversarial training, and $\ltwo$ randomized defense.

§ NO FREE LUNCH FOR ADVERSARIAL DEFENSES

In this Section, we show both theoretically and empirically that defenses mechanisms intending to defend against $\linf$ attacks cannot provide suitable defense against $\ltwo$ attacks.
Our reasoning is perfectly general; hence we can similarly demonstrate the reciprocal statement, but we focus on this side for simplicity.

2D representation of the $\linf$ and $\ltwo$ balls of respective radius $\epsilon$ and $\epsilon'$

A classifier trained with $\linf$ adversarial perturbations  (materialized by the red line) remains vulnerable to $\ltwo$ attacks.

A classifier trained with $\ltwo$ adversarial perturbations (materialized by the blue line) remains vulnerable to $\linf$ attacks.

2-dimensional representation of $\linf$ and $\ltwo$ balls

§.§ Theoretical analysis

Let us consider a classifier $f_{\infty}$ that is provably robust against adversarial examples with maximum $\linf$ norm of value $\epsilon_\infty$.
It guarantees that for any input-output pair $(x,y) \sim \Dset$ and for any perturbation $\tau$ such that $\norm{\tau}_\infty \leq \epsilon_\infty$, $f_{\infty}$ is not misled by the perturbation, , $f_{\infty}(x + \tau) = f_{\infty}(x)$.
We now focus our study on the performance of this classifier against adversarial examples bounded with a $\ltwo$ norm of value $\epsilon_2$.
Using Figure <ref>, we observe that any $\ltwo$ adversarial example that is also in the $\linf$ ball, will not fool $f_{\infty}$.
Conversely, if it is outside the ball, we have no guarantee.

To characterize the probability that such an  $\ltwo$ perturbation fools an $\linf$ defense mechanism in the general case (i.e., any dimension $d$), we measure the ratio between the volume of the intersection of the $\linf$ ball of radius $\epsilon_\infty$ and the $\ltwo$ ball of radius $\epsilon_2$. As Theorem <ref> shows, this ratio depends on the dimensionality $d$ of the input vector $x$, and  rapidly converges to zero when $d$ increases.
Therefore a defense mechanism that protects against all $\linf$ bounded adversarial examples is unlikely to be efficient against $\ltwo$ attacks.

\begin{equation}
B_{2,d}(\epsilon) \triangleq \left \{\tau \in \Rbb^d \ |\  \norm{\tau}_2 \leq \epsilon \right \}
\end{equation}

\begin{equation}
B_{\infty,d}(\epsilon') \triangleq \left \{\tau \in \Rbb^d \ |\  \norm{\tau}_\infty \leq \epsilon' \right\}.
\end{equation}

If for all $d$, we select $\epsilon$ and $\epsilon$' such that $\Vol\left(B_{2,d}(\epsilon)\right) = \Vol\left(B_{\infty,d}(\epsilon')\right)$, then

\begin{equation}
\frac{\Vol\left(B_{2,d}(\epsilon)\bigcap B_{\infty,d}(\epsilon')\right)}{\Vol\left(B_{\infty,d}(\epsilon')\right)} \rightarrow 0 \text{ when } d\rightarrow \infty.
\end{equation}

Without loss of generality, let us fix $\epsilon = 1$. One can show that for all $d$,

\begin{equation}
\Vol\left( B_{2,d}\left(\frac{2}{\sqrt{\pi}}\Gamma\left(\frac{d}{2}+1\right)^{1/d}\right)\right) = \Vol\left(B_{\infty,d}\left(1\right)\right)
\end{equation}

where $\Gamma$ is the gamma function. Let us denote

\begin{equation}
\end{equation}

If we denote $\Uset$, the uniform distribution on $B_{\infty,d}(1)$, we get:

\begin{align}
& \frac{\Vol(B_{2,d}(r_2(d)) \bigcap B_{\infty,d}(1))}{\Vol(B_{\infty,d}(1))} \\
&= \Pbb_{\xvec \sim \Uset} \left[ x \in B_{2,d}(r_2(d)) \right] = \Pbb_{\xvec \sim \Uset} \left[ \sum_{i=1}^d |x_i|^2 \leq r_2(d)^2 \right] \\
&= \Pbb_{\xvec \sim \Uset} \left[ \sum_{i=1}^d |\xvec_i|^2  - \Ebb_{\xvec \sim \Uset}\left[\sum_{i=1}^d |\xvec_i|^2 \right] \leq r_2(d)^2 - \Ebb_{\xvec \sim \Uset}\left[\sum_{i=1}^d |\xvec_i|^2 \right] \right]
% &\leq \exp{- d^{-1} \left( r_2^2(d) - d \Ebb |x_1|^2 \right)^2} \label{equation:ap4-hoeffding1} \\
% &\leq \exp{-\left( \frac{2}{\pi e}-\frac23\right)^2d+o(d)} \label{equation:ap4-hoeffding2}.
\end{align}

Note that when $d$ is sufficiently large we get

\begin{equation}
r_2(d)^2 - \Ebb_{\xvec \sim \Uset}\left[\sum_{i=1}^d |\xvec_i|^2 \right] = r_2(d)^2 - \frac{d}{3} < 0
\end{equation}

Then, with Hoeffding inequality, we finally obtain:

\begin{equation}
\frac{\Vol(B_{2,d}(r_2(d)) \bigcap B_{\infty,d}(1))}{\Vol(B_{\infty,d}(1))} \leq \exp\left(- \frac{\left(r_2(d)^2 - \frac{d}{3}\right)^2}{d} \right)
\end{equation}

Then, thanks to Stirling's formula

\begin{equation}
r_2(d) \underset{d \rightarrow \infty}{\sim} \sqrt{\frac{2}{\pi e}} d^{1/2}.
\end{equation}

Then the ratio between the volume of the intersection of the ball and the volume of the ball converges towards $0$ when $d$ goes to $\infty$.

Theorem <ref> states that, when $d$ is large enough, $\ltwo$ bounded perturbations have a null probability of being also in the $\linf$ ball of the same volume.
As a consequence, for any value of $d$ that is large enough, a defense mechanism that offers full protection against $\linf$ adversarial examples is not guaranteed to offer any protection against $\ltwo$ attacks [Theorem <ref> can easily be extended to any two balls with different norms. For clarity, we restrict to the case of $\linf$ and $\ltwo$ norms.].

Dataset      ....     Dim. $\mathbf{(d)}$     ....     Vol. of the intersection

–         2            $e^{-0.183}$   ($\approx$ 0.83)

MNIST         784             $e^{-7.344}$

CIFAR         3072             $e^{-29.76}$

ImageNet         150528            $e^{-1478.71}$

Bounds of Theorem <ref> on the volume of the intersection of  $\ltwo$ and $\linf$ balls at equal volume for typical image classification datasets. When $d=2$, the bound is $10^{-0.183}\approx 0.83$.

Note that this result defeats the 2-dimensional intuition: if we consider a 2 dimensional problem setting, the $\linf$ and the $\ltwo$ balls have an important overlap (as illustrated in Figure <ref>) and the probability of sampling at the intersection of the two balls is bounded by approximately 83%.
However, as we increase the dimensionality $d$, this probability quickly becomes negligible, even for very simple image datasets such as MNIST.
An instantiation of the bound for classical image datasets is presented in Table <ref>.
The probability of sampling at the intersection of the $\linf$ and $\ltwo$ balls is close to zero for any realistic image setting.
In large dimensions, the volume of the corner of the $\linf$ ball is much bigger than it appears in Figure <ref>.

§.§ No Free Lunch in Practice

Our theoretical analysis shows that if adversarial examples were uniformly distributed in a high-dimensional space, then any mechanism that perfectly defends against $\linf$ adversarial examples has a null probability of protecting against $\ltwo$-bounded adversarial attacks.
Although existing defense mechanisms do not necessarily assume such a distribution of adversarial examples, we demonstrate that whatever distribution they use, it offers no favorable bias with respect to the result of Theorem <ref>.
As we discussed in Chapter <ref>, there are two distinct attack settings: loss maximization (PGD) and perturbation minimization (C&W).
Our analysis is mainly focusing on loss maximization attacks.
However, these attacks have a very strict geometry[Due to the projection operator, all PGD attacks saturate the constraint, which makes them all lies in a very small part of the ball.].
This is why, to present a deeper analysis of the behavior of adversarial attacks and defenses, we also present a set of experiments that use perturbation minimization attacks.

2cAttack PGD-$\ltwo$         2cAttack PGD-$\linf$

3-4 6-7
Unprotected     AT-$\linf$         Unprotected     AT-$\ltwo$

Average $\ltwo$ norm           0.830     0.830           1.400     1.640

Average $\linf$ norm           0.075     0.200           0.031     0.031

Average norms of PGD-$\ltwo$ and PGD-$\linf$ adversarial examples with and without $\linf$ adversarial training on CIFAR-10 ($d=3072$).

Adversarial training vs. loss maximization attacks

To demonstrate that $\linf$ adversarial training is not robust against PGD-$\ltwo$ attacks we measure the evolution of $\ltwo$ norm of adversarial examples generated with PGD-$\linf$ between an unprotected model and a model trained with AT-$\linf$, , AT where adversarial examples are generated with PGD-$\linf$ [To do so, we use the same experimental setting as in Section <ref> with $\epsilon_\infty$ and $\epsilon_2$ such that the volumes of the two balls are equal.].
Results are presented in  Table <ref>.

The analysis is unambiguous: the average $\linf$ norm of a bounded $\ltwo$ perturbation more than double between an unprotected model and a model trained with AT PGD-$\linf$.
This phenomenon perfectly reflects the illustration of Figure <ref>.
The attack will generate an adversarial example on the corner of the $\linf$ ball thus increasing the $\linf$ norm while maintaining the same $\ltwo$ norm.
We can observe the same phenomenon with AT-$\ltwo$ against PGD-$\linf$ attack (see Figure <ref> and Table <ref>).
PGD-$\linf$ attack increases the $\ltwo$ norm while maintaining the same $\linf$ perturbation thus generating the perturbation in the upper area.

As a consequence, we cannot expect adversarial training $\linf$ to offer any guaranteed protection against $\ltwo$ adversarial examples .

Adversarial training vs. perturbation minimization attacks.
To better capture the behavior of $\ltwo$ adversarial examples, we now study the performances of an $\ltwo$ perturbation minimization attack (C&W) with and without AT-$\linf$.
It allows us to understand in which area C&W discovers adversarial examples and the impact of AT-$\linf$.
In high dimensions, the red corners (see Figure <ref>) are very far away from the $\ltwo$ ball.
Therefore, we hypothesize that a large proportion of the $\ltwo$ adversarial examples will remain unprotected.
To validate this assumption, we measure the proportion of adversarial examples inside of the $\ltwo$ ball before and after $\linf$ adversarial training.
The results are presented in Figure <ref> (left: without adversarial training, right: with adversarial training).

Comparison of the number of adversarial examples found by C&W, inside the $\linf$ ball (lower, blue area), outside the $\linf$ ball but inside the $\ltwo$ ball (middle, red area) and outside the $\ltwo$ ball (upper gray area). $\epsilon$ is set to $0.3$ and $\epsilon'$ varies along the x-axis. Left: without adversarial training, right: with adversarial training. Most adversarial examples have shifted from the $\linf$ ball to the cap of the $\ltwo$ ball, but remain at the same $\ltwo$ distance from the original example.

On both charts, the blue area represents the proportion of adversarial examples that are inside the $\linf$ ball.
The red area represents the adversarial examples that are outside the $\linf$ ball but still inside the $\ltwo$ ball (valid $\ltwo$ adversarial examples).
Finally, the brown-beige area represents the adversarial examples that are beyond the $\ltwo$ bound.
The radius $\epsilon'$ of the $\ltwo$ ball varies along the x-axis from $\epsilon'$ to $\epsilon' \sqrt{d}$.
On the left chart (without adversarial training) most $\ltwo$ adversarial examples generated by C&W are inside both balls.
On the right chart most of the adversarial examples have been shifted out the $\linf$ ball.
This is the expected consequence of $\linf$ adversarial training.
However, these adversarial examples remain in the $\ltwo$ ball, , they are in the cap of the $\ltwo$ ball.
These examples are equally good from the $\ltwo$ perspective.
This means that even after adversarial training, it is still easy to find good $\ltwo$ adversarial examples, making the $\ltwo$ robustness of AT-$\linf$ almost null.

§ REVIEWING DEFENSES AGAINST MULTIPLE ATTACKS

2*Baseline         2cAT         2cMAT         2cNI         2cRAT-$\linf$         2cRAT-$\ltwo$

5-6 8-9 11-12 14-15 17-18
$\linf$     $\ltwo$           Max     Rand           $\mathcal{N}$     $\mathcal{U}$           $\mathcal{N}$     $\mathcal{U}$           $\mathcal{N}$     $\mathcal{U}$

Natural               0.94           0.85     0.85           0.80     0.80           0.79     0.87           0.74     0.80           0.79     0.87

PGD-$\linf$           0.00           0.43     0.37           0.37     0.40           0.23     0.22           0.35     0.40           0.23     0.22

PGD-$\ltwo$           0.00           0.37     0.52           0.50     0.55           0.34     0.36           0.43     0.39           0.34     0.37

Comprehensive list of results consisting of the accuracy of several defense mechanisms against $\ltwo$ and $\linf$ attacks.

Adversarial attacks have been an active topic in the machine learning community since their discovery <cit.>.
Many attacks have been developed.
Most of them solve a loss maximization problem with either $\linf$ <cit.>, $\ltwo$ <cit.>, $\lone$ <cit.> or $\lzero$ <cit.> surrogate norms.
As we showed, these norms are really different in high dimension.
Hence, defending against one norm-based attack is not sufficient to protect against another one.
In order to solve this problem, we review several strategies to build defenses against multiple adversarial attacks.
These strategies are based on the idea that both types of defense must be used simultaneously in order for the classifier to be protected against multiple attacks.

§.§ Experimental Setting

To compare the robustness provided by the different defense mechanisms, we use strong adversarial attacks and a conservative setting: the attacker has a total knowledge of the parameters of the model (white-box setting) and we only consider untargeted attacks  (a misclassification from one target to any other will be considered as adversarial).
To evaluate defenses based on Noise Injection, we use Expectation Over Transformation (EOT), the rigorous experimental protocol  proposed by <cit.> and later used by <cit.> to identify flawed defense mechanisms.

To attack the models, we use state-of-the-art algorithms PGD.
We run PGD with 20 iterations to generate adversarial examples and with 10 iterations when it is used for adversarial training.
The maximum $\linf$ bound is fixed to $0.031$ and the maximum $\ltwo$ bound is fixed to $0.83$.
We chose these values so that the $\linf$ and the $\ltwo$ balls have similar volumes.
Note that $0.83$ is slightly above the values typically used in previous publications in the area, meaning the attacks are stronger, and thus  more difficult to defend against.

All experiments are conducted on CIFAR-10 with the Wide-Resnet 28-10 architecture.
We use the training procedure and the hyper-parameters described in the original paper by <cit.>.
Training time varies from 1 day (AT) to 2 days (MAT) on 4 GPUs-V100 servers.

§.§ MAT – Mixed Adversarial Training

Earlier results have shown that AT-$\lp$ improves the robustness against corresponding $\lp$-bounded adversarial examples, and the experiments we present in this section corroborate this observation (See Table <ref>, column: AT).
Building on this, it is natural to examine the efficiency of Mixed Adversarial Training (MAT) against mixed $\linf$ and $\ltwo$ attacks.
MAT is a variation of AT that uses both $\linf$-bounded adversarial examples and $\ltwo$-bounded adversarial examples as training examples.
As discussed by <cit.>, there are several possible strategies to mix the adversarial training examples.
The first strategy (MAT-Rand) consists in randomly selecting one adversarial example among the two most damaging $\linf$ and $\ltwo$, and to use it as a training example:

\begin{equation} \label{equation:ap4-mat_rand}
\min_{\Omega} \Ebb_{(\xvec, y) \sim \Dset} \left[\Ebb_{p \sim \Uset({\{2, \infty\})}} \max_{\norm{\adv}_p \leq \epsilon} L \left( N_{\Omega}(\xvec+\adv), y \right) \right].
\end{equation}

An alternative strategy is to systematically train the model with the most damaging adversarial example ($\linf$ or $\ltwo$):

\begin{equation} \label{equation:ap4-mat_max}
\min_{\Omega} \Ebb_{(\xvec, y) \sim \Dset} \left[ \max_{p \in \{2, \infty\}} \max_{\norm{\adv}_p \leq \epsilon} L \left( N_{\Omega}(\xvec+\adv), y \right) \right].
\end{equation}

The accuracy of MAT-Rand and MAT-Max are reported in <Ref> (Column: MAT).
As expected, we observe that MAT-Rand and MAT-Max offer better robustness both against PGD-$\ltwo$ and PGD-$\linf$ adversarial examples than the original AT does.
More  generally, we can see that AT is a good strategy against loss maximization attacks, and thus it is not surprising that MAT is a good strategy against mixed loss maximization attacks.
However efficient in practice, MAT (for the same reasons as AT) lacks theoretical arguments.
In order to get the best of both worlds, <cit.> proposed to mix adversarial training with randomization.

§.§ RAT – Randomized Adversarial Training

We now examine the performance of Randomized Adversarial Training (RAT) first introduced by <cit.>.
This technique mixes Adversarial Training with Noise Injection.
The corresponding loss function is defined as follows:

\begin{equation}
\min_{\Omega} \Ebb_{(\xvec, y) \sim \Dset} \left[ \max_{\norm{\tau}_p \leq \epsilon} L\left( \tilde{N}_{\Omega}(\xvec+\tau), y)  \right) \right].
\end{equation}

where $\tilde{N}_\Omega$ is a randomized neural network with noise injection as described in Appendix <ref>, and $\norm{\ \cdot\ }_p$ define which kind of AT is used.
For each setting, we consider two noise distributions, Gaussian and Uniform as we did with NI.
We also consider two different Adversarial training AT-$\linf$ as well as AT-$\ltwo$.

The results of RAT are reported in Table <ref> (Columns: RAT-$\linf$ and RAT-$\ltwo$).
We can observe that RAT-$\linf$ offers the best extra robustness with both noises, which is consistent with previous experiments, since AT is generally more effective against $\linf$ attacks whereas NI is more effective against $\ltwo$-attacks.
Overall, RAT-$\linf$ and a noise from uniform distribution offers the best performances but is still weaker than MAT-Rand.
These results are also consistent with the literature, since adversarial training (and its variants) is the best defense against adversarial examples so far.

§ CONCLUDING REMARKS

In this chapter, we tackled the problem of protecting neural networks against multiple attacks crafted from different norms.
We demonstrated and gave a geometrical interpretation to explain why most defense mechanisms can only protect against one type of attack.
Then we reviewed existing strategies that mix defense mechanisms in order to build models that are robust against multiple adversarial attacks.
We conduct a rigorous and full comparison of Randomized Adversarial Training and Mixed Adversarial Training as defenses against multiple attacks.

We could argue that both techniques offer benefits and limitations.
We have observed that MAT offers the best empirical robustness against multiples adversarial attacks but this technique is computationally expensive which hinders its use in large-scale applications.
Randomized techniques have the important advantage of providing theoretical guarantees of robustness and being computationally cheaper.
However, the certificate provided by such defenses is still too small for strong attacks.
Furthermore, certain Randomized defenses also suffer from the curse of dimensionality as recently shown by <cit.>.

Although, randomized defenses based on noise injection seem limited in terms of accuracy under attack and scalability, they could be improved either by Learning the best distribution to use or by leveraging different types of randomization such as discrete randomization first proposed by <cit.>.
We believe that these certified defenses are the best solution to ensure the robustness of classifiers deployed into real-world applications.

Missing 'biblatex' package
The bibliography requires the 'biblatex' package.

noteSoftware available from tensorflow.org
titleTensorFlow: Large-Scale Machine Learning on Heterogeneous Systems

journaltitleIEEE/ACM Transactions on audio, speech, and language processing
titleConvolutional neural networks for speech recognition

Princeton University Press

titleOptimization algorithms on matrix manifolds

journaltitlearXiv preprint arXiv:1609.08675
titleYouTube-8M: A Large-Scale Video Classification Benchmark

booktitleProceedings of the 36th International Conference on Machine Learning (ICML)
titleSorting out Lipschitz Function Approximation

Cambridge University Press

titleNeural Network Learning: Theoretical Foundations

booktitleProceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)
titleNetVLAD: CNN architecture for weakly supervised place recognition

booktitleInternational Conference on Learning Representations (ICLR)
titleWasserstein Generative Adversarial Networks

booktitleAdvances in Neural Information Processing Systems (NeurIPS)
titleImplicit regularization in deep matrix factorization

booktitleProceedings of the 35th International Conference on Machine Learning (ICML)
titleObfuscated Gradients Give a False Sense of Security: Circumventing Defenses to Adversarial Examples

journaltitlearXiv preprint arXiv:1707.07397
titleSynthesizing Robust Adversarial Examples

journaltitleProbability Theory and Related Fields
titleOn bilinear forms in Gaussian random variables and Toeplitz matrices

booktitleAdvances in Neural Information Processing Systems (NeurIPS)
titleDo Deep Nets Really Need to be Deep?

booktitleInternational Conference on Learning Representations (ICLR)
titleNeural machine translation by jointly learning to align and translate

booktitleAdvances in Neural Information Processing Systems (NeurIPS)
titleSpectrally-normalized margin bounds for neural networks

MIT Press

journaltitleNeural computation
titleAlmost linear VC-dimension bounds for piecewise polynomial networks

World Scientific

journaltitleRandom Matrices: Theory and Applications
titleAsymptotics of determinants of block Toeplitz matrices

journaltitleQuantum Info. Comput.
titleAn Intuitive Proof of the Data Processing Inequality

journaltitleJournal of Computer and System Sciences
titleOn the difficulty of approximately maximizing agreements

Princeton University Press

titleRobust optimization

journaltitleIEEE Transactions on Neural Networks
titleLearning Long-term Dependencies with Gradient Descent is Difficult

booktitleInternational Conference on Learning Representations (ICLR)
titleDeep Layers as Stochastic Solvers

booktitleJoint European conference on machine learning and knowledge discovery in databases
titleEvasion attacks against machine learning at test time

journaltitleSIAM Journal on Numerical Analysis
titleAn iterative algorithm for computing the best estimate of an orthogonal matrix

Springer Science & Business Media

titleIntroduction to large truncated Toeplitz matrices

booktitleAdvances in Neural Information Processing Systems (NeurIPS)
titleLanguage Models are Few-Shot Learners

booktitleProceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining
titleModel Compression

journaltitlearXiv preprint arXiv:1902.06705
titleOn Evaluating Adversarial Robustness

booktitleIEEE Symposium on Security and Privacy
titleTowards evaluating the robustness of neural networks

journaltitleIEEE Transactions on Signal Processing
titleNoise-enhanced performance for an optimal Bayesian estimator

booktitleProceedings of the 32nd AAAI Conference on Artificial Intelligence
titleEAD: Elastic-Net Attacks to Deep Neural Networks via Adversarial Examples

booktitleProceedings of the 32nd International Conference on Machine Learning (ICML)
titleCompressing Neural Networks with the Hashing Trick

booktitleIEEE International Conference on Computer Vision (ICCV)
titleAn Exploration of Parameter Redundancy in Deep Networks with Circulant Projections

booktitleProceedings of the 36th International Conference on Machine Learning (ICML)
titleUnifying orthogonal monte carlo methods

booktitleProceedings of the 34th International Conference on Machine Learning (ICML)
titleParseval Networks: Improving Robustness to Adversarial Examples

booktitleProceedings of the 36th International Conference on Machine Learning (ICML)
titleCertified Adversarial Robustness via Randomized Smoothing

titleMemory Bounded Deep Convolutional Networks
volumearXiv preprint arXiv:1412.1442

journaltitleMathematics of computation
titleAn algorithm for the machine calculation of complex Fourier series

journaltitlearXiv preprint arXiv:1904.06253
titleThe Coupling Effect of Lipschitz Regularization in Deep Neural Networks

booktitleAdvances in Neural Information Processing Systems (NeurIPS)
titleBinaryConnect: Training Deep Neural Networks with Binary Weights During Propagations

John Wiley & Sons

titleElements of information theory

journaltitleMathematics of control, signals and systems
titleApproximation by Superpositions of a Sigmoidal Function

booktitleProceedings of the 35th International Conference on Machine Learning (ICML)
titleCompressing Neural Networks using the Variational Information Bottleneck

booktitleProceedings of the 36th International Conference on Machine Learning (ICML)
titleLearning Fast Algorithms for Linear Transforms Using Butterfly Factorizations

booktitleInternational Conference on Learning Representations (ICLR)
titleKaleidoscope: An Efficient, Learnable Representation For All Structured Linear Maps

seriesMonographs and textbooks in pure and applied mathematics
titleCirculant Matrices

journaltitleSIAM Undergraduate Research Online
titleFinding the maximum modulus of a polynomial on the polydisk using a generalization of steckins lemma

booktitleProceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)
titleImagenet: A Large-Scale Hierarchical Image Database

booktitleProceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NAACL)
titleBERT: Pre-training of Deep Bidirectional Transformers for Language Understanding

booktitleInternational Conference on Learning Representations (ICLR)
titleStochastic Activation Pruning for Robust Adversarial Defense

booktitleAdvances in Neural Information Processing Systems (NeurIPS)
titleAdversarial Risk and Robustness: General Definitions and Implications for the Uniform Distribution

journaltitlearXiv preprint arXiv:1603.07285
titleA Guide to Convolution Arithmetic for Deep Learning

journaltitleFoundations and Trends® in Theoretical Computer Science
titleThe algorithmic foundations of differential privacy

booktitleProceedings of the 37th International Conference on Machine Learning (ICML)
titleRigging the Lottery: Making All Tickets Winners

journaltitleTransportation Research Part A: Policy and Practice
titlePreparing a nation for autonomous vehicles: opportunities, barriers and policy recommendations

booktitleInternational Conference on Learning Representations (ICLR)
titleGeneralizable Adversarial Training via Spectral Normalization

journaltitleComputer Methods and Programs in Biomedicine
titleDeep learning for healthcare applications based on physiological signals: A review

booktitleAdvances in Neural Information Processing Systems (NeurIPS)
titleAdversarial vulnerability for any classifier

booktitleAdvances in Neural Information Processing Systems (NeurIPS)
titleRobustness of classifiers: from adversarial to random noise

booktitleProceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)
titleEmpirical Study of the Topology and Geometry of Deep Networks

journaltitlearXiv preprint arXiv:1903.01287
titleSafety Verification and Robustness Analysis of Neural Networks via Quadratic Constraints and Semidefinite Programming

booktitleAdvances in Neural Information Processing Systems (NeurIPS)
titleEfficient and Accurate Estimation of Lipschitz Constants for Deep Neural Networks

journaltitlearXiv preprint arXiv:2101.03961
titleSwitch Transformers: Scaling to Trillion Parameter Models with Simple and Efficient Sparsity

journaltitleSIAM Journal on Computing
titleAgnostic Learning of Monomials by Halfspaces is Hard

booktitleInternational Conference on Learning Representations (ICLR)
titleThe Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks

booktitleCompetition and cooperation in neural nets
titleNeocognitron: A self-organizing neural network model for a mechanism of visual pattern recognition

journaltitlearXiv preprint arXiv:1611.03214
titleUltimate Tensorization: Compressing Convolutional and FC Layers Alike

booktitleProceedings of the 23rd International Conference on Machine Learning (ICML)
titleNightmare at Test Time: Robust Learning by Feature Deletion

booktitleProceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics
titleUnderstanding the Difficulty of Training Deep Feedforward Neural Networks

booktitleConference on Learning Theory (COLT)
titleSize-Independent Sample Complexity of Neural Networks

journaltitleJournal of Computational and Applied Mathematics
titleEigenvalue computation in the 20th century

booktitleInternational Conference on Learning Representations (ICLR)
titleExplaining and Harnessing Adversarial Examples

journaltitlearXiv preprint arXiv:1804.04368
titleRegularisation of Neural Networks by Enforcing Lipschitz Continuity
family=Roy Choudhury,

booktitle2019 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW)
titleCompression of Deep Neural Networks by Combining Pruning and Low Rank Decomposition

Now Publishers, Inc.

journaltitleFoundations and Trends® in Communications and Information Theory
titleToeplitz and Circulant Matrices: A Review

journaltitleSIAM journal on numerical analysis
titleCalculating the maximum modulus of a polynomial using Steckin's lemma

journaltitlePhysics Today
titleToeplitz Forms and Their Applications

Taylor & Francis

journaltitleThe College Mathematics Journal
titleA simple estimate of the condition number of a linear system

booktitleInternational Conference on Learning Representations (ICLR)
titleCountering Adversarial Images using Input Transformations

booktitleProceedings of the 32nd International Conference on Machine Learning (ICML)
titleDeep Learning with Limited Numerical Precision

Now Publishers, Inc.

journaltitleFoundations and Trends® in Communications and Information Theory
titleBlock Toeplitz matrices: Asymptotic results and applications

booktitleInternational Conference on Learning Representations (ICLR)
titleDeep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding

journaltitlearXiv preprint arXiv:1708.02691
titleUniversal Function Approximation by Deep Neural Nets with Bounded Width and ReLU Activations

booktitleConference on Learning Theory
titleNearly-tight VC-dimension bounds for piecewise linear neural networks

booktitleIEEE International Conference on Computer Vision (ICCV)
titleDelving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification

booktitleProceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)
titleDeep Residual Learning for Image Recognition

booktitleAdvances in Neural Information Processing Systems (NeurIPS)
titleFormal guarantees on the robustness of a classifier against adversarial manipulation

Wiley Online Library

journaltitleRandom Structures & Algorithms
titleJohnson-Lindenstrauss Lemma for Circulant Matrices

journaltitleIEEE Signal Processing Magazine
titleDeep neural networks for acoustic modeling in speech recognition: The shared views of four research groups

booktitleNeural Information Processing Systems – Deep Learning and Representation Learning Workshop
titleDistilling the Knowledge in a Neural Network

Springer Berlin Heidelberg

booktitleParallel Architectures and Languages Europe
titleLearning translation invariant recognition in a massively parallel networks

Wiley Online Library

journaltitleJournal of Mathematics and Physics
titleThe expression of a tensor or a polyadic as a sum of products

journaltitleNeural Networks
titleMultilayer feedforward networks are universal approximators

booktitleProceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)
titleSqueeze-and-excitation networks

booktitleProceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)
titleDensely Connected Convolutional Networks

booktitleProceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)
titleControllable Orthogonalization in Training DNNs

booktitleAdvances in Neural Information Processing Systems (NeurIPS)
titleGPipe: Efficient Training of giant Neural Networks using Pipeline Parallelism

journaltitleJournal of Fourier Analysis and Applications
titleFactoring Matrices into the Product of Circulant and Diagonal Matrices

booktitleJoint European Conference on Machine Learning and Knowledge Discovery in Databases
titleLimitations of the Lipschitz constant as a defense against adversarial examples

journaltitlearXiv preprint arXiv:1602.07360
titleSqueezeNet: AlexNet-level Accuracy with 50x Fewer Parameters and< 0.5 MB Model Size

booktitleProceedings of the British Machine Vision Conference
titleSpeeding up Convolutional Neural Networks with Low Rank Expansions

Englewood Cliffs, NJ: Prentice Hall

titleFundamentals of digital image processing

booktitleProceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)
titleAggregating Local Descriptors into a Compact Image Representation

booktitleProceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)
titleImproving Training of Deep Neural Networks via Singular Value Bounding

journaltitleIEEE Transactions on Pattern Analysis and Machine Intelligence
titleExploiting Feature and Class Relationships in Video Categorization with Regularized Deep Neural Networks

booktitleProceedings of the 34th International Conference on Machine Learning (ICML)
titleTunable efficient unitary neural networks (eunn) and their application to rnns

booktitleProceedings of 1993 International Conference on Neural Networks (IJCNN-93-Nagoya, Japan)
titleHierarchical Mixtures of Experts and the EM Algorithm

journaltitleDokl. Akad. Nauk SSSR
titleRegular points, spectrum and eigenfunctions of nonlinear operators

journaltitleJournal of Mathematical Analysis and Applications
titleDisplacement ranks of matrices and linear equations

journaltitlearXiv preprint arXiv:2001.08361
titleScaling Laws for Neural Language Models

booktitleProceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)
titleLarge-Scale Video Classification with Convolutional Neural Networks

booktitleWavelet Analysis and Its Applications
titleA Matrix Approach to Discrete Wavelets

booktitleHigh Dimensional Probability II
titleRademacher Processes and Bounding the Risk of Function Learning

booktitleNeural Information Processing Systems – Private Multi-Party Machine Learning Workshop
titleFederated Learning: Strategies for Improving Communication Efficiency

titleLearning Multiple Layers of Features from Tiny Images

booktitleAdvances in Neural Information Processing Systems (NeurIPS)
titleImageNet Classification with Deep Convolutional Neural Networks

journaltitlearXiv preprint arXiv:2002.03239
titleCurse of Dimensionality on Randomized Smoothing for Certifiable Robustness

journaltitlearXiv preprint arXiv:1607.02533
titleAdversarial Examples in the Physical World

booktitleAdvances in Neural Information Processing Systems (NeurIPS)
titlePAC-Bayes & margins

booktitleInternational Conference on Learning Representations (ICLR)
titleLipschitz Constant Estimation for Neural Networks via Sparse Polynomial Optimization

journaltitleProceedings of the IEEE
titleGradient-based learning applied to document recognition

booktitle2019 IEEE Symposium on Security and Privacy (SP)
titleCertified Robustness to Adversarial Examples with Differential Privacy

booktitleProceedings of the European Conference on Computer Vision (ECCV) Workshops
titleThe 2nd youtube-8m large-scale video understanding challenge

journaltitleSIAM Journal on Matrix Analysis and Applications
titleDeflation techniques for an implicitly restarted Arnoldi iteration

journaltitlearXiv preprint arXiv:1809.03113
titleSecond-Order Adversarial Attack and Certifiable Robustness

titleAcoustic Modeling for Google Home

booktitleEuropean Conference on Computer Vision
titleConstrained Optimization Based Low-Rank Approximation of Deep Neural Networks

titleOpenAI's GPT-3 Language Model: A Technical Overview

titleTemporal Modeling Approaches for Large-scale Youtube-8M Video Understanding
volumearXiv preprint arXiv:1707.04555

booktitleAdvances in Neural Information Processing Systems (NeurIPS)
titlePreventing Gradient Attenuation in Lipschitz Constrained Convolutional Networks

journaltitleMultiscale Modeling & Simulation
titleButterfly factorization

booktitleAdvances in Neural Information Processing Systems (NeurIPS)
titleRuntime Neural Pruning

booktitleProceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)
titleSparse Convolutional Neural Networks

booktitleEuropean Conference on Computer Vision
titleSSD: Single Shot MultiBox Detector

booktitleEuropean Conference on Computer Vision
titleTowards robust neural networks via random self-ensemble

journaltitlearXiv preprint arXiv:1907.11692
titleRoberta: A Robustly Optimized BERT Pretraining Approach

booktitleAdvances in Neural Information Processing Systems (NeurIPS)
titleThe Expressive Power of Neural Networks: A View from the Width

booktitleAdvances in Neural Information Processing Systems (NeurIPS)
titleA Tensorized Transformer for Language Modeling

booktitleIn ICML Workshop on Deep Learning for Audio, Speech and Language Processing
titleRectifier Non-Linearities Improve Neural Network Acoustic Models

booktitleInternational Conference on Learning Representations (ICLR)
titleTowards Deep Learning Models Resistant to Adversarial Attacks

booktitleProceedings of the 36th International Conference on Machine Learning (ICML)
titleProving the Lottery Ticket Hypothesis: Pruning is All You Need

booktitle2010 18th European Signal Processing Conference
titleRecursive interferometric representations

journaltitlearXiv preprint arXiv:1404.7195
titleFast approximation of rotations and hessians matrices

journaltitleThe bulletin of mathematical biophysics
titleA logical calculus of the ideas immanent in nervous activity

titleTernary Neural Networks with Fine-Grained Quantization
volumearXiv preprint arXiv:1705.01462

booktitleProceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security
titleMagnet: a two-pronged defense against adversarial examples

booktitleInternational Conference on Learning Representations (ICLR)
titlePointer Sentinel Mixture Models

booktitleInternational Conference on Learning Representations (ICLR)
titleMixed Precision Training

booktitleConference on Computer Vision and Pattern Recognition (CVPR) – Workshop on YouTube-8M Large-Scale Video Understanding
titleLearnable Pooling with Context Gating for Video Classification

Wiley Online Library

journaltitleZAMM-Journal of Applied Mathematics and Mechanics/Zeitschrift für Angewandte Mathematik und Mechanik
titlePraktische Verfahren der Gleichungsauflösung.

journaltitleProceedings of the IEEE
titleAdaptive stochastic resonance

booktitleInternational Conference on Learning Representations (ICLR)
titleSpectral Normalization for Generative Adversarial Networks

booktitleInternational Conference on Learning Representations (ICLR)
titleACDC: A Structured Efficient Linear Layer

booktitleProceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)
titleUniversal Adversarial Perturbations

booktitleProceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)
titleDeepfool: A Simple and Accurate Method to Fool Deep Neural Networks

journaltitlePhysica D: Nonlinear Phenomena
titleAlgorithmic Design of Diffractive Optical Systems for Information Processing

booktitleAdvances in Neural Information Processing Systems (NeurIPS)
titleQuadrature-based features for kernel approximation

booktitleProceedings of the 27th International Conference on Machine Learning (ICML)
titleRectified Linear Units Improve Restricted Boltzmann Machines

Toyota Technological Institute at Chicago

titleImplicit Regularization in Deep Learning

booktitleInternational Conference on Learning Representations (ICLR)
titleA PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks

booktitleAdvances in Neural Information Processing Systems (NeurIPS)
titleTensorizing neural networks

journaltitleSIAM Journal on Scientific Computing
titleTensor-train decomposition

journaltitleSIAM Journal on Matrix Analysis and Applications
titleInversion of displacement operators

titleStructured Matrices and Polynomials: Unified Superfast Algorithms

booktitleProceedings of the 33rd AAAI Conference on Artificial Intelligence
titleCompressing recurrent neural networks with tensor ring for action recognition

booktitleSecurity and Privacy (EuroS&P), 2016 IEEE European Symposium on
titleThe limitations of deep learning in adversarial settings

booktitle2016 IEEE Symposium on Security and Privacy (SP)
titleDistillation as a defense to adversarial perturbations against deep neural networks

titleRandom butterfly transformations with applications in computational linear algebra

journaltitleTransactions of the American Mathematical Society
titleExtreme eigenvalues of Toeplitz forms and applications to elliptic difference equations

journaltitlearXiv preprint arXiv:1712.04621
titleThe Effectiveness of Data Augmentation in Image Classification using Deep Learning

booktitleProceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)
titleFisher Kernels on Visual Vocabularies for Image Categorization

booktitleProceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NAACL)
titleDeep Contextualized Word Representations

journaltitlearXiv preprint arXiv:1802.09588
titleBounding Multivariate Trigonometric Polynomials with Applications to Filter Bank Design

booktitleProceedings of the 37th International Conference on Machine Learning (ICML)
titleRandomization Matters. How to Defend Against Strong Adversarial Attacks

titleImproving language understanding by Generative Pre-Training

journaltitleOpenAI Blog
titleLanguage Models are Unsupervised Multitask Learners

journaltitleJournal of Machine Learning Research
titleExploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer

journaltitlearXiv preprint arXiv:1811.09310
titleParametric Noise Injection: Trainable Randomness to Improve Deep Neural Network Robustness against Adversarial Attack

booktitleEuropean Conference on Computer Vision
titleXNOR-Net: ImageNet Classification Using Binary Convolutional Neural Networks

booktitleProceedings of the 33rd AAAI Conference on Artificial Intelligence
titleRegularized Evolution for Image Classifier Architecture Search

booktitleProceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)
titleYou Only Look Once: Unified, Real-Time Object Detection

booktitleProceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)
titleYOLO9000: Better, Faster, Stronger

Hungarian Academy of Sciences Budapest Hungary

titleOn measures of entropy and information

booktitleProceedings of the 37th International Conference on Machine Learning (ICML)
titleOverfitting in adversarially robust deep learning

American Psychological Association

journaltitlePsychological review
titleThe perceptron: a probabilistic model for information storage and organization in the brain.

booktitleInternational Conference on Learning Representations (ICLR)
titleA Constructive Prediction of the Generalization Error Across Scales

journaltitleMicrosoft Blog
titleTuring-NLG: A 17-billion-parameter Language Model

Nature Publishing Group

titleLearning representations by back-propagating errors

journaltitleInternational Journal of Computer Vision (IJCV)
titleImageNet Large Scale Visual Recognition Challenge

booktitleProceedings of the 36th International Conference on Machine Learning (ICML)
titlePlug-and-Play Methods Provably Converge with Properly Trained Denoisers

booktitleInternational Conference on Intelligent Robots and Systems (IROS)
titleJointly Learnable Behavior and Trajectory Planning for Self-Driving Vehicles

booktitle2013 IEEE International Conference on Acoustics, Speech and Signal Processing
titleLow-Rank Matrix Factorization for Deep Neural Network Training with High-Dimensional Output Targets

booktitleSixteenth Annual Conference of the International Speech Communication Association
titleConvolutional neural networks for small-footprint keyword spotting

booktitleAdvances in Neural Information Processing Systems (NeurIPS)
titleProvably robust deep learning via adversarially trained smoothed classifiers

booktitleInternational Conference on Learning Representations (ICLR)
titleDefense-GAN: Protecting Classifiers Against Adversarial Attacks Using Generative Models

journaltitleIEEE Transactions on Signal Processing
titleDiagonalizing Properties of the Discrete Cosine Transforms

booktitleInternational Conference on Learning Representations (ICLR)
titleExact solutions to the nonlinear dynamics of learning in deep linear neural networks

journaltitlearXiv preprint arXiv:1312.6120
titleExact Solutions to the Nonlinear Dynamics of Learning in Deep Linear Neural Networks

journaltitleLinear Algebra and its Applications
titleDecomposing a Matrix into Circulant and Diagonal Factors

booktitleAdvances in Neural Information Processing Systems (NeurIPS)
titleAdversarially robust generalization requires more data

booktitleInternational Conference on Learning Representations (ICLR)
titleThe Singular Values of Convolutional Layers

journaltitleBIT Numerical Mathematics
titlePreconditioning strategies for asymptotically ill-conditioned block Toeplitz systems

journaltitleLinear algebra and its applications
titleThe extension of the concept of the generating function to a class of preconditioned Toeplitz matrices

Cambridge university press

titleUnderstanding machine learning: From theory to algorithms

Nokia Bell Labs

journaltitleThe Bell system technical journal
titleCommunication theory of secrecy systems

Springer Singapore

booktitleAutomating Cities: Design, Construction, Operation and Future Impact

journaltitlearXiv preprint arXiv:1909.08053
titleMegatron-lm: Training Multi-Billion Parameter Language Models using GPU Model Parallelism

Nature Publishing Group

titleMastering the game of go without human knowledge

journaltitlearXiv preprint arXiv:1802.01421
titleAdversarial Vulnerability of Neural Networks Increases With Input Dimension

journaltitlearXiv preprint arXiv:1409.1556
titleVery Deep Convolutional Networks for Large-Scale Image Recognition

booktitleAdvances in Neural Information Processing Systems (NeurIPS)
titleStructured transforms for Small-Footprint Deep Learning

journaltitlearXiv preprint arXiv:1911.10258
titleBounding Singular Values of Convolution Layers

journaltitlearXiv preprint arXiv:1706.04572
titleDeep Learning Methods for Efficient Large Scale Video Labeling

journaltitleJournal of Physics A: Mathematical and Theoretical
titleA jamming transition from under- to over-parametrization affects generalization in deep learning

booktitleProceedings of the 57th Annual Meeting of the Association for Computational Linguistics
titleEnergy and Policy Considerations for Deep Learning in NLP

booktitleProceedings of the 31st AAAI Conference on Artificial Intelligence
titleInception-v4, Inception-ResNet and the Impact of Residual Connections on Learning

booktitleInternational Conference on Learning Representations (ICLR)
titleIntriguing properties of neural networks

journaltitleMathematische Annalen
titleEin Grenzwertsatz über die Toeplitzschen Determinanten einer reellen positiven Funktion

booktitleProceedings of the 36th International Conference on Machine Learning (ICML)
titleEfficientNet: Rethinking Model Scaling for Convolutional Neural Networks

booktitleAdvances in Neural Information Processing Systems (NeurIPS)
titleLearning Compressed Transforms with Low Displacement Rank

journaltitleMathematics of computation
titleOn the asymptotic spectrum of Hermitian block Toeplitz matrices with Toeplitz blocks

journaltitleLinear algebra and its applications
titleSingular values and eigenvalues of non-Hermitian block Toeplitz matrices

booktitleInternational Joint Conference on Neural Networks (IJCNN)
titleCompressing recurrent neural network with tensor train

booktitleInternational Conference on Learning Representations (ICLR)
titleDeep Complex Networks

booktitleAdvances in Neural Information Processing Systems (NeurIPS)
titleOn Adaptive Attacks to Adversarial Example Defenses

booktitleAdvances in Neural Information Processing Systems (NeurIPS)
titleAdversarial training and robustness for multiple perturbations

booktitleAdvances in Neural Information Processing Systems (NeurIPS)
titleLipschitz-margin training: Scalable certification of perturbation invariance for deep neural networks

titleSome mathematical notes on three-mode factor analysis

titleComputing Machinery and Intelligence

journaltitleLinear algebra and its applications
titleSpectra of multilevel Toeplitz matrices: advanced theory via simple matrix relationships

booktitleMeasures of complexity
titleOn the uniform convergence of relative frequencies of events to their probabilities

booktitleAdvances in Neural Information Processing Systems (NeurIPS)
titleAttention is all you need

Springer Science & Business Media

titleOptimal transport: old and new

booktitleAdvances in Neural Information Processing Systems (NeurIPS)
titleLipschitz regularity of deep neural networks: analysis and efficient estimation

journaltitleJournal of Functional Analysis
titleA Variant of the Johnson–Lindenstrauss Lemma for Circulant Matrices

booktitleProceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)
titleOrthogonal Convolutional Neural Networks

Prentice Hall

booktitleStudies in Real and Complex Analysis
seriesStudies in Mathematics
titleToeplitz Matrices

Academic Press

journaltitleAdvances in Mathematics
titleAsymptotic behavior of block Toeplitz matrices and determinants. II

journaltitlearXiv preprint arXiv:1609.08144
titleGoogle's Neural Machine Translation System: Bridging the Gap Between Human and Machine Translation

booktitleProceedings of the 35th International Conference on Machine Learning (ICML)
titleDynamical Isometry and a Mean Field Theory of CNNs: How to Train 10,000-Layer Vanilla Convolutional Neural Networks

booktitleInternational Conference on Learning Representations (ICLR)
titleMitigating Adversarial Effects Through Randomization

booktitleProceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)
titleAggregated residual transformations for deep neural networks

booktitleProceedings of the 34th International Conference on Machine Learning (ICML)
titleTensor-train recurrent neural networks for video classification

booktitleAdvances in Neural Information Processing Systems (NeurIPS)
titleXlnet: Generalized autoregressive pretraining for language understanding

journaltitlearXiv preprint arXiv:1705.10941
titleSpectral Norm Regularization for Improving the Generalizability of Deep Learning

titleAutomatic Speech Recognition

booktitleProceedings of the 31st International Conference on Machine Learning (ICML)
titleCirculant Binary Embedding

journaltitlearXiv preprint arXiv:1503.03893
titleCompact Nonlinear Maps and Circulant Extensions

booktitleProceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)
titleOn Compressing Deep Models by Low Rank and Sparse Decomposition

booktitleProceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)
titleBeyond Short Snippets: Deep Networks for Video Classification

booktitleProceedings of the British Machine Vision Conference (BMVC)
titleWide Residual Networks

booktitleInternational Conference on Learning Representations (ICLR)
titleUnderstanding Deep Learning Requires Rethinking Generalization

Springer Science & Business Media

titleMatrix theory: basic results and techniques

journaltitlearXiv preprint arXiv:1901.08573
titleTheoretically Principled Trade-Off Between Robustness and Accuracy

booktitleProceedings of the 34th International Conference on Machine Learning (ICML)
titleTheoretical Properties for Neural Networks with Weight Matrices of Low Displacement Rank

booktitleAdvances in Neural Information Processing Systems (NeurIPS)
titleDeconstructing lottery tickets: Zeros, signs, and the supermask

booktitleProceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)
titleLearning transferable architectures for scalable image recognition

journaltitleIEEE transactions on Signal Processing
titleStochastic resonance in discrete time nonlinear AR(1) models

journaltitleMathematische Annalen
titleEin Grenzwertsatz über die Toeplitzschen Determinanten einer reellen positiven Funktion

Wiley Online Library

journaltitleJournal of Mathematics and Physics
titleThe expression of a tensor or a polyadic as a sum of products

Wiley Online Library

journaltitleZAMM-Journal of Applied Mathematics and Mechanics/Zeitschrift für Angewandte Mathematik und Mechanik
titlePraktische Verfahren der Gleichungsauflösung.

journaltitleThe bulletin of mathematical biophysics
titleA logical calculus of the ideas immanent in nervous activity

Nokia Bell Labs

journaltitleThe Bell system technical journal
titleCommunication theory of secrecy systems

titleComputing Machinery and Intelligence

journaltitlePhysics Today
titleToeplitz Forms and Their Applications

American Psychological Association

journaltitlePsychological review
titleThe perceptron: a probabilistic model for information storage and organization in the brain.

journaltitleTransactions of the American Mathematical Society
titleExtreme eigenvalues of Toeplitz forms and applications to elliptic difference equations

Hungarian Academy of Sciences Budapest Hungary