Statistical-Query Lower Bounds via Functional Gradients

Understand

We give the first statistical-query lower bounds for agnostically learning any non-polynomial activation with respect to Gaussian marginals (e.g., ReLU, sigmoid, sign).

• For the specific problem of ReLU regression (equivalently, agnostically learning a ReLU), we show that any statistical-query algorithm with tolerance $n^{-(1/\epsilon)^b}$ must use at least $2^{n^c} \epsilon$ queries for some constant $b, c > 0$, where $n$ is the dimension and $\epsilon$ is the accuracy parameter.
• Our results rule out general (as opposed to correlational) SQ learning algorithms, which is unusual for real-valued learning problems.
• Our techniques involve a gradient boosting procedure for "amplifying" recent lower bounds due to Diakonikolas et al.