Poster
in
Workshop: OPT 2022: Optimization for Machine Learning
Neural Networks Efficiently Learn Low-Dimensional Representations with SGD
Alireza Mousavi-Hosseini · Sejun Park · Manuela Girotti · Ioannis Mitliagkas · Murat Erdogdu
Abstract:
We study the problem of training a two-layer neural network (NN) of arbitrary width using stochastic gradient descent (SGD) where the input is Gaussian and the target follows a multiple-index model, i.e., with a noisy link function . We prove that the first-layer weights of the NN converge to the -dimensional principal subspace spanned by the vectors of the true model, when online SGD with weight decay is used for training. This phenomenon has several important consequences when . First, by employing uniform convergence on this smaller subspace, we establish a generalization error bound of after iterations of SGD, which is independent of the width of the NN. We further demonstrate that, SGD-trained ReLU NNs can learn a single-index target of the form by recovering the principal direction, with a sample complexity linear in (up to log factors), where is a monotonic function with at most polynomial growth, and is the noise. This is in contrast to the known sample requirement to learn any degree polynomial in the kernel regime, and it shows that NNs trained with SGD can outperform the neural tangent kernel at initialization.
Chat is not available.