mlsanityData to 7 Oct 2026

An Equivalence Between Private Classification and Online Prediction

arXiv 2003.00563 ↗First posted 1 Mar 2020cs.LG cs.CR stat.MLcited by 63

Not on the map. Why?

Abstract (arXiv)

We prove that every concept class with finite Littlestone dimension can be learned by an (approximate) differentially-private algorithm. This answers an open question of Alon et al. (STOC 2019) who proved the converse statement (this question was also asked by Neel et al.~(FOCS 2019)). Together these two results yield an equivalence between online learnability and private PAC learnability. We introduce a new notion of algorithmic stability called "global stability" which is essential to our proof and may be of independent interest. We also discuss an application of our results to boosting the privacy and accuracy parameters of differentially-private learners.

Key facts. Cited by 63 papers in the map (data through 7 Oct 2026). First posted on arXiv 1 Mar 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 14; 2022: 8; 2023: 13; 2024: 11; 2025: 11; 2026: 6.

63 papers.

Sort:

By area:

  1. 2021A Theory of PAC Learnability of Partial Concept Classescited by 59
  2. 2021Smoothed Analysis with Adaptive Adversariescited by 57
  3. 2022Reproducibility in Learningcited by 44
  4. 2023Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalizationcited by 42
  5. 2023A survey on the complexity of learning quantum statescited by 31
  6. 2023Optimal Learners for Realizable Regression: PAC Learning and Online Learningcited by 23
  7. 2025A Theory of Learning with Autoregressive Chain of Thoughtcited by 20
  8. 2021Understanding the Eluder Dimensioncited by 19
  9. 2022How unfair is private learning ?cited by 18
  10. 2021Majorizing Measures, Sequential Complexities, and Online Learningcited by 17
  11. 2023Statistical Indistinguishability of Learning Algorithmscited by 17
  12. 2021Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Gamescited by 16
38 more
  1. 2023Information Theoretic Lower Bounds for Information Theoretic Upper Boundscited by 16
  2. 2023Local Borsuk-Ulam, Stability, and Replicabilitycited by 14
  3. 2023List and Certificate Complexities in Replicable Learningcited by 13
  4. 2023The Bayesian Stability Zoocited by 13
  5. 2024Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnabilitycited by 11
  6. 2021Private learning implies quantum stabilitycited by 10
  7. 2021Littlestone Classes are Privately Online Learnablecited by 10
  8. 2021User-Level Private Learning via Correlated Samplingcited by 9
  9. 2025Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Backcited by 9
  10. 2021On the Hardness of PAC-learning Stabilizer States with Noisecited by 8
  11. 2022Comparative Learning: A Sample Complexity Theory for Two Hypothesis Classescited by 8
  12. 2023Replicability and stability in learningcited by 8
  13. 2024Neural Collapse Meets Differential Privacy: Curious Behaviors of NoisyGD with Near-perfect Representation Learningcited by 8
  14. 2024Multiclass Transductive Online Learningcited by 8
  15. 2022Finite Littlestone Dimension Implies Finite Information Complexitycited by 7
  16. 2024On the Computational Landscape of Replicable Learningcited by 7
  17. 2022Differential Privacy Amplification in Quantum and Quantum-inspired Algorithmscited by 6
  18. 2023Optimal Unbiased Randomizers for Regression with Label Differential Privacycited by 6
  19. 2024Ramsey Theorems for Trees and a General 'Private Learning Implies Online Learning' Theoremcited by 6
  20. 2023A Unified Characterization of Private Learnability via Graph Theorycited by 5
  21. 2023A unifying framework for differentially private quantum algorithmscited by 5
  22. 2023Mixtures of Gaussians are Privately Learnable with a Polynomial Number of Samplescited by 5
  23. 2024Oracle-Efficient Differentially Private Learning with Public Datacited by 5
  24. 2024The Limits of Differential Privacy in Online Learningcited by 5
  25. 2021Multiclass versus Binary Differentially Private PAC Learningcited by 4
  26. 2022The unstable formula theorem revisited via algorithmscited by 4
  27. 2025Stability and List-Replicability for Agnostic Learnerscited by 4
  28. 2025Spherical dimensioncited by 4
  29. 2021Differentially Private Nonparametric Regression Under a Growth Conditioncited by 3
  30. 2024Not All Learnable Distribution Classes are Privately Learnablecited by 3
  31. 2024Credit Attribution and Stable Compressioncited by 3
  32. 2025Borsuk-Ulam and Replicable Learning of Large-Margin Halfspacescited by 3
  33. 2025Private Learning of Littlestone Classes, Revisitedcited by 3
  34. 2021On the Sample Complexity of Privately Learning Axis-Aligned Rectanglescited by 2
  35. 2024Agnostic Private Density Estimation for GMMs via List Global Stabilitycited by 2
  36. 2025An tildeOptimal Differentially Private Learner for Concept Classes with VC Dimension 1cited by 2
  37. 2025Private List Learnability vs. Online List Learnabilitycited by 2
  38. 2025Simplicial covering dimension of extremal concept classescited by 2

50 most cited of 63 All 63 (JSON)