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

Abstract

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 and attribute-efficient algorithms that are robust to extreme corruptions. In this paper, we consider that there is a constant amount of malicious noise in the data and show that it is possible to PAC learn an underlying $s$-sparse halfspace $w^{\ast }\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 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 even for the noiseless case. There is evidence showing that our sample complexity could be 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.

v3 adds a complementary result on an information-theoretic sample lower bound