Year: 2019

Abstract:
Deep (neural) networks have been applied productively in a wide range of supervised and unsupervised learning tasks. Unlike classical machine learning algorithms, deep networks typically operate in the overparameterized regime, where the number of parameters is larger than the number of training data points. Consequently, understanding the generalization properties and the role of (explicit or implicit) regularization in these networks is of great importance. In this work, we explore how the oft-used heuristic of data augmentation imposes an implicit regularization penalty of a novel measure of the rugosity or “roughness” based on the tangent Hessian of the function fit to the training data.

heading: 1 INTRODUCTION
text: Deep (neural) networks are being profitably applied in a large and growing number of areas, from signal processing to computer vision and artificial intelligence. The expressive power of these networks has been demonstrated both in theory and practice (Cybenko, 1989; Barron, 1994; Telgarsky, 2015; Yarotsky, 2017; Hanin & Sellke, 2017; Daubechies et al., 2019). In fact, it has been shown that deep networks can even perfectly fit pure noise (Zhang et al., 2016). Surprisingly, highly overparameterized deep networks—where the number of network parameters exceeds the number of training data points—can be trained for a range of different classification and regression tasks and perform extremely well on unobserved data. Understanding why these networks generalize so well has been the subject of great interest in recent years. But, to date, classical approaches to bound the generalization error have failed to provide much insight into deep networks.
The ability of overparameterized deep networks to overfit noise while generalizing well suggests the existence of some kind of regularization in the learning process. Sometimes the regularization is explicit, as in the case of Tikhonov or `1 regularization (Krogh & Hertz, 1992; Bishop, 1995; Han et al., 2015; Bartlett et al., 2017). By contrast, we are becoming increasingly aware that various heuristic techniques—such as dropout (Baldi & Sadowski, 2013; Wager et al., 2013; Srivastava et al., 2014), batch normalization (Ioffe & Szegedy, 2015; Salimans & Kingma, 2016; Bjorck et al., 2018), and even stochastic gradient descent (Hardt et al., 2015; Bousquet & Elisseeff, 2002; Yao et al., 2007)—that are used in deep neural networks provide implicit regularization, having effects that are not as transparent. In this work, we study another such heuristic—data augmentation (Bengio et al., 2011; Dao et al., 2018; Rajput et al., 2019; Chen et al., 2019)—and show that it has a regularizing effect reducing what we call the rugosity, or “roughness”, of the function learned by the deep network.
Our rugosity measure quantifies how far the mapping f is from a locally linear mapping on the data. Building on the concept of Hessian eigenmaps introduced by Donoho & Grimes (2003), we evaluate this deviation from a locally linear mapping using the tangent Hessian, assuming the data points x ∈ RD lie on a low-dimensional manifoldM with dimension d D. Intuitively, we would expect functions that generalize well to be smooth—that is, to not have a high amount of rugosity. For example, in classification problems, if we were to partition the feature space by class, then we might expect the set corrresponding to any given class to consist of the union of a few contiguous regions with fairly smooth boundaries. A classification function with high rugosity, particularly near the true class boundaries, will likely have an unstable decision boundary, especially for noisy observations off of the data manifold. See Section 5 for a further discussion of the caveats of using rugosity alone as a rule for learning predictors.
A key part of our analysis leverages a new perspective on deep networks provided by Balestriero & Baraniuk (2018a;b). Let f(x) represent the mapping from the input to output of a deep network constructed using continuous, piecewise affine activations (e.g., ReLU, leaky ReLU, absolute value). Such a network partitions the input space RD based on the activation pattern of the network’s units (neurons). We call these partitions Qj ⊂ RD, the vector quantization (VQ) regions of the network, and for x ∈ RD we let Q(x) denote the VQ region to which x belongs. Inside one VQ region, f is simply an affine mapping. Consequently, f can be written as a continuous, piecewise affine operator
f(x) = AQ(x)x+ bQ(x) = A[x] x+ b[x]. (1)
For the sake of brevity, we will use the simplified notation f(x) = A[x] x+ b[x] in the sequel.
This framework enables us to cleanly reason about our extension of the rugosity measure to piecewise affine functions using finite differences, enabling us to make the connection between data augmentation the measure of rugosity via the A matrices.
Contributions. We summarize our contributions as follows: [C1] We develop a new rugosity measure of function complexity that measures how much a function deviates from locally linear, with a nontrivial extension of this measure to piecewise affine functions based on finite differences. [C2] We formally connect the popular heuristic of data augmentation to an explicit rugosity regularization. [C3] We verify experimentally that data augmentation reduces rugosity. [C4] We experimentally assess the effect of explicit rugosity regularization in training deep networks.
Related work. Recently, Savarese et al. (2019) have shown that, for one-dimensional, one-hiddenlayer ReLU networks, an `2 penalty on the weights (Tikhonov regularization) is equivalent to a penalty on the integral of the absolute value of the second derivative of the network output. Moreover, several recent works (Belkin et al., 2018; 2019; Hastie et al., 2019) have shown that in some linear and nonlinear inference problems, properly regularized overparameterized models can generalize well. This again indicates the importance of complexity regularization for understanding generalization in deep networks. Rifai et al. (2011) proposed an auto-encoder whose regularization penalizes the change in the encoder Jacobian. Also, Dao et al. (2018) studied the effects of data augmentation by modeling data augmentation as a kernel.

