Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2505.21430 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915834527481856 |
|---|---|
| author | Zeng, Shiwei Shen, Jie |
| author_facet | Zeng, Shiwei Shen, Jie |
| contents | 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 the goal is to learn an underlying $s$-sparse halfspace $w^* \in \mathbb{R}^d$ with $\text{poly}(s,\log 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. Under such conditions, we show that attribute-efficiency can be achieved with simple variants to existing hinge loss minimization programs. Our key contribution includes: 1) an attribute-efficient PAC learning algorithm that works under a constant malicious noise rate; 2) a new gradient analysis that carefully handles the sparsity admitted constraints in hinge loss minimization program. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_21430 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Attribute-Efficient PAC Learning of Sparse Halfspaces with Constant Malicious Noise Rate Zeng, Shiwei Shen, Jie Machine Learning 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 the goal is to learn an underlying $s$-sparse halfspace $w^* \in \mathbb{R}^d$ with $\text{poly}(s,\log 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. Under such conditions, we show that attribute-efficiency can be achieved with simple variants to existing hinge loss minimization programs. Our key contribution includes: 1) an attribute-efficient PAC learning algorithm that works under a constant malicious noise rate; 2) a new gradient analysis that carefully handles the sparsity admitted constraints in hinge loss minimization program. |
| title | Attribute-Efficient PAC Learning of Sparse Halfspaces with Constant Malicious Noise Rate |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2505.21430 |