Efficiently Learning Adversarially Robust Halfspaces with Noise
This addresses the challenge of robust machine learning for security-critical applications, offering incremental improvements in theoretical understanding and algorithmic efficiency.
The paper tackles the problem of learning adversarially robust halfspaces, providing conditions for efficient learnability in the realizable setting and a computationally efficient algorithm for handling random label noise under any ℓ_p-perturbation.
We study the problem of learning adversarially robust halfspaces in the distribution-independent setting. In the realizable setting, we provide necessary and sufficient conditions on the adversarial perturbation sets under which halfspaces are efficiently robustly learnable. In the presence of random label noise, we give a simple computationally efficient algorithm for this problem with respect to any $\ell_p$-perturbation.