  While deep neural networks show great performance on fitting to the training
distribution, improving the networks' generalization performance to the test
distribution and robustness to the sensitivity to input perturbations still
remain as a challenge. Although a number of mixup based augmentation strategies
have been proposed to partially address them, it remains unclear as to how to
best utilize the supervisory signal within each input data for mixup from the
optimization perspective. We propose a new perspective on batch mixup and
formulate the optimal construction of a batch of mixup data maximizing the data
saliency measure of each individual mixup data and encouraging the supermodular
diversity among the constructed mixup data. This leads to a novel discrete
optimization problem minimizing the difference between submodular functions. We
also propose an efficient modular approximation based iterative submodular
minimization algorithm for efficient mixup computation per each minibatch
suitable for minibatch based neural network training. Our experiments show the
proposed method achieves the state of the art generalization, calibration, and
weakly supervised localization results compared to other mixup methods. The
source code is available at https://github.com/snu-mllab/Co-Mixup.
