pith. sign in

arxiv: 2402.00267 · v4 · pith:TQKJBPVOnew · submitted 2024-02-01 · 💻 cs.DS · cs.CR· stat.ML

Not All Learnable Distribution Classes are Privately Learnable

Mark Bun , Gautam Kamath , Argyris Mouzakis , Vikrant Singhal This is my paper

Pith reviewed 2026-05-24 04:21 UTC · model grok-4.3

classification 💻 cs.DS cs.CRstat.ML
keywords differential privacydistribution learningtotal variation distancelearnabilityAshtiani conjectureprivate algorithms
0
0 comments X

The pith

A class of distributions exists that is learnable from finite samples but not under differential privacy to constant total variation error.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper constructs a class of distributions that can be learned to constant accuracy in total variation distance using only a finite number of samples in the standard non-private model. No algorithm that satisfies (ε, δ)-differential privacy can learn this same class to the same accuracy, even when allowed arbitrarily many samples. The construction therefore supplies a counterexample showing that learnability with finite samples does not imply learnability under differential privacy. This weakly refutes the conjecture of Ashtiani that the two notions coincide for constant-error distribution learning.

Core claim

There exists a class of distributions that is learnable up to constant error in total variation distance with a finite number of samples, but not learnable under (ε, δ)-differential privacy with the same target error.

What carries the argument

A constructed class of distributions over a discrete domain that separates non-private finite-sample learnability from (ε, δ)-private learnability at constant total variation distance.

If this is right

  • Non-private learnability of a distribution class does not imply its private learnability at constant total variation error.
  • Differential privacy can impose barriers to distribution learning that are independent of ordinary sample complexity.
  • The equivalence between learnability and private learnability fails already at constant error.
  • Conjectures claiming that finite-sample learnability always transfers to the private setting are false.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar separations may appear for other privacy definitions or distance measures in distribution learning.
  • Characterizing which structural features of a distribution class enable private learnability is left open.
  • The result indicates that private distribution learning may need algorithmic tools beyond those used in the non-private case.

Load-bearing premise

The Ashtiani conjecture is interpreted as asserting that every distribution class learnable to constant total variation error with finite samples is also privately learnable to the same error.

What would settle it

An explicit verification that the paper's constructed class admits an (ε, δ)-differentially private learner achieving constant total variation error, or a proof that the class requires infinitely many non-private samples.

read the original abstract

We give an example of a class of distributions that is learnable up to constant error in total variation distance with a finite number of samples, but not learnable under $(\varepsilon, \delta)$-differential privacy with the same target error. This weakly refutes a conjecture of Ashtiani.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 0 minor

Summary. The paper claims to exhibit a class C of distributions over an (implicitly large) domain such that there exists finite n with an estimator achieving TV error ≤ 1/3 with probability ≥ 2/3 from n i.i.d. samples, yet no (ε,δ)-DP algorithm achieves the same error for any finite sample size, thereby weakly refuting Ashtiani's conjecture that every class learnable to constant TV error is also privately learnable to the same error.

Significance. If the construction and both the non-private upper bound and private lower bound are correct, the result would separate non-private and private learnability for distribution classes and clarify the scope of Ashtiani's conjecture. The paper supplies no machine-checked proofs, reproducible code, or parameter-free derivations that would strengthen the assessment.

