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 problem of agnostic learning under the Gaussian distribution. Wedevelop a method for finding hard families of examples for a wide class ofproblems by using LP duality. For Boolean-valued concept classes, we show thatthe $L^1$-regression algorithm is essentially best possible, and therefore thatthe computational difficulty of agnostically learning a concept class isclosely related to the polynomial degree required to approximate any functionfrom the class in $L^1$-norm. Using this characterization along with additionalanalytic tools, we obtain optimal SQ lower bounds for agnostically learninglinear threshold functions and the first non-trivial SQ lower bounds forpolynomial threshold functions and intersections of halfspaces. We also developan analogous theory for agnostically learning real-valued functions, and as anapplication prove near-optimal SQ lower bounds for agnostically learning ReLUsand sigmoids.

The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals