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 PAC learning one-hidden-layer ReLU networks with $k$hidden units on $\mathbb{R}^d$ under Gaussian marginals in the presence ofadditive label noise. For the case of positive coefficients, we give the firstpolynomial-time algorithm for this learning problem for $k$ up to$\tilde{O}(\sqrt{\log d})$. Previously, no polynomial time algorithm was known,even for $k=3$. This answers an open question posed by~\cite{Kliv17}.Importantly, our algorithm does not require any assumptions about the rank ofthe weight matrix and its complexity is independent of its condition number. Onthe negative side, for the more general task of PAC learning one-hidden-layerReLU networks with arbitrary real coefficients, we prove a Statistical Querylower bound of $d^{\Omega(k)}$. Thus, we provide a separation between the twoclasses in terms of efficient learnability. Our upper and lower bounds aregeneral, extending to broader families of activation functions.

Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks