Introduction
In classical statistical learning theory, overfitting is typically viewed as a failure of generalization. However, modern deep learning practice frequently encounters two counterintuitive phenomena: benign overfitting, where models generalize well despite fitting noisy training data perfectly, and grokking, where a model suddenly transitions from random guessing to near-perfect generalization long after it has achieved zero training error.
While these behaviors have been observed empirically, theoretical explanations have largely been confined to linear models or linearly separable datasets. A recent study by Xu et al. provides a rigorous theoretical bridge by proving that two-layer ReLU networks can exhibit both benign overfitting and grokking simultaneously on a non-linearly separable classification task: the XOR cluster problem.
The XOR Cluster Problem and Label Noise
The authors analyze a synthetic XOR Cluster Data distribution in a high-dimensional setting ($p \gg n$). The data consists of four clusters centered at $\pm\mu_1$ and $\pm\mu_2$, where the cluster means are orthogonal. This geometry ensures the task is fundamentally non-linear; a simple linear classifier cannot separate the classes. To study overfitting, the researchers introduce label noise by randomly flipping a fraction $\eta$ of the training labels.
Methodology: Trajectory Analysis of Neurons
The study focuses on a two-layer ReLU network trained via Gradient Descent (GD) on a logistic loss function without explicit regularization. The core of the proof lies in a trajectory analysis of individual neurons, divided into two distinct phases:
- The Linear Phase (Step 1): Immediately after initialization, the network behaves like a high-dimensional linear classifier. In this phase, it uses its high capacity to memorize specific training points, including noisy ones, but fails to capture the underlying XOR structure.
- The Feature Learning Phase (Later Steps): As training continues, the implicit regularization of GD causes neurons to align with the cluster means (the "core features"). This alignment allows the network to learn the global structure of the data.
Results: From Memorization to Grokking
The theoretical results confirm a dramatic transition in model performance. Initially, the network achieves 100% training accuracy almost immediately (at $t=1$) but remains at roughly 50% test accuracy—no better than random guessing. This represents catastrophic overfitting where the model has memorized the noise but learned no features.
As training progresses beyond a certain threshold (the "grokking point"), the test error drops exponentially toward zero. Crucially, the model maintains its 100% training accuracy throughout this process. It never "unlearns" the noisy labels; instead, it learns the global features on top of the initial memorization, demonstrating that overfitting can be benign even in non-linear settings.
Feature Alignment and Decision Boundaries
The transition from the linear phase to the feature learning phase is reflected in the network's decision boundaries. Initially, the boundary is a simple hyperplane that cannot solve the XOR task. After grokking, the network develops the complex, non-linear boundaries required to correctly classify the four clusters.
Conclusion and Implications
This work provides the first theoretical proof of simultaneous benign overfitting and grokking in ReLU networks for non-linearly separable data. It suggests that grokking is not merely a curiosity of specific datasets but a fundamental stage in the learning trajectory of neural networks where feature learning eventually overcomes initial memorization. While the current analysis is limited to two-layer networks in high dimensions, it sets a theoretical foundation for understanding how complex models navigate the tension between fitting noise and learning structure.
Summary updated