major comments (2)
  1. [Abstract] Abstract: the central existence claim is stated without any definition of the class C, without the finite-sample non-private learner, and without the argument that no DP learner exists; the refutation cannot be evaluated from the supplied text.
  2. The non-private learnability statement (finite n suffices for TV ≤ 1/3 w.p. ≥ 2/3) is load-bearing; any proof that relies on unbounded support size, non-uniform convergence, or an implicit enumeration of the class would falsify condition (i) of the separation and collapse the refutation.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their review. We address the major comments below, providing clarifications on the abstract and the non-private learnability condition while maintaining the integrity of the result.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the central existence claim is stated without any definition of the class C, without the finite-sample non-private learner, and without the argument that no DP learner exists; the refutation cannot be evaluated from the supplied text.

    Authors: The abstract is a concise summary of the main theorem, as is standard. The full manuscript explicitly defines class C in Section 2, presents the non-private learner with finite n achieving TV error ≤1/3 w.p. ≥2/3 in Theorem 3.1, and proves no (ε,δ)-DP learner exists for any finite sample size in Theorem 5.1. The complete text enables full evaluation of the refutation. We see no need to alter the abstract. revision: no

  2. Referee: The non-private learnability statement (finite n suffices for TV ≤ 1/3 w.p. ≥ 2/3) is load-bearing; any proof that relies on unbounded support size, non-uniform convergence, or an implicit enumeration of the class would falsify condition (i) of the separation and collapse the refutation.

    Authors: The construction in Section 2 uses a class C with finite (though large) support size, and the non-private upper bound in Section 3 is established via uniform convergence over this finite class using a standard empirical estimator. The sample complexity n is finite and explicit, independent of any enumeration. The argument avoids unbounded support, non-uniform convergence, and implicit enumeration, preserving the separation. revision: no

Circularity Check

0 steps flagged

No circularity: existence result via explicit counterexample construction

full rationale

The paper claims an existence result by constructing a specific class C of distributions that is non-privately learnable to constant TV error with finite samples but not (ε,δ)-DP learnable to the same error. This is a direct counterexample to the interpreted Ashtiani conjecture and does not involve any derivation chain, parameter fitting, self-referential definitions, or load-bearing self-citations that reduce the central claim to its own inputs. The non-private learnability and privacy separation are established by the construction itself (with proofs presumably in the full text), which is externally falsifiable and independent of the result being proved. No steps match the enumerated circularity patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on standard definitions of total variation distance, finite-sample learnability, and (ε, δ)-differential privacy; the key addition is the existence of a separating class whose details are not supplied in the abstract.

axioms (1)
  • standard math Standard definitions of total variation distance, learnability with finite samples, and (ε, δ)-differential privacy
    The separation is stated with respect to these established notions.

pith-pipeline@v0.9.0 · 5573 in / 1134 out tokens · 31582 ms · 2026-05-24T04:21:05.344732+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

