Attribute-Efficient Learning of Halfspaces with Malicious Noise: Near-Optimal Label Complexity and Noise Tolerance

Jie Shen, Chicheng Zhang

This paper is concerned with computationally efficient learning of homogeneous sparse halfspaces in ${\mathbb{R}}^d$ under noise. Though recent works have established attribute-effic…