heading: 2 DATA AUGMENTATION
text: Data augmentation (Wong et al., 2016; Perez & Wang, 2017) is an oft-used yet poorly understood heuristic applied in learning the parameters of deep networks. The data augmentation procedure augments the set of n training data points {(xi, yi)}ni=1 to (m + 1)n training data points{ {(xi + uij , yi)}mj=0 }n i=1
by applying transformations to the training data xi such that they continue to lie on the data manifoldM. Example transformations applied to images include translation, rotation, color changes, etc.1 In such cases, uij is the vector difference xj − xi, where xj is the translated/rotated image, and ui0 = 0. Consider training a deep network with continuous, piecewise affine activations given the original training dataset {(xi, yi)}ni=1 by minimizing the loss
L , n∑ i=1 `i = n∑ i=1 `(f(xi), yi), (2)
where `(·, ·) is any convex loss function. After data augmentation, the loss can be written as
Laug = 1 m+ 1 n∑ i=1 `augi , ` aug i , `(f(xi), yi) + m∑ j=1 ` (f (xi + uij) , yi) . (3)
In the following result, we obtain an upper bound on the augmented loss, which consists of the sum of the non-augmented loss plus a few terms pertaining to the local similarity of the output function around the training data.
1Common transformations also include flipping images, which is not a continuous operation; however, our analysis here pertains primarily to continuous transformations, for which the vector differences uij are small.
Theorem 1. Consider a deep network with continuous, piecewise affine activations and thus prediction function f as in (1). Assume that ‖xi‖2 ≤ R, and that f has Lipschitz constant K1; that is, ‖A[x]‖2 ≤ K1, for all x. Further, assume that the loss function ` has Lipschitz constant K2. Then, for ‖uij‖2 ≤ ε, Laug in (3) can be upper bounded by
Laug ≤ L+ RK2 m+ 1 n∑ i=1 m∑ j=1 ‖A [xi + uij ]−A [xi]‖2
+ K2 m+ 1 n∑ i=1 m∑ j=1 |b [xi + uij ]− b [xi]|+ K1K2mnε m+ 1 + o(ε).
(4)
We focus our attention on the second term of the right-hand side of the above inequality. Denote this term by
Ĉ(f) , n∑ i=1 m∑ j=1 ‖A [xi + uij ]−A [xi]‖2 . (5)
In the sequel, we show that this term is effectively a Monte Carlo approximation to a Hessian-based measure of rugosity evaluated at the training data points.

heading: 3 A HESSIAN-BASED RUGOSITY MEASURE
text: To arrive at Ĉ(f) and link data augmentation to an explicit regularization penalty, we first define our new Hessian-based rugosity measure for deep networks with continuous activations. Then, we extend this definition to networks with piecewise-linear activations, and finally we describe its Monte Carlo approximation. We note that while deep networks are our focus, this measure of rugosity is more broadly applicable.

