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 investigate the time complexity of SGD learning on fully-connected neuralnetworks with isotropic data. We put forward a complexity measure -- the leap-- which measures how "hierarchical" target functions are. For $d$-dimensionaluniform Boolean or isotropic Gaussian data, our main conjecture states that thetime complexity to learn a function $f$ with low-dimensional support is$\tilde\Theta (d^{\max(\mathrm{Leap}(f),2)})$. We prove a version of thisconjecture for a class of functions on Gaussian isotropic data and 2-layerneural networks, under additional technical assumptions on how SGD is run. Weshow that the training sequentially learns the function support with asaddle-to-saddle dynamic. Our result departs from [Abbe et al. 2022] by goingbeyond leap 1 (merged-staircase functions), and by going beyond the mean-fieldand gradient flow approximations that prohibit the full complexity controlobtained here. Finally, we note that this gives an SGD complexity for the fulltraining trajectory that matches that of Correlational Statistical Query (CSQ)lower-bounds.

SGD learning on neural networks: leap complexity and saddle-to-saddle dynamics