Attribute-Efficient PAC Learning of Low-Degree Polynomial Threshold Functions with Nasty Noise

Shiwei Zeng, Jie Shen

The concept class of low-degree polynomial threshold functions (PTFs) plays a fundamental role in machine learning. In this paper, we study PAC learning of $K$-sparse degree-$d$ PT…