heading: 3.1 NETWORK WITH SMOOTH ACTIVATIONS
text: Let f : RD → R be the prediction function of a deep network whose nonlinear activation functions are smooth functions (e.g., sigmoid). For regression, we can take f as the mapping from the input to the output of the network. For classification, we can take f as the mapping from the input to one of the inputs of the final softmax operation. We assume that the training data points {xi}ni=1 lie close to a d-dimensional smooth manifoldM ⊆ RD. This assumption has been studied in an extensive literature on unsupervised learning (Tenenbaum et al., 2000; Belkin & Niyogi, 2003; Donoho & Grimes, 2003), and holds at least approximately for many practical datasets, including real world images.
For p ≥ 1, we define the following measure of rugosity:
Cp(f) , (∫ M ∥∥∥∇2(tan)f(x)∥∥∥p F dx )1/p (6)
where ∇2(tan)f(x) is the Hessian of f at x in the coordinates of d-dimensional affine space tangent to manifold at x ∈ M. This is an extension of the quadratic form from the Hessian eigenmaps approach of Donoho & Grimes (2003), which is equal to C22 (f).
From Donoho & Grimes (2003), we know that Cp(f) measures the average “curviness” of f over the manifoldM and that Cp(f) is zero if and only if f is an affine function onM. In the simplistic case of one-dimensional data and one-hidden-layer networks, Savarese et al. (2019) have related C1(f) to the sum of the squared Frobenius norms of the weight matrices.

heading: 3.2 NETWORK WITH CONTINUOUS PIECEWISE AFFINE ACTIVATIONS
text: We are primarily interested in deep networks constructed using piecewise affine activations (e.g., ReLU, leaky ReLU, absolute value). Since f is now piecewise affine and thus not continuously differentiable, the Hessian is not well defined in its usual form. However, using the formulation (1)
we can extend our rugosity measure to this case. Let ε > 0. For x not on the boundary of a VQ partition and u an arbitrary unit vector, we define
Hε(x)[u] , 1
ε (A[x+ εu]−A[x]) (7)
if u is on the d-dimensional affine space tangent to the data manifoldM at x and Hε(x)[u] = 0, otherwise. Note that A[x] is a (weak) gradient of f at x, and therefore this definition agrees with the finite element definition of the Hessian. For smooth f and ε → 0, this recovers the Hessian (Milne-Thomson, 2000; Jordan & Jordán, 1965). Thus, for a network with continuous, piecewise affine activations, we define
Cp,ε(f) , √ d (∫ M ( Eu ‖Hε(x)[u]‖22 )p/2 dx )1/p (8)
where u is uniform over the unit sphere. Comparing with (6), this definition is consistent with the definition of the distributional derivative for piecewise constant functions and can be seen as measuring the changes in the local slopes of the piecewise affine spline realized by the network.

heading: 3.3 MONTE CARLO APPROXIMATION
text: We can estimate Cp(f) using a Monte Carlo approximation C̃p(f) based on the training data xi. When the network has smooth activations, we have
C̃p(f) ,
( 1
n n∑ i=1 ∥∥∥∇2(tan)f(xi)∥∥∥p F )1/p . (9)
We can also apply the Monte Carlo method to estimate ‖∇2(tan)f(xi)‖ 2 F . If u ∈ Rd is chosen uniformly at random on the unit sphere, then for A ∈ Rd×d we have
E‖Au‖22 = E ∑ i,j uiuj(A TA)ij = 1 d ‖A‖2F . (10)
For smooth f , we have
∇2f(x)u = lim δ→0
1 δ [∇f(x+ δu)−∇f(x)] . (11)
Therefore, choosing uj uniformly at random with ‖uj‖2 = 1 on the d-dimensional subspace tangent to the manifold at x, plugging (10), (11) into (9) yields the following approximation for Cp(f) for small δ > 0
C̃p,δ(f) =  dp/2 nδpmp/2 n∑ i=1  m∑ j=1 ∥∥∇f(xi + δuj)−∇f(xi)∥∥22 p/2  1/p . (12)
When the network has continuous, piecewise affine activations, Monte Carlo approximation of Cp,ε(f) based on the training data xi yields
C̃p,ε(f) ,
( dp/2
n n∑ i=1 ( Eu ‖Hε(xi)[u]‖22 )p/2)1/p . (13)
For such a network, using (7) yields
C̃p,ε(f) =  dp/2 nεpmp/2 n∑ i=1  m∑ j=1 ∥∥A[xi + εuj ]−A[xi]∥∥22 p/2  1/p
(14)
as our approximation.

