Year: 2020

Abstract:
We study mini-batch stochastic gradient descent (SGD) dynamics under linear regression and deep linear networks by focusing on the variance of the gradients only given the initial weights and mini-batch size, which is the first study of this nature. In the linear regression case, we show that in each iteration the norm of the gradient is a decreasing function of the mini-batch size b and thus the variance of the stochastic gradient estimator is a decreasing function of b. For deep neural networks with L2 loss we show that the variance of the gradient is a polynomial in 1{b. The results theoretically back the important intuition that smaller batch sizes yield larger variance of the stochastic gradients and lower loss function values which is a common believe among the researchers. The proof techniques exhibit a relationship between stochastic gradient estimators and initial weights, which is useful for further research on the dynamics of SGD. We empirically provide insights to our results on various datasets and commonly used deep network structures. We further discuss possible extensions of the approaches we build in studying the generalization ability of the deep learning models.

heading: 1 INTRODUCTION
text: Deep learning models have achieved great success in a variety of tasks including natural language processing, computer vision, and reinforcement learning (Goodfellow et al., 2016). Despite their practical success, there are only limited studies of the theoretical properties of deep learning; see survey papers (Sun, 2019; Fan et al., 2019) and references therein. The general problem underlying deep learning models is to optimize (minimize) a loss function, defined by the deviation of model predictions on data samples from the corresponding true labels. The prevailing method to train deep learning models is the mini-batch stochastic gradient descent algorithm and its variants (Bottou, 1998; Bottou et al., 2018). SGD updates model parameters by calculating a stochastic approximation of the full gradient of the loss function, based on a random selected subset of the training samples called a mini-batch.
It is well-accepted that selecting a large mini-batch size reduces the training time of deep learning models, as computation on large mini-batches can be better parallelized on processing units. For example, Goyal et al. (2017) scale ResNet-50 (He et al., 2016) from a mini-batch size of 256 images and training time of 29 hours, to a larger mini-batch size of 8,192 images. Their training achieves the same level of accuracy while reducing the training time to one hour. However, noted by many researchers, larger mini-batch sizes suffer from a worse generalization ability (LeCun et al., 2012; Keskar et al., 2017). Therefore, many efforts have been made to develop specialized training procedures that achieve good generalization using large mini-batch sizes (Hoffer et al., 2017; Goyal et al., 2017). Smaller batch sizes have the advantage of allegedly offering better generalization (at the expense of a higher training time).
The focus of this study is on the behavior of SGD subject to the conditions on the initial point. This is different from previous results which analyze SGD via stringing one-step recursions together. The dynamics of SGD are not comparable if we merely consider the one-step behavior, as the model parameters change iteration by iteration. Therefore, fixing the initial weights and the learning rate can give us a fair view of the impact of different mini-batch sizes on the dynamics of SGD. We hypothesize that, given the same initial point, smaller sizes lead to lower training loss and, unfortunately,
decrease stability of the algorithm on average. The latter follows from the fact that the smaller is the batch size, more stochasticity and volatility is introduced. After all, if the batch size equals to the number of samples, there is no stochasticity in the algorithm. To this end, we conjecture that the variance of the gradient in each iteration is a decreasing function of the mini-batch size. The conjecture is the focus of the work herein.
Variance correlates to many other important properties of SGD dynamics. For example, there is substantial work on variance reduction methods (Johnson & Zhang, 2013; Allen-Zhu & Hazan, 2016; Wang et al., 2013) which show great success on improving the convergence rate by controlling the variance of the stochastic gradients. Mini-batch size is also a key factor deciding the performance of SGD. Some research focuses on how to choose an optimal mini-batch size based on different criteria (Smith & Le, 2017; Gower et al., 2019). However, these works make strong assumptions on the loss function properties (strong or point or quasi convexity, or constant variance near stationary points) or about the formulation of the SGD algorithm (continuous time interpretation by means of differential equations). The statements are approximate in nature and thus not mathematical claims. The theoretical results regarding the relationship between the mini-batch size and the variance (and other performances, like loss and generalization ability) of the SGD algorithm applied to general machine learning models are still missing. The work herein partially addresses this gap by showing the impact of the mini-batch size on the variance of gradients in SGD. We further discuss possible extensions of the approaches we build in studying the generalization ability.
We are able to prove the hypothesis about variance in the convex linear regression case and to show significant progress in a deep linear neural network setting with samples based on a normal distribution. In this case we show that the variance is a polynomial in the reciprocal of the mini-batch size and that it is decreasing if the mini-batch size is larger than a threshold (further experiments reveal that this threshold can be as small as 2). The increased variance as the mini-batch size decreases should also intuitively imply convergence to lower training loss values and in turn better prediction and generalization ability (these relationships are yet to be confirmed analytically; but we provide empirical evidence to their validity).
The major contributions of this paper are as follows.
• For linear regression, we show that in each iteration the norm of any linear combination of sample-wise gradients is a decreasing function of the mini-batch size b (Theorem 1). As a special case, the variance of the stochastic gradient estimator and the full gradient at the iterate in step t are also decreasing functions of b at any iteration step t (Theorem 2). In addition, the proof provides a recursive relationship between the norm of gradients and the model parameters at each iteration (Lemma 2). This recursive relationship can be used to calculate any quantity related to the full/stochastic gradient or loss at any iteration with respect to the initial weights.
• For the deep linear neural network with L2-loss and samples drawn from a normal distribution, we take two-layer linear network as an example and show that in each iteration step t the trace of any product of the stochastic gradient estimators and weight matrices is a polynomial in 1{b with coefficients a sum of products of the initial weights (Theorem 3). As a special case, the variance of the stochastic gradient estimator is a polynomial in 1{bwithout the constant term (Theorem 4) and therefore it is a decreasing function of b when b is large enough (Theorem 5). The results and proof techniques can be easily extended to general deep linear networks. As a comparison, other papers that study theoretical properties of two-layer networks either fix one layer of the network, or assume the over-parameterized property of the model and they study convergence, while our paper makes no such assumptions on the model capacity. The proof also reveals the structure of the coefficients of the polynomial, and thus serving as a tool for future work on proving other properties of the stochastic gradient estimators.
• The proofs are involved and require several key ideas. The main one is to show a more general result than it is necessary in order to carry out the induction. The induction is on time step t. The key idea is to show a much more general result that lets us carry out induction. New concepts and definitions are introduced in order to handle the more general case. Along the way we show a result of general interest establishing expectation of several rank one matrices sampled from a normal distribution intertwined with constant matrices.
• We verify the theoretical results on various datasets and provide further understanding. We further empirically show that the results extend to other widely used network structures and hold for all choices of the mini-batch sizes. We also empirically verify that, on average, in each iteration the loss function value and the generalization ability (measured by the gap between accuracy on the training and test sets) are all decreasing functions of the minibatch size.
In conclusion, we study the dynamics of SGD under linear regression and a two-layer linear network setting by focusing on the decreasing property of the variance of stochastic gradient estimators with respect to the mini-batch size. The proof techniques can also be used to derive other properties of the SGD dynamics in regard to the mini-batch size and initial weights. To the best of authors’ knowledge, the work is the first one to theoretically study the impact of the mini-batch size on the variance of the gradient subject to the conditions on the initial weights, under mild assumptions on the network and the loss function. We support our theoretical results by experiments. We further experiment on other state-of-the-art deep learning models and datasets to empirically show the validity of the conjectures about the impact of mini-batch size on average loss, average accuracy and the generalization ability of the model.
The rest of the manuscript is structured as follows. In Section 2 we review the literature while in Section 3 we present the theoretical results on how mini-batch sizes impact the variance of stochastic gradient estimators, under different models including linear regression and deep linear networks. Section 4 introduces (part of) the experiments that verify our theorems and provide further insights into the impact of the mini-batch sizes on SGD performance. We defer the complete experimental details to Appendix A and the proofs of the theorems and other technical details to to Appendix B.

heading: 2 LITERATURE REVIEW
text: Stochastic gradient descent type methods are broadly used in machine learning (Bottou, 1991; LeCun et al., 1998; Bottou et al., 2018). The performance of SGD highly relies on the choice of the mini-batch size. It has been widely observed that choosing a large mini-batch size to train deep neural networks appears to deteriorate generalization (LeCun et al., 2012). This phenomenon exists even if the models are trained without any budget or limits, until the loss function value ceases to improve (Keskar et al., 2017). One explanation for this phenomenon is that large mini-batch SGD produces “sharp” minima that generalize worse (Hochreiter & Schmidhuber, 1997; Keskar et al., 2017). Specialized training procedures to achieve good performance with large mini-batch sizes have also been proposed (Hoffer et al., 2017; Goyal et al., 2017).
It is well-known that SGD has a slow asymptotic rate of convergence due to its inherent variance (Johnson & Zhang, 2013). Variants of SGD that can reduce the variance of the stochastic gradient estimator, which yield faster convergence, have also been suggested. The use of the information of full gradients to provide variance control for stochastic gradients is addressed in Johnson & Zhang (2013); Roux et al. (2012); Shalev-Shwartz & Zhang (2013). The works in Lei et al. (2017); Li et al. (2014); Schmidt et al. (2017) further improve the efficiency and complexity of the algorithm by carefully controling the variance.
There is prior work focusing on studying the dynamics of SGD. Neelakantan et al. (2015) propose to add isotropic white noise to the full gradient to study the “structured” variance. The works in Li et al. (2017); Mandt et al. (2017); Jastrzebski et al. (2017) connect SGD with stochastic differential equations to explain the property of converged minima and generalization ability of the model. Smith & Le (2017) propose an “optimal” mini-batch size which maximizes the test set accuracy by a Bayesian approach. The Stochastic Gradient Langevin Dynamics (SGLD, a variant of SGD) algorithm for non-convex optimization is studied in Zhang et al. (2017); Mou et al. (2018).
In most of the prior work about the convergence of SGD, it is assumed that the variance of stochastic gradient estimators is upper-bounded by a linear function of the norm of the full gradient, e.g. Assumption 4.3 in Bottou et al. (2018). Gower et al. (2019) give more precise bounds of the variance under different sampling methods and Khaled & Richtárik (2020) extend them to smooth non-convex regime. These bounds are still dependent on the model parameters at the corresponding iteration. To the best of the authors’ knowledge, there is no existing result which represents the variance of
stochastic gradient estimators only using the initial weights and the mini-batch size. This paper partially solves this problem.

heading: 3 ANALYSIS
text: Mini-batch SGD is a lighter-weight version of gradient descent. Suppose that we are given a loss function Lpwq where w is the collection (vector, matrix, or tensor) of all model parameters. At each iteration t, instead of computing the full gradient ∇wLpwtq, SGD randomly samples a mini-batch set Bt that consists of b “ |Bt| training instances and sets wt`1 Ð wt ´ αt∇wLBtpwtq, where the positive scalar αt is the learning rate (or step size) and ∇wLBtpwtq denotes the stochastic gradient estimator based on mini-batch Bt. An important property of the stochastic gradient estimator ∇wLBtpwtq is that it is an unbiased estimator, i.e. E∇wLBtpwtq “ ∇wLpwtq, where the expectation is taken over all possible choices of mini-batch Bt. However, it is unclear what is the value of var p∇wLBtpwtqq fi E }∇wLBtpwtq}
2 ´ }E∇wLBtpwtq} 2. Intuitively, we should have var p∇wLBtpwtqq 9 n 2
b var p∇wLpwtqq, where n is the number of training samples and stochasticity on the right-hand side comes from mini-batch samples behind wt (Smith & Le, 2017; Gower et al., 2019). However, even the quantities∇wLpwtq and var p∇wLpwtqq are still challenging to compute as we do not have direct formulas of their precise values. Besides, as we choose different b’s, their values are not comparable as we end up with different wt’s.
A plausible idea to address these issues is to represent E∇wLBtpwtq and var p∇wLBtpwtqq using the fixed and known quantities w0, b, t, and αt. In this way, we can further discover the properties, like decreasing with respect to b, of E∇wLBtpwtq and var p∇wLBtpwtqq. The biggest challenge is how to connect the quantities in iteration t with those of iteration 0. This is similar to discovering the properties of a stochastic differential equation at time t given only the dynamics of the stochastic differential equation and the initial point.
In this section, we address these questions under two settings: linear regression and a deep linear network. In Section 3.1 with a linear regression setting, we provide explicit formulas for calculating any norm of the linear combination of sample-wise gradients. We therefore show that the var p∇wLBtpwtqq is a decreasing function of the mini-batch size b. In Section 3.2 with a deep linear network setting and samples drawn from a normal distribution, we show that any trace of the product of weight matrices and stochastic gradient estimators is a polynomial in 1{b with finite degree. We further prove that var p∇wLBtpwtqq is a decreasing function of the mini-batch size b ą b0 for some constant b0.
For a random matrix M , we define var pMq fi E }vecpMq}2´}EvecpMq}2 where vecpMq denotes the vectorization of matrixM . We denote rm : ns fi tm,m`1, . . . , nu ifm ď n, andH otherwise. We use rns fi r1 : ns as an abbreviation. For clarity, we use the superscript b to distinguish the variables with different choices of the mini-batch size b. In each iteration t, we use Bbt to denote the batch of samples (or sample indices) to calculate the stochastic gradient. We denote by Fbt the filtration of information before calculating the stochastic gradient in the t-th iteration, i.e. Fbt fi
w0,Bb0, . . . ,Bbt´1 ( .

heading: 3.1 LINEAR REGRESSION
text: In this subsection, we discuss the dynamics of SGD applied in linear regression. Given data points px1, y1q, ¨ ¨ ¨ , pxn, ynq, where xi P Rp and yi P R, we define the loss function to be Lpwq “ 1 n řn i“1 Lipwq “ 1 n řn i“1 1 2 ` wTxi ´ yi ˘2
, where w P Rp are the model parameters. We consider minimizingLpwq by mini-batch SGD. Note that the bias term in the general linear regression models is omitted, however, adding the bias term does not change the result of this section. Formally, we first choose a mini-batch size b and initial weights w0. In each iteration t, we sample Bbt , a subset of rns with cardinality b, and update the parameters bywbt`1 “ wbt´αtgbt , where gbt “ 1b ř iPBbt ∇Li ` wbt ˘ .
We first show the relationship between the variance of stochastic gradient gbt and the full gradient ∇L `
wbt ˘ and sample-wise gradient ∇Li ` wbt ˘ , i P rns, derived by considering all possible choices
of the mini-batch Bbt . Readers should note that Lemma 1 actually holds for all models with L2-loss, not merely linear regression (since in the proof we do not need to know the explicit form of Lipwq).
Lemma 1. Let cb fi n´bbpn´1q ě 0. For any matrix A P R pˆp we have var ` Agbt ˇ ˇFbt ˘ “ E ” ›
›Agbt › ›
2 ˇ
ˇ ˇ Fbt
ı
´ › ›A∇L ` wbt ˘ › › 2 “ cb ´ 1 n řn i“1 › ›A∇Li ` wbt ˘ › › 2 ´ › ›A∇L ` wbt ˘ › › 2 ¯ .
Lemma 1 provides a bridge to connect the norm and variance of gbt with sample-wise gradients ∇Li ` wbt ˘ , i P rns. Therefore, if we can further discover the properties of ∇Li ` wbt ˘
, i P rns, we are able to calculate the variance of gbt . Lemma 2 addresses this problem by showing the relationship between any linear combination of∇Li ` wbt ˘ ’s and∇Li ` wbt´1 ˘ ’s.
Lemma 2. For any set of square matrices tA1, ¨ ¨ ¨ , Anu P Rpˆp, if we denote A “ řn i“1Aixix T i , then we have E ” › › řn i“1Ai∇Li ` wbt`1 ˘ › › 2 ˇ ˇ ˇ F0 ı “ E ” › › řn i“1Bi∇Li ` wbt ˘ › › 2 ˇ ˇ ˇ F0 ı
` α2t cb n2 řn k“1 řn l“1 E ” › › řn i“1B kl i ∇Li ` wbt ˘ › › 2 ˇ ˇ ˇ F0 ı , where Bi “ Ai ´ αtn A; B kl i “ A if i “ k, i ‰ l, Bkli “ A if i “ l, i ‰ k, and Bkli equals the zero matrix, otherwise.
Lemma 2 provides the tool to reduce the iteration t by one. Therefore, we can easily use it to recursively calculate the norm of any linear combinations of the sample-wise gradients, for all iterations t. Combining the fact that cb is a decreasing function of b, we are able to show Theorem 1.
Theorem 1. For any t P N and any matrices Ai P Rpˆp, i P rns, E ” › › řn i“1Ai∇Li ` wbt ˘ › › 2 ˇ ˇ ˇ F0 ı is a decreasing function of b for b P rns.
Theorem 1 states that the norm of any linear combinations of the sample-wise gradients is a decreasing function of b. Combining Lemma 1 which connects the variance of gbt with the linear combination of∇Li ` wbt ˘ ’s, and the fact that∇L ` wbt ˘ “ 1n řn i“1∇Li ` wbt ˘ , we have Theorem 2.
Theorem 2. Fixing initial weightsw0, both var ` Bgbt ˇ ˇF0 ˘ and var ` B∇L ` wbt ˘ ˇ ˇF0 ˘
are decreasing functions of mini-batch size b for all b P rns, t P N, and all square matrices B P Rpˆp.
As a special case, Corollary 1 guarantees that the variance of the stochastic gradient estimator is a decreasing function of b.
Corollary 1. Fixing initial weights w0, both var ` gbt ˇ ˇF0 ˘ and var ` ∇L ` wbt ˘ ˇ ˇF0 ˘
are decreasing functions of mini-batch size b for all b P rns and t P N.
In conclusion, we provide a framework for calculating the explicit value of variance of the stochastic gradient estimators and the norm of any linear combination of sample-wise gradients. We further show that the variance of both the full gradient and the stochastic gradient estimator are a decreasing function of the mini-batch size b. Readers should note that the framework here is not limited to showing the decreasing property of the variance, but can also be used in many other circumstance. For example, we can use Lemma 2 to induct on t and easily show that E ” › ›
řn i“1Ai∇Li ` wbt ˘ › ›
2 ˇ
ˇ ˇ F0
ı
is a polynomial of 1b with degree at most t and estimate the coefficients therein.

heading: 3.2 DEEP LINEAR NETWORKS WITH ONLINE SETTING
text: In this section, we study the dynamics of SGD on deep linear networks. We take the two-layer linear network as an example while the results and proofs can be easily extended to deep linear network with any depth (see Appendix B.3 for more details). We consider the population loss Lpwq “ Ex„N p0,Ipq ” 1 2 }W2W1x´W ˚ 2 W ˚ 1 x} 2 ı under the teacher-student learning framework (Hinton et al., 2015) with w “ pW1,W2q a tuple of two matrices. Here W1 P Rp1ˆp and W2 P Rp2ˆp1 are parameter matrices of the student network and W˚1 and W˚2 are the fixed ground-truth parameters of the teacher network. We use online SGD to minimize the population loss Lpwq. Formally, we first choose a mini-batch size b and initial weight matrices tW0,1,W0,2u. In each iteration t, we draw b independent and identically distributed samples xt,i, i P rbs from N p0, Ipq to form the mini-batch Bbt and update the weight matrices by W bt`1,1 “W bt,1´αtgbt,1 and
W bt`1,2 “W bt,2 ´ αtgbt,2, where
g b t,1 “
1
b
b ÿ i“1 ∇ Wbt,1 ˆ 1 2 › › › W b t,2W b t,1xt,i ´W ˚ 2 W ˚ 1 xt,i › › › 2 ˙ “ 1 b b ÿ i“1 W b t,2 T ´ W b t,2W b t,1 ´W ˚ 2 W ˚ 1 ¯ xt,ix T t,i, (1)
g b t,2 “
1
b
b ÿ i“1 ∇ Wbt,2 ˆ 1 2 › › › W b t,2W b t,1xt,i ´W ˚ 2 W ˚ 1 xt,i › › › 2 ˙ “ 1 b b ÿ i“1 ´ W b t,2W b t,1 ´W ˚ 2 W ˚ 1 ¯ xt,ix T t,iW b t,1 T . (2)
The derivation follows from the formulas in Petersen & Pedersen (2012). In the following, we use Wbt “W bt,2W bt,1´W˚2 W˚1 to denote the gap between the product of model weights and ground-truth weights.
For ease of developing our proofs, we first introduce the definition of a multiplicative term in Definition 1. Intuitively, a multiplicative term is a matrix which equals to the product of its parameter matrices and constant matrices (and their transpose). The degree of a matrix A in a multiplicative term M is the number of appearance of A and AT in M . The degree of M is exactly the number of appearances of all weight matrices in M .
Definition 1. For any set of matrices S, we denote sS “ S Y tMT : M P Su. Given a set of parameter matrices X “ tX1, X2, ¨ ¨ ¨ , Xnvu and constant matrices C “ tC1, C2, ¨ ¨ ¨ , Cncu, we say that a matrix M is a multiplicative term of parameter matrices X and constant matrices C if it can be written in the form of M “ MpX , Cq “
śk i“1Ai, where Ai P sX Y sC. We write
degpXj ;Mq “ řk i“1 ` 1 tXj “ Aiu ` 1 Xj “ ATi (˘ , j P rnvs as the degree of parameter matrix Xj in M , degpCj ;Mq “ řk i“1 ` 1 tCj “ Aiu ` 1 Cj “ ATi (˘
, j P rncs as the degree of constant matrix Cj in M , and degpMq “ řk i“1 1 Ai P sX ( “ řnv j“1 degpXj ;Mq as the total degree of the parameter matrices of M .
As pointed out in the Section 1, the difficulty of studying the dynamics of SGD is how to connect the quantities in iteration twith fixed variables, like initial weightsW0,1,W0,2 and mini-batch size b. We overcome this challenge by carefully calculating the relationship between gbt`1,i and g b t,i, i “ 1, 2 so that we can reduce the iteration t step by step. With the help of Lemmas 8 and 9 in Appendix B.2, we can represent gbt`1,i, i “ 1, 2 using multiplicative terms of gbt,i, i “ 1, 2 and some other constant matrices. Theorem 3 precisely gives the representation in the form of a polynomial of 1b and the coefficients as the sum of multiplicative terms of parameter matrices
W b0,1,W b 0,2
(
and constant matrices tW˚1 ,W˚2 u. Theorem 3. Given t ě 0, for any multiplicative terms Mi, i P r0 :ms of parameter matrices
gbt,1, g b t,2
(
and constant matrices W bt,1,W b t,2,W ˚ 1 ,W ˚ 2 (
with degree di, respectively, we denote M “
śm i“1 tr pMiqM0, d “ řm i“0 di and d 1 “ řm i“0 ` deg ` W bt,1;Mi ˘ ` degpW bt,2;Miq ˘
. There exists a set of multiplicative terms
Mkij , i P rmks, j P r0 :mkis , k P r0 : qs ( of parameter matrices
W b0,1,W b 0,2
( and constant matrices tW˚1 ,W˚2 u such that E rM |F0s “ N0 `N1 1b ` ¨ ¨ ¨ `Nq 1 bq ,
where Nk “ řmk i“1 śmki j“1 tr ` Mkij ˘ Mki0, k P r0 : qs. Here mk,mki and q ď 12 p3 t`1 ´ 1qd` 12 p3 t ´ 1qd1 are constants independent of b, and
řmki j“0 deg ` Mkij ˘ ď 3tp3d` d1q.
As a special case of Theorem 3, Theorem 4 shows that the variance of the stochastic gradient estimators is also a polynomial of 1b but with no constant term. This backs the important intuition that the variance is approximately inversely proportional to the mini-batch size b. Besides, note that if we consider bÑ8, intuitively we should have var `
gbt,i ˇ ˇF0 ˘ Ñ 0, i “ 1, 2. This observation aligns with the statement of Theorem 4.
Theorem 4. Given t ě 0, value var ` gbt,i ˇ ˇF0 ˘ , i “ 1, 2 can be written as a polynomial of 1b with degree at most 2 ¨ 3t with no constant term. Formally, we have var `
gbt,i ˇ ˇF0 ˘ “ β1 1b ` ¨ ¨ ¨ ` βr 1 br ,
where r ď 2 ¨ 3t`1 and each βi is a constant independent of b.
One should note that the polynomial representation of var ` gbt,i ˇ ˇF0 ˘ , i “ 1, 2 does not have the constant term. Therefore, to show the that the variance is a decreasing function of b, we only need to show that the leading coefficient β1 is non-negative. This is guaranteed by the fact that variance is always non-negative. We therefore have Theorem 5.
Theorem 5. Given t P N, there exists a constant b0 such that for all b ě b0 function var `
gbt,i ˇ ˇF0 ˘ , i “ 1, 2 is a decreasing function of b.
The constant b0 is the largest root of the equation β1br´1 ` β2br´2 ` ¨ ¨ ¨ ` βr “ 0. See the proof of Theorem 5 in Appendix B.2 for more details. Although we cannot calculate the precise value of b0, we verify that b0 is smaller than 1 in many experiments. From the proofs we conclude that the scale of each βi is of the order O p}M}q, where M is a multiplicative term of parameter matrices tW0,1,W0,2,W˚1 ,W˚2 u and constant matrixH with degree 2 ¨ 3t`1. Unlike the linear regression setting where we can iteratively calculate the variance by Lemma 2, the closed form expressions for the variance of the stochastic gradients in the deep linear network setting are much harder to calculate. However, we are able to iteratively deducing t one by one and provide a polynomial representation for any multiplicative terms of parameter matrices
gbt,i,W b t,i, i “ 1, 2
(
and constant matrices tW˚1 ,W˚2 u using only the initial weights W0,1,W0,2 and the mini-batch size b. As we further study the polynomial representation of var `
gbt,i ˇ ˇF0 ˘ , i “ 1, 2, we are also able to show the decreasing property of the variance of stochastic gradient estimators with respect to b.

heading: 4 EXPERIMENTS
text: In this section, we present numerical results to support the theorems in Section 3 and provide further insights into the impact of the mini-batch size on the dynamics of SGD. The experiments are conducted on four datasets and models that are relatively small due to the computational cost of using large models and datasets. We only report the results on the MNIST dataset here due to the limited space. A complete empirical study is deferred in Appendix A.
For all experiments, we perform mini-batch SGD multiple times starting from the same initial weights and following the same choice of the learning rates and other hyper-parameters, if applicable. This enables us to calculate the variance of the gradient estimators and other statistics in each iteration, where the randomness comes only from different samples of SGD.

heading: 4.1 RESULTS ON MNIST DATASET
text: The MNIST dataset is to recognize digits in handwritten images of digits. We use all 60,000 training samples and 10,000 validation samples of MNIST. We build a three-layer fully connected neural network with 1024, 512 and 10 neurons in each layer. For the two hidden layers, we use the ReLU activation function. The last layer is the softmax layer which gives the prediction probabilities for the 10 digits. We use mini-batch SGD to optimize the cross-entropy loss of the model. The model deviates from our analytical setting since it has non-linear activations, it has the cross-entropy loss function (instead of L2), and empirical loss (as opposed to population). MNIST is selected due to its fast training and popularity in deep learning experiments. The goal is to verify the results in this different setting and to back up our hypotheses.
As shown in Figure 1(a), we run SGD with two batch sizes 64 and 128 on five different initial weights with 50 runs for each initial point. This plot shows that, even the smallest value of the variance among the five different initial weights with a mini-batch size of 64, is still larger than the largest variance of mini-batch size 128. We observe that the sensitivity to the initial weights is not large. This plot also empirically verifies our conjecture in the introduction that the variance of the stochastic gradient estimators is a decreasing function of the mini-batch size, for all iterations of SGD in a general deep learning model.
In addition, we also conjecture that there exists the decreasing property for the expected loss, error and the generalization ability with respect to the mini-batch size. Figure 1(b) shows that the expected loss (again, randomness comes from different runs of SGD through the different mini-batches with the same initial weights and learning rates) on the training set is a decreasing function of b. However, this decreasing property does not hold on the validation set when the loss tends to be stable or increasing, in other words, the model starts to be over-fitting. We hypothesize that this is because the learned weights start to bounce around a local minimum when the model is over-fitting. As the larger mini-batch size brings smaller variance, the weights are closer to the local minimum found by SGD, and therefore yield a smaller loss function value. Figure 1(c) shows that both the expected error on training and validation sets are decreasing functions of b.
Figure 1(d) exhibits a relationship between the model’s generalization ability and the mini-batch size. As suggested by Simard et al. (2013), we build a test set by distorting the 10,000 images of the validation set. The prediction accuracy is obtained on both training and test sets and we calculate the gap between these two accuracies every 100 epochs. We use this gap to measure the model generalization ability (the smaller the better). Figure 1(d) shows that the gap is an increasing function of b starting at epoch 500, which partially aligns with our conjecture regarding the relationship between the generalization ability and the mini-batch size. We test this on multiple choices of the hyper-parameters which control the degree of distortion in the test set and this pattern remains clear.

heading: 5 SUMMARY AND FUTURE WORK
text: We examine the impact of the mini-batch size on the dynamics of SGD. Our focus is on the variance of stochastic gradient estimators. For linear regression and a two-layer linear network, we are able to theoretically prove that the variance conjecture holds. We further experiment on multiple models and datasets to verify our claims and their applicability to practical settings. Besides, we also empirically address the conjectures about the expected loss and the generalization ability.
A challenging research direction is to theoretically investigate the impact of the mini-batch size on the generalization ability. There are existing works studying the relationship between the variance of the stochastic gradients and the generalization ability (Gorbunov et al., 2020; Meng et al., 2016). Together with the tools developed herein, it would be possible to bridge the mini-batch size with the generalization ability of a neural network. We can further choose an optimal mini-batch size which minimizes the generalization ability by solving the polynomial equation if we have more precise estimations of the coefficients.
Another appealing direction is using our variance estimations to develop better variance reduction methods. As a results, the upper-bound of the variance decides the convergent rate of these algorithms. Researchers usually assume a much larger upper-bound at each iteration, like a linear function of the norm of the full gradient. With the help of our techniques, we should calculate the variance more precisely and further improve the algorithms.
Further interesting work is to extend our techniques to more complicated and sophisticated networks. Although the underlying model of this paper corresponds to deep linear network networks, we are able to show a deeper relationship between the variance and the mini-batch size, the polynomial in 1{b, while the common knowledge is simply that the variance is proportional to 1{b. The extension to other optimization algorithms, like Adam and Gradient Boosting Machines, are also very attractive. We hope our theoretical framework can serve as a tool for future research of this kind.

heading: A EXPERIMENTS
text: In this section, we present numerical results to support the theorems in Section 3, to backup the hypotheses discussed in the introduction, and provide further insights into the impact of the minibatch size on the dynamics of SGD. The experiments are conducted on four datasets and models that are relatively small due to the computational cost of using large models and datasets.
Remark: We cannot present the complete numerical results in the main paper due to the space limit. Therefore, we move the whole experimental section to Appendix. In order to keep a smooth reading, some of the content is overlapping with Section 4.

heading: A.1 DATASETS AND SETTINGS
text: For all experiments, we perform mini-batch SGD multiple times starting from the same initial weights and following the same choice of the learning rates and other hyper-parameters, if applicable. This enables us to calculate the variance of the gradient estimators and other statistics in each iteration, where the randomness comes only from different samples of SGD. The learning rate αt is selected to be inversely proportional to iteration t, or fixed, depending on the task at hand.
All models are implemented using PyTorch version 1.4 (Paszke et al., 2019) and trained on NVIDIA 2080Ti/1080 GPUs. We have also tested several other random initial weights and ground-truth weights, and learning rates, and the results and conclusions are similar and not presented.

heading: A.1.1 GRADUATE ADMISSION DATASET
text: The Graduate Admission dataset1 (Acharya et al., 2019) is to predict the chance of a graduate admission using linear regression. The dataset contains 500 samples with 6 features and is normalized by mean and variance of each feature. This is a popular regression dataset with clean data. We build a linear regression model to predict the chance of acceptance (we include the intercept term in the model) and minimize the empirical L2 loss using mini-batch SGD, as stated in Section 3.1.
For the experiment in Figure 2(a), we randomly select an initial weight vectors w0 and run SGD for 2,000 iterations where it appears to converge. We record all statistics at every iteration. There are in total 1,000 runs behind each observation which yields a p-value lower than 0.05. As for Figure 2(b), we select 20 different b’s and run SGD from the same initial point for 40 iterations. There are in total of 200,000 runs to make sure the p-value of all statistics are lower than 0.05. In all experiments, the learning rate is chosen to be αt “ 12t , t P r2000s because this rate yields a theoretical convergence guaranteed (factor 1/2 has been fine tuned). The purpose of this experiment is to empirically study the rate of decrease of the variance. The theoretical study exhibited in Section 3.1 establishes the non-increasing property but it does not state anything about the rate of decrease.

heading: A.1.2 SYNTHETIC DATASET
text: We build a synthetic dataset of standard normal samples to study the setting in Section 3.2. We fix the teacher network with 64 input neurons, 256 hidden neurons and 128 output neurons. We optimize the population L2 loss by updating the two parameter matrices of the student network using online SGD, as stated in Section 3.2. In this case we have proved the functional form of the variance as a function of b and show the decreasing property of the variance of the stochastic gradient estimators for large mini-batch sizes. However, we do not show the decreasing property for every b. With this experiment we confirm that the conjecture likely holds. In the experiment, we randomly select two initial weight matrices W0,1,W0,2 and the ground-truth weight matrices W˚1 ,W ˚ 2 . We run SGD for 1,000 iterations which appears to be a good number for convergence while there are 1,000 runs of SGD in total to again give a p-value below 0.05. We record all statistics at every iteration. The learning rate is chosen to be αt “ 110t , t P r1000s for the same reason as in the regression experiment.
1https://www.kaggle.com/mohansacharya/graduate-admissions

heading: A.1.3 MNIST DATASET
text: The MNIST dataset is to recognize digits in handwritten images of digits. We use all 60,000 training samples and 10,000 validation samples of MNIST. The images are normalized by mapping each entry to r´1, 1s. We build a three-layer fully connected neural network with 1024, 512 and 10 neurons in each layer. For the two hidden layers, we use the ReLU activation function. The last layer is the softmax layer which gives the prediction probabilities for the 10 digits. We use minibatch SGD to optimize the cross-entropy loss of the model. The model deviates from our analytical setting since it has non-linear activations, it has the cross-entropy loss function (instead of L2), and empirical loss (as opposed to population). MNIST is selected due to its fast training and popularity in deep learning experiments. The goal is to verify the results in this different setting and to back up our hypotheses.
We run SGD for 1,000 epochs on the training set which is enough for convergence. The learning rate is a constant set to 3 ¨ 10´3 (which has been tuned). For the experiment in Figure 5, there are in total 100 runs to give us the p-value below 0.05. For the experiment in Figure 4(a), we randomly select five different initial points and we have 50 runs for each initial point. For the experiment corresponding to Figure 4(b), we choose α “ 8 and σ “ 2 as in Simard et al. (2013). The initial weights and other hyper-parameters are chosen to be the same as in Figure 5.

heading: A.1.4 YELP REVIEW DATASET
text: The Yelp Review dataset from the Yelp Dataset Challenge (Zhang et al., 2015) contains 1,569,264 samples of customer reviews with positive/negative sentiment labels. We use 10,000 samples as our training set and 1,000 samples as the validation set. We use XLNet (Yang et al., 2019) to perform sentiment classification on this dataset. Our XLNet has 6 layers, the hidden size of 384, and 12 attention heads. There are in total 35,493,122 parameters. We intentionally reduce the number of layers and hidden size of XLNet and select a relatively small size of the training and validation sets since training of XLNet is very time-consuming (Yang et al. (2019) train on 512 TPU v3 chips for 5.5 days) and we need to train the model for multiple runs. This setting allows us to train our model in several hours on a single GPU card. We train the model using the Adam weight decay optimizer, and some other techniques, as suggested in Table 8 of Yang et al. (2019). This dataset represents sequential data where we further consider the hypotheses.
We randomly select a set of initial parameters and run Adam with two different mini-batch sizes of 32 and 64. For computational tractability reasons, for each mini-batch size there are in total of 100 runs and each run corresponds to 20 epochs. We record the variance of the stochastic gradient, loss and accuracy in every step of Adam. The statistics reported in Figure 6 are averaged through each epoch. In all experiments, the learning rate is set to be 4 ¨10´5 and the parameter of Adam is set to be 10´8 (these two have been tuned). The stochastic gradients of all parameter matrices are clipped with threshold 1 in each iteration. We use the same setup for the learning rate warm-up strategy as suggested in Yang et al. (2019). The maximum sequence length is set to be 128 and we pad the sequences with length smaller than 128 with zeros.

heading: A.2 DISCUSSION
text: As observed in Figure 2(a), under the linear regression setting with the Graduate Admission dataset, the variance of the stochastic gradient estimators and full gradients are all strictly decreasing functions of b for all iterations. This result verifies the theorems in Section 3.1. Figure 2(b) further studies the rate of decrease of the variance. From the proofs in Section 3.1 we see that var `
gbt ˇ ˇF0 ˘
is a polynomial of 1b with degree t` 1. Therefore, for every t, we can approximate this polynomial by sampling many different b’s and calculate the corresponding variances. We pick b to cover all numbers that are either a power of 2 or multiple of 40 in r2, 500s (there are a total of 21 such values) and fit a polynomial with degree 6 (an estimate from the analyses) at t “ 10, 20, 30, 40. Figure 2(b) shows the fitted polynomials. As we observe, the value var `
gbt ˇ ˇF0 ˘
(approximated by the value of the polynomial) is both decreasing with respect to the mini-batch size b and iteration t. Further, the rate of decrease in b is slower as the b increasing. This provides a further insight into the dynamics of training a linear regression problem with SGD.
Under the two-layer linear network setting with the synthetic dataset, Figure 3 verifies that the variance of the stochastic gradient estimators and full gradients are all strictly decreasing functions of b for all iterations. This figure also empirically shows that the constant b0 in Theorem 5 could be as small as b0 “ 4. In fact, we also experiment with the mini-batch size of 1 and 2, and the decreasing property remains to hold. We also test this on multiple choices of initial weights and learning rates and this pattern remains clear.
In aforementioned two experiments we use SGD in its original form by randomly sampling minibatches. In deep learning with large-scale training data such a strategy is computationally prohibitive and thus samples are scanned in a cyclic order which implies fixed mini-batches are processed many times. Therefore, in the next two datasets we perform standard “epoch” based training to empirically study the remaining two hypotheses discussed in the introduction (decreasing loss and error as a function of b) and sensitivity with respect to the initial weights. Note that we are using cross-entropy loss in the MNIST dataset and the Adam optimizer in the Yelp dataset and thus these experiments do not meet all of the assumptions of the analysis in Section 3.
As shown in Figure 4(a), we run SGD with two batch sizes 64 and 128 on five different initial weights. This plot shows that, even the smallest value of the variance among the five different initial weights with a mini-batch size of 64, is still larger than the largest variance of mini-batch size 128. We observe that the sensitivity to the initial weights is not large. This plot also empirically verifies our conjecture in the introduction that the variance of the stochastic gradient estimators is
a decreasing function of the mini-batch size, for all iterations of SGD in a general deep learning model.
In addition, we also conjecture that there exists the decreasing property for the expected loss, error and the generalization ability with respect to the mini-batch size. Figure 5(a) shows that the expected
loss (again, randomness comes from different runs of SGD through the different mini-batches with the same initial weights and learning rates) on the training set is a decreasing function of b. However, this decreasing property does not hold on the validation set when the loss tends to be stable or increasing, in other words, the model starts to be over-fitting. We hypothesize that this is because the learned weights start to bounce around a local minimum when the model is over-fitting. As the larger mini-batch size brings smaller variance, the weights are closer to the local minimum found by SGD, and therefore yield a smaller loss function value. Figure 5(b) shows that both the expected error on training and validation sets are decreasing functions of b.
Figure 4(b) exhibits a relationship between the model’s generalization ability and the mini-batch size. As suggested by (Simard et al., 2013), we build a test set by distorting the 10,000 images of the validation set. The prediction accuracy is obtained on both training and test sets and we calculate the gap between these two accuracies every 100 epochs. We use this gap to measure the model generalization ability (the smaller the better). Figure 4(b) shows that the gap is an increasing function of b starting at epoch 500, which partially aligns with our conjecture regarding the relationship between the generalization ability and the mini-batch size. We also test this on multiple choices of the hyper-parameters which control the degree of distortion in the test set and this pattern remains clear.
Figure 6 shows the similar phenomenon that the variance of stochastic estimators and the expected loss and error on both training and validation sets are decreasing functions of b even if we train XLNet using Adam. This example gives us confidence that the decreasing properties are not merely restricted on shallow neural networks or vanilla SGD algorithms. They actually appear in many advanced models and optimization methods.

heading: B LEMMAS AND PROOFS

heading: B.1 LEMMAS AND PROOFS OF RESULTS IN SECTION 3.1
text: For two matrices A,B with the same dimension, we define the inner product xA,By fi tr ` ATB ˘ .
Lemma 3. Suppose that fpxq and gpxq are both smooth, non-negative and decreasing functions of x P R. Then hpxq “ fpxqgpxq is also a non-negative and decreasing function of x.
Proof. It is obvious that hpxq is non-negative for all x. The first-order derivative of h is
h1pxq “ f 1pxqgpxq ` fpxqg1pxq ď 0,
and thus hpxq is also a decreasing function of x.
Proof of Lemma 1. Throughout the paper, We use Ckn “ n!k!pn´kq! to denote the combinatorial number. Note that
E ”
gbt ` gbt ˘T
ˇ
ˇ ˇ Fbt
ı “ 1 b2 E
»
–
ÿ
iPBbt
∇Li ` wbt ˘
ÿ
iPBbt
∇Li ` wbt ˘T
ˇ
ˇ
ˇ
ˇ
ˇ
ˇ
Fbt
fi
fl
“ 1 b2
˜
Cb´1n´1 Cbn n ÿ i“1 ∇Li ` wbt ˘ ∇Li ` wbt ˘T ` Cb´2n´2 Cbn ÿ i‰j ∇Li ` wbt ˘ ∇Lj ` wbt ˘T
¸
“ 1 b2
˜
b
n
n ÿ i“1 ∇Li ` wbt ˘ ∇Li ` wbt ˘T ` bpb´ 1q npn´ 1q ÿ i‰j ∇Li ` wbt ˘ ∇Lj ` wbt ˘T
¸
“ 1 b2
˜
bpn´ bq npn´ 1q
n ÿ i“1 ∇Li ` wbt ˘ ∇Li ` wbt ˘T ` bpb´ 1q npn´ 1q n ÿ i“1 ∇Li ` wbt ˘ n ÿ i“1 ∇Li ` wbt ˘T
¸
“ n´ b bnpn´ 1q
n ÿ i“1 ∇Li ` wbt ˘ ∇Li ` wbt ˘T ` pb´ 1qn bpn´ 1q∇L ` wbt ˘ ∇L ` wbt ˘T .
For any A P Rpˆp, we have
E ” ›
›Agbt › ›
2 ˇ
ˇ ˇ Fbt
ı “ E ” ` gbt ˘T ATAgbt
ˇ
ˇ ˇ Fbt
ı “ E ” tr ´ ` gbt ˘T ATAgbt
¯ ˇ
ˇ ˇ Fbt
ı
“ E ” tr ´
ATAgbt ` gbt ˘T
¯ ˇ
ˇ ˇ Fbt
ı
“ tr ´ ATAE ”
gbt ` gbt ˘T
ˇ
ˇ ˇ Fbt
ı¯
“ tr ˜
n´ b bnpn´ 1q
n ÿ i“1 ATA∇Li ` wbt ˘ ∇Li ` wbt ˘T ` pb´ 1qn bpn´ 1qA TA∇L ` wbt ˘ ∇L ` wbt ˘T
¸
“ n´ b bnpn´ 1q
n ÿ
i“1
› ›A∇Li ` wbt ˘ › › 2 ` pb´ 1qn bpn´ 1q › ›A∇L ` wbt ˘ › › 2
“ cb
˜
1
n
n ÿ
i“1
› ›A∇Li ` wbt ˘ › › 2 ´ › ›A∇L ` wbt ˘ › › 2
¸
` › ›A∇L ` wbt ˘ › › 2 .
Therefore, we have
var ` Agbt ˇ ˇFbt ˘
“ E ” ›
›Agbt › ›
2 ˇ
ˇ ˇ Fbt
ı
´ › ›E “ Agbt ˇ ˇFbt ‰ › ›
2
“ E ” ›
›Agbt › ›
2 ˇ
ˇ ˇ Fbt
ı
´ › ›A∇L ` wbt ˘ › ›
2
“ cb
˜
1
n
n ÿ
i“1
› ›A∇Li ` wbt ˘ › › 2 ´ › ›A∇L ` wbt ˘ › › 2
¸
.
Lemma 4. For any set of square matrices tA1, ¨ ¨ ¨ , Anu P Rpˆp, if we denote A “ řn i“1Aixix T i , then we have
E «› › ›
› ›
n ÿ i“1 Ai∇Li ´ w b t`1 ¯
› › › › › 2ˇ ˇ ˇ ˇ ˇ F0 ff “ E «› › › › › n ÿ
i“1 Bi∇Li
´
w b t
¯
› › › › › 2ˇ ˇ ˇ ˇ ˇ F0 ff ` α2t cb n2 n ÿ
k“1
n ÿ l“1 E «› › › › › n ÿ i“1 B kl i ∇Li ´ w b t ¯ › › › › › 2ˇ ˇ ˇ ˇ ˇ F0 ff .
Here Bi “ Ai ´ αtn A; B kl i “ A if i “ k, i ‰ l, Bkli “ A if i “ l, i ‰ k, and Bkli equals the zero
matrix, otherwise.
Proof of Lemma 4. Let Ci “ xixTi and C “ 1n řn i“1 Ci. For the given A1, . . . , An, we denote A “ řn i“1AiCi. Then we have
E
»
–
›
›
›
›
›
n ÿ i“1 Ai∇Li ` wbt`1 ˘
›
›
›
›
›
2 ˇ
ˇ
ˇ
ˇ
ˇ
ˇ
F0
fi
fl “ E
»
–E
»
–
›
›
›
›
›
n ÿ i“1 Ai∇Li ` wbt`1 ˘
›
›
›
›
›
2 ˇ
ˇ
ˇ
ˇ
ˇ
ˇ
Fbt
fi
fl
ˇ
ˇ
ˇ
ˇ
ˇ
ˇ
F0
fi
fl
“ E
»
–E
»
–
›
›
›
›
›
n ÿ i“1 Ai ` xTi w b t`1 ´ yi ˘ xi
›
›
›
›
›
2 ˇ
ˇ
ˇ
ˇ
ˇ
ˇ
Fbt
fi
fl
ˇ
ˇ
ˇ
ˇ
ˇ
ˇ
F0
fi
fl
“ E
»
–E
»
–
›
›
›
›
›
n ÿ i“1 Ai ` xTi ` wbt ´ αtgbt ˘ ´ yi ˘ xi
›
›
›
›
›
2 ˇ
ˇ
ˇ
ˇ
ˇ
ˇ
Fbt
fi
fl
ˇ
ˇ
ˇ
ˇ
ˇ
ˇ
F0
fi
fl
“ E
»
–E
»
–
›
›
›
›
›
n ÿ i“1 Ai∇Li ` wbt ˘ ´ αtAgbt
›
›
›
›
›
2 ˇ
ˇ
ˇ
ˇ
ˇ
ˇ
Fbt
fi
fl
ˇ
ˇ
ˇ
ˇ
ˇ
ˇ
F0
fi
fl
“ E
»
–
›
›
›
›
›
n ÿ i“1 Ai∇Li ` wbt ˘
›
›
›
›
›
2 ˇ
ˇ
ˇ
ˇ
ˇ
ˇ
F0
fi fl´ 2αtE « E «C n ÿ
i“1 Ai∇Li
` wbt ˘ , Agbt
G ˇ
ˇ
ˇ
ˇ
ˇ
Fbt
ff ˇ
ˇ
ˇ
ˇ
ˇ
F0
ff
` α2tE ” E ” › ›Agbt › › 2 ˇ ˇ ˇ Fbt ı ˇ ˇ ˇ F0 ı
“ E
»
–
›
›
›
›
›
n ÿ i“1 Ai∇Li ` wbt ˘
›
›
›
›
›
2 ˇ
ˇ
ˇ
ˇ
ˇ
ˇ
F0
fi fl´ 2αtE «C n ÿ
i“1 Ai∇Li
` wbt ˘ , A∇L ` wbt ˘
G ˇ
ˇ
ˇ
ˇ
ˇ
F0
ff
` α2tE « cb ˜ 1
n
n ÿ
i“1
› ›A∇Lipwbt q › › 2 ´ › ›A∇Lpwbt q › › 2
¸
` › ›A∇Lpwbt q › ›
2
ˇ
ˇ
ˇ
ˇ
ˇ
F0
ff
“ E
»
–
›
›
›
›
›
n ÿ i“1 Ai∇Li ` wbt ˘ ´ αtA∇Lpwbt q
›
›
›
›
›
2 ˇ
ˇ
ˇ
ˇ
ˇ
ˇ
F0
fi fl` α2t cbE « 1
n
n ÿ
i“1
› ›A∇Lipwbt q › › 2 ´ › ›A∇Lpwbt q › › 2
ˇ
ˇ
ˇ
ˇ
ˇ
F0
ff
“ E
»
–
›
›
›
›
›
n ÿ i“1 Ai∇Li ` wbt ˘ ´ αtA∇Lpwbt q
›
›
›
›
›
2 ˇ
ˇ
ˇ
ˇ
ˇ
ˇ
F0
fi
fl` α 2 t cb n2 ÿ i‰j E ” › ›A∇Li ` wbt ˘ ´A∇Lj ` wbt ˘ › › 2 ˇ ˇ ˇ F0 ı
“ E
»
–
›
›
›
›
›
n ÿ
i“1
´ Ai ´ αt n A ¯ ∇Li ` wbt ˘
›
›
›
›
›
2 ˇ
ˇ
ˇ
ˇ
ˇ
ˇ
F0
fi
fl` α 2 t cb n2
n ÿ
i“1
n ÿ j“1 E ” › ›A∇Li ` wbt ˘ ´A∇Lj ` wbt ˘ › › 2 ˇ ˇ ˇ F0 ı .
Therefore, if we set Bi “ Ai ´ αtn A and
Bkli “
$
&
%
A i “ k, i ‰ l, ´A i “ l, i ‰ k,
0 otherwise,
we have
E
»
–
›
›
›
›
›
n ÿ i“1 Ai∇Li ` wbt`1 ˘
›
›
›
›
›
2 ˇ
ˇ
ˇ
ˇ
ˇ
ˇ
F0
fi
fl “ E
»
–
›
›
›
›
›
n ÿ i“1 Bi∇Li ` wbt ˘
›
›
›
›
›
2 ˇ
ˇ
ˇ
ˇ
ˇ
ˇ
F0
fi
fl` α 2 t cb n2
n ÿ
k“1
n ÿ l“1 E
»
–
›
›
›
›
›
n ÿ i“1 Bkli ∇Li ` wbt ˘
›
›
›
›
›
2 ˇ
ˇ
ˇ
ˇ
ˇ
ˇ
F0
fi
fl.
Proof of Theorem 1. We use induction to show this statement.
When t “ 0, E ” › ›
řn i“1Ai∇Li ` wbt ˘ › ›
2 ˇ
ˇ ˇ F0
ı
“ } řn i“1Ai∇Li pw0q} 2 which is invariant of b. Therefore, it is a decreasing function of b.
Suppose the statement holds for t. For any set of matrices tA1, . . . , Anu in Rpˆp, by Lemma 2 we know that there exist matrices tB1, ¨ ¨ ¨ , Bnu and Bkli : i, k, l P rns ( such that
E
»
–
›
›
›
›
›
n ÿ i“1 Ai∇Li ` wbt`1 ˘
›
›
›
›
›
2 ˇ
ˇ
ˇ
ˇ
ˇ
ˇ
F0
fi
fl “ E
»
–
›
›
›
›
›
n ÿ i“1 Bi∇Li ` wbt ˘
›
›
›
›
›
2 ˇ
ˇ
ˇ
ˇ
ˇ
ˇ
F0
fi
fl` α 2 t cb n2
n ÿ
k“1
n ÿ l“1 E
»
–
›
›
›
›
›
n ÿ i“1 Bkli ∇Li ` wbt ˘
›
›
›
›
›
2 ˇ
ˇ
ˇ
ˇ
ˇ
ˇ
F0
fi
fl.
By induction, we know that E ” › ›
řn i“1Bi∇Li ` wbt ˘ › ›
2 ˇ
ˇ ˇ F0
ı and all E ” › ›
řn i“1B kl i ∇Li ` wbt ˘ › ›
2 ˇ
ˇ ˇ F0
ı
are non-negative and decreasing functions of b. Besides, clearly α 2 t cb n2 “ α2t pn´bq bn3pn´1q is a non-negative and decreasing function of b. By Lemma 3, we know that α 2 t cb n2 E ” › › řn i“1B kl i ∇Li ` wbt ˘ › › 2 ˇ ˇ ˇ F0 ı is also a non-negative and decreasing function of b. Finally, E ” › ›
řn i“1Ai∇Li ` wbt`1 ˘ › ›
2 ˇ
ˇ ˇ F0
ı
, as the sum of non-negative and decreasing functions in b, is a non-negative and decreasing function of b.
In order to prove Theorem 2, we split the task to two separate theorems about the full gradient and the stochastic gradient and prove them one by one.
Theorem 6. Fixing initial weights w0, var ` B∇L ` wbt ˘ ˇ ˇF0 ˘
is a decreasing function of mini-batch size b for all b P rns, t P N, and all square matrices B P Rpˆp.
Theorem 7. Fixing initial weights w0, var ` Bgbt ˇ ˇF0 ˘
is a decreasing function of mini-batch size b for all b P rns, t P N, and all square matrices B P Rpˆp.
Proof of Theorem 6. We induct on t to show that the statement holds. For t “ 0, we have var ` B∇L `
wbt ˘ ˇ ˇF0 ˘ “ 0 for any matrix B. Suppose the statement holds for t ´ 1 ě 0. Note that from
∇L ` wbt ˘ “ 1 n
n ÿ i“1 xi ` xTi w b t ´ yi ˘
“ 1 n
n ÿ i“1 xi ` xTi ` wbt´1 ´ αtgbt´1 ˘ ´ yi ˘
“ 1 n
n ÿ i“1 xi ` xTi w b t´1 ´ yi ˘ ´ αt n n ÿ i“1 xix T i g b t´1
“ ∇L ` wbt´1 ˘ ´ αtCgbt´1,
we have var ` B∇L `
wbt ˘ ˇ ˇF0 ˘
“ var ` B∇L ` wbt´1 ˘ ´ αtBCgbt´1 ˇ ˇF0 ˘ “ E ” › ›B∇L `
wbt´1 ˘ ´ αtBCgbt´1 › ›
2 ˇ
ˇ ˇ Fb0
ı
´ › ›E “ B∇L ` wbt´1 ˘ ´ αtBCgbt´1 ˇ ˇFb0 ‰ › ›
2
“ E ” › ›B∇L `
wbt´1 ˘ › › 2 ´ 2αt @ B∇L ` wbt´1 ˘ , BCgbt´1 D ` α2t › ›BCgbt´1 › ›
2 ˇ
ˇ ˇ Fb0
ı
´ › ›E “ B∇L ` wbt´1 ˘ ´ αtBCgbt´1 ˇ ˇFb0 ‰ › ›
2
“ E ” › ›B∇L `
wbt´1 ˘ › ›
2 ˇ
ˇ ˇ F0
ı ` α2tE ” E ” › ›BCgbt´1 › › 2 ˇ ˇ ˇ Fbt´1 ı ˇ ˇ ˇ Fb0 ı ´ 2αtE “ E “@ B∇L ` wbt´1 ˘ , BCgbt´1 D ˇ ˇFbt´1 ‰ ˇ ˇF0 ‰
´ › ›E “ E “ B∇L ` wbt´1 ˘ ´ αtBCgbt´1 ˇ ˇFbt´1 ‰ ˇ ˇFb0 ‰ › ›
2
“ E ” › ›B∇L `
wbt´1 ˘› ›
2 ˇ
ˇ ˇ F0
ı ` α2tE « cb ˜ 1
n
n ÿ
i“1
› ›BC∇Li ` wbt´1 ˘ › › 2 ´ › ›BC∇L ` wbt´1 ˘ › › 2
¸
` › ›BC∇L ` wbt´1 ˘ › ›
2
ˇ
ˇ
ˇ
ˇ
ˇ
F0
ff
´ 2αtE “@ B∇L ` wbt´1 ˘ , BC∇L ` wbt´1 ˘D ˇ ˇF0 ‰ ´ › ›E “ B∇L ` wbt´1 ˘ ´ αtBC∇L ` wbt´1 ˘ ˇ ˇFb0 ‰ › ›
2
(3)
“ E ” › ›B pI ´ αtCq∇L ` wbt´1 ˘ › › 2 ˇ ˇ ˇ Fb0 ı ` α2t cbE «˜ 1
n
n ÿ
i“1
› ›BC∇Li ` wbt´1 ˘ › › 2 ´ › ›BC∇L ` wbt´1 ˘ › › 2
¸ ˇ
ˇ
ˇ
ˇ
ˇ
F0
ff
´ › ›E “ B pI ´ αtCq∇L ` wbt´1 ˘ ˇ ˇFb0 ‰ › ›
2
“ var ` B pI ´ αtCq∇L ` wbt´1 ˘ ˇ ˇF0 ˘ ` α2t cb
˜
1
n
n ÿ i“1 E ” › ›BC∇Li ` wbt´1 ˘ › › 2 ˇ ˇ ˇ F0 ı ´ E ” › ›BC∇L ` wbt´1 ˘ › › 2 ˇ ˇ ˇ F0 ı
¸
“ var ` B pI ´ αtCq∇L ` wbt´1 ˘ ˇ ˇF0 ˘ ` α 2 t cb n2 ÿ i‰j E ” › ›BC∇Li ` wbt´1 ˘ ´BC∇Lj ` wbt´1 ˘ › › 2 ˇ ˇ ˇ F0 ı , (4) where (3) is by Lemma 1. By induction, we know that the first term of (4) is a decreasing function of b. Taking Ai “ BC,Aj “ ´BC,Ak “ 0, k P rnszti, ju in Theorem 1, we know that
E ” › ›BC∇Li ` wbt´1 ˘ ´BC∇Lj ` wbt´1 ˘ › › 2 ˇ ˇ ˇ F0 ı
is also a decreasing function of b. Note that α 2 t cb n2 decreases as b increases. By Lemma 3 we learn that (4) is a decreasing function of b and hence we have completed the induction.
Proof of Theorem 7. We have
var ` Bgbt ˇ ˇF0 ˘
“ E ” ›
›Bgbt › ›
2 ˇ
ˇ ˇ F0
ı
´ › ›E “ Bgbt ˇ ˇF0 ‰ › ›
2
“ E ” E ” ›
›Bgbt › ›
2 ˇ
ˇ ˇ Fbt
ı ˇ
ˇ ˇ F0
ı
´ › ›E “ E “ Bgbt ˇ ˇFbt ‰ ˇ ˇF0 ‰ › ›
2
“ cb
˜
1
n
n ÿ i“1 E ” › ›B∇Li ` wbt ˘ › › 2 ˇ ˇ ˇ F0 ı ´ E ” › ›B∇L ` wbt ˘ › › 2 ˇ ˇ ˇ F0 ı
¸
` E ” › ›B∇L `
wbt ˘ › ›
2 ˇ
ˇ ˇ F0
ı
´ › ›E “ B∇L ` wbt ˘ ˇ ˇF0 ‰ › ›
2
“ cb n2 ÿ i‰j E ” › ›B∇Li ` wbt ˘ ´B∇Lj ` wbt ˘ › › 2 ˇ ˇ ˇ F0 ı ` var ` B∇L ` wbt ˘ ˇ ˇF0 ˘ .
Taking Ai “ B,Aj “ ´B,Ak “ 0, k P rnszti, ju in Theorem 1, we know that
E ” › ›B∇Li ` wbt ˘ ´B∇Lj ` wbt ˘ › › 2 ˇ ˇ ˇ F0 ı
is a decreasing and non-negative function of b for all i, j P rns. By Theorem 6, we know that var ` B∇L `
wbt ˘ ˇ ˇF0 ˘ is also a decreasing function of b. Therefore, var ` Bgbt ˇ ˇF0 ˘
, as the sum of two decreasing functions of b, is also a decreasing function of b.
Proof of Corollary 1. Simply taking B “ Ip in Theorem 1 yields the proof.

heading: B.2 PROOFS FOR RESULTS IN 3.2
text: Remark. We often rely on the trivial facts that x1xT2 “ x1IpxT2 and x1xT2 x3xT4 “ x1xT2 Ipx3xT4 . Lemma 5. Given a multiplicative term of parameter matrices
uiv T i : ui, vi P Rp, i P rn1s
(
YtAj : Aj P Rpˆp, j P rn2su and constant matrix tIpu such that degpu1vT1 ;Mq ě 1, we have
tr pMq “ vT1 M 1u1,
where M 1 is a multiplicative term of parameter matrices uiv T i : ui, vi P Rp, i P rn1s ( Y tAj : Aj P Rpˆp, j P rn2su and constant matrix tIpu such that degpMq “ degpM 1q ` 1,degpAj ;Mq “ degpAj ;M 1q, j P rn2s,degpuivTi ;Mq “ degpuivTi ;M 1q, i P r2 : n1s and degpu1vT1 ;Mq “ degpu1vT1 ;M 1q ` 1.
Proof. By the definition of multiplicative terms, we know that there exist two multiplicative terms M1,M2 of parameter matrices uiv T i : ui, vi P Rp, i P rn1s (
Y tAj : Aj P Rpˆp, j P rn2su and constant matrix tIpu such that M “M1u1vT1 M2, where degpMq “ degpM1q ` degpM2q ` 1,degpAj ;Mq “ degpAj ;M1q ` degpAj ;M2q, j P rn2s,degpuivTi ;Mq “ degpuivTi ;M1q ` degpuivTi ;M2q, i P r2 : n1s and degpu1vT1 ;Mq “ degpu1vT1 ;M1q ` degpu1vT1 ;M2q ` 1. Therefore we have
tr pMq “ tr ` M1u1v T 1 M2 ˘ “ tr ` vT1 M2M1u1 ˘ “ vT1 M2M1u1.
Note that M 1 “ M2M1 satisfies that degpM 1q “ degpM1q ` degpM2q,degpAj ,M 1q “ degpAj ;M1q ` degpAj ;M2q, j P rn2s,degpuivTi ;Mq “ degpuivTi ;M1q ` degpuivTi ;M2q, i P r2 : n1s and degpu1vT1 ;M 1q “ degpu1vT1 ;M1q ` degpu1vT1 ;M2q ` 1. We have finished the proof.
The following two lemmas focus on the expectation of the product of quadratic forms of the standard normal samples. Lemma 6 focuses on single sample while 7 focuses on the same form with b i.i.d. samples drawn from the standard normal distribution.
Lemma 6. Given matrices Aj P Rpˆp, j P rm´ 1s, we have
Ex„N p0,Ipq “ xxTA1xx TA2 ¨ ¨ ¨Am´1xxT ‰
“ Nm ÿ
i“1
ni ź k“1 tr pMikqMi0,
where Nm and ni, i P rNms are constants depending on m and tMik, k P r0 : nis , i P rNmsu are multiplicative terms of parameter matrices tAj , j P rm´ 1su and constant matrix tIpu. Furthermore, for every i P rNms, we have řni k“0 degpAj ;Mikq “ 1, j P rm ´ 1s and therefore řni k“0 deg pMikq “ m´ 1.
Proof. See Magnus (1978).
Lemma 7. We are given matrices Aj P Rpˆp, j P rm´ 1s and random vectors xi, i P rbs independently and identically drawn from N p0, Ipq. We assume that the multi-set S “ ij , i 1 j : j P rms ( satisfies that for every i P S, i is an element of rbs and the number of appearance of i in S is even. Then
Exi„N p0,Ipq ” xi1x T i11 A1xi2x T i12 A2 ¨ ¨ ¨Am´1ximxTi1m ı
“ Nm ÿ
i“1
ni ź k“1 tr pMikqMi0, (5)
where Nm and ni are constants depending on m (and independent of b) and Mik, k P r0 : nis , i P rNms are multiplicative terms of parameter matrices tAj , j P rm´ 1su and constant matrix tIpu. Furthermore, for every i P rNms, we have řni k“0 degpAj ;Mikq “ 1, j P rm ´ 1s and therefore řni k“0 deg pMikq “ m´ 1.
Proof. Let βi, i P rbs be the number of appearances of i in S, which are even by assumption. We induct on the quantity N “
řb i“1 1 tβi ‰ 0u.
For the base case of N “ 1, all elements in the multi-set S have the same value. Without loss of generality, we assume ij “ i1j “ 1, j P rms. Then
Exi„N p0,Ipq ” xi1x T i11 A1xi2x T i12 ¨ ¨ ¨Am´1ximxTi1m ı “ Ex1„N p0,Ipq “ x1x T 1 A1x1x T 1 ¨ ¨ ¨Am´1x1xT1 ‰ ,
which is the statement of Lemma 6.
Suppose the statement holds forN ě 1, and we consider the case ofN`1. Note that xTi1jAjxij`1 “ xTij`1Ajxi1j is a scalar so that we can move it around without changing the value of the expression
2. We distinguish two cases.
• Let i1 ‰ i1m. Without loss of generality, we assume i1 “ 1. We can always change the order of xTi1jAjxij`1 , j P rm ´ 1s (and flip it to be x T ij`1 Ajxi1j if necessary) such that all
x1’s appear in the form of x1xT1 :
xi1x T i11 A1xi2x T i12 A2 ¨ ¨ ¨Am´1ximxTi1m “ x1
´
xTi11A1xi2x T i12 A2 ¨ ¨ ¨Am´1xim
¯
xTi1m
“ x1xT1 rA1x1xT1 rA2 ¨ ¨ ¨ rA β1 2 ´1 x1x T 1 rA β1 2 rxxTi1m
where rx P txi, i P rbsu , rx ‰ x1 and rAi’s are multiplicative terms of parameter matrices txuxTv : u, v P r2 : bsu Y tAj : j P rm´ 1su and constant matrix tIpu such that ř
u,vPr2:bs ř
β1 2
k“1 degpxuxTv ; rAkq “ m´ β1 2 ´1 and ř
β1 2
k“1 degpAj ; rAkq “ 1, j P rm´1s3.
Applying Lemma 6 and the law of iterative expectations, we have
Exi„N p0,Ipq ” xi1x T i11 A1xi2x T i12 ¨ ¨ ¨Am´1ximxTi1m ı “ Ex1,¨¨¨ ,xb ” x1x T 1 rA1x1x T 1 rA2 ¨ ¨ ¨ rA β1 2 ´1 x1x T 1 rA β1 2 rxxTi1m ı
“ Ex2,¨¨¨ ,xb
«˜
Nm ÿ
i“1
ni ź k“1 tr pMikqMi0
¸
rA β1 2 rxxTi1m
ff
“ Nm ÿ
i“1 Ex2,¨¨¨ ,xb
«˜
ni ź k“1 tr pMikqMi0
¸
rA β1 2 rxxTi1m
ff
,
where Nm and ni are constant depending on m (and independent of b) and Mik, k P r0 : nis , i P rNms are multiplicative terms of parameter matrices ! rAj , j P rβ12 ´ 1s ) and constant matrix tIpu. Furthermore, for every i P rNms, we have řni k“0 degp rAj ;Mikq “ 1, j P rβ12 ´ 1s and therefore řni k“0 deg pMikq “ β1 2 ´ 1.
Combining the definition of rAj’s, we know thatMik, k P r0 : nis , i P rNms are multiplicative terms of parameter matrices txuxTv : u, v P r2 : bsuY tAj : j P rm´ 1su and constant
2For example, we can rewrite
xi1x T i11 A1xi2x T i12 A2xi3x T i13 “ xi1
´
xTi11A1xi2
¯ ”
xTi12A2xi3
ı xTi13 “ xi1 ” xTi12A2xi3 ı ´ xTi11A1xi2 ¯ xTi13
“ xi1 ” xTi12 ´ xTi11A1xi2 ¯ A2xi3 ı xTi13 “ xi1 ” xTi12A2 ´ xTi11A1xi2 ¯ xi3 ı xTi13 .
3For example, we can rewrite
x1x T 2 A1x1x T 1 A2x3x T 3 A3x1x2 “ x1
´ xT2 A1x1 ¯ ” xT1 A2x3 ı ! xT3 A3x1 ) x2 “ x1 ´ xT1 A1x2 ¯ ” xT3 A2x1 ı ! xT1 A3x3 ) x2
“x1xT1 A1x2xT3 A2x1xT1 A3x3x2 “ x1xT1 rA1x1xT1 rA2rxx2,
where rA1 “ A1x2xT3 A2, rA2 “ A3 and rx “ x3. Besides, m “ 4, β1 “ 4, thus the degree of xuxTv in all rAk sum up to m´ β1
2 ´ 1 “ 1
matrix tIpu such that for every i P rNms, we have ř u,vPr2:bs řni k“0 degpxuxTv ;Mikq “ m´ β12 ´ 1 and řni k“0 degpAj ;Mikq “ 1, j P rm´ 1s.
Applying Lemma 5, for every k P r0 : nis and every i P rNms, there exists uik, vik P txj : j P r2 : bsu and multiplicative term M 1ik of parameter matrices txuxTv : u, v P r2 : bsu Y tAj : j P rm´ 1su and constant matrix tIpu such that
tr pMikq “ uTikM 1ikvik.
Therefore, we have ˜
ni ź k“1 tr pMikqMi0
¸
rA β1 2 rxxTi1m “
ni ź
k“1
` uTikM 1 ikvik ˘ Mi0 rA β1 2 rxxTi1m “Mi0 rA β1 2 rx ni ź
k“1
` uTikM 1 ikvik ˘ xTi1m fi Ui.
Note that for every i P rNms, we have m´1 ÿ j“1 degpxi;Ajq “ ni ÿ k“1 degpxi;M 1ikq ` degpxi;Mi0q ` deg ´ xi; rA β1 2 ¯ ` degpxi; rxq ` deg ´ xi;x T i1m ¯ ,
and for every j P rm´ 1s, we have ni ÿ
k“1 degpAj ;M 1ikq ` degpAj ;Mi0q ` deg
´
Aj ; rA β1 2
¯
“ 1.
In other words, for every i P rNms, Ui has the form of pA0xpi1x T pi11 pA1xpi2x T pi12 ¨ ¨ ¨ pAm´1xpim1x T i1m pAm1 but there is no appearance of x1. Here
x pij , x pij P txj , j P r2 : bsu, and pAi, i P r0 :ms are multiplicative terms of parameter matrices tAj , j P rm´ 1su and constant matrix tIpu. Furthermore, for every j P rm´ 1s, we have
řni k“0 degpAj ; pAiq “ 1. Note that here we use the liberty of adding identity
matrices if more than two consecutive x’s appear. Since we have reduced N ` 1 by one, we can use induction on x
pi1 xT pi11 pA1xpi2x T pi12 ¨ ¨ ¨ pAm´1xpim1x T i1m and finish the proof.
The two constant matrices pA0 and pAm do not change the result of expectation since E ´ pA0X pAm1 ¯ “ pA0EpXq pAm1 .
• If i1 “ i1m, without loss of generality we assume, i11 “ 1 and i11 ‰ i1 (note that all xTi1j Ajxij`1 , j P rm ´ 1s are inter-changeable and there is at least one element in S that
is not equal to i1). We change the orders of xTi1jAjxij`1 , j P rm ´ 1s (and flip it to be xTij`1Ajxi1j if necessary) such that all x1’s appear in a consecutive form of x1x T 1 :
xi1x T i11 A1xi2x T i12 A2 ¨ ¨ ¨Am´1ximxTi1m “ xi1
´
xTi11A1xi2x T i12 A2 ¨ ¨ ¨Am´1xim
¯
xTi1m
“ xi1 ´ rxT1 rA0 ” x1x T 1 rA1 ¨ ¨ ¨ rA β1
2 ´1 x1x
T 1
ı
rA β1 2 rx2
¯
xTi1m ,
where rx1, rx2 P txi, i P rbsu , rx1, rx2 ‰ x1 and rAi’s are multiplicative terms of parameter matrices txuxTv : u, v P r2 : bsu Y tAj : j P rm´ 1su and constant matrix tIpu such that
ÿ
u,vPr2:bs
β1 2 ÿ k“0 degpxuxTv ; rAkq “ m´ β1 2 ´ 2
and ř
β1 2
k“0 degpAj ; rAkq “ 1, j P rm ´ 1s. The remaining reasoning is the same as the previous case.
Remark. If one of the βi numbers of appearance of xj , j P rbs is odd, then it is easy to see that the result in (5) is the zero matrix.
As pointed out in the Section 1, the difficulty of studying the dynamics of SGD is how to connect the quantities in iteration t with fixed variables, like initial weights W0,1,W0,2 and mini-batch size b. We overcome this challenge by the following two lemmas. Lemma 8 provides the relationship between gbt,i, i “ 1, 2 and W bt,i, i “ 1, 2 by taking expectation over the distribution of random samples in Bbt . Lemma 9 shows the relationship between W bt,i, i “ 1, 2 and gbt´1,i, i “ 1, 2 using (1) and (2).
Lemma 8. For multiplicative terms Mi, i P r0 :ms of parameter matrices gbt,1, g b t,2
(
and constant matrices W bt,1,W b t,2,W ˚ 1 ,W ˚ 2 (
with degree di, respectively, we denote M “
śm i“1 tr pMiqM0 and d “ řm i“0 di. There exists a set of multiplicative terms
Mkij , i P rmks, j P r0 :mkis , k P r0 : qs ( of parameter matrices W bt,1,W b t,2 (
and constant matrices tW˚1 ,W˚2 u such that
E “ M ˇ ˇFbt ‰ “ N0 `N1 1
b ` ¨ ¨ ¨ `Nd
1 bd ,
where Nk “ řmk i“1 śmki j“1 tr ` Mkij ˘ Mki0, k P r0 : ds. Here mk,mki are constants independent of b, and
řmki j“0 deg ` Mkij ˘ ď 3d` řm i“0 ` deg ` W bt,1;Mi ˘ ` degpW bt,2;Miq ˘ .
Lemma 9. For multiplicative term Mi, i P r0 :ms of parameter matrices W bt,1,W b t,2
(
and constant matrices tW˚1 ,W˚2 u of degree di, let d “ 2d0`¨¨¨`dm . There exists a set of multiplicative terms tMik, i P r0 :ms , k P rdsu of parameter matrices gbt,1, g b t,2 ( and constant matrices
W bt,1,W b t,2,W ˚ 1 ,W ˚ 2 ( such that
m ź i“1 tr pMiqM0 “ d ÿ k“1 m ź i“1 tr pMikqM0k,
where řm i“0 deg pMikq ď d.
Proof of Lemma 8. By (1) and (2) we have
M “ m ź
i“1 tr pMiqM0 “
1
bd
bd ÿ
k“1
m ź i“1 tr pMkiqMk0, (6)
where each Mki, k P rbds, i P r0 :ms is a multiplicative term of parameter matrices
xt,ix T t,i, i P rbs
(
and constant matrices W bt,1,W b t,2,Wbt
( . Let ĂMk “ śm i“1 tr pMkiqMk0, k P
“ bd ‰ . We split set ! ĂMk : k P “ bd ‰ )
into disjoint and non-empty sets (equivalent classes) S1, . . . , SnM such that
1. for every i P rnM s and every M1,M2 P Si, we have E “ M1 ˇ ˇFbt ‰ “ E “ M2 ˇ ˇFbt ‰ ,
2. for every i, j P rnM s, i ‰ j and every M1 P Si and M2 P Sj , we have E “ M1 ˇ ˇFbt ‰ ‰ E “ M2 ˇ ˇFbt ‰ .
Note thatYnMi“1Si “ ! ĂMk : k P “ bd ‰ )
. Let xMk P Sk represent the equivalent class Sk (it can be any member of Sk). For every i P rnM s, we can always write |Si| “ ei,0` ei,1b` ¨ ¨ ¨` ei,dbd such that ei,j P N, ei,j ă b, j P r0 : ds (actually ei,j’s are the digits of the base-b representation of |Si|). Then
we have
E “ M ˇ ˇFbt ‰ “ E
»
–
1
bd
bd ÿ
k“1
ĂMk
ˇ
ˇ
ˇ
ˇ
ˇ
ˇ
Fbt
fi
fl “ 1 bd E
«
nM ÿ
i“1
` ei,0 ` ei,1b` ¨ ¨ ¨ ` ei,dbd ˘ xMi
ˇ
ˇ
ˇ
ˇ
ˇ
Fbt
ff
“ 1 bd
nM ÿ
i“1
` ei,0 ` ei,1b` ¨ ¨ ¨ ` ei,dbd ˘ E ” xMi
ˇ
ˇ ˇ Fbt
ı
(7)
“ nM ÿ
i“1
ˆ
ei,d ` ei,d´1 1
b ` ¨ ¨ ¨ ` ei,0
1
bd
˙
E ”
xMi
ˇ
ˇ ˇ Fbt
ı
.
It is important to note that nM , the number of different equivalent classes, is independent of b. This follows from the fact that each E ”
ĂMk
ˇ
ˇ ˇ Fbt
ı (and so as E ”
xMk
ˇ
ˇ ˇ Fbt
ı
) includes
a finite number of weight matrices W bt,1 and W b t,2 with degree less than or equal to 3d ` řm i“0 ` deg ` W bt,1;Mi ˘ ` degpW bt,2;Miq ˘
(see Lemma 7). Thus the number of partition sets is bounded by a quantity independent of b.
Note that each Mki can be represented as
Mki “ Aki0 xkit,i1x ki t,i1 T Aki1 ¨ ¨ ¨Akidi´1x ki t,idi xkit,idi T Akidi
for some matrices Aki0 , . . . , A ki di that are multiplicative term of parameter matrices
W bt,1,W b t,2andWbt
(
constant matrix tIpu (we stress again that some A matrices can be identities, based on the definition of multiplicative terms), and xkit,i1 , . . . , x ki t,idi
P txt,1, . . . , xt,bu. We have
tr pMkiq “ tr ´ Aki0 x ki t,i1x ki t,i1 T Aki1 ¨ ¨ ¨Akidi´1x ki t,idi xkit,idi T Akidi ¯
“ xkit,idi T AkidiA ki 0 x ki t,i1x ki t,i1 T Aki1 ¨ ¨ ¨Akidi´1x ki t,idi .
For every k P “ bd ‰ , we have
m ź i“1 tr pMkiqMk0 “
«
m ź i“1 xkit,idi T AkidiA ki 0 x ki t,i1x ki t,i1 T Aki1 ¨ ¨ ¨Akidi´1x ki t,idi
ff
Ak00 x k0 t,i1x k0 t,i1 T Ak01 ¨ ¨ ¨Ak0d0´1x k0 t,id0 xk0t,id0 T Ak0d0
“ « m ź
i“1 xkit,idi T AkidiA ki 0 x ki t,i1x ki t,i1 T Aki1 ¨ ¨ ¨Akidi´1x ki t,idi
ff
”
xk0t,i1 T Ak01 ¨ ¨ ¨Ak0d0´1x k0 t,id0
ı
Ak00 x k0 t,i1x k0 t,id0 T Ak0d0 ,
which can be rewritten as
ĂMk “ m ź
i“1 tr pMkiqMk0 “
˜
d ź j“1 xTt,̄ijA k jxt,̄i1j
¸
Ak00 x k0 t,i1x k0 t,id0 T Ak0d0 .
Note that the randomness of each ĂMk given Fbt only comes from the randomness of xt,j’s, i.e. for all k P “ bd ‰ we have
E ”
ĂMk
ˇ
ˇ ˇ Fbt
ı
“ Ext,j„N p0,Iq
«˜
d ź j“1 xTt,ijA k jxt,i1j
¸
Ak0xt,i10x T t,i0A k 0
1 ff
“ Ext,j„N p0,Iq
«
Ak0xt,i10
˜
d ź j“1 xTt,ijA k jxt,i1j
¸
xTt,i0A k 0
1 ff
(8)
“ nkM ÿ
i“1
nki ź j“1 tr ´ ĂMkij ¯ ĂMki0,
where the last equation comes from Lemma 7. Here nkM , n k i , i P
“ nkM ‰ , k P “ bd ‰
are constants independent of b, Mkij’s are multiplicative terms of parameter matrices W bt,1,W b t,2,Wbt (
and constant matrix tIpu such that for every i P “ nkM ‰ , we have
nki ÿ j“0 deg ´ Wbt ; ĂMkij ¯ “ d (9)
and nki ÿ
j“0
´ deg ´
W bt,1; ĂMkij
¯ ` deg ´
W bt,2; ĂMkij
¯¯ “ d` m ÿ
r“0
` deg ` W bt,1;Mr ˘ ` degpW bt,2;Mrq ˘ . (10)
These degree relationships can be observed from (1), (2), and the fact that each gbt,1 or g b t,1 contributes one Wbt and one of W bt,1 or W bt,2 in śnki j“1 tr ´ ĂMkij ¯ ĂMki0. Note that Wt “ W bt,2W bt,2 ´
W˚2 W ˚ 1 . For every i P “ nkM ‰ , if we replace all appearances of Wbt in śnki j“1 tr
´
ĂMkij
¯
ĂMki0 and
expand all parentheses of ` W bt,2W b t,2 ´W˚2 W˚1 ˘ , we have
nki ź j“1 tr ´ ĂMkij ¯ ĂMki0 “ 2d ÿ l“1 nki ź j“1 tr ´ ĂMklij ¯ ĂMkli0 , (11)
where ĂMklij ’s are multiplicative terms of parameter matrices W bt,1,W b t,2
(
and constant matrices tW˚1 ,W˚2 u such that nki ÿ
j“0
´ deg ´
W bt,1; ĂMklij
¯ ` deg ´
W bt,2; ĂMklij
¯¯ ď 3d` m ÿ
r“0
` deg ` W bt,1;Mr ˘ ` degpW bt,2;Mrq ˘ ,
(12) where the inequality comes from (9) and (10) and the fact that each gbt,1 or g b t,2 contributes 2 or 0 degrees in the form of W bt,2W b t,1 or W ˚ 2 W ˚ 1 , respectively.
Combining (7), (8) and (11), we have
E “ M ˇ ˇFbt ‰
“ nM ÿ
k“1
ˆ
ek,d ` ek,d´1 1
b ` ¨ ¨ ¨ ` ek,0
1
bd
˙
E ”
xMk
ˇ
ˇ ˇ Fbt
ı
“ nM ÿ
k“1
ˆ
ek,d ` ek,d´1 1
b ` ¨ ¨ ¨ ` ek,0
1
bd
˙ n sk M ÿ
i“1
2d ÿ
l“1
nki ź j“1 tr ´ ĂMklij ¯ ĂMkli0
“ N0 `N1 1
b ` ¨ ¨ ¨ `Nd
1 bd ,
where
Nr “ nM ÿ
k“1 ek,d´r
¨
˝
n sk M ÿ
i“1
2d ÿ
l“1
nki ź j“1 tr ´ ĂMklij ¯ ĂMkli0
˛
‚. (13)
Note that all constants in (13) are independent of b and combining with (12), we have finished the proof.
Proof of Lemma 9. Simply using the fact that W bt,i “ W bt´1,i ´ αtgbt´1,i, i “ 1, 2, if we replace each W bt,i in the left-hand-side of (13) by W b t´1,i ´ αtgbt´1,i and expand all the parentheses, then each Mi, i P r0 :ms becomes the sum of 2di multiplicative terms of parameter matrices gbt,1, g b t,2 ( and constant matrices
W bt,1,W b t,2,W ˚ 1 ,W ˚ 2 ( with degree at most di. As a result, śm i“1 tr pMiqM0
becomes the sum of 2d terms in the form of śm i“1 tr pMikqM0k where deg pMikq ď 2di , and therefore řm i“0 deg pMikq ď śm i“0 2 di “ d.
Proof of Theorem 3. We use induction on t to show this result. The base case of t “ 0 it is the same as the statement in Lemma 8.
Suppose that the statement holds for t ě 0, and we consider the case of t ` 1. By Lemma 8, there exists a set of multiplicative terms
Mkt`1,i,j , i P rmt`1,ks, j P r0 :mt`1,k,is , k P r0 : ds (
of parameter matrices
W bt`1,1,W b t`1,2
( and constant matrices tW˚1 ,W˚2 u such that
E “ M ˇ ˇFbt`1 ‰ “ Nt`1,0 `Nt`1,1 1
b ` ¨ ¨ ¨ `Nt`1,d
1 bd , (14)
where Nt`1,k “ řmt`1,k i“1 śmt`1,k,i j“1 tr ` Mkt`1,i,j ˘ Mkt`1,i,0, k P r0 : ds. Here mt`1,k,mt`1,k,i are constants independent of b, and
řmt`1,k,i j“0 deg ` Mkt`1,i,j ˘ ď 3d` d1.
For each i P rmt`1,ks and each k P r0 : ds, by Lemma 9, there exists a set of multiplicative terms tMt,i,j,k,l, j P rmt`1,i,ks , l P rdt,i,ksu of parameter matrices gbt,1, g b t,2 ( and constant matrices
W bt,1,W b t,2,W ˚ 1 ,W ˚ 2 ( such that
mt`1,k,i ź
j“1 tr ` Mkt`1,i,j ˘
Mkt`1,i,0 “ dt,i,k ÿ
l“1
mt`1,k,i ź
j“1 tr pMt,i,j,k,lqMt,i,0,k,l, (15)
where dt,i,k “ 2 řmt`1,k,i j“0 pdegpW bt,1;Mt,i,j,k,lq`degpW bt,2;Mt,i,j,k,lqq is a constant independent of b and
mt`1,k,i ÿ
j“0 deg pMt,i,j,k,lq ď 3d` d1, (16)
and mt`1,k,i ÿ
j“0 pdeg pWt,1;Mt,i,j,k,lq ` deg pWt,2;Mt,i,j,k,lqq ď 3d` d1. (17)
Combining (14) and (15), we have for every k P r0 : ds
Nt`1,k “ mt`1,k ÿ
i“1
dt,i,k ÿ
l“1
mt`1,k,i ź
j“1 tr pMt,i,j,k,lqMt,i,0,k,l. (18)
Note that
E rM |F0s “ E “ E “ M ˇ ˇFbt`1 ‰ ˇ ˇF0 ‰ “ E rNt`1,0|F0s ` E rNt`1,1|F0s 1
b ` ¨ ¨ ¨ ` E rNt`1,d|F0s
1
bd
“ mt`1,0 ÿ
i“1
dt,i,0 ÿ
l“1 E
«
mt`1,0,i ź
j“1 tr pMt,i,j,0,lqMt,i,0,0,l
ˇ
ˇ
ˇ
ˇ
ˇ
F0
ff
`
` mt`1,1 ÿ
i“1
dt,i,1 ÿ
l“1 E
«
mt`1,1,i ź
j“1 tr pMt,i,j,1,lqMt,i,0,1,l
ˇ
ˇ
ˇ
ˇ
ˇ
F0
ff
1 b ` ¨ ¨ ¨`
` mt`1,d ÿ
i“1
dt,i,d ÿ
l“1 E
«
mt`1,d,i ź
j“1 tr pMt,i,j,d,lqMt,i,0,d,l
ˇ
ˇ
ˇ
ˇ
ˇ
F0
ff
1 bd , (19)
and each Mt,i,j,k,l is a multiplicative term of parameter matrices gbt,1, g b t,2
(
and constant matrices tW bt,1,W bt,2,W˚1 ,W˚2 u such that the degree is at most 1. Therefore, by induction, for every i, k, l, we have
E
«
mt`1,k,i ź
j“1 tr pMt,i,j,k,lqMt,i,0,k,l
ˇ
ˇ
ˇ
ˇ
ˇ
F0
ff
“ Nt,i,k,l,0 `Nt,i,k,l,1 1
b ` ¨ ¨ ¨Nt,i,k,l,qt
1
bqt , (20)
where qt ď d1 ` 12 p3 t ´ 1qp3d` d1q and Nt,i,k,l,0, ¨ ¨ ¨ , Nt,i,k,l,qt are sum of multiplicative terms of parameter matrices
W b0,1,W b 0,2
( and constant matrices tW˚1 ,W˚2 u with degree at most d ¨ 3t.
Combining (19) and (20), we can rewrite
E rM |F0s “ N0 `N1 1
b ` ¨ ¨ ¨ `Nq
1 bq ,
in the same form as in the statement. Here q ď d ` 3qt ď 12 p3 t`2 ´ 1qd ` 12 p3 t`1 ´ 1qd1 and řmki j“0 deg ` Mkij ˘ ď 3ˆ 3tp3d` d1q “ 3t`1p3d` d1q follow from (16) and (17).
In conclusion, we have shown that the statement holds for t` 1, and therefore finishes the proof.
By changing the role of parameter and constant matrices in Theorem 3, we obtain the following corollary. Corollary 2. Given t ě 0, for any multiplicative terms Mi, i P r0 :ms of parameter matrices
W bt,1,W b t,2,Wbt
( and constant matrices tW˚1 ,W˚2 u such that ř2 i“1 deg ` W bt,i;M ˘ “ d and deg `
Wbt ;M ˘ “ d1, we denote M “ śm i“1 tr pMiqM0. There exists a set of multiplicative terms
Mkij , i P rmks, j P r0 :mkis , k P r0 : qs ( of parameter matrices W b0,1,W b 0,2 (
and constant matrices tW˚1 ,W˚2 u such that
E rM |F0s “ N0 `N1 1
b ` ¨ ¨ ¨ `Nq
1 bq ,
where Nk “ řmk i“1 śmki j“1 tr ` Mkij ˘ Mki0, k P r0 : qs. Here mk,mki and q ď 3t pd` 2d1q are constants independent of b, and
řmki j“0 deg ` Mkij ˘ ď 3t pd` 2d1q.
Proof of Corollary 2. We simply note that M can be written as the sum of at most 2d multiplicative terms of parameter matrices
W bt,1,W b t,2,W ˚ 1 ,W ˚ 2 ( and constant matrix tI0u. Then we apply Lemmas 8 and 9 iteratively in the same way as in the proof of Theorem 3 to finish the proof.
Proof of Theorem 4. We only show the case for gt,1 since the proof for gt,2 can be tackled similarly. Note that
var ` gbt,1 ˇ ˇF0 ˘
“ var ˜ 1
b
b ÿ i“1 W bt,2 TWbt xt,ixTt,i
ˇ
ˇ
ˇ
ˇ
ˇ
F0
¸
“ 1 b2
b ÿ i“1 var ´ W bt,2 TWbt xt,ixTt,i ˇ ˇ ˇ F0 ¯
“ 1 b var ´ W bt,2 TWbt xt,1xTt,1 ˇ ˇ ˇ F0 ¯
“ 1 b
ˆ E „ › ›
› W bt,2 TWbt xt,1xTt,1 › › ›
2 ˇ
ˇ
ˇ
ˇ
F0  ´ › › › E ” W bt,2 TWbt xt,1xTt,1 ˇ ˇ ˇ F0 ı › › › 2 ˙
“ 1 b
ˆ
E ” tr ´
xt,1x T t,1Wbt T W bt,2W b t,2 TWbt xt,1xTt,1 ¯ ˇ ˇ ˇ F0 ı ´ › › › E ” W bt,2 TWbt xt,1xTt,1 ˇ ˇ ˇ F0 ı › › ›
2 ˙
“ 1 b
ˆ
E ” E ” tr ´
xt,1x T t,1Wbt T W bt,2W b t,2 TWbt xt,1xTt,1 ¯ ˇ ˇ ˇ Fbt ı ˇ ˇ ˇ F0 ı ´ › › › E ” E ” W bt,2 TWbt xt,1xTt,1 ˇ ˇ ˇ Fbt ı ˇ ˇ ˇ F0 ı › › ›
2 ˙
“ 1 b
ˆ
E ” pp` 2qtr ´ Wbt T W bt,2W b t,2 TWbt ¯ ˇ ˇ ˇ F0 ı ´ › › › E ” W bt,2 TWbt ˇ ˇ ˇ F0 ı › › ›
2 ˙
“ 1 b
ˆ
pp` 2qtr ´ E ” Wbt T W bt,2W b t,2 TWbt ˇ ˇ ˇ F0 ı¯ ´ › › › E ” W bt,2 TWbt ˇ ˇ ˇ F0 ı › › ›
2 ˙
.
“ 1 b
ˆ
pp` 2qtr ´ E ” Wbt T W bt,2W b t,2 TWbt ˇ ˇ ˇ F0 ı¯ ´ › › › E ” W bt,2 TWbt ˇ ˇ ˇ F0 ı › › ›
2 ˙
.
Here we have used the fact that Ex„N p0,Ipqtr ` xxTAxxT ˘ “ pp`2qtr pAq. By Corollary 2 we know that there exists a set of multiplicative terms
Mkij , i P rmks, j P r0 :mkis , k P r0 : qs (
of parameter matrices
W b0,1,W b 0,2
( and constant matrices tW˚1 ,W˚2 u such that
tr ´ E ” Wbt T W bt,2W b t,2 TWbt ˇ ˇ ˇ F0 ı¯ “ γ0 ` γ1 1
b ` ¨ ¨ ¨ ` γq
1 bq , (21)
where γk “ řmk i“1 śmki j“0 tr ` Mkij ˘ , k P r0 : qs. Here mk,mki and q ď 6 ¨ 3t are constants independent of b, and
řmki j“0 deg ` Mkij ˘ ď 6 ¨ 3t. Note that W b0,1,W b0,2 are fixed, and we have γk, k P r0 : qs are constants independent of b.
Similarly we observe that there exist constants q1 ď 2 ¨ 3t`1 and γ1k, k P r0 : q1s such that ›
› › E ” W bt,2 TWbt
ˇ
ˇ ˇ F0
ı ›
›
›
2
“ γ10 ` γ11 1 b ` ¨ ¨ ¨ ` γ1q 1 bq1 . (22)
By defining γi “ 0, i ą q and γ1i “ 0, i ą q1, and combining (21) and (22) we have
var ` gbt,1 ˇ ˇF0 ˘ “ 1 b
ˆ
pp` 2qtr ´ E ” Wbt T W bt,2W b t,2 TWbt ˇ ˇ ˇ F0 ı¯ ´ › › › E ” W bt,2 TWbt ˇ ˇ ˇ F0 ı › › ›
2 ˙
“ p` 2 b
ˆ
γ0 ` γ1 1
b ` ¨ ¨ ¨ ` γq
1
bq
˙
´ 1 b
ˆ
γ10 ` γ11 1 b ` ¨ ¨ ¨ ` γ1q 1 bq1
˙
“ maxtq,q1u ÿ
k“1
` pp` 1qγk ´ γ1k ˘ 1
bk .
Note that γk’s and γ1k’s are all constants independent of b, and max tq, q1u ď 2¨3t`1. This completes the proof.
Proof of Theorem 5. We first show that in
var ` gbt,i ˇ ˇF0 ˘ “ β1 1
b ` ¨ ¨ ¨ ` βr
1
br
we have β1 ě 0. If r “ 1, the statement obviously holds. Let us assume that the statement does not hold for r ą 1, i.e. β1 ă 0. Taking b large enough such that β1br´1`β2br´2` ¨ ¨ ¨`βr ă 0 yields
var ` gbt,i ˇ ˇF0 ˘ “ 1 br ` β1b r´1 ` β2br´2 ` ¨ ¨ ¨ ` βr ˘ ă 0,
which contradicts the fact that var ` gbt,i ˇ ˇF0 ˘ ě 0. Therefore, we have β1 ě 0.
Let b0 be large enough such that for all b ě b0, we have β1br´1 ` 2β2br´2 ` ¨ ¨ ¨ ` rβr ě 0. We denote fpbq “ β1 1b ` β2 1 b2 ` ¨ ¨ ¨ ` βr 1 br ě 0. For all b ą b0 we have
f 1pbq “ ´ 1 br`1 ` β1b r´1 ` 2β2br´2 ` ¨ ¨ ¨ ` rβr ˘ ď 0.
Therefore, for all b ą b0 we have ` var ` gbt,i ˇ ˇF0 ˘˘1 “ ´ rbr`1 fpbq ` 1 br fpbq ď 0, and thus var `
gbt,i ˇ ˇF0 ˘ is a decreasing function of b for all b ą b0.

heading: B.3 EXTENSION TO DEEP LINEAR NETWORKS
text: The extension from two-layer linear network to deep linear network is straightforward. Here we only provide the ideas on how to translate the proof of two-layer network to d-layer network, but not the strict proof. For simplicity, we remove all superscripts b of matrices in this subsection.
Assume that the d-layer linear network is given by fpx;wq “ WdWd´1 ¨ ¨ ¨W2W1x, where Wi, i P rds is the parameter matrix on the i-th layer and w “ pW1, . . . ,Wdq. The population loss is defined as
Lpwq “ Ex„N p0,Ipq „ 1
2 }Wd ¨ ¨ ¨W1x´W˚d ¨ ¨ ¨W˚1 x} 2

.
Similar to (1) and (2), we have
gt,k “ 1
b
b ÿ i“1 ∇Wt,k ˆ 1 2 }Wt,d ¨ ¨ ¨Wt,1xt,i ´W˚d ¨ ¨ ¨W˚1 xt,i} 2 ˙
“ 1 b
b ÿ i“1 WTt,k`1 ¨ ¨ ¨WTt,d pWd ¨ ¨ ¨W1 ´W˚d ¨ ¨ ¨W˚1 qxt,ixTt,iWTt,1 ¨ ¨ ¨WTt,k´1, k P rds.
We denoteWt “ Wt,d ¨ ¨ ¨Wt,1 ´W˚d ¨ ¨ ¨W˚1 . The remaining are all the same as the proofs in Appendix B.2, except we should replace all appearance of tWt,2,Wt,1u to tWt,d,Wt,d´1, ¨ ¨ ¨ ,Wt,1u and all tW˚2 ,W˚1 u to W˚d ,W ˚ d´1, ¨ ¨ ¨ ,W˚1 (
. We can do this because the stochastic gradient gt,k is still the sum of multiplicative terms of parameter matrices txt,iu and constant matrices tWt,d, ¨ ¨ ¨ ,Wt,1,W˚d , ¨ ¨ ¨ ,W˚1 u so the Lemmas in Appendix B.2 still apply.
In conclusion, we can again represent var pgt,k|F0q, k P rds as a polynomial of 1b with finite degree and without the constant term. By the same approach in the proof of Theorem 5, we can show that the variance is a decreasing function of the mini-batch size b.

Review summaries:
This paper studies the variance of stochastic gradient in SGD conditioned on the initialization point. It shows that the variance of stochastic gradient is a decreasing function of minibatch size for linear regression and deep linear network. Compared with previous works that show similar the results for one step in SGD, the results in this work only rely on initialization point. 

The paper shows that the variance of the gradient has an inverse dependence on the batch size in linear networks, subject to the knowledge of the initial weights. The main novelty of the paper is the computation of an exact dependence between batch size and variance of the gradient in the linear regression setting. In addition to that, the authors conduct a lot of experiments involving non-linear networks and real-world datasets, that show the inverse dependence of the variance of gradient and batch size throughout the training.