Data-Efficient Augmentation for Training Neural Networks
Authors: Tian Yu Liu
Baharan Mirzasoleiman
Venue: ICLR 2022 Submitted (2022)
Keywords: Data Augmentation
Neural Network
Coresets

Abstract: Data augmentation is essential to achieve state-of-the-art performance in many deep learning applications. However, modern data augmentation techniques become computationally prohibitive for large 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, speeds up learning by enlarging the smaller singular values of the network Jacobian. 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 label/residual vector. We prove that stochastic gradient descent applied to augmented subsets found by our approach have similar training dynamics to that of fully augmented data. Our experiments demonstrate that our method outperforms state-of-the-art max-loss strategy by 7.7% on CIFAR10 while achieving 6.3x speedup, and by 4.7% on SVHN while achieving 2.2x speedup, using 10% and 30% subsets, respectively.

Under review as a conference paper at ICLR 2022
DATA-EFFICIENT AUGMENTATION FOR TRAINING NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
Data augmentation is essential to achieve state-of-the-art performance in many deep learning applications. However, modern data augmentation techniques become computationally prohibitive for large datasets. To address this, propose 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, speeds up learning by enlarging the smaller singular values of the network Jacobian. Then, we propose framework to iteratively extract small subsets of training data that when augmented, closely capture the alignment of the fully augmented Jacobian with label/residual vector. We prove that stochastic gradient descent applied to augmented subsets found by our approach have similar training dynamies that of fully augmented data. Our experiments demonstrate that our method outperforms state-of-the-art max-loss strategy by 7.7% on CIFAR1O while achieving 6.3x speedup, and by 4.7% on SVHN while achieving 2.2x speedup, using 10% and 30% subsets, respectively.
INTRODUCTION
Data augmentation expands the training data by applying transformations, such as rotations or crops for images, the original training examples. Due its effectiveness, data augmentation key component in achieving nearly all ttate-of-the-att the-hatett art results in deep learning applications (Shorten & Khoshgoftaar 2019). The most effective data augmentation techniques often search over (possibly large) space of transformations to find sequences of transformations that speeds up training the most (Cubuk et al., 2019 2020 Luo al., 2020) Wu et al.) 2020). In addition, multiple augmented examples are usually generated for single data point to obtain better results, increasing the size of the training data by orders of magnitude. As result, state-of-the-an data augmentation techniques become computationally prohibitive for large real-world problems (c.f. Fig. 1.
To make data augmentation more efficient and scalable, an effective approach to carefully select a small subset of the training data such that augmenting only the subset have similar training dynamics to that of full data augmentation. such a subset can be quickly found, it would directly lead to a significant reduction in storage and training costs, and lower costs incurred from selecting and tuning the optimal set transformations to apply. Despite the efficiency and scalability that it can provide, this direction has remained largely unexplored. Existing studies are limited to fully training network and subsampling data points based on its loss or influence for augmentation in subsequent training runs (Kuchnik & Smith 2018). However, this method is prohibitive for large datasets, provides
$5.0
Thaning ACCUEDCY gain
20
Tasiing
120
22.5
traiting Gime
22
(a) CIFAR
(b) SVHN/Resnet32
Figure I: Speedup/Accuracy of augmenting 30% coresets compared to original max-loss policy for (a) ResNet20 trained CIFAR10 and (b) ResNet32 trained on SVHN.

---

Under review as a conference paper at ICLR 2022
marginal improvement over augmenting random subsets, and does not provide any theoretical guarantee for the performance of the network trained on the augmented subsets.
A major challenge in finding the most effective data points for augmentation is to theorctically under- stand how data augmentation affects the optimization and generalization of neural networks. Existing theoretical results mainly limited to simple linear classifiers and analyze data augmentation as enlarging the span of the training data (Wu et al.] 2020), providing a regularization effect (Bishop) 1995, Dao al. 2019 Wager et al., 2013 Wu et al. 2020), enlarging the margin of linear classifier (Rajput et al. 2019). or having a variance reduction effect (Chen et al. 2019). 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 modeled by small additive perturbations (Rajput et al., 2019) on training dynamics of overparameterized neural networks. In particular, we rely on recent results that characterize training dynamics of neural networks based on the alignment of the labels/residuals with the singular subspace of the network's Jacobian matrix containing all its first-order partial derivatives (Arora et al. 2019). We show that label invariant data augmentation enlarges smaller singular values of the information space, and prove that this will speed up training.
Next, we develop rigorous method to iteratively find small weighted subsets (coresets) that when augmented, closely capture the alignment of the full augmented data with the label/residual, at every point during the training. Augmenting the coresets guarantees similar training dynamics to that of full data augmentation. Our key observation is that early in training, this alignment is best captured by data points that are highly representative of their classes. However towards the end of training when the network converges, data points with maximum loss best capture this alignment. Data augmentation has been empirically shown mainly affect the initial phase of training (Golatkar eet al. 2019), which crucially determines the final basin of convergence (Fort et al. 2020). Better selection of points by our method during this initial phase explains the superior accuracy improvement resulted by augmenting our coresets vs. the max-loss and the better final generalization performance. Importantly, we show that our coresets can be provably trained on even in absence of full data, and even when high fraction of labels are noisy.
We demonstrate the effectiveness of our approach applied to training ResNer20, ResNet32, Wide- ResNet on CIFARIO. CIFAR and SVHN compared to random and max-loss baselines (Kuchnik) & Smith 2018). We show that augmenting coresets found by our approach outperforms the state- of-the-art even in absence of the full data. For instance, when small augmented subsets of size 30% found by our approach are appended to CIFARIO, we attain 75% of the improvement in test accuracy compared to augmenting the full dataset while enjoying 3.4x speedup in training time. Even in the absence of full data, training and augmenting tiny coresets of size 1% can achieve 74.7% accuracy on CIFAR Net2 while providing 39x speedup compared to using the full dataset. On CIFAR10 with 50% noisy labels, augmenting 50% of the training data outperforms full data augmentation.
PROBLEM FORMULATION
We begin by formally describing the problem of learning from augmented data. Consider a dataset Drrain = train: Itrain), where Xtrain (æ11 a.) E Raxn is the set of normalized data points æ4 E [0, 1jd, from the index set V, i.e., E V = (1....,)) n), and ytroin (y1,-.,, 9n) E {y {21, ,vC}} with {u, E [0, Assume at every step t during training, we have set of augmented examples Dr Dang generated by set of label-invariant transformations. In particular, following (Rajput et al., (2019) we model data augmentation as an arbitrary bounded additive perturbation e, with | eg. Formally, for given upper bound en and the set of all possible transformations A, we study the transformations selected from S C A satisfying
S S (T, E A [T](() - x æ|ا<< cu Vx E X traing.
(1)
Under the smoothness constraint of images, where adjacent pixels have close intensities, such as small translations, crops, rotations, and for other pixel-wise augmentation methods such as sharpening, blurring, and color distortions (Cubuk et al. 2020), en is small. This model is also especially suitable for modelling sfate-of-thh--a augmentation techniques such as structured adversarial perturbation (Luo et al. 2020), in which pixel intensities are changed minimally. While in our analysis we focus on small perturbations En, our experiments use variety of strong and weak augmentations. Although other transformations such as data synthesis (Baluja & Fischer 2017 Mirza & Osindero 2014).
2

---

Under review as a conference paper at ICLR 2022
semantic augmentation (Wang et al. 2019). large translations, crops, rotations, and flips are still valid under the additive perturbation model, they can be more effectively modelled using matrices of linear transforms (Wu et al. 2020).
analyze in Appendix [33
In practice, multiple augmentations are generated for each example I; and cach augmented data point can be combination of multiple transformations, e.g. random cropping and rotating followed by horizontal flipping. The set of augmentations at iteration generating r augmented examples per data point can be specified, with abuse of notation, D Daug U (T (rrani),, Mtrain) ) where (Paugl= == rn and T trann)) transforms all the training data points with the set of transformations TŞ C at iteration L. We denote X auy = { TV (Xrain)) and yaug = { Dtrain }.
Let S(W, .)) be an arbitrary neural network with m vectorized (trainable) parameters W E RTT We assume that the network is trained using (stochastic) gradient descent with learning rate 1) minimize the squared loss L over the original and augmented training examples D' {Divain D Daug) with associated index set V*, at every iteration t:
L(w X)
C.(W' x.) ==)==
Σ (m..)))D
IIf(W' .x.) - -3il..
(2)
KEV
The gradient update at iteration i is given by W = W V/LLWW' X), VL(W", x) J X)U((" x)
(3)
where X (X train U angt and y¹ {ytrain J Yaug] are the set of original and augmented examples and their labels, J(W, X) E Raxm is the Jacobian matrix associated with f. and r' = f(W', x) - y is the residual. We further assume that I is smooth with Lipschitz constant L:
[J(W
J(W, æ;)1s (W,,;;)ls L x; x,حl
V VI, X.
(4)
This trivially holds for linear models, and when W is bounded, it holds for deep ReL.U, and generally for networks with any activation 6 with bounded derivatives ø' and ø" (Jordan & Dimakis 2020). Under this assumption, augmentation as defined in Eq. (I) results in bounded perturbations the Jacobian matrix. Le., for any transformation Tj E S, we have [[[WW, 2.)) J[W, (x:)))l Lep.
Using the shorthand notations J = J(W, Xtrain) and J J(W (Xtrotn)) we obtain J J E, where E is the perturbation matrix with 2 E| VnLEo.
3 DATA AUGMENTATION SPEEDS UP LEARNING
In this section, we analyze the effect of data augmentation on training dynamics of neural networks, and show that data augmentation can provably speed up learning. To do so, we leverage the recent results that characterize the training dynamics based properties of neural network Jacobian matrix and the corresponding Neural Tangent Kernel (NTK) (Jacot et al.] 2018) defined as θ J(W, (WW, x)" Formally (Arora al. 2019
Σ (1 (u,))) ) > (1--1 s7As)) (u,,))u
(5)
where O ---UA"=>> -im deurai is the eigendecomposition of the NTK. Although the constant NTK assumption holds only in the infinite width limit, [ee et al. 2019) found close empirical agreement between the NTK dynamics and the true dynamics for wide but practical networks, such as wide ResNet architectures (Zagoruyko & Komodakis, 2016). Eq. (5) shows that training dynamics depend on the alignment of the NTK with the residual vector at every iteration t. In particular, shrinkage of residuals along the directions associated with larger eigenvalues of the NTK is fast and happens early during the training, while learning along the space associated with the small eigenvalues is slow and happens later. In the following, we prove that for small perturbations eo. data augmentation speeds up training by enlarging smaller eigenvalues of the NTK, while decreasing larger eigenvalues with high probability. Intuitively, this can be characterized as decreasing the learning rate for dimensions with larger gradient and slightly increasing the learning in dimensions with smaller gradients, and having regularization effect by slightly perturbing the eigenvectors.
3

