On Regularization and Robustness of Deep Neural Networks
Year: 2018

Abstract:
In this work, we study the connection between regularization and robustness of deep neural networks by viewing them as elements of a reproducing kernel Hilbert space (RKHS) of functions and by regularizing them using the RKHS norm. Even though this norm cannot be computed, we consider various approximations based on upper and lower bounds. These approximations lead to new strategies for regularization, but also to existing ones such as spectral norm penalties or constraints, gradient penalties, or adversarial training. Besides, the kernel framework allows us to obtain margin-based bounds on adversarial generalization. We show that our new algorithms lead to empirical benefits for learning on small datasets and learning adversarially robust models. We also discuss implications of our regularization framework for learning implicit generative models.

heading: 1 Introduction
text: Learning predictive models for complex tasks often requires large amounts of annotated data. Interestingly, successful models such as convolutional neural networks are also hugedimensional and typically involve more parameters than training samples. Such a setting is challenging: besides the fact that training with small datasets is difficult, these models also lack robustness to small adversarial perturbations (Szegedy et al., 2013; Biggio & Roli, 2018). In the context of perceptual tasks such as vision (Szegedy et al., 2013) or speech recognition (Carlini & Wagner, 2018), these perturbed examples are often perceived identically to the original ones by a human, but can lead to arbitrarily different model predictions. In this paper, we present a unified perspective on regularization and robustness, by viewing convolutional neural networks as elements of a particular reproducing kernel Hilbert space (RKHS) following the work of Bietti & Mairal (2018) on deep convolutional kernels. For such kernels, the RKHS contains indeed deep convolutional networks similar to generic ones—up to smooth approximations of rectified linear units. Such a point of view is interesting to adopt for deep networks since it provides a natural regularization function, the RKHS norm, which allows us to control the variations of the predictive model according to the geometry induced by the kernel. Besides, the norm also acts as a Lipschitz constant, which provides a direct control on the stability to adversarial perturbations. In contrast to traditional kernel methods, the RKHS norm cannot be explicitly computed in our setup. Yet, these norms admit numerous approximations—lower bounds and upper bounds—which lead to new strategies for regularization based on penalties, constraints, or combinations thereof. Additionally, our framework provides an interpretation of some existing regularization approaches as controlling either upper or lower bounds on the RKHS norm, such as using penalties or constraints on the spectral norm of the filters (Yoshida & Miyato, 2017), various forms of robust optimization (Madry et al., 2018), double backpropagation (Drucker & Le Cun, 1991), and tangent propagation (Simard et al., 1998). Moreover, regularization and robustness are tightly linked in our kernel framework. In particular, we study the connection between adversarial training under `2 perturbations and penalizing with the RKHS norm, in a similar vein to Xu et al. (2009b); from a statistical point of view, we extend margin-based generalization bounds in the spirit of Bartlett et al. (2017); Boucheron et al. (2005) to the setting of adversarially robust generalization (see
Schmidt et al., 2018). Following these observations, we provide an empirical evaluation of the different regularization strategies obtained, by considering learning tasks with small datasets or with adversarial perturbations. Importantly, we find that robust optimization approaches often lead to a poor control of the RKHS norm, in favor of local stability and data fit, and that approaches based on spectral norms can be locally unstable. In contrast, our new lower bound penalties, as well as combined approaches based on both upper and lower bounds, enable a tighter control of the RKHS norm, yielding empirical benefits in various regimes and better guarantees. We also provide a new perspective on recent successful approaches to training generative adversarial networks as optimizing a kernel two-sample test (see, e.g., Gretton et al., 2012).
Related work. The construction of hierarchical kernels and the study of neural networks in the corresponding RKHS was studied by Mairal (2016); Zhang et al. (2016; 2017); Bietti & Mairal (2018). Our study of the relationship between robustness and regularization follows from Xu et al. (2009a;b), where the main focus is on linear models with quadratic or hinge losses. Some of the regularization strategies we obtain from our kernel perspective are closely related to previous approaches to adversarial robustness (Cisse et al., 2017; Madry et al., 2018; Simon-Gabriel et al., 2018; Roth et al., 2018), to improving generalization (Drucker & Le Cun, 1991; Miyato et al., 2018b; Sedghi et al., 2018; Simard et al., 1998; Yoshida & Miyato, 2017), and stable training of generative adversarial networks (Roth et al., 2017; Gulrajani et al., 2017; Arbel et al., 2018; Miyato et al., 2018a). The notion of adversarial generalization was considered by Schmidt et al. (2018), who provide lower bounds on a specific example of data distribution. Sinha et al. (2018) provide generalization guarantees in the different setting of distributional robustness; compared to our bound, they consider expected loss instead of classification error, and their bounds do not highlight the dependence on the model complexity.

heading: 2 Regularization strategies for deep neural networks
text: In this section, we recall the kernel perspective on deep networks introduced by Bietti & Mairal (2018), and present upper and lower bounds on the RKHS norm of a given model, leading to various regularization strategies. For simplicity, we first consider real-valued networks and binary classification, before discussing multi-class extensions.

heading: 2.1 Relation between deep neural networks and RKHSs
text: Kernel methods consist of mapping data living in a set X to a RKHS H associated to a positive definite kernel K through a mapping function Φ : X → H, and then learning simple machine learning models in H. Specifically, when considering a real-valued regression or binary classification problem, classical kernel methods find a prediction function f : X → R living in the RKHS which can be written in linear form, i.e., such that f(x) = 〈f,Φ(x)〉H for all x in X . While explicit mapping to a possibly infinite-dimensional space is of course only an abstract mathematical operation, learning f can be done implicitly by computing kernel evaluations and typically by using convex programming (Schölkopf & Smola, 2001). Moreover, the RKHS norm ‖f‖H acts as a natural regularization function, which controls the variations of model predictions according to the geometry induced by Φ:
|f(x)− f(x′)| ≤ ‖f‖H · ‖Φ(x)− Φ(x′)‖H. (1)
Unfortunately, traditional kernel methods become difficult to use when the datasets are large or when evaluating the kernel is intractable. Here, we propose a different approach that considers explicit parameterized representations of functions contained in the RKHS, given by generic convolutional neural networks, and leverage properties of the RKHS and the kernel mapping in order to regularize when learning the network parameters. Consider indeed a real-valued deep convolutional network f : X → R, where X is simply Rd, with rectified linear unit (ReLU) activations and no bias units. By constructing an appropriate multi-layer hierarchical kernel, Bietti & Mairal (2018) show that the corresponding RKHS H contains a convolutional network with the same architecture and parameters as f ,
but with activations that are smooth approximations of ReLU. Although the model predictions might not be strictly equal, we will abuse notation and denote this approximation with smooth ReLU by f as well, with the hope that the regularization procedures derived from the RKHS model will be effective in practice on the original CNN f . Besides, Bietti & Mairal (2018) show that the mapping Φ(·) is non-expansive:
‖Φ(x)− Φ(x′)‖H ≤ ‖x− x′‖2, (2)
so that controlling ‖f‖H provides some robustness to additive `2-perturbations, by (1). Additionally, with appropriate pooling operations, Bietti & Mairal (2018) show that the kernel mapping is also stable to deformations, meaning that the RKHS norm also controls robustness to translations and other transformations including scaling and rotations (Engstrom et al., 2017), which can be seen as deformations when they are small. In contrast to standard kernel methods, where the RKHS norm is typically available in closed form, this norm is difficult to compute in our setup, and requires approximations. The following sections present upper and lower bounds on ‖f‖H, with linear convolutional operations denoted by Wk for k = 1, . . . , L, where L is the number of layers. Defining θ := {Wk : k = 1, . . . , L}, we then leverage these bounds to approximately solve the following penalized or constrained optimization problems on a training set (xi, yi), i = 1, . . . , n:
min θ 1 n n∑ i=1 `(yi, fθ(xi)) + λ‖fθ‖2H or min θ:‖fθ‖H≤C 1 n n∑ i=1 `(yi, fθ(xi)). (3)
We also note that while the construction of Bietti & Mairal (2018) considers VGG-like networks (Simonyan & Zisserman, 2014), the regularization algorithms we obtain in practice can be easily adapted to different architectures such as residual networks (He et al., 2016).

