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
我們顯示,每類分布,可以學習到任意小目標錯誤在總變化距離與有限數的樣本,也可學習下($\varepsilon, δ$)-差異隱私,直到任意小目標錯誤與有限數的樣本。這證明了阿什蒂安的猜測。 以前的工作由Bun,Kamath,Mouzakis,和Singhal [arXiv:2402.00267]給出了弱否定這個猜測,顯示當可學習性被定義與固定目標錯誤相對時,這種推測不是真的。
Machine translation (Meta M2M100); the English original follows.
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