06/12/2020

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

Ilias Diakonikolas, Daniel M. Kane, Pasin Manurangsi

Keywords:

Abstract Paper Similar Papers

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$.

 0
 0
 0
 0
  Share    
This is an embedded video. Talk and the respective paper are published at NeurIPS 2020 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment
no comments yet
code of conduct: tbd Characters remaining: 140

Similar Papers

 0
 0
 0
 0
 15:40 
 1
 1
 0
 0
 3:29 
 0
 0
 0
 0
 7:41 
 0
 0
 0
 0
 19:14 
 0
 0
 0
 0
 13:24 
 0
 0
 0
 0
 20:19 
 0
 0
 0
 0
 3:20 
 0
 0
 0
 0
 10:43 
 0
 0
 0
 0
 15:18 
 0
 0
 0
 0
 5:03 
 0
 0
 0
 0
 10:40 
 0
 0
 0
 0
 3:07 
 0
 0
 0
 0
 3:06 
 0
 0
 0
 1
 3:28 
 0
 0
 0
 0
 3:42 
 0
 0
 0
 0
 17:13 
 0
 0
 0
 0
 8:04 
 0
 0
 0
 0
 5:53 
 0
 0
 0
 0
 3:04 
 0
 0
 0
 0
 3:20 
 0
 0
 0
 0
 3:12 
 0
 0
 0
 0
 2:54 
 0
 0
 0
 0
 20:29 
 0
 0
 0
 0
 15:32 
 0
 0
 0
 1
 5:18 
 0
 0
 0
 0
 13:10 
 1
 1
 0
 0
 5:46 
 0
 0
 0
 0
 15:09 
 0
 0
 0
 0
 3:11 
 0
 0
 0
 0
 5:36 
 0
 0
 0
 0
 14:56 
 0
 0
 0
 0
 2:58 
 0
 0
 0
 0
 10:13 
 0
 0
 0
 0
 3:19 
 0
 0
 0
 0
 13:56 
 0
 0
 0
 0
 7:40 
 0
 0
 0
 0
 3:01 
 0
 0
 0
 0
 10:21 
 0
 0
 0
 0
 14:21 
 0
 0
 0
 0
 12:48