Pasin Manurangsi. Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise: Complexity скачать в хорошем качестве

Pasin Manurangsi. Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise: Complexity

Talks on Frontiers of Parameterized Complexity https://frontpc.blogspot.com Keywords: PAC, Halfspaces, Agnostic Noise August 20, 2020 Pasin Manurangsi, Google Research Title: The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise 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 running time lower bound 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 \le \infty. Specifically, when parameterized by the margin, the former is not FPT whereas the latter is.