Part of Advances in Neural Information Processing Systems 33 (NeurIPS 2020)
Ilias Diakonikolas, Daniel M. Kane, Pasin Manurangsi
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$.