heading: 2.2 Exploiting Lower bounds of the RKHS norm
text: In this section, we devise regularization algorithms by leveraging lower bounds on ‖f‖H, which are obtained by relying on the following variational characterization of Hilbert norms:
‖f‖H = sup ‖u‖H≤1 〈f, u〉H. (4)
At first sight, this definition is not useful since the set U = {u ∈ H : ‖u‖H ≤ 1} may be infinite-dimensional and the inner products 〈f, u〉H cannot be computed in general. Thus, we devise tractable lower bound approximations by considering smaller sets Ū ⊂ U .
Adversarial perturbation penalty. The non-expansiveness of Φ allows us to consider the subset Ū ⊂ U defined as Ū = {Φ(x+ δ)−Φ(x) : x ∈ X , ‖δ‖2 ≤ 1}, leading to the bound
‖f‖H ≥ sup x∈X ,‖δ‖2≤1 f(x+ δ)− f(x), (5)
which is reminiscent of adversarial perturbations. Adding a regularization parameter > 0 in front of the norm then corresponds to different sizes of perturbations:
‖f‖H = sup ‖u‖H≤ 〈f, u〉H ≥ sup x∈X ,‖δ‖2≤ f(x+ δ)− f(x). (6)
Using this lower bound or its square as a penalty in the objective (3) when training a neural network can then provide a way to regularize. Optimizing over adversarial perturbations has been useful to obtain robust models (e.g., the PGD method of Madry et al., 2018), yet our approach differs in two important ways: (i) it involves a global maximization problem on the input space X , as opposed to only maximizing on perturbations near training data; (ii) it involves a separate penalty term in the training objective, in contrast to PGD which encourages a perfect fit of the training data by considering perturbations on the loss term. We further discuss the links with the robust optimization problem solved by PGD below. In practice, optimizing over all x in X is difficult, and we can replace X with random subsets of examples (such as mini-batches), which may be labeled or not, yielding further
lower bounds on the penalty. In the context of a mini-batch stochastic gradient algorithm, one can obtain a subgradient of this penalty by first finding maximizers x̂, δ̂ (where x̂ is one of the examples in the mini-batch), and then simply computing gradients of fθ(x̂+ δ̂)−fθ(x̂) (or its square) w.r.t. θ using back-propagation. We compute the perturbations δ̂ for each example x by using a few steps of projected subgradient ascent with constant step-lengths, in a similar fashion to Madry et al. (2018) in the context of robust optimization.
Relationship with robust optimization. In some contexts, our penalized approach is related to solving the robust optimization problem
min θ 1 n n∑ i=1 sup ‖δ‖2≤ `(yi, fθ(xi + δ)), (7)
which is commonly considered for training adversarially robust classifiers (Kolter & Wong, 2017; Madry et al., 2018; Raghunathan et al., 2018). In particular, Xu et al. (2009b) show that the penalized and robust objectives are equivalent in the case of the hinge loss with linear predictors, when the data is non-separable. They also show the equivalence for kernel methods when considering the (intractable) full perturbation set U around each point in the RKHS Φ(xi), that is, predictions 〈f,Φ(xi) + u〉H with u in U . Intuitively, when a training example (xi, yi) is misclassified, we are in the “linear” part of the hinge loss, so that
sup ‖u‖H≤ `(yi, 〈f,Φ(xi) + u〉H) = `(yi, 〈f,Φ(xi)〉H) + sup ‖u‖H≤ 〈f, u〉H = `(yi, f(xi)) + ‖f‖H.
For other losses such as the the logistic loss, a regularization effect is still present even for correctly classified examples, though it may be smaller since the loss has a reduced slope for such points, leading to a more adaptive regularization mechanism which may automatically reduce the amount of regularization when the data is easily separable. However, this approach might only encourage local stability, while the global quantity ‖f‖H may grow uncontrolled in order to better fit the data. Nevertheless, it is easy to show that the robust objective (7) lower bounds the penalized objective with penalty ‖f‖H.
Gradient penalties. Taking Ū = {Φ(x)−Φ(y)‖x−y‖2 : x, y ∈ X}, which is a subset of U by Eq. (2)—it turns out that this is the same set as above, since Φ is homogeneous (Bietti & Mairal, 2018) and X = Rd—we obtain a lower bound based on the Lipschitz constant of f :
‖f‖H ≥ ‖f‖L := sup x,y∈X f(x)− f(y) ‖x− y‖2 ≥ sup x∈X ‖∇f(x)‖2
where the last inequality becomes an equality when X is convex, and the supremum is taken over points where f is differentiable. Although we are unaware of previous work using such a lower bound for a generic regularization penalty, we note that variants replacing the supremum over x by an expectation over data have been recently used to stabilize the training of generative adversarial networks (Gulrajani et al., 2017; Roth et al., 2017), and we provide insights in Section 3.2 on the benefits of RKHS regularization in such a setting. Related penalties have been considered in the context of robust optimization, for regularization or robustness, noting that a penalty based on the gradient of the loss can give a good approximation of (7) when is small (Drucker & Le Cun, 1991; Lyu et al., 2015; Roth et al., 2018; Simon-Gabriel et al., 2018). This has the advantage of overcoming the difficulties of the maximization problem over δ by leveraging the closed-form expression of the gradient norm, but it may only provide a poor approximation when is large, and exhibits the same concerns as other robust optimization approaches in terms of poorly controlling ‖f‖H.
Penalties based on deformation stability. We may also obtain new penalties by considering sets Ū = {Φ(x̃)−Φ(x) : x ∈ X , x̃ is a small deformation of x}, where the amount of deformation is dictated by the stability bounds of Bietti & Mairal (2018) in order to ensure that Ū ⊂ U . In particular, such bounds depend on the maximum displacement and maximum Jacobian norm of the diffeomorphisms considered. These can be easily computed for various parameterized families of transformations, such as translations, scaling or rotations, leading to simple ways to control the regularization strength through the parameters
of these transformations. One can also consider infinitesimal deformations from such parameterized transformations, and by replacing the supremum over X by an expectation over training data, we then obtain a gradient penalty that resembles the tangent propagation regularization strategy of Simard et al. (1998). If instead we consider robust optimization formulation (7), we obtain a form of data augmentation where transformations are optimized instead of sampled, as in Engstrom et al. (2017). One advantage of these approaches based on lower bounds is that the obtained penalties are independent of the model parameterization, making them flexible enough to use with more complex architectures in practice. In addition, the connection with robust optimization can provide a useful mechanism for adaptive regularization. However, these lower bounds do not guarantee a control on the RKHS norm, and this is particularly true for robust optimization approaches, which may favor small training loss and local stability over global stability through ‖f‖H. Nevertheless, our experiments suggest that our new approaches based on separate penalties often do help in controlling upper bounds as well (see Section 4).

heading: 2.3 Exploiting upper bounds: optimization with spectral norms
text: In contrast to lower bounds, upper bounds can provide a guaranteed control on the RKHS norm. Bietti & Mairal (2018) show the following upper bound:
‖f‖H ≤ ω(‖W1‖, . . . , ‖WL‖), (8) where ω is increasing in all of its arguments, and ‖Wk‖ is the spectral norm of the linear operator Wk. Here, we simply consider the spectral norm on the filters, given by ‖W‖ := sup‖x‖2≤1 ‖Wx‖2. Other generalization bounds relying on similar quantities have been proposed for controlling complexity (Bartlett et al., 2017; Neyshabur et al., 2018), suggesting that using them for regularization is relevant even beyond our kernel perspective, as observed in previous work (Cisse et al., 2017; Sedghi et al., 2018; Yoshida & Miyato, 2017).
Penalizing the spectral norms. One way to control the upper bound (8) when learning a neural network fθ is to consider a regularization penalty based on spectral norms
min θ 1 n n∑ i=1 `(yi, fθ(xi)) + λ L∑ l=1 ‖Wl‖2, (9)
where λ is a regularization parameter. In the context of a stochastic gradient algorithm, one can obtain (sub)gradients of the penalty by computing singular vectors associated to the highest singular value of each Wl. We consider the method of Yoshida & Miyato (2017), which computes such singular vectors approximately using one or two iterations of the power method, as well as a more costly approach using the full SVD.
Constraining the spectral norms with a continuation approach. In the constrained setting, we want to optimize:
min θ 1 n n∑ i=1 `(yi, fθ(xi)) s.t ‖Wl‖ ≤ τ ; l ∈ 1, . . . , L ,
where τ is a user-defined constraint. This objective may be optimized by projecting eachWl in the spectral norm ball of radius τ after each gradient step. Such a projection is achieved by truncating the singular values to be smaller than τ (see Appendix A). We found that the loss was hardly optimized with this approach, and therefore introduce a continuation approach with an exponentially decaying schedule for τ reaching a constant τ0 after a few epochs, which we found to be important for good empirical performance.
Combining with lower bounds. While these upper bound strategies are useful for limiting model complexity, we found them less effective for robustness in our experiments (see Section 4.2). However, we found that combining with lower bound approaches can overcome this weakness, perhaps due to a better control of local stability. In particular, such combined approaches often provide the best generalization performance in small data scenarios, as well as better guarantees on adversarially robust generalization thanks to a tighter control of the RKHS norm compared to robust optimization alone.

