Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
Optimal Mistake Bounds for Transductive Online Learning
Authors: Zachary Chase, Steve Hanneke, Shay Moran, Jonathan Shafer
NeurIPS 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We resolve a 30-year-old open problem concerning the power of unlabeled data in online learning by tightly quantifying the gap between transductive and standard online learning. In the standard setting, the optimal mistake bound is characterized by the Littlestone dimension d of the concept class H (Littlestone, 1987). We prove that in the transductive setting, the mistake bound is at least Ω d . Our main result (Theorem 1.1) states that the optimal number of mistakes in the transductive setting (with access to unlabeled data) is at most quadratically smaller than in the standard setting. Furthermore, there are hypothesis classes for which a quadratic gap is achieved. Full formal statements of the results, as well as detailed rigorous proofs, appear in Sections B to D. |
| Researcher Affiliation | Collaboration | Zachary Chase Kent State University EMAIL Steve Hanneke Purdue University EMAIL Shay Moran Departments of Mathematics, Computer Science, and Data and Decision Sciences Technion Israel Institute of Technology; Google Research EMAIL Jonathan Shafer MIT EMAIL |
| Pseudocode | Yes | Algorithm 1: The strategy for the adversary that achieves the lower bound in Theorem B.1. ... Algorithm 2: A subroutine of Algorithm 1 for selecting the sequence x. ... Algorithm 7: This is the well-known halving algorithm. The experts in Algorithms 6a and 6c simulate this algorithm once their version space becomes small enough. |
| Open Source Code | No | Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [NA] Justification: The paper does not include experiments requiring code. |
| Open Datasets | No | Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [NA] Justification: The paper does not include experiments requiring code. |
| Dataset Splits | No | The paper does not include experiments. |
| Hardware Specification | No | Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments? Answer: [NA] Justification: The paper does not include experiments. |
| Software Dependencies | No | The paper does not include experiments. |
| Experiment Setup | No | The paper does not include experiments. |