Optimal Robust Learning of Discrete Distributions from Batches
Many applications, including natural language processing, sensor networks, collaborative filtering, and federated learning, call for estimating discrete distributions from data collected in batches, some of which may be untrustworthy, erroneous, faulty, or even adversarial. Previous estimators for this setting ran in exponential time, and for some regimes required a suboptimal number of batches. We provide the first polynomial-time estimator that is optimal in the number of batches and achieves essentially the best possible estimation accuracy.
Code (0)
등록된 구현이 없습니다.
Tasks
Collaborative FilteringFederated LearningSimilar Papers 제목 키워드 기반
A General Method for Robust Learning from Batches
In many applications, data is collected in batches, some of which are corrupt or even adversarial. Recent work derived optimal robust algorithms for estimating discrete distributions in this setting. We consider a genera…
ClassificationGeneral ClassificationHigh-Dimensional Robust Mean Estimation with Untrusted Batches
We study high-dimensional mean estimation in a collaborative setting where data is contributed by $N$ users in batches of size $n$. In this environment, a learner seeks to recover the mean $μ$ of a true distribution $P$ …
Learning Discrete Distributions from Untrusted Batches
We consider the problem of learning a discrete distribution in the presence of an $\epsilon$ fraction of malicious data sources. Specifically, we consider the setting where there is some underlying distribution, $p$, and…
Robust Estimation of Discrete Distributions under Local Differential Privacy
Although robust learning and local differential privacy are both widely studied fields of research, combining the two settings is just starting to be explored. We consider the problem of estimating a discrete distributio…
AlignFlow: Improving Flow-based Generative Models with Semi-Discrete Optimal Transport
Flow-based Generative Models (FGMs) effectively transform noise into complex data distributions. Incorporating Optimal Transport (OT) to couple noise and data during FGM training has been shown to improve the straightnes…