English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study the fundamental problems of agnostically learning halfspaces andReLUs under Gaussian marginals. In the former problem, given labeled examples$(\mathbf{x}, y)$ from an unknown distribution on $\mathbb{R}^d \times \{ \pm1\}$, whose marginal distribution on $\mathbf{x}$ is the standard Gaussian andthe labels $y$ can be arbitrary, the goal is to output a hypothesis with 0-1loss $\mathrm{OPT}+\epsilon$, where $\mathrm{OPT}$ is the 0-1 loss of thebest-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 standardGaussian and the labels $y$ can be arbitrary, the goal is to output ahypothesis with square loss $\mathrm{OPT}+\epsilon$, where $\mathrm{OPT}$ isthe square loss of the best-fitting ReLU. We prove Statistical Query (SQ) lowerbounds of $d^{\mathrm{poly}(1/\epsilon)}$ for both of these problems. Our SQlower bounds provide strong evidence that current upper bounds for these tasksare essentially best possible.

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