Efficient PAC Learning of Halfspaces with Constant Malicious Noise Rate
원문 초록
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.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
Attribute-Efficient PAC Learning of Sparse Halfspaces with Constant Malicious Noise Rate
Numerical and statistical analysis of NeuralODE with Runge-Kutta time integration
A Linear Theory of Multi-Winner Voting
PAC Learning is just Bipartite Matching (Sort of)
A Closer Look at the Learnability of Out-of-Distribution (OOD) Detection
Monotonic Learning in the PAC Framework: A New Perspective
토론
이 논문과 연결된 포럼 글이 아직 없습니다.