Bounding the Width of Neural Networks via Coupled Initialization -- A Worst Case Analysis
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 $\gamma^{-8}$ [Ji and Telgarsky, ICLR 2020] to $\gamma^{-2}$, where
$\gamma$ 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.