Research map / Optimization / Implicit bias and generalization

Benign Overfitting and Grokking in ReLU Networks for XOR Cluster Data

ICLR 2024 · Optimization › Implicit bias and generalization · approach: Shallow ReLU network convergence · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows theoretically that two-layer ReLU networks trained by GD on noisy XOR cluster data exhibit catastrophic overfitting after one step, then grokking into benign overfitting (near-zero test error while still fitting noisy labels).

Problem

Explaining benign overfitting and grokking provably in neural network classification on non-linearly separable data, where prior benign overfitting theory required linearly separable distributions and grokking lacked rigorous neural network proofs.

Approach

Analyzes feature learning of a two-layer ReLU network under GD on XOR cluster data with label flipping: after one step the network behaves like a linear classifier that memorizes all training points but fails to generalize, and later steps gradually align neurons with the cluster means, yielding generalization while the training labels remain fit.

Key results

• After one GD step the network reaches 100% training accuracy but test error is near 1/2 (random), per the one-step catastrophic overfitting result.
• For Cn^{0.01} <= t <= sqrt(n) the network keeps fitting training data while test error is at most exp(-Omega(n^{0.99}||mu||^4/p)) = exp(-Omega(n^{2.01})), i.e. benign overfitting via grokking.
• Simulations over 100 independent runs show benign overfitting when step size is larger than initialization scale and grokking when it is smaller.

Measured effects reported in the paper

Surprising findings

• Grokking occurs without any explicit regularization such as weight decay, attributed to implicit regularization of GD.
• Unlike prior linearly separable benign overfitting results, catastrophic overfitting precedes benign overfitting with a time separation.

Limitations

• Analysis only holds for training times up to sqrt(n); behavior as t goes to infinity is open.
• Requires high dimensionality so training points are near-orthogonal (p >= C n^2 ||mu||^2).
• Results are for a specific synthetic XOR cluster distribution with two-layer ReLU network and fixed second-layer weights.

Experimental setup

Datasets: synthetic noisy XOR cluster data

Benchmarks: synthetic XOR cluster data

Metrics: train accuracy test error under clean distribution

Baselines: Kou et al. early-stopped ReLU network analysis

Builds on: benign overfitting in two-layer networks (Frei et al.) XOR cluster data (Kou et al.) catastrophic/benign/tempered overfitting taxonomy (Mallinar et al.)

Closest papers by meaning

• Benign Overfitting in Two-Layer ReLU Convolutional Neural Networks for XOR Data (ICML 2024 · similarity 0.90)
• Benign overfitting in leaky ReLU networks with moderate input dimension (NeurIPS 2024 · similarity 0.89)
• Stable Minima Cannot Overfit in Univariate ReLU Networks: Generalization by Large Step Sizes (NeurIPS 2024 · similarity 0.88)
• Simplicity Bias and Optimization Threshold in Two-Layer ReLU Networks (ICML 2025 · similarity 0.88)
• Grokking at the Edge of Numerical Stability (ICLR 2025 · similarity 0.88)
• Grokking as the transition from lazy to rich training dynamics (ICLR 2024 · similarity 0.88)