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

Russian

Мы показываем, что каждый класс распределений, который можно узнать до произвольно небольшой целевой ошибки в общей вариационной дистанции с конечным количеством образцов, также можно узнать под ($\varepsilon, δ$)-дифференциальной конфиденциальностью до произвольно небольшой целевой ошибки с конечным количеством образцов. Это доказывает предположение Аштяни. Предыдущая работа Бун, Камата, Музакиса и Сингала [arXiv:2402.00267] дала слабое опровержение этой предположения, показывая, что это предположение не верно, когда узнаваемость определена по отношению к фиксированной целевой ошибке.

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