Year: 2021

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.

heading: 1 INTRODUCTION
text: Data augmentation expands the training data by applying transformations, such as rotations or crops for images, to the original training examples. Due to its effectiveness, data augmentation is a key component in achieving nearly all state-of-the-art results in deep learning applications (Shorten & Khoshgoftaar, 2019). The most effective data augmentation techniques often search over a (possibly large) space of transformations to find sequences of transformations that speeds up training the most (Cubuk et al., 2019; 2020; Luo et al., 2020; Wu et al., 2020). In addition, 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 a result, state-of-the-art 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 is 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. If 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 of 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 a 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
a 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 theoretically understand how data augmentation affects the optimization and generalization of neural networks. Existing theoretical results are 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 et al., 2019; Wager et al., 2013; Wu et al., 2020), enlarging the margin of a 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 a 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 to mainly affect the initial phase of training (Golatkar et 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 a high fraction of labels are noisy.
We demonstrate the effectiveness of our approach applied to training ResNet20, ResNet32, WideResNet on CIFAR10, CIFAR10-IB and SVHN, compared to random and max-loss baselines (Kuchnik & Smith, 2018). We show that augmenting coresets found by our approach outperforms the stateof-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 CIFAR10, we attain 75% of the improvement in test accuracy compared to augmenting the full dataset while enjoying a 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 CIFAR10/ResNet20 while providing a 39x speedup compared to using the full dataset. On CIFAR10 with 50% noisy labels, augmenting 50% of the training data outperforms full data augmentation.

heading: 2 PROBLEM FORMULATION
text: We begin by formally describing the problem of learning from augmented data. Consider a dataset Dtrain = (Xtrain,ytrain), where Xtrain = (x1, · · · ,xn) ∈ Rd×n is the set of n normalized data points xi ∈ [0, 1]d, from the index set V , i.e., i ∈ V = {1, · · · , n}, and ytrain = (y1,· · ·, yn) ∈ {y ∈ {ν1, ν2, · · · , νC}} with {νj}Cj=1 ∈ [0, 1]. Assume at every step t during training, we have a set of augmented examples Dtaug generated by a set of label-invariant transformations. In particular, following (Rajput et al., 2019) we model data augmentation as an arbitrary bounded additive perturbation , with ‖ ‖≤ 0. Formally, for a given upper bound 0 and the set of all possible transformations A, we study the transformations selected from S ⊆ A satisfying
S = {Ti ∈ A | ‖Ti(x)− x‖≤ 0 ∀x ∈Xtrain}. (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), 0 is small. This model is also especially suitable for modelling state-of-the-art 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 ε0, our experiments use variety of strong and weak augmentations. Although other transformations such as data synthesis (Baluja & Fischer, 2017; Mirza & Osindero, 2014),
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), as we analyze in Appendix B.3.
In practice, multiple augmentations are generated for each example xi, and each augmented data point can be a combination of multiple transformations, e.g. random cropping and rotating followed by horizontal flipping. The set of augmentations at iteration t generating r augmented examples per data point can be specified, with abuse of notation, as Dtaug = { ⋃r i=1 (T t i (Xtrain),ytrain)}, where |Dtaug|= rn and T ti (Xtrain) transforms all the training data points with the set of transformations T ti ⊂ S at iteration t. We denoteXtaug = { ⋃r i=1 T t i (Xtrain)} and ytaug = { ⋃r i=1 ytrain}.
Let f(W ,x) be an arbitrary neural network with m vectorized (trainable) parametersW ∈ Rm. We assume that the network is trained using (stochastic) gradient descent with learning rate η to minimize the squared loss L over the original and augmented training examples Dt = {Dtrain ∪ Dtaug} with associated index set V t, at every iteration t:
L(W t,X) := 1 2 ∑ i∈V t Li(W t,xi) := 1 2 ∑ (xi,yi)∈Dt ‖f(W t,xi)− yi‖22. (2)
The gradient update at iteration t is given by
W t+1 = W t − η∇L(W t,X), ∇L(W t,X) = J T (W t,X)(f(W t,X)− y), (3)
where Xt = {Xtrain ∪Xtaug} and yt = {ytrain ∪ ytaug} are the set of original and augmented examples and their labels, J (W ,X) ∈ Rn×m is the Jacobian matrix associated with f , and rt = f(W t,X)− y is the residual. We further assume that J is smooth with Lipschitz constant L:
‖J (W ,xi)− J (W ,xj)‖≤ L‖ xi − xj‖ ∀ xi,xj ∈X . (4)
This trivially holds for linear models, and whenW is bounded, it holds for deep ReLU, and generally for networks with any activation φ with bounded derivatives φ′ and φ′′ (Jordan & Dimakis, 2020). Under this assumption, augmentation as defined in Eq. (1) results in bounded perturbations to the Jacobian matrix. I.e., for any transformation Tj ∈ S , we have ‖J (W ,xi)−J (W , Tj(xi))‖≤ L 0. Using the shorthand notations J = J (W ,Xtrain) and J̃ = J (W , Tj(Xtrain)), we obtain J̃ = J +E, where E is the perturbation matrix with ‖E‖2≤ ‖E‖F≤ √ nL 0.

