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..
Littlestone Classes are Privately Online Learnable
Authors: Noah Golowich, Roi Livni
NeurIPS 2021 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We provide the first non-trivial regret bound for the realizable setting. Specifically, we show that if the class H has constant Littlestone dimension then, given an oblivious sequence of labelled examples, there is a private learner that makes in expectation at most O(logT) mistakes comparable to the optimal mistake bound in the non-private case, up to a logarithmic factor. Moreover, for general values of the Littlestone dimension d, the same mistake bound holds but with a doubly-exponential in d factor. A recent line of work has demonstrated a strong connection between classes that are online learnable and those that are differentially-private learnable. Our results strengthen this connection and show that an online learning algorithm can in fact be directly privatized (in the realizable setting). |
| Researcher Affiliation | Academia | Noah Golowich MIT CSAIl EMAIL Roi Livni Tel Aviv University EMAIL |
| Pseudocode | Yes | Algorithm 1 DP-SOA. Algorithm 2 Hist Sparse. |
| Open Source Code | No | The paper states "(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)? [N/A]", indicating no code is provided. |
| Open Datasets | No | This is a theoretical paper that does not perform empirical studies with datasets. The 'If you ran experiments...' section indicates N/A for data and splits. |
| Dataset Splits | No | This is a theoretical paper that does not perform empirical studies with datasets. The 'If you ran experiments...' section indicates N/A for data and splits. |
| Hardware Specification | No | This is a theoretical paper that does not perform empirical experiments. The 'If you ran experiments...' section states N/A for 'total amount of compute and the type of resources used'. |
| Software Dependencies | No | This is a theoretical paper that does not perform empirical experiments requiring specific software dependencies with version numbers. |
| Experiment Setup | No | This is a theoretical paper that does not perform empirical experiments. The 'If you ran experiments...' section states N/A for 'training details'. |