Attribute-Efficient Learning of Sparse Halfspaces with Constant Malicious Noise Rate

Attribute-efficient PAC learning of sparse halfspaces has been a fundamental problem in machine learning theory. In recent years, machine learning algorithms are faced with prevalent data corruptions or even malicious attacks. It is of central interest to design computationally-efficient algorithms that are robust to malicious corruptions. In this paper, we consider that there exists a constant amount of malicious noise in the data and show that it is possible to learn an underlying $s$-sparse halfspace $w^* \in \mathbb{R}^d$ with $O(s^2\log^5 d)$ samples. Specifically, we follow a recent line of works and assume that the underlying distribution satisfies a certain concentration condition and a margin condition at the same time. As a complementary result, we provide an information-theoretic sample lower bound under such conditions. Strong evidence shows that our sample complexity is nearly optimal. To show the robustness of our algorithm, we provide a new gradient analysis that carefully handles the sparsity admitted constraints in hinge loss minimization program, which could be of independent interest.