heading: 3 DATA AUGMENTATION SPEEDS UP LEARNING
text: 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 on properties of neural network Jacobian matrix and the corresponding Neural Tangent Kernel (NTK) (Jacot et al., 2018) defined as Θ = J (W ,X)J (W ,X)T . Formally (Arora et al., 2019):
rt = n∑ i=1 (1− ηλi)(uiuTi )rt−1 = n∑ i=1 (1− ηλi)t(uiuTi )r0, (5)
where Θ = UΛUT = ∑ i=1 λiuiu T i is the eigendecomposition of the NTK. Although the constant NTK assumption holds only in the infinite width limit, Lee 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 0, data augmentation speeds up training by enlarging smaller eigenvalues of the NTK, while decreasing larger eigenvalues with a 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 a regularization effect by slightly perturbing the eigenvectors.

heading: 3.1 EFFECT OF DATA AUGMENTATION ON THE EIGENVALUES OF THE NTK
text: 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 characterise the effect of data augmentation on singular values of the perturbed Jacobian J̃ , we 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, |σ̃i−σi|≤ ‖E‖2, where σ̃i and σi 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 T , and P⊥ = I−P be the projection onto its orthogonal complement subspace. Then, the singular values of the perturbed Jacobian J̃ T are σ̃2i = (σi + µi)2 + ζ2i , where |µi|≤ ‖PE‖2, and σmin(P⊥E) ≤ ζi ≤ ‖P⊥E‖2, σmin the smallest singular value of J T (Stewart, 1979). Since the eigenvalues of the projection matrix P are either 0 or 1, as the number of dimensions m grows, for bounded perturbations we get that on average µ2i = O(1) and ζ2i = O(m). 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 σ̃i − σi ∼= µi. 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. As calculating the entire Jacobian spectrum is computationally prohibitive, data is subsampled from 3 classes. For all datasets, we used the data augmentation techniques described in the Experiments section, such as rotation, translation, contrast, brightness. It 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 0 results in the following expected change to the eigenvalues of the NTK:
E[λ̃i] = E[σ̃ 2 i ] = σ 2 i + σi(1− 2pi)‖E‖+‖E‖2/3 (6)
where pi := P(σ̃i − σi < 0) is the probability that σi decreases as a result of data augmentation. All the proofs can be found in the Appendix.
From Lemma 3.1 and Eq. (5) we see that augmentation can speed up learning at every epoch by σi(1− 2pi)‖E‖+‖E‖2/3 along dimensions with smaller singular values for which pi ≤ 0.5, and by ‖E‖2/3 along dimensions with for which singular values do not change (pi ≈ 0.5). It can also speed up learning along dimensions for which singular values decrease (pi > 0.5) as long as ‖E‖≥ 3σi(2pi − 1). This is mainly relevant for smaller singular values under strong augmentation.

heading: 3.2 EFFECT OF DATA AUGMENTATION ON THE EIGENVECTORS OF THE NTK
text: 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 J = UΣV T . Then for the NTK, we
have Θ = JJ T = UΣV TV ΣUT = UΣ2UT (since V TV = 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 σi are singular values of the Jacobian. Let the perturbed Jacobian be J̃ = J + E, and denote the eigengap γ0 = min{σi − σi+1 : i = 1, · · · , r} where σr+1 := 0. Assuming γ0 ≥ 2‖E‖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
‖ui − ũi‖≤ 2 √
2‖E‖/γ0 (7) This result provides an upper-bound on the change of every left singular vectors of 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 = UΣV T = UsΣsV Ts + UnΣnV Tn , where Us 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 (Σn = 0), spans the orthogonal space of Us, which is also called the noise subspace. Similarly, let the subspace decomposition of the perturbed Jacobian be J̃ = ŨΣ̃Ṽ T = ŨsΣ̃sṼ Ts + ŨnΣ̃nṼ Tn , and Ũs = Us + ∆Us, where ∆Us 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: ∆Us = UnUTn EVsΣ −1 s (Li et al., 1993). We see 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 are more robust to perturbations than singular values.

heading: 3.3 AUGMENTATION IMPROVES TRAINING AND GENERALIZATION
text: 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 associated 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 η applied to a neural network with constant NTK and Lipschitz constant L, and data points Daug augmented with r additive perturbations bounded by 0 as defined in Eq. (1) results in the following training dynamics:
E[‖y − f(Xaug,W t)‖2] ≤ √√√√n n∑ i=1 ( 1− η ( rσ2i + √ rσi(1− 2pi)‖E‖+‖E‖2/3 ) )2t (8) where E with ‖E‖≤ √ nL 0 is the perturbation to the Jacobian, and pi := P(σ̃i − σi < 0) is the probability that σi decreases as a result of data augmentation.
Corollary 3.3 Under the same assumptions as in Theorem 3.2 let σmin be the minimum singular value of Jacobian J associated with training data Xtrain, then probability 1− δ generalization error of the network trained with gradient descent on augmented dataXaug enjoys the following bound:√
2
(σmin + √ nL 0)2
+O ( log 1
δ
) . (9)

heading: 4 MOST EFFECTIVE SUBSETS FOR DATA AUGMENTATION
text: 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 of 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 (W t,Xtaug)Trtaug. If such subsets can be found, augmenting only the subsets will change the NTK and its alignment with the residual in a similar way as that of full data augmentation, and will result in similar improved training dynamics. Effectively, such augmented subsets can be trained on along with the full non-augmented data, or without it to further
Algorithm 1 CORESETS FOR EFFICIENT DATA AUGMENTATION Input: The dataset D = {(xi, yi)}ni=1, number of iterations T . Output: Output model parametersW T .
1: for t = 1, · · · , T do 2: St = ∅,Xtaug = ∅. 3: for c ∈ {1, · · · , C} do 4: Stc = greedy(Vc) . Extract a coreset from class c by solving Eq. (11) 5: γj = ∑ i∈VcI[j=arg minj′∈S‖J
T (W t,xi)ri−J T (W t,xj′)rj′‖] . Coreset weights 6: Xtaug = {Xaug ∪ {∪ri=1T ti (XStc)}} . Augment the coreset 7: ρtj = γ t j/r 8: Update the parametersW t using weighted gradient descent onXtaug or {Xtrain ∪Xtaug}.
speed up training. However, generating the full set of transformationsXtaug 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 a 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 (W t,Xtrain)rtrain can closely estimate the alignment of the Jacobian of the full augmented data and the corresponding residual J T (W t,Xtaug)rtaug . Thus, the most effective subsets for augmentation can be directly found from the training data. Formally, subsets St∗ weighted by γ t S 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:
St∗ = arg min S⊆V |S| s.t. ‖J T (W t,Xt)rt − diag(γtS)J T (W t,XtS)rtS‖≤ ξ. (10) Solving the above optimization problem is NP-hard. However, as we discuss in the Appendix A.6, a
near optimal subset can be found by minimizing the Frobenius norm of a matrixGS , in which the ith row contains the euclidean distance between data point i and its closest element in the subset S, in the gradient space. Formally, [GS ]i. = minj′∈S‖J T (W t,xi)ri − J T (W t,xj′)rj′‖. Intuitively, such subsets contains the set of medoids of the dataset in the gradient space, where the medoids of a dataset are defined as the most centrally located elements in the dataset (Kaufman et al., 1987). The weight of every element j ∈ S is the number of data points closest to it in the gradient space, i.e., γj = ∑ i∈V I[j = arg minj′∈S‖J T (W t,xi)ri − J T (W t,xj′)rj′‖]. The set of medoids can be found by solving the following submodular1 cover problem: St∗ = arg minS⊆V |S| s.t. C − ‖GS‖F≥ C − ξ, (11)
where C ≥ ‖GS‖F is a constant. The classical greedy algorithm provides a logarithmic approximation for the above submodular maximization problem, i.e., |S|≤ (1 +Ln(n)). It starts with the empty set S0 = ∅, and at each iteration τ , it selects the training example e ∈ V that maximizes the marginal gain F (e|Sτ ) = F (Sτ ∪ {e}) − F (Sτ ). Formally, Sτ = Sτ−1 ∪ {arg maxe∈V F (e|Sτ−1)}. The O(nk) computational complexity of the greedy algorithm can be 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 matrixG 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.
At every iteration t during training, we select a coreset from every class c ∈ [C] separately, and apply the set of transformations {T ti }ri=1 only to the elements of the coresets, i.e.,Xtaug = {∪ri=1T ti (XSt)}. We divide the weight of every element j in the coreset equally among its transformations, i.e. the final weight ρtj = γ t j/r if j ∈ St. We apply the gradient descent updates in Eq. (3) to the weighted Jacobian matrix ofXt = Xtaug orX t = {Xtrain ∪Xtaug} (viewing ρt as ρt ∈ Rn) as follows:
W t+1 = W t − η ( diag(ρt)J (W t,Xt) )T rt. (12)
1A set function F : 2V → R+ is submodular if F (S∪{e})−F (S) ≥ F (T ∪{e})−F (T ), for any S ⊆ T ⊆ V and e ∈ V \ T . F is monotone if F (e|S) ≥ 0 for any e∈V \S and S ⊆ V .
The pseudo code is given in Alg. 1. 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 an error of at most ξ as in Eq. (4). Augmenting the coreset with perturbations bounded by 0≤ 1
n 3 2 √ L
captures the alignment of the fully augmented data with the residual by an error of at most
‖J T (W t,Xaug)r − diag(ρt)J t(W t,XSaug )rS‖≤ ξ +O (√ L ) . (13)
Importantly, since the augmented coresets capture the alignment of the Jacobian of a fully augmented data with residual, they can be trained on in absence of the full data to gain more speedup. This is not the case for existing methods such as max-loss. Besides, the gradient of noisy labeled data points do not cluster in the gradient space (Mirzasoleiman et al., 2020b). Thus, only clean data points are selected for augmentation. This results in an improved performance, as we will show in Sec. 5.1.

heading: 4.1 CORESET VS. MAX-LOSS STRATEGY FOR DATA AUGMENTATION
text: In the initial phase of training the NTK goes through rapid changes, which determines the final basin of convergence and network’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 al., 2019). Crucially, augmenting coresets that closely capture the alignment of the NTK with the residual during this initial phase results in a 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. 3b illustrates 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. 3a).
The following Theorem characterizes the training dynamics of training on the full data and the augmented coresets, using the additive perturbation model in Eq. (1).
Theorem 4.2 Let Li be β-smooth, L be λ-smooth and satisfy the α-PL condition, that is for α > 0, ‖∇L(W )‖2 ≥ αL(W ) for all weights W . Let f be Lipschitz in X with constant L′, and L̄ = max{L,L′}. Let G0 be the gradient at initializaion, σmax the maximum singular value of the coreset Jacobian at initialization. Choosing 0 ≤ 1
σmax √ L̄n and running SGD on full data with augmented coreset using constant step size η = αλβ , we get the following convergence bound:
E[‖∇Lf+caug(W t)‖] ≤ 1√ α
( 1− αη
2
) t 2 ( 2G0 + ξ +O ( √ L̄
σmax
)) . (14)
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 on (1) the error of the coreset ξ in Eq. (4), and (2) the error in capturing the alignment of the full augmented data with the residual derived in Lemma 4.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 on the augmented coresets, and augmentations modelled as arbitrary linear transformations using a linear model (Wu et al., 2020) in Appendix B.1, B.3.

