Statistical curriculum learning: An elimination algorithm achieving an
  oracle risk
Omer Cohen Ron Meir Nir Weinberger
We consider a statistical version of curriculum learning (CL) in a parametric
prediction setting. The learner is required to estimate a target parameter
vector, and can adaptively collect samples from either the target model, or
other source models that are similar to the target model, but less noisy. We
consider three types of learners, depending on the level of side-information
they receive. The first two, referred to as strong/weak-oracle learners,
receive high/low degrees of information about the models, and use these to
learn. The third, a fully adaptive learner, estimates the target parameter
vector without any prior information. In the single source case, we propose an
elimination learning method, whose risk matches that of a strong-oracle
learner. In the multiple source case, we advocate that the risk of the
weak-oracle learner is a realistic benchmark for the risk of adaptive learners.
We develop an adaptive multiple elimination-rounds CL algorithm, and
characterize instance-dependent conditions for its risk to match that of the
weak-oracle learner. We consider instance-dependent minimax lower bounds, and
discuss the challenges associated with defining the class of instances for the
bound. We derive two minimax lower bounds, and determine the conditions under
which the performance weak-oracle learner is minimax optimal.