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

arXiv:2306.00673v2 Announce Type: replace-cross
Abstract: 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$ PTFs on $\mathbb{R}^n$, where any such concept depends only on $K$ out of $n$ attributes of the input. Our main contribution is a new algorithm that runs in time $({nd}/{\epsilon})^{O(d)}$ and under the Gaussian marginal distribution, PAC learns the class up to error rate $\epsilon$ with $O(\frac{K^{4d}}{\epsilon^{2d}} \cdot \log^{5d} …

abstract arxiv class concept cs.ds cs.lg functions low machine machine learning noise paper polynomial role stat.ml study threshold type