Research map / Learning theory and algorithms / Sample complexity
Benign Overfitting in Two-Layer ReLU Convolutional Neural Networks for XOR Data
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 that two-layer ReLU CNNs trained by gradient descent on non-linearly-separable XOR-type data with label noise exhibit a sharp benign/harmful overfitting transition governed by n||mu||^4 vs sigma_p^4 d, using a virtual sequence comparison proof technique.
Problem
Benign overfitting theory has been limited to learning problems whose Bayes-optimal classifier is linear; it is unclear whether overfitting neural networks still generalize well on XOR-type data where linear predictors fail.
Approach
Analyzes two-layer ReLU CNNs on an XOR-type multi-patch data model with label flipping, proving matching upper and lower test-error bounds under gradient descent; introduces "virtual sequence comparison" to handle highly correlated XOR signal patches (cos theta close to 1).
Key results
- Theorem: if n||mu||_2^4 >= C1 sigma_p^4 d, the CNN achieves test error at most p + exp(-C2 n||mu||^4/(sigma_p^4 d)), near Bayes-optimal.
- Theorem: if n||mu||_2^4 <= C3 sigma_p^4 d, test error is at least p + C4, a constant gap from Bayes-optimal.
- Experiments on synthetic data (cos theta=0.8, p=0.1, m=40, T=200) confirm the predicted contour structure of test accuracy in the (sigma_p^4 d/||mu||^4, n) and (n||mu||^4/sigma_p^4, d) spaces.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase the training sample size | Two-layer ReLU CNN · Synthetic XOR-type data | test accuracy | Helped |
| Increase signal strength | Two-layer ReLU CNN · Synthetic XOR-type data | test accuracy | Helped |
| Increase data dimension | Two-layer ReLU CNN · Synthetic XOR-type data | test accuracy | Hurt |
| Use a two-layer ReLU CNN instead of a linear predictor | XOR-type data classification · XOR-type data | test accuracy: 50\% test accuracy for linear predictors | Helped |
| Meet the condition n\|\bmu\|_2^4 >= C_1 \sigma_p^4 d | Two-layer ReLU CNN · XOR-type data, classic XOR regime | test error: R(\Wb^{(T)})\leq p+\exp(-C_2n\|\bmu\|_2^4/(\sigma_p^4d)) | Helped |
| Meet the condition n\|\bmu\|_2^4 <= C_3 \sigma_p^4 d | Two-layer ReLU CNN · XOR-type data, classic XOR regime | test error: R(\Wb^{(T)}) \geq p+C_4 | Hurt |
| Meet the condition \|\bmu\|_2^4(1-\cos\theta)^2\geq \widetilde{\Omega}(m^2\sigma_p^4d) | Two-layer ReLU CNN · XOR-type data, asymptotically challenging XOR regime | test error: R(\Wb^{(T)})\leq p+o(1) | Helped |
| Meet the condition \|\bmu\|_2^4\leq \widetilde{O}(m\sigma_p^4d) | Two-layer ReLU CNN · XOR-type data, asymptotically challenging XOR regime | test error: R(\Wb^{(T)}) \geq p+C | Hurt |
Surprising findings
- Two-layer ReLU CNNs can learn XOR-type data, which no linear predictor can, with sample complexity n = omega(d), better than the omega(d^2) kernel-method requirement cited for 2-sparse parity (informal comparison).
Limitations
- Analysis restricted to two-layer CNNs with fixed second layer and only first-layer training.
- Classic XOR regime requires cos theta < 1/2; the asymptotically challenging regime has a gap between benign and harmful conditions (factor m(1-cos theta)^-2) and requires specific initialization scale.
- Experiments are small synthetic simulations only.
Experimental setup
Datasets: synthetic XOR-type data (Definition of D_XOR with noise patches and label flipping)
Benchmarks: synthetic XOR-type data
Metrics: test error test accuracy training loss
Baselines: linear predictors kernel methods
Builds on: signal-noise decomposition benign overfitting in linear logistic regression two-layer CNN benign overfitting (ReLU^q)
Closest papers by meaning
- Benign Overfitting and Grokking in ReLU Networks for XOR Cluster Data (ICLR 2024 · similarity 0.90)
- Benign overfitting in leaky ReLU networks with moderate input dimension (NeurIPS 2024 · similarity 0.87)
- Benign Overfitting in Adversarial Training of Neural Networks (ICML 2024 · similarity 0.86)
- Simplicity Bias and Optimization Threshold in Two-Layer ReLU Networks (ICML 2025 · similarity 0.86)
- Noisy Interpolation Learning with Shallow Univariate ReLU Networks (ICLR 2024 · similarity 0.86)
- Stable Minima Cannot Overfit in Univariate ReLU Networks: Generalization by Large Step Sizes (NeurIPS 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.