Robust Learning of Discrete Distributions from Batches

11/19/2019

∙

by   Alon Orlitsky, et al.

∙

0

∙

share

Let d be the lowest L_1 distance to which a k-symbol distribution p can be estimated from m batches of n samples each, when up to β m batches may be adversarial. For β<1/2, Qiao and Valiant (2017) showed that d=Ω(β/√(n)) and requires m=Ω(k/β^2) batches. For β<1/900, they provided a d and m order-optimal algorithm that runs in time exponential in k. For β<0.5, we propose an algorithm with comparably optimal d and m, but run-time polynomial in k and all other parameters.