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, δ$)의 차별적 개인 정보 보호 아래서도 배울 수 있다는 것을 보여줍니다. 이것은 Ashtiani의 추측을 증명합니다. Bun, Kamath, Mouzakis, and 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