heading: 3.4 CONNECTION TO DATA AUGMENTATION
text: We can now identify the connection between the rugosity measure in (14) and data augmentation. Note that for p = 1, the quantity in (14) is very similar (up to normalization) to Ĉ(f) from Theorem 1. In fact, we obtain Ĉ(f) by replacing L2 norm with respect to the measure dP (u) in (13) with the L1 norm. We also note that in data augmentation methods that generate data by continuous deviations from the original image, such as translation, rotation, and color change, the vectors uij in (5) are such that xi + uij ∈ M. Thus, a sufficiently rich set of small augmentations yields a distribution on uij with very similar support to the uniform distribution over unit vectors on the subspace tangent to the manifold.
The above fact suggests that using Hessian-based rugosity measure as an explicit regularization term in training a neural network would improve the prediction accuracy of a deep network by having a similar effect as data augmentation through minimizing an upper bound on the augmented loss Laug. Remarkably, the converse is observed in our simulations. Using data augmentation in training deep networks decreases the rugosity of the prediction function.

heading: 4 EXPERIMENTS
text: We now explore, through a range of experiments, the connections between data augmentation and explicit rugosity regularization. First, we show that networks trained using data augmentation feature a significant decrease in rugosity that accompanies an increase in test accuracy. Second, we show that rugosity can be employed as an explicit regularization penalty in training sufficiently overparameterized networks at no cost to training accuracy. Although using this explicit regularization decreases the rugosity of the prediction function of the deep network, surprisingly, it does not yield an increase in test accuracy, in general. We discuss this observation further in Section 5.

heading: 4.1 DATA AUGMENTATION REDUCES RUGOSITY
text: In Table 1, we tabulate the rugosity C̃22,ε(f) as well as the Jacobian norm from Novak et al. (2018), a similar proposed complexity measure, computed as
J(f) = 1
n n∑ i=1 ‖A[xi]‖F , (15)
for residual network (ResNet) and convolutional neural network (CNN) architectures (described in Appendix A.2) on several image classification tasks, trained with and without data augmentation. The data augmentation used in this experiment is translation vertically and horizontally each by no more than 4 pixels, as well as flipping horizontally. In Figure 1, we plot the rugosity over training epochs for a subset of these architecture and dataset combinations.
We can make several observations from the results in Table 1. First, for the ResNet architecture, there is a clear reduction in rugosity when using data augmentation, while there is no such decrease in Jacobian norm (in fact, we sometimes observe an increase for both network types). We also observe that the CNN results in smaller C̃2 than the ResNet on both the training and test data. In fact, we observe that C̃2,train is almost zero for CNNs on all four datasets. This suggests that the prediction function is almost linear within ε of the training data. However, the rugosity is significantly higher when measured using the test data. We also note based on Figure 1 that while the CNN does not show much reduced rugosity at the end of training, there is a significant gap between the test rugosities with and without data augmentation during training. These peculiarities of purely convolutional networks are interesting properties that beg investigation in future work. Lastly, as one might expect, training the same network for a more complex task (e.g., classification with CIFAR100 vs. CIFAR10) results in higher rugosity in the learned network.