---

Under review as a conference paper at ICLR 2022
sighnetted
131
10-1
500
1073
401
2000 1i00 THe 1000
2000
6000
5008
1311
2004
10"
2500 500 104 1000
(a) MNIST/MLP Epoch 15 (b) C10/Res20 Epoch 15 (c) SVHN/Res32 Epoch 15 (d) MNIST/MLP Epoch
Figure 2: Histogram of the singular values of the Jacobian matrix for augmented original (a) MNIST/I hidden-layer MLP, (b) QIFARIO/ReSNe22/ and (c) SVH2/ (d) Effect of strong vs. weak augmentation MNIST/MLP initialization. We sampled and transformations from rotation, translation, contrast, brightness, etc. for normal vs. strong augmentation.
3.1 EFFECT OF DATA AUGMENTATION ON THE 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 cigenvalues of the NTK. To characterise the effect of data augmentation on singular values of the perturbed Jacobian J, rely on Weyl's theorem (Weyl 1912) stating that under bounded perturbations E, no singular value can move more than the norm of the perturbations. Formally, (o, -0,5= ||E||,, where o; and o; are the singular values of the perturbed and original Jacobian respectively. Crucially, data augmentation affects larger and smaller singular values differently. Let P be orthogonal projection onto the column space of J and Pi I I- P be the projection onto its orthogonal complement subspace. Then, the singular values of the perturbed Jacobian jr are ,.- = (o, + 14:)² + L2 where I < |P 2. and mmin E) S Ç < | E 22 Fiin the smallest singular value of J (Stewart 1979). Since the eigenvalues of the projection matrix P are either 0 or as the number of dimensions m grows, for bounded perturbations we get that on average /² = (1) and 2 = (mm) Thus, the second term dominates and increase of small singular values under perturbation is proportional
/m. However, for larger singular values, first term dominates and hence o; - o, = μ4z Thus in general, small singular values can become significantly and proportionally larger, while larger singular values remain relatively unchanged. Empirically, we observed that largest singular values often decrease by data augmentation.
Fig. 2 shows the effect of data augmentation on singular values of the Jacobian matrix for a 1 hidden layer MLP trained on MNIST, ResNet32 trained on SVHN, and ResNet20 trained on CIFAR10 10. As calculating the entire Jacobian spectrum computationally prohibitive, data subsampled from classes. For all datasets, we used the data augmentation techniques described in the Experiments section, such as rotation, translation, contrast, brightness. can be observed that for less diverse datasets such as MNIST that have smaller singular values in general, data augmentation can easily enlarge the singular values. On the other hand, for more diverse datasets such as CIFAR10 that generally have larger singular values, augmentation cannot change the singular values considerably. In both cases largest singular values became smaller.
The following Lemma characterizes the expected change to the eignvalues of the NTK.
Lemma 3.1 Data augmentation as additive perturbations bounded by small en results in the follow- ing expected change to the eigenvalues of the NTK:
E[ [[o?]= = of + a 2p))|[E||||11////
(6)
where p; = P(ō; < 0) is the probubility thut o, decreases as result of data augmentation. All the proof' can be found in the Appendix.
From Lemma 3.1 and Eq. we see that augmentation can speed up learning at every epoch by a1 2p.) E E112/3 along dimensions with smaller singular values for which pt S 0.5, and
by E 112//3 along dimensions with for which singular values do not change (p. R 0.5). It can also speed up learning along dimensions for which singular values decrease (p: > 0.5) as long as
E > 30, (2p, 1). This is mainly relevant for smaller singular values under strong augmentation.
3.2 EFFECT OF DATA AUGMENTATION ON THE EIGENVECTORS OF THE NTK
Next, we focus on characterizing the effect of data augmentation on the eigenspace of the NTK. Let the singular subspace decomposition of the Jacobian be T UEVT Then for the NTK,
4

---

