  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 $n^2$ 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.
