Research map / Bandits and online learning / Online convex optimization and games
Tradeoffs between Mistakes and ERM Oracle Calls in Online and Transductive Online Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies online and transductive online learning where the learner accesses the concept class only through ERM or weak consistency oracles, proving exponential mistake lower bounds for general ERM and polynomial-oracle-call upper bounds in the transductive setting.
Problem
How many mistakes and oracle calls are needed for online and transductive online learning when the learner can access the concept class only via ERM or weak consistency oracles, rather than full knowledge of the class?
Approach
Replaces full concept-class access with oracle access: proves Omega(2^{d_LD}) mistake and Omega(sqrt(T 2^{d_LD})) regret lower bounds for general ERM in online learning, and shows that in transductive online learning, enumerating all labelings on the known instances with O(T^{d_VC+1}) weak consistency calls recovers optimal mistake bounds, with randomized algorithms improving special classes.
Key results
- Lower bound of Omega(2^{d_LD}) expected mistakes in the realizable online setting for any algorithm making finite agnostic-ERM queries.
- Lower bound of Omega(sqrt(T 2^{d_LD})) expected regret in the agnostic online setting with ERM oracle.
- Transductive learning with O(T^{d_VC+1}) weak consistency calls attains the optimal mistake bound for Littlestone classes; randomized ERM algorithm for thresholds achieves O(log T) mistakes with O(log T) expected ERM calls.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use general ERM access rather than full knowledge of the concept class | Online learning for Littlestone classes · Online, realizable | mistakes: $d_\mathrm{LD}$ to $\Omega(2^{d_\mathrm{LD}})$ | Hurt |
| Simulate restricted ERM using weak consistency | Deterministic online learning · Online, realizable | oracle calls: at most $g(T)$ to at most $T \cdot g(T)$ | Hurt |
| Use weak consistency queries to recover all labelings in advance | Transductive online learning · Transductive online, realizable and agnostic | mistakes/regret: $O(T^{d_\mathrm{VC}+1})$ weak consistency queries; optimal mistake bounds and optimal regret | Helped |
| Restrict the learner to $O(T)$ weak consistency queries | Transductive online learning · Transductive online, realizable | mistakes: $T/20$ queries; at least $T/20$ mistakes | Hurt |
| Restrict the learner to fewer than $T/2$ ERM queries | Transductive online learning for Littlestone classes · Transductive online, realizable | mistakes: fewer than $T/2$ queries; at least $2^{d_\mathrm{LD}}-1$ mistakes | Hurt |
| Randomize ERM querying instead of using deterministic ERM querying | Threshold learning · Thresholds, transductive online, realizable | oracle calls: $O(T)$ to $O(\log T)$ | Helped |
| Use randomized weak consistency querying instead of deterministic weak consistency querying | Threshold learning · Thresholds, transductive online, realizable | oracle calls: $O(T\log T)$ to $O(T)$ | Helped |
| Use randomized weak consistency queries for interval endpoint identification | $k$-Intervals transductive learning · $k$-Intervals, transductive online, realizable | mistakes: $O(k \log T)$ | Helped |
| Use one ERM query for $d$-Hamming Balls | $d$-Hamming Balls transductive learning · $d$-Hamming Balls, transductive online, realizable | mistakes: single ERM query: $2d$ mistakes; $2^{d+1}$ queries: $d$ mistakes | Hurt |
Surprising findings
- Restricting to Omega(T) weak consistency queries makes transductive online learning impossible for some classes, even though it is possible with more queries.
- Online learning of partial concepts with Littlestone dimension 1 requires Omega(T) mistakes even with ERM oracle access.
Limitations
- Exponential mistake dependence on Littlestone dimension remains for online learning with general ERM.
- Transductive general upper bound uses deterministic algorithms with polynomially many calls only for T^{d_VC+1}; gap to optimal randomized algorithms remains open.
- Results for k-Intervals and thresholds are specific to those families.
Experimental setup
Metrics: mistakes regret oracle calls
Baselines: Standard Optimal Algorithm Halving algorithm restricted ERM algorithms (Assos et al.; Kozachinskiy and Steifer)
Builds on: Standard Optimal Algorithm Halving algorithm restricted ERM oracle (Assos et al.) weak consistency oracle (Daskalakis and Golowich)
Closest papers by meaning
- Regret–Oracle Complexity Tradeoffs in Agnostic Online Learning (NeurIPS 2026 · similarity 0.89)
- Optimal Mistake Bounds for Transductive Online Learning (NeurIPS 2025 · similarity 0.89)
- From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model (NeurIPS 2026 · similarity 0.85)
- Online Learning with Unknown Constraints (ICML 2025 · similarity 0.85)
- Online Set Learning from Precision and Recall Feedback (NeurIPS 2026 · similarity 0.84)
- Multiclass Transductive Online Learning (NeurIPS 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.