Robust Learning with Optimal Error
We construct algorithms with optimal error for learning with adversarial noise. The overarching theme of this work is that the use of textsl{randomized} hypotheses can substantially improve upon the best error rates achievable with deterministic hypotheses. – For $η$-rate malicious noise, we show the optimal error is $frac{1}{2} cdot η/(1-η)$, improving on the optimal error of deterministic hypotheses by a factor of $1/2$. This answers an open question of Cesa-Bianchi et al. (JACM 1999) who showed randomness can […]