Under review as a conference paper at ICLR 2022
have θ =
= = =UEVVVVU = UEU (since VTV- 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 0; are singular values of the Jacobian. Let the perturbed Jacobian be J = J + E, and
denote the eigengap "No min 0++1 : 1, 1....,r) where 0,+1 == O. Assuming Too 2 2 2.
a combination of Wedin's theorem ( (Wedin) 1972) and Mirsky's inequality (Mirsky) 1960) (the
counterpart of Weyl's inequality (Weyl 1912) for singular values) implies that
||u, ü. = 2 Bl1/
This result provides an upper-bound on the change of every left singular vectors of the Jacobian.
However 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 UVV* U, V. + U,, Vi" where U, associated with nonzero singular values, spans the column space of J. which is also called the signal subspace, and Un. 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 = ÚΣVT
U.E.V. + U,E.V 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,E," (Li et al. 1993). We that while singular vectors associated to larger singular values are more robust to data augmentation, singular vectors associated with small singular values are more affected. We also note that singular vectors more robust perturbations than singular values.
3.3 AUGMENTATION IMPROVES TRAINING AND GENERALIZATION
As discussed, data augmentation increases the smaller eigenvalues of the NTK with a high probability, and is likely to slightly decrease the largest eigenvalues. Besides, eigenvectors (in particular those as- sociated with larger eigenvalues) are generally more robust than eigenvalues. The following Theorem characterizes the expected improvement in the training dynamics resulted by data augmentation
Theorem 3.2 Gradient descent with learning rate n applied to a neural network with constant NTK and Lipschitz constant L, and data points ' Doug augmented with r additive perturbations bounded by to as defined in Eg. results the following training dynamics:
Ellyy- f(Xaug. W')l
(1-nn + Vroa(1 - 2p.) 2p))|E[+||
where E with | vnLcu is the perturbation to the Jacobian, and pt : P < 0) is the probability that o; decreases as a result of data augmentation.
Corollary 3.3 Under the same assumptions as in Theorem 3.2 let G be the minimum singular
value of Jacobian I associated with training data Xtrain then probability 1- 8 generalization error of the network trained with gradient descent on augmented data X Xang enjoys the following bound: aug
(amin + /nLLe)2 + +0 (lg (o8))
2
4 MOST EFFECTIVE SUBSETS FOR DATA AUGMENTATION
In Sec. 3 we discussed the effect of data augmentation on changing the alignment of the NTK with the residual, and how it improves training. Here, we focus on identifying the most effective subsets for data augmentation. Our key idea is to find subsets data points that when augmented, closely capture the alignment of the NTK (or equivalently the Jacobian) corresponding to the full augmented data with the residual vector, J(Wt, X( !"r'g" the subsets will change the NTK and its aligmment with the residual in similar way that of full data augmentation, and will result in similar improved training dynamics. Effectively, such augmented subsets be trained along with the full non-augmented data, or without it to further
T'ugg If such subsets can be found, augmenting only
5

---

Under review as a conference paper at ICLR 2022
Algorithm 1 CORESETS FOR EFFICIENT DATA AUGMENTATION
Input: The dataset D (a,, yt) Me) number of iterations T. Output: Output model parameters W
1: fort = 1..... do
2: S 0. ang = 0.
3:
for c E (1, .1. C do
4:
5% = gV.)
> Extract a coreset from class e by solving Eq. [I]
5:
Y/ = Liev. 11j= min yes Il (W", a.)r;- ".)r;-J"(WW JT By yryll & Coreset weights
6:
X:
ang (aau U (X
> Augment the coreset
7:
Pj -1//r
8:
Update the parameters W' uusing weighted gradient descent on X aug or (trrin U U Xaug).
speed up training. However, generating the full set of transformations X Xun is often very expensive. This is exacerbated in the case of strong augmentations. 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 J'W", (trrai)) can closely estimate the alignment of the Jacobian of the full augmented data and the corresponding residual (W,, X (aug)) Jrag- Thus, the most effective subsets for augmentation can be directly found from the training data. Formally, subsets S weighted by 7 that capture the alignment of the full Jacobian with residual by and error of at most & can be found by solving the following optimization problem:
arg min|S|
s.t.
1|J (W', X')r²*
(iagg(>s)T"" (W", X')rr'lls
(10)
SCV
Solving the above optimization problem is NP-hard. However, as we discuss in the Appendix [A.6] near optimal subset can be found by minimizing the Frobenius norm of matrix Gs. in which the tth row contains the euclidean distance between data point and its closest element in the subset S, in
the gradient space. Formally, [Gsl. msnyrs |J ('"W,, )r,r, - J (W', , )rylll Intuitively. such subsets contains the set of medoids of the dataset in the gradient space, where the medoids of dataset are defined as the most centrally located elements in the dataset (Kaufman et al. 1987). The weight of every element j E S is the number of data points closest to it in the gradient space, i.., %/- Evev Ußj = arg y (ITTTTW'' .2:)r; I (W', .y ..y)rr [I]. The set of medoids can be found by solving the following submodulan cover problem:
S arg minggv|S]
s.t. C- C-1|Gs|1r2
(11)
where C' ||Gs|l F is constant. The classical greedy algorithm provides a logarithmic approxima- tion for the above submodular maximization problem, i.e., |S| (1 + Ln(n)). It starts with the empty set So = V. and at each iteration т. it selects the training example E V that maximizes the marginal F(S, U {e)) F(S,). Formally, S, = S U {arg ma (e]SS,
gain F(e]S O(nk) computational complexity of the greedy algorithm can reduced to O(n) using randomized methods (Mirzasoleiman et al.] 2015), and further improved using lazy evaluation (Minoux] 1978) and distributed implementations (Mirzasoleiman et al. 2013). 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 (Katharopoulos & Fleuret 2018). The above upper-bound is only marginally more expensive than calculating the value of the loss, and hence the subset can be found efficiently. Better approximations can also be obtained by considering earlier layers in addition to the last two, at the expense of greater computational cost.
The
At every iteration I. during training, we select a coreset from every class e E [C] separately, and apply the set of transformations {TH) Vr=1 only to the elements of the coresets, i.c., Xuuy [U (Xxs) }} We divide the weight of every element j in the coreset equally among its transformations, i.c. the final weight Pf = 7 /r if E St. We apply the gradient descent updates in Eq. (3) to the weighted Jacobian matrix of X X!
aug or X (Xtrain U U (viewing p² as p² E RR") as follows:
W++ W' (diag(p")) (W",))))""))))))) x²))² T 7
(12)
A set function F:2V + Rt is submodular F(SU(e)) F(S) > (TU(()))F((T) for any S SCTCV
and E V \ T. F is monotone if F(e(S)= 2 0 for any e V S and VV.

---

Under review as a conference paper at ICLR 2022
Test acturayy
68
-5
Imot Impropeeenn
615
searary
52%
25
50
75
200
225
150
375
200
23
30
73
100
125
100
175
20
Fpoom
Fporh
Fraction selectad
Loss intersection
(b) Improvement
(c) Coresets vs random
Figure 3: Training ResNet20 on full data and augmented coresets extracted from CIFARIO. (a) Intersection between elements of coresets of size 30% and maximum loss subsets of the same size. The intersection increases after the initial phase of training, (b) Accuracy improvement for training on full data and augmented coresets over training on full data and augmented max-loss points. (c) Accuracy vs. fraction of data selected for augmentation during training Resnet20 on CIFAR1O.
The pseudo code is given in Alg. [ The following Lemma upper-bounds the difference between the alignment of the Jacobian and residual for augmented coreset vs. full augmented data.
Lemma 4.1 Let S be a coreset that captures the alignment of the full data NTK with residual with error of at most & in Eq. (4). Augmenting the coreset with perturbations bounded by 6o S n I
captures the alignment of the fully augmented data with the residual by an error of at most
1 (W', Xrug)r diag(p ('' Xrong) (VL).
(13)
Importantly, since the augmented coresets capture the alignment of the Jacobian of fully augmented data with residual, they can be trained on in absence of the full data to gain more speedup. This not the case for existing methods such max-loss. Besides, the gradient of noisy labeled data points do not cluster in the gradient space (Mirzasoleiman et al. 20205). Thus, only clean data points are selected for augmentation. This results an improved performance, we will show in Sec. 5.1
4.1 CORESET VS. MAX-LOSS STRATEGY FOR DATA AUGMENTATION
In the initial phase of training the NTK goes through rapid changes, which determines the final basin of convergence and network's s final performance (Fort et al.) 2020). Regularizing deep networks by weight decay or data augmentation mainly affects this initial phase and matters little afterwards (Golatkar et af. 2019). Crucially, augmenting coresets that closely capture the alignment of the NTK with the residual during this initial phase results in considerable increase in the speed of convergence and generalization performance. On the other hand, augmenting points with maximum loss early in training decreases the alignment between the NTK and the label vector and slows down learning and convergence. Fig. [blillustrates the superior performance of coreset vs max-loss augmentation. After this initial phase (highlighted in green in Fig. 3a when the network have a good prediction performance, the gradients for the majority of data point becomes very small. Here, the alignment is mainly captured by the elements with the maximum loss. Hence, as training proceeds, the intersection between the elements of the coresets and examples with maximum loss increases (c.f. Fig. Ba).
The following Theorem characterizes the training dynamics of training on the full data and the augmented coresets, using the additive perturbation model in Eq. I
Theorem 4.2 Let Li be 8-smooth, L be X-smooth and satisfy the c-PL condition, that is for O. (VL(W) ||2 2 (L(W) for all weights W. Let f be Lipschitz in X with constant L/, and T. max L, L. Let Go be the gradient at initializaion, o Guxx the maximum singular value the coreset Jacobian at initialization. Choosing en S FmnvVia and running SGD on full data with augmented coreset using constant step size
xB. we get the following convergence bound:
Va (1 (1-20) 2Go + +
C toun (W
(14)
Tmax
7

---

Under review as a conference paper at ICLR 2022
Table I: Accuracy improvement by augmenting subsets found by our method vs, max-loss and random, over improvement of full data augmentation (F.A.) compared to no augmentation (N.A.). The table shows the results for training on CIFARIO with ResNet20 (C10/R20), SVHN with ResNet32 (SVHN/R32), and CIFAR 1--mmmbamaaaee with ResNet32 (CI0-IB/R32), with R
20.
Dataset
N.A.
F.A.
Random
Max-loss
Ours
Acc
Acc
5%
10%
30%
3%
10%
30%
5%
10%
30%
CI0/R20
89.46
93.50
21.8%
39.9%
65.6%
32.9%
47.8%
73.5%
34.9%
51.5%
75.0%
C10-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 R33
95.68
97.07
5.8%
36.7%
64.1%
35.3%
49.7%
76.4%
31.7%
48.3%
80.0%
The above Theorem shows that training on full data and augmented coresets converges with the same rate as of training on the fully augmented data, to a close neighborhood of the optimal solution. The size of the neighborhood depends capturing the alignment of the full augmented data with the residual derived in Lemma [ The first
(1) the error of the coreset in Eq. 4 and (2) the error in
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 on the augmented coresets, and augmentations modelled as arbitrary linear transformations using linear model (Wu al. 2020) in Appendix B. B.3
EXPERIMENTS
Setup and baselines. We evaluate the performance of our approach in two different settings. First, we consider the case where full data is small enough to be trained on. Here, we study the effect of augmenting coresets on the generalization performance of clean and noisy labeled data. Next, we focus on the case where the full training data is too large to be trained on. In this setting, we train only on the augmented coresets. both cases we use subsets with maximum loss, and random subsets as baselines. For all methods, we select new augmentation subset every R epochs. We note that while the original method (Kuchnik& & Smith (018)) selects points based on loss a fully trained model, to maximize fairness, our max-loss baseline selects new subset every subset selection step.
Data and augmentation. We apply our method to training ResNet20 and Wide-Resnet-28- on CIFAR1O, and ResNet32 CIFAR1O 10-IMBB--MB (Long- Tailed CIFARIO with Imbalance factor of 100 following (Kim & Kim| (020)) and SVHN datasets. All models are trained for 200 epochs using SGD with 0.9 momentum and learning rate warm-up. We use the strong augmentation proposed by (Wu et al. 2020) to generate distinct augmented examples by randomly sampling 2 augmentations from the same set used by (Cubuk et al. 2019 2020) to apply each example. A new of default augmentations (random crop and horizontal flip) are also applied every R epochs to the original data. We individually measure average time taken for subset selection, gradient descent, and subset augmentation per epoch to compute total training time and speedups. All results are averaged over 5 runs using an Nvidia A40 GPU, and full results are reported in the Appendix.
5.1 TRAINING ON FULL DATA AND AUGMENTED SUBSETS
Table I demonstrates the accuracy improvement resulted by augmenting subsets of size 5%, 10% and 30% selected by our method vs. max-loss and random over full data augmentation. We observe that augmenting coresets effectively improves generalization, and outperforms augmenting random
Spocduu bacor
Accursrr gain (1))
Sponthop facton
10
speediup
100
rend-improo
kee improve con Impress
mnnopeeddpp
come-paaddp
10
80
30%
3,2%
30%
(a) CIFAR Ne0 (b) CIFAR10/ReSNei2
(c) SVHN/ResNet22
(d) SVHN/ResNet32
Figure Accuracy improvement and speedups by augmenting subsets found by our method vs. max- loss and random, over improvement of full data augmentation (F.A.) compared to augmentation (N.A.). The Figure shows the results for CIFARIO with ResNet20 in terms of (a) speedup and (b) accuracy, and results for SVHN with ResNet32 in terms of (c) speedup and (d) acuracy.
8

---

Under review as a conference paper at ICLR 2022
Table 2: Training ResNet20 on CIFARIO with 50% label noise, with R 20. Accuracy without
augmentation is 70.72 + 0.20 and the accuracy of full data augmentation is 75.87 = 0.77. Note that augmenting 50% subsets outperforms augmenting the entire data (marked as **)
Subset
Random
Loss
Ours
10%
72.32 0.14
71.83 + 0.13
73.02 + 1.06
30%
74.46 + 0.27
72.45 + 0.48
74.67 + 0.15
50%
75.36 + 0.05
73.23 + 0.72
76.20 = 0.75**
Table 3: Training ResNet20 and WideResnet-22- CIFARIO using small subsets, with R = 1.
Training and augmenting subsets selected by max-loss performed poorly and did not converge.
Model
Subset
Random
Ours
Loss
No Aug.
Aug.
Improv.
No Aug.
Aug.
Improv.
Aug.
0.1%
31.7
+ 3.2
33.5 + 2.7
5.7%
29.6 + 3.8
37.8
4.5
27.7%
< 15%
0.2%
35.9
+ 2.1
42.7
3.9
18.9%
33.6
3.2
45.1
- 2.3
34.2%
< 15%
ResNet20
0.5%
51.1 + 2.3
58.7 + 1.3
14.9%
55.8 + 3.1
63.9
+ 2.1
14.5%
< 15%
1%
66.2 1.0
74.4
12.4%
65.9
+ 4.0
74.7
1.1
13.4%
< 15%
WRN-28-10
1%
$1.3444
57.7 0.8
5.9%
59.9 +: 2.4
62.1 + 3.1
3.7%
15%
and max-loss subsets across different models and datasets. Fig. 5 shows the speedup vs. test accuracy of augmenting subsets different size selected from CIFARIO and SVHN by our method vs baselines. We see that our method outperforms the bascline while providing similar speedup as that of max-loss. On SVHN, we achieve 80.0% of the augmentation accuracy gain by augmenting only 30% size subsets while providing 2.2x speedup, while max-loss only achieves 76.4% with the same speedup. In the Appendix, we also show that our approach is effective when trained with full data even for small augmentation subset sizes of 0.2% and 0.5% selected every epoch.
Augmenting noisy labeled data. Table 2 shows the result of augmenting coresets vs. max- and random subsets of different sizes selected from CIFARIO with 50% label noise for training ResNet20. Note that augmenting coresets selected by our method not only outperforms max-loss and random, but provides superior performance over full data augmentation. This clearly shows the effectiveness of the coresets in capturing the aligmment of the NTK with the residual of clean data points.
5.2 TRAINING ONLY ON AUGMENTED SUBSETS IN ABSENCE OF FULL DATA
We now evaluate the effectiveness of our approach for training only on the augmented coresets. Our main goal here show the accuracy improvement resulted from augmenting the coresets. In particular instead of focusing on the quality of the coresets, we aim at showing the effectiveness of the coresets for augmentation. 3 shows the test accuracy for training ResNet20 and Wese-ResNet on CIFAR10 when we only train on small augmented coresets of size 0.1% to 1% selected at every epoch (R = 1). We see that while the non-augmented coreset performs worse than random in most cases, the augmented coresets outperform augmented random subsets by large margin. That is, the improvement from augmenting the coresets is significantly larger than random data points. This clearly shows the effectiveness of augmenting the coresets, and the importance of capturing the alignment the NTK with the residual for data augmentation. Note that training on the augmented max-loss points did not converge in absence of full data. Finally, Fig. 3c shows the fraction of data selected for augmentation during training of ResNet20 on CIFÁR10. We see that the coresets achieve superior performance by carefully selecting certain data points more often than others.
CONCLUSION
We showed that data augmentation improves training and generalization by enlarging the smaller singular values of the neural network Jacobian. Then, we proposed framework to iteratively extract small subsets of training data that when augmented, closely capture the aligmment of the fully augmented Jacobian with the label/residual vector. We showed the effectiveness of augmenting the coresets selected by our method to provide a superior generalization performance when added to the full data, in presence of noisy labels, or standalone subset.

---

Under review as a conference paper at ICLR 2022
7 REPRODUCIBILITY STATEMENT
Our experimental setup along with training details are introduced in Section 5. Full results containing standard deviations can be found in Appendix C. All code use for our empirical results are also available in the supplementary material, with along with instructions on how to run them.
All proof's for non-trivial theoretical results main paper can be found in Appendix A, while additional theoretical results and their respective proofs can be found in Appendix B.
REFERENCES
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. International Conference Machine Learning, pp. 322-332. PMLR, 2019.
Shumeet Baluja and Ian Fischer. Adversarial transformation networks: Learning to generate adver- sarial examples. arXiv preprint arKiv: 770.009387 2017.
Raef Bassily. Mikhail Belkin, and Siyuan Ma. On exponential convergence of sgd in non-convex over-parametrized learning. arXiv preprint arXi:: 2018.
Chris Bishop. Training with noise is equivalent to tikhonov regularization. Neural computation, (1):108-116, 1995.
Shuxiao Chen, Edgar Dobriban, and Jane H Lee. Invariance reduces variance: Understanding data augmentation in deep learning and beyond. arXiv preprint 19X. 10905, 2019.
Ekin D Cubuk, Barret Zoph. Dandelion Mane, Vijay Vasudevan, and Quoc V Le. Autoaugment: Learning augmentation strategies from data. Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, pp. 113-123, 2019.
Ekin D Cubuk, Barret Zoph, Jonathon Shlens, and Quoc V Le. Randaugment: Practical automated data augmentation with reduced search space. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops, pp. 702-703, 2020.
Tri Dao, Albert Gu, Alexander Ratner, Virginia Smith, Chris De Sa, and Christopher Ré. A kernel theory of modern data augmentation. In International Conference on Machine Learning, pp. 1528-1537, PMLR, 2019.
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.
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: 92:10678-10688 2019.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. arXiv preprini
2018.
Matt Jordan and Alexandros G Dimakis. Exactly computing the local lipschitz constant of relu networks. arXiv preprint arXiv:2003.01219, 2020.
Angelos Katharopoulos and François Fleuret. Not all samples are created equal: Deep learning with importance sampling. In International conference on machine learning, pp. 2525-2534, PMLR, 2018.
I. Kaufman, PJ Rousseeuw, and Y Dodge. Clustering by means of medoids in statistical data analysis based on the, 1987.
Byungju Kim and Junmo Kim. Adjusting decision boundary for class imbalanced learning. IEEE Access, 8:81674-8168 2020.
10

---

Under review as a conference paper at ICLR 2022
Michael Kuchnik and Virginia Smith. Efficient augmentation via data subsampling. In International Conference on Learning Representations, 2018.
Jachoon Lee, Lechao Xiao, Samuel S Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve linear models under gradient descent. In NeurIPS, 2019.
Fu Li, Hui Liu, and Richard Vaccaro. Performance analysis for doa estimation algorithms: unifica- tion, simplification, and observations. IEEE Transactions Aerospace and Electronic Systems, 29(4):11 1011110--441 1993.
Calvin Luo, Hossein Mobahi, and Samy Bengio. Data augmentation via structured adversarial perturbations. arXiv preprint arXiv:201 1.03010, 2020.
Michel Minoux. Accelerated greedy algorithms for maximizing submodular set functions. In Optimization techniques, pp. 234-243. Springer, 1978.
Leon Mirsky. Symmetric gauge functions and unitarily invariant norms. The quarterly journal of mathematics, 11(1):50-59) 1960.
Mchdi Mirza and Simon Osindero. Conditional generative adversarial nets. arXiv preprint arXiv:1411.1784 2014.
Baharan Mirzasoleiman, Amin Karbasi, Rik Sarkar, and Andreas Krause. Distributed submodular maximization: Identifying representative elements in massive data. In Advances in Neural Information Processing Systems, pp. 2049-2057 2013.
Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, Amin Karbasi, Jan Vondrák, and Andreas Krause. Lazier than lazy greedy. In Twenty-Ninth AAAI Conference Artificial Intelligence, 2015.
Baharan Mirzasoleiman, Jeff Bilmes, and Jure Leskovee. Coresets for data-efficient training of machine learning models. In International Conference Machine Learning, pp. 6950-6960. PMLR, 2020a.
Baharan Mirzasoleiman, Kaidi Cao, and Jure Leskovee. Coresets for robust training of deep neural networks against noisy labels. Advances in Neural Information Processing Systems, 33, 2020b.
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, pp. 5321-5330. PMLR, 2019.
Connor Shorten and Taghi M Khoshgoftaar. A survey image data augmentation for deep learning. Journal of Big Data, 6(1):1-48, 2019.
GW Stewart. A note on the perturbation of singular values. Linear Algebra and Its Applications, 28: 213-216, 1979.
Stefan Wager, Sida Wang, and Percy Liang. Dropout training adaptive regularization. arXiv preprint arXiv:1307, 1307.1493. 2013.
Yulin Wang, Xuran Pan, Shiji Song, Hong Zhang, Gao Huang, and Cheng Wu. Implicit semantic data augmentation for deep networks. Advances in Neural Information Processing Systems, 32: 12635-12666 2019.
Per- Wedin. Perturbation bounds connection with singular value decomposition. BIT Numerical Mathematics, 12(1):99-111 111, 1972.
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): 441-479, 1912.
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. pp. 10410-10420. PMLR, 2020.
11

---

Under review as a conference paper at ICLR 2022
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. In British Machine Vision Conference 2016. British Machine Vision Association, 2016.
12

---

Under review as a conference paper at ICLR 2022
SUPPLEMENTARY MATERIAL: DATA-EFFICIENT AUGMENTATION FOR TRAINING NEURAL NETWORKS
A PROOF OF MAIN RESULTS
A.1 PROOF FOR LEMMA 3.1
Proof Let 6; = ā; og, where P(o, < 0) = Pt- Assuming uniform probability between 0, and between 0 to
E
to
| EEI, we have pdf (;(2)) for d;:
if E
<
E
(x(x)=
s E|
(15)
T 0,
otherwise
Taking expectation,
E(ö; o,) = E(6,)) = Ipr(r)dd
(16)
-00
||
1
Pi
dx
dx
(17)
E
[E]
E
E
Pj
(1
P:)
E
(18)
2
2
(1 2p:)
E||
(19)
We also have
E(6))
(20)
||
2.2
Ps
dx
x.
Pt dr
(21)
E
Jo
1 E
[F
|
P
(1
Pt)
|E|
1
(22)
3
3
|
(23)
3
Thus, we have
E(τ.) F(ō?)
(24)
E((o: + 6,)3)
(25)
F(a? 20;0; + 52)
(26)
of + E2,, + E[6?]
(27)
of + 20; (1 (1-2p;) |E|
|
(28)
2
|
of + +,,(1 - -2p:) |E||+
(29)
3
13

---

Under review as a conference paper at ICLR 2022
A.2 PROOF OF THEOREM 3.2
Using Jensen's inequality, have
lly f(Xaug ) =E
n),)) (u ²)²= =e
(30)
E Σ (1 (
(31)
Σ
E (1 - (-))))
(32)
1=1
Σ (1 n/E [X,])>0 )2
(33)
1=1
Σ (1 ,yE {2,))20 )
(34)
==
Σ 1 - 17 o0 +0:l - 21:) |6
3 ))
(35)
2m1
A.3 PROOF OF COROLLARY 3.3
Under the assumptions of Theorem 5.1 of Arora et al. (2019). i.c. where the minimum eigenvalue
of the NTK is Amin (JJ") Z Ao for constant À > O, and training data X of size sampled i..dd from distribution D and 1-Lipschitz loss L, we have that with probability 8/3, training the
over-parameterized neural network with gradient descent for & 2 Ω nAo log " iterations results in the following population loss LD (generalization error)
2y (JIT) +0
log Agd
LD(W' X) S
(36)
with high probability of at least 5 random initialization and training samples.
Hence, using Amin min to denote minimum eigen and singular value respectively of the NTK corresponding to full data, we get
2 1
1 z) log
Divain (W', "Xtrain) S
Amin
(37)
n
2
1
<
+
O
1log
(38)
iin
For augmented dataset X Xang- we have S 5,tt VnL hence the improvement in the generalization error at most
D (W', Xaug) S V (amin + /nLLg)² +0 [0gg] (108 !
2
(39)
Combining these results, obtain Corollary
3.3
14

---

Under review as a conference paper at ICLR 2022
A.4
PROOF OF LEMMA 4.1
Proof
|| (W'xXaug)r ddag)'- diag(p')JJ'(W (W', ggguus rrll
(40)
= =1(3" +1' ,X) + E)r ( (s) + Es)rsl
(41)
S 11[T"(WW X)r diag(p')J'( Xs)rs) + Er - Esrsl
(42)
II(TT(Wt (W X)r diag dia |r]|++++++++||
(43)
Applying definition of coresets, obtain
II (W*, X)r - ( J Xs)rs)|I||Br|||]BBB
(44)
+ Er|+||
(45)
< 2n Lco
(46)
S
(47)
A.5 PROOF THBOREM 4.2
Proof In this proof, as shorthand notation, we x and Xtrain interchangeably. We further use X, to represent the coreset selected from the full data, and X Xe.., to represent the augmented coreset.
By Theorem 1 of Bassilyet al. (2018), under the a-PL assumption for L and interpolation assump- tion (i.e. for every sequence W W such that lim, L(W', x) = O, we have that the loss for each data point lim L(W', ,.;; 0), the convergence of SGD with constant step size is given by
FL/VL(W X s tomm )1 1 (1-9) L(W". X Xiteme)
(48)
1 (1 2 ) |VV(WW" x x+
(49)
15

---

Under review as a conference paper at ICLR 2022
Using Jensen's 's inequality, we have
V X Xy+caxx)ll I111
(50)
VEIIVZ(WW X xftemm))1?
(51)
$ 1
Va (1 -1
2 |V x
(52)
$ 1
(1- ) (IVE(W") [ xl)
(53)
Va
1 (1- an)
S
(Go + [I] X.) + By
- (W", 6))))
(54)
Va
1 (1- an
(55)
Va 2
(Go + [I(J(W) xx) + E)" (y - f(W". V.f( ,x)" c(c'
(56)
V@ (1 (1- (1-2) (1-2) (Go + VL Xx)
1
(W. e+ O(E c))+
(57)
Ely- f(Wo, X. + E))
(58)
$ v@ (1 (1- amm
1
(1-2) 2
(Go + AVL(WO,X, - -(J(WO, (()) (V=,( x.) c (|
(59)
V21 El)
(60)
1 1 - )
(Go + ||V((W" tmxx + o max O(ne)) + vnncc)
(61)
v@
1 (1 anl
(Go |VL(WW xx) m I./neo + m max ((ne)) / VnnTea)
Va
2
(62)
1
1 -
am
(2Gg + + mmax Lyneo + m maxx (nn))) + v2nLo))
(63)
va=
2
A.6 FINDING SUBSETS
Let S be a subset of training data points. Furthermore, assume that there is mapping Tw.S V + S that for every W assigns every data point i V its closest element S, i.e. j == ( arg maxyes Siyr (W), where Sty (W)= = C ||JTT (W*, æz)r; - JJ J"(W', æ,)r is the similarity between gradients of and j. and C maxiy Sty (W) is a constant. Consider matrix Gan.s Raxm, in which every row contains gradient of a (i), i.e., [Gr..s]..
JJ (W', Tx s(i) TT (i)- The Frobenius norm of the matrix G provides an upper-bound on the error of the weighted subset S in capturing the alignment of the residuals of the full training data with the Jacobian matrix. Formally,
I Xtrain - Ys JT JTTTTTTWW''' (W', [ ss Srssss |
(64)
where the weight vector 7s- E RI contains the number of elements that are mapped to every element j E S by mapping Tw.S, i.e. %/ Eiey 1[T j). Hence, the set of training points that closely estimate the projection of the residuals of the full training data on the Jacobian spectrum can be obtained by finding subset S that minimizes the Frobenius norm of matrix G G
16

---

Under review as a conference paper at ICLR 2022
B ADDITIONAL THEORETICAL RESULTS
B.I CONVERGENCE ANALYSIS FOR TRAINING ON THE CORESET AND ITS AUGMENTATION
Theorem B.1 Let Li be B-smooth, L be X-smooth and satisfy the a-PL. condition, that is for o > 0, IVC(W, x)2 2 aL(W, ,X) all weights W. Let & upper-bound the normed difference in gradients between the weighted coreset and full dataset. Assume that the network f(W, XX) is Lipschitz in W. X with Lipschitz constant L and L' respectively. and L = max L, L'}. Let Go the gradient over the full dataset at initialization, Fmax the maximum Jacobian singular value at initialization. Choosing perturbation bound S VmnseLLn where max is the maximum singular value of the coreset Jacobian and n is the size of the original dataset, running SGD on the coreset and its augmentation using constant step size AB. we gel the following convergence bound:
(1- Va
1 -
VLWW' Xot Ill
S
2Go 22
(65)
T
where X Xotcaug represents the dataset containing the (weighted) coreset and its augmentation.
Proof As in the proof for Theorem 4.2 we begin with the following inequality
|1 < 1
aq --077
L(W", "WW,Xotee Xotemgg)
(66)
2
1 (1
2 ) |V x
$ a
(67)
Thus, write
V X Xotemee)ll 1l
(68)
FI1I L(W' X Xotcmug) 12]
(69)
Va (1-
am
/VL(W X )|l
(70)
2
1
(1-
amp
(XIII/CW X II)
(71)
Va
2
1
(1
(Go + + IKJ[WO X.) + E) Xx +))il)
(72)
Va
2
The rest of the proof is similar to that of Theorem 4.2
B.2 LEMMA FOR EIGENVALUES OF CORESET
The following Lemma characterizes the sum of eigenvalues of the NTK associated with the coreset.
Lemma B.2 Let & be an upper bound of the normed difference in gradient of the weighted coreset and the original dataset, Lee. for full data X and its corresponding coreset Xs with weights 7ss. and respective residuals r, Ts, we have the hound I| (W', X))r= TTT (Wi, Xs)r'lls ç. Let {>; kk be the eigenvalues of the NTK associated with the coreset. Then we have that
|ITT (W', "T", 1I-
Ir'sll
Proof Let singular values of coreset Jacobban be o, Let JT (W' X)r' = I (Yss'ss +Es where |[E>||< E
17

---

Under review as a conference paper at ICLR 2022
Taking Frobenius norm, we get
Ins (W', [s)r<(==13>> , .x)rt Esll
(73)
+ *1yss (W (WW xs) 1 ,))r' - Es
(74)
=I (W" xs)112 |
(W', X)r Esll
(75)
|rr
(W', X)r Elll
(76)
||'sl|
1T X)rr - Esll
(77)
rs'/l
|| (W', X)r'111 by reverse triangle inequality
(78)
|r'/l
We can make the following observations: For overparameterized networks, with bounded activation functions and labels, e.g. softmax and one-hot encoding. the norm of the residual vector is bounded, and the gradient norm is likely to be much larger than residual, especially when dimension of gradient large. In this case, the Jacobian matrix associated with small weighted coresets found by solving Eq. (1),, have large singular values.
B.3 AUGMENTATION AS LINEAR TRANSFORMATION: LINEAR MODEL ANALYSIS
We introduce simplified linear model to extend theoretical analysis to augmentations modelled as linear transformation matrices F' applied to the original training data. These augmentations are also originally studied by Wu et al. (2020). In this section, we specifically study the effect of these augmentations using linear model when applied to coresets.
B.4 LINEAR CASE (1 INPUT LAYER, 1 OUTPUT LAYER)
Lemma B.3 (Augmented coreset gradient bounds: Linear) Let f be simple linear model with weights W E RaxC where f(W xi;) W x; trained on mean squared loss function C. Let F E RRdxd be common linear augmentation matrix with norm [[]]] with augmentation xr. given by Fx; Let coreset be of size l and full dataset be of size n. Further assume that the predicted label of x;; and its augmentation Fx; are sufficiently close, i.e. there exists w such that W (T(Fx.)) <'' x. + zú, || w Vi. Let & upper-bound the normed difference in gradients between the weighted coreset and full dataset. Then, the normed difference between the gradient of the augmented full data and augmented coreset is given by
VL(W I
Yoj VL(W, 2
AUE I [F]((E + Vdnw)
==1
for some (small) constant &.
Proof By our assumption, we can begin with,
VLWW x.)
Yaj VL(W ..,))ls g
(79)
BEV
Furthermore, by Mirzasoleeima et al. (2020a), we know that sum of the coreset weights Ye, is given A=1
by Σ}=1 Nag S n.
18

---

Under review as a conference paper at ICLR 2022
Hence,
VC(W
(u))
Σ j=1
7o. VL(W, 23yee) ||
(80)
NEV
Σ
(J(W. ( ))² ( (Fa:)) yal Σ Yi, (W, ( (F*()x - Us,ll (81)
(FIx,)
EV
Σ EV
Fx: W (Fx;) - -vil Σ
Yas
Fæ.s (F - -Vssl
(82)
j=1
k
= FF) Σ
Ei W 2; - y-) F
Σ
Yss Tssy
(WT Diy + 2: yays Voy))l
(83)
EVV
j=1
|F
VL(WW 23)
Ys3
VL(W, Fay))
F
Ys. Tsy 2zg
(84)
LVV
j=1
j=1
I [FII VL(W, x3)
Ysg
VL(W, FL(W...,)1l =,,,|I++|FI|1
Ysy 22
(85)
EEV
j=1
S |I Fll
(86)
= (F + vdnw)
(87)
Corollary BA In the simplified linear case above, the difference gradients of the full training data with its augmentations (VL(W, X (+aug)) and gradients of the coreset with its augmentations LVL(W, Xotcoug)) )) can bounded by
VVL(W, Xstaug) VL(W, X Xeteumy))l IIS [[F] 1)g + Vdl
Proof Applying Eq.
79 and Lemma
B.3 we obtain
VVC(W X (aug)) VL(W, X Xctcoun)II
(88)
[[ X,) + VLWW, Xaug)) (VL(W, X.) + VL(W, x X
(89)
[[VCCWW xx) - VL(W, xx)) + (VL(W, Xang) - VL(W, X Xeaug)
(90)
< C(W ,X)) VLWW, IVV X Xang) VL(W, X X
(91)
- [|F]](E + Vdnw)
(92)
(1]1|++)E + VdllElmm
(93)
Theorem B.5 (Convergence of linear model) Let f be a linear model with weights W and aug- mentation be represented by the common linear transformation F. Let L, be 8-smooth, E be X-smooth and satisfy the a-PL condition, that is for a > LIVL(W x)I1² 2 aL(W. X) for all weights W. Let upper-bound the normed difference in gradients between the weighted coreset and full dataset and w bound W (Fa;) = W' + Zú, || w Vi. Let G2 be the gradient over the full dataset and its augmentations at initialization. Then, running SGD on the size k coreset with its augmentation using constant step size 1) = >B we get the following convergence bound:
a
1
(1--m)
(c& (IFF++++ + Vd(lFl(W)
VLWW X Xotcmme Ill 5
Ta
19

---

Under review as a conference paper at ICLR 2022
Proof From Bassilyct al. 2018 we have
E[IV X eor
)1 5
(1-2)
am)
L(W", Xoteoa))
(94)
2
x 1 -
|VL(W x
(95)
2
(96)
Using Jensen's 's inequality, we have
EllV X X
(97)
F]IVL(WW Xxrrmu)) }13
(98)
1
(1 (1- m |VL(WW X Xo+cmmx)l
2
(99)
Va
1
(1- ) )= (G' + (11F1++1)E (d]l
(100)
Va
where the last inequality follows from applying Corollary B.4
C APPENDIX C: EXTRA EXPERIMENTS
C.I FULL RESULTS FOR TABLE
This section contains full experiment results including standard deviations and the full augmentation benchmark for Table [ Augmenting coresets of size 10% achieves 51% of the improvement obtained from augmentation of the full data and further enjoys 6x speedup in training time on CIFAR 10. This speedup becomes more significant when using strong augmentation techniques which are mostly computationally demanding, especially when applied to the entire dataset.
Table 4: Supplementary table for Table D ResNet32, CIFAR CIFAR10- I-mallaace + ResNet32 including standard deviation errors and full dataset augmentation accuracy.
Test accuracy CIFARIO ResNet20, SVHN +
Method
Size
CIFAR10
CIFAR10-IMB
SVHN
None
0%
89.46 + 0.17%
87.08 # 0.50%
95.676 = 0. 108%
5%
90.34 + 0.18%
88.48 + 0.25%
95.760 = 0.084%
Random
10%
91.07 + 0.13%
89.52 1 0.15%
96.187 = 0. 0.112%
30%
92.11 + 0.12%
91.11 1 0.1
96.569 = 0.073%
5%
90.79 1 0.19%
88.77 1: 0.35%
96.165 + 0.108%
Max-Loss
10%
91.39 1 0.08%
89.22 1 0.48%
96.370 + 0.076%
30%
92.43 1 0.07%
91.11 1 0.25%
96.735 = 0.068%
5%
90.87 + 0.05%
89.10 + 0.41%
96.121 0.055%
Coreset
10%
91.54 1 0.19%
89.75 1 0.52%
96.354 = 0.091%
30%
92.49 + 0.15%
91.12 1 0.26%
96.791 + 0.051%
100%
93.50 + 0.25%
92.48 + 0.34%
97.068 = 0.030%
C.2 SPEED-UP MEASUREMENTS
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 speed-up to the max-loss policy and random approach respectively, our resulting accuracy outperforms these two approaches. For example, for SVHN/Resnet22 using 30% coresets, sacrifice 10% of the speed-up to obtain an additional 24.8% of the gain accuracy from full data augmentation when compared to a random subset of the same size.
20

---

Under review as a conference paper at ICLR 2022
Table 5: Speedup on CIFARIO + ResNel20 (CI0/R20), SVHN + ResNet32 (SVHN/R32).
Dataset
Full Aug.
Ours
Max loss.
Random.
100%
5%
10%
15%
20%
25%
30%
30%
30%
C1O/ / R20
1x
7.93x
6.31x
4.46x
4.27x
3.41x
3.43x
3.48x
4.03x
SVHN R32
1x
5.35x
3.93x
3.40x
2.80x
2.49x
2.18x
2.21x
2.43x
C.3 TRAINING ON FULL DATA AND AUGMENTING SMALL SUBSETS RE-SELECTED EVERY EPOCH
We apply our proposed method select new subset for augmentation every epoch (i.e. using R = 1) and compare our results with other approaches using accuracy and percentage of data not selected (NS). We see that while the max-loss policy selects small fraction of data points over and over and random uniformly selects all the data points, our approach successfully finds the smallest subset of data points that are most crucial for data augmentation. Hence, can achieve superior accuracy than max-loss policy, while augmenting only slightly more examples. This confirms the data-efficiency of our approach. This is especially evident when using corescts of size 0.2%. Furthermore, despite the random bascline using a significantly larger percentage of data, it is outperformed by our approach in both data-efficiency and accuracy. We emphasize that results in this table is different from that of Table 4 default augmentations on the full training data performed once every R = 1 epochs instead of every R = 20 epochs. Since selecting subsets at every epoch can be computationally expensive, we only perform these experiments on small coresets and hence still enjoy good speedups compared to full data augmentation. This shows that our approach is still effective at very small subset sizes, hence can be computationally efficient even when subsets are re-selected every epoch.
Table Training on full data and selecting new subset for augmentation every epoch (R 1).
Subset
Random
Max-loss Policy
Ours
Acc
NS (%)
Acc
NS (%)
Acc
NS (%)
0%
91.96 + 0.12
91.96 0.12
91.96 + 0.12
0.2%
92.22 + 0.22
67.03 + 0.04
91.94 0.12
86.70 76.70-2 0.15
92.26 + 0.13
79.19 + 1.10
0.5%
92.06 + 0.17
36.70 = 0.18
92.20 + 0.13
76.80 0.31
92.27 + 0.08
63.23 + 0.35
C.4 ADDITIONAL VISUALIZATIONS FOR TRAINING ON CORESETS AND AUGMENTATIONS MEASURING TRAINING DYNAMICS OVER TIME
We include additional visualizations in Figure 5 for training on coresets and its augmentations as supplementary plots to Figure 3c and Table 3 We plot metrics obtained during each point (epoch) of the training process based on percentage of data selected/used and test accuracy achieved. All metrics are averaged over 5 runs and obtained using R 1. These plots demonstrate that coreset augmentation approaches outperform random augmentation baselines throughout the training process. Furthermore, they show that augmentation of coresets result in a larger increase in test accuracy compared to augmentation of randomly selected training examples, especially for small subset sizes.
21

---

Under review as a conference paper at ICLR 2022
60
% intersect
coreset-loss
40
coreset-rand
coreset-loss-rand
0
2500
5000
10000
15000
selections
Figure 6: Intersection between max-loss and coresets in the top N points selected aggregated across the entire training process. Here, we show the increasing overlap between max-loss and coreset points N grows.
Coreset
Loss Policy
Figure 7: Qualitative evaluation of coreset and max-loss points.
35-
40
30-
Accuracy
25
30
20
ordonn
medemm
10
10
20
50
121
20
20
-2
50
60
% date selected
76
data selected
76
data selected
(a) CIFARIO 0.1% %
(b) CIFARIO 0.2%
(c) CIFARIO 0.5%
Rindom
80
sureset
rondom
60
farstor 26g)
messet_nig
fecuracy
20
20
20
40
A3
70
60
60
100
% deta selected
%6 data selected
(d) CIFARIO 1%
(c) CIFARIO 5%
Training coreset and its augmentation compared to random baseline, measured using test accuracy against percentage of data used on CIFAR10 dataset across various subset sizes. Accuracy and percentage of data used measured every epoch and averaged over 5 runs.
Figure 5: Supplementary plots for Figure 3c
C.5 INTERSECTION OF MAX-LOSS POLICY AND CORESETS
Figure 3a depicts the increase in intersection between max-loss subsets and coresets over time. In addition, we also aggregate 30% subsets selected every R 20 epochs using both approaches over the entire training process to compute intersection between the top N selected data points. Our plots in Figure suggest that similar pattern holds in this setting. We also qualitatively visualize this in Figure 7
22


Reviews:
[{"review_id": "oqaoyy-Me37", "reviewer": "Reviewer_fQLH", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "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": "The main contribution of this paper is, in my opinion, a sound theoretical analysis of the impact of input perturbations on the singular values of the Jacobian, or the eigenvalues of the Neural Tangent Kernel (NTK), that may inspire other researchers. However, the limitations of the analysis with respect to real-world image data augmentation, as well as the limited motivation, in my opinion, for the need for the proposed method, have an overall negative impact in my assessment of the significance of this work. I elaborate on these concerns below. \n\nFirst, the whole theoretical analysis, built upon that of Rajput et al. (2019), is based on modelling data augmentation as additive perturbations of the inputs. This is stated at the beginning of Section 2 and never recalled as a limitation again in the paper (except for one section in the supplementary material). On the contrary, the authors argue that this modelling of data augmentation captures typical real-world image transformations, such as \"translations, crops, rotations, and [...] other pixel-wise augmentation methods such as sharpening, blurring, and color distortions\" (second paragraph of Section 2). This is in sharp contrast with the limitations discussed by Rajput et al. (2019) themselves, on whose work the current paper takes inspiration for the theoretical analysis. In their Conclusion and Open Problems, Rajput et al. (2019) wrote: \"There are several interesting open problems that we plan to tackle in the future. First, it would be interesting to theoretically analyze practical state-of-the-art augmentation methods, such as random crops, flips, and rotations. Such perturbations often fall outside our framework\".\n\nIn line with Rajput et al. (2019), I would strongly argue that additive perturbations, while interesting from a mathematical point of view, only very weakly capture the extent of image transformations used in practice. Geometrical transformations can hardly be approximated by additive perturbations. One example of a widely common transformation that strongly differs from additive perturbations is horizontal flipping. This introduces a strong inductive bias, based on the properties of human visual perception, which is why it is included in almost all data augmentation schemes. Therefore, any conclusions from such a mathematical approximation to real-world data augmentation needs to be cautious. For example, the paper concludes saying that it has been shown \"that data augmentation improves training and generalization by enlarging the smaller singular values of the neural network Jacobian\". As argued above, this seems a strong claim given the limitations. The strength of the claims is particularly surprising after the authors wrote about other existing works on the theoretical analysis of data augmentation that they \"do not provide insights on the effect of data augmentation on training deep neural networks\".\n\nMy other main concern has probably a stronger impact on my overall assessment of the paper. This has to do with the motivation for the need for methods to select subsets of data on which to apply data augmentation. On the second sentence of the abstract, the authors write that \"modern data augmentation techniques become computationally prohibitive for large 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 authors mention that \"multiple augmented examples are usually generated for a single data point to obtain better results, increasing the size of the training data by orders of magnitude\", as though this was a weakness of data augmentation, while it is actually one of its main strengths. In particular, that the effective training size may be increased orders of magnitude while keeping the training time within the same order of magnitude. \n\nAn analysis of such advantages and the reasons for it (such as the fact that data augmentation can be performed in parallel to the parameter updates of the model, and even create a queue of data that would effectively keep the training time identical, given sufficient memory), as well as compelling evidence of the efficiency of data augmentation is provided by Hernández-García and König (2018). In that paper we see that training with light data augmentation (translations and horizontal flips) on the full training set provides large performance gains with a marginal increase of the training time. Furthermore, they also provide empirical evidence that training with 50 % data _and_ data augmentation (again on the full available set) achieves more than 95 % of the _full_ accuracy in about half the training time. Therefore, given that data augmentation can be applied almost _for free_ and training time can be traded by reducing the training data for a marginal reduction of the accuracy, why do we need a complex algorithm such as the one presented in this paper?\n\nIt is not clear from the paper how the training times are calculated, but we still see that in the best case the gains stay within the same order of magnitude. I believe that a stronger justification of the need for this method should take into account the considerations mentioned above, as well as a comparison with other alternative ways to trade training time for performance, such as changes in the architecture, etc.\n\n### References\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", "summary_of_the_paper": "This paper first provides a theoretical analysis, under some assumptions, of the effect of data augmentation on the singular values of the network Jacobian and then proposes a method to improve the sample complexity of data augmentation, that is to select a subset of the data on which to perform the transformations to speed up training. The proposed method aims to find subsets of data whose augmentation yields similar alignment of the Jacobian with the residual vector as the fully augmented data. ", "summary_of_the_review": "While the paper seems solid in terms of correctness, I have a less positive impression due to, in my opinion, limited significance. This has to do with the simplification of data augmentation with respect to real world necessary for the theoretical analysis, as well as with the lack of strong motivation for the proposed algorithm.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "fvNJoaoeqKk", "reviewer": "Reviewer_Q8Ag", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "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": "Strengths:\n1) The motivation of the paper is clearly justified. \n2) The presentation of the theoretical analysis and the algorithm are clear and sound.\n3) The results shows improvement over the max-loss method on some datasets.\n\nWeakness:\n1) What is the extra computation cost for finding the coreset compared with that of  the random and max-loss baseline?\n2) Does the coreset change significantly at different epochs?\n3) It would be interesting to show the performance when transferring the core-set found on one architecture (e.g., ResNet20) to train on a different architecture (e.g., Wid-ResNet). Will transfer the corset leads to performance loss?\n4) You might referred to the wrong figure in the sentence “Figure 3b depicts the increase in intersection between max-loss subsets and coresets over time”\n5) The paper only did experiments on small datasets other than large datasets such as ImageNet.\n\n", "summary_of_the_paper": "This paper shows that data augmentation can speed up learning by enlarging the smaller singular values of the Jacobian. Following this idea, this paper proposed a framework to iteratively extract small subsets of training data that captures the alignment of NTK with the residual when augmented.\n", "summary_of_the_review": "This paper proposed a data efficient augmentation framework with extensive theoretical analysis. The presentation and the proposed method are sound. However, the lack of experimental results on large datasets such as ImageNet makes the results of the paper much less convincing.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "_Fy0z6wR1BO", "reviewer": "Reviewer_1cJe", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "**Strengths**\n\nI appreciate that this paper provides rigorous theoretical analysis to data augmentation, its connection to NTK and effect on eigenvalues and how data augmentation affects the training dynamics and generalization, and it also provides mathematical proofs to the theorems proposed.\n\nIn the presence of noisy labels, the proposed technique is outperforming reference methods.\n\nAnd even when the selected subset is very small compared to randomly augmenting datasets of similar size the proposed method is capable of providing good augmentation resulting and a decent increase in performance.\n\n**Weaknesses**\n\nAs I understand one of the observations in section 3.1 suggests that augmentation cannot change the singular values considerably for diverse datasets, but we still see a gain in performance when augmenting these datasets.\nMy concern is if we have a more diverse dataset than the ones experimented on, according to my understanding we will have a larger number of singular values and that will limit the ability to find a subset to augment and we need to increase the size of the subset which can largely limit the effectiveness of the method.\n\nIn my opinion, one of the main strengths of the method is when we have a very large dataset but unfortunately, the authors didn’t provide any experiments regarding large datasets like ImageNet.\n\nThe proposed method outperforms the baseline when the size of the subset is fairly small, but when increasing the size into reasonable percentages the improvement is marginal see Table 4 in appendix C.\n\n**Suggestion To Authors**\n\nThough the whole paper is nicely executed and demonstrated, in my opinion, some of the figures aren’t easy to read e.g. (Figure 4) I suggest splitting the figure into two side by side showing the speed gain and accuracy improvement separately.\n", "summary_of_the_paper": "The authors model data augmentation as an additive perturbation and analyze its effect on training dynamics and how it enlarges the smaller singular values of the network jacobian.\nThen they propose a new method to iteratively extract a subset of the training data that when augmented closely capture the full augmented data dynamics.\nAuthors show that by augmenting this subset combined with full training data they can outperform the state-of-the-art method by 7.7% on CIFAR-10 and 4.7% on SVHN while achieving 6.3x and 2.2x speedup respectively.", "summary_of_the_review": "I think the paper is of interest, especially the theoretical analysis. It is well written and provides rigorous mathematical analysis to data augmentation and proofs for all the theorems, lemmas and corollaries mentioned.\n\nBut I believe the main application of the proposed method is in large scale dataset settings, while in small or medium-size datasets augmenting the full dataset is not an issue, but that wasn’t presented (see my concerns in the previous section).\nAlso, the improvement when increasing subsampling size is marginal, especially with diverse datasets.\nThis problem and the lack of experiments with large and diverse datasets prevents me from giving a higher recommendation of acceptance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "ZiO7_PLhy9", "reviewer": "Reviewer_xyXQ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "Strengths:\n* The paper presents a convincing reason why the approach can work in theory.\n* The approach seems novel and connects various prior works.\n\nWeaknesses:\n* I thought the algorithm description in Section 4 was a bit rushed. For example, equation 11 was hard to understand and is core to the algorithm.\n* I also though the Section 5 was rushed. The whole evaluation is ~1 page, which leaves the reader wanting for 1) how speedup is calculated 2) what is the objective of the experiments 3) what takeaways should be had. I would recommend moving other text to the appendix (e.g., anything reviewing prior work can be shortened and pushed to appendix).\n* Figure 3b seems like a random walk. Figure 3c x-axis and text labels seem misaligned. Overall, I think this figure can be improved to give a clearer and more convincing story.\n* The theory is appreciated but maybe it's worth contextualizing what values of the constants L and epsilon_0 are common in practice. Even a simple augmentation like translate can cause a large pixel deviation. For example, with 100 pixels horizontally, each varying by 1 intensity via a gradient (e.g., 0 to 99), shifting by 1 pixel will cause a change in the image that is 100 large.\n* The good results seem very CIFAR10 specific. For example, Figure 4b shows SVNH has minimal improvement. More experimental evaluation is always good. For example, MNIST would have been an easy result to add and is in-fact mentioned in the paper, yet I didn't see it in evaluation.", "summary_of_the_paper": "Deep learning uses augmentations to improve generalization performance. Using all augmentations for a dataset may slow down training. A subset selection technique is proposed (e.g., \"coreset\") using insights from the Neural Tangent Kernel (NMT) framework such that an alignment between the NMT Jacobian and the residuals is preserved. This alignment score is used to select the coreset using submodular optimization, which allows the model to be trained on a subset of augmented data (e.g., 0.1% to 30%) while preserving most augmentation benefits. The speedup of the method is reported to be up to 6.3x.", "summary_of_the_review": "The paper is ok. I think there is enough theoretical justification for why the method could work, though I think empirical evidence is necessary to still show that. The theory is a bit disconnected and seems more like a synthesis of many different works; I wonder if it can be presented more succinctly? In any case, I found the writing good enough to follow. My biggest concern is the generalization of the evaluation, since it seems quite short at the moment and very CIFAR10 specific.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The work presents a theoretical analysis of data augmentation, presenting evidence that data augmentation enlarges the smaller the singular values of the network Jacobian. Based on this theory the authors present a method for selecting a subset of training data to use with augmentation that decently approximates performance of training w/ augmentation on the full dataset. Reviewers overall agreed that the theoretical analysis was interesting, and did not find any flaws (though it is worth noting that the theory is restricted to additive perturbations). However, multiple reviewers found the presented experiments unconvincing, and questioned the stated motivation. The AC agrees with reviewers that most simple augmentations are not prohibitive in training speed. Certainly training on less data with a fixed epoch budget would require less compute time, but this is has nothing to do with augmentation and instead is a result of fewer steps taken in training. In the rebuttal, the authors argued that training on Imagenet is prohibitive with a single GPU (taking 2 weeks to do full training). However, given the authors claim their method speeds up training by a factor of 6.3x, then reducing ImageNet training from 2 weeks to 2 days would be a more convincing application of their method and would strengthen the work.
Decision: Reject