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 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\le p<\infty$.

References in corpus (2)

• On Robustness to Adversarial Examples and Polynomial Optimization
• Efficiently Learning Adversarially Robust Halfspaces with Noise

Cited by in corpus (1)

• Differentially Private Clustering: Tight Approximation Ratios