heading: 2.4 Extension to multiple classes and non-Euclidian geometries
text: We now discuss how to extend the regularization strategies to multi-valued networks, in order to deal with multiple classes. First, the upper bound strategies of Section 2.3 are easy to extend, by simply considering spectral norms up to the last layer. This is also justified by the generalization bound of Bartlett et al. (2017), which applies to the multi-class setup. In the context of lower bounds, we can consider a multi-class penalty ‖f1‖2H + . . .+ ‖fK‖2H for an RK-valued function f = (f1, f2, . . . , fK). One can then consider lower bounds on this penalty by leveraging lower bounds on each individual fk. In particular, we define:
‖f‖2M := K∑ k=1 sup x∈X ,‖δ‖2≤ (fk(x+ δ)− fk(x))2 and ‖∇f‖2 := K∑ k=1 sup x∈X ‖∇fk(x)‖22,
where we use mini-batches of training data instead of X in our experiments. For robust optimization formulations (7), the extension is straightforward, given that standard multiclass losses such as the cross-entropy loss can be directly optimized in an adversarial training or gradient penalty setup. Finally, we note that while the kernel approach introduced in this section mainly considers the Euclidian geometry in the input space, it is possible to consider heuristic alternatives for other geometries, such as `∞ perturbations, as discussed in Appendix B.

heading: 3 Theoretical guarantees and insights
text: In this section, we study how standard margin-based generalization bounds can be extended to an adversarial setting in order to provide theoretical guarantees on adversarially robust generalization. We then discuss how our kernel approach provides novel interpretations for training generative adversarial networks.

heading: 3.1 Guarantees on adversarial generalization
text: While various methods have been introduced to empirically gain robustness to adversarial perturbations, the ability to generalize with such perturbations, also known as adversarial generalization (Schmidt et al., 2018), still lacks theoretical understanding and useful guarantees. Margin-based bounds have been useful to explain the generalization behavior of learning algorithms that can fit the training data well, such as kernel methods, boosting and neural networks (Koltchinskii et al., 2002; Boucheron et al., 2005; Bartlett et al., 2017). Here, we show how such arguments can be adapted to obtain guarantees on adversarial generalization, i.e., on the expected classification error in the presence of an `2-bounded adversary, based on the RKHS norm of a given model learned from data. For a binary classification task with labels in Y = {−1, 1} and data distribution D, we would like to bound the expected adversarial error of a classifier f , given for some > 0 by
errD(f, ) := P(x,y)∼D(∃‖δ‖2 ≤ : yf(x+ δ) < 0). (10) Leveraging the fact that f is ‖f‖H-Lipschitz, we now show how to further bound this quantity using empirical margins, following the usual approach to obtaining margin bounds for kernel methods (e.g., Boucheron et al., 2005). Consider a training dataset (x1, y1), . . . , (xn, yn) ∈ X × Y. Define
Lγn(f) := 1 n n∑ i=1 1{yif(xi) < γ}.
We then have the following bound, proved in Appendix C: Proposition 1. With probability 1 − δ over a dataset {(xi, yi)}i=1,...,n, we have, for all choices of γ > 0 and f ∈ H,
errD(f, ) ≤ Lγ+2 ‖f‖Hn (f) +O ‖f‖H γ √ n √√√√ 1 n n∑ i=1 K(xi, xi) + √ log(C(‖f‖H, γ)/δ) n  , (11) where C(‖f‖H, γ) = (1 + 4(log2 ‖f‖H)2) · (1 + 4(log2(1/γ))2).
When = 0, this leads to the usual margin bound, while > 0 yields a bound on adversarial error errD(f, ), for some neural network f learned from training data. We note that other complexity measures based on products of spectral norms may be used instead of ‖f‖H, as well as multi-class extensions, following Bartlett et al. (2017); Neyshabur et al. (2018). One can then study the effectiveness of a regularization algorithm by inspecting cumulative distribution (CDF) plots of the normalized margins γ̄i = yif(xi)/‖f‖H, for different strenghts of regularization (an example is given in Figure 2, Section 4.2). According to the bound (11), one can assess expected adversarial error with -bounded perturbations by looking at the part of the plot to the right of γ̄ = 2 .In particular, the value of the CDF at such a value of γ̄ is representative of the bound for large n (since the second term is negligible), while for smaller n, the best bound is obtained for a larger value of γ̄, which also suggests that the right side of the plots is indicative of performance on small datasets. When the RKHS norm can be well approximated, then our bound provides a certificate on test error in the presence of adversaries. While such an approximation is difficult to obtain in general, the guarantee is most useful when lower and upper bounds are controlled together. We found this to be the case in our experiments for our new lower bound penalties based on adversarial perturbations or gradient norms (see Section 4.2). In contrast, we found that the upper bound is poorly controlled for robust optimization approaches such as PGD, possibly because these approaches mainly encourage local robustness around training points. In such settings, our guarantee is less meaningful, and one would likely need local verification on each test example in order to guarantee robustness to all adversaries, a possibly costly procedure. Nevertheless, our guarantee can be made more useful in such settings as well by explicitly controlling the upper bound with spectral norm constraints.

