# Benign Overfitting in Two-Layer ReLU Convolutional Neural Networks for XOR Data

arXiv: https://arxiv.org/abs/2310.01975 · HTML: https://mlsanity.com/paper/2310.01975/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 35 references that are in the map.
- First posted on arXiv 3 Oct 2023.

## Builds on (most cited first, 25 of 25)

- [Reconciling modern machine learning practice and the bias-variance trade-off](https://mlsanity.com/paper/1812.11118/) (2018)
- [Benign Overfitting in Linear Regression](https://mlsanity.com/paper/1906.11300/) (2019)
- [Surprises in High-Dimensional Ridgeless Least Squares Interpolation](https://mlsanity.com/paper/1903.08560/) (2019)
- [The generalization error of random features regression: Precise asymptotics and double descent curve](https://mlsanity.com/paper/1908.05355/) (2019)
- [Two models of double descent for weak features](https://mlsanity.com/paper/1903.07571/) (2019)
- [Benign overfitting in ridge regression](https://mlsanity.com/paper/2009.14286/) (2020)
- [Towards Understanding the Role of Over-Parametrization in Generalization of Neural Networks](https://mlsanity.com/paper/1805.12076/) (2018)
- [Regularization Matters: Generalization and Optimization of Neural Nets v.s. their Induced Kernel](https://mlsanity.com/paper/1810.05369/) (2018)
- [On the Optimal Weighted ℓ2 Regularization in Overparameterized Linear Regression](https://mlsanity.com/paper/2006.05800/) (2020)
- [Benign Overfitting in Two-layer Convolutional Neural Networks](https://mlsanity.com/paper/2202.06526/) (2022)
- [The Interpolation Phase Transition in Neural Networks: Memorization and Generalization under Lazy Training](https://mlsanity.com/paper/2007.12826/) (2020)
- [Finite-sample Analysis of Interpolating Linear Classifiers in the Overparameterized Regime](https://mlsanity.com/paper/2004.12019/) (2020)
- [Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networks](https://mlsanity.com/paper/1910.01619/) (2019)
- [Benign Overfitting without Linearity: Neural Network Classifiers Trained by Gradient Descent for Noisy Linear Data](https://mlsanity.com/paper/2202.05928/) (2022)
- [Benign Overfitting of Constant-Stepsize SGD for Linear Regression](https://mlsanity.com/paper/2103.12692/) (2021)
- [A Random Matrix Analysis of Random Fourier Features: Beyond the Gaussian Kernel, a Precise Phase Transition, and the Corresponding Double Descent](https://mlsanity.com/paper/2006.05013/) (2020)
- [Classifying high-dimensional Gaussian mixtures: Where kernel methods fail and neural networks succeed](https://mlsanity.com/paper/2102.11742/) (2021)
- [Risk Bounds for Over-parameterized Maximum Margin Classification on Sub-Gaussian Mixtures](https://mlsanity.com/paper/2104.13628/) (2021)
- [Towards Understanding Hierarchical Learning: Benefits of Neural Representations](https://mlsanity.com/paper/2006.13436/) (2020)
- [Spectrum of inner-product kernel matrices in the polynomial regime and multiple descent phenomenon in kernel ridge regression](https://mlsanity.com/paper/2204.10425/) (2022)
- [Precise Learning Curves and Higher-Order Scaling Limits for Dot Product Kernel Regression](https://mlsanity.com/paper/2205.14846/) (2022)
- [A Random Matrix Perspective on Mixtures of Nonlinearities for Deep Learning](https://mlsanity.com/paper/1912.00827/) (2019)
- [Feature selection with gradient descent on two-layer networks in low-rotation regimes](https://mlsanity.com/paper/2208.02789/) (2022)
- [Deep Linear Networks can Benignly Overfit when Shallow Ones Do](https://mlsanity.com/paper/2209.09315/) (2022)
- [Per-Example Gradient Regularization Improves Learning Signals from Noisy Data](https://mlsanity.com/paper/2303.17940/) (2023)

## Built on by (most cited first, 10 of 10)

- [Overfitting Behaviour of Gaussian Kernel Ridgeless Regression: Varying Bandwidth or Dimensionality](https://mlsanity.com/paper/2409.03891/) (2024)
- [Provably Neural Active Learning Succeeds via Prioritizing Perplexing Samples](https://mlsanity.com/paper/2406.03944/) (2024)
- [Provable Tempered Overfitting of Minimal Nets and Typical Nets](https://mlsanity.com/paper/2410.19092/) (2024)
- [When Are Bias-Free ReLU Networks Effectively Linear Networks?](https://mlsanity.com/paper/2406.12615/) (2024)
- [On the Role of Label Noise in the Feature Learning Process](https://mlsanity.com/paper/2505.18909/) (2025)
- [Scanning Trojaned Models Using Out-of-Distribution Samples](https://mlsanity.com/paper/2501.17151/) (2025)
- [Understanding the Benefits of SimCLR Pre-Training in Two-Layer Convolutional Neural Networks](https://mlsanity.com/paper/2409.18685/) (2024)
- [Linearly Separable Features in Shallow Nonlinear Networks: Width Scales Polynomially with Intrinsic Data Dimension](https://mlsanity.com/paper/2501.02364/) (2025)
- [Gradient Descent Robustly Learns the Intrinsic Dimension of Data in Training Convolutional Neural Networks](https://mlsanity.com/paper/2504.08628/) (2025)
- [The Conflict Between Logic and Memory: Training Conditions for Optimizer-Dependent Rule Acquisition](https://mlsanity.com/paper/2610.00403/) (2026)

## Abstract (arXiv)

Modern deep learning models are usually highly over-parameterized so that they can overfit the training data. Surprisingly, such overfitting neural networks can usually still achieve high prediction accuracy. To study this "benign overfitting" phenomenon, a line of recent works has theoretically studied the learning of linear models and two-layer neural networks. However, most of these analyses are still limited to the very simple learning problems where the Bayes-optimal classifier is linear. In this work, we investigate a class of XOR-type classification tasks with label-flipping noises. We show that, under a certain condition on the sample complexity and signal-to-noise ratio, an over-parameterized ReLU CNN trained by gradient descent can achieve near Bayes-optimal accuracy. Moreover, we also establish a matching lower bound result showing that when the previous condition is not satisfied, the prediction accuracy of the obtained CNN is an absolute constant away from the Bayes-optimal rate. Our result demonstrates that CNNs have a remarkable capacity to efficiently learn XOR problems, even in the presence of highly correlated features.