Bounding the Width of Neural Networks via Coupled Initialization -- A Worst Case Analysis
This work addresses the computational efficiency and theoretical understanding of neural network training for researchers in machine learning theory, though it is incremental as it builds on prior initialization techniques.
The paper tackles the problem of reducing the number of neurons required in two-layer ReLU neural networks by introducing a coupled initialization method, improving bounds from roughly γ⁻⁸ to γ⁻² for under-parameterized settings and from n⁴ to n² for over-parameterized settings.
A common method in training neural networks is to initialize all the weights to be independent Gaussian vectors. We observe that by instead initializing the weights into independent pairs, where each pair consists of two identical Gaussian vectors, we can significantly improve the convergence analysis. While a similar technique has been studied for random inputs [Daniely, NeurIPS 2020], it has not been analyzed with arbitrary inputs. Using this technique, we show how to significantly reduce the number of neurons required for two-layer ReLU networks, both in the under-parameterized setting with logistic loss, from roughly $γ^{-8}$ [Ji and Telgarsky, ICLR 2020] to $γ^{-2}$, where $γ$ denotes the separation margin with a Neural Tangent Kernel, as well as in the over-parameterized setting with squared loss, from roughly $n^4$ [Song and Yang, 2019] to $n^2$, implicitly also improving the recent running time bound of [Brand, Peng, Song and Weinstein, ITCS 2021]. For the under-parameterized setting we also prove new lower bounds that improve upon prior work, and that under certain assumptions, are best possible.