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 task of agnostically learning halfspaces under the Gaussiandistribution. Specifically, given labeled examples $(\mathbf{x},y)$ from anunknown distribution on $\mathbb{R}^n \times \{ \pm 1\}$, whose marginaldistribution on $\mathbf{x}$ is the standard Gaussian and the labels $y$ can bearbitrary, the goal is to output a hypothesis with 0-1 loss$\mathrm{OPT}+\epsilon$, where $\mathrm{OPT}$ is the 0-1 loss of thebest-fitting halfspace. We prove a near-optimal computational hardness resultfor this task, under the widely believed sub-exponential time hardness of theLearning with Errors (LWE) problem. Prior hardness results are eitherqualitatively suboptimal or apply to restricted families of algorithms. Ourtechniques extend to yield near-optimal lower bounds for related problems,including ReLU regression.

Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginals