Title: IMPLICIT RUGOSITY REGULARIZATION VIA DATA AUGMENTATION

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.

1. INTRODUCTION:

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 ∈ R D lie on a low-dimensional manifold M 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 R D based on the activation pattern of the network's units (neurons). We call these partitions Q j ⊂ R D , the vector quantization (VQ) regions of the network, and for x ∈ R D 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) = A Q(x) x + b Q(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.

2. DATA AUGMENTATION:

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 {(x i , y i )}

n i=1 to (m + 1)n training data points {(x i + u ij , y i )} m j=0 n i=1

by applying transformations to the training data x i such that they continue to lie on the data manifold M. Example transformations applied to images include translation, rotation, color changes, etc.1 In such cases, u ij is the vector difference x j -x i , where x j is the translated/rotated image, and u i0 = 0. Consider training a deep network with continuous, piecewise affine activations given the original training dataset {(x i , y i )} n i=1 by minimizing the loss

EQUATION

where (•, •) is any convex loss function. After data augmentation, the loss can be written as

L aug = 1 m + 1 n i=1 aug i , aug i (f (x i ), y i ) + m j=1 (f (x i + u ij ) , y i ) .

(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.

Theorem 1. Consider a deep network with continuous, piecewise affine activations and thus prediction function f as in (1). Assume that x i 2 ≤ R, and that f has Lipschitz constant K 1 ; that is, A[x] 2 ≤ K 1 , for all x. Further, assume that the loss function has Lipschitz constant K 2 . Then, for u ij 2 ≤ ε, L aug in (3) can be upper bounded by

EQUATION

We focus our attention on the second term of the right-hand side of the above inequality. Denote this term by

EQUATION

)

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.

3. A HESSIAN-BASED RUGOSITY MEASURE:

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.

3.1. NETWORK WITH SMOOTH ACTIVATIONS:

Let f : R D → 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 {x i } n i=1 lie close to a d-dimensional smooth manifold M ⊆ R D . 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:

C p (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 C 2 2 (f ). From Donoho & Grimes (2003), we know that C p (f ) measures the average "curviness" of f over the manifold M and that C p (f ) is zero if and only if f is an affine function on M. In the simplistic case of one-dimensional data and one-hidden-layer networks, Savarese et al. (2019) have related C 1 (f ) to the sum of the squared Frobenius norms of the weight matrices.

3.2. NETWORK WITH CONTINUOUS PIECEWISE AFFINE ACTIVATIONS:

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

EQUATION

if u is on the d-dimensional affine space tangent to the data manifold M 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 & Jordán, 1965) . Thus, for a network with continuous, piecewise affine activations, we define

EQUATION

)

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.

3.3. MONTE CARLO APPROXIMATION:

We can estimate C p (f ) using a Monte Carlo approximation C p (f ) based on the training data x i .

When the network has smooth activations, we have

EQUATION

We can also apply the Monte Carlo method to estimate ∇ 2 (tan) f

(x i ) 2 F . If u ∈ R d

is chosen uniformly at random on the unit sphere, then for A ∈ R d×d we have

EQUATION

)

For smooth f , we have

EQUATION

Therefore, choosing u j uniformly at random with u j 2 = 1 on the d-dimensional subspace tangent to the manifold at x, plugging (10), ( 11) into (9) yields the following approximation for C p (f ) for small δ > 0

EQUATION

)

When the network has continuous, piecewise affine activations, Monte Carlo approximation of C p,ε (f ) based on the training data x i yields

EQUATION

)

For such a network, using (7) yields

C p,ε (f ) =    d p/2 nε p m p/2 n i=1   m j=1 A[x i + εu j ] -A[x i ] 2 2   p/2    1/p (14)

as our approximation. 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 L 2 norm with respect to the measure dP (u) in ( 13) with the L 1 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 u ij in (5) are such that x i + u ij ∈ M. Thus, a sufficiently rich set of small augmentations yields a distribution on u ij 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 L aug . Remarkably, the converse is observed in our simulations. Using data augmentation in training deep networks decreases the rugosity of the prediction function.

4. EXPERIMENTS:

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. 

4.1. DATA AUGMENTATION REDUCES RUGOSITY:

In Table 1 , we tabulate the rugosity C 2 2,ε (f ) as well as the Jacobian norm from Novak et al. ( 2018), a similar proposed complexity measure, computed as

EQUATION

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 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.

4.2. RUGOSITY AS AN EXPLICIT REGULARIZATION PENALTY:

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 loss L+λ 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.

5. DISCUSSION:

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:

Under review as a conference paper at ICLR 2020 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

EQUATION

where g(•) is the identity mapping in regression problems and the arg max(•) 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 C p (f ) and C p,ε (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) + ∇ z f (z) u for z = x + tu for some t ∈ [0, 1].

