Data augmentation as stochastic optimization
Authors: Boris Hanin
Yi Sun
Venue:  (2021)
Keywords: data augmentation
stochastic optimization
scheduling
convex optimization
overparametrization

Abstract: We present a theoretical framework recasting data augmentation as stochastic optimization for a sequence of time-varying proxy losses. This provides a unified language for understanding techniques commonly thought of as data augmentation, including synthetic noise and label-preserving transformations, as well as more traditional ideas in stochastic optimization such as learning rate and batch size scheduling. We then specialize our framework to study arbitrary augmentations in the context of a simple model (overparameterized linear regression). We extend in this setting the classical Monro-Robbins theorem to include augmentation and obtain rates of convergence, giving conditions on the learning rate and augmentation schedule under which augmented gradient descent converges. Special cases give provably good schedules for augmentation with additive noise, minibatch SGD, and minibatch SGD with noise.

Under review as a conference paper at ICLR 2021
DATA AUGMENTATION AS STOCHASTIC OPTIMIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
We present a theoretical framework recasting data augmentation as stochastic op- timization for sequence of time-varying proxy losses. This provides unified language for understanding techniques commonly thought of as data augmenta- tion, including synthetic noise and label-pres transformations, more traditional ideas in stochastic optimization such as learning rate and batch size scheduling. We then specialize our framework study arbitrary augmen- tations in the context of a simple model (overparameterized linear regression). We extend in this setting the classical Monro-Robbins theorem to include aug- mentation and obtain rates of convergence, giving conditions on the learning rate and augmentation schedule under which augmented gradient descent converges. Special cases give provably good schedules for augmentation with additive noise, minibatch SGD, and minibatch SGD with noise.
well
INTRODUCTION
Implementing gradient-based optimization in practice requires many choices. These include set- ting hyperparameters such as learning rate and batch size as well as specifying a data augmentation scheme, popular set of techniques in which data is augmented (i.e. modified) at every step of opti- mization. Trained model quality is highly sensitive to these choices. In practice they are made using methods ranging from simple grid search to Bayesian optimization and reinforcement learning CCuuuk et al. 2019: 2020 Ho et al., 2019). Such approaches, while effective, are often ad-hoc and computationally expensive due to the need to handle scheduling, which optimization hyperparam- eters and augmentation choices and strengths chosen to change over the course of optimization.
These empirical results stand in contrast to theoretically grounded approaches to stochastic optimiza- tion which provide both provable guarantees and reliable intuitions. The most extensive work in this direction builds on the seminal article (Robbins & Monro 1951). which gives provably optimal learning rate schedules for stochastic optimization of strongly convex objectives. While rigorous, these approaches are typically are not sufficiently flexible to address the myriad augmentation types and hyperparameter choices beyond learning rates necessary in practice.
This article is a step towards bridging this gap. We provide in $ rigorous framework for re- interpreting gradient descent with arbitrary data augmentation as stochastic gradient descent time-varying sequence of objectives. This provides unified language to study traditional stochas- tic optimization methods such minibatch SGD together with widely used augmentations such as additive noise (Grandvalet & Canu 1997), CutOut Vrees & Taylor 2017). Mixup (Zhang et al.) 2017) and label-preserving transformations (e.g. color jitter, geometric transformations (Simard) al. 2003)). It also opens the door to studying how to schedule and evaluate arbitrary augmenta- tions, an important topic given the recent interest learned augmentation Cubuk et al. (2019).
Quantitative results in our framework are difficult to obtain in full generality due to the complex interaction between models and augmentations. To illustrate the utility of our approach and better understand specific augmentations, we present in } and results about arbitrary augmentations for overparameterizee linear regression and specialize to additive noise and minibatch SGD in $4 and (6 While results apply directly only simple quadratic losses, they treat very general Treating more complex models is left to future work. Our main contributions are:
augmentations.
In Theorem 5.I. we give sufficient conditions under which gradient descent under any aug- mentation scheme converges in the setting of overparameterized linear regression. Our

---

Under review as a conference paper at ICLR 2021
result extends classical results of Monro-Robbins type and covers schedules for both learn- ing rate and data augmentation scheme.
We complement the asymptotic results of Theorem 5.1 with quantitative rates of conver- gence furmished in Theorem [.2]] These rates depend only on the first few moments of the augmented data distribution, underscoring the flexibility of our framework.
In $4 we analyze additive input noise, popular augmentation strategy for increasing model robustness. We recover the known fact that it is equivalent to stochastic optimization with fz-regularization and find criteria in Theorem 4.1 for jointly scheduling the learning rate and noise level to provably recover the minimal norm solution.
66 we analyze minibatch SGD, recovering known results about rates of convergence for SGD (Theorem 6.1 and novel results about SGD with noise (Theorem 6.2
2 RELATED WORK
In addition to the extensive empirical work on data augmentation cited elsewhere in this article, we briefly catalog other thcoretical work on data augmentation and learning rate schedules. The latter were first considered in the seminal work Robbins & Monro (195I). This spawned vast literature on rates of convergence for GD, SGD, and their variants. We mention only the relatively recent articles Bach & Moulines (2013); Défossez & Bach (2015); Bottou al. (201 8); (Smihh et al.) (2018) Ma et al. (2018) and the references therein. The last of these, namely Ma et al. (2018). finds optimal choices of learning rate and batch size for SGD in the overparametrized linear setting.
A number of articles have also pointed out in various regimes that data augmentation and more gen- eral transformations such feature dropout correspond in part to fy-type regularization model parameters, features, gradients, and Hessians. The first article of this kind of which we are aware is Bishop 1995), which treats the case of additive Gaussian noise (see 44) More recent work in this direction includes includessChapelle et al. (200T): Wager et al. (2.13) LeJeune et al. (2019) et al. (2020). There are also several articles investigating optimal choices of (zrreullarizztion for linear models (cf e.g. WW et al. (2018); Wu & Xu (2020); [Battlttt et al. (2020). These articles focus directly on the generalization effects of
minima but not on the dynamics of optimization. We also point the reader to Lewkowycz & Gur-Ari (2020), which considers optimal choices for the weight decay coefficient empirically in neural networks and analytically in simple models.
We also refer the reader to number of recent attempts to characterize the benefits of data augmenta- tion. In Rajput et al. (2019), for example, the authors quantify how much augmented data, produced via additive noise, is needed to learn positive margin classifiers. Chen et al. (2019), in contrast, focuses on the case of data invariant under the action label-preserving augmentations, the authors prove that the variance of any function depending only on the trained model will decrease. This applics in particular to estimators for the trainable parame- ters themselves. Dao et al. (2019) shows augmented k-NN classification reduces to kernel method for augmentations transforming each datapoint to a finite orbit of possibilities. It also gives a second order expansion for the proxy loss of kernel method under such augmentations and interprets how each term affects generalization. Finally, the article Wu et al. (2020) considers both label preserving and noising augmentations, pointing out the conceptually distinct roles such augmentations play.
group. Using the group action to generate
DATA AUGMENTATION AS STOCHASTIC OPTIMIZATION
A common task in modern machine learning is the optimization of empirical risk Σ
C(W: D)
(lflz;W),u))
(3.1)
D
(ED
where f(x; W) is a parameterized model for a dataset D of input-response pairs (a, y) and & is a per-sample loss. Optimizing W by vanilla gradient descent on L corresponds to the update equation
W = W. Nte V L(W;; D).
In this context, we define a data augmentation scheme to be any procedure that consists, at every step of optimization, of replacing the dataset D by randomly augmented variant, which we will denote
2

---

Under review as a conference paper at ICLR 2021
by Dr. Typically, Dj is related to D in some way, but our framework does not explicitly constrain the form of this relationship. Instead, certain conditions on this relationship will be required for our main results Theorems 5.1 and 5.2 to give useful results for a specific augmentation scheme. A data augmentation scheme therefore corresponds to the augmented update equation
W++1 W - 7/e W LWW;; D,).
(3.2)
Since Dj is stochastic function of D. it natural view the augmented update rule 3.2 as form of stochastic optimization for the proxy loss at time t
(W) == ED, [c)]
(3.3)
The update 3.2) corresponds precisely to stochastic optimization for the time-varying objective (WW) in which the unbiased estimate of its gradient is obtained by evaluating the gradient of C(W;Dy) on a single sample Dr drawn from the augmentation distribution. The connection between data augmentation and this proxy loss introduced for Gaussian noise in Bishop (1995) and in general in Chapelle et al. (2001), but we now consider it in the context of stochastic optimization.
Despite being mathematically straightforward, reformulating data augmentation stochastic opti- mization provides a unified language for questions about learning rate schedules and general aug- mentation schemes including SGD. In general, such questions can be challenging answer, and even evaluating the proxy loss (WW) may require significant ingenuity.
While will return to sophisticated models in future work, henceforth analyze general augmentations in the simple context of overparameterized linear regression. Though there are many ways to perform linear regression, we restrict augmented gradient descent both to gain intuition about specific augmentations and to understand the effect of augmentation on optimization. We therefore consider optimizing the entries of a weight matrix W RPx" by gradient descent on
<WW; D) =
Σ lly - Wxll (a.N)ED
I|Y WXI N
1
(3.4)
where dataset D is summarized by data matrices X E REXN and Y RPXN, whose N < columns consist of inputs x; E IR." and associated labels y/ E IRP. Following this notation, a data augmentation scheme is specified by prescribing at each time step an augmented dataset D, consisting of modified data matrices Xx, Y, whose columns we denote by Tiat E R" and yi E IRP. Here, the number of columns in X₁ and Y, (i.e. the number of datapoints in D:) may vary.
We now give examples of some commonly used augmentations our framework can address.
Additive Gaussian noise: This is implemented by setting X, X + or and Y, Y for o, > and G a matrix of i.i.d. standard Gaussians. We analyze this in $4
Mini-batch SGD: To implement mini-batch SGD with batch size Br, can take X, XA, and Y; YA, where A₁ E N Br has i.i.d. columns containing single non-zero entry equal chosen uniformly random. We analyze this detail in {
Random projection: This is implemented by X; = 11,X and Y, Y, where II, is an orthogonal projection onto a random subspace. For 7/- = Tr(l))/m, n,, the proxy loss is
(W) = ||Y - 7 WX + 7e 7) Tr(XX [W] + 0(x
which adds a data-dependent &, penalty and applies a Stein shrinkage on input data.
Label-preserving transformations: For 2-D image viewed vector R" geomet- ric transforms (with pixel interpolation) or other label-preserving transforms such as color jitter take the form of linear transforms R. -> R... We may implement such augmentations in our framework by X, A,X and Y, Y for some random transform matrix Ar.
Mixup: To implement Mixup, we can take X, = X A, and Y, = Y A,, where A₁ E R Nx has i.i.d. columns containing with two random non-zero entries equal to 1 ct and o with mixing coefficient drawn from a Beta (r,, a;) distribution for parameter a;
Our main technical results, Theorems 5.1 and 5.2 give sufficient conditions for a learning rate schedule 7), and a schedule for the statistics of X,, Y, under which optimization with augmented gradient descent will provably converge. We state these general results in $5 Before doing so, seck to demonstrate both the utility of our framework and the flavor of our results by focusing on the simple but already informative case of additive Gaussian noise.
3

---

Under review as a conference paper at ICLR 2021
4 AUGMENTATION WITH ADDITIVE GAUSSIAN NOISE
An common augmentation in practice injects input noise as a regularizer (Grandvalet & Canu 1997):
D, = { wr.r), i = 1,...,N), N). F3 = xz + Ftgitt
yi,t
where Ii.t are i.i.d. standard Gaussian vectors and og is a strength parameter. This section studies such augmentations using our framework. A direct computation reveals that the proxy loss
Z.WW) = L., (W) = L(W; + of 1|W1
corresponding to additive Gaussian noise adds an l2-penalty to the original loss L. This is simple but useful intuition. It also raises the question: what is the optimal relation between the learning rate ?) and the augmentation strength oe (i.e. the ?2-penalty)?
To get sense of what optimal might mean in this context, observe first that if or 0, then directly differentiating the loss yields the following update rule:
2n (Y WxX)xx.
W4+1 W
(4.1)
The increment W4+1 W2 therefore contained in the column span
== column span of Xx C F."
(4.2)
of the model Hessian X.x.. Overparameterization implies Vi * R". The component W.,1 of W. that is in the orthogonal complement of VIi thus remains frozen to its initialized value. Geometrically, this means that there are some directions, namely those in the orthogonal complement ViJ. which gradient descent "cannot see." Optimization with appropriate step sizes then yields
lim W, - + W min:
W min := (XXTxx
where Wmin is the minimum norm solution of Y WX. The original motivation for introducing the fz-regularized losses La is that they provide mechanism to eliminate the component Wo, for all initializations, not just the special choice Wo = O, and they can be used to regularize non-linear models as well. Indeed, for > 0, the loss C. is strictly convex and has unique minimum
W = YXT (XxT +o2 Idwxn)
which tends to the minimal norm solution in the weak regularization limit lim W = Wmin- Geometrically, this is reflected in the fact that f2-penalty yields non-trivial gradient updates
WTLL1 = W - W = =(Id -Id- --mo =
II (Id noo Wo...
(4.3)
which drive this perpendicular component of W, to zero provided E 1/1 co. However, for each positive value of a, the f2-penalty also modifies the gradient descent updates for W.,ji ultimately causing W, to converge to W,, which is not minimizer of the original loss L.
This downside of ridge regression motivates jointly scheduling the step size 7) and the noise strength dr. We hope that driving to 0 at an appropriate rate can guarantee convergence of W. to Wmin- Namely, we want to retain the regularizing effects of fy-noise to force WT_ to zero while mitigating its adverse effects which prevent W from minimizing L. It turns out that this is indeed possible:
Theorem 4.1 (Special case of Theorem 5.1
Suppose of 1)e + 0 with of non-increasing and
Σ t=0
no? = 0
and Σ ni < 00. 2=
(4.4)
Then, We 2, Wmin- Further, if th = ()==a and of = 0) with x, > 0, x + y < 1, and
2r + y > 1, then for any e E (0, min 2/22),, we have that
minnty ]=]= I,,, Wminll || 2, 0.
4

