Timezone: »

 
Poster
The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise
Ilias Diakonikolas · Daniel M. Kane · Pasin Manurangsi

Tue Dec 08 09:00 AM -- 11:00 AM (PST) @ Poster Session 1 #231
in Poster Session 2 »
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$.

Author Information

Ilias Diakonikolas (UW Madison)
Daniel M. Kane (UCSD)
Pasin Manurangsi (Google)

More from the Same Authors