Soft Sampling for Efficient Training of Deep Neural Networks on Massive Data
Authors: Xiaodong Cui
Ashish Mittal
Songtao Lu
Wei Zhang
George Saon
Brian Kingsbury
Venue: Submitted to ICLR 2023 (2023)

Abstract: We investigate soft sampling which is a simple yet effective approach for efficient training of large-scale deep neural network models when dealing with massive data. Soft sampling selects a subset uniformly at random with replacement from the full data set in each epoch. First, we derive a theoretical convergence guarantee for soft sampling on non-convex objective functions and give the convergence rate. Next, we analyze the data coverage and occupancy properties of soft sampling from the perspective of the coupon collector's problem. And finally, we evaluate soft sampling on various machine learning tasks using various network architectures and demonstrate its effectiveness. Compared to existing coreset-based data selection methods, soft sampling offers a better accuracy-efficiency trade-off. Especially on real-world industrial scale data sets, soft sampling can achieve significant speedup and competitive performance with almost no additional computing cost.

Under review as a conference paper at ICLR 2023
SOFT SAMPLING FOR EFFICIENT TRAINING OF DEEP NEURAL NETWORKS ON MASSIVE DATA
Anonymous authors Paper under double-blind review
ABSTRACT
We investigate soft sampling which is a simple yet effective approach for efficient training of large-scale deep neural network models when dealing with massive data. Soft sampling selects subset uniformly at random with replacement from the full data set in each epoch. First, we derive a theoretical convergence guarantee for soft sampling
non-convex objective functions and give the convergence rate. Next, we analyze the data coverage and occupancy properties of soft sampling from the perspective of the coupon collector's problem. And finally, evaluate soft sampling on various machine learning tasks using various network architectures and demonstrate its effectiveness. Compared to existing coreset-basee data selection methods, soft sampling offers a better accuracy-effciency trade-off. Especially on real-world industrial scale data sets, soft sampling can achieve significant speedup and competitive performance with almost no additional computing cost.
INTRODUCTION
Deep learning (LeCun et al.
2015) has made great progress in broad variety of domains in recent
years (Silver et al. 2016 Esteva al. 2017 Saon et al. 2017 Xiong al., (017). The high
performance of deep neural network models having huge numbers of parameters relies on large amounts of training data (Brown al. 2020 Parthasarathi et 2019 Chowdhery et al. 2022). This
comes with a cost of long training time and demands substantial computing and storage resources. High computational complexity sometimes becomes barrier the dyper-paramett tuning and model validation steps that are crucial for real-world deployments. In this situation, data selection is often used to select a representative subset of the entire training data to speed up the training while maintaining decent model performance.
Subset selection has been shown to be an effective approach to alleviating the computational cost in large scale machine learning (Mirzasoleiman et al., 2020a] Borsos et al. 2021 Kowal 2022 Guo 2022). It is also used in distributed training to reduce the communication cost (Reddi et al.
ct al.
2015 and active learning create compact sets for human labeling (Hakkani Tur et al., (202 Tur ct al. 2003 Kaushal et al., 2019; Coleman et al.] 2020). Usually a subset is selected based on some criterion such that the performance of model trained on the subset is comparable to trained on the whole dataset, but with much less data and computing efforts. A variety of criteria have been introduced in various applications in the literature. For instance, diversity reward is used in (Lin) & Bilmes 2011) for document summarization and in (Kaushal et al. 2019) for computer vision (CV). Text similarity and saturated coverage are used in (Wei et al.) 2013) to select acoustic data for automatic speech recognition (ASR). The maximum entropy principle is applied in (Wu et al. 2007 Yu et al. 2009) to select an informative data subset. Confidence scores are used in (Hakkani Tur
et al. 2002 Tur et al. 2003) based on a well-trained model to select a subset with highest uncertainty for labeling for active learning. In (Sivasubramanian et al. (021) error bounds on the validation set
taken into account when selecting a data subset for & regularized regression problems for better model generalization. In (Mirzasoleiman et al. 2020aa] Killamsetty et al. 222 1a) subsets are selected to closely approximate the full gradient for training machine learning models using incremental gradient methods.
The construction of an optimal subset is combinatorial and ha-hard in principle. In (Wei et al. 2013; 2013; 20144 at Kirchhoff & Bilmes] 2014] Killamsetty et al. (2021b) subsets are selected leveraging submodular functions with diminishing returns where the subset selection can be formulated as

---

Under review as a conference paper at ICLR 2023
constrained submodular cover optimization (Fujishige 1991p. Subset selection is also viewed as summarizing the full data set using a coreset (e.g. weighted subset samples) in (Mirzasoleiman et al. 2020a b. Reddi et al. 2015 Coleman et al. 2020: Killamsetty et al. 2021ab. Most of the subset construction algorithms are greedy algorithms which are computationally efficient, and some of them can provide provable approximation guarantees compared to the solution on the full data set. For many of the existing data selection approaches, the selection is hard selection where a subset of the full data is selected and models are trained on this constant subset of data while the samples outside the subset are totally discarded (Wu et al., [007] Lin & Bilmes] 2011] Wei et al. 2014b). Furthermore, to reduce the cost of data selection, an additional night-weight proxy model introduced for selecting subsets in family of so-called selection via proxy (SVP) methods (Coleman et al., (020) Sachdeva et al. 2021). However, even with greedy algorithms which are relatively efficient in constructing subsets or selection via proxy, many of the existing data selection techniques still suffer from scaling issues when dealing with large amounts of data and models of large capacity due to demanding processing time and memory requirements (Wei et al. 2014a; Mirzasoleiman et al. 2020a).
In this paper we propose soft sampling, a simple but effective approach to training models with reduced data size for efficiency. Soft sampling selects uniformly random with replacement a subset from the full data set for each training epoch, so every data sample can be sampled with non-zero probability. The selection of data is agnostic loss functions and models. Compared to deterministic loss/cost function based data selection methods, soft sampling is significantly faster without requiring additional memory, which makes it very suitable for training deep neural networks using incremental gradient techniques such as stochastic gradient descent (SGD) and its variants. Randomized subset selection has been presented in the literature (Pooladzandi et al. 2022 Killamsetty al., 202 la
Guo et al. 2022), where it is mostly treated as an underperforming baseline. It is either compared with coreset selection methods on small datasets with a very low data selection percentage (e.g 1%) or it is not investigated at its full strength when the comparative study is made with other subset selection techniques. approach that is very computationally efficient when training deep models with a large number of parameters on large scale datasets. We study this random subset selection approach both theoretically and practically. We show that soft sampling is guaranteed converge and give its convergence rate. We also analyze its statistical properties on sample coverage and occupancy. Experiments are carried out to extensively evaluate its effectiveness on a variety of datasets from image classification and speech recognition. We show that soft sampling can obtain competitive or superior performance compared with some existing high-performance data selection approaches while being much more efficient in speed and memory usage.
this work we assess random subset selection as a low-cost data selection
2 RELATED WORK
Subset selection is cast as submodular optimization in (Lin & Bilmes 2009| 2011 Wei et al. 2013 2014b a 2015; Kirehhoff & Bilmes] 2014, Mirzasoleiman et al., 2015) where submodular functions defined on discrete sets and optimized under constraints (e.g. cardinality of the selected subset). Submodular optimization based subset selection is mathematically rigorous, as under mild conditions simple greedy implementation is theoretically guaranteed to be only constant fraction away from the optimal solution. However, despite the availability of a rich class of functions, suitable submodular functions still need to be carefully chosen and tailored the problem under investigation given the computational complexity and scale of the data. Furthermore, once the subset is selected, it usually fixed throughout the training regardless of the iteratively updated model.
Coreset al algorithms have been explored in (Mirzasoleiman et al., 2020a; Killamsetty et al. 202 lb a. Pooladzandi et al. 2202) where weighted subsets are selected to summarize some desired properties of the full data for efficient training. GLISTER, proposed in (Killamsetty et al., 2021b), selects a coreset that maximizes the likelihol on a validation set. CRAIG (Mirzasoleiman et al.) (020a) and GRAD-MATCH in (Killamsetty et al.) (021aa) each find a coreset that closely approximates the full gradient. ADACORÉ in (Pooladzandi et al., 2022) extracts a coreset that dynamically approximates the curvature of the loss function based on the Hessian matrix. CRAIG, GRAD-MATCH and ADACORE are all adaptive methods which are shown to achieve superior performance over fixed subset. ADACORE relies on second-ords statisties which are more computationally demanding, while CRAIG and GRAD-MATCH search for first-order coresets which are computationally more efficient. In this work, we compare the performance on the accuracy-efficiecy off between soft
2

---

Under review as a conference paper at ICLR 2023
sampling and BRRAD-MATCH (Killamsetty et al. 2021a). GRAD-MATCH is first-order coreset selection approach to selecting coresets to approximate the full gradient. The selection is carried out using efficient orthogonal matching pursuit (OMP) algorithm. We choose GRAD-MATOR baseline because a representative coreset selection approach and has been shown to outperform numerous existing high-performing subset selection techniques such CRAIG and GLISTER in Killlameetty et al. 202
SOFT SAMPLING
Let X' denote the input space and y the output space. The goal of machine learning is to estimate function h that maps from the input to the output
h<;; w) -
(1)
where E X' and h belongs to family of functions parameterized by Rd. A loss function fh(r;; w): y) is defined on X' x to measure the closeness between the prediction h(2; w) and the output y. A risk function ((w) is defined as the expected loss over the underlying joint distribution p(z, y):
((w) = [f
(2)
We want to find parameters w that minimize L(w)
w" arg min L(w).
(3)
In practice, we only have access to a training set 9 of n data samples g (x; where [ = n and the following empirical risk is minimized
1/ E x
1 Σ G
Eg (w)
(h((::)).ul
(4)
EEG
Incremental gradient methods such as SGD (Bottou al. 2016 Bottou & Bousquet 2007) and its
variants (Kingma & Ba 2015 Nesterov 1983) have been the dominant approach in solving this optimization problem where iteration sample (Ii, My i E {I, nj., is drawn random
from and its stochastic gradient fú, is then used to update w with an appropriate stepsize a >
0++1 wi a a (wr).
(5)
When dealing with large scale machine learning, mini-batch based incremental gradient methods commonly used for better trade-off between computing cost and approximation error (Bottou et al.) 2016).
In case of a massive training set G, subset V C G (V) < ( ) is selected and the optimization is carried out only on for computing efficiency. generic form, training after data selection can be given as
Lv, (w)
Σ SEVE
((h2::w)),) ys)
(6)
[VA
where V/ is the subset selected for each epoch & under some criterion (Wei et al. 2015 Mirzasoleiman al. 2020a Killamsetty al., 2021b a). V/8 can be constant subset some works (Lin & Bilmes
2011
Wei et | 20114)).
In this paper we investigate soft sampling that efficiently trains machine learning models using randomized subsets. Suppose Vyl m, for & 1,..... K. In each epoch k, instead of choosing a subset based on measures that are computationally demanding. we simply select a subset of size randomly from the ground set G. Suppose Ω {w1, (w . are the (*) subsets of size In each epoch, a subset is drawn with replacement from with an equal probability to be used in the optimization of Eg A detailed implementation is given in Algorithm

---

Under review as a conference paper at ICLR 2023
Algorithm Training with soft sampling
K <- Total number of epochs:
<- Total number of training samples;
f- Number of subset samples used in each epoch;
V f- SGD optimizer
Initialize wp
Create f2 = (wi, ... w consisting all subsets of size m from ground set ς for k 1,... K do
Select a subset W uniformly at random with replacement from Q Vi W
Wh +- (W VR, Liv))
4 CONVERGENCE
We assume that (A1) the loss function is smooth and gradient Lipschitz continuous with constant L; and (A2) the gradient estimate is unbiased and has bounded variance, i..,, [[V]] = vLv, (w), E| V (ww) VLv, (w))l < <o²
V and Vk.
Theorem 1. Suppose assumptions Al and A2 hold and the iterates are generated by soft sampling. When the step size of Algorithm] 7 satisfies < <1/L, we have
1
Σ E [VL(((())]
2m(Lg(ur1) [(w")) +amL (1+ n m) 0²
K
aK
where the expectation is taken over all the randomness of the subset and data sample selection process. In addition, if Lg satisfies the Polyak- Tolyak-Lojasiewier inequality with μ > 0, i.e, [[VLg 2u(Lg(w) - Lg(w" (w") )) then
E [LC((wk) - ( (1-) (Le(wi) Lc(w")) + 2akmL (1 m 0². (8)
where condition number == L/p.
Remark. Theorem [hows that when step size O(1/VK) the convergence rate of the proposed training scheme with soft sampling O(1/ (V) (i.e.. Algorithm I takes O(1/e*) number of iterations to achieve an e-approximate first order stationary point of problem Eq. Fq.Jennder the empirical risk), which the same as the standard SGD. Futher, when neural networks are overparametrized, the loss functions satisfy the Pojyak-Lojasiewicz property (Jacot et al. 2018 et al. (2022), therefore, Algorithm with soft sampling is able to achieve the global optimal solution at the rate of (1/K)) when (1/K).. Details of the proof given in Appendix A.1
5 SAMPLE COVERAGE AND OCCUPANCY
In soft sampling, subsets of samples are drawn with replacement from the ground set during training. In this section we investigate the data sample coverage and occupancy soft sampling. Given n, the total number of samples in the ground set, and m, the number of samples in the subset used in each epoch, we are interested answering the following questions:
Coverage How many samples in the ground set will we cover in training after K epochs?
Occupancy How many epochs do we need in order to cover (n) samples in the ground set?
The analysis can be cast into a balls-and-bing problem (Mitzenmacher & Uptal 2005) where there are n bins and every time m balls are drawn and dropped into m distinct bins. Each draw is independent and uniform at random. We want to analyze the distribution of non-empty bins after number of
draws. This is essentially a generalization the coupon collector's problem (Mitzemmacher & Upfal
2005) with group drawings (Stadje 1990 Holst 1986 Johnson & Kotz, 1977 David & Barton 1962) where coupons come in groups of a constant size m and all groups of coupons occur with equal probability.
4

---

Under review as a conference paper at ICLR 2023
5.1 COVERAGE
Let denote the set of distinct training samples from the ground set after K epochs of soft sampling and [S] denote the cardinality of S. The distribution of [S] is given (Stadje 1990)
P([S = =
(1)
Σ
(-1)
(m)) m
K
1= 0, .. n.
(9)
Especially, when = we have
P[[S) n)
Σ
(10)
1=0
which is the probability of covering all the training samples after K epochs soft sampling.
From Eq 9 we have the expectation
E[[S|] n 1
m
K 72
(11)
which is, on average, the number of covered training samples from the ground set after K epochs. Table the expected data coverage (in percentage) for various selection ratios ( and numbers of epochs K.
m /
K =
K ===a 20
K ===30 30
5%
40.1% %
64.2%
78.5%
10%
65.1%
87.8%
95.8%
20%
89.3%
98.8%
99.9%
Table Expected data coverage in percentage of the ground for various data selection ratios and numbers of epochs.
5.2 OCCUPANCY
Let denote the number of draws (i.c. epochs) required to cover s (sSn) samples in the ground set. The distribution of & is given as (Stadje 1990
K-1
6-1 P(K)
1
(m))
Σ
(-1)--
1=
1,2,
(12)
71
n m
mr
From Eq 12 we have its expectation
11
(n
n
n
E
(13)
m
When = n, we have
R-1
12
(.)
P(K) =
(-1
11)--i+
1i1 11
m
m
(14)
i
1=0
and its expectation
E
Σ 1=0
12
(15)
m
which is also given in (Ferranee & Saltalamacchial 2014). Eg 15 gives the number of epochs required
on average order to cover the whole training ground set given the subset size m and total sample size
5

---

Under review as a conference paper at ICLR 2023
In partieular, when we have
n-
n
k
(16)
i 71 -
1=
j=nーi
Σ ==1
11
n
1
- j=1
(-1
71
n
=nH, = n log n + O(n)
where H, Σ ] is the nth Harmonic number. Eq 16 is well-known occupancy result for the classical coupon collector's problem [Mitzenmacher & Upfal 2005).
EXPERIMENTS
We evaluate the accuracy-efficiency trade-off of soft sampling and compare with GRAD-MATCH. a high-performing coreset based subset selection approach, image classification and automatic speech recognition (ASR) tasks. For the former we use the public CIFARTO dataset. For the latter we the public Librispeech dataset and in-house Payload dataset. The Payload dataset is real-world industrial scale dataset for training product-level ASR acoustic models. We used GRAD- MATCHPB WARM (batch based GRAD-MATCH with warm start) for the experiments because it gives the best performance compared to other GRAD-MATCH implementations in (Killamsetty et al. aa). In the CIFARIO and Librispeech experiments soft sampling selects batches (similar to GRAD-MATCHPEE
while in the Payload experiments soft sampling selects chunks of data due to the storage structure of this dataset and its massive size. In the experimental results, SS denotes soft sampling and GM denotes GRAD-MATCHPP- WARM. We use R to denote the selection interval where RI stands for using different subsets for every epoch, which is the default setting for SS. R5 and R10 stand for selecting subsets every 5 and 10 epochs, respectively.
6.1 CIFAR1O
The CIFAR10 dataset (Krizhessky & Hinton 2009) has 50,000 training images and 10,000 test images in 10 classes. We use the ResNet-18 model (He et al., 2015) with 11 million parameters.
The batch size is 512 which is distributed to 4 P100 GPUs. The training ends after 320 epochs. A Nesterov accelerated SGD optimizer is used with a momentum of 0.9. The initial learning rate is 0. and it is annealed by 10x at the t6 epoch and the t40th epoch. The warm start of GM uses the 10th epoch of full data. The experimental results are given in Table 2
6.2 LIBRISPEECH
The Librispeech dataset consists 960 hours of 16kHz English audio from public domain audio books (Panayotov al. 2015). There about 30,000 utterances from 2338 speakers in the dataset with maximum duration of 35 seconds. Each utterance is converted to sequence of frames every 10ms represented by 40-dim logMel feature vector. We the test-clean split report word error rates (WERs). The acoustic model is RNN-Transducer (RNN-T) (Graves) 2012). We use the standard training recipe from Speechbrain (Ravanelli al.) 2021 The transcription network has 2 convolutional layers followed by a 4-layer bi-directional LSTM (Hochreiter & Schmidhuber
1997) and then 2 feed-forward layers. The prediction network is a single layer LST The joint network projects the 1024-dimensions embeddings from the transcription and prediction networks to the output space of 1000 Byte-pair encoding units over the vocabulary. The decoding involves an external transformer language model trained the Librispeech text. The RNN-T model has about 170 million parameters. The training uses an AdaDelta optimizer. The starting learning rate is 2.0 with annealing factor of 0.8 for the relative improvement of 0.0025 validation loss afterwards. The training is distributed on 2 A100 GPUs with a batch size of 24 utterances for 30 epochs. The warm start of GM uses the 2nd epoch of full data. The experimental results are given in Table 3

---

Under review as a conference paper at ICLR 2023
6.3 PAYLOAD
The Payload dataset consists of 56,300 hours of English spontaneous speech data after data augmen- tation. Utterances are collected from real-world ASR services. The sampling rate 8KHz. The set contains 20.3 million utterances with an average length of 10 seconds. The shortest utterances are around 0.1 seconds while the longest ones are around 333 seconds. Each utterance converted to a sequence of frames every 10ms, and every two frames are represented by 240-dim feature vector (logMel acoustic features and their first and second order derivatives), which gives rise to 10.1 billion feature vectors for the full training set. There are 8 test sets (S1 to S8) varying in duration from 1.4-7.3 hours with an average of 3.2 hours. They represent a good coverage of application domains in model deployment. The acoustic model is also an RNNN-T. It has 6 bi-directional LSTM layers in the transcription network with 1,280 cells in each layer (640 cells per direction). The prediction network single-layer uni-directional LSTT with 1024 cells. The outputs of the transcription network and the prediction network are projected down to a 256-dimensional latent space where they are combined by clement-wise multiplication in the joint network. After hyperbolic tangent nonlinearity followed by an affine transform, it connects to softmax layer consisting of 46 output units which correspond to 45 characters and the null symbol. The model has 59 million parameters. The RNN-T models are trained using the A optimizer. The learning rate starts at 5 x 100 and is annealed by V every epoch after 7 epochs. The training ends after 20 epochs. The batch size is 256 utterances which are distributed to 32 V100 GPUs. Since the dataset is large (2.4TB disk space for feature storage), is divided into 320 chunks. The training is conducted sequentially by chunks. each chunk the utterances are organized in a sorted order. This amounts to curriculum learning strategy where it starts with short utterances stabilize the training early on before gradually increasing to difficult longer utterances. SS is carried out by randomly selecting a subset of chunks. GM selects a batch subset across all chunks. The reason that GM selects entire chunks as SS will significantly sacrifice the representative nature of coreset. Furthermore, even if GM selects entire chunks it still has to go through every chunk to compute the gradient matching criterion in order to select the best subset. The warm start uses the 1s epoch of full data. Experimental results given in Table 4
Table 2: Accuracy (Acc) and training time (hours) of SS and GM on CIFARIO under various training configurations and percentage of data selection. RI denotes selection interval is every epoch and R10 denotes selection interval is every epochs.
SS_RI
SS_RTO
GM_RI
GM_R10
Ace
time
Acc
time
Acc
time
Acc
time
100%
95.08
0.60h
95.08
0.60h
95.08
0.60h
95.08
0.60h
5%
89.59
0.03h
87.24
0.03h
89.88
1.52h
87.44
0.18h
10%
92.11
0.06h
90.47
0.06h
92.11
1.55h
90.45
0.21h
20%
93.27
0.12h
92.71
0.12h
93.50
1.60h
92.63
0.27h
30%
94.29
0.18h
93.37
0.18h
93.83
1.66h
93.25
0.33h
Table 3: Word error rate (WER) and training time (hours) of SS and GM Librispeech under various training configurations and percentage of data selection. R1 denotes selection interval is every epoch and R5 denotes selection interval is every epochs.
SS_RI
SS_R5
GMRI
GM_R5
WER
time
WER
time
WER
time
WER
time
100%
4.21
103.2h
4.21
103.2h
4.21
103.2h
4.21
103.2h
1 %
6.95
8.0h
7.12
8.0h
7.09
55.3h
7.10
16.4h
5%
6.02
11.7h
6.35
11.7h
6.39
60.2h
6.41
20.9h
10%
5.65
17.0h
5.87
16.9h
5.63
64.1h
5.71
27.4h
20%
4.76
27.9h
5.08
27.8h
4.95
73.6h
5.01
35.5h
30%
4.48
36.5h
4.62
36.6h
4.55
84.2h
4.58
46.6h
it can be observed that SS has better accuracy-efficieney trade-off compared to GM considering recognition accuracy and training time. SS outperforms GM in most cases.
From Tables 2 and
4
7

---

Under review as a conference paper at ICLR 2023
Table Word error rate (WER) and training time (hours) of SS and GM on Payload under various training configurations and percentage of data selection. R1 denotes selection interval is every epoch and RIO denotes selection interval every 10 epochs. SS_R0 random subset is selected and fixed for the training. In SS RI Lnw models are trained without warm start. Note that since SS is carried out at the chunk level while GM has to be carried out at the batch level, there is extra data loading time in GM. It takes about 42 seconds to load chunk and 3.73 hours to load in all 320 chunks. That amounts to 74.6 hours for 20 epochs in the training.
S1
S2
S3
S4
S5
S6
S7
S8
Avg.
Time
100%
6.2
9.7
6.3
22.6
16.5
25.3
16.3
29.0
16.49
426.7h
SS_RO
9.7
14.5
10.4
26.8
21.2
24.3
19.0
34.4
20.04
21.7h
SS R1 _nw
9.5
14.6
9.9
26.4
21.3
24.7
19.0
33.8
19.90
22.1h
5%
SS RI
7.5
12.0
8.0
23.7
18.9
24.1
17.6
30.6
17.80
42.3h
GM_R10
7.5
12.1
7.4
23.8
18.7
25.7
17.6
31.2
18.00
128.3h
SS RO
8.2
12.6
8.3
24.5
19.7
24.0
17.7
32.3
18.41
41.6h
SS_R1_n
7.8
12.0
8.6
24.3
19.1
22.3
17.2
31.7
17.88
40.9h
10%
SS_R1
7.1
11.4
7.8
23.5
18.3
24.6
17.5
30.3
17.56
59.8h
GM RIO
7.1
11.4
7.5
23.5
18.2
26.7
18.2
30.8
17.93
192.9h
SS RO
7.2
11.1
7.9
23.8
18.0
25.0
17.7
30.5
17.65
89.0h
SS RI_nw
7.0
11.0
7.1
23.5
18.1
23.9
16.6
29.9
17.14
89.6h
20%
SS_R1
6.8
10.7
7.2
23.0
17.7
24.9
17.4
29.9
17.20
106.4h
GM.R1O
6.9
11.0
7.2
23.2
17.5
26.9
17.8
30.3
17.60
314.5h
GM only outperforms SS in cases when the selected subset is very small (e.g. 1% or 5%) and the two have the same selection interval (e.g. both with R1, R5 or R10). Even in this case, the difference of recognition accuracy between the two is not significant. However, SS has the same computational cost regardless of selection interval while GM has increasing computational cost when the selection interval is reduced. Taking that into account, SS can still outperform GM in the small subset conditions. This can be observed T (89.59%) and shorter training time (0.03h) than GM R10 (87.4 .7.44%%mom and 0. 18h), in Table 3 where for the 1% case SS_R has better WER (6.95%) and shorter training time (8h) than GM_R5 (7.10% and 16.4h), in Table 4 where for the 5% case SS_RI R.I. has better WER 17.80%) and shorter training time (42.3h) than GM.R0 (18.00% and 128.3h).
for the 5% case SS R1 has a better accuracy
The advantage of SS is apparent when the size of the dataset is large. The computational cost of data selection in GM becomes more demanding when dealing with large scale training set. In payload experiments, the data selection in GM takes about 23 hours, which is even longer than one SGD epoch using the full training data (about 21.3 hours).
55 BL 51
55 BL 5%
GN R10
3%
53
31,,00% GM A.A.L.10
83
(110 3
35.3 10%
G20 11, 10%
GM R10,10%
Figure 1: Percentage of data coverage using SS and GM for CIFARIO, Librispeech and Payload datasets when 5% and 10% subsets are selected.
Fig demonstrates the percentage of data coverage using SS and GM when 5% and 10% of data selected from the full data each epoch with different selection intervals on the three datasets. It can be seen from the figure that the coverage of distinct data samples increases both under SS and GM. If the number of epochs goes higher (e.g. 320 epochs in CIFAR10), eventually both SS and GM will tend to achieve very high coverage of distinct data samples. However, SS has obvious higher
8

---

Under review as a conference paper at ICLR 2023
coverage rate than GM does when the number of epochs are not large (e.g. 30 epochs in Librispeech and 20 epochs in Payload). In addition, due to the computational cost, GM usually can not afford to make the subset adaptive every epoch which means its selection interval is typically larger than one. For example, the selection interval is 10 epochs in CIFAR 10 and Payload and is 5 epochs in Librispeech in order to strike reasonable balance between selection accuracy and computing efficiency, Under this condition, the coverage of distinct data samples using GM is much lower than that of SS. A higher data coverage in SS could benefit the training as the models learn from more data given the same computing budget. Also note that the practically observed sample coverage in Fig[iss is in line with the theoretical estimate in Table I
DISCUSSION
The coreset based data selection methods are typically resource and time demanding. GRAD-MATCH has to go through the full training set in order to compute the full gradient, requiring (n) gradient evaluations. Furthermore, the greedy algorithm in OMP also requires ((m) evaluations of the gains when selecting data sample. When dealing with large models and massive data, the time and memory overhead could be prohibitive. Therefore the implementation of most coreset based data selection methods involves various approximations to improve efficiency. For instance, the gradient of the last layer is used to approximate the gradient of the whole model in the case of deep models, and the coreset selection is performed at the batch level instead of sample level. To guarantee good subset selection at the start of training, a warm start is often used which requires a few SGD epochs using the full data. Despite an elegant theoretical guarantee under submodularity, the fast OMP implementation may give rise to sub-optimal solutions because the approximation error is dependent on exp(->/(X + kV? mmx))): When
large. the regularized problem is not the original one anymore. When & is large. there is less theoretical benefit of selecting the subset. Compared to these first-order coresets Mirzasoleeiann af., 2020a Killamsetty al. [0021a) second order coresets (Pooladzandi et al. 2022) may face even more severe issues in scaling.
Compared to the first and second order coreset based data selection, soft sampling incurs virtually zero time and memory cost in data selection. In addition, given the selection budget, soft sampling has more flexibility in choosing the selection granularity of subsets in accordance with the data structure, which is desirable when the training data is massive (e.g. the payload data). Although for a randomly selected subset in soft sampling the approximation error can not be guaranteed to be optimal under certain criteria (e.g full gradient approximation), soft sampling can offer frequently updated subsets across epochs that can provide a higher coverage of training data under the same per-epoch budget. This may help model generalization.
If only considering accuracy, coreset based data selection has advantages in that coresets are more representative of the full training set and they can give good results with lower data sample coverage compared to soft sampling, especially under a small selection budget. It is its computational complexity that makes it less efficient on massive training data. It should be noted that for coreset based data selection a trade-off can be made between time and resources. The data selection can rely on parallelization to significantly reduce the processing time, but will meanwhile impose significant demands on CPU/GPU and memory usage.
8 CONCLUSION
In this paper we investigate soft sampling for efficient training of deep neural network models on large scale data. Soft sampling is computationally efficient with virtually no additional cost in data selection. Theoretically, we show that soft sampling has convergence guarantee on non-convex objective functions and we provide the convergence rate. We also study the data coverage and occupancy properties of soft sampling. Practically, we compare soft sampling with GRAD-MATCH. first-order coreset selection approach, on various datasets using various deep neural network models including an industrial scale ASR application. We show that soft sampling can provide a better sccurac--effiieenn trade-off, which makes it very suitable for large scale training.
a
9

---

Under review as a conference paper at ICLR 2023
REFERENCES
Zalan Borsos, Mojmir Mutny, Marco Tagliasacchi, and Andreas Krause. Data summarization via bilevel optimization. arXiv preprint arXiv:2109.12534 2021.
Léon Bottou and Olivier Bousquet. The tradeoff's of large scale learning. In Advances in Neural Information Processing Systems (NIPS), pp. 161-168, 2007.
Léon Bottou, Frank E. Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning, arXiv preprint 1606 04838, 2016.
Tom B. Brown, Benjamin Mann. Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. In Advances in Neural Information Processing Systems (NurIPS), pp. 1877-1901, 2020.
Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, Parker Schuh, Kensen Shi, Sasha Tsvyashchenko, Joshua Maynez, Abhishek Rao, Parker Barnes, Yi Tay, Noam Shazeer, Vinodkumar Prabhakaran, Emily Reif, Nan Du Ben Hutchinson, Reiner Pope, James Bradbury, Jacob Austin, Michael Isard, Guy Gur-Ari, Pengeheng Yin, Toju Duke, Anselm Lev- skaya, Sanjay Ghemawat, Sunipa Dev, Henryk Michalewski, Xavier Garcia, Vedant Misra, Kevin Robinson, Liam Fedus, Denny Zhou, Daphne Ippolito. David Luan, Hyeontaek Lim, Barret Zoph, Alexander Spiridonov, Ryan Sepassi, David Dohan, Shivani Agrawal, Mark Omernick, Andrew M. Dai, Thanumalayan Sankaranarayans Pillai, Marie Pellat, Aitor Lewkowycz, Erica Moreira, Rewon Child, Oleksandr Polozov, Katherine Lee, Zongwei Zhou, Xuezhi Wang, Brennan Saeta, Mark Diaz, Orhan Firat, Michele Catasta, Jason Wei, Kathy Meier-Helle Hellstemn Douglas Eck, Jeff Dean, Slav Petrov, and Noah Fiedel. Palm: Scaling language modeling with pathways. arXiv preprint arXiv:2204.02311, 2022.
Cody Coleman, Christopher Yeh, Stephen Mussmann, Baharan Mirzasoleiman, Peter Bailis, Percy Liang, Jure Leskovec, and Matei Zaharia. Selection via proxy: efficient data selection for deep learning. In International Conference Learning Representations (ICLR), 2020.
N. David and D. E. Barton. Combinatorial Chance. Hafner Publishing Co., New York, 1962.
Andre Esteva, Brett Kuprel, Roberto A. Novoa, Justin Ko, Susan M. Swetter, Helen M. Blau, and Sebastian Thrun. Dermatologist-leww classification of skin cancer with deep neural networks. Nature, pp. 115-118, Feburary 2017.
Marco Ferrante and Monica Saltalamacchia. The coupon collector's problem. MATerials MATemàtics, 2014:35, 2014.
Satoru Fujishige. Submodular funntiioos and optimization. Elsevier, 1991.
Alex Graves. Sequence transduction with recurrent neural networks. arXiv preprint 1rXiv:1211..33 2012.
Chengcheng Guo, Bo Zhao, and Yanbing Bai. DeepCore: A comprehensive library for coreset selection in deep learning. arXiv preprint arXiv:2204.084999 2022.
Dilck Hakkani-Tur. Giuseppe Riccardi, and Allen Gorin. Active learning for automatic speech recognition. In International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 3904-3907, 2002.
Kaiming Hc. Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Conference Computer Vision and Pattern Recognition (CVPR'I5) 15), pp. 770-778, 2015.
Sepp Hochreiter and Jurgen Schmidhuber. Long short-term memory. Neural Computation, 9()): 1735-1780, 1997.
10

---

Under review as a conference paper at ICLR 2023
Lars Holst. On birthday, collectors', occupancy and other classical urn problems. International Statistical Review, 54(1):15-27, 1986.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks, In Proceedings of Advances in Neural Information Processing Systems (NeurIPS), 2018.
Normal L. Johnson and Samuel Kotz. Um Models and Their Application. Wiley, New York, 1977.
Vishal Kaushal, Rishabh Iyer, Suraj Kothawade, Rohan Mahadev, Khoshrav Doctor, and Ganesh Ramakrishnan. Learning from less data: a unified data subset selection and active learning framework for computer vision. In IEEE Winter Conference Applications of Computer Vision, pp. 1289-1299, 2019.
Krishnateja Killamsetty, Durga Sivasubramanian, Ganesh Ramakrishnan, Abir De, and Rishabh Iyer. GRAD-MATCH: gradient matching based data subset selection for efficient deep model training. In International Conference on Machine Learning (ICML), pp. 5464 5474, 2021a.
Krishnateja Killamsetty, Durga Sivasubramanian. Ganesh Ramakrishnan, and Rishabh Iyer. GLIS- TER: generalization based data subset selection for efficient and robust learning. In Proceedings of the AAAI Conference Artificial Intelligence, pp. 81 10-8118, 2021b.
Diederik Kingma and Jimmy Ba. ADAM: method for stochastic optimization. In International Conference on Learning Representations (ICLR), 2015.
Katrin Kirchhoff and Jeff Bilmes. Submodularity for data selection in statistical machine learning. In Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 131-141, 2014.
Daniel R. Kowal. Bayesian subset selection and variable importance for interpretable prediction and classification. Journal of Machine Learning Research, 23(108):1-38, 2022.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Computer Science Department, University of Toronto, Tech. Rep, 1(4):7, 2009.
Yann LeCun, Yoshua Bengio. and Geoffrey Hinton. Deep learning. Nature, pp. 436 444, May 2015.
Hui Lin and Jeff Bilmes. How select good training-data subset for transcription: Submodular active selection for sequences. In Interspeech, pp. 510-520, 2009.
Hui Lin and Jeff Bilmes. A class of submodular functions for document summarization. In The Association for Computational Linguistics/Human Language Technology Conference (ACL/HLT), pp. 510-520, 2011.
Chaoyue Liu, Libin Zhu, and Mikhail Belkin. Loss landscapes and optimization in over-parameteriied non-linear systems and neural networks. Applied and Computational Harmonic Analysis, 59: 85-116, 2022.
Baharan Mirzasoleiman, Amin Karbasi, Ashwinkumar Badanidiyuru, and Andreas Krause, Dis- tributed submodular cover: Succinetly summarizing massive data. In Advances in Neural Informa- tion Processing Systems (NeurIPS), pp. 2881-28881 2015.
Baharan Mirzasoleiman, Jeff Bilmes, and Jure Leskovee. Coresets for data-efficient training of machine learning models. In International Conference on Machine Learning (ICML), pp. 6950- 6960, 2020a.
Baharan Mirzasoleiman, Kaidi Cao, and Jure Leskovec. Coresets for robust training of neural networks against noisy labels. In Advances in Neural Information Processing Systems (NeurIPS), pp. 11465-11477, 2020b.
Michael Mitzenmacher and Eli Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005.
Yu. E. Nesterov. A method for unconstrained convex minimization problem with the rate of conver- gence o(1 1122). Soviet Math Docl, 269:543-544 1983.

---

Under review as a conference paper at ICLR 2023
Vassil Panayotov, Guoguo Chen, Daniel Povey, and Sanjeev Khudanpur. Librispeech: an ASR corpus based on public domain audio books. 2015 IEEE international conference on acoustics, speech and signal processing (ICASSP), pp. 5200552062222 IEEE, 2015.
Sree Hari Krishnan Parthasarathi, Pranav Ladkat, Nitin Sivakrishnan, and Nikko Ström. Realizing petabyte scale acoustic modeling, IEEE Journal Emerging and Selected Topics in Circuits and Systems, 9(2):422-432 2019.
Omead Pooladzandi, David Davini, and Baharan Mirzasoleiman. Adaptive second order coresets for data-efficient machine learning. In International Conference on Machine Learning (ICML), pp. 17848-17869 2022.
Mirco Ravanelli, Titouan Parcollet, Peter Plantinga, Aku Rouhe, Samuele Cornell, Loren Lugosch, Cem Subakan, Nauman Dawalatabad, Abdelwahab Heba, Jianyuan Zhong, et al. Speechbrain: A general-purpose speech toolkit. arXiv preprint 106.0220660 2021.
Sashank J. Reddi, Barnabas Poczos, and Alex Smola. Communication efficient coresets for empirical loss minimization. In Conference on Uncertainty in Artificial Intelligence (UAI), pp. 752-761, 2015.
Noveen Sachdeva, Carole-Jean Wu, and Julian McAuley, SVP-CF: selection via proxy for collabora- tive filtering data. arXiv preprint arXiv:2109.12355 2021.
George Saon, Gakuto Kurata, Tom Sercu, Kartik Audhkhasi, Samuel Thomas, Dimitrios Dimitriadis, Xiaodong Cui, Bhuvana Ramabhadran, Michael Picheny, Lynn-Li Lim, Bergul Roomi, and Phil Hall. English conversational telephone speech recognition by humans and machines. In Interspeech, pp. 132 136, 2017.
David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis. Mastering the game of Go with deep neural networks and tree search. Nature, pp. 484-489, January 2016.
Durga Sivasubramanian, Rishabh Iyer, Ganesh Ramakrishnan, and Abir De. Training data subset selection for regression with controlled generalization error. In International Conference on Machine Learning (ICML), pp. 9202-9212, 2021.
Wolfgang Stadje. The collector's problem with group drawing, Advances in Applied Probability, 22: 866-882 1990.
Gokhan Tur, Robert E. Schapire, and Dilek Hakkani-Tur, Active learning for spoken language understanding. In International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 276-279, 2003.
Kai Wei, Yuzong liu, Katrin Krichhoff, and Jeff Bilmes. Using document summarization techniques for speech data subset selection. In North American Chapter of the Association for Computational Linguistics/Flmman Language Technology Conference (NAACL/HLTT), pp. 721-726. 2013.
Kai Wei, Yuzong Liu, Katrin Kirchhoff, Chris Bartels, and Jeff Bilmes. Submodular subset selection for large-scale speech training data. In IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 3311 3311-3315, 2014a.
Kai Wei, Yuzong Liu, Katrin Kirchhoff, and Jeff Bilmes. Unsupervised submodular subset selection for speech data. In IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 4107-4111, 2014b.
Kai Wei, Rishabh Iyer, and Jeff Bilmes. Submodularity in data subset selection and active learning. In International Conference on Machine Learning (ICMI.. pp. 1954-1963 2015.
Yi Wu, Rong Zhang, and Alexander Rudnicky. Data selection for speech recognition. In Automatic Speech Recognition and Understanding Workshop (ASRU), 2007.
12

---

Under review as a conference paper at ICLR 2023
Wayne Xiong, Jasha Droppo, Xuedong Huang, Frank Seide, Michael L. Seltzer, Andreas Stolcke, Dong Yu, and Geoffrey Zweig. Toward human parity in conversational speech recognition. IEEE/ACM Transactions on Audio, Speech, and Language Processing, 25(12):2410-2444 2017.
Dong Yu, Balakrishan Varadarajan, Li Deng, and Alex Acero. Active learning and semi-supervised learning for speech recognition: A unified framework using global entropy reduction maximization criterion. Computer Speech and Language. 24:433 444, 2009.
13

---

Under review as a conference paper at ICLR 2023
A APPENDIX
A.1 PROOF OF THEOREM 1
Recall that V4 the set of data samples randomly chosen from [n]] where [& = m < n. Also, let F {wr, ....,.. } as filtration of the iterates generated by soft sampling with w = wk. vk. We denote wi as the iterate updated by the SGD optimizer 1 times at the k epoch. Then, the iterative algorithm can be written concisely as
w = = a V. i Va-
(17)
Under the unbiasedness assumption of the gradient estimate, we know that
V [i(wAt] = Ln, (w.). Vi E Vk-
E;
(18)
According to the gradient Lipsehitz continuity of the objective function, we have
E [<Co(u(t))
L
<Lo(w)) + (V w/
1+1
w/)
-
2 1
1+1 wf
(19)
a²L
=La(w/) 0: (V Co (. F()
E
(00)
2
@ co(w))) 0z V )1
a²I
E
(21)
Q
(Lo(w)) - a: a [Cg
E
- - [
(22)
2
Q²I.
+ 2 [
(23)
S (w(k)) a (1-2) [VCg(u)))2++' (1+ m)oa 0²
(6)
(1+
(24)
n
where (a) is true because
E ({
=By,
E.
(ii Fill: E
(25)
=B5ve
(wb)) = vLo(wk),
(26)
and (b) follows due to
(v(t) - Vcg(wb)) E
E [[ VLn. (w)) + ((( -
(27)
<2 2 + m 02)
(28)
When 1 - a > 1/2, i.c., a < t. then, we have
Co(w < Co(w)) - _ (IvCg(ub)) d²L (1+ m 1
(29)
Taking the expectation over F% and applying the telescoping sum over both k and I give
K
m (Lo(wi) Lo(wx)) + a²mL (1 m m) K
0z. o
(30)
K
n
Therefore, When a OLI/VK), we have
1 K
2m((o((u)) -
Lo(wx)) -L((k)) aK
[
+ amL (1+ m m)
0²,
(31)
K
n
14

---

Under review as a conference paper at ICLR 2023
resulting in the convergence rate of (I)VK)). Alternativlly, it implies that Algorithm needs ((1/et) number of iterations to achieve an e-approximate first order stationary point (i.e., (w))l e). Applying the definition of w* gives the desired result.
1
When Lg satisfies the Polyak-Lojasicne Lojasiewicz condition, then, from Eq. we have
Lo(wx()) ) - Lg(w")
a ( - Lo(w") 2 [[
+ aZ
[1
m)
o²
(32)
$ pa) (Co(w))) Lg(w")) + 1 +
m
0²
(33)
n
mk -1
$ (1 - paa* x (Lo(w)) - [o(w")) + L
[
m
0²
Σ (1 - pa)
(34)
j=1
< - pa)* th (Cg(w1)= ()(w")) 22xmL
(1+ (1+m) m
0², Al, k
(35)
which completes the proof.
15


Reviews:
[{"review_id": "yPS-lm-6h3", "reviewer": "Reviewer_u569", "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": "", "summary_of_the_paper": "This paper analyze the soft sampling method for training DNNs, which selects a subset uniformly at random with replacement from the full data set in each epoch. Analysis of convergence rate and coverage are conducted.", "summary_of_the_review": "As the technical contribution of this paper is weak, I recommend reject.", "strength_and_weaknesses": "Strength:\n1. The theoretical analysis of convergence and coverage of the sampling method could be a useful supplement to the methodology.\n\nWeaknesses:\n1. There is no major technical contribution in this paper. Algorithm 1 seems to be a standard practice of DNN training.\n2. The theoretical results of convergence might be useful. It is not clear how the analysis coverage and occupation could be useful.\n3. The evaluation part is weak. A larger scale dataset, like ImageNet is required for evaluation for validating the effectiveness.", "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": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "nPklaMDFUgg", "reviewer": "Reviewer_BYaz", "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": "", "summary_of_the_paper": "The authors propose a method called \"Soft Sampling\" which is a data selection method for training of deep learning models. They also show some theoretical convergence guarantees and experimentally show that their method achieves similar accuracy as GradMatch (a SoTA method) while using less resources (as measured by wall-clock training time). The datasets used are CIFAR10 (image classification), Librispeech (audio to text), and their in-house Payload dataset (audio to text).\n\nThe way I understand it, Soft Sampling simply selects a random subset with replacement given the budget at each epoch, as such the subset is not pre-determined/fixed.", "summary_of_the_review": "Unless I'm missing something, which I'm hoping the authors can point out, the proposed method is not novel and has been one of the baselines that most data selection methods are always compared to. The strength of this baseline has also been observed many times before (e.g. DeepCore). As such, even though I believe the problem (data selection) to be highly important and knowing that I believe the method to be valuable, I must reject this paper.", "strength_and_weaknesses": "Strengths:\n- training time improvements on the baseline (GradMatch) are significant (e.g. when comparing GM_R1 and SS_R1 on CIFAR10)\n- theoretical guarantees are provided\n\nWeaknesses:\n- the method name is very confusing. Looking at algorithm 1, I would simply call this method a variant of random sampling. I can understand that the \"soft\" part is trying to show that the data selection is not fixed (i.e. hard), so \"soft random sampling\" (with replacement) could be a better name\n- given the above, I see no novelty in this method. Random sampling* is one of the first and most important baselines for data selection. As such, I'm surprised to see this being proposed as a novel method. The strength of this baseline has also been reported in multiple earlier works, for example, DeepCore (Chengcheng Guo et. al.) concludes: \"... although various methods have advantages in certain experiment settings, random selection is still a strong baseline.\". I believe this is a fatal flaw.\n\n\n*: I understand that \"random sampling\" can refer to different but related methods: hard vs soft (or online vs offline) as well as with/without replacement.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "fTxA9PjPWVf", "reviewer": "Reviewer_BCTj", "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": "", "summary_of_the_paper": "\n1. The paper argues in favor of random sampling (termed as soft sampling) over other methods - specifically coreset based. The argument is well understood and to summarize \n   a. The advantage of coresets in accuracy over random sampling is limited in some (maybe authors want to argue over many / most? But the evidence is provided on 3 datasets, 1 of which is very large) large scale datasets. \n   b.  On the other hand, the computational cost of coresets is usually very high which is well known and accepted. \nTo extend the argument, the time spent in coreset computation can actually be used to train models for longer times with random sampling \n\n2. The analysis seems fairly straightforward which is not a bad thing in my opinion. However, it definitely requires more scrutiny. Specifically, how is the convergence analysis different from mini-batch SGD analysis with bounded variance and smooth and lipschitz continuous ? More specifically, what new thing do we learn here ? Also, sample coverage and occupancy computations are important to understand the dynamics of random sampling in the context of training. However, to get fair understanding of the contribution, you might want to compare against a mini-batch SGD and talk about number of batches vs occupancy / coverage. (instead of epochs)\n\n3. In the results, authors use same number of epochs across different methods. However, when sampling, the number of epochs really loose their meaning. Instead, we can keep number of iterations the same . Because it is difficult to compare between, say, 10% and 20% sampling rate if the 20% is runs twice as many iterations. \n\n4. The argument that random sampling is competent for a lot of cases is a well accepted belief in the community. I am not sure if there has been a extensive study on the topic though. However, it should be noted that there will be cases where coresets will strongly outperform random sampling w.r.t accuracy and showing that random sampling beats coresets on a handful of datasets does not support using random sampling is better than coresets for training. In order to make a strong argument, i would suggest the following two directions - \n\na. Use a lot of real datasets from different domains with learning and do an extensive study confirming what people believe. Having such a study would be very useful.\nb. Else, maybe you want to make an argument in favor of random sampling even in adversarial cases. In such a case, hand design data distributions where random sampling is bad (so in terms of #iterations, coresets beat random sampling) . But in training scenarios, using the advantage of fast sampling random sampling is competent with coresets in terms of #seconds to converge. \n\n5. Also, it is not clear what the novelty of the paper is specifically because random sampling for training is the norm. It would be useful if authors would elaborate on the novelty. One interesting direction that i see in random sampling itself is this trade-off between soft-hard sampling. For example, the following two are natural extremes in random sampling, \n[softest] you pick each sample with replacement and form batches from these samples\n[hardest] you shuffle the entire dataset and make batches from this shuffled dataset. This is also what is current practice.\nYour approach is then somewhere in the middle, where you select a subset (which obviously has no repetitions) and then make batches from the subset. However the two different subset selections can have overlaps. \n\nYou can analyse effect of this granularity that you introduce w.r.t occupancy, coverage and variance of gradient estimate for convergence (in theory and simulations) and in training convergence performance (# iterations required to converge). \n\n", "summary_of_the_review": "The major concern is that the paper does not provide clear evidence to the effect that random sampling should be always preferred in training neural networks.  See points above in summary", "strength_and_weaknesses": "The paper is well written. However, it has several weaknesses. Please see the points 2, 3, 4, 5", "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": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject