BIU Learning Club, November 25 – Statistical curriculum learning — An elimination algorithm achieving the weak oracle risk

Curriculum Learning (CL) is a successful machine learning strategy that improves a learner’s performance by ordering the tasks according to difficulty, similarly to the way humans learn.  However, it still lacks a clear theoretical foundation.

In this work, we address statistical aspects of CL, and consider a multi-task problem with a target task and T source tasks. We focus on mean estimation problem of samples from multi-dimensional Gaussians. Sampling from the source tasks is then beneficial to the learner in case a source task is less noisy than the target task, while their corresponding parameters are very close. The learner may use up to N samples in total from all the tasks and can adaptively choose the model to sample from. Thus, in principle, it can identify the optimal source model from the samples observed so far.

We define a strong oracle as one that collects all N samples from the best model to sample from. We show that achieving the strong oracle’s performance is too ambitious for a learning algorithm. We define a weak oracle and develop an elimination-based learning algorithm. We determine conditions under which the performance of the weak oracle is matched by the algorithm.

We consider the optimality of the algorithm by deriving instance-dependent minimax lower bounds.  We discuss the challenges associated with defining the set of instances for the bound. We derive lower bounds for low and high dimensions and determine the conditions under which the performance weak oracle is provably optimal.

Joint work with Omer Cohen and Ron Meir.