A Theory of Optimistically Universal Online Learnability for General Concept Classes

This work considers the theory of universal consistency and optimistically universal learning rules in the binary classification case where, instead of considering all measurable target functions, the analysis is parameterized by a specific class $\mathcal{H}$ of binary classifiers. Two types of classes $\mathcal{H}$ are considered:

Strongly universal: for every $\mathcal{H}$-realizable process $\mathbb{X}$ there is a strongly universally consistent online learning algorithm for $\mathcal{H}$ and $\mathbb{X}$.

Optimistically universal: there is an online learning algorithm that is strongly universally consistent for $\mathcal{H}$ and $\mathbb{X}$ for every $\mathcal{H}$-realizable process $\mathbb{X}$.

The main results of this work (as far as I understand) are the following:

$\mathcal{H}$ is strongly universal if and only if it has no infinite VCL tree (Theorem 9).

$\mathcal{H}$ is optimistically universal if and only if it has no infinite Littlestone tree (Theorem 10).

Recall that $\mathcal{H}$ has no infinite Littlestone trees implies $\mathcal{H}$ has no infinite VCL tree.

Further results extends this characterization to the agnostic case.

This paper considers characterizations for optimistically universal online learnability, a notion that refers to the existence of learning rules that are simultaneously optimal for any data-generating process that satisfies some minimal assumptions, i.e. admitting an optimal process-dependent learning rule. Previous works have studied this notion of learnability when the function being learned can be any measurable function, a very broad class of functions. In this paper, the authors consider characterizations of learnability when the labels of the samples are realizable some known binary hypothesis class H, and also consider the agnostic task of achieving low regret with respect to the best hypothesis in H. They give characterizations of when H will be optimistically learnable based on VCL and Littlestone trees as well as some additional assumptions in certain cases. They provide clear examples to illustrate these characterizations.

This work continues the line of work by Hanneke and Blanchard et al universal online learning under general stochastic processes (instead of the more common iid or adversarial settings) with binary labels. While previous papers focused on the case of all measurable functions (as an implicit hypothesis spaces), this current work gives characterization for arbitrary hypothesis spaces.

The two main characterizations are as follows. Fix hypothesis space $H$.

1. For any data generating process $X$ there exists some algorithm that "learns" (i.e., average regret goes to $0$) on $X$ iff $H$ has no infinite VCL tree (a combinatorial dimension like VC used in universal learning).
2. For any data generating process $X$ there exists some algorithm that learns on $X$ and there exists a single algorithm that learns under any data process "under which learning is possible" iff it has no infinite Littlestone tree (a standard combinatorial dimension, characterizing online learning).

By the first chracterization, the existence of an infinite VCL tree just admits, thus, some data processes where learning fails, but it's unclear if learning still is possible on different specific processes. To tackle this, the authors offered an additional more fine-grained condition for each fixed (unlabeled) stochastic process $X$ (for the case the $H$ has infinite VCL trees):

1. $X$ is learnable iff a countable set of experts exist (which can depend on $X$) that satisfy a certain no-regret condition.
2. there is a single algorithm that learns "whenever learning is possible" (i.e., for any process that admits learning) iff there exists a countable set of experts (with no dependents on $X$) that satisfy the no regret condition for all processes $X$ that admit learning.

Both of these conditions collapse to a previously studied condition if $H$ is the set of all measurable functions.

We want to thank all reviewers for their helpful suggestions and comments. We will polish our paper to make it easier to read and follow.

We here clarify our results again:

First, we would like to clarify the motivation of our work. This line of work on optimistically universal learning is trying to capture the minimal assumption needed for learnability. We investigate the universal consistency problem beyond i.i.d. data-generating processes and for general concept classes.

To emphasize our novelty and contribution: We provide a full characterization of what data processes admit universal online learning under concept class H and what concept classes H have an optimistically universal learning rule. The formal statements are in Theorems 9, 10, 11, 12, and for agnostic cases: Theorems 24, 25. Those results are all new results, except the sufficiency of Theorem 10, which can be derived from Bousquet et al. (2021). The sufficiency of Theorem 9 is totally novel, though we use some techniques from Bousquet et al. (2021) and Alon et al. (2021). The necessity of Theorem 10 is also (subtly) different from the necessity part of Theorem 3.1 in Bousquet et al (2021), since our data process must be fixed in advance (rather than adaptively constructed by an adversary) and we need to show not only that the number of mistakes is infinite but that it does not grow sublinearly.

This work studies online learning under general stochastic processes (instead of the more common iid or adversarial settings) with binary labels continuing the line of work by Hanneke [2021]. While previous papers focused on the case of all measurable functions, this current work gives characterization for arbitrary hypothesis spaces. At a technical level the problem is a natural generalization of well-studied settings and the results are a significant progress. At the same time it is rather theoretical even by the standards of ML theory. In addition, the presentation is terse and hard to read even for experts on online learning. Still I think that the strengths of the results compensate for the limitations and recommend acceptance