heading: 3.2 Regularization of generative adversarial networks
text: Generative adversarial networks attempt to learn a generator neural network Gφ : Z → X , so that the distribution ofGφ(z) with z ∼ Dz a noise vector resembles a data distributionDx. Various recent approaches have relied on regularization strategies on a discriminator network in order to improve the stability of GAN training and the quality of the produced samples. Some of these resemble our approaches from Section 2 such as gradient penalties (Gulrajani et al., 2017; Roth et al., 2017) and spectral norm regularization (Miyato et al., 2018a). While these regularization methods had different motivations originally, we suggest that viewing them as approximations of an RKHS norm constraint provides some insight into their effectiveness in practice; specifically, we provide an interpretation as optimizing a kernel two-sample test such as MMD with the convolutional kernel introduced in Section 2:
min φ sup f∈H:‖f‖H≤1 Ex∼Dx [f(x)]− Ez∼Dz [f(Gφ(z))]. (12)
In contrast to the Wasserstein GAN interpretation of a similar objective where all 1-Lipschitz functions are considered (Arjovsky et al., 2017), the MMD interpretation yields a parametric statistical rate O(n−1/2) when learning from an empirical distribution with n samples, which is significantly better than the O(n−1/d) rate of the Wasserstein-1 distance for highdimensional data such as images (Sriperumbudur et al., 2012). While the MMD approach has been used for training generative models, it generally relies on a generic kernel function, such as a Gaussian kernel, that appears explicitly in the objective (Dziugaite et al., 2015; Li et al., 2017; Bińkowski et al., 2018). Although using a learned feature extractor can improve this, the Gaussian kernel might be a poor choice when dealing with natural signals such as images, while the hierarchical kernel of Bietti & Mairal (2018) is better suited for this type of data, by providing useful invariance and stability properties. Leveraging the variational form of the MMD (12) with this kernel suggests using convolutional networks as the discriminator f , with constraints on the spectral norms in order to ensure ‖f‖H ≤ C for some C, as done by Miyato et al. (2018a) through normalization.