41 extracted references · 41 canonical work pages

  1. [1]

    On the sample complexity of privately learning unbounded high-dimensional gaussians

    Ishaq Aden-Ali , Hassan Ashtiani, and Gautam Kamath. On the sample complexity of privately learning unbounded high-dimensional gaussians. In Proceedings of the 32nd International Conference on Algorithmic Learning Theory , ALT '21, pages 185--216. JMLR, Inc., 2021

    work page 2021

  2. [2]

    Privately learning mixtures of axis-aligned gaussians

    Ishaq Aden-Ali , Hassan Ashtiani, and Christopher Liaw. Privately learning mixtures of axis-aligned gaussians. In Advances in Neural Information Processing Systems 34 , NeurIPS '21. Curran Associates, Inc., 2021

    work page 2021

  3. [3]

    Mixtures of gaussians are privately learnable with a polynomial number of samples

    Mohammad Afzali, Hassan Ashtiani, and Christopher Liaw. Mixtures of gaussians are privately learnable with a polynomial number of samples. arXiv preprint arXiv:2309.03847 , 2023

    work page arXiv 2023

  4. [4]

    Polynomial time and private learning of unbounded gaussian mixture models

    Jamil Arbas, Hassan Ashtiani, and Christopher Liaw. Polynomial time and private learning of unbounded gaussian mixture models. In Proceedings of the 40th International Conference on Machine Learning , ICML '23, pages 1018--1040. JMLR, Inc., 2023

    work page 2023

  5. [5]

    Near-optimal sample complexity bounds for robust learning of gaussian mixtures via compression schemes

    Hassan Ashtiani, Shai Ben-David, Nicholas JA Harvey, Christopher Liaw, Abbas Mehrabian, and Yaniv Plan. Near-optimal sample complexity bounds for robust learning of gaussian mixtures via compression schemes. Journal of the ACM , 67(6):32:1--32:42, 2020

    work page 2020

  6. [6]

    Privately estimating a G aussian: Efficient, robust and optimal

    Daniel Alabi, Pravesh K Kothari, Pranay Tankala, Prayaag Venkat, and Fred Zhang. Privately estimating a G aussian: Efficient, robust and optimal. In Proceedings of the 55th Annual ACM Symposium on the Theory of Computing , STOC '23, New York, NY, USA, 2023. ACM

    work page 2023

  7. [7]

    Private and polynomial time algorithms for learning G aussians and beyond

    Hassan Ashtiani and Christopher Liaw. Private and polynomial time algorithms for learning G aussians and beyond. In Proceedings of the 35th Annual Conference on Learning Theory , COLT '22, pages 1075--1076, 2022

    work page 2022

  8. [8]

    Private PAC learning implies finite L ittlestone dimension

    Noga Alon, Roi Livni, Maryanthe Malliaris, and Shay Moran. Private PAC learning implies finite L ittlestone dimension. In Proceedings of the 51st Annual ACM Symposium on the Theory of Computing , STOC '19, pages 852--860, New York, NY, USA, 2019. ACM

    work page 2019

  9. [9]

    Private learning of gaussians and their mixtures

    Hassan Ashtiani. Private learning of gaussians and their mixtures. https://www.youtube.com/watch?v=bmNjm0lx50I, July 2022

    work page 2022

  10. [10]

    Differentially private assouad, fano, and le cam

    Jayadev Acharya, Ziteng Sun, and Huanyu Zhang. Differentially private assouad, fano, and le cam. In Proceedings of the 32nd International Conference on Algorithmic Learning Theory , ALT '21, pages 48--78. JMLR, Inc., 2021

    work page 2021

  11. [11]

    From robustness to privacy and back

    Hilal Asi, Jonathan Ullman, and Lydia Zakynthinou. From robustness to privacy and back. arXiv preprint arXiv:2302.01855 , 2023

    work page arXiv 2023

  12. [12]

    Bounds on the sample complexity for private learning and private data release

    Amos Beimel, Hai Brenner, Shiva Prasad Kasiviswanathan, and Kobbi Nissim. Bounds on the sample complexity for private learning and private data release. Machine Learning , 94(3):401--437, 2014

    work page 2014

  13. [13]

    Distribution learnability and robustness

    Shai Ben-David, Alex Bie, Gautam Kamath, and Tosca Lechner. Distribution learnability and robustness. In Advances in Neural Information Processing Systems 36 , NeurIPS '23. Curran Associates, Inc., 2023

    work page 2023

  14. [14]

    Coinpress: Practical private mean and covariance estimation

    Sourav Biswas, Yihe Dong, Gautam Kamath, and Jonathan Ullman. Coinpress: Practical private mean and covariance estimation. In Advances in Neural Information Processing Systems 33 , NeurIPS '20, pages 14475--14485. Curran Associates, Inc., 2020

    work page 2020

  15. [15]

    Private estimation with public data

    Alex Bie, Gautam Kamath, and Vikrant Singhal. Private estimation with public data. In Advances in Neural Information Processing Systems 35 , NeurIPS '22. Curran Associates, Inc., 2022

    work page 2022

  16. [16]

    Private hypothesis selection

    Mark Bun, Gautam Kamath, Thomas Steinke, and Zhiwei Steven Wu. Private hypothesis selection. In Advances in Neural Information Processing Systems 32 , NeurIPS '19, pages 156--167. Curran Associates, Inc., 2019

    work page 2019

  17. [17]

    An equivalence between private classification and online prediction

    Mark Bun, Roi Livni, and Shay Moran. An equivalence between private classification and online prediction. In Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science , FOCS '20, pages 389--402, Washington, DC, USA, 2020. IEEE Computer Society

    work page 2020

  18. [18]

    Differentially private release and learning of threshold functions

    Mark Bun, Kobbi Nissim, Uri Stemmer, and Salil Vadhan. Differentially private release and learning of threshold functions. In Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science , FOCS '15, pages 634--649, Washington, DC, USA, 2015. IEEE Computer Society

    work page 2015

  19. [19]

    Average-case averages: Private algorithms for smooth sensitivity and mean estimation

    Mark Bun and Thomas Steinke. Average-case averages: Private algorithms for smooth sensitivity and mean estimation. In Advances in Neural Information Processing Systems 32 , NeurIPS '19, pages 181--191. Curran Associates, Inc., 2019

    work page 2019

  20. [20]

    The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy

    T Tony Cai, Yichen Wang, and Linjun Zhang. The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy. The Annals of Statistics , 49(5):2825--2850, 2021

    work page 2021

  21. [21]

    Servedio

    Constantinos Daskalakis, Ilias Diakonikolas, and Rocco A. Servedio. Learning P oisson binomial distributions. In Proceedings of the 44th Annual ACM Symposium on the Theory of Computing , STOC '12, pages 709--728, New York, NY, USA, 2012. ACM

    work page 2012

  22. [22]

    Differentially private learning of structured discrete distributions

    Ilias Diakonikolas, Moritz Hardt, and Ludwig Schmidt. Differentially private learning of structured discrete distributions. In Advances in Neural Information Processing Systems 28 , NIPS '15, pages 2566--2574. Curran Associates, Inc., 2015

    work page 2015

  23. [23]

    Combinatorial methods in density estimation

    Luc Devroye and G\'abor Lugosi. Combinatorial methods in density estimation . Springer, 2001

    work page 2001

  24. [24]

    Calibrating noise to sensitivity in private data analysis

    Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Proceedings of the 3rd Conference on Theory of Cryptography , TCC '06, pages 265--284, Berlin, Heidelberg, 2006. Springer

    work page 2006

  25. [25]

    Sample complexity bounds on differentially private learning via communication complexity

    Vitaly Feldman and David Xiao. Sample complexity bounds on differentially private learning via communication complexity. SIAM Journal on Computing , 44(6):1740--1764, 2015

    work page 2015

  26. [26]

    Robustness implies privacy in statistical estimation

    Samuel B Hopkins, Gautam Kamath, Mahbod Majid, and Shyam Narayanan. Robustness implies privacy in statistical estimation. In Proceedings of the 55th Annual ACM Symposium on the Theory of Computing , STOC '23, New York, NY, USA, 2023. ACM

    work page 2023

  27. [27]

    Privately learning high-dimensional distributions

    Gautam Kamath, Jerry Li, Vikrant Singhal, and Jonathan Ullman. Privately learning high-dimensional distributions. In Proceedings of the 32nd Annual Conference on Learning Theory , COLT '19, pages 1853--1902, 2019

    work page 1902

  28. [28]

    Schapire, and Linda Sellie

    Michael Kearns, Yishay Mansour, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire, and Linda Sellie. On the learnability of discrete distributions. In Proceedings of the 26th Annual ACM Symposium on the Theory of Computing , STOC '94, pages 273--282, New York, NY, USA, 1994. ACM

    work page 1994

  29. [29]

    A bias-variance-privacy trilemma for statistical estimation

    Gautam Kamath, Argyris Mouzakis, Matthew Regehr, Vikrant Singhal, Thomas Steinke, and Jonathan Ullman. A bias-variance-privacy trilemma for statistical estimation. arXiv preprint arXiv:2301.13334 , 2023

    work page arXiv 2023

  30. [30]

    New lower bounds for private estimation and a generalized fingerprinting lemma

    Gautam Kamath, Argyris Mouzakis, and Vikrant Singhal. New lower bounds for private estimation and a generalized fingerprinting lemma. In Advances in Neural Information Processing Systems 35 , NeurIPS '22. Curran Associates, Inc., 2022

    work page 2022

  31. [31]

    A private and computationally-efficient estimator for unbounded gaussians

    Gautam Kamath, Argyris Mouzakis, Vikrant Singhal, Thomas Steinke, and Jonathan Ullman. A private and computationally-efficient estimator for unbounded gaussians. In Proceedings of the 35th Annual Conference on Learning Theory , COLT '22, pages 544--572, 2022

    work page 2022

  32. [32]

    Private robust estimation by stabilizing convex relaxations

    Pravesh K Kothari, Pasin Manurangsi, and Ameya Velingker. Private robust estimation by stabilizing convex relaxations. In Proceedings of the 35th Annual Conference on Learning Theory , COLT '22, pages 723--777, 2022

    work page 2022

  33. [33]

    Differentially private algorithms for learning mixtures of separated G aussians

    Gautam Kamath, Or Sheffet, Vikrant Singhal, and Jonathan Ullman. Differentially private algorithms for learning mixtures of separated G aussians. In Advances in Neural Information Processing Systems 32 , NeurIPS '19, pages 168--180. Curran Associates, Inc., 2019

    work page 2019

  34. [34]

    A primer on private statistics

    Gautam Kamath and Jonathan Ullman. A primer on private statistics. arXiv preprint arXiv:2005.00010 , 2020

    work page arXiv 2005

  35. [35]

    Finite sample differentially private confidence intervals

    Vishesh Karwa and Salil Vadhan. Finite sample differentially private confidence intervals. In Proceedings of the 9th Conference on Innovations in Theoretical Computer Science , ITCS '18, pages 44:1--44:9, Dagstuhl, Germany, 2018. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik

    work page 2018

  36. [36]

    Impossibility of characterizing distribution learning--a simple solution to a long-standing problem

    Tosca Lechner and Shai Ben-David. Impossibility of characterizing distribution learning--a simple solution to a long-standing problem. arXiv preprint arXiv:2304.08712 , 2023

    work page arXiv 2023

  37. [37]

    Robust and differentially private mean estimation

    Xiyang Liu, Weihao Kong, Sham Kakade, and Sewoong Oh. Robust and differentially private mean estimation. In Advances in Neural Information Processing Systems 34 , NeurIPS '21. Curran Associates, Inc., 2021

    work page 2021

  38. [38]

    Differential privacy and robust statistics in high dimensions

    Xiyang Liu, Weihao Kong, and Sewoong Oh. Differential privacy and robust statistics in high dimensions. In Proceedings of the 35th Annual Conference on Learning Theory , COLT '22, pages 1167--1246, 2022

    work page 2022

  39. [39]

    Smooth sensitivity and sampling in private data analysis

    Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. Smooth sensitivity and sampling in private data analysis. In Proceedings of the 39th Annual ACM Symposium on the Theory of Computing , STOC '07, pages 75--84, New York, NY, USA, 2007. ACM

    work page 2007

  40. [40]

    A polynomial time, pure differentially private estimator for binary product distributions

    Vikrant Singhal. A polynomial time, pure differentially private estimator for binary product distributions. arXiv preprint arXiv:2304.06787 , 2023

    work page arXiv 2023

  41. [41]

    Friendlycore: Practical differentially private aggregation

    Eliad Tsfadia, Edith Cohen, Haim Kaplan, Yishay Mansour, and Uri Stemmer. Friendlycore: Practical differentially private aggregation. In Proceedings of the 39th International Conference on Machine Learning , ICML '22, pages 21828--21863. JMLR, Inc., 2022

    work page 2022