The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise
This addresses a theoretical problem in machine learning for researchers, offering insights into the computational limits of robust learning, but it is incremental as it builds on existing PAC model frameworks.
The paper tackles the computational complexity of adversarially robust proper learning of halfspaces with agnostic noise under L_p perturbations, providing an efficient algorithm and a nearly matching hardness result, and shows that L_∞ perturbations are computationally harder than cases with 2 ≤ p < ∞.
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$.