Statistical-Query Lower Bounds via Functional Gradients

Abstract

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. (COLT 2020) and Goel et al. (ICML 2020) on the SQ dimension of functions computed by two-layer neural networks. The crucial new ingredient is the use of a nonstandard convex functional during the boosting procedure. This also yields a best-possible reduction between two commonly studied models of learning: agnostic learning and probabilistic concepts.

arXiv comment34 pages, NeurIPS 2020

References in corpus (10)

• On the Computational Efficiency of Training Neural Networks
• Reliably Learning the ReLU in Polynomial Time
• Online Gradient Boosting
• Gradient Descent for One-Hidden-Layer Neural Networks: Polynomial Convergence and SQ Lower Bounds
• Time/Accuracy Tradeoffs for Learning a ReLU with respect to Gaussian Marginals
• Agnostic Learning of a Single Neuron with Gradient Descent
• Effect of Activation Functions on the Training of Overparametrized Neural Nets
• Learning a Single Neuron with Gradient Methods
• Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descent
• Approximation Schemes for ReLU Regression

Cited by in corpus (8)

• Agnostic Learning of a Single Neuron with Gradient Descent
• Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals
• A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise
• Non-Convex SGD Learns Halfspaces with Adversarial Label Noise
• Agnostic Proper Learning of Halfspaces under Gaussian Marginals
• From Local Pseudorandom Generators to Hardness of Learning
• Near-Optimal Statistical Query Hardness of Learning Halfspaces with Massart Noise
• Achieving Adversarial Robustness Requires An Active Teacher