# Provable Benefit of Mixup for Finding Optimal Decision Boundaries

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 34 references that are in the map.
- First posted on arXiv 1 Jun 2023.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (2014)
- [mixup: Beyond Empirical Risk Minimization](https://mlsanity.com/paper/1710.09412/) (2017)
- [CutMix: Regularization Strategy to Train Strong Classifiers with Localizable Features](https://mlsanity.com/paper/1905.04899/) (2019)
- [FixMatch: Simplifying Semi-Supervised Learning with Consistency and Confidence](https://mlsanity.com/paper/2001.07685/) (2020)
- [MixMatch: A Holistic Approach to Semi-Supervised Learning](https://mlsanity.com/paper/1905.02249/) (2019)
- [The Implicit Bias of Gradient Descent on Separable Data](https://mlsanity.com/paper/1710.10345/) (2017)
- [Hard Negative Mixing for Contrastive Learning](https://mlsanity.com/paper/2010.01028/) (2020)
- [On Mixup Training: Improved Calibration and Predictive Uncertainty for Deep Neural Networks](https://mlsanity.com/paper/1905.11001/) (2019)
- [Towards Understanding Ensemble, Knowledge Distillation and Self-Distillation in Deep Learning](https://mlsanity.com/paper/2012.09816/) (2020)
- [Gradient Starvation: A Learning Proclivity in Neural Networks](https://mlsanity.com/paper/2011.09468/) (2020)
- [Puzzle Mix: Exploiting Saliency and Local Statistics for Optimal Mixup](https://mlsanity.com/paper/2009.06962/) (2020)
- [How Does Mixup Help With Robustness and Generalization?](https://mlsanity.com/paper/2010.04819/) (2020)
- [Co-Mixup: Saliency Guided Joint Mixup with Supermodular Diversity](https://mlsanity.com/paper/2102.03065/) (2021)
- [Augmenting Data with Mixup for Sentence Classification: An Empirical Study](https://mlsanity.com/paper/1905.08941/) (2019)
- [On Mixup Regularization](https://mlsanity.com/paper/2006.06049/) (2020)
- [Towards Domain-Agnostic Contrastive Learning](https://mlsanity.com/paper/2011.04419/) (2020)
- [AutoMix: Unveiling the Power of Mixup for Stronger Classifiers](https://mlsanity.com/paper/2103.13027/) (2021)
- [When and How Mixup Improves Calibration](https://mlsanity.com/paper/2102.06289/) (2021)
- [Sub-Gaussian estimators of the mean of a random vector](https://mlsanity.com/paper/1702.00482/) (2017)
- [A Unified Analysis of Mixed Sample Data Augmentation: A Loss Function Perspective](https://mlsanity.com/paper/2208.09913/) (2022)
- [Towards Understanding the Data Dependency of Mixup-style Training](https://mlsanity.com/paper/2110.07647/) (2021)
- [Cross-Entropy Loss and Low-Rank Features Have Responsibility for Adversarial Examples](https://mlsanity.com/paper/1901.08360/) (2019)
- [Mixup-Transformer: Dynamic Data Augmentation for NLP Tasks](https://mlsanity.com/paper/2010.02394/) (2020)
- [Provably Learning Diverse Features in Multi-View Data with Midpoint Mixup](https://mlsanity.com/paper/2210.13512/) (2022)
- [Midpoint Regularization: from High Uncertainty Training to Conservative Classification](https://mlsanity.com/paper/2106.13913/) (2021)

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

- [Tailoring Mixup to Data for Calibration](https://mlsanity.com/paper/2311.01434/) (2023)
- [Provable Benefit of Cutout and CutMix for Feature Learning](https://mlsanity.com/paper/2410.23672/) (2024)
- [For Better or For Worse? Learning Minimum Variance Features With Label Augmentation](https://mlsanity.com/paper/2402.06855/) (2024)
- [Distribution-Aware Robust Learning from Long-Tailed Data with Noisy Labels](https://mlsanity.com/paper/2407.16802/) (2024)
- [RandMSAugment: A Mixed-Sample Augmentation for Limited-Data Scenarios](https://mlsanity.com/paper/2311.16508/) (2023)
- [Exploiting Local Flatness for Efficient Out-of-Distribution Detection](https://mlsanity.com/paper/2606.29952/) (2026)

## Abstract (arXiv)

We investigate how pair-wise data augmentation techniques like Mixup affect the sample complexity of finding optimal decision boundaries in a binary linear classification problem. For a family of data distributions with a separability constant kappa, we analyze how well the optimal classifier in terms of training loss aligns with the optimal one in test accuracy (i.e., Bayes optimal classifier). For vanilla training without augmentation, we uncover an interesting phenomenon named the curse of separability. As we increase kappa to make the data distribution more separable, the sample complexity of vanilla training increases exponentially in kappa; perhaps surprisingly, the task of finding optimal decision boundaries becomes harder for more separable distributions. For Mixup training, we show that Mixup mitigates this problem by significantly reducing the sample complexity. To this end, we develop new concentration results applicable to n2 pair-wise augmented data points constructed from n independent data, by carefully dealing with dependencies between overlapping pairs. Lastly, we study other masking-based Mixup-style techniques and show that they can distort the training loss and make its minimizer converge to a suboptimal classifier in terms of test accuracy.