  Curriculum Learning - the idea of teaching by gradually exposing the learner
to examples in a meaningful order, from easy to hard, has been investigated in
the context of machine learning long ago. Although methods based on this
concept have been empirically shown to improve performance of several learning
algorithms, no theoretical analysis has been provided even for simple cases. To
address this shortfall, we start by formulating an ideal definition of
difficulty score - the loss of the optimal hypothesis at a given datapoint. We
analyze the possible contribution of curriculum learning based on this score in
two convex problems - linear regression, and binary classification by hinge
loss minimization. We show that in both cases, the expected convergence rate
decreases monotonically with the ideal difficulty score, in accordance with
earlier empirical results. We also prove that when the ideal difficulty score
is fixed, the convergence rate is monotonically increasing with respect to the
loss of the current hypothesis at each point. We discuss how these results
bring to term two apparently contradicting heuristics: curriculum learning on
the one hand, and hard data mining on the other.