heading: 5 EXPERIMENTS
text: 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. In both cases we use subsets with maximum loss, and random subsets as baselines. For all methods, we select a new augmentation subset every R epochs. We note that while the original method of (Kuchnik & Smith, 2018) selects points based on loss of a fully trained model, to maximize fairness, our max-loss baseline selects a new subset at every subset selection step.
Data and augmentation. We apply our method to training ResNet20 and Wide-Resnet-28-10 on CIFAR10, and ResNet32 on CIFAR10-IMB (Long-Tailed CIFAR10 with Imbalance factor of 100 following (Kim & Kim, 2020)) 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 4 distinct augmented examples by randomly sampling 2 augmentations from the same set used by (Cubuk et al., 2019; 2020) to apply to each example. A new set 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.

heading: 5.1 TRAINING ON FULL DATA AND AUGMENTED SUBSETS
text: Table 1 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
and max-loss subsets across different models and datasets. Fig. 5 shows the speedup vs. test accuracy of augmenting subsets of different size selected from CIFAR10 and SVHN by our method vs baselines. We see that our method outperforms the baseline while providing a 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-loss and random subsets of different sizes selected from CIFAR10 with 50% label noise for training ResNet20. Note that augmenting coresets selected by our method not only outperforms max-loss and random, but provides a superior performance over full data augmentation. This clearly shows the effectiveness of the coresets in capturing the alignment of the NTK with the residual of clean data points.

heading: 5.2 TRAINING ONLY ON AUGMENTED SUBSETS IN ABSENCE OF FULL DATA
text: We now evaluate the effectiveness of our approach for training only on the augmented coresets. Our main goal here is to 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. Table 3 shows the test accuracy for training ResNet20 and Wide-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 a 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 of the NTK with the residual for data augmentation. Note that training on the augmented max-loss points did not even converge in absence of full data. Finally, Fig. 3c shows the fraction of data selected for augmentation during training of ResNet20 on CIFAR10. We see that the coresets achieve a superior performance by carefully selecting certain data points more often than others.

heading: 6 CONCLUSION
text: We showed that data augmentation improves training and generalization by enlarging the smaller singular values of the neural network Jacobian. Then, we proposed a framework to iteratively extract small subsets of 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 the coresets selected by our method to provide a superior generalization performance when added to the full data, in presence of noisy labels, or as a standalone subset.

heading: 7 REPRODUCIBILITY STATEMENT
text: 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 proofs for non-trivial theoretical results in the main paper can be found in Appendix A, while additional theoretical results and their respective proofs can be found in Appendix B.

heading: DATA-EFFICIENT AUGMENTATION FOR TRAINING NEURAL NETWORKS

