Data-Efficient Augmentation for Training Neural Networks
Authors: Tian Yu Liu
Baharan Mirzasoleiman
Venue: NeurIPS 2022 Accept (2022)
Keywords: Data Augmentation
Deep Learning
Coresets

Abstract: Data augmentation is essential to achieve state-of-the-art performance in many deep learning applications. However, the most effective augmentation techniques become computationally prohibitive for even medium-sized datasets. To address this, we propose a rigorous technique to select subsets of data points that when augmented, closely capture the training dynamics of full data augmentation. We first show that data augmentation, modeled as additive perturbations, improves learning and generalization by relatively enlarging and perturbing the smaller singular values of the network Jacobian, while preserving its prominent directions. This prevents overfitting and enhances learning the harder to learn information. Then, we propose a framework to iteratively extract small subsets of training data that when augmented, closely capture the alignment of the fully augmented Jacobian with labels/residuals. We prove that stochastic gradient descent applied to the augmented subsets found by our approach has similar training dynamics to that of fully augmented data. Our experiments demonstrate that our method achieves 6.3x speedup on CIFAR10 and 2.2x speedup on SVHN, and outperforms the baselines by up to 10\% across various subset sizes. Similarly, on TinyImageNet and ImageNet, our method beats the baselines by up to 8%, while achieving up to 3.3x speedup across various subset sizes. Finally, training on and augmenting 50% subsets using our method on a version of CIFAR10 corrupted with label noise even outperforms using the full dataset.

Data-Efficient Augmentation for Training Neural Networks
Tian Yu Liu Department of Computer Science University of California, Los Angeles tianyu@cs ucla. edu
Baharan Mirzasoleiman Department of Computer Science University of California, Los Angeles baharan&cs. .ucla.uccaa..........aa...aa edu
Abstract
Data augmentation is essential to achieve state-of-the-art performance in many deep learning applications. However, the most effective augmentation techniques become computationally prohibitive for even medium-sized datasets. To address this, we propose a rigorous technique to select subsets of data points that when augmented, closely capture the training dynamics of full data augmentation. We first show that data augmentation, modeled as additive perturbations, improves learning and generalization by relatively enlarging and perturbing the smaller singular values of the network Jacobian, while preserving its prominent directions. This prevents overfitting and enhances learning the harder to learn information. Then, we propose a framework to iteratively extract small subsets of training data that when augmented, closely capture the alignment of the fully augmented Jacobian with fabels/residuals. We prove that stochastic gradient descent applied the augmented subsets found by approach has similar training dynamics to that of fully augmented data. Our experiments demonstrate that our method achieves 6.3x speedup on CIFARIO and 2.2x speedup on SVHN, and outperforms the baselines by to 10% across various subset sizes. Similarly, on ImngNeeeNet and ImageNet, our method beats the baselines by up to 8%, while achieving up 3.3x speedup across various subset sizes. Finally, training on and augmenting 50% subsets using our method on version of CIFAR10 corrupted with label noise even outperforms using the full dataset.
1 Introduction
Standard (weak) data augmentation transforms the training examples with c.g. rotations or crops for images, and trains the transformed examples in place of the original training data. While weak augmentation is effective and computationally inexpensive, strong data augmentation (in addition to weak augmentation) is a key component in achieving nearly all state-of-the-ar results in deep learning applications [31. However, strong data augmentation techniques often increase the training time by orders of magnitude. First, they often have very expensive pipeline to find or generate more complex transformations that best improves generalization 4 19 36). Second, appending transformed examples the training data often much more effective than training on the (strongly or weakly) transformed examples in-place of the original data. For example, appending one transformed example the training data often much more effecttve than training on two transformed examples in place of every original training data, while both strategies have the same computational cost (c.f. Appendix D.6). Hence, to obtain the state-of-the-art performance, multiple augmented examples are added for every single data point and to each training iteration [12] 36). In this case, even if producing transformations are cheap, such methods increases the size of the training data by orders of magnitude.
OOr code can be found at http:///ww....iiiiiii////////afe
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

