Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals

• Published in: arXiv.org 2020-06
• Main Authors: Diakonikolas, Ilias, Kane, Daniel M, Zarifis, Nikos
• Format: Article
• Language: English
• Subjects: Hypotheses; Labels; Learning; Lower bounds; Monte Carlo simulation; Upper bounds
• ISSN: 2331-8422

We study the fundamental problems of agnostically learning halfspaces and ReLUs under Gaussian marginals. In the former problem, given labeled examples \((\mathbf{x}, y)\) from an unknown distribution on \(\mathbb{R}^d \times \{ \pm 1\}\), whose marginal distribution on \(\mathbf{x}\) is the standard Gaussian and the labels \(y\) can be arbitrary, the goal is to output a hypothesis with 0-1 loss \(\mathrm{OPT}+\epsilon\), where \(\mathrm{OPT}\) is the 0-1 loss of the best-fitting halfspace. In the latter problem, given labeled examples \((\mathbf{x}, y)\) from an unknown distribution on \(\mathbb{R}^d \times \mathbb{R}\), whose marginal distribution on \(\mathbf{x}\) is the standard Gaussian and the labels \(y\) can be arbitrary, the goal is to output a hypothesis with square loss \(\mathrm{OPT}+\epsilon\), where \(\mathrm{OPT}\) is the square loss of the best-fitting ReLU. We prove Statistical Query (SQ) lower bounds of \(d^{\mathrm{poly}(1/\epsilon)}\) for both of these problems. Our SQ lower bounds provide strong evidence that current upper bounds for these tasks are essentially best possible.