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 give tight statistical query (SQ) lower bounds for learnining halfspacesin the presence of Massart noise. In particular, suppose that all labels arecorrupted with probability at most $\eta$. We show that for arbitrary $\eta \in[0,1/2]$ every SQ algorithm achieving misclassification error better than$\eta$ requires queries of superpolynomial accuracy or at least asuperpolynomial number of queries. Further, this continues to hold even if theinformation-theoretically optimal error $\mathrm{OPT}$ is as small as$\exp\left(-\log^c(d)\right)$, where $d$ is the dimension and $0 < c < 1$ is anarbitrary absolute constant, and an overwhelming fraction of examples arenoiseless. Our lower bound matches known polynomial time algorithms, which arealso implementable in the SQ framework. Previously, such lower bounds onlyruled out algorithms achieving error $\mathrm{OPT} + \epsilon$ or error betterthan $\Omega(\eta)$ or, if $\eta$ is close to $1/2$, error $\eta - o_\eta(1)$,where the term $o_\eta(1)$ is constant in $d$ but going to 0 for $\eta$approaching $1/2$.  As a consequence, we also show that achieving misclassification error betterthan $1/2$ in the $(A,\alpha)$-Tsybakov model is SQ-hard for $A$ constant and$\alpha$ bounded away from 1.

Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noise