Abstract
Parity functions are fundamental benchmarks in machine learning theory, often considered difficult due to their extreme non-linearity and sensitivity to single-bit flips. This paper investigates the learnability of "full parity" functions in neural networks, demonstrating that success is critically dependent on weight initialization. While discrete Rademacher initialization allows gradient descent (GD) to solve the problem in polynomial time, the introduction of Gaussian noise creates an alignment gap that renders learning exponentially difficult. Our findings suggest that the "learnability" of a function is not merely a property of the architecture or the algorithm, but an emergent property of the starting geometry.
Introduction
Parity functions—determining if an unknown subset of input bits contains an even or odd number of ones—are often described as the "white whales" of machine learning theory. They are notoriously difficult for local search algorithms because they lack the "smoothness" found in many natural datasets. While researchers have long understood that "sparse" parities (where only a few bits matter) are learnable, the case for "dense" or "full" parities (where most or all bits matter) has remained a point of theoretical tension.
In the Statistical Query (SQ) framework, full parity is considered trivial to learn. However, in practical settings, standard gradient descent (GD) often fails to converge on a solution. This paper resolves this contradiction by examining the initialization of two-layer and multi-layer ReLU networks, revealing how the choice of starting weights dictates the feasibility of the optimization process.
Methodology
The authors combine rigorous mathematical proofs with empirical simulations to analyze the training dynamics of neural networks. Central to their analysis are two novel concepts:
- Gradient Alignment (GAL): A loss-dependent measure that quantifies the degree to which the initial gradient of the network aligns with the target function relative to random noise.
- Junk-Flow Analysis: A proof technique demonstrating that if the initial alignment is too low, the training dynamics of the network are effectively indistinguishable from training on random, meaningless labels (the "junk flow").
The study contrasts three primary initialization schemes: Rademacher initialization (weights chosen from $\{-1, +1\}$), Gaussian initialization, and $\sigma$-perturbed Rademacher (discrete weights with added Gaussian noise). These are tested on synthetic benchmarks using uniform Boolean inputs sampled from $\{ \pm 1 \}^d$, where the target is the full parity function $\chi_d(x) = \prod_{i=1}^d x_i$.
The Geometry of Initialization
The Rademacher "Cheat Code"
The research reveals that Rademacher initialization provides a specific structural advantage. With these discrete weights, the hidden layer embeddings of the parity function become linearly separable with high probability. This structural alignment allows GD to find the solution in polynomial time ($poly(d)$), effectively bypassing the complexity usually associated with high-degree parities.
The Gaussian Barrier
Conversely, Gaussian initialization spreads weights in a manner that "washes out" the parity signal. The authors prove that with Gaussian weights, the initial gradient alignment is exponentially small ($exp(-\Omega(d))$). Consequently, the network begins in an exceptionally flat region of the loss landscape, where it cannot find a meaningful direction for improvement. In this regime, any network with a linear output layer trained via noisy-GD requires an exponential number of steps to perform better than random guessing.
The Fragility of Success
The success of discrete initialization is remarkably brittle. The authors found that adding Gaussian noise with a standard deviation $\sigma$ as small as a constant is enough to trigger the negative result. There appears to be a sharp phase transition around $\sigma = O(d^{-1})$, where the problem shifts from being computationally easy to exponentially hard.
Empirical Results
Experiments on a 4-layer Multi-Layer Perceptron (MLP) confirmed these theoretical predictions. As the perturbation noise $\sigma$ increased, the test accuracy after training dropped sharply from 100% to 50% (random chance). This empirical evidence supports the claim that the interaction between the optimization algorithm and the starting geometry is the primary determinant of success in learning high-degree parities.
Discussion and Limitations
While this work provides a significant step forward in understanding the optimization of non-linear functions, several questions remain. The most rigorous negative results are currently tied to the correlation loss. While experiments show similar behavior with the hinge loss, a full theoretical proof for the latter remains an open challenge. Additionally, while the paper identifies the existence of a noise threshold $\sigma$, the exact characterization of this phase transition is not yet fully defined. Future work may also extend the "Gradient Alignment" theory to deeper architectures to see if depth can mitigate or exacerbate these initialization effects.
Summary updated