heading: 4 Experiments
text: We tested the regularization strategies presented in Section 2 in the context of improving generalization on small datasets and training adversarially robust models. Our goal is to use common convolutional architectures used for large datasets and improve their performance in different settings through regularization. For the adversarial training strategies, the inner maximization problems are solved with 5 steps of projected gradient ascent (Madry et al., 2018) with a randomly chosen starting point. In the case of the multi-class lower bound penalties ‖f‖2M and ‖∇f‖2 (see Section 2.4), we also maximize over examples in the mini-batch, only considering the maximal element when computing gradients w.r.t. parameters. For the robust optimization problem (7), we consider the PGD approach for `2 and `∞ perturbations (Madry et al., 2018), as well as the corresponding `2 (squared) and `1 gradient norm penalties. For the upper bound approaches with spectral norms (SNs), we consider the SN projection strategy with decaying τ , as well as the SN penalty (9), either using power iteration (PI) or a full SVD for computing gradients.

heading: 4.1 Improving generalization on small datasets
text: In this setting, we use 1 000 and 5 000 examples of the CIFAR10 dataset, with or without data augmentation. We consider a VGG network (Simonyan & Zisserman, 2014) with 11 layers, as well as a residual network (He et al., 2016) with 18 layers, which achieve 91% and 93% test accuracy respectively when trained on the full training set with data augmentation. We do not use any batch normalization layers in order to prevent any interaction with spectral norms. Each regularization strategy derived in Section 2 is trained for 500 epochs using SGD with momentum and batch size 128, halving the step-size every 40 epochs from a fixed initial step-size (0.05 for VGG-11, 0.1 for ResNet-18), a strategy we found to work relatively well for all methods. In order to study the potential effectiveness of each method, we assume that a fairly large validation set is available to select hyper-parameters; thus, we keep 10 000 annotated examples for this purpose. Table 1 shows the test accuracies we obtain for upper and lower bound approaches, as well as combined approaches and different geometries. We also include virtual adversarial training (VAT, Miyato et al., 2018b). Among upper bound strategies, the constrained approach often works best, perhaps thanks to a more explicit control of the SNs compared to the
penalized approach. The SN penalty can work well nevertheless, and provides computational benefits when using the PI variant. For lower bound approaches, we found our ‖f‖2M and ‖∇f‖2 penalties to often work best, particularly without data augmentation, while the robust optimization gradient `1 and `2 norm penalties can be preferable with data augmentation. We note that the best regularization parameters are often quite small on such datasets, making the gradient penalties good approximations of the robust objective (7) used by PGD. Because gradient penalties have closed form gradients while PGD only obtains them by solving (7) approximately, they may work better in this setting thanks to optimization benefits. The adaptive nature of the regularization through robust optimization may also be beneficial on these datasets which are often easily separable with CNNs, however the explicit penalization by ‖f‖2M or‖∇f‖2 seems to be more helpful in the case of 1 000 examples with no data augmentation, which is plausibly the hardest setting in our experiments. Finally, we can see that the combined approaches of lower bounds (either robust optimization, or separate penalties) together with SN constraints often yield the best results. Indeed, lower bound approaches alone do not necessarily control the upper bounds (and this is particularly true for PGD, as discussed in Section 4.2), which might explain why the additional constraints on SNs are helpful.

