Abstract
We consider online learning in the model where a learning algorithm can access the class only via the consistent oracle—an oracle that, at any moment, can give a function from the class that agrees with all examples seen so far. This model, recently introduced by Assos et al. (2023), is motivated by the computational intractability of standard methods like the Standard Optimal Algorithm (SOA), which requires computing the Littlestone dimension of subclasses. While previous work established a mistake bound of $C^d$ for an unspecified constant $C$, we present a novel, significantly simpler algorithm that achieves a mistake bound of $O(256^d)$. Our approach utilizes basic properties of the Littlestone dimension and introduces the concept of $\gamma$-advanced sets. Additionally, we establish a lower bound of $3^d$ mistakes for any algorithm in this model and demonstrate that every class of finite Littlestone dimension with a recursively enumerable representation admits a computable online learner.
Introduction
In the classical framework of online learning, a learner is presented with a sequence of unlabeled instances and must predict their labels. After each prediction, the true label is revealed, and the learner updates its hypothesis. The fundamental measure of complexity in this setting is the Littlestone dimension ($d$). A hypothesis class $H$ is learnable in the online setting if and only if its Littlestone dimension is finite.
The Standard Optimal Algorithm (SOA) is known to achieve a mistake bound exactly equal to $d$. However, the SOA is often computationally impractical. At each step, it requires calculating the Littlestone dimension of various subclasses of $H$ to determine which label prediction minimizes the potential for future mistakes. This calculation is known to be NP-hard for many simple classes and can even be uncomputable.
The Consistent Oracle Model
To address the gap between the theoretical optimality of the SOA and its computational reality, researchers have turned to the consistent oracle model. In this model, the learner does not need to perform complex combinatorial calculations. Instead, it has access to an oracle that, given a history of labeled examples, returns any hypothesis from the class $H$ that is consistent with those examples.
This model is highly motivated by practice, as the oracle essentially performs Empirical Risk Minimization (ERM), a standard task in machine learning. The central question is: what is the "price of simplicity"? If we restrict ourselves to using a consistent oracle, how many more mistakes must we tolerate compared to the $d$ mistakes of the SOA?
A Simpler Recursive Algorithm
Previous work by Assos et al. (2023) proved that the mistake bound in the consistent oracle model is at most $C^d$ for some constant $C$. However, their proof was highly complex and the constant $C$ was estimated to be extremely large (approximately $e^{2 \cdot 10^5}$).
This paper introduces a much simpler algorithm based on a recursive structure and unweighted majority voting. The algorithm is improper, meaning its final prediction is not necessarily a single hypothesis from $H$, but rather a combination of hypotheses.
Key Components:
- Recursive Structure (
CreateAdv): The algorithm for a class of dimension $d$ is built by making calls to sub-routines designed for classes of lower dimensions. - Majority Voting (
VoteAndUpdate): The learner maintains a set of "active" functions provided by the consistent oracle. For each new instance, it predicts based on the majority vote of these functions. - The $\gamma$-advanced Property: To prove the mistake bound, the authors introduce the "$\gamma$-advanced" property. This combinatorial tool allows for an inductive proof showing that every time the algorithm makes a mistake, the set of functions it has collected becomes increasingly "complex" in a way that eventually violates the Littlestone dimension $d$, forcing the sequence of mistakes to end.
Theoretical Results
The primary contribution of this work is the drastic improvement of the upper bound and the establishment of a new lower bound.
Upper Bound: $O(256^d)$
By utilizing the $\gamma$-advanced property and a streamlined recursive analysis, the authors show that the algorithm makes at most $O(256^d)$ mistakes. While still exponential in $d$, this constant is significantly more manageable than previous estimates and the proof is accessible using only basic properties of the Littlestone dimension.
Lower Bound: $3^d$
The paper also provides a new lower bound, proving that no algorithm using only a consistent oracle can make fewer than $3^d - 2$ mistakes in the worst case. This is a significant result because it demonstrates that the consistent oracle model is fundamentally more difficult than the standard model. In the standard model, the lower bound is $d$; here, it is exponential.
Computability
The algorithm also resolves an open problem posed by Hasrati and Ben-David (2023). It proves that for any hypothesis class with a finite Littlestone dimension and a recursively enumerable representation, there exists a computable online learner. This bridges a gap in the understanding of which classes are effectively learnable.
Discussion and Future Work
While this work simplifies the landscape of online learning with consistent oracles, several questions remain. The gap between the lower bound ($3^d$) and the upper bound ($256^d$) is still large. Determining the optimal constant $C$ remains a challenging open problem.
Furthermore, the current algorithm is improper. While randomized techniques exist to convert improper learners into proper ones, it is not yet clear if a deterministic proper learner can achieve similar bounds using only a consistent oracle. Finally, while the algorithm is "efficient" in terms of the number of oracle calls, the exponential dependence on $d$ suggests that further refinements are needed for high-dimensional practical applications.
Summary updated