Tradeoffs between Mistakes and ERM Oracle Calls in Online and Transductive Online Learning

Abstract

This paper explores the fundamental limits of online learning when the learner lacks upfront knowledge of the concept class and must interact with it through oracles like Empirical Risk Minimization (ERM). While standard online learning suffers an exponential explosion in mistakes under these conditions, the authors demonstrate that transductive learning—where unlabeled data points are seen in advance—enables efficient learning with only a polynomial number of oracle calls.

Introduction and Problem Statement

In classical online learning, a learner predicts labels for a sequence of data points sequentially. The performance benchmark is the Littlestone dimension ($d_{LD}$), representing the maximum mistakes a perfect learner will make. However, achieving this typically requires full knowledge of the concept class, which is often computationally intractable.

To address this, researchers use oracles as an interface:

• ERM Oracle: A black box that returns a hypothesis fitting a provided labeled dataset.
• Weak Consistency Oracle: A simpler interface that confirms if a specific labeling is consistent with the concept class.

This paper investigates the "oracle tax": the cost in mistakes and query complexity when relying on these black-box interfaces rather than full structural knowledge.

Methodology and Algorithmic Approach

The authors analyze two primary settings:

1. Standard Online Learning: Instances are revealed one by one.
2. Transductive Online Learning: The learner observes all $T$ unlabeled instances at the start, though labels are revealed sequentially.

They employ probabilistic lower bounds to establish fundamental limits and algorithmic constructions to demonstrate achievability. For the transductive setting, they introduce a preprocessing strategy that uses the weak consistency oracle to "map out" the concept class's potential behaviors on the known instances before the prediction game begins.

Concept Classes and Benchmarks

As a theoretical study, this work evaluates performance on canonical mathematical concept classes that serve as complexity benchmarks:

• Thresholds: Points on a line where labels transition from 0 to 1 at a specific point.
• $k$-Intervals: Concepts defined by $k$ distinct active segments on a line.
• $d$-Hamming Balls: Concepts defined by similarity to a central prototype point.

Key Insights and Results

The Cost of Restricted Access

The research reveals that the "Oracle Tax" is exceptionally high in standard online learning. If a learner only has oracle access, the mistake bound jumps from $d_{LD}$ to at least $2^{d_{LD}}$. This exponential gap proves that structural knowledge of the concept class is vastly more powerful than simple query access.

Expand

Source, p. 3

As shown in Figure 1, the lower bounds for mistakes in both realizable and agnostic online settings are exponential in the Littlestone dimension, highlighting the difficulty of learning without prior structural knowledge.

The Transductive Advantage

Transduction acts as a game-changer. By seeing the unlabeled points first, the learner can use the oracle to discover the class's behavior on those specific points. This allows the learner to bypass exponential mistake bounds and achieve optimal performance with a polynomial number of oracle calls ($O(T^{d_{VC}+1})$).

Expand

Source, p. 4

Figure 2 details how specific classes benefit from transduction and randomization. For instance, in the Thresholds class, randomized algorithms can achieve the same mistake bounds as deterministic ones but with exponentially fewer oracle calls ($O(\log T)$ instead of $O(T)$).

Conclusion and Future Work

The authors establish that while black-box oracles impose a heavy burden in standard online learning, transductive information can restore efficiency. However, several gaps remain for future exploration:

1. Query Efficiency: The current general transductive upper bound ($T^{d_{VC}+1}$) remains high; a tighter bound may be possible.
2. Randomization Power: It remains an open question whether randomized algorithms are provably superior to deterministic ones across all oracle-based tasks.
3. Generalization: Extending these oracle tradeoffs to multiclass classification and regression is a logical next step.

@inproceedings{attias2025tradeoffs,
  author = {Idan Attias and Steve Hanneke and Arvind Ramaswami},
  title = {{Tradeoffs between Mistakes and ERM Oracle Calls in Online and Transductive Online Learning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2025},
  url = {https://openreview.net/forum?id=u2GzxdWLFW},
}