heading: 4.2 Training adversarially robust models
text: We consider the same VGG architecture as in Section 4.1, trained on CIFAR10 with data augmentation, with different regularization strategies. Each method is trained for 300 epochs using SGD with momentum and batch size 128, dividing the step-size in half every 30 epochs. This strategy was successful in reaching convergence for all methods. Figure 1 shows the test accuracy of the different methods in the presence of `2-bounded adversaries, plotted against standard accuracy. We can see that the robust optimization approaches tend to work better in high-accuracy regimes, perhaps because the local stability and data fit that they encourage are sufficient on this dataset, while the ‖f‖2M penalty can be useful in some regimes where robustness to large perturbations is needed. We find that upper bound approaches alone do not provide robust models, but Figure 1(bottom) shows that combining the SN projection approach with a lower bound strategy (in this case PGD-`2) helps improve robustness, perhaps thanks to a better control of margins and stability. The plots also confirm that gradient penalties are preferable for small regularization strengths (they achieve higher accuracy while improving robustness for small test), possibly due to
better optimization, while for stronger regularization, the gradient approximation no longer holds and the adversarial training approaches such as PGD are preferred. These results suggest that a robust optimization approach such as PGD can work very well on the CIFAR10 dataset, perhaps because the training data is easily separable with a large margin and the method adapts to this “easiness”. However, this raises the question of whether the approach is actually controlling ‖f‖H, given that it only attempts to minimize a lower bound, as discussed in Section 2.2. Figure 2(left) casts some doubt on this, showing that for PGD in contrast to other methods, the product of spectral norms (representative of an upper bound on ‖f‖H) increases when the lower bound ‖f‖M decreases. This suggests that a network learned with PGD with large may have large RKHS norm, possibly because the approach tries to separate -balls around the training examples, which may require a more complex model than simply separating the training examples (see also Madry et al., 2018). This large discrepancy between upper and lower bounds highlights the fact that such models may only be stable locally near training data, though this happens to be enough for robustness on many test examples on CIFAR10. Moreover, guaranteeing robustness at test time against all adversaries would likely require expensive verification procedures, given that the global guarantee given by the product of spectral norms is weak in this case. In constrast, for other methods, and in particular the lower bound penalties ‖f‖2M and ‖∇f‖2, the upper and lower bounds appear more tightly controlled, suggesting a more appropriate control of the RKHS norm. This makes our guarantees on adversarial generalization more meaningful, and thus we may look at the empirical distributions of normalized margins γ̄ obtained using ‖f‖M for normalization, shown in Figure 2(right). The curves suggest that for small γ̄, smaller values of λ are preferred, while stronger regularization helps when γ̄ increases, yielding lower test error when an adversary is present according to our bounds in Section 3.1. This qualitative behavior is indeed observed in the results of Figure 1 on test data for the ‖∇f‖2 penalty approach.

heading: 5 Discussion
text: Making generic machine learning techniques more data efficient is crucial to reduce the costs related to annotation. While other approaches may also be important to solve this grand challenge, such as incorporating more prior knowledge in the architecture (e.g., Oyallon et al., 2017), semi-supervised learning (Chapelle et al., 2006) or meta-learning (when multiple tasks or datasets are available, see, e.g., Thrun, 1998), basic regularization principles will be needed and those are crucially missing today. Such principles are also essential for obtaining robust models in applications where security is a concern, such as self driving cars. Our paper presents various algorithmic strategies for regularization on generic deep convolutional networks, by leveraging the structure of an appropriate RKHS, leading to many existing approaches to regularization, as well as new ones, in addition to providing theoretical guarantees and insights on different methods.

heading: A Details on optimization with spectral norms
text: This section details our optimization approach presented in Section 2.3 for learning with spectral norm constraints. In particular, we rely on a continuation approach, decreasing the size of the ball constraints during training, towards a final value τ . The method is presented in Algorithm 1. We use an exponentially decreasing schedule for τ , and found using 2 epochs for κ to work well in practice. In the context of convolutional networks, we simply consider the SVD of a reshaped filter matrix, but we note that alternative approaches based on the singular values of the full convolutional operation may also be used (Sedghi et al., 2018).

heading: B Extensions to non-Euclidian geometries
text: The kernel approach from previous sections is well-suited for input spaces X equipped with the Euclidian distance, thanks to the non-expansiveness property (2) of the kernel mapping. In the case of linear models, this kernel approach corresponds to using `2-regularization
Algorithm 1 Stochastic projected gradient with continuation Input: τ , κ, step-sizes ηt for t = 1, . . . do Sample mini-batch and compute gradients of the loss w.r.t. each W l, denoted Glt τt = τ(1 + exp (−t κ ) )
for l = 1, . . . , L do W̃ lt := W lt − ηtGlt Compute SVD: W̃ lt = Udiag(σ)V T σ̂ := proj‖.‖∞≤τt (σ) W lt+1 := Udiag(σ̂)V T
end for end for
by taking a linear kernel. However, other forms of regularization and geometries can often be useful, for example to encourage sparsity with an `1 regularizer. Such a regularization approach presents tight links with robustness to `∞ perturbations on input data, thanks to the duality relation ‖w‖1 = sup‖u‖∞〈w, u〉 (see Xu et al., 2009a).
In the context of deep networks, we can leverage such insights to obtain new regularizers, expressed in the same variational form as the lower bounds in Section 2.2, but with different geometries on X . For `∞ perturbations, we obtain
sup x,y∈X f(x)− f(y) ‖x− y‖∞ ≥ sup x∈X ‖∇f(x)‖1. (13)
The Lipschitz regularizer (l.h.s.) can also be taken in an adversarial perturbation form, with `∞-bounded perturbations ‖δ‖∞ ≤ . When considering the corresponding robust optimization problem
min θ 1 n n∑ i=1 sup ‖δ‖∞≤ `(yi, fθ(xi + δ)), (14)
we may consider the PGD approach of Madry et al. (2018), or the associated gradient penalty approach with the `1 norm, which is a good approximation when is small (Lyu et al., 2015; Simon-Gabriel et al., 2018). As most visible in the gradient `1-norm in (13), these penalties encourage some sparsity in the gradients of f , which is a reasonable prior for regularization on images, for instance, where we might only want predictions to change based on few salient pixel regions. This can lead to gains in interpretability, as observed by Tsipras et al. (2018). We note that in the case of linear models, our robust margin bound of Section 3.1 can be adapted to `∞-perturbations, by leveraging Rademacher complexity bounds for `1- constrained models (Kakade et al., 2009). Obtaining similar bounds for neural networks would be interesting but goes beyond the scope of this paper.
Experiments with `∞ adversaries. Figure 3 shows similar curves to Figure 1 from Section 4.2, but where the attacker is constrained in `∞ norm instead of `2 norm. We can see that using the right metric in PGD indeed helps against an `∞ adversary, nevertheless controlling global stability through the RKHS norm as in the ‖f‖2M and ‖∇f‖2 penalties can still provide some robustness against such adversaries, even with large test. For gradient penalties, we find that the different geometries behave quite similarly, which may suggest that more appropriate optimization algorithms than SGD could be needed to better accommodate the non-smooth case of `1/`∞, or perhaps that both algorithms are actually controlling the same notion of complexity on this dataset.

