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 an 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, 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.
*Revision after author response*
I thank the authors for the comments on my questions. 
Unfortunately, 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. 
Moreover, 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.
Because 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.
--------------------------------------------------------------------------------------------------------------
The 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.
---- Overall opinion ----
Overall 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. 
---- Major issues ----
1. 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). 
2. 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.
3. 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)?
---- Minor issues ----
1. How do you choose T0, gamma and gamma_k?
2. 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).
3. 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.
4. In Figure 1, the axes are barely readable.
5. 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.
6. This is not an issue, but I just wanted to say I appreciated Appendix B.
---- Suggestions ----
1. 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).
2. Major issues 3 -> a study on the effect of k and how to choose it.
3. 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.
4. 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.
---- Questions ----
1. “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?
2. See Major issues 3.
3. 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?
4. How did you choose T0, gamma and gamma_k, as well as the schedules in Appendix C (page 17)?