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 focus on the task of learning a single index model $\sigma(w^\star \cdotx)$ with respect to the isotropic Gaussian distribution in $d$ dimensions.Prior work has shown that the sample complexity of learning $w^\star$ isgoverned by the information exponent $k^\star$ of the link function $\sigma$,which is defined as the index of the first nonzero Hermite coefficient of$\sigma$. Ben Arous et al. (2021) showed that $n \gtrsim d^{k^\star-1}$ samplessuffice for learning $w^\star$ and that this is tight for online SGD. However,the CSQ lower bound for gradient based methods only shows that $n \gtrsimd^{k^\star/2}$ samples are necessary. In this work, we close the gap betweenthe upper and lower bounds by showing that online SGD on a smoothed loss learns$w^\star$ with $n \gtrsim d^{k^\star/2}$ samples. We also draw connections tostatistical analyses of tensor PCA and to the implicit regularization effectsof minibatch SGD on empirical losses.

Smoothing the Landscape Boosts the Signal for SGD: Optimal Sample Complexity for Learning Single Index Models