heading: C Details on generalization guarantees
text: This section presents the proof of Proposition 1, which relies on standard tools from statistical learning theory (e.g., Boucheron et al., 2005).
C.1 Proof of Proposition 1
Proof. Assume for now that γ is fixed in advance, and let Fλ := {f ∈ H : ‖f‖H ≤ λ}. Note that for all f ∈ Fλ we have
errD(f, ) = P (∃‖δ‖ ≤ : yf(x+ δ) < 0) ≤ P (yf(x) < λ ) =: Lλ (f), since ‖f‖H ≤ λ is an upper bound on the Lipschitz constant of f . Consider the function
φ(x) =  0, if x ≤ −γ − λ 1, if x ≥ −λ 1 + (x+ λ )/γ, otherwise.
Defining A(f) = Eφ(−yf(x)) ≥ Lλ (f) and An(f) = 1n ∑n i=1 φ(−yif(xi)) ≤ Lλ +γn (f), and noting that φ is upper bounded by 1 and 1/γ Lipschitz, we can apply similar arguments to (Boucheron et al., 2005, Theorem 4.1) to obtain, with probability 1− δ,
Lλ (f) ≤ Lλ +γn (f) +O (
1 γ Rn(Fλ) + √ log 1/δ n ) ,
where Rn(Fλ) denotes the empirical Rademacher complexity of Fλ on the dataset {(xi, yi)}i=1,...,n. Standard upper bounds on empirical Rademacher complexity of kernel classes with bounded RKHS norm yield the following bound
errD(f, ) ≤ Lλ +γn (f) +O  λ γ √ n √√√√ 1 n n∑ i=1 K(xi, xi) + √ log 1/δ n  . Note that the bound is still valid with γ′ ≥ γ instead of γ in the first term of the r.h.s., since Lγn(f) is non-decreasing as a function of γ. In order to establish the final bound, we instantiate the previous bound for values λi = 2i and γj = 2−j . Defining δi,j = δ(1+4i2)·(1+4j2) , we have that w.p. 1− δi,j , for all f ∈ Fλi and all γ ≥ γj ,
errD(f, ) ≤ Lλi +γn (f) +O  λi γj √ n √√√√ 1 n n∑ i=1 K(xi, xi) + √ log 1/δi,j n  . (15) By a union bound, this event holds jointly for all integers i, j w.p. greater than 1− δ, since∑ i,j δi,j ≤ δ. Now consider an arbitrary f ∈ H and γ > 0 and let i = dlog2 ‖f‖He and j = dlog2(1/γ)e. We have λi ≤ 2‖f‖H 1 γj ≤ 2 γ
log(1/δi,j) ≤ log(C(‖f‖H, γ)/δ).
Applying this to the bound in (15) yields the desired result.

Review summaries:
This paper looks at adversarial examples from the context of RKHS norms for neural networks.  The work builds conceptually on the work of Bietti and Mairal (2018), who investigate approximate RKHS norms for neural networks (including computation via a specialized convolutional kernel), and Xu et al., (2009) which looks at robustness properties of kernel classifiers.  The authors discuss how the RKHS norm of neural network functions provide robustness guarantees for the resulting classifier, both in terms of a straightforward robustness property for a given example, as well as in terms of generalization guarantees about robustness.

In this paper, the authors consider CNN models from the lens of kernel methods. They build upon past work that showed that such models can be seen to lie in appropriate RKHS, and derive upper and lower bounds for the kernel norm. These bounds can be used as regularizers that help train more robust neural networks, especially in the context of euclidean perturbations of the inputs, and training GANs. They show that the bounds can also be used to recover existing special cases such as spectral norm penalizations and gradient regularization. They derive generalization bounds from the point of view of adversarial learning, and report experiments to buttress their claims.