Abstract:
We study a new variant of online learning that we call "ambiguous online learning". In this setting, the learner is allowed to produce multiple predicted labels. Such an "ambiguous prediction" is considered correct when at least one of the labels is correct, and none of the labels are "predictably wrong". We show that in this setting, the optimal mistake bound is captured by a combinatorial invariant that we call "ambiguous Littlestone dimension". Some combinatorial invariants associated with the lattice of label-sets are also relevant. We demonstrate a trichotomy of mistake bounds: up to logarithmic factors, any hypothesis class has an optimal mistake bound of either Theta(1), Theta(sqrt(N)) or N.