heading: A PROOF OF MAIN RESULTS

heading: A.1 PROOF FOR LEMMA 3.1
text: Proof Let δi := σ̃i − σi, where P(δi < 0) = pi. Assuming uniform probability between −‖E‖ to 0, and between 0 to ‖E‖, we have pdf ρi(x) for δi:
ρi(x) =  pi ‖E‖ , if − ‖E‖≤ x < 0 1−pi ‖E‖ , 0 ≤ x ≤ ‖E‖ 0, otherwise
(15)
Taking expectation, E(σ̃i − σi) = E(δi) = ∞∫ −∞ xρi(x)dx (16)
= 0∫ −‖E‖ x pi ‖E‖ dx+ ∫ ‖E‖ 0 x 1− pi ‖E‖ dx (17)
= −‖E‖pi 2 + (1− pi)‖E‖ 2 (18) = (1− 2pi)‖E‖
2 (19)
We also have
E(δ2i ) = ∞∫ −∞ x2ρi(x)dx (20)
= 0∫ −‖E‖ x2 pi ‖E‖ dx+ ∫ ‖E‖ 0 x2 1− pi ‖E‖ dx (21)
= ‖E‖2pi
3 +
(1− pi)‖E‖2
3 (22)
= ‖E‖2
3 (23)
Thus, we have
E(λ̃i) = E(σ̃ 2 i ) (24)
= E((σi + δi) 2) (25)
= E(σ2i + 2σiδi + δ 2 i ) (26)
= σ2i + 2σiE[δi] + E[δ 2 i ] (27)
= σ2i + 2σi (1− 2pi)‖E‖ 2 + ‖E‖2 3 (28) = σ2i + σi(1− 2pi)‖E‖+ ‖E‖2
3 (29)

heading: A.2 PROOF OF THEOREM 3.2
text: Using Jensen’s inequality, we have
E [ ‖y − f(Xaug,W t)‖2 ] = E √√√√ n∑ i=1 (1− ηλ̃i)2t(uTi y)2 ±  (30) ≤
√√√√E[ n∑ i=1 (1− ηλ̃i)2t(uTi y)2 ]
(31)
≤ √√√√ n∑ i=1 E [ (1− ηλ̃i)2t(n) ] (32)
≤ √√√√n n∑ i=1 (1− ηE [ λ̃i ] )2t (33)
= √√√√n n∑ i=1 (1− ηE [ λ̃i ] )2t (34)
= √√√√n n∑ i=1 ( 1− η ( σ2i + σi(1− 2pi)‖E‖+ ‖E‖2 3 ))2t (35)

heading: A.3 PROOF OF COROLLARY 3.3
text: Under the assumptions of Theorem 5.1 of Arora et al. (2019), i.e. where the minimum eigenvalue of the NTK is λmin(JJ T ) ≥ λ0 for a constant λ0 > 0, and training data X of size n sampled i.i.d. from distribution D and 1-Lipschitz loss L, we have that with probability δ/3, training the over-parameterized neural network with gradient descent for t ≥ Ω ( 1 nλ0 log nδ ) iterations results in the following population loss LD (generalization error)
LD(W t,X) ≤ √
2yT (JJ T )−1y n
+O (
log nλ0δ n
) , (36)
with high probability of at least 1− δ over random initialization and training samples. Hence, using λmin, σmin to denote minimum eigen and singular value respectively of the NTK corresponding to full data, we get
LDtrain(W t,Xtrain) ≤
√ 2 1λmin ‖y‖ 2
n +O
( log 1
δ
) (37)
≤
√ 2
σ2min +O
( log 1
δ
) . (38)
For augmented datasetXaug , we have σ̃i ≤ σi+ √ nL 0, hence the improvement in the generalization error is at most
LDaug (W t,Xaug) ≤
√ 2
(σmin + √ nL 0)2
+O ( log 1
δ
) . (39)
Combining these two results, we obtain Corollary 3.3.

heading: A.4 PROOF OF LEMMA 4.1

heading: Proof
text: ‖J T (W t,Xaug)r−diag(ρt)J t(W t,XSaug )rS‖ (40) = ‖(J T (W t,X) +E)r − (diag(ρt)J t(W t,XS) +ES)rS‖ (41) ≤ ‖(J T (W t,X)r − diag(ρt)J t(W t,XS)rS) +Er −ESrS‖ (42) ≤ ‖(J T (W t,X)r − diag(ρt)J t(W t,XS)rS)‖+‖Er‖+‖ESrS‖ (43)
Applying definition of coresets, we obtain
‖(J T (W t,X)r−diag(ρt)J t(W t,XS)rS)‖+‖Er‖+‖ESrS‖ (44) ≤ ξ + ‖Er‖+‖ESrS‖ (45)
≤ ξ + 2n 32L 0 (46) ≤ ξ + 2 √ L (47)

