Bayes-optimal learning of an extensive-width neural network from quadratically many samples
This provides a theoretical foundation for understanding optimal learning in wide neural networks with quadratic activations, addressing a specific open problem in high-dimensional statistics.
The paper tackles the problem of learning a target function from a single hidden layer neural network with quadratic activation in the asymptotic limit of large input dimension and width, solving the open challenge of deriving the Bayes-optimal test error when the number of samples is quadratic in the dimension. They provide a closed-form expression for this error and propose an algorithm (GAMP-RIE) that asymptotically achieves optimal performance.
We consider the problem of learning a target function corresponding to a single hidden layer neural network, with a quadratic activation function after the first layer, and random weights. We consider the asymptotic limit where the input dimension and the network width are proportionally large. Recent work [Cui & al '23] established that linear regression provides Bayes-optimal test error to learn such a function when the number of available samples is only linear in the dimension. That work stressed the open challenge of theoretically analyzing the optimal test error in the more interesting regime where the number of samples is quadratic in the dimension. In this paper, we solve this challenge for quadratic activations and derive a closed-form expression for the Bayes-optimal test error. We also provide an algorithm, that we call GAMP-RIE, which combines approximate message passing with rotationally invariant matrix denoising, and that asymptotically achieves the optimal performance. Technically, our result is enabled by establishing a link with recent works on optimal denoising of extensive-rank matrices and on the ellipsoid fitting problem. We further show empirically that, in the absence of noise, randomly-initialized gradient descent seems to sample the space of weights, leading to zero training loss, and averaging over initialization leads to a test error equal to the Bayes-optimal one.