The Heavy-Tail Phenomenon in SGD
Authors: Mert Gurbuzbalaban
Umut Simsekli
Lingjiong Zhu
Venue:  (2021)
Keywords: heavy tails
stochastic gradient descent
deep learning

Abstract: In recent years, various notions of capacity and complexity have been proposed for characterizing the generalization properties of stochastic gradient descent (SGD) in deep learning. Some of the popular notions that correlate well with the performance on unseen data are (i) the 'flatness' of the local minimum found by SGD, which is related to the eigenvalues of the Hessian, (ii) the ratio of the stepsize $\eta$ to the batch size $b$, which essentially controls the magnitude of the stochastic gradient noise, and (iii) the 'tail-index', which measures the heaviness of the tails of the network weights at convergence. In this paper, we argue that these three seemingly unrelated perspectives for generalization are deeply linked to each other. We claim that depending on the structure of the Hessian of the loss at the minimum, and the choices of the algorithm parameters $\eta$ and $b$, the SGD iterates will converge to a \emph{heavy-tailed} stationary distribution. We rigorously prove this claim in the setting of quadratic optimization: we show that even in a simple linear regression problem with independent and identically distributed Gaussian data, the iterates can be heavy-tailed with infinite variance. We further characterize the behavior of the tails with respect to algorithm parameters, the dimension, and the curvature. We then translate our results into insights about the behavior of SGD in deep learning. We finally support our theory with experiments conducted on both synthetic data and fully connected neural networks.

