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^* \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.

Machine Learning (cs.LG)

arXiv:2505.21430 [cs.LG]

(or arXiv:2505.21430v3 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2505.21430 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.