Learning High-Degree Parities: The Crucial Role of the Initialization
Emmanuel Abbe Elisabetta Cornacchia Jan Hązła Donald Kougang-Yombi
Parities have become a standard benchmark for evaluating learning algorithms. Recent works show that regular neural networks trained by gradient descent can efficiently learn degree $k$ parities on uniform inputs for constant $k$, but fail to do so when $k$ and $d-k$ grow with $d$ (here $d$ is the ambient dimension). However, the case where $k=d-O_d(1)$, including the degree $d$ parity (the \textit{full parity}), has remained unsettled. This paper shows that for gradient descent on regular neural networks, learnability depends on the initial weight distribution. On one hand, the discrete Rademacher initialization enables efficient learning of full parities, while on the other hand, its Gaussian perturbation with large enough constant standard deviation $\sigma$ prevents it. The positive result for full parity is shown to hold up to $\sigma=O(d^{-1})$, pointing to questions about a sharper threshold phenomenon. Unlike statistical query (SQ) learning, where a singleton function class like the full parity is  trivially learnable, our negative result applies to a fixed function and relies on an \emph{initial gradient alignment} measure of potential broader relevance to neural networks learning.
initialization, neural networks, gradient descent, parity functions, complexity, initial alignment