Not All Learnable Distribution Classes are Privately Learnable

2024/02/01 by Bun, Mark, Kamath, Gautam, Mouzakis, Argyris +1 · 1 citation
#Cryptography and Security (cs.CR) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.2402.00267

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 (ε, δ)-differential privacy with the same target error. This weakly refutes a conjecture of Ashtiani.

Cited by

• Robust Learnability of Sample-Compressible Distributions under Noisy or Adversarial Perturbations

Related

• Differentially-Private Bayes Consistency
• Learning with Differential Privacy: Stability, Learnability and the Sufficiency and Necessity of ERM Principle
• Learning discrete distributions: user vs item-level privacy
• Private Distribution Learning with Public Data: The View from Sample Compression
• Differentially Private Sampling from Distributions