Not All Learnable Distribution Classes are Privately Learnable

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 $(\epsilon ,\hat{I}´)$-differential privacy with the same target error. This weakly refutes a conjecture of Ashtiani.

Appeared in ALT 2024. Fixed a bug and improved exposition. Same version as the one in AM's PhD thesis