heading: 4.2 RUGOSITY AS AN EXPLICIT REGULARIZATION PENALTY
text: In Figure 2, we plot the rugosity as well as the training and test accuracies when training a network with and without using rugosity as an explicit regularization term. Specifically, we optimize the regularized lossL+λĈ(f), where Ĉ(f) is computed using using vertical and horizontal translations of up to 2 pixels. As we observe in these plots, the network can achieve almost zero training error even after adding the extra penalty term. Also, as expected, adding the regularization term decreases the rugosity of the obtained prediction function. However, somewhat surprisingly, minimizing the rugosity-penalized loss does not necessarily result in improved test accuracy. In fact, increasing the weight λ on the regularization term results in lower test accuracy even though the resulting network has zero training error. We discuss a few possible reasons for this phenomenon in Section 5. This observation points to the difference between data augmentation and explicit rugosity regularization. Although using data augmentation reduces rugosity, it also provides an improvement in test accuracy not achieved using rugosity alone as an explicit regularization.

heading: 5 DISCUSSION
text: Now that we have made the connection between data augmentation and rugosity regularization, the question remains of whether an explicit rugosity penalty in the optimization criterion is of value in its own right. Arguing in favor of such an approach, one may compare our Hessian-based rugosity measure with the notion of counting the “number of VQ regions” (Hanin & Rolnick, 2019) in a
ReLU network. One might argue that the rugosity measure provides a more useful quantification of the network output complexity, because it explicitly takes into account the changes in the output function across the VQ regions. For instance, consider the analysis of infinitely wide networks, which have been used to help understand the convergence properties and performance of deep networks (Lee et al., 2017; Mei et al., 2019; Arora et al., 2019). The number of VQ regions can be infinite in such networks; however, the rugosity measure can remain bounded.
For instance, consider the minimum-rugosity interpolator
f∗ , argmin f Cp,ε(f) s.t. g(f(xi)) = yi ∀i, (16)
where g(·) is the identity mapping in regression problems and the argmax(·) function in classification problems. Here, f∗ is the least rugous function that interpolate the training data.
In the classification setting, observe that, for any α > 0, g(f(x)) = g(αf(x)). Thus, for any function f , we can make Cp(f) and Cp,ε(f) arbitrarily small by rescaling f by an arbitrarily small α while still predicting the same labels for the training data. This is also true of other proposed complexity measures based on derivatives such as the Jacobian norm. In the binary classification setting, where f can have unidimensional output and g(·) = sgn(·), the effect is that f need only rise slightly above zero to predict the correct label for positive training examples and fall slightly below zero for negative training examples. Suppose that such a function were to perfectly classify all points on the training data manifold, but consider a test data point x + u, where x lies on the training data manifold M but u is some noise orthogonal to the tangent space of the manifold at x. Then by Taylor’s theorem, f(x + u) = f(x) +∇zf(z)>u for z = x + tu for some t ∈ [0, 1]. For a function f learned by a deep network, it is unlikely that ∇zf(z) will be exactly equal to zero, effectively changing the classification function from thresholding f(x) at 0 to thresholding f(x) at some small positive or negative value. For f that has been scaled to have very small output values, the result is that classification performance on noisy data will be poor.
The regression setting is not immune to problems. Savarese et al. (2019, Claim 5.2) showed the existence of a class of regression functions realizable by infinite-width deep networks that perfectly interpolate any finite set of training points. Functions in this class can have arbitrarily small Hessian norm integral—that is, C1(f)—and have a constant value almost everywhere, therefore generalizing very poorly. However, for sufficiently large p (dependent on d), this particular argument does not hold for the more general Cp(f). Further, realizable networks are of finite width and are heavily regularized in training, and so it is not clear whether such functions can be learned in practice. More thoroughly quantifying the shortcomings of using Cp to reason about deep networks as well as developing more useful measures of network complexity remains an exciting area for future work.

heading: ACKNOWLEDGMENTS
text: We thank [redacted] for helpful discussions on the rugosity measure in an anonymous personal communication.

