[edit]
Exponential Weights Algorithms for Selective Learning
Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:3833-3858, 2021.
Abstract
We study the selective learning problem introduced by Qiao and Valiant (2019), in which the learner observes n labeled data points one at a time. At a time of its choosing, the learner selects a window length w and a model ˆℓ from the model class L, and then labels the next w data points using ˆℓ. The \emph{excess risk} incurred by the learner is defined as the difference between the average loss of ˆℓ over those w data points and the smallest possible average loss among all models in L over those w data points. We give an improved algorithm, termed the \emph{hybrid exponential weights} algorithm, that achieves an expected excess risk of O((loglog|L|+loglogn)/logn). This result gives a doubly exponential improvement in the dependence on |L| over the best known bound of O(√|L|/logn). We complement the positive result with an almost matching lower bound, which suggests the worst-case optimality of the algorithm. We also study a more restrictive family of learning algorithms that are \emph{bounded-recall} in the sense that when a prediction window of length w is chosen, the learner’s decision only depends on the most recent w data points. We analyze an exponential weights variant of the ERM algorithm in Qiao and Valiant (2019). This new algorithm achieves an expected excess risk of O(√log|L|/logn), which is shown to be nearly optimal among all bounded-recall learners. Our analysis builds on a generalized version of the selective mean prediction problem in Drucker (2013); Qiao and Valiant (2019), which may be of independent interest.