heading: A.5 PROOF OF THEOREM 4.2
text: Proof In this proof, as shorthand notation, we useXf andXtrain interchangeably. We further use Xc to represent the coreset selected from the full data, andXcaug to represent the augmented coreset.
By Theorem 1 of Bassilyet al. (2018), under the α-PL assumption for L and interpolation assumption (i.e. for every sequenceW 1,W 2, . . . such that limt→∞ L(W t,X) = 0, we have that the loss for each data point limt→∞ L(W t,xi) = 0), the convergence of SGD with constant step size is given by
E[‖∇L(W t,Xf+caug)‖2] ≤ (
1− αη 2
)t L(W 0,Xf+caug) (48)
≤ 1 α
( 1− αη
2
)t ‖∇L(W 0,Xf+caug)‖2 (49)
Using Jensen’s inequality, we have
E[‖∇L(W 0,Xf+caug)‖] (50) ≤ √
E[‖∇L(W t,Xf+caug)‖2] (51)
≤ 1√ α
( 1− αη
2
) t 2 ‖∇L(W 0,Xf+caug)‖ (52)
≤ 1√ α
( 1− αη
2
) t 2 (‖∇L(W 0,Xf )‖+‖∇L(W 0,Xcaug)‖) (53)
≤ 1√ α
( 1− αη
2
) t 2 ( G0 + ‖(J (W 0,Xc) +E)(y − f(W 0,Xc + ))‖ ) (54)
≤ 1√ α
( 1− αη
2
) t 2
(55)( G0 + ‖(J (W 0,Xc) +E)T (y − f(W 0,Xc)−∇xf(W 0,Xc)T −O( T )‖ ) (56)
= 1√ α
( 1− αη
2
) t 2
(G0 + ‖∇L(W 0,Xc)− (J (W 0,Xc)T (∇xf(W 0,Xc)T +O( T ))+
(57)
E(y − f(W 0,Xc + ))‖) (58)
≤ 1√ α
( 1− αη
2
) t 2
(G0 + ‖∇L(W 0,Xc)− (J (W 0,Xc)T (∇xf(W 0,Xc)T +O( T ))‖+
(59) √
2‖E‖) (60)
≤ 1√ α
( 1− αη
2
) t 2
(G0 + ‖∇L(W 0,Xc)‖+σmaxL̄ √ n 0 + σmaxO(n 20)) + √ 2nL̄ 0) (61)
= 1√ α
( 1− αη
2
) t 2
(G0 + ‖∇L(W 0,Xf )‖+ξ + σmaxL̄ √ n 0 + σmaxO(n 20)) + √ 2nL̄ 0)
(62)
≤ 1√ α
( 1− αη
2
) t 2
(2G0 + ξ + σmaxL̄ √ n 0 + σmaxO(n 20)) + √ 2nL̄ 0) (63)

