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 consider the well-studied problem of learning intersections of halfspacesunder the Gaussian distribution in the challenging \emph{agnostic learning}model. Recent work of Diakonikolas et al. (2021) shows that any StatisticalQuery (SQ) algorithm for agnostically learning the class of intersections of$k$ halfspaces over $\mathbb{R}^n$ to constant excess error either must makequeries of tolerance at most $n^{-\tilde{\Omega}(\sqrt{\log k})}$ or must make$2^{n^{\Omega(1)}}$ queries. We strengthen this result by improving thetolerance requirement to $n^{-\tilde{\Omega}(\log k)}$. This lower bound isessentially best possible since an SQ algorithm of Klivans et al. (2008)agnostically learns this class to any constant excess error using $n^{O(\logk)}$ queries of tolerance $n^{-O(\log k)}$. We prove two variants of our lowerbound, each of which combines ingredients from Diakonikolas et al. (2021) with(an extension of) a different earlier approach for agnostic SQ lower bounds forthe Boolean setting due to Dachman-Soled et al. (2014). Our approach alsoyields lower bounds for agnostically SQ learning the class of "convex subspacejuntas" (studied by Vempala, 2010) and the class of sets with bounded Gaussiansurface area; all of these lower bounds are nearly optimal since theyessentially match known upper bounds from Klivans et al. (2008).

Near-Optimal Statistical Query Lower Bounds for Agnostically Learning Intersections of Halfspaces with Gaussian Marginals