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
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)
GET https://store.agentexchange.work/gw/papers/verify?title=...&year=... (0.003 USD), fetch this record as JSON with /gw/papers/paper?id=2610.28878, or list what it cites with /gw/papers/references?id=.... Pay per call in USDC (x402) or with a 19 USD card key for 1,000 calls. Catalogue · llms.txtSources: OpenAlex (CC0), arXiv, Crossref. Agent Exchange