heading: A.6 FINDING SUBSETS
text: Let S be a subset of training data points. Furthermore, assume that there is a mapping πw,S : V → S that for every W assigns every data point i ∈ V to its closest element j ∈ S, i.e. j = πw,S(i) = arg maxj′∈S sij′(W ), where sij(W ) = C − ‖J T (W t,xi)ri − J T (W t,xj)rj‖ is the similarity between gradients of i and j, and C ≥ maxij sij(W ) is a constant. Consider a matrix Gπw,S ∈ Rn×m, in which every row i contains gradient of πw(i), i.e., [Gπw,S ]i. = J T (W t,xπw,S(i))rπw,S(i). The Frobenius norm of the matrixGπw 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,
‖J T (W t,Xtrain)rttrain − γStJ T (W t, [Xtrain].St)rSt‖≤ ‖Gπw,S‖F , (64)
where the weight vector γSt ∈ R|S| contains the number of elements that are mapped to every element j ∈ S by mapping πw,S , i.e. γj = ∑ i∈V 1[πw,S(i) = 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 a subset S that minimizes the Frobenius norm of matrixGπw,S .

heading: B ADDITIONAL THEORETICAL RESULTS

heading: B.1 CONVERGENCE ANALYSIS FOR TRAINING ON THE CORESET AND ITS AUGMENTATION
text: Theorem B.1 Let Li be β-smooth, L be λ-smooth and satisfy the α-PL condition, that is for α > 0, ‖∇L(W ,X)‖2 ≥ αL(W ,X) for all weights W . Let ξ upper-bound the normed difference in gradients between the weighted coreset and full dataset. Assume that the network f(W ,X) is Lipschitz in W , X with Lipschitz constant L and L’ respectively, and L̄ = max{L,L′}. Let G0 the gradient over the full dataset at initialization, σmax the maximum Jacobian singular value at initialization. Choosing perturbation bound 0 ≤ 1
σmax √ L̄n 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 η = αλβ , we get the following convergence bound:
E[‖∇L(W t,Xc+caug)‖] ≤ 1√ α
( 1− αη
2
) t 2 ( 2G0 + 2ξ +O ( L̄
σmax
)) , (65)
whereXc+caug 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
E[‖∇L(W t,Xc+caug)‖2] ≤ (
1− αη 2
)t L(W 0,Xc+caug) (66)
≤ 1 α
( 1− αη
2
)t ‖∇L(W 0,Xc+caug)‖2 (67)
Thus, we can write
E[‖∇L(W 0,Xc+caug)‖] (68) ≤ √
E[‖∇L(W t,Xc+caug)‖2] (69)
≤ 1√ α
( 1− αη
2
) t 2 ‖∇L(W 0,Xc+caug)‖ (70)
≤ 1√ α
( 1− αη
2
) t 2 (‖∇L(W 0,Xc)‖+‖∇L(W 0,Xcaug)‖) (71)
≤ 1√ α
( 1− αη
2
) t 2 ( G0 + ξ + ‖(J (W 0,Xc) +E)(−f(W 0,Xc + ))‖ ) (72)
The rest of the proof is similar to that of Theorem 4.2.

heading: B.2 LEMMA FOR EIGENVALUES OF CORESET
text: 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, i.e. for full data X and its corresponding coreset XS with weights γS , and respective residuals r, rS , we have the bound ‖J T (W t,X)rt − γSJ T (W t,XS)rtS‖≤ ξ. Let {λi}ki=1 be the eigenvalues of the NTK associated with the coreset. Then we have that
√√√√ k∑ i=1 λi ≥ |‖J T (W t,X)rt‖−ξ| ‖rtS‖ .
Proof Let singular values of coreset Jacobian be σi. Let J T (W t,X)rt = γSJ T (W t,XS)rtS+ξS where ‖ξS‖≤ ξ.
Taking Frobenius norm, we get
‖γSJ T (W t,XS)rtS‖= ‖J T (W t,X)rt − ξS‖ (73) ⇒‖γSJ T (W t,XS)‖‖rtS‖≥ ‖J T (W t,X)rt − ξS‖ (74)
⇒‖γSJ T (W t,XS)‖≥ ‖J T (W t,X)rt − ξS‖
‖rtS‖ (75)
⇒ √√√√ s∑ i=1 σ2i ≥ ‖J T (W t,X)rt − ξS‖ ‖rtS‖ (76)
⇒ √√√√ s∑ i=1 λi ≥ ‖J T (W t,X)rt − ξS‖ ‖rtS‖ (77)
⇒ √√√√ s∑ i=1 λi ≥ |‖J T (W t,X)rt‖−ξ| ‖rtS‖ by reverse triangle inequality (78)
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 is large. In this case, the Jacobian matrix associated with small weighted coresets found by solving Eq. (11), have large singular values.

heading: B.3 AUGMENTATION AS LINEAR TRANSFORMATION: LINEAR MODEL ANALYSIS
text: We introduce a simplified linear model to extend our 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 a linear model when applied to coresets.

heading: B.4 LINEAR CASE (1 INPUT LAYER, 1 OUTPUT LAYER)
text: Lemma B.3 (Augmented coreset gradient bounds: Linear) Let f be a simple linear model with weights W ∈ Rd×C where f(W ,xi) = W Txi, trained on mean squared loss function L. Let F ∈ Rd×d be a common linear augmentation matrix with norm ‖F‖ with augmentation xaugi given by Fxi. Let coreset be of size k and full dataset be of size n. Further assume that the predicted label of xi and its augmentation Fxi are sufficiently close, i.e. there exists ω such thatW T (Fxi) = W Txi + zi, ‖zi‖≤ ω ∀i. 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
‖ ∑ i∈V ∇L(W ,xaugi )− k∑ j=1 γsj∇L(W ,xaugsj )‖≤ ‖F‖(ξ + √ dnω)
for some (small) constant ξ.
Proof By our assumption, we can begin with,
‖ ∑ i∈V ∇L(W ,xi)− k∑ j=1 γsj∇L(W ,xsj )‖≤ ξ (79)
Furthermore, by Mirzasoleiman et al. (2020a), we know that sum of the coreset weights γsj is given by ∑k=1 j=1 γsj ≤ n.
Hence,
‖ ∑ i∈V ∇L(W ,xaugi )− k∑ j=1 γsj∇L(W ,xaugsj )‖ (80)
= ‖ ∑ i∈V (J (W ,xaugi )) T [W T (Fxi)− yi]− k∑ j=1 γsj (J (W ,xaugsj )) T [W T (Fxsj )− ysj ]‖ (81) = ‖ ∑ i∈V Fxi[W T (Fxi)− yi]− k∑ j=1 γsjFxsj [W T (Fxsj )− ysj ]‖ (82) = ‖F ∑ i∈V xi(W Txi − yi)− F k∑ j=1 γsjxsj (W Txsj + zi − ysj )‖ (83) = ‖F ∑ i∈V ∇L(W ,xi)− F k∑ j=1 γsj∇L(W ,xsj )− F k∑ j=1 γsjxsjzsj‖ (84) ≤ ‖F‖‖ ∑ i∈V ∇L(W ,xi)− k∑ j=1 γsj∇L(W ,xsj )‖+‖F‖‖ k∑ j=1 γsjxsjzsj‖ (85) ≤ ‖F‖ξ + √ d‖F‖nω (86) = ‖F‖(ξ + √ dnω) (87)
Corollary B.4 In the simplified linear case above, the difference in gradients of the full training data with its augmentations (∇L(W ,Xf+aug)) and gradients of the coreset with its augmentations (∇L(W ,Xc+caug )) can be bounded by
‖∇L(W ,Xf+aug)−∇L(W ,Xc+caug )‖≤ (‖F‖+1)ξ + √ d‖F‖nω
Proof Applying Eq. (79) and Lemma B.3, we obtain
‖∇L(W ,Xf+aug)−∇L(W ,Xc+caug )‖ (88) = ‖(∇L(W ,Xf ) +∇L(W ,Xaug))− (∇L(W ,Xc) +∇L(W ,Xcaug ))‖ (89) = ‖(∇L(W ,Xf )−∇L(W ,Xc)) + (∇L(W ,Xaug)−∇L(W ,Xcaug ))‖ (90) ≤ ‖(∇L(W ,Xf )−∇L(W ,Xc))‖+‖(∇L(W ,Xaug)−∇L(W ,Xcaug ))‖ (91)
≤ ξ + ‖F‖(ξ + √ dnω) (92) = (‖F‖+1)ξ + √ d‖F‖nω (93)
Theorem B.5 (Convergence of linear model) Let f be a linear model with weights W and augmentation be represented by the common linear transformation F . Let Li be β-smooth, L be λ-smooth and satisfy the α-PL condition, that is for α > 0, ‖∇L(W ,X)‖2 ≥ αL(W ,X) for all weightsW . Let ξ upper-bound the normed difference in gradients between the weighted coreset and full dataset and ω bound W T (Fxi) = W Txi + zi, ‖zi‖≤ ω ∀i. Let G′0 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 η = αλβ , we get the following convergence bound:
E[‖∇L(W t,Xc+caug)‖] ≤ 1√ α
( 1− αη
2
) t 2 ( G′0 + (‖F‖+1)ξ + √ d‖F‖nω )
Proof From Bassilyet al. (2018), we have E[‖∇L(W t,Xc+caug)‖2] ≤ (
1− αη 2
)t L(W 0,Xc+caug) (94)
≤ 1 α
( 1− αη
2
)t ‖∇L(W 0,Xc+caug)‖2 (95)
(96)
Using Jensen’s inequality, we have
E[‖∇L(W t,Xc+caug)‖] (97) ≤ √
E[‖∇L(W t,Xc+caug)‖2] (98)
≤ 1√ α
( 1− αη
2
) t 2 ‖∇L(W 0,Xc+caug)‖ (99)
≤ 1√ α
( 1− αη
2
) t 2 ( G′0 + (‖F‖+1)ξ + √ d‖F‖nω ) (100)
where the last inequality follows from applying Corollary B.4.

heading: C APPENDIX C: EXTRA EXPERIMENTS

heading: C.1 FULL RESULTS FOR TABLE 1
text: This section contains full experiment results including standard deviations and the full augmentation benchmark for Table 1. Augmenting coresets of size 10% achieves 51% of the improvement obtained from augmentation of the full data and further enjoys a 6x speedup in training time on CIFAR10. This speedup becomes more significant when using strong augmentation techniques which are mostly computationally demanding, especially when applied to the entire dataset.

heading: C.2 SPEED-UP MEASUREMENTS
text: 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/Resnet32 using 30% coresets, we sacrifice 10% of the speed-up to obtain an additional 24.8% of the gain in accuracy from full data augmentation when compared to a random subset of the same size.

heading: C.3 TRAINING ON FULL DATA AND AUGMENTING SMALL SUBSETS RE-SELECTED EVERY EPOCH
text: We apply our proposed method to select a 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 a 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 the most crucial for data augmentation. Hence, it can achieve a 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 coresets of size 0.2%. Furthermore, despite the random baseline 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, as default augmentations on the full training data are 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.

heading: C.4 ADDITIONAL VISUALIZATIONS FOR TRAINING ON CORESETS AND ITS AUGMENTATIONS - MEASURING TRAINING DYNAMICS OVER TIME
text: 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.
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 6 suggest that a similar pattern holds in this setting. We also qualitatively visualize this in Figure 7.

Review summaries:
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.

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. Then they propose a new method to iteratively extract a subset of the training data that when augmented closely capture the full augmented data dynamics. Authors 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.