Implicit Rugosity Regularization via Data Augmentation
Authors: Daniel LeJeune
Randall Balestriero
Hamid Javadi
Richard G. Baraniuk
Venue:  (2020)
Keywords: deep networks
implicit regularization
Hessian
rugosity
curviness
complexity

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.

Under review as a conference paper at ICLR 2020
IMPLICIT RUGOSITY REGULARIZATION VIA DATA AUGMENTATION
Anonymous authors Paper under double-blind review
ABSTRACT
Deep (neural) networks have been applied productively in a wide range of super- vised and unsupervised learning tasks. Unlike classical machine learning algo- rithms, deep networks typically operate in the overparameterized regime, where the number of parameters larger than the number of training data points. Con- sequently, 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 implicit regularization penalty a novel measure the rugosity or "roughness" based on the tangent Hessian of the function fit to the training data.
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 net- works has been demonstrated both in theory and practice (Cybenko 1989 Barron 1994 Tel Telgarsky
2015 Yarotsky 2017: Hanin & Sellke, 2017: Daubechies et al. 2019). In fact, it has been shown that deep networks even perfectly fit pure noise (Zhang et al. 2016). Surprisingly, highly over- parameterized deep wehworks-where the number of network parameters exceeds the number of training data points-can be trained for 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 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 explicit, as in the case of Tikhonov or & regularization (Krogh & Hertz 1992] [Bihhop] [995] Han et al., 2015 Bartlett et al., 2017). By contrast, we are becoming increasingly aware that vari- ous heuristic techniques -uchh as dropout (Baldi & Sadowski] 2013) Wager et al. 2013 Srivastava
et al. 2014), batch normalization (Ioffe & Ezegedy][211. Salimans & Kingma 2016 Bjorck al. 2018 and even stochastic gradient descent (Hardt et al. 2015 Bousquet & Elisseeft 2202 Yao al. 2007) that are used in deep neural networks provide implicir regularization, having effects that are not as transparent. In this work, we study another such heuristic data augmentation (Ben- gio et [011 Dao et al., (2018) Rajput al. 2019 Chen al., (019)) and show that it has 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 E RDD 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 high amount of rugosity. For example, classification problems, if we were to partition the feature space by class, then we might expect the set corrrespondigg 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 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 rule for learning predictors.

---

Under review as a conference paper at ICLR 2020
A key part of our analysis leverages new perspective on deep networks provided by Balestriero & Baraniuk 20188 b). Let fx() represent the mapping from the imput to output of deep network constructed using continuous, piecewise affine activations (e.g.. RcLU, leaky ReLU, absolute value). Such network partitions the input space IR. based on the activation pattern of the network's units (neurons). We call these partitions 2- C TR.D, the vector quantization (VQ) regions of the network, and for R we let 2(x) denote the VQ region to which belongs. Inside one VQ region, is simply an affine mapping. Consequently, f can be written as a continuous, piecewise affine operator
f(x) [x) xxxx) A b(x].
For the sake of brevity, we will use the simplified notation fxx A x b[x] in the sequel.
This framework enables us cleanly reason about our extension of the rugosity measure to piece- wise 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 new rugosity measure of function complexity that measures how much a function deviates from locally linear, with nontrivial extension of this measure to piecewise affine functions based finite differences. [C2] We formally connect the popular heuristic of data augmentation to an explicit rugosity regu- larization. [C3] We verify experimentally that data augmentation reduces rugosity. [C4] We exper- imentally assess the effect of explicit rugosity regularization in training deep networks.
Related work. Recently, Savarese et al. (2019) have shown that, for one- mnc-dimensional, one-hidden- layer ReLU networks, an 22 penalty on the weights (Tikhonov regularization) equivalent to a penalty the integral of the absolute value of the second derivative of the network output. More- over, several recent works (Belkin et al. [2018: 2019 Hastie et al., (019) have shown that in some linear and nonlinear inference problems, properly regularized overparameterized models can gen- eralize 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 kernel.
2
DATA AUGMENTATION
Data augmentation Wong et al. 2016, Perez Wang 2017) an oft-used yet poorly under- stood heuristic applied in learning the parameters of deep networks. The data augmentation pro- cedure augments the set of n training data points (x),, to (m + 1)n training data points
[[(, + U.j. }=) }" i=1 by applying transformations to the training data x; such that they con- tinue to lie on the data manifold MM. Example transformations applicd to images include translation, rotation, color changes, etc In such cases, Uy is the vector difference X;- X,, where xj is the translated/rotated image, and Ugo = O. Consider training a deep network with continuous, piecewise affine activations given the original training dataset {(x;, k by minimizing the loss
Σ {((()).))
where (((,-) is any convex loss function. After data augmentation, the loss can be written
m
Cang
aug
gaug A ((f(xx).
ex( . j=1
(3)
m
In the following result, we obtain an upper bound on the augmented loss, which consists of the sum of the non-augmented loss plus few terms pertaining to the local similarity of the output function around the training data.
"Common transformations also include flipping images, which is not a continuous operation; however, analysis here pertains primarily continuous transformation,, for which the vector differences uy are small.
2

---

Under review as a conference paper at ICLR 2020
Theorem 1. Consider deep network with continuous. piecewise affine activations and thus pre- diction function as in (I). Assume that ||x,|22 S R, and that f has Lipschitz constant K1; that is, ||A [x]] I K all Further. assume that the loss function has Lipschitz constant K2. Then,
for [ [ S &, Laus in 33 can be upper bounded by
RK2
a
m
Cang C
| x. + u,J - A |xi]l2
m
f=1
(4)
K2
Ki K2Kan m +1
[b[x; + ugy bxx]]]
+ o(e)-
+
5=1
We focus our attention on the second term of the right-hand side of the above inequality. Denote this term by
| + u.y - [x.]]l2-
(5)
In the sequel, we show that this term is effectively a Monte Carlo approximation Hessian-based measure of rugosity evaluated at the training data points.
3 A HESSIAN-BASED RUGOSITY MEASURE
To arrive at Č(J) and link data augmentation to 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 piccewise-liness activations, and finally describe its Monte Carlo approximation. We note that while deep networks are our focus, this measure rugosity is more broadly applicable.
3.1 NETWORK WITH SMOOTH ACTIVATIONS
Let R + 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 as the mapping from the input to one of the inputs the final softmax operation. We assume that the training data points {x lie close to d-dimensional smooth manifold M C TRP. This assumption has been studied in an extensive literature on unsupervised learning (Tenenbaum et al., 2000); Belkin & Niyogi] (2003] DDnoho & Grimes 2003), and holds at least approximately for many practical datasets, including real world images.
For 2 1, we define the following measure of rugosity:
1/p
Cp(f) & (imn f(x) dx
(6)
where V f(x is the Hessian of f at x in the coordinates d-dimensional affine space tangent to manifold at x E M. This is an extension of the quadratic form from the Hessian eigenmaps approach of Donoho & Grimes (2003), which is equal to Cf
From Donoho & Grimes (2003). we know that Cp) measures the average "curviness" of f over the manifold M and that Cf()) zero and only if f is an affine function on M. In the simplistic case of one-dimensional data and one- mee-hidden-laae layer networks, Savarese et al. (2019) have related
C (f)) the sum of the squared Frobenius norms of the weight matrices.
3.2 NETWORK WITH CONTINUOUS PIECEWISE AFFINE ACTIVATIONS
We 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
3

---

Under review as a conference paper at ICLR 2020
extend our rugosity measure to this case. Let 0. For not on the boundary of a VQ partition and u an arbitrary unit vector, we define
1 (Aix+ - A(x])
H (x)
is on the d-dimensional affine space tangent to the data manifold .M at x and (x j 0, otherwise. Note that A is (weak) gradient of at x, and therefore this definition agrees with the finite element definition of the Hessian. For smooth and e - 0, this recovers the Hessian MMile--Thomse 2000 Jordan & Jordán 1965). Thus, for network with continuous, piecewise affine activations, we define
(p) Va ( (E, 2/2
1/p
dx
where is uniform the unit sphere. Comparing with (6). this definition is consistent with the definition 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 Cp) using a Monte Carlo approximation Cp(s) based on the training data When the network has smooth activations, we have
1/P
|")
(f( -
V (fan)
(9)
We can also apply the Monte Carlo method estimate
|| || (
(tan) (tan)) (x.))
Rd is chosen
uniformly random the unit sphere, then for A E Rdxd we have
E Au =
ua u, (ATA) = = A
(10)
b2
For smooth f, we have
42 f2
lim
V + 5u) V
(11)
8-2
5
Therefore, choosing uy uniformly at random with ||u ||2 the d-dimensional subspace tangent to the manifold at x, plugging (10). (II) into yields the following approximation for Cp(() for small 8 >
8/2
1/p
dP/2
m
m
Cp,((f)=
f + 5uy) [xxx))
(12)
noPme/2
When the network has continuous, piccewise affine activations, Monte Carlo approximation of Cf.)(f) based on the training data x; yields
En | (x.((() p/2 1/p
dP/2
(p)
(13)
For such a network, using 7 yields
p/2
1/p
de/2
m
Čp.)(f)=
Σ
A |x + +uuy]
A[x;]]1
(14)
nsPmpl2
approximation.
4

---

Under review as a conference paper at ICLR 2020
Table 1: Data augmentation reduces rugosity in classification task with range of deep networks and datasets. We tabulate the converged values for C2 and J on the training and test data without and with data augmentation (denoted by DA). Missing values are omitted due to time constraints.
C2 C2
C
Jarain
Jees
Test accuracy (%)
CNN (MNIST)
1.57e-09
0.036
33.0
33.2
99.6
CNN+DA (MNIST)
1.56c-09
0.074
6.79
6.83
99.6
CNN (SVHN)
8.3c-10
0.022
67.0
63.3
95.6
CNN+DA (SVHN)
6.32c-10
0.019
108.5
103.2
95.5
CNN (CIFARIO)
1.54e-09
0.10
102.0
102.0
87.4
CNN+DA (CIFARIO)
2.58c-09
0.11
137.0
138.0
91.7
CNN (CIFARI00)
6.3e-08
1.51
61.1
CNN+DA (CIFARI00)
7.0e-08
1.40
68.3
ResNet (MNIST)
0.086
0.20
23.7
23.7
99.4
ResNct+DA (MNIST)
0.021
0.016
17.7
17.8
99.4
Large ResNet (MNIST)
0.061
0.079
99.5
Large ResNet+DA (MNIST)
0.019
0.025
99.5
ResNet (SVHIN)
0.08
0.09
48.3
47.8
93.9
ResNet+DA (SVHN)
0.01
0.01
56.5
56.5
94.1
ResNet (CIFAR 10)
0.43
0.50
105.0
105.4
84.9
ResNet+DA (CIFARIO)
0.10
0.12
107.3
107.8
91.0
ResNet (CIFAR 100)
4.32
4.39
49.3
ResNet+DA (CIFAR
1.08
1.14
64.5
3.4 CONNECTION TO DATA AUGMENTATION
We can now identify the connection between the rugosity measure (4) and data augmentation. Note that for p 1, the quantity in (14) is very similar (up to normalization) to Ō(f) from The- orem 1 In fact, we obtain C(f) by replacing 2 norm with respect to the measure dl in (L3 with the L norm. We also note that in data augmentation methods that generate data by continuous deviations from the original image. such translation, rotation, and color change, the vectors u. in (5) are such that x; + Ui E .M. Thus, a sufficiently rich set of small augmentations yields a distribution Uy with very similar support to the uniform distribution subspace tangent to the manifold.
unit vectors the
The above fact suggests that using dessiannbasse rugosity measure as explicit regularization term in training neural network would improve the prediction accuracy of a deep network by having similar effect as data augmentation through minimizing an upper bound on the augmented loss Lang 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 range of experiments, the connections between data augmentation and explicit rugosity regularization. First, we show that networks trained using data augmentation fea- ture 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 cost to training accuracy. Although using this explicit regulariza- tion decreases the rugosity of the prediction function the deep network, surprisingly, it does not yield an increase in test accuracy, in general. We discuss this observation further in Section 5
5

---

Under review as a conference paper at ICLR 2020
C2
on training data
CIFARIO ResNet
C2 on test data
CIFARIO - ResNet
0.5
My www.harruun
0.6
0.4
0.3
Min M
0.2
0.2
0.1
0.0
0.0
1000
2000
3000
4000
5000
25
125
150
learning opochs
learning epochs
2 on training data
SVHN ResNet
22
test data
SVHN - ResNet
0,20
0.15
0.10
0.04
0.05
0.00
3500
learning spochs
learning epachs
C2
training data
CIFARI00 ResNet
C2
test data
CIFARIO0
ResNet
M www.iaaaaaaaaannnn. /
3-
4-
2-
2
0-
2000
125
175
learning epochs
learning epochs
C2
training data
CIFAR100 CNN
C data
CIFAR100 CNN
1.25
1.5
0.50
0.5
6
500
1000
15.00
2000
25.00
3000
20
40
60
60
100
learning epochs
learning epochs
Figure 1: Data augmentation reduces rugosity. The blue and black curves correspond to experiments with and without data augmentation, respectively.
4.1 DATA AUGMENTATION REDUCES RUGOSITY
In Table we tabulate the rugosity (f) as well as the Jacobian norm from Novak et 2018
similar proposed complexity measure, computed
1 n Σ |Axx]]le,
J(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 no more than 4 pixels, as well as flipping horizontally. In Figure I we plot the rugosity over training epochs for subset of these architecture and dataset combinations.

---

Under review as a conference paper at ICLR 2020
Ö on training data - ResNet
Ö on test data - ResNet
6-
40
2.0
2.0
0.003
5.021
2-
0.01
0.01
0.1
01
100
120
20
80
120
140
Training accuracy ResNet
Test accuracy ResNet.
0.65
0.60
0.6
0.0
0.55
0.0
0.001
0.021
0.01
0.01
0.1
0.45
140
120
Figure 2: 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 A. We observe that rugosity can used as an explicit regularization penalty at no cost to training accuracy but there are no test accuracy gains.
We can make several observations from the results in Table [ First, for the ResNet architecture, there is clear reduction in rugosity when using data augmentation, while there no such decrease in Jacobian norn (in fact, we sometimes observe an increase for both network types). We also ob- serve that the CNN results in smaller C2 than the ResNet both the training and test data. In fact, observe that C2 is almost zero for CNNs on all four datasets. This suggests that the pre- diction function is almost linear within E of the training data. However, the rugosity is significantly higher when measured using the test data. We also note based on Figure[ttha while the CNN does not show much reduced rugosity at the end of training, there is significant gap between the test rugosities with and without data augmentation during training. These peculiarities of purely con- volutional networks are interesting properties that beg investigation in future work. Lastly, as one might expect, training the same network for 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 network with and without using rugosity as an explicit regularization term. Specifically, we optimize the regularized loss C+)C(ff, where C(f) is computed using using vertical and horizontal translations of up to pixels. As we observe in these plots, the network can achieve almost zero training error after adding the extra penalty term. Also, expected, adding the regularization term decreases the rugosity of the obtained prediction function. However, somewhat surprisingly, minimizing the 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 few possible reasons for this phenomenon in Section This observation points to the difference between data augmentation and explicit rugosity regularization. Although using data augmentation reduces rugosity, also provides an improvement in test accuracy not achieved using rugosity alone as an explicit regularization.
DISCUSSION
Now that we have made the connection between data augmentation and rugosity regularization, the question remains of whether 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
7

---

Under review as a conference paper at ICLR 2020
ReLU network. One might argue that the rugosity measure provides 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 net- works (Lee al., 2017 Mei al., 2019; Arora et al., 2019). The number of VQ regions can be infinite in such networks; however, the rugosity measure can remain bounded.
useful quantification
For instance, consider the minimum-rugositty interpolator
arg min (f.)(f) s.t. ((f(x:)) - yı Vi,
(16)
where g(-) is the identity mapping in regression problems and the arg max(-) function in classifica- tion problems. Here, I is the least rugous function that interpolate the training data.
In the classification setting, observe that, for any a > O, g(f(x)) = ((a((x)). Thus, for any function f.
make Cp(f) and (f= arbitrarily small by rescaling f by 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 the Jacobian norm. In the binary classification setting, where f can have unidimensional output and g(-) sgu(-), 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 function were to perfectly classify all points on the training data manifold, but consider test data point x + u, where x lies on the training data manifold M but is some noise orthogonal to the tangent space of the manifold at x. Then by Taylor's theorem, f(x + u) = f(x) + Vzf(z) Tu u for z = x + tu for some E [o, 1]. For function learned by deep network, it is unlikely that vzf(z) will be exactly equal to zero, effectively changing the classification function from thresholding fxx at 0 to thresholding fxx at some small positive 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. Saaareee 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 of training points. Functions in this class can have arbitrarily small Hessian norm integral- is, (f)) 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 (f).) Further, realizable networks are of finite width and are heavily regularized in training, and so is not clear whether such functions can be learned 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.
ACKNOWLEDGMENTS
We thank [redacted] for helpful discussions on the rugosity measure in an anonymous personal communication.
REFERENCES
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, and Ruosong Wang. On 1955, 2019.
exact computation with an infinitely wide neural net. arXiv preprint
Pierre Baldi and Peter J Sadowski. Understanding dropout. In Advances in neural information processing systems, pp. 2814-2822, 2013.
Randall Balestriero and Richard Baraniuk. Mad max: Affine spline insights into deep learning.
arXiv preprint leee:080500011 2018a.
Randall Balestriero and Richard G. Baraniuk. A spline theory of deep networks. In International Conference on Machine Learning, pp. 383-3933 2018b.
Andrew R Barron.
Approximation and estimation bounds for artificial neural networks. Machine learning, 15-1)3 1994.
8

---

Under review as a conference paper at ICLR 2020
Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky. Spectraaly-normalizee neural networks. In Advances in Neural Information Processing Systems, pp. 6240-6244 2017.
normalized margin bounds for
Mikhail Belkin and Partha Niyogi. Laplacian eigemmaps for dimensionality reduction and data rep-
resentation. Neural Computation, 15(6):1373-139, 2003. doi: 10. 10.16228997760032170077
URL BRRhhttp::// /ttp:///oiiio/ htt.:pp:///oi.og/11........ /ttp://..1116//0996633222222
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine learning and the bias-variance trade-off. arXiv preprint arXiv: 1eXXvv/8/2.1. 18/2.11118 2018.
Mikhail Belkin, Daniel Hsu, and Ji Xu. Two models of double descent for weak features. arXiv preprint arXiv:1903.07571 2019.
Yoshua Bengio, Frédéric Bastien, Arnaud Bergeron, Nicolas Boulanger-Lewandowskii Thomas Breuel, Youssouf Chherawala, Moustapha Cisse, Myriam Côté, Dumitru Erhan, Jeremy Eustache, et al. Deep learner benefit more from out-of-distribution examples. In Proceedings of the Four- teenth International Conference on Artificial Intelligence and Statistics, pp. 164-172, 2011.
Christopher M Bishop. Regularization and complexity control in feed-forward networks. 1995.
Nils Bjorck, Carla P Gomes, Bart Selman, and Kilian Q Weinberger. Understanding batch normal- ization. In Advances in Neural Information Processing Systems, pp. 7694-7705, 2018
Olivier Bousquet and André Elisseeff. Stability and generalization. Journal of machine learning research, 2(Mar):499-553 526,, 2002.
Shuxiao Chen, Edgar Dobriban, and Jane H Lee. Invariance reduces variance: Understanding data augmentation in deep learning and beyond. arXiv preprint arXiv: 19905 2019.
George Cybenko. Approximation by superpositions a sigmoidal function. Mathematics control, signals and systems, 2(4))303-31 1989.
Tri Dao, Albert Gu, Alexander Ratner, Virginia Smith, Christopher De Sa, and Christopher Ré. A kernel theory of modern data augmentation. arXiv preprint arXiv: /803. 1803.06084, 2018.
Ingrid Daubechies, Ronald DeVore, Simon Foucart, Boris Hanin, and Guergana Petrova. Nonlinear approximation and (deep) relu networks. arXiv preprint arXiv: 2019.
David I. Donoho and Carrie Grimes. Hessian eigenmaps: Locally linear embedding techniques for high-dimensional data. Proceedings of the National Academy of Sciences, 100(10)55511-559, 2003.
Song Han, Jeff Pool, John Tran, and William Dally. Learning both weights and connections for efficient neural network. In Advances in neural information processing systems, pp. 1135-1143, 2015.
Boris Hanin and David Rolnick. Complexity of linear regions in deep networks. arXiv preprint 1rXiv:/901.00022 2019.
Boris Hanin and Mark Sellke. Approximating continuous functions by relu nets of minimal width. arXiv preprint arXiv:
2017.
Moritz Hardt, Benjamin Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. arXiv preprint 109.024500 2015.
Trevor Hastic, Andrea Montanari, Saharon Rosset, and Ryan J Tibshirani. Surprises in high-
dimensional ridgeless least squares interpolation. arXiv preprint arXiv:1903.08560 2019.
Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. arXiv preprint arXiv:1502.03167. 2015.
Charles Jordan and Károly Jordán. Calculus of finite differences, volume 33. American Mathemati- cal Soc., 1965.

---

Under review as a conference paper at ICLR 2020
Anders Krogh and John A Hertz. A simple weight decay improve generalization. In Advances in neural information processing systems, pp. 950-957, 1992.
Jaehoon Lee, Yasaman Bahri, Roman Novak, Samuel S Schoenholz, Jeffrey Pennington, and Jascha Sohl-Dickstein. Deep neural networks as gaussian processes. arXiv preprint 1rxXi:1711.00100 2017.
Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Mean-field theory of two-layer neural networks: dimension-free bounds and kemee limit. arXiv preprint arXiv:1902006015 2019.
Louis Melville Tilmm-Thomson. The calculus of finite differences. American Mathematical Soc., 2000.
Roman Novak, Yasaman Bahri, Daniel A Abolafia, Jeffrey Pennington, and Jascha Sohl- Dickstein. Sensitivity and generalization in neural networks: an empirical study. arXiv preprint 180.::8000.0760. 2018.
Luis Perez and Jason Wang. The effectiveness of data augmentation image classification using deep learning. arXiv preprini arXiv: (712.0v7712046111 2017.
Shashank Rajput, Zhili Feng, Zachary Charles, Po-Ling Loh, and Dimitris Papailiopoolos. Does data augmentation lead to positive margin? arXiv preprint arXiv:1905.03177 2019.
Salah Rifai, Grégoire Mesnil, Pascal Vincent, Xavier Muller, Yoshua Bengio, Yann Dauphin, and Xavier Glorot. Higher order contractive auto-encoder. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 645-660. Springer, 2011.
Tim Salimans and Durk P Kingma. Weight normalization: A simple reparameterization to accelerate training of deep neural networks. In Advances in Neural Information Processing Systems, pp. 901-909, 2016.
Pedro Savarese, Itay Evron, Daniel Soudry, and Nathan Srebro. How do infinite width bounded norm networks look in function space? arXiv preprint 190.05500, 2019.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: a simple way prevent neural networks from overfitting. The journal of machine learning research, 15(1):1929-195, 2014.
Matus Telgarsky. Representation benefits of deep feedforward networks. arXiv:
arXiv preprint
2015.
Joshua Tenenbaum, Vin De Silva, and John C Langford. A global geometric framework for nonlinear dimensionality reduction. science, 29065500): 2323, 2000.
Stefan Wager, Sida Wang, and Percy S Liang. Dropout training as adaptive regularization. In Advances in neural information processing systems, pp. 351-359, 2013.
Sebastien C Wong, Adam Gatt, Victor Stamatescu, and Mark D McDonnell. Understanding data augmentation for classification: When to warp? In 2016 international conference on digital image computing: techniques and applications (DICTA), pp. 1-6. IEEE, 2016.
Yuan Yao, Lorenzo Rosasco, and Andrea Caponnetto. On early stopping in gradient descent learn- ing. Constructive Approximation, 26(2):289-33) 2007.
Dmitry Yarotsky. Error bounds for approximations with deep relu networks. Neural Nenworks, 94: 103-114, 2017.
Sergey Zagoruyko and Nikos Komodakis. arXiv:1605.07146, 2016.
Wide residual networks.
arXiv preprint
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint 16.v:3361..03300 2016.
10

---

Under review as a conference paper at ICLR 2020
A APPENDIX
A.1 PROOF OF THEOREM
Let by & [(f(xx + u.y) v:). Using T have
Li = [A[x + u (x: + Uiy) + b(x; + u.yl. 34)
(17)
= =[(A(x)) x; + b[x:]
+ (A[x; + u.y Axx + (b(x; + ugl - b(x,]) + A + uyyl 81).
(18)
Therefore, for Egg. the first order approximation of byy around & = [(f(x:)) 34) we obtain
bg = + [AAx + uzy xxx,)xx + (6(x; + u.y b(x,)) + A(x: + u.y u V ((x))
(19)
Under the conditions of the theorem, obtain
Egj S l + RK2 |||[
u:y] A[xi]l2 + K2 16[x; + u,yl b(xi|| + kKiK2.
(20)
Summing over x; and U,y yields the following bound for Zaaus, the first order approximation of La for small E,
aug
Eij
(21)
+ 1 i=1
I C + RK₂
n
A x + uzy
[x]]ll
m +
i=1 j=1
m K₂ Σ Σ
K2mae
+ m +
bb |x Uzyl - bxx]] + m
(22)
==
which completes the proof.
A.2 EXPERIMENTAL DETAILS
The experiments Figure T and Table 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 CIFARIO 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 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=O 01))
Conv2D (Number Pilters=96, size=3x3, Leakiness=O 01))
Pool2D (2x2)
Conv2D (Number Filters=192, size=3x3, Leakiness=0.0m
Conv2D (Number Pilters=192, size=3x3, Leakiness=0, 01))
11

---

Under review as a conference paper at ICLR 2020
Conv2D (Number Filters=192, size=3x3, Leakiness=0.01)
Pool2D (2x2)
Conv2D (Number Filters=192 92, size=3x3, Leakiness=O. .1))
Conv2D (Number Filters-192, size-1x1, Leakiress-O.00 0101
Conv2D (Number Pilters=Number Classes, size=1x1, Leakiness=0.01)
GlobalPool2D spool_type='Ae
A.2.2 RESNET AND LARGE RESNET ARCHITECTURES
The ResNets follow the original architecture (Zaoruykoo & Komodakis, 2016) with depth 2, width for the ResNet and depth 4, width 2 for the Large ResNet.
A.2.3 IMPLEMENTATION NOTES
In ReLU network with L layers, for a given x, A[x] can be computed via
i [I
A w())
(23)
where ((!) is the weight matrix of the b-th layer and [( a diagonal matrix with (x)) the output of the r-th ReLU unit in the l-th layer nonzero (when the unit 0 if the ReLU ouput is zero. This enables to C()) as regularization penalty in training real networks.
is "active") with input and (D(*)x))
12


Reviews:
[{"review_id": "rJlfN3TjtS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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).\n\nI 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.\n\nThe paper is well written and easy to follow, however I found the actual contribution limited because:\n- 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.\n- 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.\n \nAdditional Comments:\n- 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.\n- The entire paper seems written with the idea of using rugosity as a surrogate of DA, but at the end it does not work\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "Syl3tBeAtH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper aims to explain the regularization and generalization effects of data augmentation commonly used in training Neural Networks. \nIt suggests a novel measure of \"rugosity\" that measures a function's diversion from being locally linear and explores the connection between data augmentation and the decrease in rugosity.\nIt further suggests the explicit use of rugosity measure as a regularization during training to replace need for data augmentation.\nThe paper is very well written and both the positive and negative findings are clearly presented and discussed. \nCons:\n- The main contribution of the paper, in my view, is the suggestion of using rugosity as a explicit regularization for training Neural Networks. Nevertheless, all the results in the paper show a negative impact of this on the test accuracy which is contradicting to the proposition. \nThis result has been discussed in section 5 but without much evidence to the explanations mentioned. The connection is very interesting but I believe further work is needed to explain those negative results on test accuracy. \n- The difference in finding (Table 1) between the CNN and ResNet networks can be more discussed. \n- Additional tasks (like regression) or even toy examples can be useful in further explaining the connection between rugosity and generalization to test data. \n ", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "HJgBtISK5r", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper shows that a penalty term called rugosity captures the implicit regularization effect of deep neural networks with ReLU (and piecewise affine in general) activation. Roughly, rugosity measures how far the function parametrized as a deep network deviates from a locally linear function. \n\nThe paper starts by showing that the amount of training loss increased from adding data augmentation is upper bounded in terms of (roughly) a Monte Carlo approximate to a Hessian based measure of rugosity. It then formally derives this measure of rugosity for networks with continuous piecewise affine activations. Finally, experimental evaluation for classification tasks on MNIST, SVHN and CIFAR shows that data augmentation indeed reduces the rogusity by a significant amount particularly when using the ResNet structure. A somehow surprising message is, however, that if one imposes explicit regularization with rugosity in lieu of data augmentation, then the better generalization usually seen from data augmentation no longer presents, though one does get a network with smaller rugosity.\n\nComments:\n\nIt is quite interesting to see that the rugosity measure proposed in the paper captures at least some aspects of the implicit regularization effect of data augmentation both in terms of theory (i.e. Theorem 1) and practical observations. My feeling is that rugosity is mostly a measure of the smoothness of the function parametrized by the neural network. From that perspective, how is the rugosity as a smoothness measurement for neural networks with piecewise affine activations different from the Lipschitz constant for general neural networks? My guess is that data augmentation also decreases the Lipschitz constant of a neural network near the training data points, but regardless of whether this is true or not, it is not clear if and how rugosity is better than Lipschitz constant for characterizing the implicit regularization of data augmentation. \n\nIn addition, there have been many recent studies on showing that gradient penalty / Lipschitz regularization are useful for achieving better generalization and adversarial robustness, see e.g. [a,b,c]. The results in this paper on showing that regularizing rugosity does not improve accuracy seem to contradict with the conclusion of these prior studies. It is unclear to me whether this is caused by insufficient experimentation or if there is any fundamental difference between rugosity and Lipschitz regularization that I am missing.\n\n[a] Finlay et al., Lipschitz regularized deep neural networks generalize and are adversarially robust\n[b] Gouk et al., Regularisation of Neural Networks by Enforcing Lipschitz Continuity\n[c] Thanh-Tung et al., Improving generalization and stability of GANs\n\n\n\n\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper aims to study the effect of data augmentation of generalization performance. The authors put forth a measure of rugosity or "roughness" based on the tangent Hessian of the function reminiscent of a classic result by Donoho et. al. The authors show that this measure changes in tandem with how much data augmentation helps. The reviewers and I concur that the rugosity measure is interesting. However, as the reviewer mention the main draw back of this paper is that this measure of rugosity when made explicit does not improve generalization. This is the main draw back of the paper. I agree with the authors that this measure is interesting in itself. However, I think in its current form the paper is not ready for prime time and recommend rejection. That said, I believe this paper has a lot of potential and recommend the authors to rewrite and carry out more careful experiments for a future submission.
Decision: Reject