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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

The success of neural networks over the past decade has established them aseffective models for many relevant data generating processes. Statisticaltheory on neural networks indicates graceful scaling of sample complexity. Forexample, Joen & Van Roy (arXiv:2203.00246) demonstrate that, when data isgenerated by a ReLU teacher network with $W$ parameters, an optimal learnerneeds only $\tilde{O}(W/\epsilon)$ samples to attain expected error $\epsilon$.However, existing computational theory suggests that, even forsingle-hidden-layer teacher networks, to attain small error for all suchteacher networks, the computation required to achieve this sample complexity isintractable. In this work, we fit single-hidden-layer neural networks to datagenerated by single-hidden-layer ReLU teacher networks with parameters drawnfrom a natural distribution. We demonstrate that stochastic gradient descent(SGD) with automated width selection attains small expected error with a numberof samples and total number of queries both nearly linear in the inputdimension and width. This suggests that SGD nearly achieves theinformation-theoretic sample complexity bounds of Joen & Van Roy(arXiv:2203.00246) in a computationally efficient manner. An importantdifference between our positive empirical results and the negative theoreticalresults is that the latter address worst-case error of deterministicalgorithms, while our analysis centers on expected error of a stochasticalgorithm.

Is Stochastic Gradient Descent Near Optimal?