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. We study the dynamics of training a 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 t (i) be a measure of instantaneous (i.e., at time t) hardness of a sample, where i is a sample index and t is a time iteration index (typically a count of mini-batches that have been processed). In previous work, a t (i) has been called the "instance hardness" (Smith et al., 2014) corresponding to 1−p w (y i |x i ), i.e., the complement of the posterior probability of label y i given input x i for the i th sample under model w. We introduce three different notions of instantaneous instance hardness in this work: (A) the loss (y i , F (x i ; w t )), where (·, ·) is the loss function and F (·; w) is the model with parameters w, (B) the loss change | (y i , F (x i ; w t )) − (y i , F (x i ; w t−1 ))| between two consecutive time steps, and (C) the prediction flip 1[ŷ t i =ŷ t−1 i ], whereŷ t i is the prediction of sample i in step t, e.g., argmax j F (x i ; w t )[j] for classification. Our (A) corresponds closely to the "instance hardness" of Smith et al. (2014) . However, our (B) and (C) require information from previous time steps. Nevertheless, we consider (A), (B) , and (C) all variations of instantaneous instance hardness since they use information from only a very local time window around training iteration t. Dynamics is achieved when we compute a running average over instantaneous instance hardness, computed recursively as follows: where γ ∈ [0, 1] is a discount factor, S t ⊆ V , and V = [n] is the set of all n training sample indices. S t is the set of sample selected for training at time t 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 t should be large early during training, but as r t (i) decreases to small values for many samples, choosing significantly smaller S t is possible to result in faster training and more accurate models. We find that r t (i) can vary dramatically between different samples since very early stage (with small t). 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 a sample's r t (i) 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 DIH value converges relatively quickly to its final relative position amongst all of the samples DIH values. For example, if a sample's DIH becomes small (i.e., meaning the sample is 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. I.e., once r t (i) for a 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 t corresponds mostly to those samples that are hard according to r t−1 (i). In other words, the model concentrates on that which it finds difficult. This is similar to strategies that improve human learning, such as the Leitner system for spaced repetition (Leitner, 1970) . This is also analogous to boosting (Schapire, 1990 ) -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., 2015; 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 a special case of DIH in Eq. (1) with γ = 1 /t+1 and t = 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 a novel curriculum learning strategy and also steps towards a better theoretical understanding of curriculum learning. Also, in Toneva et al. (2019) , a 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 t (i), which requires no additional model or inference steps and hence is computationally trivial. Another observation we find is that r t (i), for any sample, tends to monotonically decrease with t 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 r t (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 r t (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 a setting where the quality of the learnt curriculum is provably approximately good. As will be shown below, DIHCL performs optimization in a greedy manner. At each time step t, DIHCL selects a subset S t of samples using r t (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 t rather than V , which requires performing inference (e.g., a forward pass of a DNN) only on S t . This therefore leads to a speedup to the extent that |S t | |V |. The inference produces new instantaneous instance hardness a t (i) that is then used to update r t+1 (i) as in Equation 1. To encourage exploration, improve stability, and get an initial estimate of r t (i) for all i ∈ V , during the first few epochs, DIHCL sweeps through the entire training set. We provide several options for DIH-weighted subset sampling, which introduces different types of randomness in the selection since randomness 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 CIFAR10, CIFAR100, STL10, 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.
New understanding of training dynamics and metrics of memorization hardness lead to efficient and provable curriculum learning. This paper formulates DIH as a curriculum leaning problem that can more effectively utilize the data to train DNNs, and derives theory on the approximation bound.