Efficient sparse data augmentation cuts transformation cost in machine learning
Sparse Data Augmentation for Optimization with Provable Guarantees
Machine LearningArtificial Intelligence
Summary
When teaching computers using geometric data, it's helpful to include many variations of that data to make the computer's learning more reliable. But checking every single variation can be too slow or costly. The authors show that using a small, carefully chosen set of variations before starting the learning process can almost match the quality of using all variations with fewer steps, saving time and resources. They also provide mathematical guarantees to explain why this approach works well.
What this means in practice
- •For machine learning engineers: Improve training efficiency in geometric learning tasks by reducing costly data transformation computations through sparse augmentation.
- •For computer vision developers: Decrease computational load when applying invariances via data augmentation in image recognition models without sacrificing accuracy significantly.
Authors
Behrooz Tahmasebi, Melanie Weber
Abstract
In nonconvex optimization problems arising in geometric machine learning, data augmentation is commonly used to promote invariance by averaging empirical losses over transformations of the data. Computing the fully augmented objective, however, requires access to every element of the transformation group $G$, which may be prohibitively expensive when $G$ is large or accessible only through sampling. We study whether full augmentation can instead be approximated using a small, fixed sample of transformations acquired before optimization and reused thereafter. Under suitable regularity conditions, we show that, with probability at least $1-δ$, gradient descent (GD) on the resulting sparsely augmented objective returns an $\varepsilon$-stationary point of the fully augmented objective using $\mathcal{O}\bigl((\log |G|+\log(1/δ))/\varepsilon^2\bigr)$ group-transformation-oracle queries. By comparison, standard group stochastic gradient descent (group-SGD), which samples a fresh transformation at every iteration, uses $\mathcal{O}(1/\varepsilon^4)$ transformation queries. Therefore, gradient descent with fixed sparse augmentation requires fewer transformation queries than both GD applied to the fully augmented objective and group-SGD. Our proof techniques, which may be of independent interest, establish a uniform approximation of the full group-averaged gradient field by a random group average using spectral properties of group-induced operators and tools from representation theory.