  Though data augmentation has rapidly emerged as a key tool for optimization
in modern machine learning, a clear picture of how augmentation schedules
affect optimization and interact with optimization hyperparameters such as
learning rate is nascent. In the spirit of classical convex optimization and
recent work on implicit bias, the present work analyzes the effect of
augmentation on optimization in the simple convex setting of linear regression
with MSE loss.
  We find joint schedules for learning rate and data augmentation scheme under
which augmented gradient descent provably converges and characterize the
resulting minimum. Our results apply to arbitrary augmentation schemes,
revealing complex interactions between learning rates and augmentations even in
the convex setting. Our approach interprets augmented (S)GD as a stochastic
optimization method for a time-varying sequence of proxy losses. This gives a
unified way to analyze learning rate, batch size, and augmentations ranging
from additive noise to random projections. From this perspective, our results,
which also give rates of convergence, can be viewed as Monro-Robbins type
conditions for augmented (S)GD.
