Tuned Convex Augmentation Beats the Sample It Is Built From

Data-augmentation methods such as SMOTE and mixup create synthetic points as random convex combinations of $K$ real examples. We ask when the resulting synthetic distribution is closer to the data distribution, in Wasserstein distance, than the $n$ real examples it is built from, whose empirical distribution converges at rate $n^{-1/d}$. Mixing nearby points smooths the sample. This reduces fluctuation at the cost of a bias of order $h^2$, where $h$ is the neighbourhood size. For a smooth density bounded away from zero, we prove that $k$-NN SMOTE with tuned $k$ beats $n^{-1/d}$ for every $K\ge 2$ in every dimension $d\ge 3$. Its rate reaches $n^{-2/(d+2)}$ once $K\ge d$, and for a non-flat density on the torus no local mixing scheme with a bias of order $h^2$ can do better. The gain carries over to a finite training set only if synthetic points make up most of it. In experiments, tuned mixing of pairs beats the real sample for $n$ as small as $90$. In full dimension a tuned kernel does better, while on the two manifolds we test mixing beats an isotropic kernel at every sample size and ambient dimension.