heading: A APPENDIX
text: A.1 PROOF OF THEOREM 1
Let `ij , `(f(xi + uij), yi). Using (1), we have `ij = ` ( A[xi + uij ](xi + uij) + b[xi + uij ], yi ) (17)
= ` ( A[xi]xi + b[xi]
+ (A[xi + uij ]−A[xi])xi + (b[xi + uij ]− b[xi]) +A[xi + uij ]uij , yi ) . (18)
Therefore, for ˜̀ij , the first order approximation of `ij around `i = `(f(xi), yi) we obtain
˜̀ ij = `i + [ (A[xi + uij ]−A[xi])xi + (b[xi + uij ]− b[xi]) +A[xi + uij ]uij ]>∇f(xi)`(f(xi), yi). (19)
Under the conditions of the theorem, we obtain
˜̀ ij ≤ `i +RK2 ‖A[xi + uij ]−A[xi]‖2 +K2 |b[xi + uij ]− b[xi]|+ εK1K2. (20)
Summing up over xi and uij yields the following bound for L̃aug, the first order approximation of Laug for small ε,
L̃aug = 1 m+ 1 n∑ i=1 `i + m∑ j=1 ˜̀ ij  (21) ≤ L+ RK2
m+ 1 n∑ i=1 m∑ j=1 ‖A [xi + uij ]−A [xi]‖2
+ K2 m+ 1 n∑ i=1 m∑ j=1 |b [xi + uij ]− b [xi]|+ K1K2mnε m+ 1 (22)
which completes the proof.
A.2 EXPERIMENTAL DETAILS
The experiments in Figure 1 and Table 1 used the following parameters: batch size of 16, Adam optimizer with learning scheduled at 0.005 (initial), 0.0015 (epoch 100) and 0.001 (epoch 150). The default training/test split was used for all datasets. The validation set consists of 15% of the training set sampled randomly.
For the experiments in Figure 2, the number of training samples is 10, 000 sampled randomly from the training set. The test set still consists of the CIFAR10 test set of 10, 000 samples. The learning rate is 0.0001 and is divided by 3 at 75 epochs and again at 120 epochs. The images are renormalized to have zero mean and infinity norm of one.
A.2.1 CNN ARCHITECTURE
Conv2D(Number Filters=96, size=3x3, Leakiness=0.01))
Conv2D(Number Filters=96, size=3x3, Leakiness=0.01))
Conv2D(Number Filters=96, size=3x3, Leakiness=0.01))
Pool2D(2x2)
Conv2D(Number Filters=192, size=3x3, Leakiness=0.01))
Conv2D(Number Filters=192, size=3x3, Leakiness=0.01))
Conv2D(Number Filters=192, size=3x3, Leakiness=0.01))
Pool2D(2x2)
Conv2D(Number Filters=192, size=3x3, Leakiness=0.01))
Conv2D(Number Filters=192, size=1x1, Leakiness=0.01))
Conv2D(Number Filters=Number Classes, size=1x1, Leakiness=0.01))
GlobalPool2D(pool_type=’AVG’))
A.2.2 RESNET AND LARGE RESNET ARCHITECTURES
The ResNets follow the original architecture (Zagoruyko & Komodakis, 2016) with depth 2, width 1 for the ResNet and depth 4, width 2 for the Large ResNet.
A.2.3 IMPLEMENTATION NOTES
In a ReLU network with L layers, for a given x, A[x] can be computed via
A[x] = W(L) ( L∏ `=1 D(L−`)[x]W(L−`) ) , (23)
where W(`) is the weight matrix of the `-th layer and D(`)[x] is a diagonal matrix with( D(`)[x] ) rr
= 1 if the output of the r-th ReLU unit in the `-th layer is nonzero (when the unit is “active”) with x as input and ( D(`)[x] ) rr
= 0 if the ReLU ouput is zero. This enables us to use Ĉ(f) as a regularization penalty in training real networks.

Review summaries:
This paper shows (theorem 1) that data augmentation (DA) induces a reduction of rugsity on the loss function associated to the model. Here rugosity is defined as a measure of the curvature (2nd order) of the function. However, the two concepts seems to be different because the authors empirically show that directly reducing the rugosity of a network does not improve generalization (in contrast to DA).