The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise

Part of Advances in Neural Information Processing Systems 33 (NeurIPS 2020)

Authors

Ilias Diakonikolas, Daniel M. Kane, Pasin Manurangsi

Abstract

We study the computational complexity of adversarially robust proper learning of halfspaces in the distribution-independent agnostic PAC model, with a focus on $L_p$ perturbations. We give a computationally efficient learning algorithm and a nearly matching computational hardness result for this problem. An interesting implication of our findings is that the $L_{\infty}$ perturbations case is provably computationally harder than the case $2 \leq p < \infty$.