A Proper SQ PTAS for Agnostic Learning of Arbitrarily Biased ReLUs

Agnostic ReLU regression seeks to match the best single ReLU under arbitrary label noise. Under standard Gaussian inputs, we give a deterministic proper statistical query (SQ) polynomial-time approximation scheme (PTAS) for this problem with arbitrary bias. For every fixed $\eta >0$, the learner returns a ReLU with weight norm at most $W$ and squared loss at most $(1+\eta ){\mathrm{OPT}}_W+\epsilon$, where ${\mathrm{OPT}}_W$ is the minimum loss over the same class. This sharpens prior constant-factor guarantees to a factor arbitrarily close to one while preserving the model class and norm constraint. To obtain this guarantee, we reduce the search to $O({\eta }^{-2})$ dimensions while preserving the comparator's Gaussian output distribution and controlling its label correlation. For fixed $\eta$ and a known label second-moment bound, the query count, inverse tolerance, and arithmetic cost are polynomial in the dimension, $W$, the moment bound, and $1/\epsilon$. Moreover, the same guarantee extends to unknown finite label second moments without polynomial dependence on label scale: only logarithmically many additional queries are needed to locate the label mean.