Is There an Online Learning Algorithm That Learns Whenever Online Learning Is Possible?

§ Problem Statement

Setup

Let $(\mathcal X,\Sigma)$ be a measurable space. An (online) binary classification protocol proceeds in rounds $t=1,2,\dots$ : an instance $X_t\in\mathcal X$ is revealed to the learner, the learner outputs a prediction $\hat Y_t\in\{0,1\}$ , and then the label $Y_t\in\{0,1\}$ is revealed. The learner may be randomized, i.e., it is specified by a sequence of measurable maps $f_t$ such that [ \hat Y_t = f_t\bigl(X_{1:t-1},Y_{1:t-1},X_t;U\bigr), ] where $U$ denotes internal randomness independent of the instance sequence $X=(X_t)_{t\ge 1}$ .

Assume realizability: there exists an unknown measurable target function $f^*:\mathcal X\to\{0,1\}$ such that $Y_t=f^*(X_t)$ for all $t$ . Define the cumulative number of mistakes through time $T$ by

M_T(f^*) := \sum_{t=1}^T \mathbf 1\{\hat Y_t \ne f^*(X_t)\}.

Fix an (arbitrary, possibly random) instance sequence $X$ . An algorithm is

weakly universally consistent under $X$ if for every measurable $f^*$ , $\mathbb E\bigl[M_T(f^*)\bigr]=o(T)$ as $T\to\infty$ (expectation over $U$ and any randomness of $X$ ), and
strongly universally consistent under $X$ if for every measurable $f^*$ , $M_T(f^*)=o(T)$ almost surely.

Say weak (respectively, strong) universal online learning is possible under $X$ if there exists at least one algorithm that is weakly (respectively, strongly) universally consistent under $X$ . Call an algorithm optimistically weakly (respectively, strongly) universal if it is weakly (respectively, strongly) universally consistent under every $X$ for which weak (respectively, strong) universal online learning is possible.

Unsolved Problem

Does there exist an optimistically universal online learning algorithm (in the weak sense, the strong sense, or both)?

Open Problem 2 (characterizing when universal online learning is possible): For a (possibly random) instance sequence $X$ and $T\in\mathbb N$ , write $X_{1:T}:=\{X_1,\dots,X_T\}$ for the set of observed instances. For any sequence of pairwise disjoint measurable sets $A_1,A_2,\dots\in\Sigma$ , define

N_T(A_{1:\infty}) := \bigl|\{i\in\mathbb N : X_{1:T}\cap A_i\ne\emptyset\}\bigr|.

Let $\mathcal C_w$ be the set of all $X$ such that for every pairwise disjoint $(A_i)_{i\ge 1}\subseteq\Sigma$ , $\mathbb E\bigl[N_T(A_{1:\infty})\bigr]=o(T)$ . Let $\mathcal C_s$ be the set of all $X$ such that for every pairwise disjoint $(A_i)_{i\ge 1}\subseteq\Sigma$ , $N_T(A_{1:\infty})=o(T)$ almost surely. Is $\mathcal C_w$ exactly the set of instance sequences $X$ under which weak universal online learning is possible? Is $\mathcal C_s$ exactly the set of instance sequences $X$ under which strong universal online learning is possible?

§ Discussion

Loading discussion…

§ Significance & Implications

The question asks whether online learnability in the realizable, universal sense (sublinear 0/1 mistakes simultaneously for all measurable targets $f^*$ ) admits a single, process-agnostic learner that succeeds whenever any learner could succeed on that same instance sequence $X$ . A positive answer would produce a canonical "no-extra-assumptions" online classifier and isolate the minimal process property that governs universal sublinear mistake rates; a negative answer would show an irreducible gap between (i) existence of some universally consistent learner tailored to a given $X$ and (ii) existence of a single strategy that automatically adapts to every learnable $X$ .

§ Known Partial Results

Hanneke (2021): formulates weak and strong universal online learning for realizable binary classification over arbitrary measurable spaces and poses the existence of an optimistically universal learner.
Hanneke (2021): proposes the criteria $\mathcal C_w$ and $\mathcal C_s$ (defined via sublinear growth in the number of disjoint measurable sets hit by $X_{1:T}$ ) as candidate characterizations of when weak/strong universal online learning is possible.

§ References

[1]

Open Problem: Is There an Online Learning Algorithm That Learns Whenever Online Learning Is Possible?

Steve Hanneke (2021)

Conference on Learning Theory (COLT), PMLR 134

📍 Open-problem note in COLT proceedings.

Link ↗

[2]

Open Problem: Is There an Online Learning Algorithm That Learns Whenever Online Learning Is Possible? (PDF)

Steve Hanneke (2021)

Conference on Learning Theory (COLT), PMLR 134

📍 Proceedings PDF.

Link ↗

§ Tags

colt-open-problem learning-theory online-learning