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 \emph{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.
이 논문에서는 믹스업과 같은 데이터 증강 기법이 이진 분류 문제에서 최적의 결정 경계를 찾기 위해 필요한 데이터 수에 어떻게 영향을 미치는지 탐구하였다. 데이터 분리 정도가 분리도 상수 $\kappa$에 의해 매개화 되는 데이터 분포들에 대하여 우리는 훈련 손실함수에 대해 최적인 결정 경계가 테스트 데이터에 대해 최적인 결정 경계와 얼마나 가까운지 분석하였다. 아무런 증강 기법을 사용하지 않는 기본적인 훈련에 대하여 우리는 분리도의 저주라고 부르는 흥미로운 현상을 밝혀냈다. 우리가 분리도 상수 $\kappa$를 증가시켜 데이터 분포의 분리도를 높이면 기본적인 훈련으로 최적의 결정 경계를 찾는 데 필요한 데이터 수의 샘플 복잡도가 $\kappa$에 지수적으로 증가한다. 이는 최적의 결정 경계를 찾는 일은 데이터 분포의 분리도가 높을수록 더 어려워짐을 의미한다. 우리는 믹스업이 데이터 수의 샘플 복잡도를 줄임으로써 이러한 문제를 완화한다는 사실을 증명하였다. 이를 위하여 $n$개의 독립적인 데이터의 쌍들로부터 증강된 $n^2$ 개의 데이터에 대해 적용할 수 있는 새로운 증명 기법을 개발하였다. 마지막으로, 마스킹을 기반으로 하는 믹스업 유형의 기법을 분석하였고, 이들이 훈련 손실 함수를 왜곡하고 최소화해가 최적이 아닌 분류기로 수렴할 수 있음을 보였다.