Under review as a conference paper at ICLR 2021
THE HEAVY-TAIL PHENOMENON IN SGD
Anonymous authors
Paper under double-blind review
ABSTRACT
In recent years, various notions of capacity and complexity have been proposed for characterizing the generalization properties of stochastic gradient descent (SGD) deep learning. Some of the popular notions that correlate well with the performance on unseen data are (i) the 'flatness' of the local minimum found by SGD, which is related to the eigenvalues of the Hessian, (ii) the ratio of the stepsize n the batch size b, which essentially controls the magnitude of the stochastic gradient noise, and (iii) the 'tail-index', which measures the heaviness of the tails of the network weights at convergence. In this paper, we argue that these three seemingly unrelated perspectives for generalization are deeply linked to each other. We claim that depending on the structure of the Hessian of the loss at the minimum, and the choices of the algorithm parameters 1/ and b, the SGD iterates will converge heavy-tailed stationary distribution. We rigorously prove this claim in the setting of quadratic optimization: we show that even simple linear regression problem with independent and identically distributed Gaussian data, the iterates can be heavy-tailes with infinite variance. We further characterize the behavior the tails with respect algorithm parameters, the dimension, and the curvature. We then translate our results into insights about the behavior of SGD in deep learning. We finally support our theory with experiments conducted on both synthetic data and fully connected neural networks.
INTRODUCTION
The learning problem in neural networks can be expressed as an instance of the well-known population risk minimization problem in statistics, given follows:
min F(x) == EswDIf(x,
(1.1)
where E RR denotes random data point, D is a probability distribution I2P that denotes the law of the data points, x E IRd denotes the parameters of the neural network to be optimized, and f: IRd x Iº + R, denotes measurable cost function, which is often non-convex in While this problem cannot be attacked directly since 'D is typically unknown, if we have access to a training dataset S {=1,..., , ) with independent and identically distributed (i.i.d.) observations, i.e., Mid. D for i = 1..... n. we can use the empirical risk minimization strategy, which aims at solving the following optimization problem Shaale-Shwarrz & Ben- David 2014):
min f(x) == S) = (1/n) "
(x), (,))
(1.2)
where ((t denotes the cost induced by the data point 2,. The stochastic gradient descent (SGD) algorithm has been one of the most popular algorithms for addressing this problem:
I 1/ i
where Via(z) = (1/b) Σ iE0z
V (z).
(1.3)
Here, & denotes the iterations, > is the stepsize (also called the learning-rate), V f the stochastic gradient, is the batch-size, and Q, C [I,..., n is random subset with [Sa=] b for all k.
Even though the practical success of SGD has been proven in many domains, the theory for its generalization properties is still in early phase. Among others, one peculiar property of SGD that has not been theoretically rell-grounded that, depending on the choice of r) and b, the algorithm unseen test data.
can exhibit significantly different behaviors in terms of the performance
common perspective over this phenomenon is based on the 'flat minima' argument that dates back to Hochheeter & Schmidhhberr (1997), and associates the performance with the 'sharpness' or 'flatness' of the minimizers found by SGD, where these notions are often characterized by the magnitude of the eigenvalues of the Hessian, larger values corresponding sharper local minima

---

Under review as a conference paper at ICLR 2021
(Keskar et al. 2016). Recently, Jastrzebski et al. (2017) focused this phenomenon well and empirically illustrated that the performance of SGD on unseen test data is mainly determined by the stepsize 17 and the batch-size b, i.e., larger 7/66 yields better generalization. Revisiting the flat-minima argument, they concluded that the ratio nj/b determines the flatness of the minima found by SGD; hence the difference in generalization. In the same context, (Simşekli et al. (2019b) focused on the statistical properties of the gradient noise (V (x) - V fxx)) and illustrated that under an isotropic model, the gradient noise exhibits a heavy-tailed behavior, which was also confirmed in follow-up studies (hhng al., 2019). Based on this observation and a metastability argument (Pavlyukevichl 2007), they showed that SGD will 'prefer' wider basins under the heavy-tailed noise assumption, without an explicit mention of the cause of the heavy-tailed behavior.
In another recent study, Martin & Mahoney 2019) introduced new approach for investigating the generalization properties of deep neural networks by invoking results from heavy-tailes random matrix theory. They empirically showed that the eigenvalues of the weight matrices in different layers exhibit a heavy-tailed behavior, which is an indication that the weight matrices themselves exhibit heavy tails as well (Ben Arous & Guionnet 2008). Accordingly, they fitted a power law distribution to the empirical spectral density of individual layers and illustrated that heavier-tailed weight matrices indicate better generalization. Very recently, (Simçekli et al. (2020) formalized this argument in mathematccally rigorous framework and showed that such a heavy-tailed behavior diminishes the "effective dimension' of the problem, which in results in improved generalization. While these studies form an important initial step towards establishing the connection between heavy tails and generalization, the originating cause of the observed heavy-tailed behavior is yet be understood.
In this paper, we argue that these three seemingly unrelated perspectives for generalization are deeply linked to each other. We claim that, depending on the choice of the algorithm parameters r and b. the dimension d, and the curvature of f (to be precised in Section 3). SGD exhibits a 'heavy-tail phenomenon', meaning that the law of the iterates converges rigorously prove that, this phenomenon is not specific to deep learning and in fact it can be observed even in surprisingly simple settings: we show that when f is chosen as a simple quadratic function and the data points are i.i.d. from an isotropic Gaussian distribution, the iterates can still converge to a heavy-tailed distribution with arbitrarily heavy tails, hence with infinite variance. We summarize contributions follows:
heavy-tailed distribution. We
1. When f is a quadratic, we prove that: (i) the tails become monotonically heavier for increasing curvature, increasing 7) or decreasing b, hence relating the heavy-tails to the ratio n/bb and the curvature, (ii) the law of the iterates converges exponentially fast towards the stationary distribution in the Wasserstein metric, (iii) there exists higher-order moment (e.g., variance) of the iterates that diverges at most polynomially-fai fast, depending on the heaviness of the tails at stationarity. 2. We support our theory with experiments conducted on both synthetic data and neural networks. Our experimental results confirm our theory on synthetic setups and also illustrate that the heavy-tail phenomenon is also observed in fully connected multi-layer neural networks.
To the best of our knowledge, these results are the first of their kind to rigorously characterize the empirically observed heave-tailed behavior of SGD with respect n, b, d, and the curvature, with explicit convergence rates.
TECHNICAL BACKGROUND
Heavy-tailed distributions with a power-law decay. In probability theory, a real-valued random variable X is said to be heavy-tailed if the right tail or the left tail of the distribution decays slower
We note that in concurrent work, which very recently appeared on arXiv, Hodgkinson & Mahoney 2020 showed that heavy tails with power laws arise in more general Lipschitz stochastic optimization algorithms that are contracting on average for strongly convex objectives near infinity with positive probability, Our Theorem | and Lemma are more refined as we focus on the special case of SGD with Gaussian data, where we are able to provide constants which explicitly determine the tail index as expectation over data and SGD parameters (see also eqn. (3.6)) Due the generality of their framework, (Hodgkinson Mahoney 2020 Thm 1) more implicit and cannot provide such characterization of these constants, however can applied to other algorithms beyond SGD. All our other results (including Theorem monotonicity of the tail-index and Corollary 9 central limit theorem for the ergodic averages) are all specific to SGD and cannot be obtained
under the framework of Hodgkinson & Mahoney (2020). We encourage the readers to refer to (Hodgkinson & Mahoney 2020) for the treatment of more general stochastic recursions.
2

---

Under review as a conference paper at ICLR 2021
than any exponential distribution. We say X has heavy (right) tail if lim P(X 2 2))e²² for any c > 0. Similarly, an I -alued random vector X has heavy tail if tu'x "X has heavy right tail for some vector gd-), where Sd := {u E R ||a]]| 1] is the unit sphere in R
Heavy tail distributions include a-stable distributions, Pareto distribution, log-normal distribution and the Weilbull distribution. One important class of the heavy-tailed distributions is the distributions with power-law decay, which is the focus of our paper. That is, P(X 2 x) ~ cg.= as x + oo for some co > 0 and a > O, where or > 0 is known as the tail-index, which determines the tail thickness of the distribution. Similarly, we say that the random vector X has power-law decay with tail-index if for some u E gd-1, we have P(u" X 2 x) ~ Cyz for some Co. a > 0.
Stable distributions. The class of a-stable distributions are an important subclass of heavy- distributions with a power-law decay, which appears as the limiting distribution of the generalized CLT for sum of i.i.d. random variables with infinite variance (Lévy) 1937). A random variable X follows a symmetric a-stable distribution denoted as X SaS((r) (a) its characteristic function takes the form: E [e*t]] = exp (-0[((1). E R. where > 0 is the scale parameter that measures the spread of X around 0, and a E (0, 2] is known as the tail-index, and SaS becomes heavier-tailed as a gets smaller. The probability density function of symmetric o-stable distribution, a E (0, 2]. does not yield closed-form expression in general except for few special cases. When a = 1 and a 2,
SaS reduces to the Cauchy and the Gaussian distributions, respectively. When 0 < a < 2, a-stable distributions have their moments being finite only up the order a in the sense that [| [*] < co
and only if p < which implies infinite variance.
Wasserstein metric. For any p 2 1, define (P*)) as the space consisting of all the Borel probability measures on I with the finite p-th moment (based on the Euclidean norm). For any two Borel probability measures V1, 122 E Pp (Idd), we define the standard p- p-Wasserstein metric (Villani 2009): Wp(P1, 12) := (inf IE [||Z,- 1211 where the infimum is taken over all joint distributions of the random variables Z1, Zz with marginal distributions V1, 1/2 respectively.
3 SETUP AND MAIN THEORETICAL RESULTS
Before stating our theoretical results in detail, let us informally motivate our main method of analysis. Suppose that the initial SGD iterate zo is in the domain of attraction of local minimum x, of and the function f is smooth and vell-approximated by a quadratic function in this basin. Under this assumption, by considering a first-order Taylor approximation of V (z)) around x., we have V (z)( V (0x,,) (r., + V (1.)
(x u x.). By using this approximation, we can approximate
the SGD recursion 1.3) as follows:
(n//b) Σ sen
V2 (n/b) Σ vEa (v2 (v2)(( ( (
Tk -6-1
(I- 2k-1 + 9k.
(3.1)
where I denotes the identity matrix of appropriate size. Here, our main observation is that the SGD recursion can be approximated by linear stochastic recursion, which gives us access to the tools from implicit renewal theory for investigating its statistical properties (Kesten 1973) Goldie [191). In renewal theoretic context, the object of interest would be the matrix (7 o HR), whose statistical properties determine the behavior of zu: depending the moments of this matrix, 2a can have heavy or light tails, or might even diverge.
In this study, we focus on the tail behavior of the SGD dynamics by analyzing it through the lens of implicit renewal theory. As, the recursion (3.1) is obtained by a quadratic approximation of the component functions f()), which arises naturally in linear regression, we will consider a simplified setting and rigorously study this dynamics in the case of linear regression.
We would like to underline that, in our analysis, the Taylor approximation 3..1 is not crucial. Indeed, we can easily extend our theory to more general non-linear recursions by imposing strict statistical assumptions on the loss function (which can be chosen non-convex) and the data distribution (Mirek) 2011). Unfortunately, such assumptions would either be trivially false for deep lcarning problems,
2 A real-valued random variable X has heavy (left) tail if limz P(X S =x = oo for any c <>0 O. 3 We say zo is in the domain of attraction of local minimum J., if gradient descent iterations to minimize f started at z0 with sufficiently small stepsize converge to x, as the number of iterations goes infinity.
3

---

Under review as a conference paper at ICLR 2021
e.g.. (Mirek 2011) cannot be verified in practice, e.g.. (Hodgkinson & Mahoney 2020p. In order to be able to provide explicit results with clear assumptions, we limit our scope to quadratic optimization, which turns out to be already fairly technical. We leave the analysis of the general case as natural next step of our work.
We now consider the case when f is quadratic, which arises in linear regression:
min F(x) == (1 [a v) ZER2
(3.2)
where the data y) comes from unknown distribution D with support R x R. Assume have access to i..d. samples (a;, 31) from the distribution D where fz(((()) a.(a;' x y1) is an unbiased estimator of the true gradient V=(=). The curvature, i.c. the value of second partial derivatives, of this objective around minimum is determined by the Hessian matrix E(aa") which depends on the distribution of a. In this setting, SGD with batch size leads to the iterations
Tkk 1 1 + 2h with M& == 1 - (n/b) HR: H₂ = Even, a.a7 Qk == (n/b) Σ iES a,ll
(3.3)
where S2g := {b(k - 1) 1, ()) + 2.... bk} with [2x = Here, for simplicity, we assume that we are in the one-pass regime (also called the streaming setting (Frostig et al.) 2015 Jain et al., 2017)) where each sample is used only once without being recycled. Our purpose in this paper is to show that heavy tails can arise in SGD even in simple settings such as when the input data a, is Gaussian, without the necessity to have a heavy- tailed input data [4) Consequently, we make the following assumptions on the data throughout the paper:
(A1) ag ~ (N, of Ia) are i.i.d.
(A2) y/ are i.i.d. with continuous density whose support is IR with all the moments finite.
Assumption (A2) would be satisfied in many cases, for instance when y is normally distributed on R. Note that by Assumption (A1), the matrices M2 = I- - H. are i..d. and the Hessian matrix of the objective (.2)) satisfies B(aa")
o² la where the value of o² determines the curvature around minimum; smaller (larger) o² implies the objective will grow slower (faster) around the minimum and the minimum will be flatter (sharper) (see e.g. Dinh et al. (017)). We introduce
h(s) == lim M M. 11
(3.4)
which arises in stochastic matrix recursions (see e.g. Buraczewski et al. (0144) where || || denotes the matrix 2-norm (i.c. largest singular value of matrix). Since M we have h(s) < oo. Let us also define
< for all k and > 0,
1 = M
and p== oo (2k) log (largest eigenvalue of TT (3.5)
The latter quantity called the top Lyapunov exponent of the stochastic recursion (3.3 Furthermore, exists.
if p exists and is negative, it can be shown that a stationary distribution of the recursion (3.
In the Appendix (see Lemma [4). we show that under our assumptions,
h(s)) E [I](T (n/b) H) e [1"] for p <, where H is matrix with the same distribution as H1, and is the first basis vector.
p E log (T H)
(3.6)
In the following, we show that the limit density has polynomial tail with a tail-index given precisely by o, the unique critical value such that h(a)) = 1. The result builds on adapting the techniques de- veloped in stochastic matrix recursions (Alsmeyer & Mentemeier] 2012] Buraczewski et al.) (016) to our setting. Our result shows that even in the simplest setting when the input data is Gaussian without any heavy tail, SGD iterates can lead to heavy-tailed stationary distribution with an infinite variance. To our knowledge, this is the first time such a phenomenon is proven in the linear regression setting.
(.3). If P < O, then SGD iterations admit a unique Theorem 1. Consider the SGD iterations stationary distribution Ioc which satisfy
lim P x0'xoo > >t) eo (u),
u E Ed-1-
(3.7)
for some positive and continuous function functioonn ea on the unit sphere gd-1, where a the unique positive value such that h(x)) I.
'Note that if the input data is heavy-tailed, the stationary distribution of SGD automatically becomes heavy- tailed, see (urrcczwwkii et al. (2012) for details. In our context, the challenge is to identify the occurrence of the heavy tails when the distribution of the input data light-tailed, such simple Gaussian distribution.
4

---

Under review as a conference paper at ICLR 2021
As Martin& & Mahoney 2 showing that the tail-index of the density of the network weights is closely related to the generalization performance, where smaller tail-index indicates better generalization, a natural question of practical importance is how the tail-index depends on the parameters of the problem including the batch size, dimension and the stepsize. We prove that larger batch sizes lead to lighter tail (i.e. larger a),, which links the heavy tails to the observation that smaller b yields improved generalization in a variety of settings in deep learning (Keskar al. 2016 Panigrahi al. 2019 Martin & Mahoney 2019). We also prove that smaller stepsizes lead to larger a, hence lighter tails, which agrees with the fact that the existing literature for linear regression often choose 1) small enough to guarantee that variance of the iterates stay bounded (Dieuleveut et al. 201 Jain et al. (017).
: Simsekli et al. (2020) provide both numerical and theoretical evidence
Theorem 2.
The tail-indes is strictly increasing in batch size b and strictly decreasing in stepsize n and variance o² provided that a 2 1. Moreover the tail-index a is strictly decreasing in dimension d.
Next result characterizes the tail-index a depending on the choice of the batch size b. the variance o². which determines the curvature around the minimum and the stepsize; in particular we show that the stepsize exceeds an explicit threshold, the stationary distribution will become heavy tailed with an infinite variance.
Proposition 3. Let Merit G*(d+++1 The following holds: (i) There exists Mmax > Meerit such that
2b
for any Merit < 1) < Tmaz, Theorem holds with tail index 0 < 2. (ii) If Meritt Theorem 7 holds with tail index a = 2. (iii) 1f E (0, Moro), then Theorem 1 holds with tail index a > 2.
Relation to first exit times. Proposition 3 implies that, for fixed and b, the tail-index will be decreasing with increasing σ. Combined with the first-exit-time analyses of Simseklii et al. (2019b); Nguyen al. (2019), which state that the escape probability from a basin becomes higher for smaller o, our result implies that the probability of SGD escaping from a basin gets larger with increasing curvature; hence providing an alternative view for the argument that SGD prefers flat minima.
Three regimes for stepsize. Theorems 2 and Proposition 3 identify three regimes: (I) convergence to limit with a finite variance if p < and a > 2; (II) convergence to a heavy-tailed limit with infinite variance if < 0 and a < 2; (III) > 0 when convergence cannot be guaranteed. For Gaussian input, if the stepsize is small enough, smaller than nerse. by Proposition S p < 0 and a > 2, therefore regime (I) applies. As we increase the stepsize, there is a critical stepsize level Merse for which 17 > Merit leads a < 2 as long as 7 < Mmex where Mmar is the maximum allowed stepsize for ensuring convergence (corresponds to p = O). A similar behavior with three (learning rate) stepsize regimes was reported in Lewkowyez et al. (2020) and derived analytically for one hidden layer linear networks with large width. The large stepsize choices that avoids divergence. called the catapult phase for the stepsize, yielded the best generalization performance empirically, driving the iterates to flatter minima in practice. We suspect that the catapult phase in Lewkowyez et al. (2020) corresponds to regime (II) in our case, where the iterates are heavy-tailed, which might cause convergence flatter minima as the first-exit-imme discussions suggest (Simşekli al.) (019a).
Moment Bounds and Convergence Speed. Theorem T is of asymptotic nature which characterizes the stationary distribution &he of SGD iterations with tail-index a. Next, we provide non-asymptotic moment bounds for I& at each k-th iterate, and also for the limit Foo-
Theorem 4. (i) If the tail-index a S 1, then for any p E (0,a), at), we have h(()) < 1 and
E| < (h(p)) + 1- -m((p))* El
(3.8)
1- h(())
(ii) If the tail-inder 1, then for any p a1, we have h(p) < and any e >> 0 such that (1 + +))(p)) < 1, we have
E E| < ((1 (11+ +))(())) + 1 1- ((1 + c)h()))* (1 - (1++)
E 1. (3.9)
- e1+)))(p) (1+6)=- - -1p
Theorem shows that when p < a the upper bound on the p-th moment of the iterates converges exponentially the p-the moment of qı when < 1 and neighborhood of the p-moment of qı when a > 1, where Qi is defined in (3.3). By letting l + oo and applying Fatou's 's lemma, we can also characterize the moments of the stationary distribution.
5

---

Under review as a conference paper at ICLR 2021
Corollary 5. (i) If the tail-indes S 1, then for any p (0, ao0 1l' 1 h-h( Elgg Bllgll,, where
h(p) < 1. (ūi If the tail-index a > 1, then any p E (1, we have h(p) < and for any c >
-1+0) (l such that (1 <)h(p) 1, we have Bl 1| $ (1+c)))(p) ((1+))=1-1))
Next, we will study the speed of convergence of the k-th iterate Iy its stationary distribution Tec. in the Wasserstein metric Wp for any 1 1 a.
Theorem 6. Assume Or > Let us, Usa denote the probability laws of Ii and too respectively. Then (vk Moc) S (h(p)) )so) for any 1 S p < o, where the convergence rate
(h(p)) E 1),
Theorem Giswws that in case fast, i.e. with a linear convergence in the p- --Wasserstein metric. We can also characterize the constant h(p) in Theorem 6 which controls the convergence rate as follows:
the convergence to heavy tailed distribution occurs relatively
Corollary 7. When 7 < Merit
odd4b+1jj the tail-index a > 2.
2b
Wy(Kk, Poo) S (1 2njo² (1 7/ ) k/2 W2( V50).
(3.10)
Theorem d works for any p < At the critical p a, Theorem 1 indicates that |E|[ |l oo, and therefore has || + 00 as the number of iterates à increases. By adapting the proof of Theorem we have the following result stating that the moments of the iterates of order a go to infinity but this speed can only be polynomially fast.
- xc, 5l which serves as an evidence that the tail gets heavier
Proposition 8. Given the tail-index a, we have E|| l co. Moreover, and | = O(k*) if >> 1.
xx| = O(k) 1
It may be possible to leverage recent results the concentration of products of i.d.d random matrices
(Huang et al. 2020: Henriksen & Ward 2020) to study the tail of xy for finite k; which can be a future research direction.
Extension to Gau-Gansiaan data. Our main purpose in Theorem to show that heavy tails can arise even in the simplest setting when the input is Gaussian. However, Proposition I extends naturally if the input a; is not necessarily Gaussian. For example, we assume that the distribution of a; has support of IRd and has finite second moment, it can be checked that our proof technique for Theorem I will be still applicable and Theorem [ will hold with h((s) defined by (3.4). The only
difference is that when input is not Gaussian, the explicit formula (36)) for h(s) will not hold as an equality but will become an inequality, i.e.
h(s) & h(s) == E [I[ - H)
(3.11)
where h(s) is defined by (3.4 This inequality is just consequence of sub- aub-mltiplicattvityy of matrix products appearing in 3.4p. If ā such that ((a)
then by 1.. ā is lower bound on the tail index that satisfies (()a) = where h is defined as in (.4). In other words, when the input is not Gaussian, we have ā S a and therefore serves as lower bound on the tail index. Furthermore, Theorem
2 will also apply in the sense that â. â will be strictly increasing in batch size b and strictly increasing in stepsize 7) and variance x² provided that 1.
Extension to non-quadratic optimization. We note that extending our results beyond quadratic optimization is possible, if the gradients have asymptotic linear growth. For example, consider the cost F(z) [[[(a"= x y)] with loss function f. The choice of {()) = || /2 is the standard linear regression setting where the gradient of F' is an affine function
and in this case [[V[(z) - Ex is bounded if we choose Σ- = E[aa""] Theorem | will hold as long as there exists matrix Σ such that [[) - Σx| stays bounded even if the function is not a quadratic function, the proof is straightforward and would be based on verifying that the conditions of (Mirek) 2011 Theorem 1.4) hold in the setting of Theorem T This type of optimization problems arises for instance in robust regression where the objective is F F(x) (a 2: - b) >g(x:) with a penalty function g(x:) whose gradient is bounded and a tunable parameter A. The boundedness of the gradient of g(z) results in at-most linear growth of g(z) and allows robustness outliers where the parameter can be used to adjust the robustness level desired. Examples for the choice of g(z) include the smoothly clipped
OOterwiise one can construct subsequence Jny that is bounded in the space I converging Too which would he contradiction.

---

Under review as a conference paper at ICLR 2021
absolute deviation (SCAD) penalty (Loh & Wainwright (2015)) Huber loss (Huber 1992) or the exponential squared loss when (() = - exp(- (xx(--[=]//c where c is a tuning parameter.
2. by Corollary 5 second moment of the iterates 2g are finite, in which case central limit theorem (CLT) says that if the cumulative sum of the iterates SK = _k=1 Tyy is scaled properly, the resulting distribution is Gaussian. In the case where a the variance of the iterates is not finite; however in this case, we derive the following generalized CLT (GCLT) which says that if the iterates are properly scaled, the limit will be an o-stable distribution. This stated in a more precise manner as follows.
Generalized Central Limit Theorem for Ergodic Averages. When
Corollary 9. Assume p < O so that Theorem holds. Then, we have the following:
(i) a E (0, 1) (1,2). then there is a sequence dx- = dx (x)(a) and a function Ca :d=1 + such that as K + oo the random variables K =/2 (Sk - dx) converge in law to the a-stable random variable with charucteristic function
functtioo Y (1u) = exp(1 (u)). for > and E Sd-1.
(ū) If 1, then there are functions T, : oo) - The and C1= S + C such that as K - oo the random variables K K-SSK- KE [K- converge in law to the random variable with characteristic function Y (te) = exp (1C)(v) + (())),(())), for L 0 and v E ga-1
(ii) If a= 2, then there a sequence dx = dg (2) and a function C2 Sd + TK such that as K + so the random variables (Klog K) - (SK - dx) converge in law to the random variable with characteristic function T 22((v) = exp (12 (2))) for 1 O and v E Sd-1
(iv) If E (0, 1), then dx = 0, and if (1, then dx= = KT, where T = Ju 20 (dx).
In addition to its evident theoretical interest, Corollary has also an important practical implication: estimating the tail-index of a generic heavy-tailed distribution is a challenging problem (see e.g. Clauset et al. (009);; Goldstein et al. (2004); [Bauke| (2007); however, for the specific case of o-stable distributions, accurate and computationally efficient estimators, which do not require the knowledge of the functions C.. T. &, have been proposed (Mohammadi et al., 2015). Thanks to Corollary | we will be able to use such estimators in our numerical experiments, as we will detail in the next section.
We finally note that the gradient noise in SGD is actually both multiplicative and additive (Dieuleveut let al. aa); a fact that is often discarded for simplifying the mathematical analysis. In the linear regression setting, we have shown that the multiplicative noise Mj is the main source of heavy-tails, where deterministic Mr would not lead to heavy tails 5 In the light of our theory, in Appendix A we discuss in detail the recently proposed stochastic differential equation (SDE) representations of SGD in continuous- time and argue that, compared to classical SDEs driven by a Brownian motion (e.g.. (Jastrzebski et al. [0177] Cheng et al., 2019), SDEs driven by heavy-tailed a-stable Lévy processes (e.g., Simsekli et 2019b)) are more adequate when a < 2.
EXPERIMENTS
In this section, present experimental results on both synthetic and real data, in order to illustrate that our theory also holds in finite-sum problems (besides the streaming setting). Our main goal will be to illustrate the tail behavior of SGD by varying the algorithm parameters: depending on the choice of the stepsize and the batch-size b, the iterates do converge to a heavy-tailed distribution (Theorem 1 and the behavior of the tail-index obeys Theorem 2
Synthetic experiments. In our first setting, we consider a simple synthetical setup, where we assume that the data points follow Gaussian distribution. We will illustrate that the SGD iterates can become heavy-tailed even in this simplistic setting where the problem is a simple linear regression with all the variables being Gaussian. More precisely, we will consider the following model:
Fo ~ NN(0000)))
04 a NNO, 02 IT) We Vilas, xo ~ N (a. no, (,),o))
(4.1)
where zo, aj E Rd, Mi E R for 1, and a, By 0.
In our experiments, we will need to estimate the tail-index a of the stationary distribution V.o- Even though several tail-index estimators have been proposed for generic heavy-tailed distributions in the literature (Paulauskas & Vaičiulis 201I), we observed that, even for small d, these estimators can yield inaccurate estimations and require tuning hyper-parameters, which is non-trivial. We
'F.g g.. if Mj is deterministic and ge Gaussian, then Jy is Gaussian for all k. and is Joo if the limit exists.
7

---

Under review as a conference paper at ICLR 2021
circumvent this issue thanks the GCLT in Corollary 9 since the average of the iterates is guaranteed to converge to a multivariate a-stable random variable, we can use the tail-index estimators that are specifically designed for stable distributions. By following Tzagkarakis al. (2018); Şimşekli et al. (2019b), we use the estimator proposed by MMhhammai et al. (2015). which is fortunately agnostic to the scaling function Ca. The details of this estimator are given in Appendix B
To be able to benefit from the CLT. we are required to compute the average of the 'centered' iterates: K-Ko Σk -
0.02
0.08
1.3
b-10
- z). where Ko is a 'burn-in' period aiming to discard the initial phase of SGD, and the mean of Voo is given by F SR. oo (dx)
b-
0.3
01
(a)
2.0
(A (4"A)='A") A"y
2:00
3.75
as long as a > 17 where the i-th row of A E Ruxd contains a, and y = WM,..... Wn] E R". We then repeat this procedure 1600 times for different initial points and obtain 1600 different random vectors, whose distributions are supposedly close to an a-stable distribution. Finally, we run the tail-index estimator of Mohammadii et al. (2015) on these random vectors to estimate a.
3.95
1.0
1.90
1.25
43
0.0
0.5
9b
(b)
(c)
Figure 1: Behavior of with (a) varying stepsize n and batch-size b. (b) d and a, (c) under RMSProp.
In our first experiment, we investigate the tail-index of the stationary measure 1/20 for varying stepsize 17 and batch-size b. We set d = 100 first fix the variances o = 1. 0g = By = 3, and generate run the SGD recursion (3.3) for a large number of iterations and vary v from 0.02 to 0.2 and from 1 to 20. We also set K 1000 and Ko 500. Figure (igure[(a)innn) illustrates the results. We can observe that, increasing 7) and decreasing b both result in decreasing a, where the tail-index can be prohibitively small (i.e., a < 1, hence even the mean of V/c not defined) for large 7). Besides, we can also observe that the tail-index is in strong correlation with the ratio n/b.
fag.y: )=>) by simulating the statistical model. Then, by fixing this dataset,
In our second experiment, we investigate the effect of and a on a. In Figure [(b) (left), we set d = 100, = 0.1 and 6 = 5 and vary from 0.8 to 2. For each value of a, we simulate a new dataset from by using the generative model and run SGD with K, Kg. We again repeat each experiment 1600 times. We follow a similar route for Figure ( (right): we fix a 1.75 and repeat the previous procedure for each value of ranging from to 50. The results confirm our theory: a decreases for increasing and d, and we can observe that for a fixed b and 1) the change in d can abruptly alter a.
In our final synthetic data experiment, we investigate how the tails behave under adaptive optimization algorithms. We replicate the setting of our first experiment, with the only difference that we replace SGD with RMSProp (Hinton et al. 2012). As shown in Figure [[c] the 'clipping' effect of R.MSProp as reported in ZZang et al. (2019) prevents the iterates become heavy-tailed and the vast majority of the estimated tail-indices is around 2. indicating a Gaussian behavior. On the other hand, we repeated the same experiment with the dariance-reduced optimization algorithm SVRG (Johnson & Zhang 2013), and observed that for almost all choices of and b the algorithm converges near the minimizer (with an error in the order of 10 6), hence the stationary distribution Voc seems to be a degenerate distribution, which does not admit a heavy-tailed behavior. Regarding the observed link between heavy-tails and generalization (Martin & Mahoney) 2019 Şimşekli et al., 2020), this behavior of RMSPPop and SVRG might be related to their ineffective generalization performance as reported in Keskar & Socher (011)): Defazio & Bottou (019)).
Experiments on fully connected neural networks. In the second set of experiments, we investigate the applicability of our theory beyond the quadratic optimization problems. Here, we follow the setup of Şimşekli et al. (2019a) and consider fully connected neural network with the cross entropy
'The form of a can be verified by noticing that [[a] converges to the minimizer of the problem by the law of total expectation. Besides, our GCLT requires the sum of the iterates to be normalized by (x (// however, for a finite K, normalizing by K-ko results in a scale difference, to which our tail-index estimator is agnostic.
8

---

Under review as a conference paper at ICLR 2021
Layer
Layer2
Layer
Layer
Layer
7.00
2.00
2.0
1.75
1.75
2.3
1.5
2.5
1.5
1.25
125
1.0
0.30
0.05
0.00
5.05
5.50
0.05
0.00
0.02
5.54
2.50
0.53
0.04
0.30
0.02
0.04
(a) MNIST
(b) CIFARIO
Figure 2: Results on FCNs. Different markers represent different initializations with the same 17, b.
loss and ReLU activation functions on the MNIST and CIFARIO datasets. We train the models by using SGD for 10K iterations and we range y from 10-4 to 10-2 and b from 1 to 10. Since it would be computationally infeasible to repeat each run thousands of times experiments, in this setting we follow a different approach based on (i) (Simşekli et al., 2019a) that suggests that the tail behavior can differ in different layers of neural network, and (ii) (De Bortoli eet al. (0200) that shows that in the infinite width limit, the different components of a given layer of a two-layer fully connected network (FCN) becomes independent. Accordingly, we first compute the average of the last 1K SGD iterates, whose distribution should be close an a-stable distribution by the GCLT. We then treat each layer as collection of i.i.d. a-stable random variables and measure the tail-index of each individual layer separately by using the the estimator from Mohammadi et al.) (2015). Figure showss the results for a three-layer network (with 128 hidden units at each layer). whereas we obtained very similar results with two-layer network as well. We observe that, while the dependence of a on n differs from layer to layer, in each layer the measured a correlate very-well with the ratio 1//b in both datasets.
did in the synthetic data
Experiments on VGG networks. In our last set of experiments, we evalu- ate our theory on VGG networks (Si monyan & Zisserman 2015) with II layers (10 convolutional layers with max-pooling and ReLU units, followed by a final linear layer), which contains 10M parameters. We follow the same procedure as we used for the fully con- nected networks, where we vary v) from 10-4 to 1.7 x 10-3 and b from to 10.
Laver:
Layer2
Layera
18
1.5
18
x10
n/
100
Layers
Layens
Layer??
Layera
615
4/3
Lavers
Loyer:0
Layen:11
The results are shown in Figure Sim- ilar to the previous experiments, we ob- serve that a depends on the layer. For the intermediate layers (Layers 2-8), the tail index correlates well with the ratio n/b, whereas the first and last two convolutional layers (Layers and 10) exhibit Gaussian behavior (a z 2).
10
1.2
1.
x70
310
100
Figure 3: Results on VGG networks. The values of a that
exceeded 2 is truncated to 2 for visualization purposes.
On the other hand, the tail-index of the last layer (which is linear) does not correlate with either v or b. support
These observations provide further support for our theory and show that the heavy-tail phenomenon also occurs in neural networks, whereas is potentially related to r and b in a more complicated way.
5 CONCLUSION AND FUTURE DIRECTIONS
We studied the tail behavior of the SGD in a quadratic optimization problem and showed that depending on the curvature, 7), and b, the iterates can converge to a heavy-tailed random variable. We further supported our theory with experiments conducted on fully connected neural networks and illustrated that our results would also apply to more general settings and hence provide new insights about the behavior of SGD in deep learning. This study also brings up number of future directions. (i) Our proof techniques are for the streaming setting, where each sample is used only once. However, in practice SGD is typically implemented on the finite-sum problem (.2) with multiple passes over the data. Extending our results to this scenario and investigating the effects of finite-sample size on the tail index and generalization would be an interesting future research direction. (ii) We suspect that the tail index of the SGD iterates may have an impact on the time required to escape saddle point and this can be investigated further as another future research direction.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Alnur Ali, Edgar Dobriban, and Ryan J Tibshirani. The implicit regularization of stochastic gradient flow for least squares. arXiv preprint arXiv:2003.078% 2020.
Gerold Alsmeyer and Sebastian Mentemeier. Tail behaviour of stationary solutions of random differ- ence equations: the case of regular matrices. Journal of Difference Equations and Applications, 18 335-3305-33 2012.
Heiko Bauke. Parameter estimation for power-law distributions by maximum likelihood methods. The European Physical Journal B, 5882)))1177773, 2007.
Gérard Ben Arous and Alice Guionnet. The spectrum of heavy tailed random matrices. Communica- tions in Mathematical Physics, 278(3):71--51, 2008.
Jean Bertoin. Lévy Processes. Cambridge University Press, 1996.
Dariusz Buraczewski, Ewa Damek, and Mariusz Mirek. Asymptotics of stationary solutions of multivariate stochastic recursions with heavy tailed inputs and related limit theorems. Stochastic Processes and Their Applications, 122(1):42-67 2012.
Dariusz Buraczewski, Ewa Damek, Yves Guivarc'h, h, and Sebastian Mentemeier. On multidimensionall Mandelbrot cascades. Journal of Difference Equations and Applications,
2014.
Dariusz Buraczewski, Ewa Damek, and Tomasz Przebinda. On the rate of convergence in the Kesten renewal theorem. Electronic Journal of Probaiblity, 20(22):1-35. 2015.
Dariusz Buraczewski, Ewa Damek, and Thomas Mikosch. Stochastic Models with Power-Law Tails. Springer, 2016.
Pratik Chaudhari and Stefano Soatto. Stochastic gradient descent performs variational inference, con- verges limit cycles for deep networks. In International Conference on Learning Representations, 2018.
Xiang Cheng, Dong Yin, Peter L Bartlett, and Michael I Jordan. Stochastic gradient and langevin processes. arXiv preprint arXiv:1907.03223. 2019.
Aaron Clauset, Cosma Rohilla Shalizi, and Mark EJ Newman. Power-law distributions in empirical data. SIAM Review, 51(4):661-70) 2009.
Valentin De Bortoli, Alain Durmus, Xavier Fontaine, and Umut Simsekli. Quantitative propagation of chaos for sgd in wide neural networks. arXiv preprint arXiv:2007.06352, 2020.
Aaron Defazio and Leon Bottou. On the ineffectiveness of variance reduced optimization for deep learning. Advances in Neural Information Processing Systems, pp. 1755-1765, 2019.
Aymeric Dieuleveut, Alain Durmus, and Francis Bach. Bridging the gap between constant step size stochastic gradient descent and Markov chains. arXiv preprint 1rXIv:1707.06366, 2017a.
Aymeric Dieuleveut, Nicolas Flammarion, and Francis Bach. Harder, better, faster, stronger con- vergence rates for lquat-s regression. The Journal of Machine Learning Research, 18(1): 3520-3570, 2017b.
Laurent Dinh, Razvan Pascanu, Samy Bengio, and Yoshua Bengio. Sharp minima can generalize for deep nets. In Proceedings of the 34th International Conference on Machine Learning-Vonr Volume 70, pp. 1019-1028. JMLR. org, 2017.
Holger Fink and Claudia Klüppelberg. Fractional Lévy-driven stochastic differential equations. Bernoulli, 17(1):844506, 2011.
processes and
Roy Frostig, Rong Gc, Sham M Kakade. and Aaron Sidford. Competing with the empirical risk minimizer in a single pass. Conference on Learning Theory, pp. 728-763, 2015.
Charles M Goldie. Implicit renewal theory and tails solutions of random equations. Annals of Applied Probability, 1(1):126-1666 1991.
10

---

Under review as a conference paper at ICLR 2021
Michel L Goldstein, Steven A Monri,, and Gary G Yen. Problems with fitting to the power-law distribution. The European Physical Journal B-Condensed Matter and Complex Systems, 41(2): 255-258, 2004.
Amelia Henriksen and Rachel Ward. Concentration inequalities for random matrix products. Linear Algebra and its Applications, 594:81 10::8--98 1-94, 2020.
Geoffrey Hinton, Nitish Srivastava, and Kevin Swersky. Overview of mini-batch gradient descent. Neural Networks for Machine Learning, Lecture 6a, 2012. URL hattp:///ww wttp:/s.s..o.oooooooooooooo toronto
Sepp Hochreiter and Jürgen Schmidhuber. Flat minima. Neural Computation, 9(1):1-42, 1997.
Liam Hodgkinson and Michael W Mahoney. Multiplicative noise and heavy tails in stochastic optimization. arXiv preprint Ttth:2000006299. 2020.
Wenqing Hu, Chris Junchi Li, Lei Li, and Juan-Guo Liu. On the diffusion approximation of nonconvex stochastic gradient descent. Anmals of Mathematical Science and Applications, 4(1):3-32, 2019.
De Huang, Jonathan Niles-Weed, Joel A. Tropp, and Rachel Ward. Matrix concentration for products. arXiv preprint mrtXXi::0003.05435 2020.
Peter Huber. Robust estimation of a location parameter. In Breakthroughs in statistics, pp. 492-518. Springer, 1992.
Prateek Jain, Sham M Kakade, Rahul Kidambi, Praneeth Netrapalli, and Aaron Sidford. Accelerating stochastic gradient descent. In Proc. STAT, volume 1050, pp. 26, 2017.
Stanislaw Jastrzębski, Zachary Kenton, Devansh Arpit, Nicolas Ballas, Asja Fischer, Yoshua Bengio, and Amos Storkey. Three factors influencing minima in SGD. arXiv preprint arXiv: 11Xiv:1711.046/ 1.04623, 2017.
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Advances in Neural Information Processing Systems, pp. 315-323, 2013.
Nitish Shirish Keskar and Richard Socher. Improving generalization performance by switching from Adam to SGD. arXiv preprini arXiv: arXiv:1712.07628, 2017.
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang. On large-batch training for deep learning: Generalization gap and sharp minima. arXiv preprint arXiv: (tll::609..400.0 2016.
Harry Kesten. Random difference equations and renewal theory for products of random matrices. Acta Mathematica, 131:207-248, 1973.
Paul Lévy. Théorie de l'addition des variables aléatoires. Gauthiers-Ville Paris, 1937.
Aitor Lewkowycz, Yasaman Bahri, Ethan Dyer, Jascha Sohl-Dickstein, and Guy Gur-Ari. The large learning rate phase of deep learning: the catapult mechanism. arXiv preprint arXiv:2003.02211. 2020.
Qianxiao Li, Cheng Tai, and Weinan E. Stochastic modified equations and adaptive stochastic gradient algorithms. In Proceedings of the 34th International Conference on Machine Learning. pp. 2212211222 -21 10, 06-11 11 Aug 2017.
Po-Ling Loh and Martin J Wainwright. Regularized m-estimators with nonconvexity: Statistical and algorithmic theory for local optima. The Journal of Machine Learning Research, 16(1):559-616. 2015.
Stephan Mandt, Matthew D. Hoffman, and David M. Blei. A variational analysis of stochastic gradient algorithms. In International Conference on Machine Learning, pp. 354-363, 2016.
Charles H Martin and Michael W Mahoney. Traditional and heavy-tailed self regularization neural network models. arXiv preprint
2019.

---

Under review as a conference paper at ICLR 2021
Mariusz Mirek. Heavy tail phenomenon and convergence stable laws for iterated Lipschitz maps. Probability Theory and Related Fields, 151(3-4):705-733 2011.
Mohammad Mohammadi, Adel Mohammadpour, and Hiroaki Ogata. On estimating the tail index and the spectral measure of multivariate a-stable distributions. Metrika, 78(5):549-561, 2015.
Charles M Newman. The distribution of Lyapunov exponents: Exact results for random matrices. Communications in Mathematical Physics, 103(1):121-126, 1986.
Thanh Huy Nguyen, Umut Simsekli, Mert Gurbuzbalaban, and Gaël Richard. First exit time analysis of stochastic gradient descent under heavy-tailed gradient noise. In Advances in Neural Information Processing Systems, pp. 273-283, 2019.
Bernt Øksendal. Stochastic Differential Equations: An Introduction with Applications. Springer Science & Business Media, 2013.
Abhishek Panigrahi, Raghav Somani, Navin Goyal, and Pranceth Netrapalli. Non-Gaussianity of stochastic gradient noise. arXiv preprint 19X1v:1910.09626, 2019.
Vygantas Paulauskas and Marijus Vaičiulis. Once more on comparison of tail index estimators. arXiv preprint arXiv: 1242 2011.
Ilya Pavlyukevich. Cooling down Lévy flights. Journal of Physics A: Mathematical and Theoretical, 40241):1229--12313, 2007.
Shai Shaley-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In ICLR, 2015.
Umut Şimsekli, Mert Gürbüzbalaban, Thanh Huy Nguyen, Gaël Richard, and Levent Sagun. On the heavy-tailed theory of stochastic gradient descent for deep neural networks. arXiv preprint arXiv: 19/2.0008, 2019a.
Umut Şimşekli, Levent Sagun, and Mert Gürbüzzalaban. A tail-index analysis of stochastic gradient noise in deep neural networks. In International Conference on Machine Learning, pp. 5827-5837, 2019b.
Umut Şimşekli, Ozan Sener, George Deligiannidis, and Murat A Erdogdu. Hausdorff dimen- sion, stochastic differential equations, and generalization neural networks. arXiv preprint N03V:22006009313. 2020.
George Tzagkarakis, John P Nolan, and Panagiotis Tsakalides. Compressive sensing of tempo- rally correlated sources using isotropic multivariate stable laws. In 2018 26th European Signal Processing Conference (EUSIPCO), pp. 1710-1714, IEEE, 2018.
Cédric Villani. Optimal Transport: Old and New. Springer, Berlin, 2009.
Jingzhao Zhang, Sai Praneeth Karimireddy, Andreas Veit, Seungyeon Kim, Sashank J Reddi, Sanjiv Kumar, and Suvrit Sra. Why ADAM beats SGD for attention models. arXiv preprint 1rXiv:1912.03 2019.
Zhanxing Zhu, Jingfeng Wu, Bing Yu, Lei Wu, and Jinwen Ma. The anisotropic noise in stochastic gradient descent: Its behavior of escaping from minima and regularization effects. arXiv preprint arXiv:1803.00195. 2018.
12

---

Under review as a conference paper at ICLR 2021
A A NOTE ON STOCHASTIC DIFFERENTIAL EQUATION REPRESENTATIONS FOR SGD
In recent years, popular approach for analyzing the behavior of SGD has been viewing it as a discretization of a continuous-ting stochastic process that can be represented via a stochastic differential equation (SDE) (Mandt et al., 2016 Jastrzebski et al. 2017: Li et al., 2017 Hu et al. 2019| Zhu et al., 20188] Chaudhari & Soatto| 2018, Simşekli et al. 2019b While these SDEs have been useful for understanding different properties of SGD, their differences and functionalities have not been clearly understood. In this section, in the light of our theoretical results, we will discuss in which situation their choice would be more appropriate. We will restrict ourselves the case where fz) is a quadratic function; however, the discussion can be extended to more general f.
The SDE approximations are often motivated by first rewriting the SGD recursion as follows:
1k+1 2k Sr41 (æx) 2x - V (Ix) + 1
(A.1)
where (x() == (x)) [x)) called the 'stochastic gradient noise". Then, based on certain statistical assumptions on U2. we can view (A.I) as a discretization of an SDE. For instance, if we assume that the gradient noise follows a Gaussian distribution, whose covariance does not depend
on the iterate Tge i.e., n/U& s vTZz where Zx .N(0,,, (nn) for some constant d= > 0, we can see IA.I as the Mally-ma discretization of the following SDE with stepsize 1j (Mandt et al. 2016::
dr.- = - ((r)dd + dd
(A.2)
where B, denotes the d-dimensional standard Brownian motion. This process is called the Ornstein- Uhlenbeck (OU) process (see e.g. Øksendal (2013). whose invariant measure a Gaussian distribu- tion. We argue that this process can be a good proxy to (3.3) only when a 2 2, since otherwise the SGD iterates will exhibit heavy-tails, whose behavior cannot be captured by a Gaussian distribution. As we illustrated in Section to obtain large a, the step-size 7) needs to be small and/or the batch-size b needs to be large. However, it is clear that this approximation will fall short when the system exhibits heavy tails, i.c.. a < 2. Therefore, for the large n/ regime, which appears to be more interesting since it often yields improved test performance (Jastrzehski et al. 2017). this approximation would be inaccurate for understanding the behavior of SGD. This problem mainly stems from the fact that the additive isotropic noise assumption results in a deterministic Mj matrix for all k. Since there is no maltiplicative noise term, this representation cannot capture a potential heavy-tailed behavior.
A natural extension of the state-independent Gaussian noise assumption is to incorporate the covari- ance structure of Ug. In our linear regression problem, we can easily see that the covariance matrix of the gradient noise has the following form:
0² -f "b
Ex(x) = Cov(UR|z)= = diag(1 o x),
(A.3)
where o denotes element-wise multiplication and 0² is the variance of the data points. Therefore, we can extend the previous assumption by assuming Zz|ær NN (ar)). It has been observed that this approximation yields a more accurate representation (Cheng et al. 2019 Ali et al., 2020 Jastrzębski et al.) 2017). Using this assumption in (A.I) the SGD recursion coincides with the Euler-Maruyama discretization of the following SDE:
dx;- = - (xz)ddt + Vn (d.
4 -AT (AT A v) dt V 02n Vop diag(a:)dB.
(A.4)
where - denotes equality in distribution. The stochasticity in such SDEs is called often called multiplicative. Let us illustrate this property by discretizing this process and by using the definition of the gradient and the covariance matrix, we observe that (noting that N₂ ~ NO, 1))
02n2 b
Tb+1 = Ik n7 "AAA Axx - vA + V
diag(xx)
= =(1- -I-nAA A + v / diag Ib nA y,
M-nATA
(A.5)
13

---

Under review as a conference paper at ICLR 2021
where we clearly see the multiplicative effect of the noise, indicated by its name. On the other hand, we can observe that, thanks to the multiplicative structure, this process would be able to capture the potential heavy-tailed structure of SGD. However, there are two caveats. The first one is that, in the case of linear regression, the process is called a geometric (or modified) Prnstein-Uhlenbeen process which is an extension of geometric Brownian motion. One can show that the distribution of the process at any time t will have lognormal tails. Hence it will be accurate only when the tail-index is close to the one of the lognormal distribution. The second caveat is that, for more general cost function f. the covariance matrix is more complicated and hence the invariant measure of the process cannot be found analytically, hence analyzing these processes for a general f can be as challenging as directly analyzing the behavior of SGD.
The third way of modeling the gradient noise is based on assuming that it is heavy-tailed. In particular, we can assume that rjL's 1/1/aa La where [La]i SaS(ozzn/- for all i 1, I....,dd d. Under this assumption the SGD recursion coincides with the Euler discretization of the following Lévy-driven SDE (Simşekli et al. 2019b):
dx. (fx + F (01//// -T
(A.6)
where L denotes the a-stable Lévy process with independent components (see Section A. for
technical background on Lévy processes and in particular a-stable Lévy processes). In the case of linear regression, this processes is called a fractional OU process (Fink & Klüppelberg] (2011). whose invariant measure is also an a-stable distribution with the same tail-index a. Hence, even though it is based on an isotropic, state-independent noise assumption, in the case of large n//b regime, this approach can mimic the heavy-tailed behavior of the system with the exact tail-index a. On the other hand, Buraczewski et al. (2016) (Theorem 1.7 and 1.16) showed that if Us is assumed to heavy tailed with index a (not necessarily Sac) then the process zg will inherit the same tails and the ergodic averages will still converge to an SoS random variable, hence generalizing the conclusions of the SaS assumption to the case where Ug follows an arbitrary heavy-tailed distribution.
A.1 TECHNICAL BACKGROUND: LÉVY PROCESSES
Lévy motions (processes) stochastic processes with independent and stationary increments, which include Brownian motions as a special case, and in general may have heavy-tailed distributions (see e.g. |Bertoin (199)) for survey). Symmetric a-stable Lévy motion is a Lévy motion whose time increments are symmetric a-stable distributed. We define L," a d-dimensional symmetric a-stable Lévy motion as follows. Each component of L is an independent scalar a-stable Lévy process defined as follows:
(i) T 0 almost surely;
(ii) For any to < 4 < ... < IN, the increments I.g, LE _ are independent, n = 1,2,..., N;
(iii) The difference T.g T. and T, have the same distribution: (esS((=s))0 for <
(iv) L has stochastically continuous sample paths, i.e. for any 8 > 0 and 2 0, P[LL, Lgl
5) - 0 as
When a= 2, we obtain scaled Brownian motion special case, i.e. Lg 2BB, that the difference T.f T.g follows a Gaussian distribution. (0,0 2(t - s)).
B TAIL-INDEX ESTIMATION
In this study, we follow Tzagkarakis et al. 20118 Şimşekli et al. (2019)), and make use of the recent estimator proposed by Mohammadi et al. 2015
Theorem 10 MMhammadi et al. 2015) Corollary 2.4). Let {X be a collection strictly stable random variables in Rd with tail- index (0. 2] and K K1 K2, Define Y: ΣØ= X X for E [1, K2]l Then, the estimator
T
1
log ||Y|||
1 K K
Σ E=1
log IX:II).
(B.1)
log K₁
Kg i=1
14

---

Under review as a conference paper at ICLR 2021
converges 1/a almost surely, K2
As this estimator requires hyperparameter K1, at each tail-index estimation, we used several values for バ and we used the median the estimators obtained with different values K,, We provide the codes in the supplement, where the implementation details can be found. For the neural network experiments, we used the same setup as provided in the repository of ofimsmseli et al. (2019b).
C PROOFS OF MAIN RESULTS
C.I PROOF OF THEOREM I
Proof of Theorem 7
The proof follows from (Buraczewski et al. 2016 Thm 4.4.15) which goes
back to [Alsmeyer& & Mentemeier 2012 Theorem 1.1) and Kesten (Kesten, 1973 Theorem 6). See also (Goldie 1991 Buraczewski al. 2013). We recall that we have the stochastic recursion:
2k M + qk>
(C.1)
where the sequence (Ma, gs) are i.i.d. distributed (M, q) and for each k. (M& Tu) is independent of 1--1- To apply (Buraczewski et al. 2016 Thm 4.4.15), it suffices to have the following conditions being satisfied:
1. M is invertible with probability 1.
2. The matrix M has continuous Lehesgue density that is positive in neighborhood of the identity matrix.
3. p < 0 and h(a:) 1.
4. P(Mr q z) for every x.
5. E [[[M]] || + log" |M- < co.
6. 0 E| co.
All the conditions are satisfied under our assumptions. In particular, Condition and Condition are proved in Lemma [8] and Condition 2 and Condition 4 follow from the fact that M and q have continuous distributions. If p < O, then by Lemma [5] we have h(0) 1, h'(0) p < 0 and h(s) convex 8, and moreover by Lemma 16 we have lim inf h(s) > 1. Therefore, there exists some (0, oo) such that h(a) 1, which gives Condition 3. Finally, Condition 6 is satisfied by the definition of and by the Assumptions (A1)-(2).
C.2 PROOF OF THEOREM
Proof of Theurem We will split the proof of Theorem 2 into two parts:
(I) We will show that the tail-index a is strictly decreasing in stepsize and variance o² provided that a 2 1.
(II) We will show that the tail-index is strictly increasing in batch size provided that 2 1.
(III) We will show that tail-index a strictly decreasing dimension d.
First, let prove (I). Let == uar > 0 be given. Consider the tail-index function of a, i.e.
(a) == min (s: h(a, s) = 1},
where M(a, x) = 1s))) with emphasis on dependence on a.
By assumption, (a) 1. The function h(a, s) is convex function of (see Lemma 19 for > 1 and a strictly convex function of s for 2 0). Furthermore, it satisfies fa(a, 0) for every a 2 0 and h(0, s) 1 for every 0. We consider the curve
C : ((a, 8) (0, 00) [o] Maa, s) 1)-
15

---

Under review as a conference paper at ICLR 2021
This is the set of the choice of which leads to tail-index where 2 1. Since h is smooth in both a and 8, we can represent s as smooth function of a, i.c. on the curve
h(aa s(a)) = 0,
where 8(a) is a smooth function of a. We will show that s'(a) < i.e. we increase a; the tail-index s(a) will drop. Pick any (a., 8.) C, it will satisfy h(a., 8.) 1. We have the following facts:
The function h(a, 8) for either a = 0 or s This is illustrated in Figure with a blue marker.
(1 h(a,,s) 8) < for that h(a,, 0) = 1, h(a,, s,) = 1. From here, we see that the function h(a, s) is increasing at and we have its derivative
This follows from the convexity of h(a,, 8) function and the fact
Oh 0s
(a. 9a) >
(iii) The function h(a, 8.) is convex as function of by Lemma 19 it satisfies h(0, s.) h(a,,,, 8.) = Therefore, by convexity h(a, 8.) < for E (0, (0,s.): otherwise the function h(a, s.) would be constant function. We have therefore necessarily.
Oh (a., 8.) 0.
da
By convexity of the function h(a, s.), we have also h(a, 8.) 2 hhha, s.) Do a.) > h(a,, 8.)
ah (a., 8.)(a
Therefore, h(a,s.) s.) 1 for > a. Then, it also follows that h(a,8) > for a > a, and 8 > 8, (otherwise if h(a, s) S 1, we get a contradiction because h(0, s) h(a., > 1 and h(a, s) S is impossible due convexity). This is illustrated in Figure 4 where we mark this region as a rectangular box where h > 1.
(iv) By similar arguments we can show that the function h(a, s) < if (s, E (0.a.) x (1,s.). Indeed, if h ((a, s) 2 1 for some (s, a) (1, x a., this contradicts the fact that h(0, s) = 1 and h(a,, s) < proven in part (ii). This is illustrated in Figure where inside the rectangular box on the left-hand side, we have h <
S
h > 1
S *
h < 1
h h(a,s) = 1
1
h h 1
a
Figure 4: The curve hia, s) = in the (a, s) plane
Geometrically, see from Figure 4 that the curve s(a) as function of a, is sandwiched between two rectangular boxes and has necessarily s'(a) < 0. This can also be directly obtained rigorously from the implicit function theorem: if differentiate the implicit equation hia, s(a)) 0 with respect to a, we obtain
Öh
Oh
(a., S.)
(a., s.) (oo))s((()) (a.) 0.
da
0s
From parts (ii) (λái), we have dh (a., Sa) and 0h
(a., 8.). > 0. Therefore, have (a., 8.)
ah
8 s((0))
Ba
0,
(C.2)
Sh
Oo (a., 8.)
16

---

Under review as a conference paper at ICLR 2021
which completes the proof for 8, 2 1.
Next, let us prove (II). With slight abuse of notation, we define the function k(b,s) = h(ss) to
emphasize the dependence on b. We have
(
h(b, s) E
a
ei
(C.3)
where we used Lemma 14 When $ 2 1, the function x + we get for any b 2 2 and b E N.
||>|
is convex, and by Jensen's 's inequality,
h(b,8) E
1 b
ajaj
i
< E
1 - b-
Σ
azug T
i=1
1 b
E
aja T
h(b 1,8);
b
where we used the fact that ag are i.i.d. Indeed, from the condition for equality to hold in Jensen's inequality, and the fact that a, are i.i.d. random, the inequality above is striet inequality. Hence when d E N for any 2 1, /(b, s) is strictly decreasing in b. By following the same argument as in the proof of (I), we conclude that the tail-indes
strictly increasing batch size b.
Finally, let us prove (III). Let us show the tail-index a is strictly decreasing in dimension d. Since a; are i.i.d. and a, NN00, o II)). by Lemma 25
2a x (1-
a X2
a 12 XX
6/2
h(s) E
(C.4)
where X, Y are independent chi-square random variables with degree of freedom b and d 1 respectively. Notice that (s)s) is strictly increasing in d since the only dependence of h(s) on d is via Y, which is chi-square distribution with degree of freedom (d-1). By writing Y Z7 + Z where Z₁ N (0. 1) ii.d., it follows that h(s) is strietly increasing in d. Hence, by similar argument as in (I), we conclude that a is strictly decreasing in dimension
and a; are ii.dd N(0, (2) we can provide an alternative proof that the tail-index is strictly increasing in batch size b. It suffices to show that for any 2 1, h((s) is strictly decreasing the batch size b. By Lemma 25 when dl 1,
Remark 11. When
h(b. E [
2n X+
1200 b2
x2 + 12
6/27
XY
(C.5)
where h(b, s) is as in C.3 and X, Y are independent chi-square random variables with degree of freedom and d - 1 respectively. When d = 1, we have Y = 0, and
h(b,s) s) = E [11
11-2100 2no² b
1/
8/27
1102 =
x +
X2
X
(C.6)
b2
b
Since X is chi-square random variable with degree of freedom b, we have
b
k(b, s) =
E
11²2
Σ
Z
(C.7)
b
i=1
17

---

Under review as a conference paper at ICLR 2021
where Z₁ are ii.d. (0, 1) random variables. When 2 the function - [x]* is convex, and by Jensen's inequality, we get for any b 2 2 and b
110
1(b, 8)
Zj
b
j$i
no²
Σ
Zj
jts
6
no
Zz
1:66 1,5),
where used the fact that Z₁ are i..d. Indeed, from the condition for equality hold in Jensen's
inequality, and the fact that 7; are i..d. (0, 1) distributed, the inequality above a strict inequality. Hence when d 1 for any 2 1, k(b, 8) is strictly decreasing in b.
C.3 PROOF OF PROPOSITION
Proof of Proposition 3
We next prove (i). When 17 = Merit
26 o2(d+6+1)
that is n = 2b.
it follows from the proof of Proposition 23 that
2nj0² 2 b
1
P 5 log E
(212 + +... + Zid2za) 211 = 0. (C.8)
2
11
12
1=1
Note that since - 2no²
b Σm=
2
+
E
1 .... + 2 random,
62
the inequality above is a strict inequality from Jensen's inequality. Thus, when rj = Nerit i.e.
mo² b + 2b. p 0. By continuity, there exists some ō > 0 such that for any 26 <
8 (d < 26 + 6, i.e Meritt < Uman. where Oman Morit 5T(4o-- we have 0.
Moreover, when noo (d + b 1) > 2b, i.e. 1j > Merit, we have
2n 2
0
((2)
b
211
622
Σ
2n 2j1 + + (dz2d)2212))
==
12
2nj0² 2
(d + + 1) 1
which implies that there exists some < a < 2 such that h(a) 1.
Finally, let us prove (ii) and (iii). When n (d - b + 1) < 2b, i.e. S Merits we have h(2) < 1,
which implies that a > particular, when 170 (d + bbb 1) 2b, i.c. 1) = Moris the tail-index a= 2.
C.4 PROOF OF THEOREM 4 AND COROLLARY
Proof of Theorem
We recall that
Ig MM + 9k.
(C.9)
which implies that
| < |M 11
(C.10)
(i) If the tail-index 1, then for any a, we have h(p) El|Ma < and moreover
by Lemma 20
||x|| < M 1| ||..
(C.11)
Due to spherical symmetry of the isotropic Gaussian distribution, the distribution of MM not depend the choice of (0) Therefore,
does
|
|M all and ||ææ-a||| are independent, and 4x-1
18

---

Under review as a conference paper at ICLR 2021
MM [=--1]
has the same distribution |M ||, where e1 is the first basis vector. It follows that
E T
P S M | +
(C.12)
so that
z P v h(p) Bl
(C.13)
where hp) E (0, 1). By iterating over k; we get
1- (h(p)))
E| || < (h(p))
1 1- h(p) l
(C.14)
(ii) If the tail-index > then for any a, by Lemma 20 for any >> O, we have
(1 + +) e1
| | < (1 + +) MM
11x011.
(C.15)
(1 + (1+
which (similar as in (i)) implies that
(1+ +)= -1 + El
E ||" < (1 + M
(C.16)
(1 (1+ -
that
(1+ (1+e)r (1 + -1(+))((1++
B I S (1 =ma--)
(1+ E1
(C.17)
We choose so that (1 + <ph
1. By iterating over k, we get
1 - ((1+ ()+c))()))* (1 (1+ +6) Elg/...
B|| < ((1 + e)((p))
+
(C.18)
1 (1 <)(pp)
(1++)==--) -
The proof is complete.
Remark 12. In general, there is no closed-form expression for El[g I| in Theorem upper bound as follows. When p > by Jensen's inequality, we can compute that
We provide an
E E1 = P
E aaayall" E [111
|| [1"
(C.19)
and when by Lemma
20
compute that
17" 60
Σ |a-vill) )
17"
E 11
E
a.Ya
E
E |aay
E/ [111]" [|a I!")
10
(C.20)
Proof of Corollary
5
It follows from Theorem by letting - oo and applying Fatou's lemma.
C.5 PROOF OF THEOREM 6 COROLLARY
PROPOSITION AND COROLLARY 9
Proof of Theorem 6 For any 1o, Do E P, (R²), there exists a couple æg 1/ and žo 5o indepen-
dent of (M₁, q kEN and ( Mb) = E æ žo P. We define 2 and ig starting from 2o and øo respectively, via the iterates
MA + gs
(C.21)
34 M2 + 4k.
(C.22)
and let ie and ii denote the probability laws of JĄ and o. respectively. For any < a, since M|| and [||q < 20, we have uk. i E Pp (Rd) for any k. Moreover, we have
Fk Sx
Ma xx-1),
(C.23)
19

---

Under review as a conference paper at ICLR 2021
Due to spherical symmetry of the isotropic Gaussian distribution, the distribution of || does ||=||
not depend on the choice of x E (00. Therefore, 1- 1
1))l and ||
-x-1 1|l are
independent, and [12-- -2-1)ll has the same distribution as M [|. where en is the first basis I
vector. It follows from that
Ex Il
S E [|| Ma 5x- 1)11"]]
Ma.M [1"] [1|22=]] -K- [|P]
E(p) || - Tx- -x-1,
which by iterating implies that
(1x, 2x) - E| 3x.1P & (M(p))*El=0 - Roll ( v0).
(C.24)
By letting in = Voc. the probability law of the stationary distribution Zico we conclude that
Wy Vox) & (1b(e)) k
Wp(vo.
(C.25)
Finally, notice that 1 S p < at and therefore h(p)) < 1. The proof is complete.
Proof of Corollary 7
When no²
d+b+1 by Proposition the tail-index a > by taking p n²o² (d b (see Proposition 3 it follows from Theorem
and using (2) = 21j0² + b that
Woo) S (1 (1-21p0 2n102 (1-
no² (d (a+b+1))
k/2
W2(uu, Voo)-
(C.26)
2b
Remark 13. Consider the case as are i..dd. N(0, Ta). In Theorem the key quantity h(p) (0, where p a. We recall that
Corollary 5 and Theorem
2a x
a X2
P/2
h(p) E
xXY)
XY
(C.27)
where a = noo?, X, are independent chi-square random variables with degree of freedom b and d - 1 respectively. The first-order approximation of h(p) is given by
hP)) 11+
PF 2
2a
X
a²
X2
a
XY
=1
=
p
2a
a² (b+2)
a²
(d 1) 1
b
1
(C.28)
provided that na²
which occurs if and only if
other words, when
d+b+1
go² < 24641 a > 2 and
2b
h(p) ~ 1 1-pno 11- n0 + (bb++1))
<
(C.29)
26
On the other hand, when no² given by
2b
S 2, and the second-order approximation of h((p) is
d+b+T'
h(p) 1+
E
2a
X
+
a
X2
XY
+
2G
-)
E
2a
X
+
X2
+
xx
27
2
b
12
12
2
b
(abb + d
+
2 - PB
[(320
20
)
= =1 qa
X
XY
2b
8
1
B
and we computed before in
E.55
that for small a = 2ar and large d,
2a
a
2
4a
4
E
X
x2
XY
b (b + 2) + b
(6 + 2 2)
(b + 2)d,
(C.30)
b
12
1
12
20

---

Under review as a conference paper at ICLR 2021
and therefore with no"
h(p) 1 11-1 pM
-a(b
+ d d+11
+1
(2-p)a(b= +
(
1+
)
a²
dp
<1, (C.31)
2h
2qb
482
provided that 1 <
a(b+d+1)
(2 (2-p)a(b+2)
(1
a² 46
d2
{d)
2b
2gb
Proof of Proposition
First, we notice that it follows from Theorem that E Fo cc. To
this, notice that lim, (e Too > t) = Ca(e), where 61 the first basis vector in R and F( 2 t) 2 P(ef Too 2 t), and thus
[F 2 t)dt /
[P[[ 2 1 co.
(C.32)
By following the proof of Theorem 4 by letting o = a in the proof, one can show the following.
(i) If the tail-index S then have
E||xx I| S E 20ll kE||@1
(C.33)
which grows linearly in k.
(ii) If the tail-index > then for any > 0, we have
| s (1 =||===1 (1+ c) (1 c) (1+))= El O(k),
(C.34)
e
(1 (1+ (1+ 11)
which grows exponentially in k for any fixed > 0. By letting c - 0, we have
B| = (1 +1+ +) + (1 (()))((1 + c)¹ - (a 1)a-1
E
11
aa
Therefore, holds for any sufficiently small 6 that,
+ +
E ||
(Bl|zol1* + (a- -
e
We can optimize (1+c)* over the choice of >> 0. and by choosing -- which goes to zero k goes oo, we have (1+e)* (1 - )d{ k= = O(k)), and hence
||| = 0(*)),
(C.35)
which grows polynomially in k. The proof is complete.
Proof of Corollary the recursions this theorem hold.
The result is obtained by direct application of (Mirek 2011 Theorem 1.15)
where it can be checked straightforward manner that the conditions for
D SUPPORTING LEMMAS
In this section, we present a few supporting lemmas that are used the proofs of the main results of the paper well the additional results in the Appendix.
First, we recall that the iterates are given by Ikk -M + gu. where (Mxx qk) are i.i.d. and Mx is distributed as / 7 H, where H = Σb i=1 a,a," and gu is distributed as / Eb=n 0,Ui, where and yi are i.i.d. satisfying the Assumptions (1)-((2)
We can compute and h(s) as follows where and ((ss) are defined by 3.5 and 3.4 Lemma 14. p can be characterized
(1
!7 11 e1
p E log
(D.1)
and h(s) can be characterized as:
h(s) E "1)
e 17
(D.2)
provided that p O.
21

---

Under review as a conference paper at ICLR 2021
Proof. It is known that the Lyapunov exponent defined in (35 admits the alternative representation
= lim log |xll
(D.3)
k-+00
where & == Tg with I M M1 and un == zo (see NNwmman 1986, eqn. (2))). We will compute the limit on the right-hand side of (D3). First, we observe that due to spherical symmetry of the isotropic Gaussian distribution, the distribution of ||Maall does not depend on the |||]|
choice of E I {0) and is i.i.d. over & with the expectation B(II B(] (7 8 H) eill) where we chose x = e1. Therefore,
|.l||
M
log |لا log |ااه||
Σ
log
log
|لد-ا|
ال;-ب|
is an average of i.i.d. random variables and by the law of large numbers we obtain
lim
log |ل
E
||
2
E1
From D.3 we conclude that this proves D.I)
remains prove D.2
We consider the function
| |
1/k
((()) lim
E
where the initial point Ty = Wy is deterministic, the rest of the proof, we will show that for p < h(s) h(s) where h(s) given by (3.4) and h(s) is equal to the right- hand side of (D.2): our proof inspired by the approach of Newman 1986). We will first compute h(s) and show that it equal
the right-hand side of (D.2) Note that can write
| I |
M 1
II
This is product of i..dd random variables with the same distribution that of |Meq I| due the spherical symmetry of the input a, Therefore, we can write
1/k
| |
1/k
k
h(ss) = lim
lim k-+00
IE
M,eell*
ttt
|||
= E [|MMM =
H
(D.4)
where we used the fact that Mei are i.i.d. over i. It remains to show that h(s)) h(s) for p < Note that ||2,1"" < ||[| and therefore from the definition of h(s) and h(s), we have immediately [
h(s) 2 h(s)
(D.5)
for any O. We will show that h(s) < h(s) when p O. We assume p < 0. Then, Theorem !
applicable and there exists a stationary distribution Ios with a tail index a such that h(a) =
We will show that i((a) = 1. First, the tail density admits the characterization 3.7 and therefore J E Lg for a, i.e. the s-th moment of xoo is finite. Similarly due to 337 Too L, for >
Since h(a) 1, it follows from (D.5) that we have h((a) < However h(aa) < then by the continuity of the h function there exists & such that ((ss) < for every s E (a - a,a
(0, 1). From the definition of h(s) then this would imply that [[ l1*) + for every E (a (a- E, a + E). On the other hand, by following similar argument to the proof technique of Corollary 5 it can be shown that the s-th moment of Foo has to bounded which would be contradiction with the fact
that Foo L, for > Therefore, h(a)) 2 Since h(a) D.5) leads to
h(a) = h(a))
(D.6)
$ Note that the proof of Corollary 5 establishes first that aoc has bounded s-th moment provided that h(s) E [[aMell < and then cites Lemma regarding the equivalence h(s) h(s).
22

---

Under review as a conference paper at ICLR 2021
We observe that the function h is homogeneous' in the sense that if the iterations matrices M, replaced by cM, where с >> 0 is real scalar, h(() will be replaced by he(s) = c <((s). In other words, the function
hc(s)= == limg-soo
(D.7)
clearly satisfies hs(s) - c((ss) by definition. A similar homogeneity property holds for h(s): If the iterations matrices M; are replaced by cM; then h(s) will be replaced by (s) = h(() We will show that this homogeneity property combined with the fact that h(a) h(a) = 1 will force 1/4 //(s). Then, by considering input matrix cM, instead M; and by following a similar argument which led to the identity D.6). we can show that ho(s) = c*((s) 1. Therefore, he(s) = he(s) 1. This implies directly h(s) = h(s).
h(s)) hs(s) for any
O. For this purpose, given O, choose
Next, show the following property for the function h. Lemma 15. We have h(0) h' (0) p and h(s) is strictly convex in s.
Proof. By the expression of h(s) from Lemma 14 it is easy check that h(0) 1. Moreover, can compute that
W(ss E log
" (1)) (I(I-" b
H)
" b hH) c1 [|]
(D.8)
and thus
N'(0) p.
(D.9)
Moreover, we can compute that
h((s) = E [log
ei ())))((( -11--" ")
e Ea a117 >0, (D.10)
which implies that h(s) is strictly convex in
In the next result, show that lim in h(s) This property, together with Lemma 15 implies that if p < 0, then there exists some a (0, oc) such that h(a) = 1. Indeed, in the proof of Lemma 16 will show that lim infs-soe l(s))
Lemma 16. We have lim inf h(s) 1.
Proof. We recall from Lemma 14 that
h(s) =
(1)
e1
(D.11)
23

---

Under review as a conference paper at ICLR 2021
where 61 is the first basis vector in R and H Ei= a.d and a, (a......, ard) are i..d. distributed as (0, of Ta). We can compute that
4/2
E
E|(
H b
E
H
61
s/2
E
1
(1-b)
1
a
T
61
8/27
b
21 T
E
1
a
0:0
T
a.a E1
s/27
27
E
1
a:10g1 +... acaa)a)a11911
b
1=1
2
8/2
2
E
41
2
62
(122z2 .... andaja)a
i=1
1=
E
2
n2
E "=nn0000otttttt00a)aaaaaaaa
62
= 22/2p
(a,2a, + ... andaja)a 22 400
62
2m 5=1
as + 20.
In the next result, we show that the inverse of M exists with probability 1, and provide an upper bound result, which will be used to prove Lemma [8]
Lemma 17. M exists with probability 1. Moreover, we have
E (log* + || ||M- s 8.
Proof. Note that M is a continuous random matrix, by the assumption on the distribution of a Therefore,
PPM -1 does not exist) P'det M 0) = 0.
(D.12)
Note that the singular values of -1 of the form |1 fonl -1 where o a singular value of И and we have
0
if 3 21,
(log+ ||~~ = ( - if 0 0 2
(D.13)
We consider two cases for each case:
I < 1 and 1 1 H = 21. We compute the conditional expectations
E (log* + ||M
|0 " H = 1
log (I (I-" "H) 11)
2
0= " "H
"
<1
(D.14)
$
2 HI) )
|03 7 b =1
(D.15)
4,
(D.16)
where in the first inequality used the fact that
log(T -1
2X
(D.17)
24

---

Under review as a conference paper at ICLR 2021
for symmetric positive semi-definite matrix X satisfying 0 X I (the proof of this fact is
analogous to the proof of the scalar inequality log( ( S 2x for I r 1). By a similar computation,
E
(log*
||M-
1= " H 21
(r-1) "1 H
|| |/ 90 H -
EE
log
(1 | - (7 (T - " 21
E
log²
(1((2=) 1- -T= 1) | | |
E
log"
21
(1|4- (1"" (1
14= fu =21
IE
log
(1|-- (
(1) ( 1 (1r1) <1]
E
log
where in the last incquality we used the fact that (1 3 1 for 3 x 21. If we apply the inequality (D.17) the last inequality for the choice of X (2 we obtain
E
log²
2
H
1 (b
HH x
1
1
(H
-1
<
E
2
<
b
x 1 44
(D.18)
2
Combining (6. and D.18) it follows from (D.13) that EE log"
| 1 < 8.
In the next result, we show that a certain expected value that involves the moments and logarithm of [|M]], and logarithm of || is finite, which is used in the proof of Theorem 1
Lemma 18.
M (log* || + log
|| < co.
Proof. Note that M ? H, where H Σ. aja? in distribution. Therefore for any >
|| T 1
|a: 12 }}
M| = EE
aga
T
E
00,
(D.19)
since all the moments of a, are finite by the Assumption (A1). This implies that
[[MI] (log+ [[]] < co.
By Cauchy-Schward inequality,
E [ (log* ||M] < (E [[]M][2 EE (log* [IM-)1)) ")) 1/2 co,
where we used Lemma
In the next result, we show a convexity result, which is used in the proof of Theorem 2 to show that the tail-index is strictly decreasing stepsize 7 and variance o².
Lemma 19. For any given positive semi-definite symmetric matrix H fixed, the function Fu [0, oc) + R defined as
(a(a) |I(T - (aH)a))
25

---

Under review as a conference paper at ICLR 2021
is fonvex 2 1. It follows that for given b and d with H == Ei=1 a:a5, the function
Ma, 8) :- ([Fn(a)))))))))) =E [1 e1 ||
(D.20)
is a convex function of a for a fixed 8 2 1.
Proof. We consider the case 2 and consider the function
G ||(I aH) eil,,
and show that it is convex for H 2 0 and it is strongly convex for H 0 over the interval [0, oo). Let
a1 42 E [0, oc) be different points, i.e. 01 j 02. It follows from the subadditivity of the norm that
01 + 02
01 +
02
G#
H
61
2
2
01
2 H 2
<
H
e1
+
2
2
2 Gn((i) + (a()
which implies that (a) is a convex function. On the other hand, the function g(x) x is convex for s 2 1 on the positive real axis, therefore the composition g(G (a)) is also convex for any H fixed. Since the expectation of random convex functions is also convex, we conclude that h(s) is also convex.
The next result is used in the proof of Theorem to bound the moments of the iterates.
Lemma 20. (i) Given < p S L, for any x, y 2 0, (x + y) S x + y"
(D.21)
(ii) Given p > for any x, 2 0, and any e 0,
(1 + +)))== - (1+
(x + y) s (1 + +)) +
v².
(D.22)
(1+ -
Proof. (i) y = 0, then (a + y) S xx + ye trivially holds. If > 0, it is equivalent to show that
( (++1)
P x y/
<
11,
(D.23)
which is equivalent to show that
for any x N 0. Let F(x)= = (r+ 1) xx - and F(0)- = 0 and F'(x) = p( + 1)p-1 pa. < since p S 1,
(x + 1) s x" + 1,
(D.24)
which shows that F(x) 0 for every 2 0.
(ii) If y -y=00 0, then the inequality trivially holds. If y > 0, by doing the transform x + x/y and + 1, 0.
it is equivalent to show that for any
x1+ < (1 [)+) + (1 [ - (1+c)
(D.25)
(1 (1+ 11) p
To show this, we define
F(x) (1 x)+ (1 + e)x²,
x x20. 0.
(D.26)
Then F'(x) p(1 x-p-1 p(1 + c) so that F' (x)
0if < ((1 +c) 1) and
F((x) of 2 ((1 + (e+ - - Thus,
(1+ = (1+c)== - (1+c) )
max (x) = z20
(D.27)
(1+ p
The proof is complete.
26

---

Under review as a conference paper at ICLR 2021
E ADDITIONAL TECHNICAL RESULTS
We recall that the iterates are given by I = -M where (Mx, qu) are ii.d. copies of (M, q)
where .M = I Y H.H with H Σi=
i= a.a? in distribution and q Ei= azys, where a, and y:
are i..d. satisfying the Assumptions (A2).
We first obtain more explicit expressions for p and h(s) under the Assumption (A1). Proposition 21.
We have
2no
2
b
77000 b b
p = 2
E Elog
1
Fil
62
211
+ 2122))221221
(E.1)
1=1
for any 8 2 0.
8/2
(1
2n 2
0
h(8) =E
b
211
1/2
+ + 2113))
(E.2)
i=1j=1
where: 2, == (211, ......., zia) NO Ia). 1 15 < are i..dd
Proof. By the expression of p from Lemma 14
we can compute that
(1
p Elog
H
61
E log
I
H
c1
b
E. log
e
-- 1
Σ aaa
(1
(1-
Σ
aja
61
b
= E log
2
21 T
b
aga
+
1
62
1
Σ
aga
Σ
ana
t=1
d=1
1=1
2no²
2
b
11 120²
b
= E log
21 +
(2112z1
+ 24d 21d2)a)
2
62
1=1
j=1
where = (2,1. ..,,...,
2nd)
No, La), 1 S i < b are iid. Similarly, by the expression of h(s)
from Lemma 14 we have
h(s) IE
(
11
1l
8/2
b
2
E
21
(za Zyz .... + 211 Zy1
62
Remark 22. It follows from Proposition 21 that h(s) and hence the tail-index depends r and o² only via its product no?
We have seen in Theorem T that the iterates converge to a heavy-tailed distribution with tail-index (0, 5o) provided that < 0. When the data o; are i.i.d. in general, it is not easy to check whether P < 0 holds. For the Gaussian data (Assumption (A1)), is possible characterise the region of the parameters 7, b, d, o² in which p < 0. We first state the following result, which provides sufficient (but not necessary) condition for p < O. Proposition 23. p provided that
110 (d b + 1) 2b.
(E.3)
27

---

Under review as a conference paper at ICLR 2021
Proof. We recall from Proposition 21 that
2no 2
b
p Elog 1
#1
2
(
(E.4)
i=1
where 2; (211,... ................................ Zid) (0, Ia). by Jensen's inequality, we have
i S b. Note that the function log is concave, and
- 2
log
1
2nj0² 2
2 21
+
11
2 4
Σ
b
Bj1 + + 2nd 2dd
(E.5)
1
im1
can compute that
211
bE[2 = b,
(E.6)
and
E
Ri1 + +..
E Σ 21 +... 2
+
Σ
(#1 +... + 2zd 2n
bE [(2]] + ... = + b(b 1)B [(211221 + ... =1d=24)=1122)
bE(11] + b(d - 1) () 6 - 2)
= 3b + b(d - 1) + -
b(d 1),
where we used the property that 2; = (zi,, و < d) are i.i.d. and 2iy are i.i.d. N(0, 1) and
Ei 1,
Biai1] = 3.
(E.7)
Hence, we conclude that < 0 provided that
1 - 2nj + 17 004
(d+ 1) <1,
(E.8)
which is equivalent
no (d + h 1) < 2b.
(F.9)
The proof is complete.
L
Remark 24. It is worth pointing that p 0 does not hold for arbitrary model parameters. In particular, we can compute that
170 2
2
b
d
n
= - log
2
211
+
62
2s1
Zih
Zyk
i=1
i=1
j=
2
2
27
1102
11
E log 2
211
+
Zel Zikk
k=2
1221
E log
Zi1 Zik
112
(n1²²
llo
E log
211 Zikk
2
k=2
28

---

Under review as a conference paper at ICLR 2021
Note that conditional on 2,1, 1 S i b,
b
2:1 Pik ~ N
0, 1. 211
(E.10)
1=1
are ii.d. for k = 2....,d. d. Therefore,
2
Σ
Ziz
log [XY] - log
+ log log log Y,
1 2
(E.11)
where X is a chi-square random variable with degree of freedom and Y is a chi-square random variable with degree of freedom (d - 1). Therefore, we can compute that
2.10 m0 log(z) x² -eee
Elog X
dx
2
r (
2
log(x)x* -
2
[/ log(x)x² 1 -1d
-1 Hence, we conclude that 2 0
2 + 2 (
2 -
Similarly, we can show that provided that
1 log Y 2
(d (d-1)ar(_))))
no² bexp
(E.12)
2 22-1)21(2))
2 2
1)p
Next, we provide alternative formulas for fi(s) and for the Gaussian data (Assumption (A1)) which used for some technical proofs.
Lemma 25. For any 8 > 0,
h(s) E [(1--0x)
(
no²
2
0²
8/2
x)
+
XY
and
1 p 2
(11- n b
n²o4
log
X
XY
ba
where X, Y are independent and X is chi-square random variable with degree of freedom b and Y is chi-square random variable with degree of freedom (d (d-1)).
Proof.
We can compute that
e/2
2no 2
20
b
h(s) =
E
b
2i1
+
62
[2112 + 21d3ja)211911
1=1
/=1
8/2
2no 2 b
2
d Σ
E
Σ
211
+
2 21 + 211
2she 2yk 2yk
62
im
j=l
2m
s/2
2no 2
2
b
E
21
+
211
Σ
2/ Zik
62
2=
x/2
n
20
E
401
12
Zik
29

---

Under review as a conference paper at ICLR 2021
Note that conditional on 2,1, 1 S S b,
Σ
Fik ~ N
Σ.
(B.13)
$1
1=1
1=1
are i..d. for ls ...... d. Therefore, we have
s/27
1702
0
h(s) = E
b
21
+
b²
Σ
211 Zide
k=
8/2
110
= E
b
21
+
62
11
2m1
Am
k=
where mP are i... (0, 1) independent of 2,1, i
1, l....: Hence, we have
110
2
b
2
1 o
b
d
8/2
M(s) =
b
71
i=1
1=1
R=2
8/27
n1²
17
04
X
+
XY
62
where X, Y are independent and X is chi-square random variable with degree of freedom b and Y is chi-square random variable with degree of freedom (d 1). Similarly, we can compute that
P
E
log
1
110
211
2
+
11
211 2y1
i=1
k=2
1102
2
2
d
27
E
log
1
11
2
+
12
Zíl Zik
i=1
k=2
[i=1
110
0
E
log
X
+
XY
b2
where X, Y are independent and X chi-square random variable with degree of freedom b and Y is a chi-square random variable with degree of freedom (d (d. The proof is complete.
In Theorem I we showed the existence of the tail-index a. For the Gaussian data (Assumption (A1)), we can provide some explicit bound on the tail-index provided some explicit technical conditions hold. Next, we provide a technical condition under which the tail-index a E (0, 4]. (See also Proposition
3 for technical condition under which the tail-index E (0,2).)
Proposition 26. There exists some 0 < a < such that h(a)) = 1 provided that
2b 0ll (d+b+1)
20 b
2 2h 2010 (b +
(b (b+22 2b+ +d+3)
6
1 1
17066
2 b2 (b + 2) + (b + 6)
(b (b+
2) 1)
(b+ + 4)(d-1) -1). 1).
2 b2
b
Proof. It follows from Lemma 25 that
27
h44) = E ((1
no
1200
X
+
XY
b
12
30

---

Under review as a conference paper at ICLR 2021
where X, Y are independent and X is chi-square random variable with degree of freedom b and Y is a chi-square random variable with degree of freedom (d (1). We can further compute that
no² x ((4) - E
(1--=
)
o b
{1-
no² X
2 n1 XY
E
x²
+
(E.14)
12
First, we can compute that
E (1
no²2 b x
#7
2no² b
617- of
41y 83
n' ba
E[X]
B[X²]
[
B[X*]. (E.15)
8
We recall the formula for the m-th moment of a chi-square distribution with degree of freedom given by 2mm + /)( which is 2m & ( + 1) +).... ... ( + (m - 1)) when m is positive integer.
Since X is chi-square distributed with degree of freedom b, we have
= 2 b
E [[X]
b.
E[X²] 2 b b
+ 1
b(b + 2),
2 2
b
b + 2
23 [
+1
b(bb + 2)(6 + 4),
2
b
b
E -
+
+
+ b(b + ())+
2
2
2
which implies that
(
172 xx)
61/201 (b+2) (b+2)(b+4)+ n'08
4n
-no2+
(b+2)
b
(E.16)
Second, we can compute that
n 64
17008 ba
7008
n
E
x²
E
[
2
E
b(b + 2)(d - 1)(d + 1)
(b (d 1),
64
63
(E.17)
where used the fact that Y is independent of X and Y is chi-square distributed with degree of freedom d - 1 so that [E[ = (d l) 1).
Third, we can compute that
[
n02
172
2E
X
XY
b
12
o1 XY
11/08
11/00
2E
+ 2E
X²y
- 4E
X²y
b²
be
63
1) 1200
(d - 1) +2 1 08
4)(d 1) - 4 000
2
(b + 2)
(b (d 1).
63
62
Putting everything together, we have
61jz0
4nj06 (b+2)(b +4) + ()+ 4)
10008
M(4) = 4no² +
(b+
1/ 1/00
13 2dd 1)
2 110 04
b (d 1) + 2 10
(b + 2)(6 4) - 1) 4 n'06
(b + 2) - 1),
1,3
b2
31

---

Under review as a conference paper at ICLR 2021
and h(4) 2 1 if and only if
4no + 6nj
4n
(b+2)(b + +)+ + n'0²
(b (b+
(b+ + 4)
+ 1 8
(b + +))((d= -1)
113
+ 2 0
(d - 1) + 11000
+ 2)b 4) 1) 4 n¹O6
(b 2) 1) 1,
133
82
which is equivalent to
2b + n10 200o(336 + 6) + (d -1
21/²04 2)b+ 4)
1 1
822 (b+2) 4) ()+) 1 1
122 (b + 2) 1)
b
0' 1
00 (b - 2) 1) 2 0,
(b
(b+ 2) 4) 1)
which is equivalent to
2b + no² (d
+d+b+ 1) ス 2noo 2)
217204
1 1
1 (b (b+ 2) -1)
+
(b 2)+
(b (b 4)(0 66
b
2 822
n 0
8 (b + 2b + 4) - 1)
(b 2) - 1).
Finally, recall that p < if > no b 1) and h(4) 2 1 implies there exists some 0 < a S 4 such that h(a) 1. The proof is complete.
D
Let us define D,,b as the set consisting of (17. 0) such that
D. = (1) no (d + b+ 1) < 26 and h(s) 2 1}.
We have shown in Proposition 23 that o 0 provided that no? + b- 1) 26. Therefore, (n,a) E DD.b, then the tail-index E (0, s). In Proposition 26 we characterised the set D4.6- In the next proposition, we show that Da,5 non-trivial, i.e., Da.5 is not an empty set.
Proposition 27, DA,5 not an empty set. particular, it includes the pairs (n. such that
ag
T1²2
2
<
(E.18)
d+b+1
b
d+b+1
for some 0g E 20 such that F(ae) = 0 and F(a) S 0 for any de S a S 2, where
2a
2a
F(a) = 2 - a
(b+ 2) +
+ 2b + 3)
d+ b
172
1
1 a3
2 (d b + 1)3 (b + (b + 4)(b + 6)
2 2 + b 1)3 (b + 2) 1)
(d b + 1)3 (b + 2) 4)(d - 1).
Proof. We aim to show that there exist some 7,, a such that
1102
2
++b++1 1)
2110² 2
b (b + 2) + 2n
2 2
12 (b+ + 2) + +d
1n'00
1 17100
7'06
(b + 2)(b + 4)(b + 6)
(b + 2) - 1)
(b 2) 4)(d -1). 1).
2 1a
2 13
b
32

---

Under review as a conference paper at ICLR 2021
Let n0² 8 (d+b+11 1) = a. Then, suffices to show that there exists some a < 2 such that
2a
2a²
a a
(b 2b+ + (d+b+ + 1)2 (b + 2) + d
d+ b
a
(b+ + 2) 4)
2 (d b 1)3 (b + 2) - 1)
2 (d + b+ 1)3
(d (d+b+1) (b 2) + 4)(d-1),
Let us define
2a
2a
F(a) = 2 a
2b+ + (d+b+ + 1)2 (b + (b+
d+ +
1
a
1 a
(b + (b (b++)((b+++ 6)
(b + 2) -1)
2 (d + b + 1)3
2
(d 1)3
a
(b + 1)
(d+b+1)) 1)3
Then, we can check that F(0) = 2>>>0 0 and
4
8
F(2) = d+ b
(b+ 2) +
(d+ 1)² (b (b+ 2b + d
+
4
(b 2b (b bd+b b + 1)3 (b+
2) 1)
(d+b+
1)3
8
(d+ 1)3 2b+ 4)
so that
(d (d+b+ b+ 1)3
F(2) = -0=-)04000-0--1--220-1--- 1)
4(b+2)
26 44
24 d + 2bd 8dd + 26 + 8
22 2b 10 < 0.
Thus, F(2) < O. Hence, conclude that there exists some 0 < a 2 such that F F(a.) 0 and F(a) & 0 for any de I a < 2. Then, for any
T a S b (d+b+1)<2,
(E.19)
we have (1), o) E Da..- The proof is complete.
Recall that Dam,b consists of (1) σ) such that
D2m,b (1, 0): no 2 (d + b b+ < 2b and h(2m) 2 21}
Since D4, A 9 and D4,6 D2m,p for any 2 Indeed, we can characterises the set D2m,b in the following proposition.
Proposition 28, Given any m E N, there exists some 0 < a S 2m such that h(a) = 1 provided that no² 1) < 2b and
m
22
kmm
(11)22)+2(m-
62(m-k)++
k=0
Г(j + m - k 2) T(m - k +
d-1)
1.
r(
d-1 T
2
33

---

Under review as a conference paper at ICLR 2021
Proof. By applying Lemma
25
we can compute that
m
1702 b
h(2m) = E
X
XY
b²
m
17 2 1m
1(m k)
7722
E
1
X
Xm-ky y
k
62(m 16j
b
k=0 0
m
m
1i 2 (m σ 1(m-k)) k)
2k
2k
(-1)² 17/ 0/25
Flxxitm-kym-
k:
ba(m 1-)
j
1=0
m
1 1(m k)
2k
Tp 02)
(-1)²
2
k
12(m-hh
1
b
k=0
[ + m
k + 2)
T(m - k + 1=11
2m
((2)
r( 2
m
2k
2) 4)+ (mmm-))=2
k j
k))+)
k=
0==
(-1))2 [(j + m k + 9) 7(m - k+ d-1
r(g)
I
where we used the formula for the moments of chi- square distribution, that is, the m-th moment of chi-square distribution with degree of freedom k is given by T ())
Previously, we have provided some upper bounds on the tail-index a under some technical conditions on the model parameters. Next, let provide an upper bound for the tail-index without relying on any additional technical conditions.
Proposition 29, The tail-index is upper bounded by:
2no b
X +
00 X2 +
22 ba
XY $0)
6
S. &ax
2,
(E.20)
E
2n02 X
apa x2 + r2 XY
where X, Y are independent and X is chi-square random variable with degree of freedom b and Y a chi-square random variable with degree of freedom (d 1).
Proof. We recall that
1= h(a)) = IF. (1-
2mo2 b
10 b2
1700 1
X
+
x2
XY
(F.21)
where X, Y are independent and X is chi-square random variable with degree of freedom b and Y a square random variable with degree of freedom (d - 1). Note that for any x 2 0 and a 2 (1 + 2 2 1 + zz. Therefore.
201
1/
1²004
1 E
b
X
12
x²
82
XY
1
2002 x+ 12 X2+ 2204 XY
E
1
2no²
b
X
1744
6
x²
1044 b
XX
)
2002 x u2 xY20
2m
17 2
1200
IP
X
X2
XY 2 20)
b
b2
5²
a +
E
(
(-2110²
200
x
Ro
52 x2
+
0 +1
b² XY
2
which yields the desired result. The proof is complete.
34

---

Under review as a conference paper at ICLR 2021
Remark 30. (i) Note that it follows from Lemma 23
that we have
1 E 2
no² x
n004 XX ]
log
+ 62
where X,Y are independent and X is chi-square random variable with degree of freedom b and Y is a chi-square random variable with degree of freedom (d (d-1) 1). Therefore, we have
1 log
1 00
((1-1)
((1
1102
1100²
x - y 1
p p= 2-200 2 20 J0
b
x
+
6²
2y
2
2 2 1 1
drdy. (E.22)
In particular, when
1, we have = 0 and
11022
x
p
log
1
dr.
(B.23)
T8
b
(ii) Note that it follows from Lemma
25 that we have
((11
no²
2
1
#/2
h(s) = E
X
+
XY
62
where X,Y Y are independent and X is chi-square random variable with degree of freedom b and Y is chi-square random variable with degree freedom (d 11). Therefore, we have
h(s) [ (11
no²
1)20
r
r y
ry
drdy.
b
ba
25T(2)
2 1
1-1
In particular, when d = 1, we have Y = 0 and
100
110
T2
h(s)
1
da.
(E.24)
0
b
T
So far, we have studied various properties of the tail-index a, including the monotonicity on stepsize, noise variance, batch size and the dimension, as well as some quantitative bounds. In general, there is no simple closed-form form formula for the tail-index a. Next, we will obtain some approximations for the tail-index a in various asymptotic regimes. First, we provide rigorous first-order approximation for the tail-index a when it is less than and close to 2.
Proposition 31. Let == sou and 0g 2+b+I. Then the tail-index satisfies:
a ~
Fc (a ac),
(F.25)
for any 1 aei where
20 Fo = (1-220
2a
2 12
x² XY 1
+
log 1-
20c
x
2
T
x²
To
Le
xx))
)
|>0, >0, (E.26)
where X, Y are independent and X is chi chi-square random variable with degree of freedom b and Y is a chi-square random variable with degree of freedom (d 1).
Proof of Proposition 37 Let us define = In Proposition
showed that there exists some 8 > 0 such that for any 26 < a(d + 6 + 1) < 26 + 8, < and there exists some 0 < a < 2, such that l(((x)= = 1. In particular, when a = ag := ã+b+I. the tail-index a = 2. Consider the tail-index
a = a(a as a function of a. Then, we have
$ XY
1 h(()= = E (1-
2a
a
x
(E.27)
b
1
35

---

Under review as a conference paper at ICLR 2021
where X, Y are independent and X is chi-square random variable with degree of freedom b and Y is a chi-square random variable with degree of freedom (d ().. By differentiating E.27 W.E.t a, we get
0
E
da
log
1 -
20
X
+
X
XY
e² log
30 x 1 xx)
2 da
b
62
+ a -
+
28
8
X2
XY
Φ 1og
(1
1 2
87
x2
+
XY
which implies that
da
-2E
2a 6
X2
+
24 XY 6
(E.28)
Da
l==0.
E
20 b
X
02 5
X2
+
5/ XY
log
b
X
X2 X2
a 8
XX
where we used the fact that = 2 when = ae Note that the function + x log x is convex, and
by Jensen's inequality and the fact that 1
20
b
X
+
b
x2
+
XY is not constant, we have
20c
2
20c X
a
a
E
X
X2
XY
log 1
+
x"
XY
b
62
12
12
1
20
2
4
(1-
20
d
a XY )
E
1
X
+
x2
XY
log E
X
x2_
0.
b²
6²
b
b
b²
Moreover, we can compute that
20
20c
20c (b + 2)
20c (d 1) = -4
-2
x
x2
+
XY
= -2 -2+
+
6²
b²
b
b
Hence, we conclude that
4 Fc
a
(a ac),
(B.29)
for any a J ae. where
Fe = E [11- 2
2
d
20c
a
+ a
]
X
+
x²+
+
XY
log
1
x
+
x2
XX
> 0. (E.30)
6
82
b
6²
6²
Next, we derive an approximation for the tail-index when it is close zero Proposition 32. Let naa and p = p(a) emphasizing the dependence Define u2 = inf(a > 0: p(a) = 0}. Then, we have
a a~ c~ a),
(E.31)
as a 1 aa, where
X +
2a. x
20
XY
2a. x
2 X
a
27 -1
c. :=E
E log 1 1-
XY
2a b
x
XY
12
(E.32)
where X, Y are defined in Proposition 37
Proof of Proposition
32 The tail-index a is uniquely determined by
(1 2a x b
2 12 x2
0/2
h((a) = E
XY
(E.33)
where na?2 and X, Y are independent and X is chi-square random variable with degree of freedom 6 and Y is a chi-square random variable with degree of freedom (d - 1). It is clear that a
depends on y and only via = no2. In Proposition 3. we showed that there exists some d 0
36

---

Under review as a conference paper at ICLR 2021
such that for any 2b I a(d++++1 < 2b + 6. p 0 and there exists some 0 S 2, such that h(a) = 1. Let p p(a) with emphasis on the dependence of p on a = noo In Proposition 23 we showed that p < 0 provided that a(d + ++bbb+ 1) < 26. On the other hand, we showed in Remark 24
that p 2 0 for any 2 bexp 2 ())())
1
Therefore, there exists some 2 =²= - (u=
critical value > 0 such that p(a) < 0 for every < a, and p(ax) O. It is clear that as a - a+,
0. We are interested in studying the tail-index a when a is close to zero. By differentiating
E..3
w.r.t a, we get
1 da 2 da
20 b
0 = E
log
1
X
+
X2
XY
12
12
+
a
- b
+
20 1
x²
+
20 XY
12
log (1- x x² xx)
2
20 X
X2 + b
XY
5
and by differentiating w.r.t again, we get
{
0a 8a
2a b
2
2
0 E
log
1-
x
X
2
XY
6
a
2 +
X² 20 XY
4 log
24
x
XY)
+
21
X
X2 + XY
aa
11 2a
+ a²
+ IE
log
X
X2
b XY
2 da
b
B
da X 24 x2 + 12
XY x x2 XY
9 1oR
1 11
+ EE
Da
X
x 20 x2 24 XY
e log (
a
+ E
2 da
24 X
+ 5z
X2
At 0., a
0 and p
f llog (1
2/4 X
X2
XY x
0. which implies that
1
20.
2
03
0 = 1 (a'(a.))
log
x
+
x22
XY
b
1
1
2 + X2 XY
+ + (a, E
20. b
X
x2
XY
12
62
which implies that
x 201 x2 XY
4E
14
20 X+ X2 XY
a' d((a.)
(B.34)
[log (1- -0= x + 3
x xx+
E
and therefore
x 24 x2 28 XY
4
1 20,
X
x2+ 1 XY
(a. a))
(F.35)
E
[log
[ -
20 X
+ 3
X2 + 37 XY
t a...
When the dimension df is large, we can use Proposition and Proposition 32 to obtain a more explicit approximation for the tail-index when it is between 0 and 2.
37

---

Under review as a conference paper at ICLR 2021
Theorem 33. When the dimension d is large, the tail-index satisfies:
d
26
110²
(B.36)
4b(b
2)
+ b
26 for any 1+b+I S no?
26
+
2h(b+2)
a4b+1
d3
Note that in Theorem 33 the approximation
d (n0² 1b(b+2)
decreases from 2 d+b+1
26
as no² increases from I+b+I
86(b+2) which is approximation of Moreover, is strictly decreasing in d, 17 and o² and strictly increasing in b. This is consistent with the monotonicity results have shown before.
26
to
a+b+I +
26
ds
the approximation 1b(b22
n d+b+1)
Proof of Theorem 33
When no² increases from de
24 to d., where in 0: p(a) 246-I
0}. the mall-index decreases from to O. When d 1 0. - 0 and a - 0, and hence suffices to show that
d3
2b
ak ~ 4b(b + 2)
110²
(E.37)
d b b
t and no² 4 d4b-1
and ax d+b+1 +
8b(b+2) d
and when oo and no? 1 d+b+1 + 8b(b+2)
d
d3
2b
n1
(E.38)
4b + 2)
d
6
We will prove
E.37 in Corollary 34 which is a corollary of Proposition 31 when d 1 oc and we will prove E.38 Corollary 35 which corollary of Proposition 32 when d co.
When the dimension d is large, we have the following result as corollary of Proposition 31 Corollary 34. The cail-inder satisfies:
d3
26
- 4b(b +
1102
(E.39)
d
b
as d co and no² 146+I
Proof of Corollary
34
As d co, 0g 4 have 3 X
a²
x2 +
XY 0 in probability, and
using log(1 + x)
x²
so that (1 + x)) log(1 + x) ~ (1 + x)
2²
we have
2
2
E. [
2a
a
22
2 x b
a x
]
F.
X
x
XY
X
b
B
B
1
20 x
d
a
27
B
x2
XY
2
b2
20
2
a
27
X
x
XY
b2
b2
38

---

Under review as a conference paper at ICLR 2021
Next, we can compute that
20c
E
X
XY
b
6²
6²
4a
E
+
de
+
4 53
- +
20
4
B
5a
ba
b²
63
4a²
b(b + 2)
b(b 2) + 4)(b + 6) + b5 + 2)( -1)
12
1
4 3 c
24
4
b(b + 2) 14
b(b = 2) 4) - 1)
b(b + 2) - 1)
7
B3
16b(b + 2)
16b(b + 2b 4) + 6) 16b(b + +2 -1
(d+b+10 1)2
(d+ b 1)2
(d+ 6++b+- 1)1
32b(b + (b + 32b(b + 2) + 4)(d 32b(b + (d 1) (d+b+ 1)3
+
(d+ 1)3
(d (d+
16b(b + 2)
=
(d (d+b+ 1)4
(d+ 0))
- 2((b - 4) + 6 1) 4)(d - 1) 2 + bb 1)(d 1)
32b(b + 2) d3
as d f 0o, where we used the formulas for the moments of chi-square random variables, and 0g d
for d f co. Therefore, it follows from Proposition 3 that we have
d
2h
no²
(E.40)
4b(b
d d+b+1.
as d f xo and you 4 2+841
26
The proof is complete.
When the dimension d is large, we have the following result as corollary of Proposition 32
Corollary 35. When f oo and no² t a. a+b+1
8b(6+2) d
the tail-index satisfies
d
25
1102
(E.41)
4b(b 2)
d b +
Proof of Corollary 35 Note that by the definition of a..
1 - E log 11
2a,
2
0 = p(a.)
X
X2
xX
(B.42)
2
b
1
B
When the dimension d is large, i.e. d f oc, we have xo in probability, and thus a, + 0. This a²
implies that 20 + f follows that x2 x2
in probability, and hence we must have / XY + well.
20 b
a
+
X2
+
XY
(F.43)
b
b
which implies that as 1 oc,
2h
a, 0g
(E.44)
+ b+1
39

---

Under review as a conference paper at ICLR 2021
where we used E
20= b
X
+
x=
+
XY
= 0. Note that when a = des a = 2, which is not
close to zero, and to get finer approximation, using log(1 + x))
I
2 we get
20,
a
20
a
27
X2
XY
X
X²
XY
2
6
6
4
6
6
20,
20c
2 XY
21
X
X²
XY
+
x
2
b
1
12
1
1
20.
2
a b
8b(b + 2)
x²
XY
2
b
b
d3
where we used from the proof of Corollary
34
that
20
a
a
xx))
32b(b + 2)
E
{-
X
x2
xX
b
1
d3
as d f c0. Let write a, de then as - 0, we have
1 E
2a X
2
a
2
20
20c XY
8b(b + 2)
0
x
XY
+ E
x
+
x2
(B.45)
82
b
1
12
d3
and we can compute that
28c
20c
-2
20 b
2ac
X
X²
+
XY
=
+
b(b + 2) +
b(d - -1) =2,
(E.46)
6
b2
b
which implies that
8b(b +2) d3
(E.47)
Hence, we have
4E
2 b
X
+
2a
X2
+ 20 XY
12
P
(a. 110
28
+
03
X2
XY
2
b
4E
2 X
+
28 x2 + 2 XY
(ac + c - c
27
20
X
+
X2
a
12 XY
We recall that
2 X
2a
20 122
4E
x
XY
= 8,
(E.48)
12
and from the proof of Corollary
34
we have
E
(-bbx
20c b
x +
2 x2
2 +
xx)
3b + 2)
82
ba
d3
as d f oo, where we used the formulas for the moments of chi-square random variables, and a for d f co. Hence, we conclude that
2b
8d3
2b
8b(b + 2)
a
32b(b + 2)
d
d+b+1
d3
no²
(E.49)
when d t oo is large and no
d-b+i +
2b(b+2) d3
The proof is complete by noticing that
8d
2b
(b(b 2)
d3
2b
no0²)
2
1102
(E.50)
32b(b + 2)
++1
d
4b(b
d b b+b+11
40

---

Under review as a conference paper at ICLR 2021
Remark 36. We have already obtained approximation of a when lies between 0 and 2 and the dimension d large (see Theorem 33). Fix the dimension d and batch size b, when a = no² + 0, the tail-inde miil-index - so. Let derive approximation for the tail tail-index in this asymptotic regime. We recall that the tail-index a is uniquely determined by
1= ==)(a== = (1-30
(1
20
a X2
0/2
X
XY
(E.51)
B
where =no² and X, are independent and X is chi-square random variable with degree of freedom and is a chi-square random variable with degree of freedom (d - 1). We apply the
approximation (1 + 2///22 1
22
+ $
(15-1)
x² get:
1~1
2n0²²
X
1/01
x2
0/
XY)
b
b
2 2
1)
EF
2n
X
1/o1
x2
1/01
XY
2
B
B2
Assume that no² is small and ignore the higher-order terms, we get
2E
X
21
X2
+
n²00 6²
XY
a
~
+
2
2no² xx)
E
Ano 2 b
2 200
(b² + 2b)= - 22 2n"00 b(d - 1) An'o' b
b
1
d d-1
=1
(62 + 2b)
2p
2)
2
+bb+2)
Hence, we conclude that as gou _ O, the tail-index satisfies
2b
d -
(b+ +
(E.52)
b b 2
Note that the approximation (b+2(
2h
$22 is strictly increasing in b, and strictly decreasing in
o² and d, which is consistent with what we have shown before. If 17o2 24b4I, we know from
2h
Proposition that the tail-index 2. Indeed, by plugging N1022 J+b+I into the right hand side of
E.52 we get
26
d-1
2b(d +ld+b++1]
+ d
+
= 2,
(E.53)
(b 2)
b+2
2b(b + 2)
b+2
which is consistent with Proposition
Remark 37. The approximation in (E.52) is good if no² is small, and every other model parameter fixed. When 2 small, and dimension is large, a finer approximation is given by
2E
2g
x
- 2E
y²o" 6
X2
+
y²0" y²="Xy XY
b
(E.54)
27
2no b
X
+
X2
n
xy 2
6²
and we can compute that
2n12
004
104
27
X
X
XY
b
12
4a²
at
a b(b (
b(b
+ 2) +
b(b 2)(b 4) + 6)
ba
4
2
4a
b(b + 2)(b + 4) +
b(b + 2) + 4) - 11)
b(b b(b -1
1
b
733
4a²
a
3
b(b + 2) + b
b(b + 2)d
b(b + 2)d,
(B.55)
1
b
41

---

Under review as a conference paper at ICLR 2021
where = no² Hence, obtain the approximation:
4n 6
2n (1² 2b) 2 b(d - 1)
(E.56)
4n b(b b(b 2) 2)+ 62
+
ター 6 b(b + 2)d2
b(b + 2)d
which yields that the tail-index a can be approximated as:
2b
4(d + + 1)
Or 2+
(E.57)
1702 2)(1 +
3 4h2
d2
m0²2 d) (b+ 2) a² d² 4n d)
b
42


Reviews:
[{"review_id": "wFToM9QUE--", "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": "Summary: This paper studies the heavy-tail phenomenon in SGD. In recent years, many works either empirically or theoretically showed that the heavy-tail property of SGD leads to a better generalization performance. But no rigorous theory has been developed to explain the cause of this phenomenon. \n\nIn this paper, the authors studied SGD iterates in solving a quadratic linear regression problem with i.i.d (Gaussian) data. In this setting, they proved the main result that shows that the tails of SGD iterates become monotonically heavier for increasing curvature, decreasing stepwise, or increasing b, hence this tends to provide a rigorous explanation of the heavy-tail phenomenon. The authors also developed other results on the law convergence and variance bounds.\n\nComments: Overall I think the paper is technically sound and develops rigorous proof. My main comment is that the problem studied in the paper is very idealized, I.e., a regression with iid Gaussian data. I understand that this makes the proof cleaner with compact results. However, this may not have direct implications on the heavy-tail phenomenon in deep learning. In fact, it may be more meaningful and motivated to study other simpler problems, such as binary classification with linearly separable data, in which the data structure is more practical than iid Gaussian. \n\nOverall, I consider the results in this paper as rigorously exploring the heavy-tail of SGD in linear regression under iid Gaussian data. I suggest the authors consider other more practical problems, and the results need not be related to deep learning. Focusing on the heavy-tail phenomenon in standard machine learning problems is already an interesting problem. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "uaGz5M7KT-", "reviewer": "AnonReviewer3", "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": "This paper studies the relations between the heavy tail phenomenon of SGD and the ‘flatness’ of the local minimum found by SGD and the ratio of the step size $\\eta$ to the batch size $b$ for the quadratic and convex problem. They show that depending on the curvature, the step size, and the batch size, the iterates can converge to a heavy-tailed random variable.  They conduct experiments on both synthetic data and fully connected neural networks, and illustrate that the results would also apply to more general settings and hence provide new insights about the behavior of SGD in deep learning. \nI do not have time to check the proofs and are not familiar with this topic. However the results seem to be novel and interesting. \n\npros: 1, They characterize the empirically observed heavy-tailed behavior of SGD with respect to the step size, mini batch size, dimensions, and the curvature, with explicit convergence rates. \n\ncons:1, The theoretical analysis is only for the quadratic and convex function. The input data is Gaussian, which is quite restrictive. \n\nAfter the rebuttal.\n\nThe authors addressed my concerns. I have read other reviewers' comments. I decide to remain the current score.", "extra_scores": {}, "extra_text": {}}, {"review_id": "S2_rqkUZWUc", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "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 main theme of this work is to study conditions under which SGD iterations result in random variables with heavy-tail random distributions. Specifically they focus on the step size, batch size and problem dimension. First they show theoretical results showing how the tail-index of the distribution generated by SGD depends on the chosen step size, batch size and problem dimension.\nThese results make several assumptions limiting their scope of applicability. Namely, they are limited to quadratic optimisation problems, normally distributed data and one-pass regime of SGD. However, the authors argue that since even in this simplest setting SGD results in a heavy-tail distribution, the more complex problems should not be expected to behave otherwise.\nThe experiments verify the correctness of the theoretical results, but they are also of limited value. For example, the deep learning section studies a shallow fully connected network on MNIST and CIFAR10. It would be more interesting to see a model performing closer to the state of the art here.\nWhile the main results of this work are interesting, I have a few reservations. First, as I wrote above the setting (even in experiments) is limited to the simplest case and hence is of limited value. Second, it is quite difficult to follow the theoretical results, mostly because all details are given in the Appendix, which is 30 pages long. Perhaps, this work is better suited for a journal publication, where the authors will have more space to explain their work. And finally I have some rather minor comments:\n- the paper refers to equation (3) in several places of the article and the Appendix, but there is no equation (3). I had to guess to which equation they refer each time, which made reading the already technically heavy paper more difficult.\n- In Theorem 4, it is not clear how \"the p-th moment of the iterates are of exponentially decaying nature\", since in both cases the coefficient of $\\mathbb{E}\\Vert q_1\\Vert^p$ is larger than 1.  Also, in the second case, the coefficient's value depends on whether $\\alpha<2$. What is $q_1$ here?\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "KgWY2lcpI9I", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "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 gives a theoretical study of the tail behavior of the SGD in a quadratic optimization problem and explores its relationship with the curvature, step size and batch size. To prove their results, the authors approximate the SGD recursion by a linear stochastic recursion and analyze the statistical properties by the tools from implicit renew theory. Under this setting, they show that the law of the SGD iterates converge to a heavy-tailed stationary distribution depending on the Hessian structure of the loss function at the minimum and choices of the step size and batch size. They take a further step to clarify the relationship and study the moment bounds and convergence rate. \n\nOverall, I vote for accepting. I think the study of heavy tail phenomenon in SGD is quite a novel field and full of interest. \n1.\tThis paper is the first one to study the originating cause of heavy tail phenomenon in SGD and give a rigorous proof of the relationship between tail index and the choice of step size and batch size. This helps a better understanding of the generalization properties of SGD. \n2.\tThe paper provides comprehensive experiments to support their result. Experiments are conducted on both synthetic data and neural networks. The design of experiments is reasonable, and the results of the experiment not only support the claim that the tail index is deeply linked to the curvature of the loss and the ratio of step size and batch size but also give an insight on more general cases besides the quadratic optimization.\n\nHowever, I am still concerned about the setting in the theoretical frame. This paper completes its proof under the settings of quadratic optimization and infinite streaming data, which may limit the applicability of the theoretical result. Although these issues have been discussed in this paper, whether or why this extension is feasible remains questionable.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work seeks to describe the heavy-tail phenomenon observed for deep networks learned with SGD. The work presents proof of a relationship between curvature, step size, batch size, and a heavy-tail weight distribution. The proofs assume a quadratic optimization problem and the authors speculate that the results may also be relevant for non-convex deep learning settings. On the positive side the reviewers agreed that this work is one of the first, if not the first, to try to theoretically describe a poorly understood phenomenon in deep learning. On the less positive side, the reviewers believe that the proofs developed in this paper are for an idealized setting that is too different from the settings under which deep models are trained. As such, even though the authors provide some (somewhat mixed) experimental results to support the claim of relevance to deep learning, the reviewers were not convinced. Given that the stated goal of the work is to attempt to explain this phenomenon in deep models, the majority view is that this work, while promising, needs further development to convincingly claim some relevance to the original phenomenon being studied.
Decision: Reject