As result, state-of-the data augmentation techniques become computationally prohibitive for even medium-sized real-world problems. For example, the state-of-the thet augmentation of [36]. which appends every example with its highest-loss transformations, increases the training time of ResNet20 on CIFAR1O by 13x on an Nvidia A40 GPU (c.f. Sec. (
To make state-of-the-ar data augmentation more efficient and scalable, an effective approach is to carefully select a small subset of the training data such that augmenting only the subset provides similar training dynamics to that of full data augmentation. If such a subset can be quickly found, it would directly lead significant reduction in storage and training costs. First, while standard in-place augmentation can be applied to the entire data, the strong and expensive transformations can be only produced for the examples in the subset. Besides, only the transformed elements of the subset can be appended to the training data. Finally, when the data is larger than the training budget, one can train on random subsets (with standard in-place augmentation) and augment coresets (by strong augmentation and/or appending transformations) to achieve superior performance.
Despite the efficiency and scalability that can provide, this direction has remained largely unex- plored. Existing studies are limited to fully training network and subsampling data points based on their loss influence, for augmentation in subsequent training runs 17.. However, this method is prohibitive for large datasets, provides marginal improvement over augmenting random subsets, and does not provide any theoretical guarantee for the performance of the network trained on the augmented subsets. Besides, when the data contains mislabeled examples, augmentation methods that select examples with maximum loss, and append their transformed versions the data, degrade the performance by selecting and appending several noisy labels.
A major challenge in finding the most effective data points for augmentation is to theoretically under- stand how data augmentation affects the optimization and generalization of neural networks. Existing theoretical results are mainly limited simple linear classifiers and analyze data augmentation as
enlarging the span of the training data (36), providing a regularization effect [3 8, 33 36), enlarging the margin of linear classifier (28). or having a variance reduction effect (5] However, such tools
do not provide insights on the effect of data augmentation on training deep neural networks.
Here, we study the effect of label invariant data augmentation training dynamics of overparameter- ized neural networks. Theoretically, we model data augmentation by bounded additive perturbations (28. and analyze its effect on neural network Jacobian matrix containing all its first-order partial derivatives [. We show that label invariant additive data augmentation proportionally enlarges but more importantly perturbs the singular values of the Jacobian, particularly the smaller ones, while maintaining prominent directions of the Jacobian. In doing so, data augmentation regularizes training by adding bounded but varying perturbations to the gradients. In addition, it speeds up learning harder to learn information. Thus, it prevents overfitting and improves generalization. Empirically, we show that the same effect can be observed for various strong augmentations, e.g., AutoAugment 16). CutOut [9I, and AugMix [12
Next, we develop rigorous method to iteratively find small weighted subsets (coresets) that when augmented, closely capture the alignment between the Jacobian of the full augmented data with the label/residual vector. We show that the most effective subsets for data augmentation examples that when data is mapped to the gradient space, have the most centrally located gradients. This problem can be formulated as maximizing a submodular function. The subsets can be efficiently extracted using a fast greedy algorithm which operates on small dimensional gradient proxies, with only a small additional cost. We prove that augmenting the coresets guarantees similar training dynamics to that of full data augmentation. We also show that augmenting our coresets achieve a superior accuracy in presence of noisy labeled examples.
the set of
We demonstrate the effectiveness of our approach applied to CIFARIO (ResNet20, WideResNee- 28-10), CIFAR 10-IB (ResNet32), SVHN (ResNet32), noisy-CIFAR10 (ResNer20), Caltech256 (ResNet18, 8, ResNet50), TinyImageNet (ResNet50). and ImageNet (ResNet50) compared to random and max-loss baselines [17]. We show the effectiveness of our approach (in presence of standard augmentation) in the following cases:
When producing augmentations is expensive and/or they are appended to the training data:
"W note that our results are in line with that of (30), that in parallel to our work, analyzed the effect of linear transformations on a two-layer convolutional network, and showed that it can make the hard to learn features more likely to be captured during training.
2

---

We show that for the state-of- tf-ee-fft augmentation method of [36 applied to CIFARI0/ReSNet20 it is 3.43x faster to train on the whole dataset and only augment our coresets of size 30%, compared to training and augmenting the whole dataset. At the same time, we achieve 75% of the accuracy improvement of training on and augmenting the full data with the method of [66] outperforming both max-loss and random baselines by up to 10%.
When data is larger than the training budget: We show that can achieve 71.99% test accuracy on RessNet50/maaeNet when training on and augmenting only 30% subsets for 90 epochs. Compared to AutoAugment [6, despite using only 30% subsets, we achieve 92.8%
of the original reported accuracy while boasting 5x speedup in the training time. Similarly, on Caltech256/ResNeclk training on and augmenting 10% coresets with AutoAugment yields 65.4%
accuracy, improving over random 10% subsets by 5.8% and over only weak augmentation by 17.4%.
When data contains mislabeled examples: We show that training on and strongly augmenting 50% subsets using our method on CIFARIO with 50% noisy labels achieves 76.20% test accuracy. Notably, this yields superior performance to training on and strongly augmenting the full data.
2 Additional Related Work
Strong data augmentation methods achieve state-of-the-ar performance by finding the set of trans- formations for every example that best improves the performance. Methods like Auto Augment [6] RandAugment 77. and Faster Rand/ugment [7] search over (possibly large) space of transfor- mations to find sequences of transformations that best improve generalization [6] 21 36. Other
techniques involve a very expensive pipeline for generating the transformations. For example, some
use Generative Adversarial Networks to directly learn new transformations 2 21 24 29 Strong augmentations like Smart Augmentation [19]. Neural Style Transfer-based [3. and GAN-based aug- mentations
4 require an expensive forward pass through a deep network for input transformations. For example, [3] increases training time by 2.8x for training ResNet18 on Caltech256. Similarly, [36] generates multiple augmentations for each training example, and selects the ones with the highest loss.
Strong data augmentation methods either replace the original example by its transformed version, or append the generated transformations to the training data. Crucially, appending the training data with transformations is much more effective in improving the generalization performance. Hence, the most effective data augmentation methods such as that of (36) and AugMix [12] append the transformed examples to the training data. In Appendix D.6, we show that even for cheaper strong augmentation methods such as Augmmnt (6), while replacing the original training examples with transformations may decrease the performance, appending the augmentations significantly improves the performance. Appending the training data with augmentations, however, increase the training time by orders of magnitude. For example, AugMix [12] that outperforms AutoAugment increases the training time by at least 3x by appending extra augmented examples, and [6) increases training time by 13x due appending and forwarding additional augmented examples through the model.
3 Problem Formulation
We begin by formally describing the problem of learning from augmented data, Consider dataset Dirain = [X Xrain Itrain), where Xtrain = (EI."..,,,,) E Rdxxn is the set of n normalized data points x; E [0, 1]d from the index set V, and Ytrrann = (y1. .,)) E {y E (21,22, ",,." with
{ E [0, 1].
The additive perturbation model. Following 28 we model data augmentation as an arbitrary bounded additive perturbation c, with ||||ك cp. For a given and the set of all possible transforma- tions A, we study the transformations selected from S C A satisfying
S {T, A A [T] x ك| En Vx E (rrann.
While the additive perturbation model cannot represent all augmentations, most real-worke augmenta- tions are bounded to preserve the regularities of natural images (e.g. AutoAugment [6] finds that 6 degree rotation is optimal for CIFARIO) 10). Thus, under local smoothness of images, additive pertur- bation can model bounded transformations such as small rotations, crops, shearing, and pixel-wise transformations like sharpening. blurring, color distortions, structured adversarial perturbation (2T]. As such, we see the effects of additive augmentation the singular spectrum holds even under
3

---

real-world augmentation settings (c.f. Fig. 3 in the Appendix). However, this model is indeed limited when applied to augmentations that cannot be reduced to perturbations, such as horizontallvertical flips and large translations. We extend our theoretical analysis to augmentations modeled as arbitrary linear transforms (e.g. as mentioned, horizontal flips) in Appendix B.5.
The set of augmentations at iteration generating r augmented examples per data point can be specified, with abuse of notation, D Daug - UU!= (I (rrin)), Mtroin where (D' (Dugg== |= rn and
T. (Xtran)) ) transforms all the training data points with the set of transformations T S at iteration 1. We denote X ung (U'=1 T. (Xtraa)) and Yaug {U==1 ytrain ).
Training on the augmented data. Let f(W, x)) be an arbitrary neural network with m vectorized (trainable) parameters WER". We assume that the network is trained using (stochastic) gradient descent with learning rate v) to minimize the squared loss L over the original and augmented training examples D' [Pirain UDaug) Dagg) with associated index set V at every iteration l. Lee.
C(W', X)
Σ (W) iEV*
Σ (m..)))D
Il.(WW x..) -yell2
The gradient update at iteration given by
W = W n/CC'W' X), s.t.
VC(W", = J' (W, xx--)) -
(3)
where X = {X UX angt and y = {yirain U yaug] are the set of original and augmented examples and their labels, J(W X) E R is the Jacobian matrix associated with f. and r' SSW,,, x) - y is the residual.
We further assume that J is smooth with Lipschitz constant L. Le.. [[](W (,,,,,)-- I.,-J(W, ②T) e|) L|l x; - æ A 34, Zy E X. Thus, for any transformation T} E S, we have [I ..) J (W, Tí (2:)))l Leg. Finally, denoting J JWW, (trin)))))) and J = J [W;TT )), we get
I=J+ + E, where E is the perturbation matrix with E 2 E E VnLeo-
4 Data Augmentation Improves Learning
In this section, we analyze the effect of data augmentation on training dynamics of neural networks, and show that data augmentation can provably prevent overfitting. To do so, leverage the recent results that characterize the training dynamics based on properties of neural network Jacobian and the corresponding Neural Tangent Kernel (NTK) [4] defined as O J(W, X)J x"". Formally:
(1 (
Σe - (1-,A))(mu)) 1=1
(4)
Ei= Xmnnuy is the eigendecomposition of the NTK 1. Although the constant NTK assumption holds only in the infinite width limit, [88 found close empirical agreement between the NTK dynamics and the true dynamies for wide but practical networks, such as wide ResNet architectures (37). Eq. (4) shows that the training dynamics depend on the alignment of the NTK with the residual vector every iteration Next, we prove that for small perturbations eo. data augmentation prevents overfitting and improves generalization by proportionally enlarging and perturbing smaller eigenvalues of the NTK relatively more, while preserving its prominent directions.
where O UAUT
4.1 Effect of Augmentation on Eigenvalues of the NTK
We first investigate the effect of data augmentation on the singular values of the Jacobian, and use this result to bound the change in the eigenvalues of the NTK. To characterize the effect of data augmentation on singular values of the perturbed Jacobian J. we rely on Weyl's theorem [35] stating that under bounded perturbations E, no singular value can move more than the norm of the perturbations. Formally, |ā; a, S El|2. where ã; and a; are the singular values of the perturbed and original Jacobian respectively. Crucially, data augmentation affects larger and smaller singular values differently. Let be orthogonal projection onto the column space of JT, and P, I be the projection onto its orthogonal complement subspace. Then, the singular values of the perturbed

---

dfferencce
0
Singuar Value
Stngular value
Singular value
Siiguter value
(a) MNIST Ar.
(b) CIFAR Ar:
(c) MNIST Subs. Angle (d) CIFAR Sub. Angle
Figure 1: Effect of augmentations on the singular spectrum of the network Jacobian of ResNet20 trained on CIFARIO 10, and MLP MNIST, trained till epoch 15. (a), (b) Difference in singular values and (c), (d) singular subspace angles between the original and augmented data with bounded perturbations with co = 8 and co 16 for different ranges of singular values. Note that augmentations with larger bound Eo results in larger perturbations to the singular spectrum.
Jacobian J are 07 (a,
14)² 2 + G. where 14 ||PE||2 and m S ||
min the smallest singular value of JJ 32 Since the eigenvalues of the projection matrix P are either or 1, as the number of dimensions m grows, for bounded perturbations we get that on average " = (11) and ? (mm). Thus, the second term dominates and increase of small singular values under perturbation is proportional to /m. However, for larger singular values, first term dominates and hence o; o; ~ μ4. Thus in general, small singular values can become proportionally larger, while larger singular values remain relatively unchanged. The following Lemma characterizes the expected change to the eignvalues of the NTK.
Lemma 4.1. Data augmentation as additive perturbations bounded by small eo results in the following expected change to the eigenvalues of the NTK:
B[A = El = of + as(1 -
(5)
where p: : P(; < 0) is the probability that a; decreases a result of data augmentation, and is smaller for smaller singular values.
The proof can be found in Appendix A.I.
Next, we discuss the effect data augmentation on singular vectors of the Jacobian and show that it mainly affects the prommient directions of the Jacobian spectrum, but to smaller extent compared to the singular values.
4.2 Effect of Augmentation on Eigenvectors of the NTK
Here, we focus characterizing the effect of data augmentation the eigenspace of the NTK. Let the singular subspace decomposition of the Jacobian be J UEV* Then for the NTK, we have θ JJT ' UΣV* VEU" UΣ (since V V = I). Hence, the perturbation of the eigenspace of the NTK is the same as perturbation of the left singular subspace of the Jacobian J. Suppose o, are singular values the Jacobian. Let the perturbed Jacobian be J = J + E, and denote the eigengap "r min(ø; 0++1 1, 1.. where dr+1 := 0. Assuming To > 2 E
r a combination of Wedin's 's theorem 34 and Mirsky's inequality 23 implies
|/u u. 1 2v2 Bll/To-
(6)
This result provides an upper-bound on the change of every left singular vectors the Jacobian.
However as we discuss below, data augmentation affects larger and smaller singular directions differently. To see the effect of data augmentation on every singular vectors of the Jacobian, let the subspace decomposition of Jacobian be J = UEVT U. E, VT + E,, VT, where U, associated with nonzero singular values, spans the column space of J. which is also called the signal subspace, and U,, associated with zero singular values (E,, = 0). spans the orthogonal space of U., which is also called the noise subspace. Similarly, let the subspace decomposition of the perturbed Jacobian be J ÜΣİT = U,E.V. + U, VT. and U. = U, + AU., where AU, is the perturbation of the singular vectors that span the signal subspace. Then the following general first-order expression for the perturbation of the orthogonal subspace due to perturbations of the Jacobian characterize the change of the singular directions: AU, U EV,Σ,1 (0) We
see that singular vectors associated to larger singular values are more robust to data augmentation, compared to others. Note that in general singular vectors more robust than singular values.
5

---

Fig. [[soswsw the effect of perturbations with = 8, 16 on singular values and singular vectors of the Jacobian matrix for hidden layer MLP trained on MNIST, and ResNet20 trained on CIFARIO. As calculating the entire Jacobian spectrum is computationally prohibitive, data is subsampled from 3 classes. We report the effect of other real-world augmentation techniques, such as random crops, flips, rotations and Autoaugment 66] which includes translations, contrast, and brightness transforms in Appendix C. We observe that data augmentation increases smaller singular values relatively more. On the other hand, it affects prominent singular vectors of the Jacobian to smaller extent.
4.3 Augmentation Improves Training & Generalization
Recent studies have revealed that the Jacobian matrix of common neural networks is low rank. That is there are a number of large singular values and the rest of the singular values are small. Based on this, the Jacobian spectrum can be divided into information and nuisance spaces [27]. Information space is a lower dimensional space associated with the prominent singular value/vectors of the Jacobian. Nuisance space a high dimensional space corresponding to smaller singular value/vectors of the Jacobian. While learning over information space is fast and generalizes well, learning over nuisance space is slow and results in overfitting
[27]. Importantly, recent theoretical studies connected the generalization performance to small singular values (of the information space) [
Our results show that label-preeerving additive perturbations relatively enlarge the smaller singular values of the Jacobian in a stochastic way and with high probability. This benefits generalization in 2 ways. First, this stochastic behavior prevents overfitting along any particular singular direction in the muisance space, as stochastic perturbation of the smallest singular values results in a stochastic noise to be added to the gradient at every training iteration. This prevents overfitting (thus a larger training loss shown in Appendix D.5), and improves generalization 7 g) Theorem B. in the Appendix characterizes the expected training dynamics resulted by data augmentation. Second, additive perturbations improve the generalization by enlarging the smaller (useful) singular values that lie in the information space, while preserving cigenvectors. Hence, it enhances learning along these (harder to learn) components. The following Lemma captures the improvement in the generalization performance, as a result of data augmentation.
Lemma 4.2. Assume gradient descent with learning rate is applied to train neural network with constant NTK and Lipschitz constant L, on data points augmented with additive perturbations bounded by eo defined in Sec. 3 Let min be the minimum singular value of Jacobian I associated with training data X train With probability gradient descent augmented data X aug enjoys the following bound:
8, generalization error of the network trained with
(amin + //LCo)² + +0 (1055 8)
2
The proof can be found in Appendix A.2.
Effective Subsets for Data Augmentation
Here, we focus on identifying subsets of data that when augmented similarly improve generalization and prevent overfitting. To do so, our key idea is find subsets of data points that when augmented, closely capture the alignment of the NTK (or equivalently the Jacobian) corresponding to the full aullanteee augmented data with the residual vector, J(W. x( Trt
)T "rang- If such subsets can be found, augmenting only the subsets will change the NTK and its alignment with the residual in similar way as that of full data augmentation, and will result similar improved training dynamics. However, generating the full set of transformations X! aug is often very expensive, particularly for strong augmentations and large datasets. Hence, generating the transformations, and then extracting the subsets may not provide considerable overall speedup.
In the following, we show that weighted subsets (coresets) S that closely estimate the alignment of the Jacobian associated to the original data with the residual vector J (T("., Xtrain) Ptrein can closely estimate the aligmment of the Jacobian of the full augmented data and the corresponding residual JTH (W' Xt. aagg) )rang Thus, the most effective subsets for augmentation can be directly found from the training data. Formally, subsets St weighted by 7 that capture the alignment of the full Jacobian

---

Algorithm 1 CORESETS FOR EFFICIENT DATA AUGMENTATION
Require: The dataset D {(x; y))) number of iterations T.
Ensure: Output model parameters W
1: for t = ,...., do
2: X aug 0.
3: for E {1. [1,.... C) do
4: St = 0. [Gs = 41 Vi.
5:
while |G p2 { do
> Extract coreset from class c by solving Eq. (9)
6:
= (Sa U arg max, ( [|
7:
end while
8:
Y Eiev. I[j = arg wwg.min yes (W", ww)rr (W', Dry y ||I > Coreset weights
9:
X Xang (Xaug U { (X
> Augment the coreset
p = =/5/rr
11: end for
12: Update the parameters W using weighted gradient descent on X aug or (Xtrain U UX xaug)
13:
end for
with the residual by an error of at most & can be found by solving the following optimization problem:
5 arg min S)
s.t. T (W', X')r' diag(n's) (W', X3)rrllss
(8)
sgv
Solving the above optimization problem is NP-hard. However, we discuss in the Appendix A.5, near optimal subset can be found by minimizing the Frobenius norm of matrix Gs, which the ith row contains the euclidean distance between data point and its closest element in the subset S, in the gradient space. Formally, sGs miny [TW' (W",,;),;
(W', ,ry)) When S = [G Ci 1, where is big constant. Intuitively, such subsets contain the set of medoids of the dataset in the gradient space. Medoids a dataset are defined as the most centrally located elements in the dataset [16). The weight of every element j E S is the number of data points closest to it in the gradient space, i.c., 7 = Eiev I[j arg minyrs [JT(W", xx)r; - Jd (W", zy )ry The set of medoids can be found by solving the following submodular cover problem:
S argminsgv|S) s.l. ||Gs|FSS..
The classical greedy algorithm provides logarithmic approximation for the above submodular maximization problem, i.e., | (1 (1+ (n))... It starts with the empty set Sn = 0, and at each iteration 7, it selects the training example s E V S,-1 that maximizes the marginal gain, i.c..
S, = S U {arg max,ev I| (s_,))) complexity of the greedy algorithm can be reduced to ((n) using randomized methods [25] and
The O(nk) computational
further improved using lazy evaluation [22] and distributed implementations (26). The rows of the matrix G can be efficiently upper-bounded using the gradient of the loss w.r.t. the input to the last layer of the network, which has been shown to capture the variation of the gradient norms closely [15]. The above upper-bound is only marginally more expensive than calculating the value of the loss. Hence the subset can be found efficiently. Better approximations can be obtained by considering earlier layers in addition to the last two, the expense of greater computational cost.
At every iteration t during training, we select a coreset from every class c E [C] separately, and apply the set of transformations {TT) only to the elements of the coresets, i.e., X aug {U, T? (Xs:) } We divide the weight of every element
the coreset equally among its transformations, i.e. the final weight D / if E St. We apply the gradient descent updates in Eq.
3 to the weighted Jacobian matrix of X X Yug X [Xtrain U (aag)) (viewing pt as p R") follows:
W W'_ - (diag (')) x'))² n
(10)
The pseudocode is illustrated in Alg.
The following Lemma upper bounds the difference between the alignment of the Jacobian and residual for augmented coreset vs. full augmented data.
A set function F ; 2 + ig+ is submodular if ( F(S) > F(TU(e)) -FTT, for any s g C and E V T. F'ss monotone if (ee(S) 0 for any eE V and S CVV
7

---

Table 1: Training ResNet20 (R20) and WideResnet-22-101 10 (W2810) CIFARIO (C10) using small subsets, and R (R18) on Caltech256 (Cal). We compare accuracies training on and strongly (and weakly) augmenting subsets. For CIFARIO, training and augmenting subsets selected by max- loss performed poorly and did not converge. Average number of examples per class in each subset is shown in parentheses. Appendix D.4 shows baseline accuracies from only weak augmentations.
Model/Data
C10/2200
C10/W2810
CaI/R18
Subset
0.1% (5) 0.2% (10) 0.5% (25)
1% (50)
1% (50)
5% (3)
10% (6) 20% (12)
30% (18) 40% (24) 50% (30)
Max-loss
< 15%
< 15%
< 15%
< 15%
15%
19.2
30.6
71.3
75.6
77.3
78.6
Random
33.5
12.7
58.7
7444
57.7
41.5
61.8
72.5
75.7
77.6
78.5
Ours
37.8
45.1
63.9
74.7
62.1
52.7
65.4
73.1
76.3
77.7
78.9
Lemma 5.1. Let S be a coreset that captures the alignment of the full data NTK with residual with an error of at most & as in Eq. 8 Augmenting the coreset with perturbations bounded by co n nāvi V captures the alignment of the fully augmented data with the residual by an error of at most
I (Wug) - diag(p (' X sang rrsls (VL).
(1I)
5.1 Coreset vs. Max-loss Data Augmentation
In the initial phase of training the NTK goes through rapid changes. This determines the final basin of convergence and network's final performance [TO.. Regularizing deep networks by weight decay or data augmentation mainly affects this initial phase and matters little afterwards [1]]. Crucially, augmenting coresets that closely capture the alignment of the NTK with the residual during this initial phase results in less overfitting and improved generalization performance. On the other hand, augmenting points with maximum loss early training decreases the alignment between the NTK and the label vector and impedes learning and convergence. After this initial phase when the network has good prediction performance, the gradients for majority of data points become small. Here, the alignment is mainly captured by the elements with the maximum loss. Thus, as training proceeds, the intersection between the elements of the coresets and examples with maximum loss increases. We visualize this pattern in Appendix D.11. The following Theorem characterizes the training dynamics of training on the full data and the augmented coresets, using our additive perturbation model.
Theorem 5.2. Let L; be B-smooth, L be X-smooth and satisfy the a-PL condition, that is for O. V V 12 aL(W) for all weights W. Let be Lipschitz, in X with constant T', and = max { T., }. Let Go be the gradient at initializaion, mmax the maximum singular value of the coreset Jacobian at initialization. Choosing Eo S JupaVin and running SGD on full data with augmented coreset using constant step size x3. result in the following bound:
Va -1- )==
L
E C Cann (W'III
2Go +
Tmax
The proof can be found in Appendix A.4.
Theorem 5.2 siswws that training on full data and augmented coresets converges to a close neighbor- hood of the optimal solution, with the same rate as that of training on the fully augmented data. The size of the neighborhood depends on the error of the coreset & in Eq. (8). and the error in capturing the alignment of the full augmented data with the residual derived in Lemma 55.1 The first term decrease as the size of the coreset grows, and the second term depends on the network structure.
We also analyze convergence of training only the augmented coresets, and augmentations modelled as arbitrary linear transformations using a linear model [36] in Appendix B.5.
Experiments
Setup and baselines. We extensively evaluate the performance of our approach in three different settings. Firstly, we consider training only on coresets and their augmentations. Secondly, we investigate the effect of adding augmented coresets to the full training data. Finally, we consider adding augmented coresets to random subsets. We compare our coresets with max-loss and random subsets as baselines. For all methods, we select a new augmentation subset every epochs. We note that the original max-loss method [17] selects points using fully trained model, hence it can only
8

---

Table 2: Caltech256/Reseed with same set- tings as Tab. with default weak augmenta- tions but varying strong augmentations.
Table 3: Training on full data and strongly (and weakly) augmenting random subsets, max-loss subsets and coresets on TnnylmageNe//RsNNe5500, R = 15.
Random
Ours
Augmentation
30% 40% 50% 30%
40%
50%
Random
Max-loss
Ours
CutQut
43.32 62.84 76,21 55,53
66.10
76.91
20%
30%
50%
20%
30%
60%
20%
30%
50%
AugMix
40.77 61.81
72.17
52.72
64.91
73.01
Perturb
48.51 66.20
75.34 58.29 67.47 76.50
50.97
52.00 54.92 51.30
52.34
53.37
51.99
54.30
55.16
Table 4: Accuracy improvement by augmenting subsets found by our method vs. max-loss and random, over improvement of full (weak and strong) data augmentation (F.A.) compared to weak augmentation only (W.A.). The table shows the results for training on CIFAR10(C10/ResNe1) (R20), SVHN/eesNe(32((32)) and CIFARIO-Imbalaneee 10laII0lmaaaaaddC110 (CIo://BdddIIOOO/0////////// Nesss with = 20.
Datasct
W.A.
F.A.
Random
Max-lost
Ours
Ace
Acc
5%
10%
30%
5%
10%
30%
5%
10%
30%
C10/R20
89.46
93.50
21.8%
39.9%
65.6%
32.9%
47.8%
73.5%
34.9%
51.5%
75.0%
CI0-IB/R32
87.08
92.48
25.9%
45.2%
74.6%
31.3%
39.6%
74.6%
37.4%
49.4%
74.8%
SVHN/R32
95.68
97.07
5.8%
36.7%
64.1%
35.3%
49.7%
76.4%
31.7%
48.3%
80.0%
select one subset throughout training. To maximize fairness, we modify our max- -loss baseline to select a new subset at every subset selection step, For all experiments, standard weak augmentations (random crop and horizontal flips) are always performed on both the original and strongly augmented data.
6.1 Training on Coresets and their Augmentations
First, we evaluate the effectiveness of our approach for training on the coresets and their augmenta- tions. Our main goal here is to compare the performance of training on and augmenting coresets vs. random and max-loss subsets. Tab. D shows the test accuracy for training ResNet20 and Wide-ResNe on CIFARIO when we only train on small augmented coresets of size 0.1% to 1% selected every epoch (R 1), and training & 8 on Caltech256 using coresets of size 5% to 50% with R = 5. We see that the augmented coresets outperform augmented random subsets by a large margin, particu- larly when the size of the subset is small. On Caltech256/Reser1188 training coresets yields 65.4% accuracy, improving over random by 5.8%, and over only weak augmentation by 17.4%. This clearly shows the effectiveness of augmenting the coresets. Note that for CIFARIO experiments, training on the augmented max-loss points did not even converge in absence of full data.
and augmenting 10%
Generalization across augmentation techniques. We note that our coresets are not dependent on the type of data augmentation. To confirm this, we show the superior generalization performance of our method in Tab. for training ResNet18 8 with R = 5 on coresets vs. random subsets of Caltech256. augmented with CutOut (9), AugMix [2]. and noise perturbations (color jitter, gaussian blur). For example, on 30% subsets, we obtain 28, 2%. 29.3%, 20.2% relative improvement over augmenting random subsets when using CutOut, Aug, and noise perturbation augmentations, respectively.
6.2 Training on Full Data and Augmented Coresets
Next, we study the effectiveness of our method for training on full data and augmented coresets. Tab. 4 demonstrates the percentage of accuracy improvement resulted by augmenting subsets of size 5%, 10%, and 30% selected from our method vs. max-loss and random subsets, over that of full data augmentation. We observe that augmenting coresets effectively improves generalization, and outperforms augmenting random and max-loss subsets across different models and datasets. For example, on 30% subsets, we obtaín 13.1% and 2.3% relative improvement over random and max-loss average. We also report results on Neeeima (R= =2=10 15) in Tab. 3 where we show that augmenting coresets outperforms max-loss and random baselines, e.g. by achieving 3.7% and 4.4% relative improvement over 30% max-loss and random subsets, respectively.
Training speedup. Fig. [ we measure the improvement in training time in the case of training on full data and augmenting subsets of various sizes. While our method yields similar or slightly lower speedup to the mox-loss and random baselines, our resulting accuracy outperforms the baselines on average. For example, for SVHN/Resnet32 using 30% coresets, we sacrifice 11% of the relative speedup to obtain an additional 24.8% of the relative gain in accuracy from full data augmentation, compared to random baseline. Notably, get 3.43x speedup for training on full data and augmenting

---

Table 5: Training ResNet20 CIFARIO with 50% label noise, R = 20. Accuracy without strong augmentation is 70.72 + 0.20 and the accuracy of full (weak and strong) data augmentation is 75.87 + 0.77. Note that augmenting 50% subsets outperforms augmenting the full data (marked **).
Subset
Random
Max-loss
Ours
10%
72.32
0.14
71.83 0.13
73.02 + 1.06
30%
74.46
0.27
72.45
74.67 0.15
50%
75.36 0.05
03.23
76.20 0.75
30% coresets, while obtaining 75% of the improvement of full data augmentation. We provide wall- clock times for finding coresets from Caltech256 and TinylmageNet in Appendix D.7.
103
Spotsdap Lator
A5
quandup com speecip
m0s-mooo ccreumprovve
10
23th spendip
los
rastirgres USS HEOrORO
30
5%
10%
30%
10%
30%
30%
30%
35
3,0%
30%
(a) CIFAR10/ReSNe120 (b) CIFARIO//
(c) SVHN/ResNet32
(d) SVHN/ResNet32
Figure 2: Accuracy improvement and speedups by augmenting subsets found by method vs. max-loss and random on (a), (b) Res.Ne20/CIIFAR1 10 and (c), (d) ResNet32/SVHN.
Augmenting noisy labeled data. Next, we evaluate the robustness of our coresets to label noise. Tab. shoows the result augmenting coresets vs. max-loss and random subsets of different sizes selected from CIFARIO with 50% label noise on ResNer20. Notably, our method not only outperforms max-loss and random baselines, but also achieves superior performance over full data augmentation.
6.3 Training on Random Data and Augmented Coresets
Finally, we evaluate the performance of our method for training on random subsets and augmenting coresets, applicable when data is larger than the training budget. We report results on TinylmageNet and ImageNet on ResNet50 (90 epochs. R == 15). Tab. showw the results of training on random subsets, and augmenting random subsets and coresets of the same size. We see that our results hold for large-scale datasets, where we obtain 7.9%. 4.9%, and 5.3% relative improvement over random baseline with 10%, 20%. 30% subset sizes respectively on TinylmageNet, and 7.6%, 2.3%, and 1.3% relative improvement over random baseline with 10%, 30%, and 50% subset sizes on ImageNet. Notably, compared to AutoAugment, despite using only 30% subsets, we achieve 71.99% test accuracy, which 92.8% of the original reported accuracy, while boasting 5x speedup in training.
Table 6: Training on random subsets and strongly (and weakly) augmenting random and max loss subsets vs coresets for TinylmageNet (left) and ImageNet (right) with ResNet50.
Random
Max-loss
Ours
Random
Maxloss
Ours
10%
10%
10%
20%
10%
30%
30%
50%
50%
28.64 38.97 44.10 27.64 41.00
30.90
40.88 46.42
63.67
70.39 72.35 65.43 71.55 72.77 68.53
71.99
73.28
7 Conclusion
We showed that data augmentation improves training and generalization by relatively enlarging and perturbing the smaller singular values of the neural network Jacobian while preserving its prominent directions. Then, we proposed a framework to iteratively extract small coresets training data that when augmented, closely capture the alignment of the fully augmented Jacobian with the label/residual vector. We showed the effectiveness of augmenting coresets in providing a superior generalization performance when added to the full data or random subsets, in presence of noisy labels, or as a standalone subset. Under local smoothness of images, our additive perturbation can be applied to model many bounded transfornations such small rotations, crops, shearing, and pixel-wise transformations like sharpening, blurring, color distortions, structured adversarial perturbation [2I]. However, the additive perturbation model is indeed limited when applied augmentations that cannot be reduced to perturbations, such as horizontal/vertical flips and large translations. Further theoretical analysis of complex data augmentations is indeed an interesting direction for future work.
8 Acknowledgements
This research was supported in part by the National Science Foundation CAREER Award 21 2144492, and the UCLA-Amazoo Science Hub for Humanity and AI.
10

---

References
[1] Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of op- timization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning, pages 322-332, PMLR, 2019.
[2] Shumeet Baluja and Ian Fischer. Adversarial transformation networks: Learning to generate adversarial examples. arXiv preprint
09387, 2017.
[3] Chris Bishop. Training with noise equivalent to tikhonov regularization. Neural compula- lion, 7(1):108-116, 1995.
[4] Christopher Bowles, Roger Gunn, Alexander Hammers, and Daniel Rueckert. Gansfer learning: Combining labelled and unlabelled data for gan based data augmentation. arXiv preprint arXiv:1811.1066, 2018.
[5] Shuxiao Chen, Edgar Dobriban, and Jane H Lee. Invariance reduces variance: Understanding data augmentation in deep learning and beyond. arXiv preprint arXiv:1907.10903 2019.
[6] Ekin D Cubuk, Barret Zoph, Dandelion Mane, Vijay Vasudevan, and Quoe V Le. Autoaugment: Learning augmentation strategies from data. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 113-123, 2019.
[7] Ekin D Cubuk, Barret Zoph, Jonathon Shlens, and Quoc V Le. Randaugment: Practical automated data augmentation with a reduced search space. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition Workshops, pages 702-703, 2020.
[8] Tri Dao, Albert Gu, Alexander Ratner, Virginia Smith, Chris De Sa, and Christopher Ré. kernel theory of modern data augmentation. In International Conference on Machine Learning, pages 1528 1528-1537. PMLR, 2019.
[9] Terrance DeVries and Graham W Taylor. Improved regularization of convolutional neural networks with cutout. arXiv preprint arXivv1108.044 04552, 2017.
[10] Stanislav Fort, Gintare Karolina Dziugaite, Mansheej Paul, Sepideh Kharaghani, Daniel M Roy, and Surya Ganguli. Deep learning versus kernel learning: an empirical study of loss landscape geometry and the time evolution of the neural tangent kernel. Advances in Neural Information Processing Systems, 33, 2020.
[11] Aditya Sharad Golatkar, Alessandro Achille, and Stefano Soatto. Time matters in regularizing deep networks: Weight decay and data augmentation affect early learning dynamics, matter little near convergence. Advances in Neural Information Processing Systems, 32:10678-10688 2019.
[12] Dan Hendrycks, Norman Mu, Ekin Cubuk, Barret Zoph. Justin Gilmer, and Balaji Lakshmi- narayanan. Augmix: A simple data processing method to improve robustness and uncertainty. arXiv preprint arXiv: 192.:71912.0228112222 2019.
[13] Philip TG Jackson, Amir Atapour Abarghouei. Stephen Bonner, Toby P Breckon, and Boguslaw Obara. Style augmentation: data augmentation via style randomization. In CVPR Workshops, volume 6, pages 10-11, 2019.
[14] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization neural networks. arXiv preprint 1rXiv:1806.007 075572, 2018.
[15] Angelos Katharopoulos and François Fleuret. Not all samples are created equal: Deep learning with importance sampling. In International conference machine learning, pages 2525-2534 PMLR, 2018
[16] L Kaufman, PJ Rousseeuw, and Y Dodge. Clustering by means of medoids in statistical data analysis based on the, 1987.
[17] Michael Kuchnik and Virginia Smith. Efficient augmentation via data subsampling. In Interna- tional Conference on Learning Representations, 2018.
11

---

[18] Jachoon Lee, Lechao Xiao, Samuel S Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl-Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. In NeurIPS, 2019.
[19] Joseph Lemley, Shabab Bazrafkan, and Peter Corcoran. Smart augmentation learning an optimal data augmentation strategy. leee Access, 5:5858 1-5858-5869, 2017.
[20] Fu Li, Hui Liu, and Richard J Vaccaro. Performance analysis for doa estimation algorithms: unification, simplification, and observations. JEEE' Transactions on Aerospace and Electronic Systems, 29(4): 170-1110111 1184, 1993.
[21] Calvin Luo, Hossein Mobahi, and Samy Bengio. Data augmentation via structured adversarial perturbations. arXiv preprint wrXiv:2011.03010 2020.
[22] Michel Minoux. Accelerated greedy algorithms for maximizing submodular set functions. In Optimization techniques, pages 234-243. Springer. 1978.
[23] Leon Mirsky, Symmetric gauge functions and unitarily invariant norms, The quarterly journal of mathematics, 11(1):50-59, 1960.
[24] Mehdi Mirza and Simon Osindero. Conditional generative adversarial nets. arXiv preprint arXiv:1411.1784 2014.
[25] Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, Amin Karbasi, Jan Vondrák, and Andreas Krause. Lazier than lazy greedy. In Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015.
[26] Baharan Mirzasoleiman, Amin Karbasi, Rik Sarkar, and Andreas Krause. Distributed submodu- lar maximization: Identifying representative elements in massive data. In Advances in Neural Information Processing Systems, pages 2049-2057, 2013.
[27] Samet Oymak, Zalan Fabian, Mingehen Li, and Mahdi Soltanolkotabi. Generalization guaran- tees for neural networks via harnessing the low-rank structure of the jacobian. arXiv preprint arXiv:1906.00 05392, 2019.
[28] Shashank Rajput, Zhili Feng, Zachary Charles, Po-Ling Loh, and Dimitris Papailiopoulos. Does data augmentation lead to positive margin? In International Conference on Machine Learning, pages 5321-5330. PMLR, 2019.
[29] Alexander Ratner, Henry R Ehrenberg, Zeshan Hussain, Jared Dunnmon, and Christopher Ré. Learning to compose domain-specific transformations for data augmentation. Advances in neural information processing systems, 30:3239, 2017.
[30] Ruoqi Shen, Sébastien Bubeck, and Suriya Gunasekar. Data augmentation as feature manipula- tion: a story of desert cows and grass cows. arXiv preprint arXiv:2203.01572 2022.
[31] Connor Shorten and Taghi M Khoshgoftaar. A survey on image data augmentation for deep learning, Journal of Big Data, 6(1):1-48, 2019.
[32] GW Stewart. A note the perturbation of singular values. Linear Algebra and Its Applications, 28:213-216, 1979.
[33] Stefan Wager, Sida Wang, and Percy Liang. Dropout training as adaptive regularization. arXiv preprint arXiv: 130..1493. 2013.
[34] Per-Åke Wedin. Perturbation bounds connection with singular value decomposition. BIT Numerical Mathematics, 12(1):99-111, 1972.
[35] Hermann Weyl. The asymptotic distribution law of the eigenvalues of linear partial differential equations (with an application to the theory of cavity radiation). mathematical annals, 71(4):411 479, 1912.
[36] Sen Wu, Hongyang Zhang, Gregory Valiant, and Christopher Ré. On the generalization effects of linear transformations in data augmentation. In International Conference on Machine Learning, pages 10410-10420. PMLR, 2020.
12

---

[37] Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. In British Machine Vision Conference 2016. British Machine Vision Association, 2016.
13


Reviews:
[{"review_id": "zNFn6Qddyyo", "reviewer": "Reviewer_rqcs", "summary": "This paper tackles the problem of finding subsets of a data set on which to apply data augmentation, such that the performance is as close as possible to augmenting the whole data set. First, the paper models data augmentation as additive perturbations of the data and provides a theoretical analysis of the effect of perturbations on the singular values of the network Jacobian. Then, it proposes a method to select a subset of the data that aims at matching the alignment of the Jacobian of the fully augmented data with the residual vector. Finally, the paper evaluates the proposed method on several data sets and architectures, comparing with selecting random subsets and max-loss, a previously proposed method.", "questions": "Besides the concerns discussed in the previous section, I would like to ask the authors whether they could elaborate on how the theoretical analysis and the conclusions contribute to our understanding of how data augmentation (or additive perturbations) impact overfitting and generalisation. In particular, I refer to Section 4.3, where this conclusions are mentioned. However, I either do not understand completely the relationship between the results and overfitting and generalisation, or the connection is just weak.\n\nI have another comment or suggestion regarding a sentence in the introduction that I find a bit misleading: \n\n\"We demonstrate the effectiveness of our approach applied to training ResNet18, ResNet20, ResNet32, ResNet50, Wide-ResNet on CIFAR10, CIFAR10-IB, SVHN, Caltech256, TinyImageNet, and ImageNet compared to random and max-loss baselines\"\n\nThis gives the impressions that multiple architectures are tested all on multiple data sets, while in fact, only one or maximum two architectures are tested per data sets and the evaluation on some of the data sets, for instance ImageNet, is quite limited.\n\nFinally, a few minor typing errors: \n\n* In Table 1, the heading of the first column is Model/Dataset, but it should read Dataset/Model.\n* In page 8, \"We use [37] for...\" reads weirdly.\n* I would use \"Table\" instead of just \"Tab.\", which reads more easily and uses just one more character.", "limitations": "I have discussed the limitations above. In particular, regarding limitations, I kindly encourage the authors to more explicitly and openly discuss the limitations of the paper. I believe it is a good paper, the results are interesting and relevant, but it is important to discuss, in my opinion, the limitation of modelling data augmentation as additive perturbation, the fact that simple data augmentation methods are effective and computationally cheap and that the empirical results of coresets provide only moderate benefits compared to other methods.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\nAs main strength, I highlight that this paper provides a sound theoretical analysis of how additive perturbations of the inputs impact the eigenspace of the Neural Tangent Kernel (NTK), or the singular values of the model Jacobian. The analysis concludes that input perturbation change proportionally the smaller singular values, while the larger singular values are affected less.\n\nAnother strength of the paper is the breadth of the empirical evaluation, in which CIFAR-10, SVHN, Caltech256, Tiny ImageNet and ImageNet are used as benchmarks, though with large differences in the depth of the analysis across data sets.\n\nFinally, regarding strengths, I would like to point out that the paper is clearly written, it is mostly easy to follow and the structure is reasonable.\n\nRegarding weaknesses, my first concern is about the generality of modelling data augmentation as additive perturbations, following the work by Rajput et al. (2019). While I acknowledge that simplifying data augmentation as something that can be easily modelled mathematically is currently necessary, and I do not reject the significance of the results of this paper because of this assumption, I do argue that it is important to also acknowledge the limitation of this modelling assumption. In my opinion, this limitation is barely discussed and, on the contrary, the paper argue that the results can be extended to more complex augmentations, while this is barely analysed in the paper, besides a short section and one figure in the appendix. Data augmentation comprises a range of complex transformations that, in the case of natural images, encode properties of the human visual system. Take, for instance, the case of horizontal flips, which largely preserve the label of the image by applying a transformations that is fundamentally different to additive perturbations. However, the paper makes this strong modelling assumption but then uses the term \"data augmentation\" to talk about the conclusions from using additive perturbations. As a comparison, Rajput et al. (2019) do acknowledge this limitation and discuss the need to extend the theoretical analyses to practical augmentation methods.\n\nAnother concern has to do with the overall motivation for the proposed method, that is for the need to select subsets of data on which to apply data augmentation. On the second sentence of the abstract, the authors write that \"the most effective augmentation techniques become computationally prohibitive for even medium-sized datasets\". This statement is extended in the introduction, where the authors cite several papers on so-called _automatic data augmentation_. First, these methods are indeed disproportionally expensive in computational terms, while providing only marginal improvements (in the best case) with respect to traditional, simple, cheap data augmentation techniques (Pérez and Wang, 2017). The paper also mentions that performing data augmentation increases \"the training time by orders of magnitude\". However, it has been shown that the largest benefits of data augmentation are achieved by very simple and cheap transformations such as horizontal flips and translations, and more complex transformations only marginally improve the performance further (Hernández-García and König, 2018). Such simple transformations largely increase the performance without increasing the training time. By way of illustration, the previously cited paper shows that training with 50 % of CIFAR-10 _and_ data augmentation on the full available set achieves more than 95 % of the _full_ accuracy in about half the training time. Therefore, given this result, is it really necessary to develop methods to select subsets given a full data set? In fact, the present paper does not stick to so-called automatic augmentation methods, but also studies CutOut, which is computationally very cheap to perform. Again, if CutOut is considered a strong augmentation method, then what is the need for improving the computational efficiency?\n\nRelated to the concerns discussed above, my last main concern is related to the effectiveness of the proposed method given the results and the degree to which the conclusions and claims reflect the results. For example, the conclusion from Table 1 is that \"the improvement from augmenting the coresets is significantly larger than random data points\". However, a close inspection of the results in the table casts some doubts about the strength of the statement. On CIFAR-10 and ResNet20, the improvement of augmenting the coresets with respect to no augmentation (right-most column) is better than augmenting random sets with 0.1 and 0.2 % subsets. With 0.5 and 1 % subsets, the improvement is about the same. On Caltech256 with ResNet18, the improment on coresets is actually worse than on random sets with 5 and 10 % of the data, and about the same in the rest of the cases. Furthermore, the trend is the opposite than on CIFAR-10, which is confusing. Therefore, I would humbly suggest to adjust the claims regarding this set of results. In particular, these sentences:\n\n* \"the augmented coresets outperform augmented random subsets by a large margin\": this is not true, as discussed above.\n* \"the improvement from augmenting the coresets is significantly larger than random data points\": this is not true either, by extension.\n* \"We see that while the non-augmented coreset performs worse than random in most cases\": this is also not true, by inspecting the table.\n\nIn Table 4, we also see that coresets provide better improvement on average than max-loss, but not consistently in all cases and by a small margin. In particular, the averages across data sets and architectures with 5, 10 and 30 % sets are: \n\n|          | 5 %    | 10 %   | 30 %   | \n|----------|--------|--------|--------|\n| max-loss | 33.2 % | 45.7 % | 74.8 % |\n| coresets | 34.7 % | 49.7 % | 76.6 % |\n\nWhile coresets indeed provide better improvement on average, the difference is very small, especially if we take into account that that these numbers are the improvement of the performance from no augmentation to full augmentation. The small margin becomes relevant since the speed up of coresets is smaller than that of max-loss, but the authors claim that \"[w]hile our method yields similar or slightly lower speed-up to the max-loss policy and random approach respectively, our resulting accuracy outperforms these two approaches\". I would kindly suggest to adjust this claim too.\n\nReferences\n\n* Pérez and Wang. [The effectiveness of data augmentation in image classification using deep learning](https://arxiv.org/abs/1712.04621). 2017.\n* Hernández-García and König. [Data augmentation instead of explicit regularization](https://arxiv.org/abs/1806.03852). 2018", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "fbgeHWFSXa2", "reviewer": "Reviewer_xtob", "summary": "This paper provides analysis to show that the effect of data augmentations can be explained by looking at the singular values of the network jacobian. Based on this, an algorithm is proposed to find a subset of the data points on which data augmentations can be done to best approximate the effect of doing augmentations on the whole dataset. Experiments show that the proposed algorithm works better than selecting the subset randomly or according to max-loss. ", "questions": "Please see Weaknesses", "limitations": "The authors included some discussions about the limitations.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. I like the analysis part which focuses on the effect of data augmentation on the singular values of the network jacobian, which is a novel observation and motivates the proposed selection algorithm.\n2. Extensive experiments show that the proposed selection algorithm works better than the random selection and the selection according to max-loss.\n\nWeaknesses:\nI have two major concerns:\n1. The problem itself is not well motivated enough, i.e., why do we need to select a subset to perform data augmentation. Although some augmentation techniques are computationally expensive, there are many ``easy'' augmentations (that are also commonly used like random cropping, flipping, permutation, etc.) and these augmentations are not computationally prohibitive.\n2. Even if we leave the motivation concern aside, the current experiments do not support the authors' claim. The authors claim that by selecting a subset to perform augmentations, we can speed up the overall training time by several times. Ideally the experiments should compare the training time of (1) train the network using the whole dataset while performing augmentations on all data and (2) traing the network using the whole dataset while only performing augmentations on the selected subset. If the training of (2) is several times faster than (1), then the authors' claim is well supported. However, the current experiments only show that training on a selected subset is much faster than training on the whole dataset. This speedup is a result of fewer training steps and has nothing to do with the data augmentation.\n\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "ZRnWx19w7Mb", "reviewer": "Reviewer_y9hQ", "summary": "The paper first studies the relationship between data augmentation and the singular values of Jacobian in an over-parametrized network. Then, the authors propose a method to select a subset of data augmented training data to speed up the training of the neural networks. Empirically, the proposed approach achieves improved results than the random data argumentation subset selection and speeds up the training on standard image classification tasks.", "questions": "Comments:\n* As mentioned above, I wonder if there is a useful application for their proposed approach.\n* CIFAR-10 baseline (with standard data augmentation) for ResNet20 seems to be lower than the reported values in the literature, where you can above 95% test accuracy.\n\nMinor comments:\n* In Equation 3, the eigenvalue $\\lambda$ is not defined.\n* In Algorithm 1, it would be helpful if variables $V_c$ and $T_i$ were defined.\n\n\n** After Rebuttal **\nI acknowledge that I have read the author's response and other reviews. Thank you for the clarification on the use-cases of the proposed approach. As noted by other reviewers, I believe that including these points more clearly would strengthen the paper. \n\nRegarding the accuracy of the CIFAR-10 baseline, I apologize for the confusion. I thought 95 percent accuracy can be obtained on ResNet-20 on CIFAR-10. ", "limitations": "I believe that the work does not have any potential negative societal impact. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The topic of the paper is interesting and relevant to the Neurips community. The technical details of the paper look correct, and the authors properly cite important relevant works. The empirical analysis in the paper is detailed, and the authors provide code to reproduce experiments in the paper. It is convincing that the proposed approach can select a subset of augmented data helpful in improving the training accuracy (with reduced dataset) and speed up training.\n\nHowever, I am still unclear about the core motivation and application of the paper. More specifically, in what cases selecting a subset of the training data is useful (especially when using the full augmentation typically achieves the best test accuracies)? It would be helpful if the authors provided a specific use case of the proposed approach. Moreover, the authors did not fully describe the limitations of their proposed approach. Does the proposed approach work for smaller networks (under-parameterized) or when the dataset size is small? Discussing these limitations in the paper would be helpful to the readers.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept