Dynamic Instance Hardness
Authors: Tianyi Zhou
Shengjie Wang
Jeff A. Bilmes
Venue:  (2020)
Keywords: training dynamics
instance hardness
curriculum learning
neural nets memorization

Abstract: We introduce dynamic instance hardness (DIH) to facilitate the training of machine learning models. DIH is a property of each training sample and is computed as the running mean of the sample's instantaneous hardness as measured over the training history. We use DIH to evaluate how well a model retains knowledge about each training sample over time. We find that for deep neural nets (DNNs), the DIH of a sample in relatively early training stages reflects its DIH in later stages and as a result, DIH can be effectively used to reduce the set of training samples in future epochs. Specifically, during each epoch, only samples with high DIH are trained (since they are historically hard) while samples with low DIH can be safely ignored. DIH is updated each epoch only for the selected samples, so it does not require additional computation. Hence, using DIH during training leads to an appreciable speedup. Also, since the model is focused on the historically more challenging samples, resultant models are more accurate. The above, when formulated as an algorithm, can be seen as a form of curriculum learning, so we call our framework DIH curriculum learning (or DIHCL). The advantages of DIHCL, compared to other curriculum learning approaches, are: (1) DIHCL does not require additional inference steps over the data not selected by DIHCL in each epoch, (2) the dynamic instance hardness, compared to static instance hardness (e.g., instantaneous loss), is more stable as it integrates information over the entire training history up to the present time. Making certain mathematical assumptions, we formulate the problem of DIHCL as finding a curriculum that maximizes a multi-set function $f(\cdot)$, and derive an approximation bound for a DIH-produced curriculum relative to the optimal curriculum. Empirically, DIHCL-trained DNNs significantly outperform random mini-batch SGD and other recently developed curriculum learning methods in terms of efficiency, early-stage convergence, and final performance, and this is shown in training several state-of-the-art DNNs on 11 modern datasets.

Under review as a conference paper at ICLR 2020
DYNAMIC INSTANCE HARDNESS
Anonymous authors Paper under double-blind review
ABSTRACT
We introduce dynamic instance hardness (DIH) to facilitate the training of machine learning models. DIH is a property of each training sample and is computed as the rumning mean of the sample's 's instantaneous hardness as measured over the training history. We use DIH to evaluate how well a model retains knowledge about each training sample over time. We find that for deep neural nets (DNNs), the DIH of a sample in relatively early training stages reflects its DIH in later stages and as a result, DIH can be effectively used to reduce the set of training samples in future epochs. Specifically, during each epoch. only samples with high DIH are trained (since they are historically hard) while samples with low DIH can be safely ignored. DIH is updated each epoch only for the selected samples, so it does not require additional computation. Hence, using DIH during training leads to an appreciable speedup. Also, since the model is focused on the historically more challenging samples, resultant models are more accurate. The above, when formulated as an algorithm, can be as form of curriculum learning, we call our framework DIH curriculum learning (or DIHCL). The advantages of DIHCL, compared to other curriculum learning approaches, are: (1) DIHCL does not require additional inference steps over the data not selected by DIHCL in each epoch, (2) the dynamic instance hardness, compared to static instance hardness (e.g.. instantaneous loss), is more stable as it integrates information over the entire training history up to the present time. Making certain mathematical assumptions, we formulate the problem of DIHCL as finding a curriculum that maximizes unknown multi-set function f(-) from its partial observations, and derive an approximation bound for a DIH-produced curriculum relative to the optimal curriculum. Empirically, DIHCI--trined DNNs significantly outperform random mini-batch SGD and other recently developed curriculum learning methods in terms of efficiency, carly-stage convergence, and final performance, and this is shown in training several -ffte-oftthe-ar DNNs on 11 modern datasets.
INTRODUCTION
We study the dynamics of training machine learning model, and in particular, the difficulty a model has over time (i.e., training epochs) in learning each sample from a training set. To this end, we introduce the concept of "dynamic instance hardness" (DIH) and propose several metrics to measure DIH, all of which share the same form as a running mean over different instantaneous sample hardness measures. Let a, (i) be a measure of instantaneous (i.e., at time !) hardness of a sample, where i sample index and is time iteration index (typically a count of mini-batches that have been processed). In previous work, a, has been called the "instance hardness" (Smith et al., 2014)) corresponding to 1- 1-p (y. (z2), i.e., the complement of the posterior probability of label ys given ipput o; for the th sample under model w. We introduce three different notions of instantaneous instance hardness in this work: (A) the loss fy,, F(x;;; ((rr;))))) where .(...) is the loss function and ((:: w) is the model with parameters w, (B) the loss change [((v,, F(x;; wx)) E(js, F(T;; w/-1)) between two consecutive time steps, and (C) the prediction flip 1 [0] J. where of is the prediction of sample in step e.g., argmax, F(z;; 15] for classification. Our (A) corresponds closely to the "instance hardness" of Smith et al. (2014). However, our (B) and (C) require information from consider (A), (B), and (C) all variations of instantaneous
previous time steps. Nevertheless, instance hardness since they use information from only a very local time window around training iteration f. Dynamics is achieved when we compute running average over instantaneous instance

---

Under review as a conference paper at ICLR 2020
hardness, computed recursively as follows:
(7 x (i) + (1-7) x e (1)
T++( (1)
else,
where y E [o, 1] is a discount factor, S C V. and == [n] is the set of all n training sample indices. S, is the set of sample selected for training time by some method (e.g., a DIH-based curriculum learning (DIHCL) algorithm we introduce and study below) or simply a random batch. In general, S₁ should be large early during training, but as (i) decreases to small values for many samples, choosing significantly smaller St is possible to result in faster training and more accurate models.
We find that ry (i) can vary dramatically between different samples since very early stage (with small (). One can think of this as some samples being more memorable and are retained more easily, while other samples are harder to learn and retain. In addition, the predictions of the hard samples are less stable under changes in optimization parameters (such as the learning rate).
More importantly, once sample's ' (1) is established (i.e., once t is sufficiently but not unreasonably large) each sample tends to maintain its DIH properties. That is, a sample's 's DIH value converges relatively quickly to its final relative position amongst all of the samples DIH values. For example, if a sample's 's DIH becomes small (i.e., meaning the sample easily learned), it stays small relative to the other samples, or if it becomes large DIH (i.e., the sample is difficult to learn), it stays there. Lee., once ri( for sample has converged, its DIH status is retained throughout the remainder training. We can therefore accurately identify categories of sample hardness relatively early in the course of training. This suggests a natural curriculum learning strategy where S, corresponds mostly to those samples that are hard according to r r (t). In other words, the model concentrates on that which it finds difficult. This is similar to strategies that improve human learning, such the Leitner system for spaced repetition (Leitner 1970). This also analogous to boosting (Schapire) [990) in boosting, however, we average the instantaneous sample performance of multiple weak learners at the current time, while in DIHCL, we average the instantaneous sample performance of one strong learner over the training history.
As mentioned above, instance hardness has been studied before (Smith et al. 2014 Prudencio et al.. 2013: Smith & Martinez, 2016) where it corresponds to the complement posterior probability. More recently, instance hardness has also been studied as an average over training steps in Toneva et al. (2019) where the mean of prediction flips over the entire training history is computed. We note that Toneva et al. (2019) is special case of DIH in Eq. (1) with 7 1/r+1 and ( = T, where T is the total number of training steps. Our study generalizes Toneva et al. (2019) to the running dynamics computed during training. This therefore leads to novel curriculum learning strategy and also steps towards a better theoretical understanding of curriculum learning. Also, in Toneva et al. (2019), small neural net is trained beforehand to determine the hard samples, and this is then used to train large neural nets. In our approach, we take the average over time of a, (i), which requires no additional model inference steps and hence is computationally trivial.
Another observation we find that (i). for any sample, tends to monotonically decrease with for any i. This means, not surprisingly. that during training samples become easier in terms of small DIH (i.e., they are better learned). This also means that easy samples stay easy throughout training. and hard samples also become easier the more we train on them. If we also make (admittedly) a mathematical leap, and assume that (i) is generated by the marginal gain of an unknown diminishing returns function f(() that measures the quality of any curriculum, we can formulate DIHCL as an online learning problem that maximizes the unknown f(() by observing its partial observation (i) over time for each i. Here, f is defined over an integer lattice and has a diminishing returns property, although the function is accessible only via the gains of every element. This formulation provides setting where the quality of the learnt curriculum is provably approximately good.
As will be shown below, DIHCL performs optimization in greedy manner. At each time step t, DIHCL selects a subset S, of samples using rz(i) where the hard samples have higher probabilities of being selected relative to the easy samples. The model is then updated based only on the selected subset S; rather than V. which requires performing inference (e.g., a forward pass a DNN) only on S,. This therefore leads to speedup to the extent that |S,l < [V). The inference produces new instantaneous instance hardness (i) that is then used to update r(+1(t) as in Equation I To encourage exploration. improve stability, and get an initial estimate of r (1) for all i E V. during the first few epochs, DIHCL sweeps through the entire training set. We provide several options for DIH weightett subset sampling, which introduces different types of randomness in the selection since
2

---

Under review as a conference paper at ICLR 2020
randommess is essential in optimizing non-convex problems. Under certain additional mathematical assumptions, we also give theoretical bounds on the curriculum achieved by DIHCL compared to the optimal curriculum. We empirically evaluate several variants of DIHCL and compare them against random mini-batch SGD as well as against recent curriculum learning algorithms, and test on 11 datasets including CIFARIO, 10, CIFAR 100, STI.10, SVHN, Fashion-MNIST. Kuzushiji-MNIST Food-101, Birdsnap, FGVC Aircraft, Stanford Cars and ImageNet. DIHCL shows an advantage over other baselines in terms both of time/sample efficiency and test set accuracy.
1.1 RELATED WORK
Early curriculum learning (CL) (Khan et al. 2011: Basu & Christensen, 2013 Spitkovsky et al. 2009) work shows that feeding an optimized sequence of training sets (i.e., a curriculum), that can be designed by a human expert (Bengio et al. 2009). into the training algorithms can improve the models' performance. Self-paced learning (SPL) (Kumar et al. 2010 Tang et al., 2012at Supaancic III & Ramanan 2013 Tang et al., 2012b) chooses the curriculum adaptive some instance hardness (e.g.. per-sample e loss) during training. selects samples with smaller losses, and gradually increases the subset size over time to cover all the training data. Self-paced curriculum learning (Jiang al. (015) combines the human expert in CI. and loss-adaptation in SPI.. SPL. with diversity (SPLD) (Jiang et al. 2014) adds negative group sparse regularization term to SPL. and increases its weight increase selection diversity. Machine teaching (Khan et al. 2011 Zhu 2015 Patil et al.] 2014) aims to find the optimal and smallest training subset leading simila ar performance as tramiig on all the data. Minimax curriculum learning (MCL) (Zhou & Bilmes) 2018) argues that the diversity of samples is more critical in early learning since it encourages exploration, while difficulty becomes more useful later. It also uses a form of instantaneous instance hardness (the loss) but is not dynamic like DIH, and formulates optimization as a minimax problem. Compared to the above methods, DIHCL has the following advantages: (1) DIHCL improves the efficiency of CL since extra inference on the entire training set per step is not required; and (2) DIHCL uses DIH as the metric for hardness which is a more stable measure than instantaneous hardness.
Our paper is also related to Zhang et al. (0117), which refers to overfitting in noisy data. Our observa- tions suggest that the learning of simple patterns (Arpit et al. 2017) happen mainly amongst the easy memorable early during in training (additional discussion is given in the Appendix and Figure Our paper is also distinct from catastrophic forgetting (Kirkpatrick et al. (017), which considers sequential learning of multiple tasks, where later learned tasks make the model forget what has been learned from earlier tasks. In our work, consider single task learning and show that easy samples remain easy.
If we make certain additional mathematical assumptions (as we do in our theoretical discussion below), our work is related to online submodular function optimization. Specific forms have been studied including maximization (Streeter & Golovin, 2009 Chen & Krause 2013), maximization in the bandit setting with noisy feedback (Chen et al. 2017). and continuous submodular function maximization (Chen et al. 2018b
The work most related to ours, perhaps, is the work on instance hardness (Smith et al. 2014, Prudencio ct al. 2015 Smith& Martinez (0166). where the hardness of a sample corresponds to the complement posterior probability, as discussed above. Also, a special case of DIH was studied in Toneva et al. (2019): they compute DIH after training completes, and show that removing the easy samples (those having the smallest DIH over training set) leads to less degradation on generalization performance than removing random samples. By contrast, our study of DIH focuses its dynamics during training.
2 DYNAMIC INSTANCE HARDNESS
We start out by conducting an empirical study of DIH in DNN training. We train a WideResNet with depth of 28 and width factor 10 on CIFARIO 10 dataset, and apply modified cosine annealing learning rate schedule (Loshchilov & Hutter 2017) for multiple episodes of increasing length (300 epochs in total) and target learning rate decaying. We contend that a cyclic learning rate suits our study because: (1) it includes the most commonly used monotone decreasing schedule since the learning rate in each cycle is decreasing; (2) compared to monotone decreasing schedule, it can uncover the properties of DIH in more scenarios such as increasing learning rate and different decaying speeds of the learning rate. In the study, we test two type of instantaneous instance hardness, where a, (i) is either prediction flips or loss (i.e., cases (A) and (C) in the previous section). We visualize (1 for
3

---

Under review as a conference paper at ICLR 2020
Epoch 10
Epoch 10
reverry 20
Epoch 40
Epoch 40
meceing single
29
wct most Epoch 210
Epoch
Figure 1: LEFT: Averaged prediction flip and RIGHT: losses (mean and std.) of the three groups of samples partitioned by DIH metric (i.c.,running mean of prediction-flip) computed at epoch 10,40 and 210 during training WideResNett28--
on CIFARIO. DIH in early stage (Epoch 40) can predict the forgettable and memorable samples for later stages. The failed partition based on Epoch DIH implies the importance of sufficient exploration to accurately measure hardness over time.
all i E [50000] training samples, but divide [50000] them into three groups according to (i) (with a, (i) as prediction flips), and we do this at epoch either 10, 40, 210. For example, epoch 40, the 10,000 samples with the largest (i) comprise the first group, the 10,000 samples ones with the smallest Txo (i) comprise the next group, and the remaining 30,000 samples comprise the final group.
In Figure ! we plot the dynamics for the average prediction flips over each group (left plot) and the mean/standard deviation of loss in each group (right plot).
We observe that samples with small ri) are learned quickly in the early epochs and their losses remain small and predictions almost un- changed thereafter, indicating they are easy over time. By contrast, the samples with large (i) have large variance, i.e., their losses oscillate rapidly between small and large values, and their predictions frequently change, indicating diffi- culty. The quickly identified easy samples are never unlearnt, and do not suffer from any large loss later in the training. The hard samples are also quickly identified, and remain difficult to learn even after training for many epochs. On average, the dynamics on the hard samples is more consistent with the learning rate schedule, which implies that doing well on these samples can only be achieved at a shared sharp local min- ima. This suggests that the model generalizes better in the regions containing the easy samples than those containing the hard ones. Similar to human learning, a natural resolution is to learn the hard samples more frequently and reduce the learning on the easy, already learnt, ones. That is, based on (i) (even during the early stages when t is not large). it is prudent to apply additional training effort on hard samples and begin to ignore already learnt easy samples. Further empirical verification can be found in experiments and Figure 4 in the Appendix.
can will lorge dtoed Diva
The three strategies (A), (B), and (C) for DIH on ten hard and easy samples, each that have been randomly sampled from the top 10k samples with the largest/smallest DIH at Epoch 40.
Figure 2:
2.1 PROBLEM FORMULATION
Figure 2 shows that all three types (base on (A), (B), and (C)) of DIH metrics decrease during training for both easy and hard samples. This indicates that as learning continues, samples become less informative more training takes place. If we make additional mathematical assumptions. we can model the curriculum learning procedure as a scheme that maximizes an unknown diminishing return function f()) via only observing its marginal gains (i).
curriculum is a sequence of selected subsets, where each subset is a mini-batch of data points, Le. (S1, S2.... ......... Sr). We define function f z%o - R20 on the non-negative integer lattice zy Each point Zyo is an non-negative integer valued vector of length [V] where =(i) counts
4

---

Under review as a conference paper at ICLR 2020
how many times sample has been selected in the T training data subsets. Any subset 5 C V has a characteristic vector Eg where (i) = if E and otherwise 85(() = if & S. We also define S1 _ Ei=1 es, as a multi-set input to function f and SIze E ZZ Ideally, our goal becomes Sr), i.e. one that maximizes [(Si.T), as in:
finding the best curriculum
max
[(Si:T);
where hy is a limit on the size of the set of samples selected at time t. However, f(.) can be an arbitrary unknown function in practice. It is also intractable estimate since it measures the utility of all possible training sequences (in exponential number), so it inaccessible for optimization. As surrogate, information about ((.) might be available at each step in the form of the DIH values (i). That is, we make the mathematical assumption that there is some function f such that (i)
f(][S _ f(e; + S1==-) - f(S1:=1), then rt()) may be used in f's stead and we can optimize the unknown f(-) only based on its partial observation (i). In such case, DIHCL can be seen as a form of online optimization problem whose goal is to find a curriculum that maximizes f: at every step l, we select subset of samples (e.g., mini-batch) S, C V of size [S,] = k2 to train the model, observing only marginal gains ry (i) of f()) for each i. We can therefore define the following objective:
((SI.) A
max Sir [TT,
For simplicity, we slightly overload the notation of S1.T for function g()) so that we retain information about the subset selected every time step (i.e., we can extract S. for < & T from S1r). In practice, we update ri( only for samples in St since it is a byproduct of training (i.e., the more computation than what needed train the model on SD). Hence, for & St, (i) = r (t). Although our solution is an approximate solution to the ideal but intractable optimization in Eq. 2 give its approximation bound in Corollary I to the global optimal solution of Eq. 22. and the bound is tight (the best we can get) up to a constant factor.
information needed to update (t) requires
DIH CURRICULUM LEARNING
We arrive at a curriculum learning strategy that increases the probability learning on hard samples, and reduces learning on easy ones. However, directly solving Eq. (3) requires costly inference over all the training samples before selecting every subset S,, most previous curriculum learning methods do.
3.1 A "FREE" CURRICULUM
Most optimization algo- rithms require inference on the training samples be- fore updating the model pa- rameters, which generates the predictions and losses for the samples used for training. In step i, after the model gets trained on S,, the feedback ax(1) for i E S, is already available. However, for & St, extra inference is inevitable if the curriculum design requires instantaneous instance hard- ness on the remaining sam- ples to select next subset S411 By contrast, DIHCL relies on re()) which is a running mean of at (t), and it only updates ri) for i E St and keeps (1) for & S; unchanged, thereby saves extra computation.
Algorithm 1 DIH Curriculum Learning (DIHCL-Greedy)
input: {(x,, 9:) Hm (
m). Mhr ((.,),. F(:w);
T. T.To: 7, ? E [0
initialize: W. 17, k1 = n. ro( W4 [n]
3: for t E (1.....T) do
ift < To then
5:
S, + [n]]
else
7:
Let St = argmax Eies r
end
9: Apply optimization ((:)) and record F(x;; (e- for E Sa
W/ - - + t
Σ SES.
f(v.. F(,; (x;;w-))))
10:
Compute normalized (i) for i E S, using Eq. 44:
11:
Update dynamic instance hardness 1++1(1) using Eq. 1.: k + 7k x kGi
12:
13:
end for
At step of DIHCL, we select subset S. C [n] with large r (i) and then update the model by training on S., We then update ri) via Equation (T). Since the learning rate can change over different steps, and large learning rates means greater model change, we normalize ai()) by the learning rate
5

---

Under review as a conference paper at ICLR 2020
7-- Specifically, we use one of the following depending on if we're we're in case (A), (B), or (C):
az(i) + f(y,, F(x;; w(-1))
ax(i) (1) - [e(us F(x;; w)-1)) {(Vs, (Z -00/ TF
(4)
ax( + 1 1 05 1/ Th
DIHCL is given in Algorithm | where {(2,, is the training data, (T:: 77) is an optimization method such as SGD, 7/:T are the learning rates of steps 1 to I" and 7k is the reduction factor for subset sizes kG. DIHCL trains on more samples early on to produce an initial more accurate estimate of rz()). This is indicated by To. the number of warm start epochs over the whole training set at the start. After this, we start by selecting larger subsets each step and gradually reduce hi down to the most difficult samples as training proceeds.
A simple method to further reduce training time in the earlier stages is to extract small subset of S by encouraging the diversity of the selected samples. We gradually reduce the diversity preference as training switching to the exploitation stage (reduce X by 0 S 7> S for every step L). Inspired by MCL (Zhou & Bilmes, 2018), after line 7, we reduce St to a subset of size KG = Thk hig (0 Yke S 1) by (approximately) solving the following submodular maximization.
max 8 SS
Σ ri( + *,G(S))
(5)
iE
The function G _ + RR,, is may be any submodular function (Fujishige 2005 ) and hence we can
exploit fast greedy algorithms (Nemhauser et al. 1978 Minoux 1978 Mirzasoleiman et al.) 2015) to solve Eq. (5) with an approximation guarantee.
3.2 APPROXIMATION BOUND UNDER FURTHER MATHEMATICAL ASSUMPTIONS
If in addition to the assumption that there exists some function ʃ 2% - Rgo such that rx) (i] A f(e +
11)) we also assume that f has certain properties, then an approximation bound is achievable. The diminishing return (DR) property for I can be defined if, v0 S y::
(6) Recall that e, is a one-hot vector with all zeros except for a single one at the ith position. We also assume f is normalized and monotone, i.e., f(0)= assume the max singleton gain is bounded by 1 (max; f(e) S 1). With such an assumption, we see that (1) is monotonically decreasing with increasing t. That is, rt( monotonically decreasing is necessary, but not sufficient, condition for the DR property on f to hold. Empirically we observe, in Figure 2 that rz (i) is indeed decreasing, meaning this evidence does not rule out there being DR function governing ri(i)'s 's behavior. On the other hand, this of course does not guarantee the DR property. Nevertheless, if it is the case that ri( is produced above from some DR function, it enables the following analysis to proceed.
f(x + f(x) > f'y + es) (w))
and f(x)) S f(y), 4 S. y. W.l.o.g.
Under the above assumptions, we may derive bounds of DIHCL-Greedy(Allg when K2 = k Vt E [T). For simplicity, assume mod A = 0 and let m A g. We first show the bound on function g of observed gains, and then connect the unknown function f.
Theorem 1. For f Zy + R200 on ground set V with DR property, compared to any solution Si. Sy.r, the solution of DiHec-Greedy, achieves
-- k g(Si.T),
g(S1:T) + Cf.m 2 max
k ' 2n
Where Cy. A m min g(A1m) such that U
Ai = V, and |Ag = K.
Corollary 1. f(SAT))++ + k c 2 max {
1---1 4 2n f(Si.T)
The proofs are given the Appendix. The Cy,m term in the bound reflects our loss during the warm start phase, where cannot estimate the gain of each sample unless we select each sample at least once, which is independent of T and vanishes in the long run. The - e comes from the DR property and our greedy procedure. For the 1 /k factor and the k/n factor of the bound on y. we give hard cases in the Appendix so our bound tight to constant factors. These factors result from
We use 7t-1 instead of 77 hecause (1) is computed based Mt-1 before the weight update in step

---

Under review as a conference paper at ICLR 2020
assumption about the function f. which may have arbitrary interactions among data points. In practice, similar data points tend to have similar DIH, and we can incorporate such information by adding an additional term of submodular function G to the DIH value to model data point interactions.
3.3 PRACTICAL METHODS FOR DIH-WEIGHTED SAMPLING IN DIHCL
In line 7 of Alg. | we select St with the highest 1 values. In practice, we find adding randomness the selection procedure gives better performance as (1) exploration on samples with small re(i) is necessary for accurate estimate to re()), and (2) randomness of training samples is essential to achieve a good quality solution w for non-convex models such DNNs. Instead of choosing greedily the top ki samples, we perform random sampling with probability Pt.i X h (i)), where h(-) is a monotone non-decreasing function, and we still prefer data points with high DIH. An ideal choice of (.) should balance between the exploration of data with poorly estimated DIH and exploitation of data with well estimated DIH. We propose the following three sampling methods to replace line of Alg. and give extensive evaluations in the experiment section.
DIHCL-Rand: Let (i)) (i). We sample data points weighted by their DIH values.
We trade-off exploration and exploitation similarly to Exp3 (Auer et al.) 2003). which samples based on the softmax value and reweigh the observation by the selection probability to encourage exploration:
DIHCL-Exp:
h(ra(i)) = exp /2log x ri()). (i) + ac(il/pss Vi E St.
(8) DIHCL-Beta: We utilize the idea of Thompson sampling Thompson 1933) and use Beta distribution prior to balance exploration and exploitation, i.e., (+) (rta(r: - ri)),
where e is sufficiently large constant that 2 re()), e.g. when (i) is prediction flip. The Beta distribution encourages exploration when the difference between T (i) and c c (i) is small.
Table 1: The final test accuracy (%) achieved by different methods training DNNs on 11 datasets (without pre-training). We use "Loss, dLoss, Flip" respectively denote the 3 choices of DIH metries based (A), (B), and (C) respectively. all DIHCL variants, we apply fazier-than taaee-ttha------eaeee
(Mirzasoleiman al. 2015 for
Eq. (5) on all datasets except Food-101, Birdsnap, Aireraft (FGVC Aireraft), Cars (Stanford Cars), and NetgNNet.
Curriculum
CIFARIO CIFAR100 Food-101
ImageNet
STL10
SVHN KMNIST FMNIST Birdsnap Aircraft Cars
Rand mini-hatch
96.18
79.64
83.56
75.04
86.06
96.48
98.67
95.22
64.23
74.71
78.73
SPL
93.55
80.25
81.36
73.23
81.33
96.15
97.24
92.09
63.26
68.95
77.61
MCL.
96.60
80.99
84.18
75.09
88.57
96.93
99.09
95.07
65.76
75.28
76.98
DHICI Rand, Loss
96.76
80.77
83.82
75.41
87.25
96.81
99.10
95.69
65.62
79.00
80.91
DIHCL-Rand, dLoss
96.73
83.82
75.34
96.83
99.14
78.70
DIICC Exp. Loss
97.03
82. 23
84.65
75.10
88, 36.36
96.91
99.20
95.45
66.13
77.66
79.85
DIHCL-Exp, di nos
96.40
84.75
75.62
96.80
99.18
95.50
66.59
79.72
DIICC Beta, Flip
96.51
81.06
84.94
76.33
86.88
97.18
99.05
95.66
65.48
78.49
80.13
4 EMPIRICAL EXPERIMENTAL EVALUATION
We train different DNNs by using variants of DIHCL, and compare them with three baselines, vanilla random mini-batch SGD, self paced learning (SPL) (Kumar et al.) 2010), and minimax curriculum learning (MCL) (Zhou& & Bilmes 2018) on 11 image classification datascts (without pre-training). i.c..
(1) WideResNet-22 28- 10 (Zagoruyka ko & Komodakis 2016) on CIFAR 10 and CIFAR 100 (Krizhevsky & Hinton :0in:) (2) ResNeX 32x4d (Xic al. 2017) on Food- 101 (Bossard et al. 2014). FGVC Aircraft (Aircraft) Maji et al., 2013), Stanford Cars (Krause et al., 2013). and Birdsnap (Berg et al. 2014); (3) ResNer50 et al. (2016) on ImageNet (Deng et al.) 2009); (4) NideResNee-16--1 on
Fashion-MNIST (FMNIST) (Xiao et al. 2017) and Kuzushiji-MNi MNIST (KMNIST) (Clanuwat et al.
2018); (5) PreActResNer34 He et al. (016) on STL10 (Coates et al. 2011) and SVHN (Netzer et al.
2011). We use mini-bated SGD with momentum of 0.9 and cyelic cosine annealing learning rate schedule (Loshchilov & Hutter 2017) (multiple episodes with starting/target learning rate decayed by multiplicative factor 0.85). We use Tú 5, Y 0.95, 7 0.85 for all DIHCL variants, and gradually reduce & from n to 0.2n. On each dataset, we apply each method to train the same model for the same number of epochs, but each method may select different amount of samples per epoch. More details about the datasets and settings can be found in the Appendix. For DIHCL variants that further
reduce S, by solving Eq. (5) use X1 =1.0, 7A 0.8, TK- 0.4 and employ the "facility location"
7

---

Under review as a conference paper at ICLR 2020
submodular function (Coruueools et al. 1977 G(S) Ejes, maxes wiy where wij represents the similarity between sample Ti and z.. We utilize Gaussian kernel for similarity using neural net features (e.g., the inputs to the last fully connected layer our experiments) =(x) for each x, i.e.
wij exp (- (1)) (afli))>>(a))))) ((as)ll /20"), where the mean value of all the 11/2 pairwise distances.
random
MCL
WIHCL-Raand-Diverr
DIHCL-Rand Diverse, cLess
DiHCL-Exp-DDeee Loss
DIHCL Exp Diverse, dloss
DIHCL -ee---Bet----eeee Diverse. Flip
random mini- mini-batch batch SPL
DIHCI-Rand, Loss
Dand dLoss
DIHO Loss
DIHC dLoss
rumber nagiing betches Betch
random mini-hatch
MCL
DiHCL-Rand, Loss
cLoss
DIHO
DIHO-Feap -Fap, Loss
DiHC,EEpp, dLoss
Dita
random mini minc- batch SPL
MCL
DiHCL-Rand,
DIHCL-Rand, closs
DIHCL-Ekp,
DIHCL-Exp, dLoss
DIHCL Flip
néo
Figure 3: Training DNN' by using DIHCL (and its variants), SPL Kumar et al. 2010 MCL (Zhou & Bilmes 2018). and random mini-batch SGD on CIFARIO, Food-101, FGVC Aurraalt and Birdsnap. We use "Diverse" to denote DIHCL that further reduces St by applying submodular maximization for Eq. (5. We report how the test accuracy changes with the number of training batches for each method.
In Figure we show how the test set accuracy changes when increasing the number of training batches in each curriculum learning method on 3 datasets. The results for other 8 datasets can be found in the Appendix, together with the wall-clock time for (1) the entire training and (2) the submodular maximization part in DIHCL with diversity and MCL. The final test accuracy achieved by each method is reported in Table DIHCL and its variants show significantly faster and smoother gains test accuracy than baselines during training especially at earlier stages. They also achieve higher final accuracy and show improvements in sample efficiency (meaning they reach their best performance sooner, after less computation has taken place). MCL can reach similar performance as DIHCL on some datasets but it shows less stability and requires more computation for submodular maximization. We also observe similar instability of SPL. The reason is that, compared to the methods that use DIH, both MCL and SPL deploy instantaneous instance hardness (i.e., current loss) as the score to select samples, measure that more sensitive to randomness and perturbation that occurs during training. Compared to MCL and DIHCL, SPL and the random mini- -atch curriculum method requires more epochs reach their best accuracy, since they spend training effort on the easier and memorable samples but lack sufficient repeated-learning of the forgettable ones. Although every variant of DIHCL achieves the best accuracy among all the evaluated methods using loss and DIHCL-Beta using prediction flip, as the instantaneous hardness, exhibit advantages over the other DIHCL variants. One possible explanation is that the running mean computed on the
datasets, DIHCL-Exp
8

---

Under review as a conference paper at ICLR 2020
loss and prediction flips more stable along the training trajectory shown in Figure 2 perhaps they are more line with our assumption in Section 3.2 about the diminishing return property of ʃ()).

---

Under review as a conference paper at ICLR 2020
REFERENCES
Devansh Arpit, Stanislaw Jastrzæbski, Nicolas Ballas, David Krueger, Emmanuel Bengio, Maxinder S. Kanwal, Tegan Maharaj, Asja Fischer, Aaron Courville, Yoshua Bengio, and Simon Lacoste-Julien. A closer look at memorization in deep networks. In ICML, volume 70, pp. 233-242, 2017.
Peter Auer, Nicolò Cesa-Biande Yoav Freund, and Robert E. Schapire. The nonstochastic multiarmed bandit problem. SIAM J. Comput., 32(1))48-77, 2003.
Sumit Basu and Janara Christensen. Teaching classification boundaries to humans. In AAAI, pp. 109-115, 2013.
Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston, Curriculum learning. In ICML, pp. 41 48, 2009.
Thomas Berg, Jiongxin Liu, Seung Woo Lee, Michelle L. Alexander, David W. Jacobs, and Peter N. Belhumeur. Birdsnap: Large-scale fine-grained visual categorization of birds. In Proc. Conf. Computer Vision and Pattern Recognition (CVPR), 2014.
Lukas Bossard, Matthieu Guillaumin, and Luc Van Gool. Food-101 mining discriminative compo- nents with random forests. In ECCV, 2014.
Lin Chen, Andreas Krause, and Amin Karbasi. Interactive submodular bandit. In Advances in Neural Information Processing Systems, pp. 141-152, 2017.
Lin Chen, Christopher Harshaw. Hamed Hassani, and Amin Karbasi. Projection-free free free online optimiza- tion with stochastic gradient: From convexity to submodularity. arXiv preprint arXiv: arXiv:1802.08// 180.00813, 8a.
Lin Chen, Hamed Hassani, and Amin Karbasi. Online continuous submodular maximization. arXiv preprint wwXiv:1802.00022 2018b.
Yuxin Chen and Andreas Krause. Near-optimal batch mode active learning and adaptive submodular optimization. In International Conference on Machine Learning, pp. 160-168, 2013.
Tarin Clanuwat, Mikel Bober-Irizar, Asanobu Kitamoto, Alex Lamb, Kazuaki Yamamoto, and David Ha. Deep learning for classical japanese literature, 2018.
Adam Coates, Honglak Lee, and Andrew Y. Ng. An analysis of single-layer networks in unsupervised feature learning. In AISTATS, pp. 215-223, 2011.
G. Cormuéjols, M. Fisher, and G.L. Nemhauser. On the uncapacitated location problem. Annals of Discrete Mathematics, 1: 1:163-177, 1977.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. ImageNet: A large-scale hierarchical image database. CVPR, 2009.
Satoru Fujishige. Submodular functions and optimization. Annals of discrete mathematics. Elsevier, 2005.
Kaiming He. Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 770-778, 2016.
Lu Jiang, Deyu Meng, Shoou-I Yu, Zhenzhong Lan, Shiguang Shan, and Alexander G. Hauptmann. Self-paced learning with diversity. In NeurIPS, pp. 2078-2086, 2014.
Lu Jiang, Deyu Meng, Qian Zhao, Shiguang Shan, and Alexander G. Hauptmann. Self-paced curriculum learning. In AAAI, pp. 2694-2700, 2015.
Faisal Khan, Xiaojin (Jerry) Zhu, and Bilge Mutlu. How do humans teach: On curriculum learning and teaching dimension. In NewrIPS, pp. 1449-1457, 2011.
10

---

Under review as a conference paper at ICLR 2020
James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei A. Rusu, Kieran Milan, John Quan, Tiago Ramalho, Agnieszka wyraska-BBawiinse Demis Hassabis, Claudia Clopath, Dharshan Kumaran, and Raia Hadsell. Overcoming catastrophic forgetting in neural networks. Proceedings of the National Acudemy of Sciences (PNAS), 114(13)3521-3556 2017.
Andreas Krause and Cheng S Ong. Contextual gaussian process bandit optimization. In Advances in Neural Information Processing Systems, pp. 2447-2455, 2011.
Jonathan Krause, Michael Stark, Jia Deng, and Fei-Fei. 3d object representations for fine-grained categorization. In 4th International IEEE Workshop on 3D) Representation and Recognition (3dRR-13), Sydney, Australia, 2013.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
M. Pawan Kumar, Benjamin Packer, and Daphne Koller. Self-paced learning for latent variable models. In NeurlPS, pp. 1189-1197, 2010.
Sebastian Leitner. Leitner system, 1970.
URL https://en, http:///w..kkkppcia...oo////////
Leitner system
I. Loshchilov and F. Hutter. Sgdr: Stochastic gradient descent with warm restarts. In ICLR, 2017.
S. Maji, J. Kannala, E. Rahtu, M. Blaschko, and A. Vedaldi. Fine-grained visual classification of aircraft. Technical report, 2013.
Michel Minoux. Accelerated greedy algorithms for maximizing submodular set functions. In Opti- mization Techniques, volume of Lecture Notes in Control and Information Sciences, chapter 27, pp. 234-243. Springer Berlin Heidelberg, 1978.
Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, Amin Karbasi, Jan Vondrák, and Andreas Krause. Lazier than lazy greedy. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, pp. 1812-18 1818, 2015.
G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher. An analysis of approximations for maximizing submodular set functions. Mathematical Programming, 14(1):265-294, 1978.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y. Ng. Reading digits in natural images with unsupervised feature learning. In NeurIPS Workshop Deep Learning and Unsupervised Feature Learning, 2011.
Kaustubh R Patil, Xiaojin Zhu, t ukasz Kopeé, and Bradley C Love. Optimal teaching for limited- capacity human learners. In NeurlPS, pp. 2465-2473, 2014.
Ricardo B. C. Prudencio, Jose Hernandez-Orallo, and Adolfo Martinez-Uso. Analysis of instance hardness machine learning using item response theory. In 2nd International Workshop on Learning over Multiple Contexts (LMCE 20/5), 2015.
Robert E. Schapire. The strength of weak learnability. Machine Learning, 5(2):197-227, 1990.
Michael R. Smith and Tony Martinez. A comparative evaluation of curriculum learning with filtering and boosting in supervised classification problems. Comput. Intell., 32(2):167-195, 2016.
Michael R. Smith, Tony Martinez, and Christophe Giraud-Carries An instance level analysis of data complexity. Machine Learning, 95(2):225-25 226, 2014.
Valentin Spitkovsky, Hiyan Alshawi, and Daniel Jurafsky. Baby Steps: How "Less is More" in unsu- pervised dependency parsing. In NeurIPS 2009 Workshop on Grammar Induction, Representation of Language and Language Learning, 2009.
Matthew Streeter and Daniel Golovin. An online algorithm for maximizing submodular functions. In Advances in Neural Information Processing Systems, 1577-1584, 2009.
James Steven Supancic III and Deva Ramanan. Self-paced learning for long-term tracking. In CVPR, pp. 2379-2386, 2013.
11

---

Under review as a conference paper at ICLR 2020
Kevin Tang, Vignesh Ramanathan, Li Fei-fei, and Daphne Koller. Shifting weights: Adapting object detectors from image to video. NewrIPS, pp. 638-646, 2012a.
Ye Tang, Yu-Bin Yang, and Yang Gao. Self-paced dictionary learning for image classification. In MM, pp. 833-836, 2012b.
William R Thompson. On the Likelihood that One Unknown Probability Exceeds Another in View of the Evidence of Two Samples. Biometrika, 25(3-4):285-299) 1933.
Mariya Toneva, Alessandro Sordoni, Remi Tachet des Combes, Adam Trischler, Yoshua Bengio, and Geoffrey J. Gordon. An empirical study of example forgetting during deep neural network learning. International Conference on Learning Representations (ICLR), 2019.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnin a novel image dataset for benchmarking machine learning algorithms, 2017.
Saining Xie, Ross Girshick, Piotr Dollár, Zhuowen Tu, and Kaiming He. Aggregated residual transformations for deep neural networks. In CVPR, 2017.
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. In BMVC, 2016.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In ICLR, 2017.
Tianyi Zhou and Jeff Bilmes. Minimax curriculum learning: Machine teaching with desirable difficulties and scheduled diversity. ICLR, 2018.
Xiaojin Zhu. Machine teaching: An inverse problem to machine learning and an approach toward optimal education. In AAAI, pp. 4087,4087, 2015.
12

---

Under review as a conference paper at ICLR 2020
A PROOFS
I: Z20 - R22 on ground set is defined over an integer lattice. The diminishing return (DR) property of the following inequality 0 I Va S y:
f(x + e,) f() 2 fly -
(9)
Where e; is one-hot vector with all zeros except for single one at the ith position. We assume f is normalized and monotone, i.e., f(0) and f(x) S f(y), 4A I x S y. W.l.o.g. we also assume the max singleton gain is bounded by 1, i.e., max; [(e) S 1. We can think that / takes input as a multi-set, and the gain of an item diminishes as its counter increases in the multi-set.
In the setting of selecting mini-batches for training machine learning models, suppose the mini-batch size is k, the training set is V. and every time step we select S. S V with [Se] k, and only observe the gains on the selected subset (e.g.. for neural networks, we update the running mean of training losses during the forward pass of the chosen mini-batch, or DIH type (A)). At every time step of selecting a mini-batch, we observe [( Vi E St. Let n = [V m E.r and for simplicity assume mod & = O. We define function g to reflect the observed gains from f as we select data samples at each training step:
9(S1.)
Σ Σ
f(1lS1.011)
(10)
For simplicity, we slightly overload the notation of S1:r for function g(-) so that we retain information about the subset selected every time step (i.e.. we can extract S, for S t S. T from Si:)). Note that is permutation-variant for k > 1, i.e., for different ordering in S 9 gives different values.
Theorem 1. For f Zi/o Rzo on ground set V with DR property, compared to any solution Si. SuT, the solution of DiHCL-Greedy, achieves
g(S1T) + Cs. 2 max (1-e-1 k
9 g(Sirr)
k 2n
Where Cy.m A m Ai g( (A1m)) such that U
A; V. and A = k.
To bridge S1.7 with Sirr we first connect S1.7 to the greedy solution with singleton gain oracle, but uses the history of sequence of S2,, ...,,,,.... ST ST 1). which we denote by S2..., ST):
S: = argmax
Σ (()SS
(11)
SCV. 9|=k iSS
Note we denote any set with subscript 0 (at time step 0) empty set, i.e. So 0. So 0, and etc.. We define the observed gain values on the singleton gain oracle with history (S .................... ST
as:
((SIT(STTT = Σ Σ (i|Siaa))
(12)
iES.
Firstly, we derive lower bound of g(S1:T) in terms of g(S ((ST
Lemma 1. g(Su.)) + Cym 2 g(Sir1//1T-1
Proof. Define Ç(i, A1:) return the subsequence of A that starts from A₁ and ends Ay where Ay is the last set in the whole sequence that contains the element i, i.e., ((i, A1a) = t' ('l When i is not present in the whole sequence A ((i, A1:) returns 0.
argmax Ane
By definitions of CJ.m and g($1mm| (1:m-1), we have C,.m 2 mf(VV 2 ( S1:mm1) due to the diminishing return (DR) property.
For T S m, Lemma is true because of the above inequality.
For T 2 + 1, we compare the previous gains of elements in S₁ to the current gains of elements in S.
13

---

Under review as a conference paper at ICLR 2020
((Srr) + Cym 2 ((SI.) + g 111m-1)
(13)
Σ
Σ
f(i Slit-1)) + g(81mm 111mmmmmm-
(14)
f=m+1: 1:7 EES
Σ
Σ
(i S1+t-)) + g (m S1mm-
(15)
t=++l:7 ies,
Σ
(( + g(S S1mm-
(16)
(=m+ 1:2 iES.
= (S:r-1))
(17)
Eq. [3dddd and Eq. 16 hold due the diminishing return property and Eq. 15 result the greedy step (i.e., S, is optimal when conditioning on ((i, S1a- D). Note that we are guaranteed to find an
element the sequence history ((Cii, S1.-1)l in Eq. and Eq. 15 since we sweep the ground set V in the first steps of solution Sim-
Remarks. In the proof, we ignore the gain the step, i.e., Eies, f(i(S1:r-1) as such gain can potentially be zero. In other words, ((S1TT-1) + Cym g($1.r(SiT-I). For the case that f is modular, i... f(z + e,) = f(x) + f(e.). and for only elements V, the function evaluations are non-zero, the bound meets in equality: 9(S1.T-)) + Cy. m = 9(S A - The idea is that we have sweep all elements in the ground before we identify the non-zero-valued elements.
Next, find lower bound of (( in terms of g(5
Lemma 2. g(Str)/Str- 2 l-e-! g(S).r)
Proof. For T' < <T, we compare ((Sirr) with g(Sur1S1TT-1)
T. g
Σ Σ f(iSSt.-1)
(18)
1=1:7 SES;
Σ tm E:T
ts x max YEs;
f(ilS
(19)
(20)
$ f(STr + SI:))
(21)
x f(SEr)+ Σ f(()))
(22)
VESi.
S f(SiT) + f((STT))
(23)
iEST
= f(SIT) + ((
11 (8
(24)
g(S1.r (1:11 (1 - g 0(S1. S1T)
(25)
From Eq. 19 to Eq. 20 we use Σ maxles; fi < E f(S Sia-1) = f(St.r)
Eq. 22 is due to DR property and Eq. 23 is result of greedy selection. Also note that for Eq. 21
Si.r + SI.T Σ es; + Σ es.
By rearranging Eq. 25 we have (( ((STT I 1( (1:T))
((ST.T( i.c., every time step, we reduce the gap to 1/k of the of optimal solution by least 4. Therefore (( 2 1- g(Si.r)
14

---

Under review as a conference paper at ICLR 2020
Remarks. We will show that there is a hard case with 1/k factor. Suppose f is set cover function ((i)A) = 0 if i A) and [V] = k2. The ground set V is partitioned into k groups V GUKU....UK with l elements in each group, such that f(a) = 1 Va E V. [(abb) and f(fa,b)) = f(a) + f(b) Va E V V ( j. For the first time step, g S1 (0) gets gain of k which is equal to g(S)). However, S1 may select one element from each of the group since we doing the ground set sweeping exploration, and all the rest gains will be zero conditioned on S1- The optimal solution, on the other hand, can select all k elements from one group at a time, and get a value of h2 in the end.
0 Va, b E Vi
Combine Lemma
1 and Lemma
2 we get the first factor I-e for the bound in Theorem
Lemma 3. g(11r)/1T- 2n (S
Proof. We will first connect (( with the solution that selects the entire ground set V at every step, i.., (VV..)) g((V, V, V....,V. V)).
k 9 (VITISSTT-) 2
0($
(26)
n
g
(Vi.r
Vi.T-V
(27)
k
(i]V
(28)
h (Vi.))
(29)
n
For Eq. 26
the fact that Sur achieve the top l gains selected by the greedy process in each step. Next, we will bound any solution g(S by
Firstly, we will need to partition Si. into two parts: (1) for the first part, we collect all the new elements introduced every time step t that do not exist in Si i.c. Si.r (Si \ 0,55 \ U(Si.)). S3 \ U(S..))..... S7. U(Si.r-))). where S; _ St \ 1( and U(S..)) & U.-1. St, which is the set union on all elements in the multiset (you can think it sets all the counters in the multiset with values 2 1 to ones), and "\" is the set minus operation. Therefore, S1.r contains every element in Si.r exactly once, i.e., every element in Si. only appears once in Si.T, and at many time steps, St might be empty; (2) the other part contains all the rest elements, i.e., Si. Si (ST \ S S5 \ Si,..., S7. \ ST). We bound the two parts as follows:
g(Si:r)
Σ
Σ
(30)
1:1: VES;
= Σ
Σ
f(ilst.
Σ
Σ
f(1lSt.))
(31)
1:T veš;
1=1: VE(S;
$ Σ f()) + Σ
Σ
(32)
1EV
1=1:T (p()))5p)
Σ [(i) + f(Si.)
(33)
LEV
S(Vi.) we use the fact Σi=1T Eies; [((SSi.-1) S EiSrr Eies; 1(i)
< SVVi.
(34)
From Eq. 31 to Eq.
32
S
Eiev f(i) since 5 contains one instance of every element in Si.r and removing the conditioning
part would make the gains larger (guaranteed by diminishing return property). To get Eq. 33 we reduce the conditioning part of fi](Si.-1) 1) in Eq. 32 by using the following inequality: for
As C. A2 C V, denote A3 A2 \ A₁ and let A f2,, MAI.. by diminishing return property of f(-), we have:
Σ f(ilA2) S A(ilAss + f(iltt)) U As) + fislltin {s)+
1EA1
... ...+s(4n \ ((AA1) f(A21As).
(35)
15

---

Under review as a conference paper at ICLR 2020
According to the pre-defined partition, pick out the first occurrence of every element into Si.7- every remaining element i E sSs \ (5)) is guaranteed to find itself in its conditioning history Si. and therefore, we may use the inequality described in Eq. [3 to bound the second term Eq. 32
by [(St.r (letting A, St \ S7 and A = Si.z- and applying the inequality from t = 1 to 7 sequentially). To make it more concrete, for example, step f = 2, by using Eq. 33 we have:
Σ
f(ds)) & f(11) + f(22 + f(s (2)
kE( (85)
+... + 111551881 S S \ (1s1)1;1))
(36)
= =1(S S5);
(37)
At time step 1 =3,, have:
Σ
f(dlST.)) f(1152 \ 5:) +
\ (3)) + f(is (2) 8;))
(E(S))55)
+ f(i 1 (5 (S3) 53 (155118) u) {3)
(38)
[(5 55 5)
(39)
Hence, we have the inequality between Eq. 32 and Eq. 33
To get Eq. 34 from Eq.
33 we use the fact Viev f(i) S 9(V1.1 V1r-i1 because g(V1:2 V1-1-1
contains Liev iEV (1i) at step 1, and the second term Eq. 34 is due to the fact that f(-)
monotone non-decreasing.
Finally, we combine Eq. 29 and Eq.
34
we get (0(S).7\Si.T--) 2 2k [(V..) (s(i)))
By combining Lemma 1 and Lemma
we get the second factor
k. for the bound in Theorem 2n
Remarks. The first factor l-e= dominates when is relatively small compared to n. Recall the lo hard case example above on the 1/K factor. We can generalize distribute the n elements into the k groups described in the hard case. Then, for n < k2, the optimal solution gets n in the end while the greedy solution gets k. so the ratio is & For n 2 k2,, the optimal solution still gets 1:2 while the greedy solution gets k. so the ratio is 1 In both scenarios, our bounds T
any k < n by (almost) equally
a.
match the hard example up constant factors.
Corollary 1. f(S1.) + 1. Jmm m 2 max
1-e-1 1-- & 2n f(Si.r)
Proof.
1
1
f(SIT) + cym
2 (g(S1:T) )= +c
(40)
k
E -1
k
max
lg(()
(41)
k
k
2n
- k
max
)((ii))
(42)
k
2n
Remarks. We will show there hard case with the 1/k² factor. The same as the hard case mentioned above for the set cover function, f($i) gets a gain since the selected items can be totally redundant, and the future gains are all zeros since S₁ select one element from each group. However, the optimal solution can still achieve an evaluation of k.2 in the end. Also, note that Theorem iss true for any solution Si. and the optimal solution for and the optimal solution for can be different.
We mentioned a few weighted sampling method to replace the greedy step. Here, we apply a random sampling procedure similar the lazier-than-lazy approach Mirzasoleiman al. (2055): we sample a subset Rg C V St.j-1 of size 2 & log 1, and then choose the top-gain element from R2 and add to St.j-1 to from St.j- We denote such sampling based greedy as DIHCI--Greedy-randon
16

---

Under review as a conference paper at ICLR 2020
Theorem 2. For f: 2 Rzu on ground set V with DR property, compared to any solution Si.r SiT, the solution of DIHCI-GGreedyy-rnddnn achieves
-
6 1
_
Big(SirT) F 2 (1
((Sir)
(43)
k:
(1-6-1 c)
1 gl g(Si:r)
(44)
Proof. We can think the selection of every St is a greedy process of k steps, with St as the optimal solution. Suppose up to step j. we select the set St.j. We first bound the probability that the sampled set has some intersection with the optimal set St.
S St.j
Pr[R, n (S, \ Sti-1) 1) +
2 (1
)(2
(45)
VV
\ St.s-1
Se St.j )18)
2 1 - (1
(46)
n
[i] (
2 1
(47)
Liik
Se
Sr,5-1
2 (1
(48)
k
(49)
In step j. we denote the selected item by viy We can then get the expected gain given the probability that there is some intersection:
( Pr[Ht n (S, \ Sed) # 0] S.
Σ
f(ils(i, S1a-1))
(50)
Smal
iES.
Σ
(51)
k
EES:
Again, we get the argument that we are reducing the gap to the optimal solution by (1 - c)/k for every selected item 2ny on expectation.
Σ
Elflegl(c,, S1a-1)) 2 (1 (1-
1- ))) Σ S(((i)((
(52)
SE
We can then apply Eq. 52 the Eq. 14 of Lemma and get
((g(S) + C,, 2 (1 - 1
(
(53)
k
Combine with Lemma 2 we get the bound in Theorem 2
Remarks. When n is large and n >> k. we can approximate the sample without replacement using sample with replacement, and can independently sample l subsets each of size [R] at every time step to generate Sg. In such a case, the bound becomes [[g(()).T)] + Cr.m 2 1-c - g((
Similarly, we can also get the expectation bound on f:
Corollary 2. B[f(Sur)] + to Cy 2 (1 - (1 - 1 f(SiT)
Proof.
E(f(S + Cy > k
(E(g(S1:)] + C)
(54)
- -1
(1 - (1
é kb
9 1TT)
(55)
k
122
1 -
bky 1 =
21 (1
1(Si.)
(56)
k
1.2
17

---

Under review as a conference paper at ICLR 2020
We can extend the setting so that get noisy feedback from the gains of function f: f(([S1=-1) +ag and the problem becomes multi-armed bandit problem. Specifically if we assume the noise de form martingale difference sequence, i.e. E[ar//on, (2,, ..,...., ar-1 1] 0 and all at, are bounded az S and if we make further assumption about the smoothness of the f and y function (assume the gains of f and y have RKHS-norm bounded by value B with some kernel k), we can utilize the contextual bandit UCB algorithm proposed in Krause & Ong 2011 to get a VT dependent regret. Also, under the noise setting, the contextual information becomes crucial, as the function has DR- property,.. and without an estimate of how much the gain decreases, we cannot have a better estimate of the upper bound on the noise term. However, we note that utilizing the contextual information involves calculating large kernel matrices, which is not feasible for our purpose of efficient curriculum learning. We include the following result for completeness.
Theorem 3. For f 2 + R20 on ground set V with DR property, suppose the gain of function has RKHS-norm bounded by value B with some kernel k), and the noise 0t 's from a martingale difference sequence: E[a, (a1, ,Q....... 04--1 = 0 and all a₁ are bounded aa σ. We define the maximum information gain if we have the perfect information about f. -P = max (YA:.)) H (YAAr f), where H is the Shannon entropy, and YArr {f(i] + acli E A,, 1 T)
denotes the collection of gain values we get from the sequence of A1:r We get the following regret bound:
1-e1 Pr(
h -9((1) S CCTTTP + G,.m + 2 1 6,
-
(57)
Where, C = log(1 + a 2), Br 22 300pT In (T/6).
Proof. The proof directly utilizes the third case of Theorem I in Krause & Ong 2011 history sequence (51, .,, St) as the context:
using the
Pr( g(Sir) (( VCTBrPT + 2 1
(58)
Combine with Lemma 1 we have:
Pr h g(Si.r) - ((Strr) S VCTBrPT + Csm + +2] 2 1 8.
(59)
B DYNAMIC INSTANCE HARDNESS (CONT.)
Figure 4: LEFT: Entry A., (i < f) is the percentage of shared samples between the top- 10k samples with the largest DIH computed in epoch 15% and epoch 15j RIGHT: Entry A < j) the percentage of shared samples between the top-10k: 10k samples with the smallest DIH computed epoch 15i and epoch 15j. It shows that both the forgettable and memorable samples in the future are predictable by using the DIH values in carly epochs.
Firstly, we present a quantitative verification of the second observation in Section 2, i.e., dy- namic instance hardness in early stages can predict later dynamics. It tries predict the samples
18

---

Under review as a conference paper at ICLR 2020
with large/small DIH values in the future by only using the DIH computed on early training history. In Figure 4 we show two upper triangle matrices quantitatively verifying the above statement. They are computed based on the results of the CIFARIO training experiment in Section 2. Take the matrix in the left plot for example, given U, the top-10k samples with the largest DIH values computed in epoch 15i, and U for any j i, the entry A., |0,n0,1/100 Similarly, the matrix in the right plot measures the same overlapping percentage for the top- samples with the smallest DIH values between epoch 15i and epoch 15j. They show that after few first epochs, DIH can accurately predict the forgettable and memorable samples in the future. This verifies the second statement we made in Section 2. In addition, they also show that [1/0000/00000 between consecutive epochs 15i and 15j is close 100%, which indicates that DIH is stable and smoothly changed metric with high consistency across training trajectory.
Epoch 10
LANGEN will LI Lanple
Mund
Epoch
Epoch 40
Epoch 40
/ bood
Epoch 60
capel wil Fit
Epoch 60
losses (mean and std.) of the three groups of samples partitioned by DIH metric (i.c..unnnngg mean of prediction-ftip) computed epoch 10,40 and 60 during training 2ideRessNel-2--10 on CIFARIO with random labels. In this setting, the random (but wrong) labels will re- membered very well after some training, and DIH in carly stages loses the capability to predict the future DIH, i.c., they can only reflect the history but not the future. This characteristic of DIH might be helpful to detect noisy data.
Figure 5: LEFT: Averaged prediction flip and RIGHT:
Epoch
Epoch
Epoch
Epoch
Figure 6: LEFT: Averaged prediction flip and RIGHT: losses (mean and std.) of the three groups of samples partitioned by a DIH metric fice.running mean of prediction-flip computed at epach 10, 40, 140 and 210 during training a smaller CNN on CIFARI0. It shows that the difference of memorable and forgettable samples is not sufficiently obvious until very late training epochs, e.g., after epoch-140.
Secondly, we conduct an empirical study of dynamic instance hardness during training a neu- ral net on very noisy data, as studied in (Zhang al. 2017) and (Arpit et al. 2017). particular, we replace the ground truth labels of the training samples by random labels, and apply the same training setting used in Section 2. Then, we compute the running mean of prediction-fiip for each sample at some epoch (i.e., 10, 40, 60), and partition the training samples into three groups, as we did to generate Figure I
The result is shown in Figure 5 It shows 1) the group with the smallest
19

---

Under review as a conference paper at ICLR 2020
prediction flip over history (left plot) is possible have large but unchanging loss shown in the right plot; and 2) the DIH in this case can only reflect the history but cannot predict the future. However, it also indicates that the capability of DIH to predict the future is potential to be an effective metric to distinguish noisy data or adversarial attack from real data. We will discuss our future work.
Thirdly, we change the WideResNet to a much smaller CNN architecture with three convolu- tional layer We apply the same training setting used in Section 2. Then, we compute the running mean of prediction-flip for each sample some epoch (i.c., 10, 40, 140, 210), and partition the training samples into three groups, as we did to generate Figure [ The result is shown in Figure Compared to DIH of training deeper and wider neural forgettable samples are indistinguishable until very late stages, e.g., Epoch- 140. This indicates that using DIH in earlier stage to select forgettable samples into curriculum might not be reliable when training small neural nets. We will leave explanation of this phenomenon to our future works.
shown in Figure [ the memorable and
@ 2.0
$ 2.5
2.0-
0.5
0.0
50
100
150
200
250
300
opoch
instantatreous
50
100
150
200
250
300
epoch
Figure 7: Top: DIH (running mean loss) vs. Bottom: instantaneous loss randomly selected samples from CIFAR10 when training WideResNet-28. 10. shows that for each individual sample, DIH smoothly decreases while the corresponding instantaneous loss is much noisier.
Moreover, we provide a comparison of the smoothness between DIH and instantaneous loss on individual samples in Figure 7 It shows that the DIH is smooth and consistent measure of the leamiin//eemorzztton progress on individual samples. In contrast, the frequently used instantaneous loss is much noisier, selecting training samples according to it will lead unstable behaviors during training. Figure we also provide comparison of DIH and instantancous loss on the two groups of samples in Figure 2 which shows similar phenomenon.
C EXPERIMENTS (CONT.)
We use cosine annealing learning rate schedule for multiple episodes. The switching epoch between each two consecutive episode for different datasets are listed below.
CIFAR1O, CIFARI00: (5, 10, 15, 10,20, 30, 40, 60, 90, 140, 210, 300);
Food-101 Birdsnap, FGVCaireraft, StanfordCars: (10, 200,20,00 30, 40, 60, 90, 150, 240, 400);
ImageNet: (5, 10, 15, 20, 30, 45, 75, 120,200);
STL10: (20, 40, 60, 80, 120, 160, 360, 560, 840, 1200);
SVHN: (5, 10. 15, 20, 30, 40, 60,90090 140, 210, 300);
KMNIST, FMNIST: (5, 10, 20, 30, 40, 60, 90, 140, 210,300);
We report how the test accuracy changes with the number of training batches for each method, and the wall-clock time for all the 11 datasets Figure 12
"hhe "v3" network from https://git http:/hhhhccccoooppppaaaaeeer/ee
com wwwppssss.eccc.....
20

---

Under review as a conference paper at ICLR 2020
remembered samples Epoch
running mean less
10 well rellmbreembred samples at Epoch 43
100
300
opoch
harder remembered samples Epoch
Instammaeeea lass
10 remembeed samples at Epoch
3
epoch
of loss) Bottom: instantaneous loss of 10 samples randomly selected from the top 10k samples with the largest(red) and the smallest(blue) DIH epoch 40 of training of WideResNet-- 28-10 CIFARIO (the same as Figure shows that for each individual sample from the two groups, DIHI smoothly decreases while the corresponding instantancous loss is much noisier.
Figure 8: Top: DIH (rumning
Table Details regarding the datasets and training settings (#Feature denotes the number of features after cropping if applied), "Ir_staae starst and "Ir target" denote the starting and target learning rate for the first episode of cosine annealing schedule, they gradually decayed over the episodes.
Dataset
CIFARIO
CIFARI00
Food-101
ImageNet
STL10
SVHN
#Training 50000
50000
75750
1281 167
5000
73257
#Test
10000
10000
25250
50000
8000
26032
#Feature
(3, (3,32,35 32)
(3,32, 32)
(3, 224, 224)
(3, 224, 224)
(3, 96, 96)
(3, 32, 32)
#Class
10
100
101
1000
10
10
#Epoch T
300
300
400
200
1200
300
BatchSize
128
128
80
256
128
128
Ir Itart
10
10
2 x 10
2 x 10
x 10
2 10
Ir lr_target
5 10-1
5 10-1
1 1 10-4
1 10-1
5 x 10
1 1 10 10-3
Table 3: Details regarding the datasets and training settings (cont.)
Dataset
Birdsnap
FGVCaircraft
StanfordCARs
KMNIST
FMNIST
#Training
47386
6667
8144
50000
50000
#Test
2443
3333
8041
10000
10000
#Feature #Class
(3, 224, 224)
(3, 224, 224) 100
(3, 224, 224)
(1, 11,28, 28)
(1,28, 28)
500
196
10
#Epoch T'
400
400
400
300
300
BatchSize
258
256
256
128
128
start
x 10
4 x 10-1
4 x 10
4 10
4 10
target
10
1 10-4
10
1 1 10
1 10
21

---

Under review as a conference paper at ICLR 2020
random
SPL
DiHCLLRand-DDiveras
SMMCL-Rand-Diverr closs
DIHCL Exp pr-iiierse, Loss
DIHCL Exp Diverse, dloss
DHHCL-Beta-Dlvee
rambe 1048
1291
Total
SubmodularMax Time
CHOc UPR pocce (81
random mini batch
M
MCL
WHHCL-Rand-Diverss Loss
DiHCL--anndDDiveree dloss
DIHCL-Exp-Diverse Loss
DilICL-Cxp-Diverr dLoss
DIHCL- BetL---ett--iiveeeeee Flip
Total Time
SubmodularMax Time
CACH 1910 SACEMAA
random mini-batch
MCL
DiHCL-Rand-
DiHCL-Rand-Divves dLoss
DIHCL-EXp Diverse, Loss
DIHCL-EXp Exp: Diverse, dLoss
Beto. Diverse,
2013
360
Submodula/Max Time
Figure 9: Training DNNs by using DIHCL (and its variants), SPL (ummar et al. 2010 MCL Zhou & Bilmes
2018). and random mini bini-batch SGD on 3 datasets, i.c., CIFARIO, CIFAR100 and STL-10 10. We use "Diverse" to denote DIHCL that further reduces S, by applying submodular maximization for Eq. 5 We report how the accuracy changes with the number training batches for each method, and the (log-scale) wall-clock time for the entire training and 2) submodular maximization part DIHCL with diversity MCL.
22

---

Under review as a conference paper at ICLR 2020
Vetts Micelesten
random mini-bathh
SPL
-an---anddddrsss Loss
DIHCL--Rndd-Diver
DIHCL-EXp Exp-ii-rree,,,,e, Loss
Exp
DIHCL Beta Diverse, Fllp
rumbe ol bramang butcties (beton sic 3281
Total Time SubmodularMax Time
cluck Docerdi
Fund Siens
060 Fund Soeme
Sea Prebwmen
Fer
Familc M8SS7 Raraaaa
mini-batch
SPL
DIMCL-Ran HaIcL--and-Divesse Loss Diverse, ExccLLEx---ivesee DIHCL Exp Diverse, Loss
DIHCL Exp Divorse,
DIHCL Beta Diverse, Filp
Furberr of thariing betenes (butchh soe 120
Total Time
SubmodularMax
Swers
random
THE acuuncy 980
SPL.
DIHCLL-Rand Ra-L-Rnd--iiiese,, Loss
MIHCL-Rand-Diverss dLoss
DIHHCL- Diverse, Loss
DIHCCL-Exp Diverse, dless
DIKCL- Diverse, Flip
namber trainng betches bandh 500 120
2006
2000
Korahe MN Set
Total Time
SubmedularMax Time
CRICK tee Laccora
Training DNNs by using DIHCL (and variants), SPL (Kmmar et al. 2010 MCL (Zhou Bilmes 2018), and random mini-batch SGD on 3 datasets, i.c., SVHN, Fashion MNIST and Kuzushiji MNIST. We use "Diverse" to denote DIHCL that further reduces S, by applying submodular maximization for Eq. (5) We report how the test accuracy changes with the number of training batches for each method, and the (log-scale) wall-clock time for 1) the entire training and 2) the submodular maximization part DIHCL with diversity and MCL.
Figure 10:
23

---

Under review as a conference paper at ICLR 2020
SPL
RanCL-Rand, Leas
DIHCL WHHCL-Rand,
DIHCL Exp, Loss
DIHCL dLoss
DIHCL Beta, Fiip
Total Time
SubmedutarMaa
6-0
SAO Aw
SPL
DIHCL-Rand, Less Rand,
DIHCL-EXp, Loss
DIHCL-Exp, dloss
DIHCL Beta, Flip
FLTTDR training buich Ibalch 00)
Feadiz
Total Time
MOL
IKODO RAB
random mini-batch SPL
MCL
DIHCL- -Rand, Loss
DIHCL-Rand, dloss
-Exp. Loss
DIHCL-Exp, dloss
DIHCL- Beta,,Bera, Flip
360
2008
Total Time SubmodularMex Time
OOOk
BIN AAS
B-
BH4 4th 001
Training DNNs by using DIHCL (and variants), SPL Kumar et al. 2010 MCL Zhou & Bilmes 2018), and random mini-batch SGD datasets, i.e., ImageNet, Food- 101 and Birdsnap. We report how the test accuracy changes with the number training batches each method, the wall-clock time for 1) entire training and 2) the submodular maximization part in MCL.
Figure 11:
24

---

Under review as a conference paper at ICLR 2020
Fest
SPI
DHHLLRand. Less
101 90
DiHCL-Rand,
DIHCL-Exp, Less
DIHCL-EEp, dloss
DiHCL-Beta, Flip
ala
Hoet Reshedtoo Ctata
Total Time
200
PLL
random
SPL
DIHCL Rand, Less
DIHCL Exp, Loss
DIHCL-Exp, cLoss
DIHCL Beta, Flip
number traiiing batther (uicc 254)
2600
Total Time
SuamodularMa
2200
Training DNNs by using DIHCL (and its variants), SPL Kumar et al. 2010 MCL Zhou & Bilmes 2018), and random mini-batch SGD on 2 datasets, i.c., FGVC Aireraft and Stanford Cars. We report how the accuracy changes with the number of training batches for each method, and the wall-clock time for 1) the entire training and the submodular maximization part MCL.
Figure 12:
25


Reviews:
[{"review_id": "ryeC-rzhYr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the curriculum learning approach that can more effectively utilize the data to train DNNs. It formulates DIH as a curriculum learning problem, and derives theory on the approximation bound. The method is verified by a set of experiments. There are  several concerns raised by the reviewer.\n\nI found the presentation of this paper is rather bad. The structure of the paper is quite strange. The Introduction section contains a lot of stuffs that I believe should be moved to the preliminary or method sections. \n\nAlso, there are a lot of confusions in the descriptions. For example, when defining the curriculum learning problem in eq.2 and eq.3, are the f's the same? If so, why do they have different input arguments?\n\n\"In step t, after the model gets trained on S_t, the feedback a_t(i) for i \\in S_t is already available\": I don't get this.\n\nI am not sure what Theorem 1 tries to tell. If one chooses k large enough, the inequality satisfies trivially. BTW, what is A_{1:T}?\n\nTo sump up, there are some interesting ideas in this paper. However, with the current stage of writing, I cannot recommend acceptance.\n\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "Syg2KlC0Fr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper presents a technique for curriculum learning using Dynamic Instance Hardness (DIH). DIH is defined as value for each training instance that characterizes how hard that instance is and is updated throughout the training process. The DIH value is used to select the best set of instances to learn. It is shown that instances with high  (low)  DIH values maintain the high (low) value throughout the training process.\n\nThe main contributions and pros of the paper are\n1. A notion of instance hardness that is persisted and updated throughout the training procedure.\n2. An objective function for characterizing instance hardness as a dynamic subset selection problem. Presenting a greedy algorithm for online maximization of this function.\n3. Experimental results that show how the property of instance hardness is maintained throughout training and showing how DIH-driven curriculum learning techniques that use random sampling outperforms non-curriculum learning techniques.\n\nCons\n1. The writing of this paper is difficult and in many of the core parts of the paper, the important definitions are not clear. E..g a) the role of the function 'f' that is being maximized in section 3.2 is not clear. To elaborate, it is not obvious what this function is or why should one care about it? \n2. The greedy algorithm has a bound in equation 7 that appears to be quite loose as the value of k is as high as the order of the size of the entire training set (in the experiments, 0.2n <= k < n). Am I misinterpreting it?\nFurthermore, the greedy algorithm -- while being focused on the core of the technical contributions -- is not used in experimental comparisons and instead all the results presented use random sampling. At least the result of DIH-greedy should be presented.\n\n3. This is more of a suggestion: one of the claimed advantages of the algorithm (over non curriculum learning and MCL) is that it requires less training examples to train. Given this, the authors should present training time improvements over large datasets.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Bkx48v0Jqr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "*Revision after author response*\n\nI thank the authors for the comments on my questions. \n\nUnfortunately, I do not feel that these comments addressed my main concerns. For all my experimental analysis questions, the authors promised some analyses for future versions, but I was hoping to see at least a minor preliminary analysis at this point, to see if indeed my concerns are valid or not. \n\nMoreover, for my question number 1 about the optimization problem, the authors referred me to Corollary 1 from the paper, but that didn't really help me because, as the other reviewers also point out, the writing is quite hard to follow.\n\nBecause of all these, I have decided to revise my score to a weak reject. While I believe the paper has merit, it requires revisions at many points in order for a reader to truly understand the method and trust the experimental results.\n\n--------------------------------------------------------------------------------------------------------------\nThe paper proposes a curriculum learning approach that relies on a new metric, the dynamic instance hardness (DIH). DIH is used to measure the difficulty of each sample while training (in an online fashion), and to decide which samples to train on next. The authors provide extensive experiments on 11 datasets as well as some theoretical motivation for the use of this approach.\n\n---- Overall opinion ----\nOverall I believe this paper is an interesting take on curriculum learning that is able to achieve good results. I believe this approach is a combination of core ideas from multiple sources, such as boosting, self-paced learning, continual learning and other curriculum learning approaches, but overall it seems different enough from each one of them individually. Because of the resemblance with these many different methods, the method itself does not surprise through the novelty of a new idea, but the authors seemed to have found something that was missing from these methods and that leads to very good results. The experimental results look great, but I believe the paper is missing some ablation studies to assess the importance of certain components (see details below). I also had some trouble understanding certain arguments, which I hope the authors can clarify. \n\n---- Major issues ----\n1. I find the arguments section 2.1 quite difficult to follow. In particular, under the assumption stated in the paper that r_t(i) = f(i|S_{1:t−1}) =  f(e_i + S_{1:t−1}) − f(S_{1:t−1}) , why does it follow that r_t(i) can be used instead of f in the minimization problem (2). \n\n2. Based on the method itself, it seems to me that the parameter k_t could would have a lot of influence on how well the method doing.  The authors mention in the experimental section what values they use, but there is no indication on how one would choose this value. Moreover, it would be good to see an analysis of how sensitive the results are to this choice.\n\n3. In Figure 1, it is not clear whether the figure on the right shows the actual loss, or the smooth loss using Equation (1) with instantaneous instance (A). If it is the former, then if the loss is so smooth, why do we need DIH? If it is the latter, then what does the instantaneous loss look like? This actually raises the question of how important the smoothing component is -- could we achieve the same results with an instantaneous loss (i.e. set gamma to 1 in Eq. 1)?\n\n---- Minor issues ----\n1. How do you choose T0, gamma and gamma_k?\n\n2. In the conclusions, the authors state that “ The reason [why  MCL and SPL are less stable] is that, compared to the methods that use DIH, both MCL and SPL deploy instantaneous instance hardness (i.e., current loss) as the score to select sample”. Since there are so many other differences in the way training progresses, I think we don’t have enough evidence to attribute this to merely the “instantaneousness” of the loss. In fact, it would be interesting to see how SPL does if you use DIH as a metric (just smoothing the loss over time), but their approach of scheduling samples (easy to hard, and not the opposite and in DIHCL).\n\n3. Appendix C shows some interesting results regarding wall time comparison. I was surprised to see that, despite the extra computations, DHCL is comparable to random mini-batches. This makes me wonder what the stop criteria was, because when you stop matters a lot for run time comparisons. It would also be interesting to see a more ample discussion on this in the main text.\n\n4. In Figure 1, the axes are barely readable.\n\n5. The authors oftentimes reverse the use of \\citet and \\citep, for example “has been called the “instance hardness” Smith et al. (2014) corresponding to” should have a bracket, whereas “Our paper is also related to (Zhang et al., 2017)” should not have brackets.\n\n6. This is not an issue, but I just wanted to say I appreciated Appendix B.\n\n---- Suggestions ----\n1. It would be interesting to make a connection between the DIH and what other papers have discovered about example forgetting (e.g. Toneva et. al, that was mentioned in the paper).\n\n2. Major issues 3 -> a study on the effect of k and how to choose it.\n\n3. While I understand that the models chosen in the experiments are expensive to train, it would be good to report standard deviations in Table 1.\n\n4. Based on Table 1 and Figure 3, there is no concrete winner among the DIHCL methods. It would be good to include some recommendations in your conclusion on which one to choose and when.\n\n---- Questions ----\n1. “On average, the dynamics on the hard samples is more consistent with the learning rate schedule, which implies that doing well on these samples can only be achieved at a shared sharp local minima.” -> can you please explain why this is so?\n\n2. See Major issues 3.\n\n3. In Table 1, on some datasets, the authors apply lazier-than-lazy-greedy, and on some not.Why, and how does one decide this for a new dataset?\n\n4. How did you choose T0, gamma and gamma_k, as well as the schedules in Appendix C (page 17)? ", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: All three reviewers, even after the rebuttal, agreed that the paper did not meet with bar for acceptance. A common complaint was lack of clarity being a major problem. Unfortunately, the paper cannot be accepted in its current form. The authors are encouraged to improve the presentation of their approach  and resubmit to a new venue.  
Decision: Reject