Newest papers

Actually, All Learnable Distribution Classes Are Privately Learnable

Mohammad Afzali, Hassan Ashtiani, Alex Bie, Gautam Kamath, Peihan Liu, Argyris Mouzakis, Vikrant Singhal · 2026 · arXiv (Cornell University)

DOI: 10.48550/arxiv.2610.28878 · cited by 0 works (OpenAlex) · open-access PDF

German

Wir zeigen, dass jede Klasse von Verteilungen, die bis zu willkürlich kleinen Zielfehlern in der Gesamtvariationsdistanz mit endlich vielen Proben lernbar ist, auch unter ($\varepsilon, δ$)-differenzieller Privatsphäre bis zu willkürlich kleinen Zielfehlern mit endlich vielen Proben lernbar ist. Dies beweist eine Vermutung von Ashtiani. Frühere Arbeiten von Bun, Kamath, Mouzakis und Singhal [arXiv:2402.00267] gaben eine schwache Widerlegung dieser Vermutung, was zeigt, dass diese Implikation nicht wahr ist, wenn Lernbarkeit in Bezug auf einen festen Zielfehler definiert wird. Im Gegensatz dazu zeigen wir, dass die Vermutung unter der Standarddefinition von Lernbarkeit wahr ist.

Machine translation (Meta M2M100); the English original follows.

Abstract

We show that every class of distributions that is learnable up to arbitrarily small target error in total variation distance with finitely many samples is also learnable under ($\varepsilon, δ$)-differential privacy up to arbitrarily small target error with finitely many samples. This proves a conjecture of Ashtiani. Previous work by Bun, Kamath, Mouzakis, and Singhal [arXiv:2402.00267] gave a weak refutation of this conjecture, showing that this implication is not true when learnability is defined with respect to a fixed target error. In contrast, we show that, under the standard definition of learnability, the conjecture is true.

Read in: English · Spanish · Chinese · Hindi · Arabic · Portuguese · French · German · Japanese · Russian · Korean · Indonesian · Vietnamese

Topics: Mathematics, Conjecture, Learnability, Combinatorics, Discrete mathematics, Class (philosophy)

Sources: OpenAlex (CC0), arXiv, Crossref. Agent Exchange