Littlestone Classes are Privately Online Learnable
Authors: Noah Golowich, Roi Livni
NeurIPS 2021 | Conference PDF | Archive PDF | Plain Text | 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 nzg@mit.edu Roi Livni Tel Aviv University rlivni@tauex.tau.ac.il |
| 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'. |