Efficient PAC Learning of Halfspaces with Constant Malicious Noise Rate

Jie Shen
Proceedings of The 36th International Conference on Algorithmic Learning Theory, PMLR 272:1108-1137, 2025.

Abstract

Understanding noise tolerance of machine learning algorithms is a central quest in learning theory. In this work, we study the problem of computationally efficient PAC learning of halfspaces in the presence of malicious noise, where an adversary can corrupt both instances and labels of training samples. The best-known noise tolerance either depends on a target error rate under distributional assumptions or on a margin parameter under large-margin conditions. In this work, we show that when both types of conditions are satisfied, it is possible to achieve constant noise tolerance by minimizing a reweighted hinge loss. Our key ingredients include: 1) an efficient algorithm that finds weights to control the gradient deterioration from corrupted samples, and 2) a new analysis on the robustness of the hinge loss equipped with such weights.

Cite this Paper

BibTeX
@InProceedings{pmlr-v272-shen25a, title = {Efficient PAC Learning of Halfspaces with Constant Malicious Noise Rate}, author = {Shen, Jie}, booktitle = {Proceedings of The 36th International Conference on Algorithmic Learning Theory}, pages = {1108--1137}, year = {2025}, editor = {Kamath, Gautam and Loh, Po-Ling}, volume = {272}, series = {Proceedings of Machine Learning Research}, month = {24--27 Feb}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v272/main/assets/shen25a/shen25a.pdf}, url = {https://proceedings.mlr.press/v272/shen25a.html}, abstract = {Understanding noise tolerance of machine learning algorithms is a central quest in learning theory. In this work, we study the problem of computationally efficient PAC learning of halfspaces in the presence of malicious noise, where an adversary can corrupt both instances and labels of training samples. The best-known noise tolerance either depends on a target error rate under distributional assumptions or on a margin parameter under large-margin conditions. In this work, we show that when both types of conditions are satisfied, it is possible to achieve constant noise tolerance by minimizing a reweighted hinge loss. Our key ingredients include: 1) an efficient algorithm that finds weights to control the gradient deterioration from corrupted samples, and 2) a new analysis on the robustness of the hinge loss equipped with such weights.} }
Endnote
%0 Conference Paper %T Efficient PAC Learning of Halfspaces with Constant Malicious Noise Rate %A Jie Shen %B Proceedings of The 36th International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2025 %E Gautam Kamath %E Po-Ling Loh %F pmlr-v272-shen25a %I PMLR %P 1108--1137 %U https://proceedings.mlr.press/v272/shen25a.html %V 272 %X Understanding noise tolerance of machine learning algorithms is a central quest in learning theory. In this work, we study the problem of computationally efficient PAC learning of halfspaces in the presence of malicious noise, where an adversary can corrupt both instances and labels of training samples. The best-known noise tolerance either depends on a target error rate under distributional assumptions or on a margin parameter under large-margin conditions. In this work, we show that when both types of conditions are satisfied, it is possible to achieve constant noise tolerance by minimizing a reweighted hinge loss. Our key ingredients include: 1) an efficient algorithm that finds weights to control the gradient deterioration from corrupted samples, and 2) a new analysis on the robustness of the hinge loss equipped with such weights.
APA
Shen, J.. (2025). Efficient PAC Learning of Halfspaces with Constant Malicious Noise Rate. Proceedings of The 36th International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 272:1108-1137 Available from https://proceedings.mlr.press/v272/shen25a.html.

Related Material