---

Under review as a conference paper at ICLR 2021
Let us give a few comments Theorem 4.1 an analogous version holds for arbitrary additive noise with bounded moments, with the only change being constant multiplicative factor in the second condition of (4.4).
First, although it is stated for additive Gaussian noise,
Second, that convergence in probability W, P Wmin follows from (4.4 analogous to a Monro- Robbins type theorem (Robbins & Monro 1951). Indeed, inspecting (4.3). we see that the first condition in (4.4) guarantees that effective learning rate 17:0द in the orthogonal complement to Vi is sufficiently large that the corresponding component W,, of W, tends to O, allowing the result of optimization to be independent of the initial condition Wo. Further, the second condition in (4.4) guarantees that the variance of the gradients, which at time & scales like of is summable. As in the usual Monro-Robbins setup, this means that only a finite amount of noise is injected into the optimization. Further, (.44) is direct specialization of (5.5) and (5.6) from Theorem 5.1
Third, by optimizing over I. y, we see that fastest rate convergence guaranteed by Theorem 4.1 obtained by setting '/2 12/+++ of 1-1/3 and results in a O(t-1/3te) rate of convergence. not evident that this is the best possible rate, however.
Finally, although we leave systemic study of augmentation in non-linear models to futurre work, our framework can be applied beyond linear models and quadratic losses. To see this, noted for kernels in Dao et al. (2019), augmenting inputs of nonlinear feature models correspond to applying different augmentations on the outputs of the feature map. To give concrete example, consider additive noise for small o, For any sufficiently smooth function y, Taylor expansion reveals
ot oi A((=))
[g(( o,G =9(x)=
where = E, 0f is the Laplacian and G is standard Gaussian vector. For a general loss of the have
form 3.1
I,WW = L(W; + 2
Σ Tr (/V= (2,gED)
where we have written H for the Hessian of some convex per-sample loss É with respect to and Vz. v for the gradients with respect x, f. respectively. This is consistent with the similar expansion done in the kernel setting by Dao et al. (2019) Section 4). If a, is small, then the proxy loss L, will differ significantly from the unaugmented loss L only we expect v to be small and H E to be positive semi-definite. Hence, we find heuristically that, neglecting higher order terms in or. additive noise with small o; corresponds an fz-regularizer
the end of training, when
a (V.)) (HI =: of IV 2
Tr
for the gradients of f with respect to the natural inner product determined by the Hessian of the loss. This is intuitive since penalizing the gradients of f is the same requiring that f is approximately constant in neighborhood of every datapoint. However, although the input noise was originally isotropic, the & f2-penalty is aligned with the loss Hessian and hence need not be.
5 TIME-VARYING MONRO-ROBBING FOR LINEAR MODELS UNDER AUGMENTATION
In this section, we state two general results, Theorems 5.1 and 5.2 which provide sufficient condi- tions for jointly scheduling learning rates and general augmentation schemes to guarantee conver- gence of augmented gradient descent in the overparameterized linear model (3.4).
5.1 A GENERAL VARYING MONRO-ROBENE THEOREM
Given an augmentation scheme for the model
3.4b. the time gradient update at learning rate T) is
2m (Y: W.X.XXT.
W = W.+
(5.1)
N
5

---

Under review as a conference paper at ICLR 2021
where D. (X,, Yi) is the augmented dataset at time t. The minimum minimizer of the corresponding proxy loss C, (see 3.3 is
W
(5.2)
where I denotes the Moore-Penross, pseudo-inverse In this section state rigorous result, Theorem 5.1 giving sufficient conditions on the learning rate ÿ and distributions of the augmented matrices Xz, Yr under which augmented gradient descent converges. In analogy with the case of Gaussian noise, (5.1) shows W++1 W, is contained in the column span of the Hessian X of the augmented loss and almost surely belongs the subspace
V == column span of E[X,X,] R
(5.3)
To ease notation, we assume that Vi is independent of f. This assumption is valid for additive Gaussian noise, random projection, MixUp, SGD, and their combinations. We explain in Remark B.2 how to generalize Theorems 5.1 and 5.2 the case where Vi varies with t.
Let us denote by Q R" + R" the orthogonal projection onto VII. At time 6, gradient descent leaves the projection WId 1Q1) of W, onto the orthogonal complement of Vi unchanged. In contrast, || W decreases at a rate governed by the smallest positive eigenvalue
Amin, (E [X,X,) == Amin (Q X Q11
of the Hessian for the proxy loss Le, which is obtained by restricting its full Hessian E XX to Vi. Moreover, whether and at what rate W₂Q W2 converges to 0 must depend on how quickly
E
W - W
(5.4)
tends to zero. Indeed, ,| is the distance between proxy loss optima at different times and hence must tend to zero if [| W converges to zero.
Theorem 5.1. Suppose that V1 is independent of t, that the learning rate satisfies + 0, that the proxy optima satisfy
E F < <0,
(5.5)
ensuring the existence of a limit W = lim Wi, and that
Tt Ammmi Vi (E[X,X]1) = 00.
(5.6)
If either
<0
(5.7)
t=0
or the more refined condition
E
X
E[XxX]) (MX---E))) -EXTTEEXX,IDI <0
(5.8)
hold, then for any initialization Wo have W.Qj P W
The conditions of Theorem 5.1 can be applied to the choice of joint schedule for the learning rate and augmentation scheme applied gradient descent. If the same augmentation is applied with different strength parameters at each step t such on the choice of joint schedule for т and these strength parameters. In the example of Theorem 4.1 for Gaussian noise, the condition that of is non-increasing implies (5.5). the first condition of 4.4 implies (5.6). and the second condition of (4.4) implies (5.7)
for Gaussian noise, they impose conditions
In addition the conditions Theorem 5. imposes D,, the proxy optima W and their limit W are determined by the distribution of D,. Therefore, for W in Theorem be desirable set of parameters for the original dataset DD, the augmented dataset D, must have some relation D.

---

Under review as a conference paper at ICLR 2021
When the augmentation procedure is static in t, Theorem [.1 reduces to standard Monro-Robbing theorem Robbins & Monro (1951) for the (static) proxy loss L.(W). As in that setting, condition (5.6) enforces that the learning trajectory travels far enough to reach an optimum. Condition (5.7) implies the weaker condition (5.8; the second summand in (5.8) is the variance of the gradient of the augmented loss L(W: D.), meaning (5.8) implies the total variance of the stochastic gradients summable. Condition (55) is new; it enforces that the minimizers W? of the proxy losses (W) change slowly enough that the augmented optimization procedure can keep pace.
Though it may be surprising that [[[;] appears in this condition, it may be interpreted as the gra- dient descent trajectory for the deterministic sequence of proxy losses L (W)). Accounting for the dependence on B[W;] allows us to give more precise rates using the variance of the stochastic gra- dient in (.8); we include both (5.7) and (5.8) to allow user of our results to separately analyze
E[ to obtain stronger conclusions.
5.2 CONVERGENCE RATES AND SCHEDULING FOR DATA AUGMENTATION
more precise analysis of the the proof of Theorem 5.1 allows us to obtain rates of convergence for the projections W || of the weights onto VIj to the limiting optimum W In particular, when the quantities in Theorem 5.1 have power law decay, we obtain the following result.
Theorem 5.2 (informal Special case of Theorem B.4 If Vi is independent of t, the learning rate satisfies Tp + O, and for some 0 < a < 1 < 31, 82 and > a we have
Ty MiAna V XX,,,X,]
22(t
E || Ot) 11)
(5.9)
and
B X X
E x = 0(L7)
(5.10)
and
n/ [IE[ x(X, (YxX) EE ELY Ott
(5.11)
then any initialization Wo. we have for any > 0 that
mmn (8 1, 12
1 - W - 0.
Theorem measures rates in terms of optimization steps t, but different measurement of time called the intrinsic time of the optimization will be more suitable for measuring the behavior of optimization quantities. This was introduced for SGD in Smith & Le (0018): Smith al.) (2018), and we now generalize it to our broader setting. For gradient descent on a loss 2, the intrinsic time a quantity which increments by 17 (H) for optimization step with learning rate 17 at a point where L has Hessian H. When specialized to our setting, it is given by
[-1
2 N
7 +(1)
A Vi [B(X,X]))
(5.12)
Notice that intrinsic time of augmented optimization for the sequence of proxy losses E. appears in Theorems 5. and 5.2 which require via condition (5.6) that the intrinsic time tends to infinity as the number of optimization steps grows.
Intrinsic time will be a sensible variable in which to measure the behavior of quantities such as the fluctuations of the optimization path [(t) == (W, - @ In the proofs of Theorems we show that the fluctuations satisfy an inequality of the form
5.1 and 5.2
f(t 1) S (() a(t)) + b(t)
(5.13)
for a(t) :- 27): N Amin, v, (E XxX,X) and b(t) = Varll V ((W))l so that T(1) = Σt= a(s).
Iterating the recursion (5.3)) shows that
1-1
(()) < (0) II (()))²
Σ b(s) 0=0
II (1 (1-aa a())²
b(s) 2r 2x(1) (7(s
2 f(0) + Σ
a(s)
7

---

Under review as a conference paper at ICLR 2021
For =(t) and changes of variable A(r), B()), and F(T) such that A(T(t)) a(t), B(r(t))
b(t), and F(r(t)) = f(t), we find by replacing right Riemann sum by an integral that
F(T) 3 e F(O) [(O)+/ /-" B(o) 22 do
(5.14)
A(o)
In order for the result of optimization to be independent of the starting point, by (5.14) we must have + 0O to remove the dependence on F(0); this provides one explanation for the appearance of in condition (5.6). Further, (5.14) implies that the fluctuations at an intrinsic time are bounded by an
Blo which depends only the ratio of A(o) and B(o). In the case of integral against the function A(aj minibatch SGD, we compute this ratio in (6.2) and recover the commonly used "linear scaling" rule for learning rate.
In Section O we specialize Theorem 5.2 to obtain rates of convergence for specific augmentations. Optimizing the learning rate and augmentation parameter schedules in Theorem 5.2 allows us to derive power law schedules with convergence rate guarantees these settings.
IMPLICATIONS FOR MINI-BATCH STOCHASTIC GRADIENT DESCENT (SGD)
We apply framework to study mini-batch stochastic gradient descent (SGD) with the po- tential presence of additive noise. Though data augmentation commonly refers to techniques aside from SGD, will see that our framework handles it uniformly with other augmentations.
6.1 MINI-BATCH SGD
In mini-batch stochastic gradient descent, Dj is obtained by choosing a random subset B, of D of prescribed batch size B, | Each datapoint in B, is chosen uniformly with replacement from D, and the resulting data matrices X, and Y, are scaled so that Z.(W) D): Concretely, this means that for the normalizing factor G == VN/B, we have
=x=AXA
and Y, :Y=
where A, NxB. has i...d columns At, with single non-zero entry equal chosen uniformly at random. In this setting the minimum norm optimum for each are the same and given by
W W YX"(XXX
which coincides with the minimum norm optimum for the unaugmented loss. Our main result for standard SGD is the following theorem, whose proof is given in Appendix D.]
Theorem 6.1. If the learning rate satisfies Tr 0 and
Σ m=
00,
(6.1)
then for any initialization Wo, we have WiQj P W If further we have that m O(t with
0 < x 1, then for some C > 0 we have
Ca [W&Q] W 1F O.
1. the exponential convergence rate for SGD, which has been extensively studied through both empirical and theoretical means (Bottou et al. 2018 Ma et al. 2018). Because 1 < B, S . for all t, it does not affect the asymptotic results Theorem 6.1 In practice, however, the number of optimization steps t often small enough that ft is of order a- for some a O. meaning the choice of B, can affect rates in this non-asymptotic regime. Though we do not attempt push our generic analysis this granularity, this done in Ma et al. (2018) to derive optimal batch sizes and learning rates in the overparametrized setting.
B.
Our proof of Theorem 6.1 shows the intrinsic time is rtt) -'= 2n, N
1 Amin. Vi (XXT) and the
ratio a!!)
Me) in 5.14) is by D.4 bounded uniformly for constant C' > 0 by
b(t) < C a(t)
(6.2)
B.
8

---

Under review as a conference paper at ICLR 2021
b(2) Thus, keeping a(t) fixed function of 7 suggests the "linear scaling" T)e x B, used empirically in Goyal al. (2017) and proposed via an heuristic SDE limit in Smith et (0188)
6.2 MINI-BATCH SGD WITH ADDITIVE SYNTHETIC NOISE
In addition to handling synthetic noise and SGD separately, our results and framework also cover the hybrid case of mini-batch SGD with batch size B, and additive noise at level o, Here,
X, = (x , + o,G,)
and
== Ar,
where ot and A, are as Section 6.1 and G. E RR has i.i.d. Gaussian entries. The proxy loss is
N Z,WW= = N A & Go, = | || - w + o
with ridge minimizer W = -XX + of Idnxx) Like with synthetic noise but unlike noiseless SGD, the optima W7 converge to the minimal norm interpolant Winn Y XXx(XXX (XX!)+
Theorem 6.2. Suppose of + 0 decreasing, Tpe + O, and for any C > we have
Σ (mo) - CTlE = 0o and t=
Σ of < co. ==
(6.3)
Then we have W. Ps Wmin- we further have ti = O(t=)) and of = Ot with x, > 0 and x + < 1 < 2x + y, we have for any > that
(min W Wmin & 0.
Theorem 6.2 provides an example where our framework can handle the composition of two augmen- tations, namely additive noise and SGD. It reveals a qualitative difference between SGD with and without additive noise. For polynomially decaying 7/t the convergence of noiseless SGD in Theorem 6. exponential in 1, while the bound from Theorem 6.2 is polynomial in /. This is unavoidable. In- deed, for components
W, orthogonal to colspan (X). convergence requires that Eis no? = co (see (4.3) ). This occurs only if has power law decay, causing the |Wr mmin F to have at most power law decay as well. Finally, the Monro-Robbins conditions (6.3) are more restrictive than the analogous conditions in the pure noise setting (see (4.4), the latter allow for large Ne schedules in which 2i The diverges but Drmo N/. ? does not.
DISCUSSION
We have presented a theoretical framework to rigorously analyze the effect of data augmentation. As can be seen in our main results, our framework applies to completely general augmentations and relies only on analyzing the first few moments of the augmented dataset. This allows us to handle augmentations diverse additive noise and mini-bate SGD well as their composition in uniform manner. We have analyzed some representative examples in detail in this work, but many other commonly used augmentations may be handled similarly: lreee-pgs transformations (e.g. color jitter, geometric transformations). random projections (DeVries Taylor (017)] Park] al. 2201),, and Mixup (Zhang al. 2017), among many others. Another line of investigation left to future work is to compare different methods of combining augmentations such as mixing, alternating, or composing, which often improve performance in the empirical literature (Hendrycks) et al. 2020).
Though our results provide a rigorous baseline compare to more complex settings. the restriction of the present work to linear models is of course a significant constraint. In future work, we hope to extend our general analysis to models closer to those used practice. Most importantly, we intend to consider more complex models such as kernels (including the neural tangent kernel) and neural networks by making similar connections to stochastic optimization. In an orthogonal direction, our analysis currently focuses on the mean square loss for regression, and we aim to extend it to other losses such as the cross-entropy loss. Finally, our study has thus far been restricted to the effect of data augmentation for generalization with more complex models. We hope our framework can provide the theoretical underpinnings for more principled understanding of the effect and practice of data augmentation.
optimization, and it would be of interest to derive consequences

---

Under review as a conference paper at ICLR 2021
REFERENCES
Francis Bach and Eric Moulines. Non-strongly-coonexx smooth stochastic approximation with con- vergence rate (1/n). In Advances in neural information processing systems, pp. 773-781, 2013.
Peter I. Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 2020.
Chris M Bishop. Training with noise is equivalent tikhonov regularization. Neural computation, 7(1):108-116, 1995.
Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. Siam Review, 60(2):223-31,, 2018.
Olivier Chapelle, Jason Weston, Léon Bottou, and Vladimir Vapnik. Vicinal risk minimization. In T. K. Leen, T. G. Dietterich, and V. Tresp (eds.), Advances in Neural Information Process- ing Systems 13, pp. 416-422. MIT Press, 2001. URL http::/papers. ceappers..ipp... (l..s.cccpaperr 1876-vicine
wwiii--mmiiimmn zat ..t.atiii..................m....
Shuxiao Chen, Edgar Dobriban, and Jane H Lee. Invariance reduces variance: Understanding data augmentation in deep learning and beyond. stat, 1050:25, 2019.
Ekin D Cubuk, Barret Zoph, Dandelion Mane, Vijay Vasudevan, and Quoe V Le. Autoaugment: Learning augmentation strategies from data. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 113-123, 2019.
Ekin Cubuk, Barret Zoph, Jonathon Shlens, and Quoc Le. Randaugment: Practical automated data augmentation with reduced search space. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops, pp. 702-703, 2020.
Tri Dao, Albert Gu, Alexander Ratner, Virginia Smith, Chris De Sa, and Christopher Re. A kernel theory of modern data augmentation. volume 97 of Proceedings Machine Learn- ing Research, pp. 5528-1537, Long Beach, California, USA, 09-15 Jun 2019. PMLR. URL http::/pproceedinng mlr. press /1/////////// dawl 9b. html
Alexandre Défossez and Francis Bach. Averaged meass-seasss
Bias-variance trade-offs and optimal sampling distributions. In Artificial Intelligence and Statistics, pp. 205-213, 2015.
Terrance Vries and Graham W Taylor. Improved regularization of convolutional neural networks with cutout. arXiv preprint arXiv:
2017.
Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, An- drew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch sgd: Training imagenet in hour. arXiv preprint arXiv: 120.0677 2017.
Yves Grandvalet and Stéphane Canu. Noise injection for inputs relevance determination. In Ad- vances intelligent systems, pp. 378-382. IOS Press, 1997.
Dan Hendrycks, Norman Mu, Ekin D. Cubuk, Barret Zoph, Justin Gilmer, and Balaji Lakshmi- narayanan. AugMix: A simple data processing method to improve robustness and uncertainty. Proceedings of the International Conference on Learning Representations (ICLR), 2020.
Daniel Ho, Eric Liang, Xi Chen, Ion Stoica, and Pieter Abbeel. Population based augmentation: Efficient learning of augmentation policy schedules. In International Conference on Machine Learning, pp. 2731-2744 2019.
De Huang, Jonathan Niles-Weed, Joel A. Tropp, and Rachel Ward. Matrix concentration for prod- ucts, 2020.
Daniel Leleune, Randall Balestriero, Hamid Javadi, and Richard G Baraniuk. Implicit rugosity regularization via data augmentation. arXiv preprint arXiv: /639, 2019.
Aitor Lewkowycz and Guy Gur-Ari. On the training dynamics of deep networks with / regular- ization. arXiv preprint arXiv:2006.0866 2020.
10

---

Under review as a conference paper at ICLR 2021
Frederick Liu, Amir Najmi, and Mukund Sundararajan. The penalty imposed by ablated data aug-
mentation, arXiv preprint vrXiv:2006.04766 2020.
Siyuan Ma, Raef Bassily, and Mikhail Belkin. The power of interpolation: Understanding the effec- tiveness of sgd in modern wer-parametrriee learning. In International Conference Machine Learning, pp. 3325-3334. PMLR, 2018.
Daniel S Park, William Chan, Yu Zhang, Chung-Cheng Chiu, Barret Zoph, Ekin D Cubuk, and Quoc V Le. Specaugment: A simple data augmentation method for automatic speech recognition. Proc. Interspeech 2019, pp. 2613-2617, 2019.
Shashank Rajput, Zhili Feng, Zachary Charles, Po-Ling Loh, and Dimitris Papailiopoulos. Does data augmentation lead to positive margin? arXiv preprint arXiv: /90500370 2019.
Herbert Robbins and Sutton Monro. stochastic approximation method. Ann. Math. Statist. 22(3): 400-407, 09 1951. doi: 10. 1/214//mm//1177225500
URL
http:///oo.orggo/ 1214/
2oma/117712958
PY Simard, D Steinkraus, and JC Platt. Best practices for convolutional neural networks applied to visual document analysis. In Seventh International Conference on Document Analysis and Recognition, 2003. Proceedings., volume 2. pp. 958-958, 2003.
Samuel L Smith and Quoe V Le. A bayesian perspective on generalization and stochastic gradient descent. In International Conference Learning Representations, 2018.
Samuel L Smith, Pieter-Jan Kindermans, Chris Ying, and Quoe V Le. Don't decay the learning rate, increase the batch size. In International Conference on Learning Representations, 2018.
Stefan Wager, Sida Wang, and Percy S Liang. Dropout training as adaptive regularization. In Advances in neural information processing systems, pp. 351-359, 2013.
Denny Wu and Ji Xu. On the optimal weighted 12 regularization in overparameterized linear regres- sion. arXiv preprint 20X0:20006.05800, 2020.
Lei Wu, Chao Ma, and E Weinan. How sgd selects the global minima in wver-parameterizee learning: A dynamical stability perspective. In Advances Neural Information Processing Systems, pp- 8279-8288, 2018.
Sen Wu, Hongyang R. Zhang, Gregory Valiant, and Christopher Ré. On the generalization effects of linear transformations data augmentation, 2020.
Hongyi Zhang. Moustapha Cisse, Yann N Dauphin, and David Lopez-Paz. mixup: Beyond empirical risk minimization. arXiv preprint 11X::17710.0942,,
A ANALYTIC LEMMAS
In this section, we present several basic lemmas concerning convergence for certain matrix-valued recursions that will be needed to establish our main results. For clarity, first collect some matrix notations used in this section and throughout the paper.
A.1 MATRIX NOTATIONS
Let M Rmxx be matrix. We denote its Frobenius norm by ||M||| and its spectral norm by || la. Ifm= = n so that M is square, we denote by diag(M) the diagonal matrix with (lag(M). ) Mg. For matrices A, B, C of the appropriate shapes, define
Ao B & C* = BAC
(A.1)
and
Var(A) E 3 A] E[AT] & [[A].
(A.2)
Notice in particular that
Tr(Iooar(AA) = Bl|l B[A]]]]]
11

---

Under review as a conference paper at ICLR 2021
A.2 ONE- AND TWO-SIDED DECAY
Definition A.I. Let A. E ERax be sequence of independent random non-negative definite matri-
with
sup ||A 2 almost surely,
let Bi E -Pxx" be a sequence of arbitrary matrices, and let Ct E R be a sequence of non- negative definite matrices. We say that the sequence of matrices X₁ E TRxx has one-sided decay of rype ({At), {B+]) if satisfies
X+1=
- B2-
(A.3)
say that a sequence of non-negative definite matrices Ze E Raxx has two-sided decay of type ((Ar) (C.)) if satisfies
2+11 = A -A)) C.-
(A.4)
Intuitively, if a sequence of matrices X, (resp. Z,) satisfies one decay of type ([Ac), {B+}) (resp. two-sided decay of type ((A.),(C))) then in those directions Rn for which ||A,u]] does decay too quickly in f we expect that X2 (resp. Z,) will converge to 0 provided B, (resp. C₁) are large. More formally, let us define
DO
Vii
[I -[[A.) ker
u R"
lim I -LA,E[AA))=. VA 2
and let Q1 be the orthogonal projection onto Vi. It is on the space VI that that we expect X,, Ze to tend to zero if they satisfy one two-side decay, and the precise results follows.
A.3 LEMMAS ON CONVERGENCE FOR MATRICES WITH ONE AND TWO-SIDED DECAY
We state here several results that underpin the proofs of our main results. We begin by giving in Lemmas A.2 and A..3 two slight variations of the same simple argument that matrices with one or two-sided decay converge to zero.
Lemma A.2. If a sequence {Xt} has one-sided decay of type ((Ar), (B.}) with
BBlF < <0,
(A.5)
1=0
then lim X1Q21 = O.
Proof. For any > 0, choose Ti so that Eis,, | < and Ta so that for > Ta we have
( ii (Id (Id- Q11
< 2 Xooll + J1- Bell
==
By A.3 we find that
X Xo II (Id E[A.))
Σ B II (I.-E)A.)),
-=
which implies for t > T2 that
11 & x
[I [Id -E-EE/ -E(AA)
+ Σ
B.llF
II r=
(Ta Aa-EE/A (E(E(4))
==0
(A.6)
Our assumption that |||||| < almost surely implies that for any T <
T
[ld - E(A.)) Q1
<
(II ([dd=E[A.]) ==0
Q1
12

---

Under review as a conference paper at ICLR 2021
since each term in the product is non-negative-definis Thus, we find
Ti
|| ii (Ld -B(A,))
= ||oolle |
Σ
|BBll
21
+ Σ
|BB F
<6.
==
Taking & and then 0 implies that lime-
X,Q 0, desired.
Lemma A.3. Ifa sequence {Ze} has two-sided decay of type ((Ar), {Ct)) with
T
(ilud-A))00 =0 for all t 2
lim E T T-200
(A.7)
2
and
Tr(C,) <0,
(A.8)
then lim 272 = O.
Proof. The proof is essentially identical to that of Lemma A.2 That is, for c 0, choose T₁ that ΣiSn, Tr(C,) < and choose T2 by (A.7) 7 so that for t >> T2 we have
II and A.))
"2 Tr(Z)) EID Tr((.))
Conjugating A.4 by Qi, we have that
2 =E Q II (Id
(Ta-) -a))
Zo
II (Id (Id--A)))
==0
8=0
E
II (1d r=
Ab)) T C.
II (Id (a--a))01 r=8+1
#=0
Our assumption that ||Ae|| < almost surely implies that for any T s
(Id (aaa)
< [ ([aa-A.)) (
==0
Fort t T2. this implies by taking trace of both sides that
(fina (1((a-A)))
T+1 S Tr(Z))
Qn
+ Σ Tr(C.JE
II
(Td - A.) A.) Qi
r=st1
(A.9)
T1-1
Tr Tr(Za)
Σ Tr(Cs)
E
II ==
(Td A.) A.))
+ Σ Tr(C.)
==0
==N
<6
which implies that 4om 272:211 =
The preceding Lemmas will be used to provide sufficient conditions for augmented gradient descent to converge in Theorem B.I below. Since we also interested in obtaining rates of convergence, we record here two quantitative refinements of the Lemmas above that will be used in the proof of Theorem B.4
13

---

Under review as a conference paper at ICLR 2021
Lemma A.4. Suppose (Xt) has one-sided decay of type (fAc), {Bi)). Assume also that for some X and C' 0, we have
[[( <x C f. rr
<x-c..
log
and |B,I| Ott @) for some 0 D<a<l < 3. Then, |X O(t P)
Proof. Denote Ys S ar. By A.6). we have for some constants C₁, C2 that
| < Cne + Cze P) -
(A.10)
The first term on the right hand side is exponentially decaying in é since 71,41 grows polynomially in To bound the second term, observe that the function
f(s) Css1i4411 3 log( +
satisfies
1/0 a) =:
20 +
C(s 1)
1
Hence, the summands are monotonically increasing for s greater than a fixed constant K depending only B, C. Note that
E(++s) 8e C% Ce & Ke CTRLE. Ke Ke-C't -'t
for some C" depending only on a and and hence sum is exponentially decaying in Further, using integral comparison, we find
81+s)-Be-Crttin I (1 (1+ ( ds.
(A.11)
K+1
Changing variables using a = (1+ 8) "1/)"///(111// - a), the last integral has the form
91
9= (1 + 11+x)==- x)2-a
8 3-0
Cg (1 (1-
u u
(A.12)
Integrating by parts, we have
[ u
C C f u
e C-
+ (u -u-=e C
9k
9x
Further, since on the range 9K S u I gt the integrand is increasing, we have
I u -u Ege -5.
g)
Cang g
Hence, e-Cy Cye times the integral in 1212) is bounded above by
O + e Cae (u C'C St = O
Using A.I1 and substituting the previous line into (A.12) yields the estimate
Σ (1+
-C S (1 t 8t0
$=
which completes the proof.
14

---

Under review as a conference paper at ICLR 2021
Lemma A.5. Suppose {Ze} has two-sided decay of type ({A,), {C()). Assume also that for some X and C' 0, we have
c (i (Idda <x <x-c/
J(L r-
log E
as well as Tr(C;) O(t P) for some 0 <a <1< Then Tr Z(Q1) O(ta-A).
Proof. This argument identical to the proof Lemma A.4 Indeed, using (A.9) we have that
Tr (of & Cie Cn + C2ex E (1 s) -
The right hand side this inequality coincides with the expression on the right hand side of (A.10) which we already bounded by ((to-a) in the proof of Lemma A.4
In what follows, we will use concentration result for products matrices from Huang et al. 2020 Let Vi.................. Yn NxN be independent random matrices. Suppose that
| S and
E [[|Y, - E| < b.ag
for some a,...., On and ... bn. We will use the following result, which a specialization of Huang et al. 2020 Theorem 5.1) for p ======--- 2.
Theorem A.6 ((Huang al. 2020
Theorem 5.1)). For Zo E RN the product 2.
Y, Y ... Zg satisfies
E
S Siat
of 12
E Zi, B(Z 2 (C 1)0a aa 1
Finally, we collect two simple analytic lemmas for later use. Lemma A.7. For any matrix M E mR we have that
B[[M Z |[[M]|
Proof. We find by Cauchy- SchwartS and the convexity of the spectral that
E z B[Il 2 [|[M]]|
Lemma A.8. For bounded 04 2 0, if we have Σe a = oc, then for any C > we have
age 0: 9x 00.
Proof. Define bi = Ei= Ug so that
00 - C= dx < <0,
S :
are
C. C.
[(, be- Ch <
1=0
t=0
where use 000 da to upper bound its right Riemann sum.
B ANALYSIS OF DATA AUGMENTATION STOCHASTIC OPTIMIZATION
In this section, prove generalizations of our main theoretical results Theorems 5.1 and 5.2 giving
type conditions for convergence and rates for augmented gradient descent in the linear setting.
15

---

Under review as a conference paper at ICLR 2021
B.1 MONRO-ROBBINS TYPE RESULTS
To state our general Monro-Robbins type convergence results, let us briefly recall the notation. We consider overparameterized linear regression with loss
C(W; D) N [
where the dataset 'D of size N consists of data matrices X, Y that each have N columns 2; E R", U/ IR with N. We optimize L(W; D) by augmented gradient descent, which means that at each time we replace D = (X, Y) by a random dataset D, = (X,, Y,). We then take a step +++ = W. 7 V WWW;; D,))
of gradient descent the resulting randomly augmented loss (DW;D;) with learning rate v)-- Recall that we set
Vi column span of x[X,X;]
and denoted by Ql the orthogonal projection onto Vij. As noted $ on VI the proxy loss
Z. = E. (C(W;
strictly convex and has a unique minimum, which is
W = E [,,]]] (Q EE [X,X,] Q11)"
The change from one step of augmented GD to the next in these proxy optima is captured by
E Wi+1 W..
With this notation, varying Monro-Robbin type conditions under which the optimization trajectory We converges for large In Theorem B.4 refine the analysis additionally give rates of convergence.
ready to state Theorems B.1 which gives two different sets of time-
Theorem B.1. Suppose that Vi is independent of t, that the learning rate satisfies n) - 0, that the proxy optima satisfy
Σ
E F < 00,
(B.1)
ensuring the existence of a limit W = so Wi and that
TcAmin, vi (E[X,,]1) 0c.
(B.2)
Then if either
TE [|I,XX] - EXX,XT]11 + || ||X,,] - E|YxXTI113 <0
(B.3)
or
De E |X B[X,X|]]
+ I[IIWIXX,X] - E[X,X]) (XXX E|XxN1) <0 (B.4)
hold, then for any initialization Wo, have WiQu 2 W
Remark B.2. In the general case, the column span VI xXx, may vary with t. This means that some directions in Ih." may only have non-zero overlap with colspan( [XI, for some positive but finite collection of values of L. In this case, only finitely many steps of the optimization would move W, in this direction, meaning that we must define a smaller space for convergence. The correct definition of this subspace turns out be the following
2n
E(XxX!I)
V1
ker
Id
(B.5)
N
R
lim
Id II
2nh
u x[X;XXI)==00
EIX,
u00
T-000
t=
s=t
16

---

Under review as a conference paper at ICLR 2021
With this re-definition of Vij and with Q1 still denoting the orthogonal projection Vi, Theorem B. holds verbatim and with the same proof. Note that if n). 0. Vicoospam(E](xxX]] fixed in t, and B.2) y holds, this definition of V1 reduces to that defined in (5.3)
Remark B.3. The condition
B. can be written in a more conceptual way as
Σ [IX.x]
o Tr Var (BII,)X, xX)x <00,
where we recognize that (E[W,)X, - Y is precisely the stochastic gradient estimate at time t for the proxy loss L, evaluated at E [Wa]. which is the location at time t for vanilla GD on Ce since taking expectations in the GD update equation (5.1) coincides with GD for Lt. Moreover, condition (B.4) actually implies condition (B.3) (see (B.12) below). The reason we state Theorem B.1 with both conditions, however, is that B.4 makes explicit reference to the average E (We) of the augmented trajectory. Thus, when applying Theorem B. with this weaker condition, one must separately estimate the behavior of this quantity.
Theorem B.1 gave conditions joint learning rate and data augmentation schedules under which augmented optimization is guaranteed to converge. Our next result proves rates for this convergence.
< B1, B2 and C1, C2 > we Theorem B.4. Suppose that 17 + and that for some 0 a < have
log E
[II
2nh ld
x x x
< C1 - C2
r+1
r rr
(B.6)
N
as well
| = 0t
(B.7)
and
wh Tr Ido - -Y.X)) 01 -0(-))))
(B.8)
Then, for any initialization Wo. we have for any c > that
mmi (Bt -1, 1, 1,-2-")
|1:Q W 2 0.
Remark B.S. To reduce Theorem 5.2 Theorem B.4 notice that (5.9) and (5.10) mean that
X.X! Theorem A.6 applies to Y, = Id 1d-2m 2m N with 1 - (t and and b? Ott")), thus
implying B.6
The first step in proving both Theorem B.I and Theorem B.4 is to obtain recursions for mean and variance of the difference W. W between the time proxy optimum and the augmented
optimization trajectory at time t. We will then complete the proof of Theorem B. in BB3 and the proof of Theorem B.4 in B.4
B.2 RECURSION RELATIONS FOR PARAMETER MOMENTS
The following proposition shows that difference between the mean augmented dynamics E[[]] and the time-t optimum W7 satisfies, in the sense of Definition A.I. one-sided decay of type (fAr), (B.)) with
2m N
A
X,XX,
-
also shows that the variance of this difference, which is non-negative definite, satisfies two-sided decay of type (IA,), {C.)) with A, as before and
4n N2
Var - -EI])
C =
In terms of the notations of Appendix A.1
we have the following recursions.
17

---

Under review as a conference paper at ICLR 2021
Proposition B.6. The quantity E[W;] Wi satisfies
B[ W (B[w,) - wi) (Td 2n B(x,)?])
- =;
(B.9)
and Z, = E[(W; - E(WW) [[])]] satisfies
Z4+1 E (Id
2m
x,X,) ZT
2T xxx,))
+
4nk N
Var E[W,X, YXX)
N
(B.
Proof. Notice that EXX,XX if and only if X7 u = almost surely, which implies that
W
E [
|XXX | |X E[
Thus, the learning dynamics 5.1 yield
2n B[ B[W.]
[
[
N
2n
E[]]
[E[W;] W |[
N
Subtracting Wi+1 from both sides yields (Am = A A have
B.9
We now analyze the fluctuations. Writing
2n
B[W [[ [E 2+1] [[w.]
Sym B.W. (BW.
N
+ 4np N Similarly, we have that
21 N
E[W
W+]] E
E[W, Wil +
Sym(EE(W))))) YXXy wTW.X.x7])
4m
E
W.
Sym(S,, WTT.T X.Y,
N2
Noting that X2 and Y; are independent of W, and subtracting yields the desired.
B.3 PROOF THEOREM B.I
First, by Proposition B.6 we see that B[W,
W has oidds decay with
A = 2m X,XT
and
B, = E
Thus, by Lemma A.2 and B.I
we find that
lim (E[W.]Qq W?) = 0,
(B.
which gives convergence in expectation.
For the second moment, by Proposition B.6
we see that Z, has two-sided decay with
A. 27) X,XT
4nF
and
C
Var
[[W,]XxxX -xx7)]
N2
We now verify A.7 and (AS.) in order to apply Lemma A.3
For
A.7
for any
0, notice that
El A, E[A.1|| = EXI,XX - E[X,XX] T
so by either B.3 or B.4 we may choose Ti > so that - E[lIA, E[A.JIE] < 5. Now
choose T2
Ti that for T > T2. have
E[Td- -..)
Eld
-
1, - [E[ A, - E[A.]11.]
18

---

Under review as a conference paper at ICLR 2021
For T > T2, we then have
E
II
(1d A.)
#=1
T
T ΣB
T
Biid - -A.1) Q1
E
(ld A,)
II (Id (id-E(A,))Qj
(Id A,) II [Td (id-B[A.1)0))
==1
==1
1ms+111
T
2
T (Id AA) -[IA.) II (Ld (id-E[A,)))
[
Biid A.l Q
F
s
#=++1
T1 11
T
T Σ
T
B - A.]
II
IT 4.1) Q1
+
BlI B[A.]l
II
E[Id A- -.1)
r=T1
F=s+1
(
E[ld - A.]
+
E Σ
| - -(A.I1+))
[I
E|id 1. -.1)
BiI E[4.11
7
<,
which implies A.7
Condition
A.8 follows from either B.4 or B.3) and the bounds
8n
Tr(C,)
([X
(B.12)
N2
(I
-[X, |1
+ |
E 112))
N2
where in the first inequality we the fact that || M2 < 2( M1 | Ma 2) Furthermore, iterating (B.9) yields
[[] W | S
|| W. Wo + Σt= E r. which combined with (B.12)
and either (B.3)
B.4 therefore implies (.8). We conclude by Lemma A.3 that
lim Q 2 = lim ][Q] (W, B(W.)) (W, - 1 = O.
(B.13)
1-000
t100
Together, (B.11) and B.13)
imply that W.Q W7 2, 0. The conclusion then follows from the This complete the proof Theorem B.I
fact that lim W W
B.4 PROOF OF THEOREM
By Proposition B.6 E EWW W," has one-sided decay with
2m.
A,
X,X,
-
=
N
By Lemma A.7 and B.6b. B[A,] satisfies
log πI
ld 2n, N
EXX,X,1]
1 log
Id
2n,
X,X
)){)
2
N
C
C2
1+1
2
Applying Lemma A.4 using this bound and (B.7). , we find that
[E Will 0(10-81)
Moreover, because | || (t- we also find that IW; - W O and hence [| II O(
Further, by Proposition B.6
[W, E(W.)) B[W,)) has two-sided decay with
2n A =
X.X,,
C =
4n
Id Var E.W.X.XX - yxx,]]
N
N22
19

---

Under review as a conference paper at ICLR 2021
Applying Lemma A.5 with (B.6) and (B.)) find that
[[(w: - B[ [1[]] - O(ta-8a).
By Chebyshev's inequality, for any x: we have
P P(IW W || 2 ( -+t) O(t 0(t)²())
S xx
For any 0, choosing 1 for small 0 < 6 we find as desired that
minn (8= 1, "- [ - W |l & 0,
thus completing the proof of Theorem B.4
C ANALYSIS OF NOISING AUGMENTATIONS
In this section, we give full analysis of the noising augmentations presented in Section Let us briefly recall the notation. As before, we consider overparameterized linear regression with loss
1 N II YII L(W;D)
where the dataset D of size N consists of data matrices X, that each have N columns 2; R" y/ E Rº with > N. We optimize L(W; D) by augmented gradient descent with additive Gaussian noise, which means that at each time we replace D = (X,Y) by random dataset D, (X,,), where the columns Fi, of Xt are
Ft 24 orGi,
G 1.
We then take step
W++1 W. V V (
of gradient descent on the resulting randomly augmented loss L(W;D.) with learning rate Th- A direct computation shows that the proxy loss
Z. E [CWW; D.)l L(W: of
which is strictly convex. Thus, the space
Vi = column span of XXX,X]]
is simply all of IR, Moreover, the proxy loss has a unique minimum, which is
W Y Nd, +XX")-1
C. PROOF OF THEOREM
We first show convergence. For this, we seek show that o? mr - with of non-increasing and
Σ 1=0
nho oc
and
2 2 < 00,
(C.1)
t=0
check that assumptions imply the hypotheses of these theorems. For [..lrem[..]] we directly compute
then, W. 2 Wmin- We will do this by applying Theorem 5.1
EYXXT = Y and B[X,X,] XXT ofN Id
and x + ON +n+1)x
E[X.X X,X,I x +o² n + To(X"")ddxxx +o,N(N +n 1) Id
20

---

no Under review as a conference paper at ICLR 2021
We also find that
| lož I N YXT XxX + tofN Idnxn) -1
("xxx + +oi Idaxn
- - MIX
Thus, because of is decreasing, we see that the hypothesis 5.5 of Theorem 5.1 indeed holds. Further, note that
Σ E | E[X,XX111 + |X 1|
0c oo En
Σ no 2
NI ofNn(n 1)) =0
which by C.1 implies
B.3
Theorem
5.1 and the fact that lim, We Wmin min therefore yield
that W. 2 W min-
For the rate of convergence, we aim to show that if 1/s @(t=2) and of = (t with x, > 0, x y < 1, and 2x + y > then for any > we have that
mmin {a) W. Wmin P O.
We now check the hypotheses for and apply Theorem B For B.6p, notice that Y, = ld -21, x.
satisfies the hypotheses of Theorem A.6 with a, = 2n and b3 a3 2( + 1) ||? +
Nnnn + 1) Thus, by Theorem A.6 and the fact that 17, (t==)) and of O ッ), find for some C₁, C2 > 0 that
f [Id 2m X,XT
log E
6 Σ log(1 21,
SC1 rr--v
For B.7
we find that
|| F S l0? - |
Finally, for B.S
we find that
tf Tr Id o Var
E E[,,JX,,; - y,x?)] - 22-
Noting finally that ||W W mf O - ((-"), apply Theorem B.4 with a x + y. 31 y + 1, and B2 = 2x + y to obtain the desired estimates. This concludes the proof of Theorem
D ANALYSIS OF SGD
This section gives the full analysis of the results for stochastic gradient descent with and without additive synthetic noise presented in Sections 6.1 and 6.2 Let us briefly recall the notation. As before, we consider overparameterized linear regression with loss
L(W;D)- N
| X YI?
where the dataset D of size N consists of data matrices X, Y that each have N columns 2; E R" Ys Ip with N. We optimize L(W; D) by augmented SGD either with without additive Gaussian noise. In the forner case, this means that at each time we replace D = (X, Y) by random batch B, (X,, Yi) given by prescribed batch size B, |B,l in which each datapoint
21

---

Under review as a conference paper at ICLR 2021
in B, is chosen uniformly with replacement from D, and the resulting data matrices X, and Y are scaled so that (WW = L(W;D). Concretely, this means that for the normalizing factor = //BB we have
= and
Y =Y
(D.1)
where A, NxB. has columns At.: with single non-zero entry equal chosen uniformly at random. In this setting the minimum norm optimum for each are the same and given by
W W XXX
which coincides with the minimum norm optimum for the unaugmented loss.
In the setting SGD with additive noise at level ot we take instead
X₁ = ex o,Gi) and Gy
where et and A, are before and G. RexB, has i.dd Gaussian entries. In this setting, the proxy loss is
((W = N L [IQYA, AWAA, - Go, G., 2 = N Y
Wx of
which has ridge minimizer W X + oÑ. Iddxx)
We begin in D. treating the case of noiseless SGD, We then do the analysis in the presence of noise D.2
D.1 PROOF OF THEOREM 6.1
In order apply Theorems B. and B.4 begin by computing the moments of A follows. Recall the notation diag( M) from Appendix A.
Lemma D.1. For any Z E N we have that
B N
B₁ (iag(Z)== + Be 1) Z.
R [A
I and
Z[AAAAZA
N2
Proof. We have that
B. E[A,A| Σ E[A, A =
B
IdNNN
N
Similarly, we find that
B. Z[A.A ZA = Σ
E[A,A]
B[A,, AT ZA
i,=1
B.
B[A 1,A4,,
+2
Σ
ISigjSB.
B diag(Z)
Be Z,
N
N2
which completes the proof.
Let us first check convergence in mean:
E[W]Q + W
To see this, note that Lemma D.I implies
E|,XI11 T
= =[X,X]]=xX,
which yields that
W. = -xX W
(D.2)
22

---

Under review as a conference paper at ICLR 2021
for all t. We prove convergence, Since all Wł equal W find that Ej 0. By (B.9)
and Lemma D.I we have
2n xxx)..
E[W W (W w
N
which implies since
N Amax ( for large that for some C
0 have
2ms
[ Wolle S I16Q
W
Q
XXx
N
$ < - l exp
t-1
27
mmin Vi (XXT)).
(D.3)
N
From this we readily conclude using 6..1 the desired convergence in mean [ W..
Let prove that the variance tends zero. By Proposition B.6 we find that Z, E((W, B(WI)) (W;: has two-sided decay of type (fAt), (Ct)) with
2Th X,X,, A; N
4 N
C.
[Id addoVa((B Y)),)]
To understand the resulting rating of convergence, let first obtain a bound on Tr(C,). To do this, note that for any matrix A, we have
Tr (Id Var Tr E A [[] [[A)"B(A)) B(A))
Moreover, using the definition D.I of the matrix A, and writing
M, E [W,] x-y;
we find
as well [. X))XT) (W: x)) =
[( - x))xT) [ x)x7] = XE XE [A,4]] M. ME [A,4]]X* XT.
Hence, using the expression from Lemma D.I for the moments of A, and recalling the scaling factor 1/2 (N/B4 1/2,, we find
Tr(C,) = 4n Tr B,
1 N
Mr Mr }
x diag (M,
Next, writing
A, = E(W, - W
and recalling D.2), we see that
= =
Thus, applying the estimates D33
about exponential convergence of the mean, we obtain
8mF
Tr(C,)
|
2
1
C
|
11 exp
4ms N
min, vg (XXT)). (D.4)
B,
Notice now that Y, = Q A, satisties the conditions of Theorem
A.6 with a,
2nj, 1 Amin, vi (XXT) and b2
B.a Tr X diag(X diag(X - +XX"XX] By Theorem A.6
4n2
we then obtain for any
that
E
II Q A,) r=++1
< c
Et Si
II (1 2n, N
Amin, Vn (XXT))2
(D.5)
r=
23

---

Under review as a conference paper at ICLR 2021
By two-sided decay of Z₁, we find by (D.4) (D.3). and A.9 that
B B [1:]] = (r(Q ((Q
< Amin (xx1) Dizo 7h
|
Si
ahe A (xx")+ Dimmi (D.6)
N2
Bz/N
Since 77 +
is uniformly bounded and that 63 s Amin.Vy (XXT) mn, for sufficiently large r. We therefore find that for some C" > O,
we find that 7/ B,
N
Ann vy (XX")
4
N
B[I[ B [1 S C²
nae Aoinyy Dx
hence lim B B[ 0 by Lemma A.8
Combined with the fact that
B| + W this implies that WiQu 5 W
To obtain rate of convergence, observe that by D.3 and the fact that The O for some C1. C2 > we have
|B[[ W S C1 exp (- -C2t The B./N < do uniformly, for some Cz. Co, Cs > we have
(D.7)
Similarly, by (D.6 and the fact that
|| E Q | S C3 exp Catt-2 x
12-1
We conclude by Chebyshev's 's inequality that for any 0 we have P P(I [W: W || 2 Ci exp
C2t + a CCttt --- S sa-
Taking a = f, we conclude as desired that for some > 0, we have
W Wollr 3 0. Cc [WQ]]
This completes the proof of Theorem 6.1
D.2 PROOF OF THEOREM 6.2
We now complete our analysis of SGD with Gaussian noise. We will directly check that the op- timization trajectory W2 converges at large to the minimal norm interpolant W with the rates claimed in Theorem 6.2 We will deduce this from Theorem B.4 To check the hypotheses of this theorem, we will need expressions for its moments, which we record in the following lemma. Lemma D.2. We have
B|xXT = Y
and B|X,XI1 = XXT + N.NINAx
(D.8)
Moreover,
E|YXX] X.Y
+ O.
N Y diag xX +
B, B Y +ONNYYT
=
B.
B,
[VXXXX,,, = G A, A, x GYAGGAA
+ + A.G. XA.G! - -YAAA"
N
y diag X X)X B, B.-1
n YXT + +N XX
B.
B.
B,/N
XXXXXXxXX
A + + + + +oXXAG]AXA!
+ x.G.
+ +oG X.G.A.XTAAL XAG.
+GGGGGGGGG
N
B.
xx X + (2N + n 2 B./N
X diag(X X x)XT
XXX
B.
B₁
+ of N B,
TT(XxT) Idnxn NN + n 1
B./N Idaxa
24

---

Under review as a conference paper at ICLR 2021
Proof. All these formulas obtained by direct, if slightly tedious, computation.
With these expressions in hand, we can readily check the of conditions Theorem B.4 First, we find using the Morraanoooorooooooooooo matrix inversion formula that
| lo
(XXT + offN Idaxx)_'( (XXT + o N Idnxn)
(D.9)
$ No - ا YX (x'x(xx")
Hence, assuming that of = V)) we see that condition [B77 of Theorem B.4 holds with
$1
Next, let us verify that the condition B.6 holds for an appropriate a. For this, we need to bound
log E
II
Id
2m,
x,xx
which we will do using Theorem the formula
A.6
In order to apply this result, find by direct inspection of
E
E[X,
XXT + o Idnxn
that
2 N
E
Id
X X
=1
21 == dr
12
Moreover, we have
2n E
2m
27
4m N2
E
ld
X,XX
-E
ld
x
X
E
X,XX
E
[
N
N
Using the exact expressions for the resulting moments from Lemma D.2 we find
4
E
- E [x,x,]]]
N2
4nF
1
Tr ((N diWWdag''x xx_ x-xxxxx + 20 n2 1 B./N
NNn(n + 1)
T((XT)++ +o,
N²
B
B./N
I Cnf.
Thus, applying Theorem A.6
we find that
log E
II ld
2mr X
Σ Cn log
f [1 2n,
C < 2n
Recall that, in the notation of Theorem 6.2 we have
7 Or )
0f 0
Hence, since under out hypotheses we have < 2y, conclude that condition
B.6 holds with
x. + y. Moreover, exactly in Proposition B.6 we have
A
A
2n E
[xxx]]
2 =. N
A B.W [WW]
Since
||
and we already saw that
2nk E [
ld
= 2n
we may use the single sided decay estimates Lemma A.4 to conclude that
||l||
O(1=1)).
25

---

Under review as a conference paper at ICLR 2021
Finally, it remains to bound
2 Tr
Id Ido - -xxx)]
7/
A direct computation using Lemma D.2 shows
||XX? - E|
Tr (')) -xxxx) + + +
1
Be
Hence, again using D.2
we find
"/ Tr [ld o (N diag(X' X) - X XXx
- YXT))
= = Tr
Br
Be/ ElW,]XX'E[W.]" + (0) N
Tr(xxT) oNN + 1 [[(,)E[(a]])) B./N
+ 2
B,
2n Tr Y(N diag x) x x E(Wi] +o? +1
Y E(Wi))
B./N
n Tr
1
Y(N diag (x X +o!NYYT).
B.
To make sense this term, note that
X =Y
Hence, we find after some rearrangement that
tf 'Ir [dd]ar([[W]]]xx]] YxX,)] S Cnf ||A.)?))
where we
A, == E W, - W
Finally, we have
A - 4/+ ||W W = 0(t + O( 0)
since assumed that + 1. Therefore, obtain
nh Tr [Id (X - Yxx[)] & on = (
showing that condition
B.8 holds with B3 = 2r + y. Applying Theorem B, completes the proof.
26


Reviews:
[{"review_id": "owCKEUoGyu", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper is stuffed with mathematical theorems which makes it almost impossible for me to evaluate the contribution of the work without going through the proofs in the appendix, making this paper more suited for a journal than a conference with 8 pages limit in my opinion. They consider additive Gaussian noise as a data augmentation technique for mini-batch SGD over a simple linear regression with Frobenius loss. The main contribution of the work, as far as I understood, is to derive a range of possible annealing learning rate and additive noise power in Theorem 6.2 that can guarantee convergence of SGD to the global minima of the Frobenius linear regression loss which is convex. But I'm not sure about the derivation; for instance, take x=y=0.4 and e=0.3, then $W_t$ does not necessarily converge to $W_{min}$ in Theorem 6.2, right? Or have I missed something? \n\nAnyway, my biggest problem with the paper is the generality of the proposed framework, which only takes into consideration additive noise and depends strictly on the calculation of gradients as the Frobenius loss illustrates. The author tried to explain a rough idea about how to handle a nonlinear case on Page 4, but this approach can be dramatically cumbersome for the deep neural networks as it needs the calculation of Hessian and gradient with respect to the input x even! Besides, the derivations strictly depend on the additive noise power model $\\sigma_t$, but the author claims that their framework is applicable to advanced data augmentation techniques such as Mixup. This is not possible in my opinion. For instance, take a data augmentation technique like Mixup which is not totally data-agnostic such as additive noise. As you know, Mixup is applied to each mini-batch after shuffling in each step of SGD, resulting in a convex combination of the samples of different classes.  In other words, there is no parameter like the noise power $\\sigma_t$ that you can control during each step of SGD. There is only $\\alpha$ which is not quite flexible either in Mixup as it usually takes a value around 0.2. \n\nTherefore, I strongly doubt the universality of the proposed framework to deal with various networks and data augmentation techniques that are mostly used by practitioners nowadays and do not see the paper as a good fit for a conference like ICLR.\n\nAfter rebuttal: I thank the author for their response and have raised my rating by one after reading the author's response, but my concern still holds unfortunately regarding the whole approach that the author has taken to analyze the effect of data augmentation. Therefore, I'm still not confident about my rating.", "extra_scores": {}, "extra_text": {}}, {"review_id": "ehG_mH2l-oa", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a framework that re-interprets data augmentation as stochastic optimization for a time-varying sequence of objectives. The paper also provides a theoretical analysis of the simple case of over-parameterized linear regression. \n\nComments:\n\n1. In section 4, the paper claims that the gradient descent will not converge to W_min because gradient descent “cannot see” the directions in the e in the orthogonal complement of the column span of XX^T. However, it’s easy to choose an initial point W_0 which is in the column span of XX^T. Then the gradient descent may converge to W_min.\n\n2. For over-parameterized linear regression, we can directly compute W_min from the data matrix X and Y. The authors should point out the situation where data augmentation is necessary.\n\n3. Thm 5.1 and Thm 5.2 requires some conditions on W_t, which depends on the algorithm rather than the data.\n\n4. I think the authors should add some experiments to verify the effectiveness of their methods. For example, the experiments can compare the performance of gradient descent and data augmentation with Gaussian noise.", "extra_scores": {}, "extra_text": {}}, {"review_id": "Wr178JHN9ln", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "**Summary.** Authors present a novel theoretical framework for assessing the effect of data augmentation (e.g. mini batch SGD), noise addition and the learning rate setup in gradient-based optimization with overparametrized models. Despite the analysis is only performed for linear regression, results extend the well-known Monro-Robbins theorem on rates of convergence. The manuscript is a first step for future analysis of the aforementioned techniques with other type of models and/or loss functions.\n\n**Strengths.** The paper is extremely well-written and even being theoretical, authors did an effort for making it fully understandable to non-familiar readers. I particularly recognize that the line of argumentation is thorough and step-by-step decisions and equations are carefully described with intuitive sentences. i.e. first paragraphs in section 4.\n\nThe organization of the paper is good as well, first presenting the type of regression model to be analyzed, the fact of augmenting data, second with the noise-additive models and their implications and finally, connecting all the previous insights with the Moneo-Robbins theorem for a general result that authors fit with mini-batch SGD.\n\nAuthors recognize the limitations of their analysis since it is focused in linear models, but to me, this is not an issue for this type of paper. The results, focused on three trending methods as data augmentation, learning rate selection and additive noise are elegant, and as authors mention it only relies on first order moments. \n\nI took a look on the appendix demonstrations and extra information, results seems to be reproducible. References are pretty contemporaneous (last two years).\n\n**Weaknesses, Questions & Recommendations.** \nThe main weaknesses (to me) in the paper are:\n[W1]. Data augmentation is described in a very general way during the first 5-6 papers without much description, and, in the last page, authors focus on the particular case of mini-batch SGD. I understand the reasons for doing this, but preferably, a comment on the application to the mini-batch SGD case would help at the beginning. \n[W2]. In a similar way as in [W1], I missed some information about the conditions of $D_t$ wrt $D$ in the beginning of section 3.\n[W3]. References are “clustered” in the introduction and related work, but later on, not many of them are connected to the main text. So, connections are difficult to establish with the results and the argumentation. One example is in Section 4, where I missed some cases or references about the synthetic additive noise.\n\nQuestions:\n[Q1]. Could authors enumerate or describe cases/examples of data augmentation different from mini-batch SGD? References would help. (To make an idea)\n[Q2]. In pp.4 authors mention a sufficiently smooth function g. How smooth this function must be? How can we measure this sort of smoothness.\n[Q3]. Similarly as before, additive noise is referred with a small \\sigma_t. Which is the scale of sigma values considered?\n[Q4]. I liked when authors expand the previous results to the case of having the expectation term E[X_t X_t^{\\top}]. Just a silly question, in this case, could the expectation operator work as a lower bound? Similarly as in free energy methods or similar? If so, maybe working with the lower bound could help for obtaining similar results for non-linear models.\n[Q5]. I do not see why V_{||} in Eq. 5.3 is independent of t as mentioned below Eq. (5.4). The expected value remains stable?\n\nRecommendations:\n[Rec1]. A bit more of intuitive descriptions in section 4. for Eq. 4.1. and Eq. 4.2 would help to follow posterior explanations.\n[Rec2]. Similarly as Rec1, a bit more of description about Eq. 5.12 and the intrinsic time would help. I lost myself a bit on that part.\n[Rec3]. There a few “negative” sentences in the last two pages: “Though SGD is not often considered as a form of …” and “the restriction of the present work to linear models is…”. I think rewriting them in a more positive way would be better. This is an opinion.\n\n**Reasons for score.** I vote for accepting the paper at the conference. Despite the fact that the work is limited to linear models, I think the results are interesting and authors demonstrated a deep comprehension of the main strategies for optimization/fitting of models that are nowadays used everywhere. I would appreciate if authors elaborate a bit more during the rebuttal on the questions pointed out and particularly in the examples of data augmentation.\n\n**Post-Rebuttal Comments.** Thanks for the author's response and their dedication during the rebuttal period, I re-read the updated version of the manuscript and authors did an effort for adding extra content and editing based on the questions and recommendations. In my particular review, they answered and solved the questions that I did. I understand the points addressed by the other reviewers and the theoretical limitations of the method. However, I still have a positive opinion about the paper, and I believe that the aforementioned limitations are well indicated in the paper, something that is valuable. For these reasons, I keep my score.", "extra_scores": {}, "extra_text": {}}, {"review_id": "F1ID96BsI4t", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper considers stochastic gradient descent with noisy gradients. In contrast to the standard setting (e.g., gradient Langevin dynamics) where additive Gaussian noise is added to the model gradient, this work focuses on additive perturbations of data instances. As a result of this, the optimization objective changes throughout the training process because the data is no longer static/fixed but assumed to be sampled from some distribution governing the perturbation process (see Eq. 3.3).\n\nSection 4 restricts its consideration to multi-output linear models. A review of prior works shows that stochastic gradient descent with Gaussian perturbations of the inputs is in that setting equivalent (under suitable conditions on the loss) to optimizing regularized objective with the squared Frobenius norm of the weight matrix acting as a regularizer. The problem is then how to characterize the relation between the standard deviation of the Gaussian perturbation measure and learning rate. The main contribution is Theorem 5.1 which provides conditions under which the stochastic gradient descent converges to the min-norm solution. Theorem 4.1 is a special case designed to illustrate the relationship between perturbations and learning rate. The main result is further extended in Theorem 6.1 to mini-batch stochastic gradient descent.\n\n# clarity\nI find that the paper is to a certain extent well-written. Still there are parts which are difficult to follow and a revision would be required. For example, I have had problems below Eq. 5.3 when referring to $Q_{||}$. It is not clear what is being projected to $V_{||}$. I have lost track at that point and this then complicates understanding of Theorem 5.1 and pretty much everything that follows. Moreover, checking the proofs was equally confusing.\n\n# originality\nThe title of this work is miss-leading and not really sure why this is the case. I was expecting to see characterizations of more complex data augmentation schemes that span group theory (e.g., Lie group perturbations). Focusing on additive Gaussian noise might be better suited to stochastic gradient descent with noisy gradients. The noise is different from, for example, Langevin dynamics but there are similarities certainly. Given that I am not an expert on numerous settings and versions of stochastic gradient descent it is difficult to assess the originality. Still, I think that the setting with input perturbations is interesting and worth studying. In addition to this, it might be worthwhile to mention in the abstract (if not in the title) that the focus is on linear models.\n\n# quality\nI find the theoretical contribution non-trivial and technical. Still I am not completely convinced in the significance. The first reason for this is in the quite robust nature of Theorem 5.1. I find it difficult to assess how realistic the assumptions are in that theorem (see 5.7 and 5.8). The work attempts to give a more readable result in, for example, Theorem 4.1. The confusing part is what happens to assumptions 5.7 and 5.8. Are they assumed to hold?\n\nI am also not convinced about the related work on data augmentation and stochastic gradient descent with noisy gradients. I am unaware of other works on stochastic gradient descent studying this particular case with input space perturbations. Still some previous works that might be related are:\n[1] Vicinal Risk Minimization (NIPS). Chapelle et al.\n[2] Variance-based Regularization with Convex Objectives (NIPS). Namkoong & Duchi.\n\nI would also expect a detailed analysis of the contributions relative to:\n[3] A Kernel Theory of Modern Data Augmentation (ICML). Dao et al.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the behavior of SGD for linear models fit with the squared Euclidean loss. There are three main results:

The first result (Sec. 4) studies the behavior where instead of regularizing the objective, Gaussian noise is added to the inputs. The main result is a sufficient condition for how the learning rate and noise can jointly change over time in order for SGD on the MSE error with noisy input to asymptotically converge to the same solution as regular gradient descent without noisy input.

The second result (Sec. 5) is slightly more general in that is considers the case where the noise can be an isotropic Gaussian where the variance changes over time. Again, a result is given for how the learning rate interacts with the data in order to asymptotically converge to the unregularized solution. This is first studied in Thm 5.1 then assuming power-law decay in the noise in Thm. 5.2. It should be emphasized that though these are asymptotic guarantees, the results give asymptotic *rates* of convergence. In my opinion this is a significant strength of the results that was not emphasized by the reviewers.

The third result (Sec. 6) studies SGD for least-squares linear models where the stochasticity is due to data subsampling only. The fraction of subsampled data may change over time.

The primary sentiment from reviewers was that the mathematical complexity of the paper meant that they could not understand it or give a fair review. (More on this below.) For this reason, and because the overall reviews are somewhat borderline, I read the paper in detail. A specific concern raised by two reviewers was that the paper first presents a very general framework but then studies very restricted specific problems. Some reviewers felt that the paper was very well-written, while others felt it was poorly written. There are no experiments.

For my part, I mostly concur that the paper is well-written (albeit quite technical). However, I agree with the concern from reviewers that the technical results all concern extremely restricted settings, and it's not clear what value the extremely general setup brings. I also find the title of the paper a bit puzzling. For specifics of the results, the practical value of Sections 4 and 5 is unclear. It's well-known that adding data noise is exactly equivalent to adding ridge regularization when doing linear regression. But ridge regularized linear regression would be a non-stochastic problem. So what is the value of studying the convergence rates in this case? The paper never makes this clear.

I have concerns about the exponential convergence rate in Thm. 6.1. The paper claims that an exponential convergence rate for SGD has been extensively studied. I do not believe this is true. In general SGD does not have an exponential convergence rate. There are modified methods like SAG that achieve this on finite data sets, but that's not what's studied here. The paper cites two papers: The first is Bottou et al. (2018). This is a lengthy review, with no specific reference given. I am familiar with it and also spent time searching but could not find a specific result. Ma et al. (2018) is also cited. This indeed gives an exponential convergence rate but assuming that at the optimum the loss for all datapoints is zero! No such assumption is made in the submitted paper, and the issue is not further discussed. This is cause for grave concern.
Decision: Reject