Not All Learnable Distribution Classes are Privately Learnable

Mark Bun; Gautam Kamath; Argyris Mouzakis; Vikrant Singhal

Not All Learnable Distribution Classes are Privately Learnable

Mark Bun, Gautam Kamath, Argyris Mouzakis, Vikrant Singhal

Proceedings of The 35th International Conference on Algorithmic Learning Theory, PMLR 237:390-401, 2024.

Abstract

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

Cite this Paper

BibTeX


@InProceedings{pmlr-v237-bun24b,
  title = 	 {Not All Learnable Distribution Classes are Privately Learnable},
  author =       {Bun, Mark and Kamath, Gautam and Mouzakis, Argyris and Singhal, Vikrant},
  booktitle = 	 {Proceedings of The 35th International Conference on Algorithmic Learning Theory},
  pages = 	 {390--401},
  year = 	 {2024},
  editor = 	 {Vernade, Claire and Hsu, Daniel},
  volume = 	 {237},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {25--28 Feb},
  publisher =    {PMLR},
  pdf = 	 {https://proceedings.mlr.press/v237/bun24b/bun24b.pdf},
  url = 	 {https://proceedings.mlr.press/v237/bun24b.html},
  abstract = 	 {We give an example of a class of distributions that is learnable in total variation distance with a finite number of samples, but not learnable under $(\varepsilon, \delta)$-differential privacy. This refutes a conjecture of Ashtiani.}
}

Endnote

%0 Conference Paper
%T Not All Learnable Distribution Classes are Privately Learnable
%A Mark Bun
%A Gautam Kamath
%A Argyris Mouzakis
%A Vikrant Singhal
%B Proceedings of The 35th International Conference on Algorithmic Learning Theory
%C Proceedings of Machine Learning Research
%D 2024
%E Claire Vernade
%E Daniel Hsu	
%F pmlr-v237-bun24b
%I PMLR
%P 390--401
%U https://proceedings.mlr.press/v237/bun24b.html
%V 237
%X We give an example of a class of distributions that is learnable in total variation distance with a finite number of samples, but not learnable under $(\varepsilon, \delta)$-differential privacy. This refutes a conjecture of Ashtiani.

APA


Bun, M., Kamath, G., Mouzakis, A. & Singhal, V.. (2024). Not All Learnable Distribution Classes are Privately Learnable. Proceedings of The 35th International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 237:390-401 Available from https://proceedings.mlr.press/v237/bun24b.html.

Related Material

Download PDF