For a function f learned by a deep network, it is unlikely that ∇ z f (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, C 1 (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 C p (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 C p to reason about deep networks as well as developing more useful measures of network complexity remains an exciting area for future work.

:

Common 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.

Figures and Tables:

Figure 1: Data augmentation reduces rugosity. The blue and black curves correspond to experiments with and without data augmentation, respectively.

Figure2: Explicit rugosity regularization. We plot the rugosity and accuracy on the training and test data over training time for several different values of the penalty weighting factor λ. We observe that rugosity can be used as an explicit regularization penalty at no cost to training accuracy but there are no test accuracy gains.

Data augmentation reduces rugosity in a classification task with a range of deep networks and datasets. We tabulate the converged values for C 2 2 and J on the training and test data without and with data augmentation (denoted by DA). Missing values are omitted due to time constraints.

Table content: <table><tr><td/><td>C 2 2,train</td><td>C 2 2,test</td><td>Jtrain</td><td>Jtest</td><td>Test accuracy (%)</td></tr><tr><td>CNN (MNIST)</td><td>1.57e-09</td><td>0.036</td><td>33.0</td><td>33.2</td><td>99.6</td></tr><tr><td>CNN+DA (MNIST)</td><td>1.56e-09</td><td>0.074</td><td>6.79</td><td>6.83</td><td>99.6</td></tr><tr><td>CNN (SVHN)</td><td>8.3e-10</td><td>0.022</td><td>67.0</td><td>63.3</td><td>95.6</td></tr><tr><td>CNN+DA (SVHN)</td><td>6.32e-10</td><td>0.019</td><td colspan="2">108.5 103.2</td><td>95.5</td></tr><tr><td>CNN (CIFAR10)</td><td>1.54e-09</td><td>0.10</td><td colspan="2">102.0 102.0</td><td>87.4</td></tr><tr><td>CNN+DA (CIFAR10)</td><td>2.58e-09</td><td>0.11</td><td colspan="2">137.0 138.0</td><td>91.7</td></tr><tr><td>CNN (CIFAR100)</td><td>6.3e-08</td><td>1.51</td><td>-</td><td>-</td><td>61.1</td></tr><tr><td>CNN+DA (CIFAR100)</td><td>7.0e-08</td><td>1.40</td><td>-</td><td>-</td><td>68.3</td></tr><tr><td>ResNet (MNIST)</td><td>0.086</td><td>0.20</td><td>23.7</td><td>23.7</td><td>99.4</td></tr><tr><td>ResNet+DA (MNIST)</td><td>0.021</td><td>0.016</td><td>17.7</td><td>17.8</td><td>99.4</td></tr><tr><td>Large ResNet (MNIST)</td><td>0.061</td><td>0.079</td><td>-</td><td>-</td><td>99.5</td></tr><tr><td>Large ResNet+DA (MNIST)</td><td>0.019</td><td>0.025</td><td>-</td><td>-</td><td>99.5</td></tr><tr><td>ResNet (SVHN)</td><td>0.08</td><td>0.09</td><td>48.3</td><td>47.8</td><td>93.9</td></tr><tr><td>ResNet+DA (SVHN)</td><td>0.01</td><td>0.01</td><td>56.5</td><td>56.5</td><td>94.1</td></tr><tr><td>ResNet (CIFAR10)</td><td>0.43</td><td>0.50</td><td colspan="2">105.0 105.4</td><td>84.9</td></tr><tr><td>ResNet+DA (CIFAR10)</td><td>0.10</td><td>0.12</td><td colspan="2">107.3 107.8</td><td>91.0</td></tr><tr><td>ResNet (CIFAR100)</td><td>4.32</td><td>4.39</td><td>-</td><td>-</td><td>49.3</td></tr><tr><td>ResNet+DA (CIFAR100)</td><td>1.08</td><td>1.14</td><td>-</td><td>-</td><td>64.5</td></tr><tr><td colspan="2">3.4 CONNECTION TO DATA AUGMENTATION</td><td/><td/><td/><td/></tr></table>

Peer review (iclr2020):
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). I lean to reject this paper because the contributions, even if interesting, do not lead to any new understanding of the topic. More in detail, data augmentation improves the generalization on deep learning models. This paper shows that DA induces rugosity (theorem 1), but rugosity does not improve generalization (empirically). Thus, rugosity is not responsible for generalization, which is the interesting property that we care about. The paper is well written and easy to follow, however I found the actual contribution limited because: - The definition of rugosity is an extension of (Donoho & Grimes (2003)) in which the extension is not really improving anything or used anywhere in the paper. - The Hessian-based rugosity analysis of DA is correct, but it does not help to understand the generalization performance or any other useful property of DA. Additional Comments: - In 3.4 second paragraph the authors suggest that reducing rugosity can improve generalization as DA, but later we see that this is not the case. - The entire paper seems written with the idea of using rugosity as a surrogate of DA, but at the end it does not work