Large Learning Rate Tames Homogeneity: Convergence and Balancing Effect
Authors: Yuqing Wang
Minshuo Chen
Tuo Zhao
Molei Tao
Venue: ICLR 2022 Poster (2022)
Keywords: large learning rate
gradient descent
matrix factorization
implicit regularization
convergence
balancing
alignment

Abstract: Recent empirical advances show that training deep models with large learning rate often improves generalization performance. However, theoretical justifications on the benefits of large learning rate are highly limited, due to challenges in analysis. In this paper, we consider using Gradient Descent (GD) with a large learning rate on a homogeneous matrix factorization problem, i.e., $\min_{X, Y} \|A - XY^\top\|_{\sf F}^2$. We prove a convergence theory for constant large learning rates well beyond $2/L$, where $L$ is the largest eigenvalue of Hessian at the initialization. Moreover, we rigorously establish an implicit bias of GD induced by such a large learning rate, termed `balancing', meaning that magnitudes of $X$ and $Y$ at the limit of GD iterations will be close even if their initialization is significantly unbalanced. Numerical experiments are provided to support our theory.

Published as a conference paper at ICLR 2022
LARGE LEARNING RATE TAMES HOMOGENEITY: CONVERGENCE AND BALANCING EFFECT
Yuqing Wang, Minshuo Chen, Tuo Zhao, Molei Tao
Georgia Institute of Technology
(ywang3398, mchen tourzhao, mt mtao)@gatech..... edu
ABSTRACT
Recent empirical advances show that training deep models with large learning rate often improves generalization performance. However, theoretical justifications on the benefits of large learning rate are highly limited, due challenges in analysis. In this paper, we consider using Gradient Descent (GD) with large learning rate on a homogeneous matrix factorization problem, i.e., minx,y y || XYTIP We prove a convergence theory for constant large learning rates well beyond 2/ L., where L is the largest eigenvalue of Hessian at the initialization. Moreover, we rigorously establish an implicit bias of GD induced by such large learning rate, termed bblancing', meaning that magnitudes of X and Y at the limit of GD iterations will be close even if their initialization is significantly unbalanced. Numerical experiments are provided to support our theory.
INTRODUCTION
Training machine learning models such deep neural networks involves optimizing highly nonconvex functions. Empirical results indicate an intimate connection between training algorithms and the performance of trained models (Le al., 2011; 1; Bottou al., 2018: 8; Zhang al., 2021; Soydaner, 2020; Zhou et al., 2020). Especially for widely used first-order training algorithms (e.g., GD and SGD), the learning rate is of essential importance and has received extensive focus from researchers (Smith, 2017; Jastrzebski et al., 2017; Smith, 2018; Gotmare et al., 2018; Liu et al., 2019; Li & Arora, 2019). A recent perspective that large learning rates often lead to improved testing performance compared to the counterpart trained with small learning rates (Smith & Topin, 2019; Yue et al., 2020). Towards explaining the better performance, common belief that large learning rates encourage the algorithm search for flat minima, which often generalize better and are more robust than sharp ones (Seong et al., 2018; Lewkowyzz al., 2020).
Despite abundant empirical observations, theoretical understandings of the benefits of large learning rate are still limited for non-convex functions, partly due to challenges in analysis. For example, the convergence (of GD or SGD) under large learning rate not guaranteed. Even for globally smooth functions, very few general results exist if the learning rate exceeds certain threshold (Kong & Tao, 2020). Besides, popular regularity assumptions such as global smoothness for simplified analyses are often absent in homogencous models, including commonly used ReLU neural networks.
This paper theoretically studies the benefits of large learning rate in matrix factorization problem
min X.Y
A - X- where A E g X,Y e Rad
(1)
2
We consider Gradient Descent (GD) for solving (1): at the k-th iteration, we have
X Xx + h(A X,Y and Y = Yv h(AT )xX
where is the learning rate. Despite its simple formula, problem (1) serves as an important foundation of variety of problems, including matrix sensing (Chen & Wainwright, 2015: Bhojanapalli et al., 2016; Tu et al., 2016), matrix completion (Keshavan et al., 2010; Hardt, 2014), and linear neural networks (Ji & Telgarsky, 2018; Gunasekar al., 2018).

---

Published as a conference paper at ICLR 2022
Problem (1) possesses several intriguing properties. Firstly, the objective function is non-convex, and critical points are either global minima or saddles (see e.g.. Baldi & Hormik (1989); Li et al. (2019b); Valavi et al. (2020a); Chen et al. (2018)). Secondly, problem (1) is homogeneous in X for any a * O will not change the objective's
and Y. meaning that rescaling X, Y to ax,aa a value. This property is shared by commonly used ReLU neural networks. A direct consequence of homogeneity is that global minima of (1) are non-isolated and can be unbounded. The curvatures at these global minima are highly dependent on the magnitudes of X, Y. When X, Y have comparable magnitudes, the largest eigenvalue of Hessian is small, and this corresponds to a flat minimum; on the contrary, unbalanced X and Y give sharp minimum. Last but not the least, the homogeneity impairs smoothness conditions of (1), rendering the gradient being not Lipschitz continuous unless x,Y Y are bounded. See a formal discussion in Section 2.
Existing approaches for solving (1) often uses explicit regularization (Ge et al., 2017: Tu et al., 2016; Cabral et al., 3013: Li et al., 2019a), or infinitesimal (or diminishing) learning rates for controlling the magnitudes of X, Y (Du et al., 2018: Ye & Du, 2021). In this paper, we go beyond the scope of aforementioned works, and analyze GD with large learning rate for solving (1). In particular, we allow the learning rate to be as large as approximately 4/ (see more explanation Section 2), where L denotes the largest eigenvalue of Hessian at GD initialization. In connection to empirical observations, we provide positive answers to the following two questions:
Does GD with large learning rate converge at least for some cases of (1)? Does larger learning rate biases toward flatter minima (i.e., X,Y Y with comparable magnitudes)?
We theoretically show the convergence of GD with large learning rate for the two situations n = 1, d E N+ or d = 1, N+ with isotropic A. We also observe a, perhaps surprising. "balancing effect" for general matrix factorization (i.e., any d, nt, and A), meaning that when / is sufficiently large, the difference between X and Y shrinks significantly the convergence of GD compared to its initial, even if the initial point is close to an unbalanced global minimum. In fact, with proper large learning rate h, || Y lf may decrease by an arbitrary factor at its limit. The following is simple example of our theory for n (i.e. scalar factorization), and more general results will be presented later with precise bound for l depending on the initial condition and A.
Theorem 1.1 (Informal version of Thm.3.1 & 3.2). Given scalar A and initial condition Xo. Yo E R lx chosen almost everywhere, with learning rate h S L, GD converges a global minimum (X, Y) satisfying || 1 || < h. Consequently, its extent of balancing is quantified by |X - YI 2 22A
We remark that having learning rate h ~ 4/L is far beyond the commonly analyzed regime in optimization. Even for globally L-smooth objective, traditional theory requires h < 2/L. for GD convergence and h I/L L is optimal for convex functions (Boyd al., 2004), not to mention that our problem (1) is never globally L-smooth due to homogeneity. Modified equation provides tool for probing intermediate learning rates (see Hairer et al. (2006, Chapter 9) for a general review, and Kong& & Tao (2020, Appendix A) for the specific setup of GD), but the learning rate here is too large for modified equation to work (see Appendix C). In fact, besides blowing up. GD with large learning rate may have zoology of limiting behaviors (see e.g., Appendix B for convergence to periodic orbits under our setup, and Kong& & Tao (2020) for convergence to chaotic attractors).
Our analyses (of convergence and balancing) leverage various mathematical tools, including a proper partition of state space and its dynamical transition (specifically invented for this problem), stability theory of discrete time dynamical systems (Alligood et al., 1996), and geometric measure theory (Federer, 2014).
The rest of the paper is organized as: Section 2 provides the background of studying (1) and discusses related works; Section 3 presents convergence and balancing results for scalar factorization problems; Section 4 generalizes the theory to rank-1 matrix approximation; Section 5 studies problem (1) with arbitrary A and its arbitrary-rank approximation; Section summarizes the paper and discusses broadly related topics and future directions.
2

---

Published as a conference paper at ICLR 2022
2 BACKGROUND AND RELATED WORK
Notations. ||u|| is l norm of a column row vector v. || is the Frobenius norm of a matrix M.
Sharp and flat minima in (I) We discuss the curvatures at global minima of (I), To ease the presentation, consider simplified versions of (1) with either n = 1 or = 1. In this case, X and Y become vectors and we denote them 2. y, respectively. We show the following proposition characterizing the spectrum of Hessian at a global minimum.
Proposition 2.1. When n = 1, E N+ or d I, E N+ in (I), the largest eigenvalue of Hessian at global mininuum (x.y) is ||=|| + |yll and the smallest eigenvalue is O.
Homogenity implies global minimizers of (1) are not isolated, which is consistent with the O eigen- value. On the other hand, if the largest eigenvalue ||=]| + |lvll is large (or small), then the curvature at such a global minimum is sharp (or flat), in the direction of the leading eigenvector. Meanwhile, note this sharpness/flannss an indication of the balancedness between magnitudes of æ, y at global minimum. To see this, singular value decomposition (SVD) yields that at a global minimum, (z, y) satisfies |yzy T ll: ((xx((A), Therefore, large |||||| 2 + |lv/l is obtained when |||=|| - |vlll is large, i.e., x and y magnitudes are unbalanced, and small ||0:|| | + ||y| is obtained when balanced.
Large learning rate We study smoothness properties of (1) and demonstrate that learning rate is well beyond conventional optimization theory. We first define the smoothness of function.
Definition 2.2 (L-smooth), A function f C¹ defined on R: L-smooth if for all U1 U2 E R.V
[V - f( S L|| - u2ll-
(2)
If further / E C², then V²ʃ 3 LI. Moreover, if we have (2) for U1, E 2' C RA, we call it locally L-smooth.
In traditional optimization (Nesterov, 2003: Polyak, 1987: Nesterov, 1983; Polyak, 1964; Beck & Teboulle, 2009), most analyzed objective functions often satisfy (i) (some relaxed form of) convexity or strong convexity, and (ii) L-smoothness. Choosing a step size h < 2/ L guarantees the convergence of GD to minimum by the existing theory (reviewed in Appendix F.3). Our choice of learning rate R 4/L (more precisely, 4/ Lo: see below) goes beyond the classical analyses.
Besides, in our problem (1). the regularity very different. Even simplified versions of (1), i.e., with either = or d 1, suffer from (i) non-convexity and (ii) unbounded eigenvalues of Hessian, i.e., no global smoothness (see Appendix F.2 for more details). As shown in Du al. (2018); Ye Du (2021); Ma et al. (2021), decaying infinitesimal learning rate ensures that the GD trajectory stays in a locally smooth region. However, the gap between the magnitudes of X, Y can only be maintained in that case. We show, however, that larger learning rate can shrink this gap. More precisely, if initial condition is well balanced, there is no need to use large learning rate; otherwise, we can use learning rate large as approximately 4/ L,, and within this range, larger h provides smaller gap between X and Y at the limit (i.e. infinitely many GD iterations).
Related work Matrix factorization problems in various forms have been extensively studied in the literature. The version of (1) is commonly known as the low-rank factorization, although here d can arbitrary and we consider both d < rank(A) and >> rank(AA) cases. Baldi & Hornik (1989); Li et al. (2019b); Valavi et al. (2020b) provide landscape analysis of (1). Ge et al. (2017); Tu et al. (2016) propose to penalize the Frobenius norm of | x - and establish global convergence guarantees of GD for solving (1). Cabral et al. (2013); Li al.
YTY yl? to mitigate the homogeneity
(2019a) instead penalize individual Frobenius norms of || + [| We remark that penalizing ||I + ||Y|| is closely related to nuclear norm regularization, since the variational formula for nuclear norm || mmnlixxxx X | + ||Y||" More recently, Liu et al. (2021) consider using injected noise as regularization to GD and establish a global convergence (see also Zhou et al. (2019); Liu et al. (2022). More specifically, by perturbing the GD iterate (Xx, Y2) with Gaussian noise, GD will converge to a flat global optimum. On the other hand, Du et al. (2018); Ye & Du (2021); I); Ma et al. (2021) show that even without explicit regularization, when the learning rate of GD is infinitesimal,
3

---

Published as a conference paper at ICLR 2022
Le., GD approximating gradient flow, X and Y maintain the gap in their magnitudes. Such an effect is more broadly recognized as implicit bias of learning algorithms (Neyshabur et al., 2014; Gunasekar et al., 2018; Soudry al., 2018; Li et al., 2020; 2021). Built upon this implicit bias, Du et al. (2018) further prove that GD with diminishing learning rates converges to a bounded global minimum of (1), and this conclusion is recently extended to the case of constant small learning rate (Ye & Du, 2021). Our work goes beyond the scopes of these milestones and considers matrix factorization with much larger learning rates.
Additional results exist that demonstrate large learning rate improve performance in various learning problems. Most of them involve non-constant learn rates. Specifically, Li et al. (2019c) consider two-layer neural network setting, where using learning rate annealing (initially large. followed by small ones) can improve classification accuracy compared to training with small learning rates. Nakkiran (2020) shows that the observation Li al. (2019c) even exists in convex problems. Lewkowycz et al. (2020) study constant large learning rates, and demonstrate distinct algorithmic behaviors of large and small learning rates, as well as empirically illustrate large learning rate yields better testing performance perspective (Jacot et al., 8), with a focus on the kernel spectrum evolution under large learning rate. Worth noting is, Kong& & Tao (2020) also study constant large learning rates, and show that large learning rate provides a mechanism for GD to escape local minima, alternative to noisy escapes due to stochastic gradients.
neural networks. Their analysis is built upon the neural tangent kernel
OVERPARAMETRRIZED SCALAR FACTORIZATION
In order to provide intuition before directly studying the most general problem, we begin with a simple special case, namely factorizing scalar by two vectors. It corresponds to (1) with 1 and d E N+ and this overparameterized problem is written as
1 (p (1- fla-ry' ry
min Z xn 2
(3)
where μ is assumed without loss of generality to be positive scalar. Problem (3) can be viewed as univariate regression using a linear two-layer neural network with the quadratic loss, which is studied in Lewkowycz et al. (2020) with atomic data distribution. Yet our analysis in the sequel can be used to study arbitrary univariate data distributions; see details in Section 6.
Although simplified, problem (3) is still nonconvex and exhibits the same homogeneity as (1). The convergence of its large learning rate GD optimization was previously not understood, let alone balancing. Many results that we will obtain for (3) will remain true for more general problems.
We first prove that GD converges despite of > 2/T. learning rate and for almost all initial conditions: Theorem 3.1 (Convergence). Given (I) yo E (Rd x y B where B is some Lebesgue measure-0 set, when the learning rate h satisfies
1
5 min
[ 12
+
|80| 2
4t
3p
GD converges to global minimum.
Theorem 3.1 says that choosing a constant learning rate depending on GD initialization guarantees the convergence for almost every starting point in the whole space. This result is even stronger than the already nontrivial convergence under small learning rate with high probability over random initialization (Ye & Du, 2021). Furthermore, the upper bound on h is sufficiently large: on the one hand, suppose GD initialization (#o, yo) close to an unbalanced global minimum. By Proposi- tion 2.1, we can check that the largest eigenvalue L( Mo) of Hessian fzo, Mo) is approximately || + |! Consequently, our upper bound of h is almost 4/T., T,, which is beyond 2/T. (see Section 2 for more details). On the other hand, we observe numerically that the 4/T. upper bound actually very close the stability limit of GD when initialized away from the origin (see more details in Appendix E).
The convergence in Theorem 3.1 has an interesting toapiiigg-o--oovegiing transition as depicted in Figure 1, where we observe two phases. In Phase large learning rate drives GD search for flat
4

---

Published as a conference paper at ICLR 2022
4
||xel1 lbxall
h
Phase
||= - Ibxll e ||xx|| Mblll
Phase
1x + 11x/l1 2
large Figure 1: The dynamics of GD under different learning rate h
small
regions, escaping from the attraction of sharp minima. After some iterations, the algorithm enters the vicinity of a global minimum with more balanced magnitudes in Then in Phase 2. GD converges the found balanced global minimum. We remark that the searching-to-or tovveverggn transition also appears in Lewkowycz. et al. (2020). However, the algorithmic behaviors are not the same. In fact, in our searching phase (phase 1), the objective function does not exhibit the blow-up phenomenon. In convergence phase (phase 2), the analysis relies detailed state space partition (see Line 192) due to nonconvex nature (3), while the analysis Lewkowycz et al. (2020) is akin to monotone convergence in convex problem.
In comparison with the dynamics of small learning rate, we note that the searching phase (Phase 1) is vital to the convergence analysis. Meanwhile, the searching phase induces a balancing effect of large learning rate. The following theorem explicitly quantifies the extent of balancing.
Theorem 3.2 (Balancing). Under the same initial condition and learning rate h as Theorem 3.1, GD for (3) converges a global minimizer (z. y) satisfying
| 11 - h
Consequently, its extent of balancing is quantified by
|| - y/1 S 24.
One special case of Theorem 3.2 is the following theorem, which states that no matter how close to a global minimum does GD start, if this minimum does not correspond to well-halanced norms, large learning rate will take the iteration to more balanced limit. We also demonstrate sharp shrinkage in the distance between æ and y.
Corollary 3.3 (From 'unbalanced" to "balanced'), For any å E (0, n.). let the GD initialization satisfy
(zo, yo) {u, v) |uv n1 8, ||u||2 + ||a||2 \
where B is some Lebesgue measure-O set. When the learning rate h satisfies h = T 1 44p the extent of balancing at the limiting point (z, y) of GD obeys
1 || - y/1 < 2 |1000 - yo 2 + 2p..
Both Theorem 3.2 and Corollary 3.3 suggest that larger learning rate yields better balancing effect, as ||æ - 2/12 the limit of GD may decrease lot and is controlled by the learning rate. We remark that the balancing effect a consequence of large learning rate, as small learning rate can only maintain the difference in magnitudes of xr (Du et al., 2018)
In addition, the actual balancing effect can be quite strong with ||, 11 decreasing to be almost its limit under proper choice of large learning rate. Figure illustrates almost perfect balancing case when h = || -- Vo 44 R 0.0122 is chosen as the upper bound. The difference || yk decreases from approximately 17. 1..9866 0.0154 its limit. Additional experiments with various learning rates and initializations can be found in Appendix A.
Technical Overview We sketch the main ideas behind Theorem 3.1, which lead to the balancing effect in Theorem 3.2. Full proof is deferred Appendix G.
5

---

Published as a conference paper at ICLR 2022
0.0122
10
20
Loss
109
10
5
10
0
100
200
300
100
200 300
number of iterations
number of iterations
Figure 2:
The objective function (1 - xy /2/2, where x .y" R. Highly unbalanced initial
condition is uniformly randomized, with the norms to be || 18, l| = 0.09.
The convergence proved by handling Phase and separately (see Fig.1), 1). In Phase we prove that || 2 ||v==l has a decreasing trend as GD searches for flat minimum. We show that || + || may not be monotone, i.e., either decreases every iteration decreases every other iteration.
In Phase 2, we carefully partition the state space and show GD at each partition will eventually enter a monotone convergence region, Note that the partition based on detailed understanding of the dynamics and is highly nontrivial. Attentive readers may refer Appendix G for more details. The combination of Phase & is briefly summarized as a proof flow chart in Figure 3.
||x,|| llxal
Phase
bp(ll=,11* + lxxI1))
Apr(I 11xa119
xox or
h(112 + [bxlP) $ x <
hr 1 lIxx1²
|| + ID < ||x,11+ lIxIll
|| + llbaaall < ||xil1 l1xil1?
h 2hyx < Bayll l1xall 2
11x.11 + lbxal1 2hy²
x.s > 3p
|| + I1 < ||x,11 lbxull?
or xox <
Phase 2
- S xooT 1
5
52
# x 33p
8k+1 86-1
||
IB
||xgl12
lbxll
Convergence
Figure 3: Proof overview of Theorem 3.1. At the k-th iteration, we denote (Mi,, yh)) as the iterate and 8g defined as FK+1VE+1 J 84 (1 - 14).
RANK-1 APPROX. OF ISOTROPIC A (AN UNDER- PNDER-PARAMETERIZED CASE)
Given insights from scalar factorization, we consider rank-1 factorization of an isotropic matrix A, ie.,, A juax with y 0, d and N+. The corresponding optimization problem is
2 || - ry Ty
min z.yeRax1
(4)
Although similar at an uncareful glance, Problems (4) and (3) are rather different unless n
First of all, Problem (4) is under-parameterizes for > 1, while (3) is overparameterized. More importantly, we'll show that, when (x, y) is a global minimum of (4), x, y must be aligned, i.e., x = fy for some & > 0. In the scalar factorization problem, however, such alignment is required. As result, the set of global minima of (4) an n-diiennsinal submanifold embedded a on-dimenssionl space, while in the scalar factorization problem the of global minimum (2d dimieenssiaa

---

Published as a conference paper at ICLR 2022
submanifold one rank deficient - in 2d-dimensional space. We expect the convergence in (4) is more complicated than that in (3), since searching in (4) demanding.
To prove the convergence of large learning rate GD for (4), our theory consists of two steps: (i) show the convergence of the alignment between and y (this is new); (ii) use that to prove the convergence of the full iterates (i.e., x y). Step (i) first:
Theorem 4.1 (Alignment). Gäven (mo, vo)
(R" RB,,B where B is some Lebesgue measure-O aa ++ 1+ 20Th) } the iterator (Ig, yk) of GD at the
set, when learning rate h min k-th iteration satisfies | cos( ((Tk: Vk))
+ Las as k oc.
Proof sketch. A sufficient condition for the convergence of cos( ( vk))) is | ] (m) yx)² + O. To ease the presentation, let Us+ Fx yk: Vi Fg Tke and Wx Uh yk- By the GD update and some algebraic manipulation, we derive
|l ||
V&+1 W - U rkk (V&W - U.))
where rs =
(1 - h(V + W&) + (V& - 2²)) When h is sufficiently large, we can show a uniform upper bound ræ < 1 for some constant e O. In this way, deduce that V& U2 will exponentially decay and converge to O. More details are provided in Appendix H.
Theorem 4.1 indicates that GD iterations will converge to the neighbourhood of {(x, y) ey, for some / R [\OO). This helps establish the global convergence stated in Step (ii).
Theorem 4.2 (Convergence). Under the same initial conditions and learning rate h as Theorem 4.1, GD for (4) converges to global minimum.
Similar to the over-parametriae scalar case, this convergence can also be split into two phases where phase motivates the balancing behavior with the decrease of ||axx|1 + || and phase 2 ensures the convergence. The following balancing theorem is thus obtained.
Theorem 4.3 (Balancing). Under the same initial conditions and learning rate h as Theorem 4.1, GD for (4) converges to global minimizer that obeys
||=||² |18/1 S h'
and its extent of balancing quantified by
x y1 < 2p.
This conclusion is the same as the one in Section A quantitatively similar corollary like Corol- lary 3.3 can also be obtained from the above theorem, namely, if zo and start from unbalanced point near a minimum, the limit will a more balanced one.
5 GENERAL MATRIX FACTORIZATION
In this section, consider problem (1) with an arbitrary matrix A pax=, We replicate the problem formulation here for convenience,
min X,Y e
|A A- X
(5)
Note this is the most general case with n, E N+ and any square matrix A. Due to this generalization, longer utilize the convergence analysis and instead, establish the balancing theory via stability analysis of GD as a discrete time dynamical system.
Let #1 2 U2 2 ... 2 Pn 2 0 be the singular values of A. Assume for technical convenience and n. We denote the singular value decomposition of A
|| = Σ being independent as A = UDVT where D,D.V V e R= U, V are orthogonal matrices and is diagonal. Then we establish the following balancing effect.
7

---

Published as a conference paper at ICLR 2022
Theorem 5.1. Given almost all the initial conditions, for any learning rate h such that GD for (5) converges to a point (X,Y), there exists с = c(n, d) > co with constant co > independent of h, n, and d, such that (X, Y) satisfies
a(x + < h
and the extent of balancing is quantified by || (UV
y
< ch -
2
-
ti which means
min(d.n)
2
|| - || <
2
Σ
ch
In particular, when d = 1, i.e., fank-Ifactorizztiio of an arbitrary A, the constant eequals 1.
We observe that the extent of balancing can be quantified under some rotation of Y. This is necessary, since for factorizing general matrix (which can be asymmetric), at a global minimum, X, Y may only align after a rotation (which is however fixed by A, independent of initial or final conditions). Figure 4 illustrates an example of the balancing effect under different learning rates. Evidently, larger learning rate leads a more balanced global minimizer. Additional experiments with various dimensions, learning rates, and initializations can be found in Appendix A; a similar balancing effect also shown for additional problems including matrix sensing and matrix completion there.
A=0.1839
1= 0460
10
10
Loss
XxIl |F Y P
Loss
109
109
X ||=
Ya
10
10
100
200
100 number of iterations
200
100 number of iterations
number iterations
number of iterations
Figure 4: Balancing effect of general matrix factorization. We independently generate elements in A E R6x6 from a Gaussian distribution. We choose X, Y E 166x100 and randomly pick a pair of initial point (Xo, Yo) with X = 1 and ||ooll= = 9.
Different from previous sections, Theorem 5.1 builds on stability analysis by viewing GD as a dynamical system in discrete time. More precisely, the proof of Theorem 5.1 (see Appendix for details) consists of two parts: (i) the establishment of an easier but equivalent problem via the rotation of X and Y. (ii) stability analysis of the equivalent problem.
For (i), by singular value decomposition (SVD), A UDVT, where U,D.V E Ruxn U and V are orthogonal matrices, and is non-negative diagonal matrix. Let X₁ = RR, Y, = VS.. Then
{
X = Xx + h(A X Y Yot1 Yv + -(A-Ax
UR = UR + MUDVV S VTVVVVS
VS++1 = VS, + +UUDV - SURS V VTTTUR
{
R&+1 = R4 + hhD - -RRST)S SS Sk+1 = + +hDD R& T TR.
Therefore, GD for problem (5) is equivalent to GD for the following problem
min 1 |I R
x 2
and it thus suffices to work with diagonal non-negative A.
For (ii), here is a brief description of the idea of stability analysis: consider each iteration of GD as a mapping d from us (Xx, YR) u441 (Xe+1, Yk+1), where matrices X and Y are flattened
8

---

Published as a conference paper at ICLR 2022
and concatenated into vector that a is closed map on vector space IR GD iteration is thus discrete time dynamical system on state space 22dd given by
uk+1 = (ux) = fux),
where f the objective function f(ux) = 1 ||A Y lF. and gradient returns vector that
collects all component-wise partial derivatives.
It's easy to see that any stationary point of f. denoted by u", is a fixed point of th, i.e., u = ((")). What fixed point will the iterations of &b converge to? For this, the following notions are helpful: Proposition 5.2. Consider a fixed point u² of tb. If all the eigenvalues of Jacobian matrix Vab(u") are of complex modulus less than 1, is stable fixed point.
Proposition 5.3. Consider a fixed point 4² of tb. If at least one eigenvalue of Jacobian matrix Vib(u)) is of complex modulus greater than 1, it is an unstable fixed point.
Roughly put, the stable set of an unstable fixed point is of negligible size when compared to that of a stable fixed point, and thus what GD converges to is a stable fixed point for almost all initial conditions (Alligood et al., 1996). Thus, we investigate the stability of each global minimum of (each saddle of f is an unstable fixed point of & and thus is irrelevant). By detailed evaluation of Ve'ss eigenvalues (Appendix D, we see that a global minimum (X, Y) of f corresponds to a stable
fixed point of GD iteration if 1 (I + [181A)
< 1, i.e., is balanced as in Thm. 5.1.
CONCLUSION AND DISCUSSION
In this paper, we demonstrate an implicit regularization effect of large learning rate on the homo- geneous matrix factorization problem solved by GD. More precisely, phenomenon termed as "balancing" is theoretically illustrated, which says the difference between the two factors X and Y may decrease significantly at the limit of GD, and the extent of balancing can increase learning rate increases. In addition, we provide theoretical analysis of the convergence of GD to the global minimum, and this is with large learning rate that can exceed the typical limit of 2/ T,, where L is the largest eigenvalue of Hessian at GD initialization.
For the matrix factorization problem analyzed here, large learning rate avoids bad regularities induced by the homogeneity between X and Y. We feel it is possible that such balancing behavior also be seen in problems with similar homogeneous properties, for example, in tensor decomposition (Kolda & Bader, 2009), matrix completion (Keshavan al., 2010; Hardt, 2014), generalized phase retrieval (Candes et al., 2015; Sun et al., 2018), and neural networks with homogeneous activation functions (e.g., ReLU). Besides the balancing effect, the convergence analysis under large learning rate may be transplanted to other non-convex problems and help discover more implicit regularization effects.
In addition, factorization problems studied here are closely related to two-layer linear neural networks. For example, one-dimensional regression via two-layer linear neural network can be formulated as the scalar factorization problem (3): Suppose we have collection of data points (æ 9:) E IR x IR for 1,..., n. We aim to train linear neural network y = (u v)æ with u, data. We optimize u, v by minimizing the quadratic loss,
U E Rd for fitting the
1 Di= Difi 5 E x?
(u", (u)" E arg min 0,0
(y: (u v))::) arg min 2,22 n
(6)
As can be seen, taking 1 Σ.
2ith
recovers (3). In this regard, our theory indicates that training
of u, v by GD with large learning rate automatically balances u, U, and the obtained minimum is flat.
This may provide some initial understanding of the improved performance brought by large learning rates in practice. Note that (6) generalizes to arbitrary data distribution of training two-layer linear network with atomic data (i.e., x = and 0) in Lewkowycz et al. (2020).
is important to clarify, however, that there is a substantial gap between this demonstration and extensions to general neural networks, including deep linear and nonlinear networks. Although suspect that large learning rate leads to similar balancing effect of weight matrices in the network, rigorous theoretical analysis is left as future direction.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
We thank anonymous reviewers and area chair for suggestions that improved the quality of this paper. The authors are grateful for partial supports from NSF DMS-1847802 (YW and MT) and ECCS-1936776 (MT).
REFERENCES
Kathleen T Alligood, Tim D Sauer, and James A Yorke. Chaos: an introduction to dynamical systems. Springer, 1996.
Pierre Baldi and Kurt Horiik. Neural networks and principal component analysis: Learning from examples without local minima. Neural networks, 2(1))53-58, 1989.
Amir Beck and Mare Teboulle. A fast iterative shrinkage-threshollinng algorithm for linear inverse problems. SIAM journal on imaging sciences, 2(1):183-202, 2009.
Srinadh Bhojanapalli,, Anastasios Kyrillidis, and Sujay Sanghavi. Dropping convexity for faster semi-definite optimization. In Conference on Learning Theory, pp- 530-582. PMLR, 2016.
Léon Bottou, Frank Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. Siam Review, 60(2):223-311, 2018.
Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
Ricardo Cabral, Fernando De la Torre, João P Costeira, and Alexandre Bernardino. Unifying nuclear norm and bilinear factorization approaches for low-rank matrix decomposition. In Proceedings of the IEEE International Conference on Computer Vision, pp. 2488-2495, 2013.
Emmanuel J Candes, Xiaodong Li, and Mahdi Soltanolkotabi. Phase retrieval via wirtinger flow: Theory and algorithms. IEEE Transactions Information Theory, 1985-2077,2 2015.
Yudong Chen and Martin J Wainwright. Fast low-rank estimation by projected gradient descent:
General statistical and algorithmic guarantees. arXiv preprint arXiv: 03025, 2015.
Zhehui Chen, Xingguo Li, Lin F Yang, Jarvis Haupt, and Tuo Zhao. On landscape of la- grangian functions and stochastic search for constrained nonconvex optimization. arXiv preprint 10x10:1806.00151,, 2018.
Simon Du, Wei Hu, and Jason D Lee. Algorithmic regularization in learning deep homogeneous models: Layers are automatically balanced. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
Herbert Federer. Geometric measure theory. Springer, 2014.
Rong Ge, Chi Jin, and Yi Zheng. No spurious local minima in nonconvex low rank problems: A unified geometric analysis. In International Conference on Machine Learning, pp. 1233-1242. PMLR. 2017.
Akhilesh Gotmare, Nitish Shirish Keskar, Caiming Xiong, and Richard Socher. closer look at deep learning heuristies: Learning rate restarts, warmup and distillation. arXiv preprint arXiv:1810.13243. 2018
Suriya Gunasekar, Blake Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nathan Srebro. Implicit regularization in matrix factorization. 2018 Information Theory and Applications Workshop (ITA), pp- 1-10. IEFF, 2018.
Emsst Hairer, Marlis Hochbruck, Arich Iserles, and Christian Lubich. Geometric numerical integration. Oberwolfach Reports, 3(1):805-882) 882, 2006.
10

---

Published as a conference paper at ICLR 2022
Moritz Hardt. Understanding alternating minimization for matrix completion. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pp. 651-660. IEEE, 2014.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. arXiv preprint arXiv: arXiv:/806.07555 006.0757, 2018.
Stanislaw Jastrzebski, Zachary Kenton, Devansh Arpit, Nicolas Ballas, Asja Fischer, Yoshua Bengio, and Amos Storkey. Three factors influencing minima in sgd. arXiv preprint urXiv:/711 1711.04623, 2017.
Ziwei Ji and Matus Telgarsky. Gradient descent aligns the layers of deep linear networks, arXiv preprint arXiv:1810.02032, 2018.
Raghunandan H Keshavan, Andrea Montanari, and Sewoong Oh. Matrix completion from a few entries. IEEE transactions on information theory, 56(6):2980-299) 2010.
Tamara G Kolda and Brett W Bader. Tensor decompositions and applications. SIAM review, 51(3): 455-500, 2009.
Lingkai Kong and Molei Tao. Stochasticity of deterministic gradient descent: Large learning rate for multiscale objective function. In Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 2625 2638.. Curran Associates, Inc., 2020.
Quoc Le, Jiquan Ngiam, Adam Coates, Ahbik Lahiri, Bobby Prochnow, and Andrew Ng. On optimization methods for deep learning. In ICML, 2011.
Aitor Lewkowycz, Yasaman Bahri, Ethan Dyer, Jascha Sohl-Dickstein, and Guy Gur-Ari. The large learning rate phase of deep learning: the catapult mechanism. 2020.
Qiuwei Li, Zhihui Zhu, and Gongguo Tang. The non-convex geometry of low-rank matrix optimiza- tion. Information and Inference: Journal of the IMA, 8(1):51 16, 2019a.
Xingguo Li, Junwei Lu, Raman Arora, Jarvis Haupt, Han Liu, Zhaoran Wang, and Tuo Zhao. Symmetry, saddle points, and global optimization landscape of nonconvex matrix factorization. IEEE Transactions Information Theory, 65(6):3489-33) 3514, 2019b.
Yan Li, Ethan X.Fang, Huan Xu, and Tuo Zhao. Implicit bias of gradient descent based adversarial training on separable data. In International Conference on Learning Representations, 2020. URL
https:// https///pppeeiieeeeeeeee net / forum iid HKgTTTFFF....
Yan Li, Caleb Ju, Ethan X Fang, and Tuo Zhao. Implicit regularization of bregman proximal point
algorithm and mirror descent on separable data. arXiv preprint arXiv:2108. 06808, 2021.
Yuanzhi Li, Colin Wei, and Tengyu Ma. Towards explaining the regularization effect of initial large learning rate in training neural networks. arXiv preprint arXiv:1907.04555 2019c.
Zhiyuan Li and Sanjeev Arora. An exponential learning rate schedule for deep learning. arXiv preprint arXiv:1910.07454 2019.
Liyuan Liu, Haoming Jiang, Pengcheng He, Weizhu Chen, Xiaodong Liu, Jianfeng Gao, and Jiawei Han. On the variance of the adaptive learning rate and beyond. arXiv preprint arXiv: 1906,03265, 2019.
Tianyi Liu, Yan Li, Song Wei, Enlu Zhou, and Tuo Zhao. Noisy gradient descent converges to flat minima for nonconvex matrix factorization. 2021.
Tianyi Liu, Yan Li, Enlu Zhou, and Tuo Zhao. Noise regularizes over-parameterized rank one matrix recovery, provably. arXiv preprint ar arXiv:2202.03535. 2022.
Cong Ma, Yuanxin Li, and Yuejic Chi. Beyond procrustes: Balancing-five gradient descent for
asymmetric low-rank matrix sensing. JEEE Transactions on Signal Processing, 69:867-877, 2021.
Prectum Nakkiran. Learning rate annealing can provably help generalization, even for convex problems. 2020.
11

---

Published as a conference paper at ICLR 2022
Yurii Nesterov. Introductory lectures convex optimization: A basic course, volume 87. Springer Science & Business Media, 2003.
Yurii E. Nesterov. A method for solving the convex programming problem with convergence (1/K22) 2). In Dokl. akad. nauk Sssr, volume 269, pp. 543-547, 1983.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. search of the real inductive bias: On the role of implicit regularization in deep learning. arXiv preprint arXiv: 1eti.6112........ 2014.
Boris T Polyak. Some methods of speeding up the convergence of iteration methods. Ussr computa- fional mathematics and mathematical physics, 4(5):1-17, 1964.
Boris T Polyak. Introduction to optimization. optimization software. Inc., Publications Division, New York, 1, 1987.
Sihyeon Seong, Yegang Lee, Youngwook Kee, Dongyoon Han, and Junmo Kim. Towards flatter loss surface via nonmonotonic learning rate scheduling. In UAI, pp. 1020-1030, 2018.
Leslie N Smith. Cyclical learning rates for training neural networks. In 2017 IEEE winter conference on applications of computer vision (WACV), pp. 464 472. IEEE, 2017.
Leslie N Smith. disciplined approach to neural network hyper-parameters: Part l-Icarning rate, batch size, momentum, and weight decay. arXiv preprint 1rxXiv:8833.08200 2018.
Leslie N Smith and Nicholay Topin. Super-convergence: Very fast training of neural networks using large learning rates. In Artificial Intelligence and Machine Leurning for Malli-Domain Operations Applications, volume 1 11006, pp. 1100612. International Society for Optics and Photonics, 2019.
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent on separable data. The Journal of Machine Learning Research, 19(1): 2822-2878, 2018
Derya Soydaner. A comparison of optimization algorithms for deep learning. International Journal of Patlern Recognition and Artificial Intelligence, 34(13):2052013, 2020.
Ju Sun, Qing Qu, and John Wright. A geometric analysis of phase retrieval. Foundations of Computational Mathematics, 1865):1 2018.
Stephen Tu, Ross Boczar, Max Simchowitz, Mahdi Soltanolkotabi, and Ben Recht. Low-rank solutions of linear matrix equations via procrustes flow. In International Conference on Machine Learning, pp. 964-973. PMLR, 2016.
Hossein Valavi, Sulin Liu, and Peter Ramadge. Revisiting the landscape of matrix factorization. In Silvia Chiappa and Roberto Calandra (eds.), Proceedings of the Twenty Third International Conference Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pp. 1629-1638. PMLR, 26-28 Aug 2020a.
Hossein Valavi, Sulin Liu, and Peter J Ramadge. The landscape of matrix factorization revisited. arXiv preprint 200: 20..20002..7995. /2795, 2020b.
Tian Ye and Simon S Du. Global convergence of gradient descent for asymmetric low-rank matrix factorization. arXiv preprint arXiv:2106.144 14289, 2021.
Xubo Yue, Maher Nouiched, and Raed Al Kontar. Salr: Sharpness-aware learning rates for improved generalization. arXiv preprint arXiv:2011.0553 1.05348, 2020.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107-115, 2021.
Mo Zhou, Tianyi Liu, Yan Li, Dachao Lin, Enlu Zhou, and Tuo Zhao. Toward understanding the importance of noise in training neural networks. In International Conference on Machine Learning. pp. 7594-7602. PMLR, 2019.
Pan Zhou, Jiashi Feng, Chao Ma, Caiming Xiong, Steven Hoi, et al. Towards theoretically under- standing why sgd generalizes better than adam in deep learning. arXiv preprint arXiv:2010.05627, 2020.
12

---

Published as a conference paper at ICLR 2022
Supplementary Materials for "Large Learning Rate Tames Homogeneity: Convergence and Balancing Effect"
A ADDITIONAL EXPERIMENTS
A.1 MORE RESULTS FOR MATRIX FACTORIZATION
In this section, we present more experiments with different choices of n, d, various initializations and scalings, and broader range of learning rates. All these experiments verify our claim on the balancing effect of large learning rate, i.e., the shrinkage of the gap between the magnitudes X and Y exists for general matrix factorization problems, i.e., for any choice of d E N
We first provide examples of scalar factorization in Figure 5, 6, and 7 to numerically justify our theory Section In the three figures, the initial conditions randomly generated, respectively with (|æooll [l) (9, 1). (o || = (19, 1), and (I|æol) [| = (99. 1); the learning rates are chosen within the range Theorem 3.1 from large to small as hg. hho hho tho, &ho, &ho for the || 2 + 8). The learning rates of the left three columns are larger than 2/L (L is the local Lipschitz constant of gradient near the initial condition), where we can see the decrease in the gap between ||ا||||| and || and larger learning rate leads to smaller gap; the right three correspond to h < 2/L where there are almost no changes in || and llvell as k increases. Moreover, the loss does not decrease monotonically the beginning of the iterations for all the h > 2/ cases while the later iterations GD shows monotone convergence; for the right three columns (h 2/T. cases), our two-phase pattern of convergence (see e.g. Figure and Section for detailed explanation).
1st-6th columns respectively where ho 4/([|=o
monotone decrease of the loss. This validates
10
10
10
10
10
10
n 19
8
8
8
6
6
6
6
4
2
2
2
2
50
100
50
100
0
50
100
0
50
100
0
50
100
50
100
à
=0.
0.0444
-0.0381
h
00.81175
h
=0.0554
=001900
h
=0.0127
10
105
5
10
10
105
10
10
10 /
10
10
10
10
5
10
10:5
10
10
10
100
10
10
10-10
10-10
10 15
15
10
15
15:15
10:15
15
100
100
100
0
50
100
50
100
100
1. The x axis represents the number of iterations k; the y-axis represents the value for the norm of 24 and yı in the first row, and the value for loss in the second row; the learning rate h for each column is the same.
Figure 5: Scalar factorization with || = 9, |lyol|
Then we experiment with the general matrix factorization as a supplement of our theory in Sec- tion where we only rigorously prove the balancing effect given the convergence of GD. In the following examples, we show that there indeed exist large learning rates that trigger the shrinkage of the gap between || and Y&llF and at the same time guarantee the convergence of GD. Fig- ure 8, 9, and 10 correspond to the over-parann parameterized version of matrix factorization problem (5) with e 6 (asymmetric, generated by i.i.d. Gaussian) and X, Y.Y E R 100 The initial con- ditions randomly generated with Xolle ||Yoll)) (9, 1), (I) Gooole.//oll -Yolle) (19, and
13

---

Published as a conference paper at ICLR 2022
20
20
20
20
20
20
16
16
16
12
12
12
12
12
12
8
8
8
4
0
100
50
100
50
100
100
=0.01081
-0.00927
0.00772
=0.00618
=0.00463
-0.00309
105
109
106
10
10
105
Loss
10
10
10
10
10
10
10
10.5
10.5
10.5
10:5
10
10 10
10 10
10 10
10
10 10
10" 10
10-15
10-15
10-15
10-15
10-15
10-15
50
100
100
50
100
50
100
50
100
50
100
1. The x- axis represents the number of iterations k; the y-axxs represents the value for the norm of iy and yh in the first row, and the value for loss in the second row; the learning rate h for each column is the same.
Figure 6: Scalar factorization with ||00||| 19, |vol|
100
100
100
100
100
100
| ||
80
80
80
80
80
80
60
60
60
60
60
60
40
40
40
40
40
40
20
20
0
0
0
100
100
50
0
50
100
50
100
100
à 0.00041
0.00035
0.00029
=0.00023
h
0.00012
5
Loss
105
105
105
105
105
1
10
10
10
10
10
10 5
5
10.5
10
10:
10
10-10
10-10
10-10
10-10
10-10
10-10
10
10
10
15
10
10:15
50
100
50
100
50
100
0
50
100
0
50
100
50
100
1. The x- axis represents the number of iterations k; the y y-axis represents the value for the norm of sy and yk in the first row, and the value for loss in the second row; the learning rate h for each column is the same.
Figure 7: Scalar factorization with ||æ0||| 99, |voll
(olll (|oolle) = (99, 1) respectively. Similarly, the learning rates are chosen from large to small as hog hho hog &ho, hho hg for the 1st-6th columns respectively where & (the 2nd column) is picked near the stability limit. We also similarly provide two examples of the under-parameteriized version in Figure 11 and 12. The two examples correspond to problem (5) with E 1g100x100 (asymmetric, similarly generated as the previous one) and X, Y ER 100x3 Here we use shifted loss which is to subtract the global minimum error.
As is shown Figure 8, 9, 10, 11, and 12, we can observe the similar phenomenon as the scalar case, in the sense that (1) larger learning rate gives smaller the gap between ||.X|llr and ||Y |F in the limit, except for the overly large that causes GD to diverge; (2) when the learning rate becomes sufficiently big, two-phase pattern of convergence appears, which does not manifest in traditional optimization analysis and thus indicates that the learning rate is already larger than that permitted by traditional theory, and yet still has convergence.
14

---

Published as a conference paper at ICLR 2022
More precisely, the 2nd-4th columns the large learning rate cases, where observes shrinkage of the unbalancedness and non-monotonicity of the loss at the beginning, while the right two columns corresponds to the small learning rates for which ||Xx and || barely change as & increases, and the decrease loss is monotone. These are all evidence of the consistency between the most general case of matrix factorization in Section 5 and the special cases in Section 3 and 4.
x10
10
10
Xxelle X
5
10
50
100
100
50
100
100
100
h 00.2093
0.1194
A
-0.1495
0.1196
h
000897
00.0588
10
105
103
109
10
Lowe
10
109
10
10
10
20000
10:6
10-5
10.5
10
10:5
10
10
10
10
10:10
100
10
10
10 15
10"
16
10
10
100
100
50
100
100
1. The axis represents the number of iterations k; the y y-axis represents the value for the norm of Xş and Y2 in the first row, and the value for loss in the second row; the learning rate h for each column is the same.
Figure 8: General weer-parameterized matrix factorization with X 9
||
10 153
20
20
|x,IIp >x1==
16
16
16
16
12
12
12
12
8
8
8
4
4
0
0
0
5
10
50
100
0
50
100
50
100
0
50
100
50
100
06005461
0.04684
=0.03003
=0.03123
=0.02342
=0.01561
200
10
10
10
10
10
Loss
10
10
10
10
10"
10
10.5
10.5
10
10.5
10
10-10
10:10
10-10
10"10
10:10
100
15
10:15
10
10
10:15
10
50
100
100
50
100
0
100
50
100
Figure 9: General over- weeepaaramttri matrix factorization with ||ooll = 19 |Yolf = 1. The axis represents the number of iterations k; the y- axis represents the value for the norm of X and Y& the first row, and the value for loss in the second row; the learning rate for each column the same.
A.2 MATRIX SENSING AND MATRIX COMPLETION
As demonstrated, the balancing effect is nontrivial implicit bias created by large learning rate in GD. and this was rigorously established for the problem of matrix factorization. Matrix factorization already corresponds feel balancing is an effect even more general, and thus we now demonstrate it empirically on two related additional problems, namely matrix sensing and matrix completion.
class of important problems
consider arbitrary and d; however,
15

---

Published as a conference paper at ICLR 2022
x10044
100
100
100
100
100
||.Xa IF ||ailE
80
80
80
80
80
60
60
60
60
40
40
40
40
40
20
20
20
20
20
0
0
10
50
100
0
50
100
50
100
0
50
100
50
100
h
00000204
=0.00175
00.00146
=0.00117
00000087
0.00058
10
109
103
10
10
10
Loss
109
10
10
10
10
10
10
10
10
10
10-10
10-10
10-10
10110
10:10
10
10-15
10-15
10-15
10"15
10
10
1000
2000
1000
2000
1000
2000
0
1000
2000
1000
2000
Figure 10: General weer-parameterized matrix factorization with ||Xal| 99 ||oo|=
The
axis represents the number of iterations k; the y-axis represents the value for the norm of X and in the first row, and the value for loss in the second row; the learning rate for each column is the same. Note the r-ixis range of the 1tt row is shortened to better show the changes of X lF and | = at the beginning of the iterations.
x10
10
10
Xelle Yal
10
5
2
10
50
100
100
50
100
0
100
50
100
13333
à 10.11499
=0.95524
=0.07619
=0.05714
=0.0381
200
105
105
105
10
10
10
10
10
10
10 100
10.5
10-5
10
10.5
10:5
10
10 10
10 10
10
10:10
10:10
10:10
x
x10*
x10*
x10
x10
= The Figure 11: General mnder-parameterizee matrix factorization with | 9 ||ol|==
r- axis represents the number of iterations k; the y-axis represents the value for the norm of X and Y& in the first row, and the value for loss in the second row; the learning rate for each column the same. Note the axisx range of the 1st row is shortened better show the changes of || lF and ||Y&|l at the beginning of the iterations.
In Figure 13, we consider matrix sensing corresponding to the problem
Σ (b. (A,,
min X.Y 2m
Here A, 10000100 are generated from element-wise i.i.d. Gaussian; by E R are generated from uniform distribution [0, 1];
10; X,Y E [100x6; (U,V) UU) The problem is solved via GD. Experiments in the figure correspond to learning rates chosen from large to small ho. $ ho, o ho. ho where hy (the 1st column) is picked near the stability limit. We can from the figure that matrix sensing exhibits a similar balancing effect with matrix factorization that larger learning rate leads to more balanced norms between X and Y.
16

---

Published as a conference paper at ICLR 2022
176
20
20
20
Xxel>p X=1=
16
16
16
16
16
12
12
12
12
8
8
8
2
4
0
0
5
10
50
100
0
50
100
50
100
0
50
100
50
100
0.00334
000278
0.002317
-0.01853
=000339
=0.00927
109
10
10
10
10
10000
Loss
10
100
109
109
10
10 100
1
10.5
10
10
10:5
100
10-10
10-10
10
10
10:10
10
1.5
1.5
0
1.5
x10
x10
x10
x10
x10
Figure 12: General mider-parrmeeterized matrix factorization with ||Xoll: 19 ||
The
I- axis represents the number of iterations k; the y- axiss represents the value for the norm of Xx and Y& in the first the same. Note the z-ixis range of the 1st row is shortened to better show the changes of | lF and || at the beginning of the iterations.
and the value for loss in the second row; the learning rate h for each column
In Figure 14, we consider matrix completion corresponding to the problem
min X,YeR"xd 2 PPoAA - (oo(A-xy)]1i
where A 10 is low-rank matrix with rank 2; X,Y 10x2 Pa(U) (Ug))e))
(Ea) with sparsity- 0.6 where (parse of non-zero elements) / (number of all elements). The problem solved via GD. the above mentioned figure, the learning rates are similarly chosen as the above matrix sensing example. Likewise, the decrease of learning rate results in the increase in gap between the norms of X and Y.
Both the matrix sensing and matrix completion above hold the same homogeneity property between X and Y. The "balancing effect" that we proved for matrix factorization is also observed when and only when the learning rate is large, in which case the norms of and Y become close at the convergence of GD (and yes, GD still converges even though h is large enough such that the convergence is not monotone.
We feel the techniques invented and employed this paper can extend these two cases, but that beyond the scope of this paper.
B GD CONVERGING TO PERIODIC ORBIT
Consider the objective - (1-ry)2/2 //2 Take step size h = 1.9. Then GD can converge to periodic orbits with period 2, 3 and respectively in Figure 15.
C MODIFIED EQUATION FAILS FOR LARGE LEARNING RATES
Consider the objective function f(x, v) 2/)2//2 Then the GD update is the following
Fe+l = Ft + h1( - J4
xk++1 yk++1
[2 yk
+ 1 ([V
Ub++ Uk + h(1 VLT
=
17

---

Published as a conference paper at ICLR 2022
25
25
25
X Yaal:
20
20
20
20
15
15
5
5
0
0
50
100
50
100
100
50
100
000518
h =D 00000114
0.000111
A =00000000
10
16
10
10
10
10-10
10"10
10 20
10 20
10 20
10
100
100
Figure 13: Matrix sensing. The axis represents the number of iterations k; the y axis represents the value for the norm of X3 and Y2 in the first row, and the value for loss the second row; the learning rate h for each column is the same.
20
20
20
X2I
Y=ll-
10
10
10
5-
5
5
50
50
100
100
50
100
à -0.01615
=0.01292
h -0.00000
A =0.00646
Lose
10
10
10
10
10
10
10
10
5
10
10
x10
x10
X10
x10
Figure 14: Matrix completion. The x-axis represents the number of iterations k; the y- yxiis represents the value for the norm of X₁ and Y2 in the first row, and the value for loss in the second row; the learning rate for each column is the same. Note the x z-axis range the 1st row is shortened to better show the changes of || [[&el and ||ell the beginning of the iterations.
By backward error analysis (Hairer et al.. 2006, Chapter 9), the modified equation can better approximate GD than gradient flow and is defined as follows
1 -- -
(8)
Figure 16 shows the trajectories of the 1st order modified equation of (8) and GD (7) with initial condition x = 4, y = 10 and h = 0.026. The --axis represents the time and for GD, the time point for kth step is kh. We compare the absolute values of æ and y of both methods due to the symmetry of the global minima zy = 1. As is shown the figure, even if GD almost converges to the most balanced minimizer, the solutions of modified equation are still far away from each other, as 0.1 and y R= 9. Actually, large learning rate fall outside the convergence domain of the modified equation which thus is not appropriate tool for the analysis of norm balancing.
18

---

Published as a conference paper at ICLR 2022
0
Figure 15: Three orbits of period 2, 3, and 4. The blue line are the orbits; the red line is reference line the global minima zy 1.
Absolute values x and y
modified equation x
modified equation y
GD x
GD y
0
2
10
12
Time
Figure 16: Trajectories: modified equation GD
D PROOF OF PROPOSITION 2.1
Proof of Proposition 2.1. This proposition is direct consequence of Theorem F.2 and I.3.
E OVER-PARAMETRIZED SCALAR DECOMPOSITION: STABILITY LIMIT
Consider the objective (1- 2/2y)2/2. Choose the initial condition to be xо = 20, yo = 0.07 and use GD update. The upper bound of in Theorem 3.1 is 20-06 +4 where μ 1. In Figure 17, when
25 +3++ (the left one), GD converges; however, when h is slightly larger than this bound, blows up. Hence our restriction for is very close to the stability limit.
F OVERPARAMETRIZER OBJECTIVE: LARGE LEARNING RATE
In this section, we use column vector instead of row vector for sake of better understanding, i.e., our objective function is (μ x. ///
F.I EIGENVALUES HESSIAN
Lemma F.1 (Matrix determinant lemma). Suppose an invertible matrix and u, R are column vectors. Then
det (At(AA ue (1 + A A-1a) det A.
19

---

Published as a conference paper at ICLR 2022
10000
10
loss h-0.0099009
loss h-0.01
10 100
20
10
500 1000
1500
2000
Number iterations
Number iterations
Figure 17: The loss with slightly different h near its upper bound
Theorem F.2. The eigenvalues of the Hessian of (n+ y)² / 2 are +(1 x. y) repeated times and (|>l| + Ilyll = 2( + 11yl13y2 + 4(1 y)² 8(p x y) y). Especially, at y = μu, the eigenvalues are || + |lyl2 and repeated 2n times.
Proof. Consider the objective f(x, 3) = (μ - y))/2. Its Hessian is the following
yy T
(x u 11 + yo
(x y In + xz
xx
0
(x y m)ln
y
y
(x y In
Then to calculate the eigenvalues, also need
Alza = ( (w By Lemma F.I, we have for invertible
Aha In
(n- - x 8)4n
T
T
B
Aln
x
x
det B
y
y
1
y
B
det B.
x
x
Since (n - x. In and AT, commute, have
det B det((X (μ - x [,)) (A² - (μ x 2)
By the formula for inversion of block matrix, we have for X2 - (14 - T "))² + O.
x² 2 In H- x²-(μ-0 2)2
M-x y xa (-- y)²
B B-1=
x- In
Then combining all these and by the continuity of characteristic polynomial, we obtain the following expression for all
de H) = (22 -a-xx xT)) A(x x x TaTx
+ (μ xT TTy? + 2(μ x [yyx² y).
When x TTy= μl, it becomes
det(Al2n - H) = 2m () (x To x + +yy 4)).
F.2 LOCAL NON-CONVEXITY NEAR THE GLOBAL MINIMUM
Consider the region D = {6 > x y y- px > for some 5 > O. Consider two points (zr, v], [r. ū D with x eT and t/c for c >> 0 constant.
0}. a small neighbourhood of the global minima f = y
20

---

Published as a conference paper at ICLR 2022
Then
f(z,8) + (Vf(a,y) - -2, 2, y)) (n x /)/////2222 + (μ 1--2 x) (a - 3) + + 7))
(u I /) (2-c- (2-c-l/c)( ā² "'
(1 - /)² /2 f(a.
This contradicts the definition of convexity. Therefore the objective is not locally convex.
F.3 A REVIEW OF TRADITIONAL CONVERGENCE ANALYSIS OF GD UNDER L-SMOOTHINESS
For general function f. GD is defined as follows
Øk+1 2k NV (VF()
Theorem F.3. If RNN + L- smooth, then with t, GD converges to a stationary point.
Proof. Let min f = f".
f(Ix+1) S f(xx) + (Vf(=)), ((f T4+1 - rR) + L
2 || zxll2
= -((x)) - M(1 1 (\)>)\))))>>
Then
N
[f(x))11 <
(f(xo) - f(xx))
111 41)
(f(z0) f*).
h11 1 h)
Therefore 1om IV = 0, i... GD converges to a stationary point.
L
G PROOF OF THEOREM 3.1, THEOREM 3.2, AND COROLLARY 3.3
In this section, use column vectors for r and y instead of row vectors for better understanding. Then the objective function is [ 2: y))²
The following Theorem G.I and G.2 are the main theorems of the over-parametrized scalar case. Next, for sake of convenience, let u = || l|
Theorem G.1 (Main 1). Let ug Aega Assume e 1 and un > Sp. Then GD converges to
point in (xx v) ||~|| || S h y μh except Lebesgue measure-O set of (æv, yo).
Proof. By Lemma G.7 and Lemma G. the theorem holds. Theorem G.2 (Main 2). Let h
Spt (2+c) Assume > and uz < 8p. Then GD
4
converges to point in ((x,1) v) || + |lvll < 2. y 11 except for Lebesgue measure-O set of (o).
Proof. For the measure-O set, by Lemma G.5, the set of points converging [||=||| + |1v|| 3 is measure-O; by the proof of Lemma G. I, the set of points converging to the origin is measure-O; also {ug ||= + llvll 0} is hyperplane and thus is measure-0. O. Hence the set of all the initial conditions not converging to [| + ||vll 2 y μ1} is measure-O.
Since 4 < 8p. ug 7. by Lemma G.7, it will decrease to uf s for some k. Then by Lemma G.I we have the convergence.
With the above two theorems, prove all the theorems and corollary in Section 3.
21

---

Published as a conference paper at ICLR 2022
Proof of Theorem 3.1 and Theorem 3.2. From Theorem G.1, h
for 2 1 which implies
2g He
h S 4g for all un > 8p. Similarly, for Theorem G.2, h S When u 8p,, a5+
4
4 3p when un > 8j, 4g 3p when ug < 8μ,, u5+44 3p" Also, all the limit
points are in {||==| + |lyll < }. Then we can get Theorem 3.1 and 3.2 where the second
inequality of Theorem 3.2 is because at the global minimum zTy = 1 and also || y/1 ||>|| + |ly|| 2x yryy. y.
Proof of Corollary 3.3. For [o yo a <. ||=0|12 2 + 11B8012 2 > 8p,, have
4
T Zg M/ < + | yoll² = |2ol| 2 + 11100 1 - 2x0g 1/0 >
4u 2( - 8) -h
6μ 23.
h
Also, from Theorem 3.2, || y/1²
2p S 2 2/ and --24
, 6p 25 8p. We then obtain
|| - 2 S 2 |100
yoll² + 2/s.
We will divide the proof of the two main theorems into two phases: (1) when < . yic 4 we would like to show that GD escapes to a smaller ball =f + yi S R exxepp for a measure-0 0 set; (2) once GD enters o + v < A. it will converge to the global minimum inside this region except for a measure-0 set.
G.1 PHASE 1: 2 < 3 </
We first deal with the situation where GD just converges in this region by showing that such points form a null set. This is stated in Theorem G.5.
Theorem G.3 and Corollary G.4 are the preliminary of proving Theorem G.5. Also Corollary G.4 is direct result of Theorem G.3.
Theorem G.3. Let f RNN- + RR and f E C. If the set of critical points of f is null-set, i,e.,
C(1x RN fx)( is not invertible)) O,
then ((f = for any null-set B.
Proof. Let G = [[V A 0} and G is an open set, where /V denotes the determinant of f. By implicit function theorem, we have G i (2) is a (N - -usummmandfold in C².
Consider G Cf E B} = U.EB GNf fofff(pf (2), where LIG f-! (z)) 0 from the above discussion. Hence, if B is countable, L(G' [ BJ) O.
When B is uncountable, using co-area formula from geometric measure theory, we have for any bounded open ball B,,
Jon glV Sa.l Jal (())dCx-1(x)d= J J g(z)dCx-1())d
Let g be the indicator of UsEBGn B.GBBnn n
Then since B is null-set, we have
B. / (()))BBB dxx=1
(())dxx1((2dd=
(())nGB
{
g/V
GNB,
Then g V = a.c. in Gn B,. Also, V & a.e.. Therefore, g = 0 a.e. G n B,, i.c.
C UGn gdl = 0.
#EB
22

---

Published as a conference paper at ICLR 2022
Since find sequence of bounded open ball B,, s.t., RN Up= Br, and also L(G²) 0. we have
c( S L UGnf + [(G) - ( (<UUUGnBnnF + L(G)) = 0.
=EB
r=1zER
Corollary G.4. Let 1b R2dd + Rdd be the GD iteration map, i.e, 12 v) = {xr + h(p x vvv.
h(u y)) T. Then if
[((det(De)) =0)) = 0,
then C(v (B)) for any mull-set B.
Lemma G.S. Given h wot4cp and u
t. GD will not converge to the points in {||==12 + llvll >
h x y = nb, except for measure-O set.
Proof. For d = 1,
4h22ypp det(D(b) - hx? hy² - 2h222y² 4h zyp h2p² pp( -. Pm y) 0,
where (c( y) is irreducible polynomial and pe( v) = 0 is co-dimensional-1 manifold. Then ((.,y): : del(De) = 0} U (pr y) = 0} are measure zero, i.e., L((del(D()) = 0}} = 0. Similarly for d 1, we also have [((det(Di)) 0}) 0.
From the GD iteration, we have
x7 T 2I418k+1 1 = (x1 yk - p) - (1 h([ 12 || 1) 12 yz(u 3k yk))
Then let B = {(x,)) - 1(11=112 |1,|1 h2x 7(1 - x xTy) =O}. For any (z, v) E B, let
[++, |+] 1T = (x y). Then 2+8+ μ. Similarly, L(B) = By Corollary G.4 L( (B))
and then (())-((B) = L(w .... - (B)) 0. Let af (B) = B and G = U (B). Hence
[(G) = L
U i=0
1 (B)
<
L( " (B)) 0.
1=0
Moreover, for any 0 < 6 < 14, assume 1 yk - 11| < c. When uf 2 2 + chlp + c),
h
I [1441/4+11 uk|= = | 8k 14| |1 hu x² yk (p - x yv)l
| Uk 141 (-1 + huu + 11²xT yu (u - 2 vz))
2 |oo Uh 14| 1 +
+ ch(p + +)) - 112 (1 + t)e
h
|x yk p4l.
Hence, [1|=|]2 + || > 3. x. Ty- = 14} is not the limit of this GD map vh, except for the measure-)
set G.
Next we show that GD will be bounded inside {|<=]|² + ||y|1 # Lemma G.6. Given h = top then for 0 < k < minfk: uf < } we have uf S 1/2 - 3p <
4
for all k.
Proof. First og
4cp
<
4
4f < Then if zf yo > a or x yo
<
hang 1-hug
from
h
Lemma G.8, of < u/ 4. If
< =o y/ < p. from Lemma G.9 and its proof, uz ug < 1
4-hug
and in uB # < o μ S
4
3p - Therefore, iteratively we have of < +
h
23

---

Published as a conference paper at ICLR 2022
Therefore, without loss of generality, we can just assume u < un for a fixed kth iteration that need to analyze because for every two step there exists an ith iteration such that ut I ug and we can choose k = i to do the analysis.
Lemma G.8 and G.9 describe one-step or two-step decay of u which lead to the primary result, Lemma G.7, in phase one. Moreover, the proof of Lemma G.7 contains finer characterization of uf making it possible to end phase one and enter phase two.
Lemma G.7. Given h 4o4 for 2 1, GD will enter {||-|| + llvll S 1 except for
measure-O set of initial conditions.
Proof. By Lemma G.6 and its discussion, assume without loss of generality A < u S ug. From
Lemma G.8 and G.9, the region where the decrease of up may be small is when The y/ are close to hum?
Ty Uk 1s or 2g Uk hug
Since
3 +++1 - 1 (I yh 11)(1 hug - 122x yn 2x mx)),,
consider 8k
huk 112 yz(u xx yk). From the proof of Lemma G.9, we know when h-hu Sk -1+2h2 22== < O. Therefore, there exists ó 0, s.t., for all zR. yk E { y
hym?
Ik yk
hadd -u,
< 8, T n S vg) 82 < O. Then x/4, 191+11 1 >
Hence, when -ō S x yk + I- hag
< O,
we will skip this step and consider the decrease of the next step with x 2f4, 144+1 n. Also, there
exist 3, (6) O, s.t., when 2i uk +
A hug
-Ō
- uh h(p (1 hug oo yk + huîu) < -B1.
From the proof of Lemma G.9, when - -- 2h²y,2y 2 (8- N22ug + ))} > 0, ubi2- u &max(-N(e 2 Uh ) hw -2h?22)? hh(p -xx ux 2 luuu + x1)+)))
I xx yk S for B2 max hu (-u
--
Fix an small e in < c < μ. When of ys 2 1 + c, from the proof of Lemma G.8, we have for Bg = 4hue > 0,
_ u < 4hpll Jg vk) S -4hue -33-
When 0 < z U S ş e with e > from the proof of Lemma G.9, we have for Br he?
1(2n6 + ()) > 0,
2 2
uk < -h(u -10--x110 vz ) h(u + uz++1)) S -34.
When [x yh p| < e, assume | yk pl Eu. In this case, we have sk 0 meaning GD oscillates around y μ. Also, if 0 x yk < y and ut 2. 8k
hut 122x y(1 x y) < -1, i..., if GD in 0 x y < μ, then we have | Mk++1 p I yk- pp.. Hence we only need to focus on the other side which is x yk > μ. From Lemma G.5, if ut 2 7/ - ch(u + e). |x 1 3k+1 - 14| > | yv - /4). Then within finite steps (note all these steps satisfy either one-step or two-step decrease of u²: we ignore these steps only because the decrease maybe small), we will have either { yh μi keeps increasing or u < 2 + Ekhh( + EK) (here we also consider x &Bu > p). For the former one, the decrease of U, for each step will be lower bounded away from O; for the latter one, from the discussion above, u 2 < 4hfuE + u
From Lemma G.5, we know GD will not terminate in finite steps except for measure-O set. From all the discussion above, have that uē decreases by constant for either one-step or two-step except and hence GD will enter ||=]| + |/y||² < 3 except for measure-0 set.
24

---

Published as a conference paper at ICLR 2022
Lemma G.8. Given
and us < 4, when o. ys > fe or x. yk <
we have
- oB <
Proof.
u u// = h(p - 2k ((4 hug) yk + hugu) = h(p - 21 uk (4 + hu 2/ vn)) =(ub))
If 2y yk > μ. by v < t.
uk
2
uk
h1p mg uk (4xb yu + hug(u D3. 2b Ux)) S 4hp( 2x Mh) < O.
If 2g Uk <
hun
+ z yk < p. then,
1- hug
1h+1 u = hluu 2g (x4 - hu uk + +hggH) < O.
Lemma G.9. Given h 444 Eg Uk < ,4 then u u Ux < O.
c > m 2h1 > O, and u S uy. when
haau S
4-hug
Proof. For every up. there exist a constant Ck > 0, s.t.
4 titis
Since 2 < uz S up < A. we
have c c Ck < 2hy Since
(Ir yk (1( - hug n² vb - z yk)) = (2 Uk - 1
1k+1lk+1
hung then 8 = hug x1 (1 2hf yk) bounded by the value at xt yk h-hug i.e.
or 2/ yk = p.
8k =1 11 11--ee huk 11²xxx vu(p - x uk) S max { hu? + (4 hu?)
4h²u 22
1 - hug
Since w > 3. we have 1 - -nu < 1. For the other one, since w > n and C₁ < 2hp
2
1 1- huk + 4h²u (1 (1-3c))ut + 4c# < -1 + 2h²²
(4 huf)² Qu(u + 4c*2)
hy+ /2-
where
This is because either un 8p + hp < 3p or S 3p and then
211 211-
Ayet 22-
< S c. Also note here this is c not c₁; this value -1 -1+ + 2h²2² is achieved when
21 112)))
hyt /2 or Zhp 2111
" = 2/h and ck
Also, when 0 S #1 Uk < 1b,
8k = 1
hug n²x yn - 2t uks) S -hu < -1
We then prove hn? > 0. When xx 4k < u.
2 uh 11(1 - 2h (x hug))zz us + +hagu).
The maximum is achieved at x/ 4k when e > 1/2.
2-hu² I-hut u1 i.e., uā+1 - w s a < H. Hence 4 - hugg+ > 0
c
Since x 8k < μ and 8 S 0,
2k uº u² u + 2 th
2
hllp IT_ 1 () (4-
huu )x1 Mk+1 + h224
+ h14 - 2t yk) yx)
(4- - -hu oo yk - huā
hh(f - IT ITTTI ((( - -hu2) + hru + su (hw (her
14 + (4 hu h y2 (1) + +x])
=
11( - I (2 yx(4 houft + S - huz 4 yk (1) hug sh + (4 - h))4
25

---

Published as a conference paper at ICLR 2022
When 0 S 2 yk < p. -1, then
uk42 u - -h(u Ih yx) -8 12+1)) < <0
When hami 1-hug < Eg 1/4 0, 5% 2 0, then for c 2 2h14.
uktt - u < h(p - _ı ) - ++ huy + 8h² μ - (4 hu -1 22)22
< < x yk p4(4 hu h1 (1 1 2h 22) <
where this bound is achieved by taking sn -1 + 21²2 and o u/ O.
G.2 PHASE 2: u S A
In this part, we will show the convergence of GD in Lemma G.II.
There are two convergence patterns: (i) transversal convergence, i.e., oscillating around the valley; (ii) unilateral convergence, i.e., converging from one side of the valley.
yx: The key point of the proof of pattern (i) is to analyze the change of 8 1 huf y 2y yk)- We know 2
P sk (2 V/ 14), i.., St measures the change of the loss. If for some constant K > 0 we have [sy| < Ak 2 K such that | yk - pul is guaranteed decrease O, then the convergence follows. Moreover, we will need to analyze $22 and $2k+1 separately because in this case 8 < 0 and 2 yk a changes sign each step.
Mk++1 1
For pattern (ii), we will show that the trajectory of GD is bounded in subset of this region |sk| < that guarantees the decrease of the loss.
Before presenting our main result in phase 2, we first show a boundedness theorem when GD enters this phase.
Lemma G.10. Once GD enters [|a=]|² + |1yl S R. it will stay bounded inside [| + |lvll <
+ 24} and re-enter {||==|] + ||vll < } within finite steps where the number of such steps do not
depend on the number of ileration.
Proof. If at step K, u S h. then from Lemma G.15, 2 S 7/ + μ and it returns to phase 1. From the proof of Lemma G.9, = 2 S u + 4 < 2 + 2p and we know either u²x+2 < u or wK+3 + < + and until it re-enters ui S h for some > K. Therefore, all the u < h + 2/
2
once GD enters {||==| + llyl < J.
Then by Lemma G. we can always pick a kth iteration such that uz < 2 Also, when un 8/c, we have hp < 3. Together with the choice of h [2+c]μ when 0 < up S 8p, we have hys S 3 Then we obtain the following convergence of GD inside phase 2.
Lemma G.11. Given hp S 1 if GD enters [||=|| + 1| < 2. it converge to xT y = y inside this 3, region except for measure-O) set of initial conditions.
Proof. First, from Corollary G.4, we know the set of points converging to (0, in finite steps is measure O. For all the other points, we have the following discussion.
8y = 0, then Tf +++++++11111 = 14, i.e., it converges.
If a yk < 1 and :/ + 22 < v < 2. then by Lemma G.14,
wh _ = h(μ - _ yk ((4 (4- huu J yk + huf, S 2h(p2² (I yk 0.
Hence for 6, > O, when - - 6, < N yk < -4, we have I uk+1 > μ and we will skip this step and directly consider the (k+1))t iteration; when 2 yk S - u - < - 2h 22 (1++-, - Namely when xrI yı < -4,, either uZ+1 is some constant away from uf or we can ignore the decrease in this step and directly look at the next one with If 1++++ > p.
26

---

Published as a conference paper at ICLR 2022
If 22 Uk < 1 and u - 2h4x, then
" " - u = h(p zx uo) us + huī - 2/ Uk))
< h(p z vx)) ys + (1+ 2h² (atpx²)en vk))
S -4hy 21h 12)) <.
If og Uk 3/4, then u2+1 u - 27(n²² - =g < -16hp?. Also, when ut - 6p, Fx yk I 3/.
Next, for the rest of the region, we first consider 1/2 + 2h42² < u S 2/2 (by Lemma G.10, we are always able to find u < ). In this region, by Lemma G.18, we know Sp- < 0, i.e, (x yk (z 1o++1 μ)) < O. We divide the whole region into two parts: 2 yv > μ and I yk p. Therefore all the 22 should be on the same side for such that A 2hp²² u S n
If - S Ty U/ < and 8 < -1, by Lemma G.16, we have w - xx < - 4h((1 - h
2y yx < 0. Hence when GD does not converge, i.c., {< vk 1 does not converge u will keep decreasing with u +2 S 1/8 for all K +2 with i 2 0 such that 52421 S 1. Moreover, there exists N > 0s.t. SK+2N > 1 because 8% = 1 -h - >12 3h (u- "Iysk uk) and if 22+ yk is the first iteration to leave this region, then it has to satisfy 22 - which implies S4-2: -1, and then it follows from Lemma G.13 and 12 just as the following two paragraphs of discussion; if it never leaves this region and GD is not converging, i.e., 1 1 Fg yv has lower bound, then u will keep decreasing until 8 > -1 (from the proof of Lemma G.12, if f z ys is very small, then 86+11 < 8% meaning both sides are blowing up and therefore | - 2g yks has a lower bound 8k S -1).
If - S S < f and 8; > -1, from Lemma G.12 and Lemma G.13, similar to the previous
discussion, there exists N1 > 0, s.t., for all k > N1, $t > min + co, -1 + c2(# xx )2 for some co. > O, namely |и z4 yk strictly decreases. Then it will either converge in 1, + 2hp² <
|| + ||y|| < & or enter ||x:| + |lvll2 - + 2hpp²
u < o.. yk S 3/1, from the definition of sk. we have 8 > -1. Also by Lemma G.13, we know sn min { 1 + co. -1 -1+ + ei (μ y } for all m > k. Hence similarly, it will either converge
or enter u S 1o4 + 2hp².
Then we consider u < h. + 2hp²². From Lemma G.17 and Lemma G.20, we know |sy| < 1 and will be away from by a constant in this area. We will show that GD stays bounded in the converging domain. If sk < 0, it follows from the previous discussion and the proof of Lemma 1.17
and Lemma G.20. If sq > 0, when the trajectory is in {|= y) > 14), from Lemma 14, we have
- < u when it is in {|x=" y/ < ju), then | 1/++1| < |2 y& from Lemma G.19. Hence
the trajectory will stay inside the monotone decreasing region. Next, since | 2x yk monotonically decreases and is lower bounded by 0, we have that |/4 x ykl converges. If | x ykl converges to
C' > 0, then minf-1 + co. -1 + (μ- x )² < S 1 C2 for some co. C1 C2 0 meaning
|p x T
ykl does not converges C. Contradiction. Therefore, || 2y yk converges to 0.
Lemma G.12. When -M < I 2k < μ and t. 2h42² ux <
2/2 + 24, if 32 > -1, then
8642 > min( k²
2 5h p -1 + h2 xx uk) > - 1, for 22² < 1.
Proof. From previous statement, Sy < 0 when ut > h + 2hp2² For sk hu? -12xx ya(H
2 yx), let E = f - N yk- Then xf 1 1 = -KKE.
Sk+1 = 1 hu h²2 1² 1 (1 2x (++18k+1) = Sk - 11² h2²ep(3 + sx) + 11 11222 + 2 haut)
Hence if is very small, we have 8841 5k. Also, Tb429142 1 Sk+ ( 1u) -8641866 Moreover, u2+1 3 + 2p by Lemma G.6.
27

---

Published as a conference paper at ICLR 2022
8k42 = 1 hugzz 122x 2 212-
Sk 13 + 4sk +
huj +
+ 2 s
hu 11))
2 8k 12 + 48k + (1
S4+1 (2
1²2p
13c + 48k) + +1 + st)
8k 4
3 + 48 2 0, then
h²2p2
h
122 n²a(33 + 48k) + 1122 + +
Sk+2 2 8k
4
==+ 18s ((2(+0)))
1²
h² 1² + 4sk)
8k
4
4(1 + 2t)
86 = or 3/-
3
h² h²p²
5h² 2
2
min
-1.
4
4
2
If + 48k <0, <., -1 < -1< 8/ <
3 then
1'
8k+2 = 8/ - ei:equl3 + 48 + 81* + 1:2 + a hug + +,/(3 + 2 - -1)
= 5k - 12eep(3 + 43; + -
+ 5k) + 1²22 + s² - -hug)))
- 11) 8k - (+) p pc² s + 2/ - hhug)
+ -u
+ -
+ 2 +
hw + +1²p²²
su (3 + sx)).
When
-1 < 8g < 1-3hiem
1-6h2 2 heeu 83 (s + 8k) +3+ 8x) > -1. Since 6 S 2/s, we have
1-3h2ep Kde
2
2h² 2 - 3 for h 12 < 1. Also,
4
3 h12 μt > 0,
h1² ue sk sy + tt hul) >
4
h² 2 + 2 huk + s/ + kk+
2
h + h² 22222 (3++ sx)) > hie > 0.
Hence
8k42 -1 - 112 -1'uee
3 (3 + st - hmu
+ + (3 + Sh hu? + 2 + s h2k+1) + +h²
22222s/33 > -1 -1+112 h
Lemma G.13. When 2 yk > μ and + 2hp2² < u1 <
N + 2p. sk > - 1, then 8k+1 > 8/ and
8k+2 > min(-1- + h²2 (p I 22( 2²²²²) - (p - nx yk 12 222 L. for 8h2 2. 1.
Moreover, if uh < 2. 8k I 1, and 8k+1 > -1, then 5k42 > 8k + 112 - xI v. - sh² 22²)
Proof. From previous statement, 8k < 0 when of > 1 + 2hp22. Without loss of generality, we can
just assume ul < 3 (otherwise u2+2 < 3 and we can use this as our starting point). For x yk > p.
h
S% = huy - h2 k (k(u x (k). Let or yk - = c. Then
8k+1 = hun 122
2 1++1 = 8k + cp + sk) +k) +h? + st - -hug) > 8k:
where 8k > -3 in this region. Also, x 2 - 1 8k+15KE.
Then for 8y < -1, ub+1 S R.- and $ > -1,
Sk-2 = S% + hh2ep(3 (3 + 4s + sk5k+1) 1 + 22222 + 2/ - hut + +2 1 - -hu 1))
= 8t - 112ep(3 + 48 + + 2 + 1=22 + 22 hu - -1h2eu - 122 (2esu8841)
+ x hhu 1) + 21 + ( - 122 24 + 11+1) +s)]
> 8/ 2²2 2h²
28

---

Published as a conference paper at ICLR 2022
where the inequality is achieved by 8k+1 -1, f S n. u22t I 8h²22 < <1,c sp.
For 8% > -1
hn 8k+2 8h 1/pEpp(3 + 4sk + + x -
{p)
+ + -
> 5k + 45 + 12 s/ st]]
h2
5k + 1
4s + 28 + sk)
When 8/ > -1, we have + - -
h² 12
4 + sg) > 0. Since
48k
- 8h 8h²p² 22 < 1, 2 +
for -1 8k S
1 For <
2.
8k S 0, 2 +
+ (.) 2 + 82) 2 h2pp > 2
Hence
86+2 > min - 11²)) 1
Lemma G.14. Given u S t. when 12%1 vol μs, 26-1 uz O.
Proof.
u - u h(u 2g 2x (4x yu + hu? (1
3h y1 hL4 2 uk )zx yk + h2 un x 1/:) )
S hlu 2I 1k)))444 yk + 21( zx7 3x
2h(2² (I un) <0
Lemma G.15, Given u < To ub u S. n.
Proof.
4hp²
uh h(p xx yk) (4rr 8k + huū xx bk)) s
ub+1
heu
2-hu2 4-hu Jr. When h
where the maximum is achieved 2 Uk
u ustdeu from the proof of
Lemma G.9, ug+1 un S μ. When h (2+0]a and in this case ut s 2 (1 {u), uk+1 of S
7(2+o / <
Lemma G.16. When -u -u xo Uk < <u, if88 = lug 11a. yk (u uI vh) S 11, u2 - u S
-h(4 4hp)(u 2 y2)² < 0.
Proof.
T ub+2 uh h1p xx yk (((4 hu yk + hug shhn (4
yh -1) ()))
ub hul 1 yx) (-(4 huk + 52(4 hug () yk) + 4(1 s)
S (B - huu + 1) - x y2
S (4(4 4hp)) Ix yn)² ) < 0
where the first inequality is because when sk 1 has the maximum value; the second is from Lemma 10
Lemma G.17. When u 32 then 8k < 1 and will be away from I by a constant.
29

---

Published as a conference paper at ICLR 2022
Proof.
122 2
ur +
huk x1 yx(u 2x Ub) S
heg
8k
2
2
where the equality is achieved when oi yk
-
Since 0 o z h
8k S hug
h22
u 2
14
" 2
max < 1.
Actually this 9p will be away from by a constant. This is because when un are close O, 9k will be close I; however, u will be increasing because of the decrease of | I vul and thus 8 will decrease accordingly.
Lemma G.18. When u > T + 21y2 and -u 2h yn 3u, (F (1 ya 14) meaning oscillates around x:' y pb.
Proof.
1 - --hu - - yk(H Ix uu) < 1 -,l + 2hp22) + 2h²p2 = -0
Lemma G.19. When -p S 2 yk < p and hu S 3. we have |14411 Uk+1l lark - ykl-
Proof.
[kk+1 - yk+ 120k - ykl 11 h( 2x 1k))
Since hy 1, then
-1 -1<1- 1-2pp < hl xb yk)
Lemma G.20. When uh S + 2hy2² and hp S 5. 8k 2 -
Proof. By hu 3.
1:2p2
9h2pp
1
1222 (u(u Ih vn) huk
-2h2 12
>
2
4
H PROOF OF THEOREM 4.1, THEOREM 4.2, AND THEOREM 4.3
The proof in this section mainly follows the strategy of the scalar case. More precisely, all the expressions, e.g., u and T 14441 μ4, in this rank-1 approximation case contains two parts: the one that can be handled using the technique in scalar case, and the other one measuring the extent of alignment between and ye. Again, let ui | I
Theorem H.1 (Main 1). Let h
uo+4 Assume e /7 and u > 4VTp, Then GD converges to a point ((x,y) y) : || + ||vl|2 h. x = μ} except for Lebesgue measure-O set of (x):30).
Proof. The proof follows from Lemma H.3 and Lemma H.8.
30

---

Published as a conference paper at ICLR 2022
Theorem H.2 (Main 2). Let h 4yTu+Aou (v7+c)u" Assume v7 and ub 4v7p.. Then
GD converges a point in {(r,y) ||=|| + l1all s set of (No. yo).
2 n. x y ju} except for Lebesgue measure-0
Proof. Since c 2 V7, in this case we have op < 4V7H & 2(V7 + c)ı = K² Therefore, the convergence follows from Lemma H.8.
Hence we can show the proof of the theorems in Section 4.
Proof of Theorem 4.1. By Lemma H.3 and H.7, the proof follows from Lemma H.9.
Proof of Theorem 4.2 and 4.3. Similar to scalar case, h ag+4cp for 2 7 implies h ug+4v77
and h (VF+c)j implies 2V7 Therefore, the convergence and balancing of GD follow from
Theorem H.1 and H.2. The second inequality of Theorem 4.3 follows from x = ju at the global
minimum because of diagonal and non-negative A and the best rank-1 approximation in SVD. O
H.1 PHASE
The main theorem in phase 1 is the following. Lemma H.3. Given h
ug u5+4ep for c 2 VT, GD will enter {|<=1|] + ||vll s 7t) except for
measure-O set of initial conditions.
Since the expressions, 2 ur and ux - u.. of the lank-1 version have additional term upper bounded by co (xx yx)² z JRSI yk) for some constant co >> 0 which non-posinn non-positive, we have u decreases by constant for either one- two-step if (Ir - fe yk < -c1 for some constant 01 >> 0 when < o < 4. Therefore,
Proof.
can pick K >> S.t. (1 yx)² x uwu y -C1 for k < K. If GD enters [||=]|2 + | < } within K steps, then we are done. Otherwise, we can just assume that for all the k > K, -c I (2tg yx)²
x1 I I 0. Then again, like the scalar case, we only need to consider when 2k, yk are close to N
kyme
and æ yk = 4- kug
hum? For the region near F Uk 4-hug we can always choose s.t. there exists a 6 > 0, when
huu? < 0, we have both of Uk+1 > and 8 < 0. Then all the discussion just -5 v o + 4-hot follows the scalar case. For the region near x yk = i.c., | yk ul < for some 0 < consider
++1 - p (x] W/s 1)8kk 1 3 -x yk ((x) yx) 2 2x Jzli yk).
Similar scalar decomposition, only need consider the case when s S - because if s -1 which can only happen when z > μ. we have u² S 7 + chh( + c) and then uZ - h 88 2 -1 for all the following iterations, together with the bounded second term in 1 J4, i.., 2hh uc; (2 2 vx) yx) z1 Z&yE yk) S
2
have that there exists K s.t. k n| 2 é for some >> unless it leaves this region |z y μll < Therefore, by the same discussion in scalar case, u will decrease either in one step or two steps by at least a constant.
Moreover, by Lemma H.4, GD will not terminate inside (
||
llvl
{] in finite step.
Thus, GD is guaranteed to enter [||=|| + ||v|l < ) in finite steps.
Lemma H.4. GD will not converge to any fixed points in {||x| 2 ||w/1 > R. except for a measure-0 set.
Proof. Similar to the discussion in scalar case, the set of points converging to x Ty = 1 in finite step measure-0.
31

---

Published as a conference paper at ICLR 2022
Also, since pa y =xxxy" y 2², the fixed points of GD map requires x ''xy" y (x y)). This can be seen in the following expression
#k+18k+1 = ( yk - p) - hug h²² 2 yk - 2 v=))
-1 uk) vh) yx)² xx aank ub).
where the convergence of k μ requires the convergence of x J&VK yk (x ux)²
Hence if 17 " y (1 )² does not converge, then GD will not converge. If 2 yke (x) yx)² converges, then 2 Z4yk yk (x yx)² 2 0 for all the rest of the iterations with some
0, and we further assume | yk pu| for any 0 < μ. As is shown in scalar case, when 2
Mi 2 h + eh(ju + <), we have 8p 1 - hug x yvu (11 k& yk -1 Then
II 13++1 μ (a yk pt + h² (2 2 yk ( (1 yk) 2 24Vi 94)
will never converge (hecause 8/ S -1 and the second term is bounded).
Lemma H.5. When of yk > j or 2g Uk
hund a-hug we have u - uf. < 0.
Proof.
2 "1+1 Uk = h(p nu (14 - hu
yk + hugu) + h(4 ((x yb)²
xx A& yk)
S h(p n yk ((4 hu yk hugu).
Hence the proof follows ID case.
Lemma H.6. When
haug a-huz
S x yk < 11, we have u uZ u < O.
Proof. Let 8h
hug x yr yx(u Fig yk), the same ID.
Tk41 1 = (I 4k 11 hun =2² ux( - 2I + 1222 x ux) (xTT))) yx)2 - x awgl yk)
(I 8k
s)sk + M.
uk+2 - uh =
2
2 u uh + u u
h(u 2 yk ((4 huu x yu huguu + h(4 hug) (12 v= Ig AzUI yk)
-bl - 1/: ((4 + +
hu
+ +h44 - hut ) ((x k 1/ 14
In( - 2T ()))((( ho Us + huzu) + (hu (4 hu? (sn( - -2 + w)))
=
+ [b(4 - hut) yx)² 2x ax vk) ( huū
(-M(-uu + (-4 + 2 ) + 2(4 hou 2% yk v1)ss))
1
I is the same as 1D u²+2 oi and hence (1) < O. For II,
II hM² + huk 1) + 1((( yx.) 2 x.VA W1) x (4 - hu² + 1/2 22 21 ya) (-hu (-4 + ho 2(4 hhu x 21 )sk))
III
From 1D results, < 0. Then, III achieves its lower bound at ar. uu or 2rj yn.
hpmy huz
For
K yk 14
II| 4 hag 24--4h2224 4h²y2²
4hplc- h40 > 0,
32

---

Published as a conference paper at ICLR 2022
where the inequality is from u S ug A - 4cp and hys
For o yk
4- Aung
III 4-hnk 482 heu (4- hug 28h (4 hug 1)
(4 - huuf)
482 hu (4 -hu - 28k (4 )2
2 4 huk
(4 hvw )2
4h² hu (1- )
4 hun
hug
5u0
4h2 (4 + 4ch 2
2 4 huk
4ch4u
" uu 4hp
2 c
(-1 + e² 2sk + cch-c1 11 + 25x)
1:2113 - 7 11211²
(1 + 8h2² ) + =chp
2
2
0,
where * follows from
8% 1 hug
11²xxh T yk (1= I mk)
vb)
2 v2=122
h2p²² p2
1- 1-hug
4
-3 + 4ch 12pu2 2₂
and follows from c 2 V7. From ID discussion, -4 + hu 0. Also, (z) yk)² 21 Sx2l yk 0. Hence we have (3) 2 0. Overall, (2) S 0 and therefore the whole discussion of (1) is the same as ID.
H.2 PHASE 2
The proof in phase 2 is partly different from the scalar case due to the alignment. Before presenting the main convergence lemma, first state the boundedness of GD in the following lemma.
Lemma H.7. Once GD enters [|/=|12 + ||,/| s }. will stay bounded inside {||xr]|2 llyll2 s
+ 21p2(1 + -= and re-enter f||=:||² + llvil? < R} within finite steps where the number of such steps do not depend on the number of iteration.
Proof. Assume un s 7. Then
u 2+11 U = h(p I 3k ((4 - hat)) yk + huRu) + h(4 ((x) yu)² - 1x A yk
< 2h(μ² I IN yx) S 2h4²2
where the first inequality follows from U < R. If further uht1 2 + 2hp2, then by 2 1 2
V [ Fb+110 11 1 and + 122 0. we have
" 2 - ubtt1 = h0pp - - uk+ ) ((4 hu ) 10++1 + h212+114
+ h(( hu? + ( (1) T
I I Ih+ 1
< 2h II 1 1
112 //2,,² + n1² (1
12 (2²x2)
+ p² 32 + T 1k 222 + h2 212)
2h 11
2hμ²
33

---

Published as a conference paper at ICLR 2022
The first inequality is from 2 S A + 2hp2; the second inequality follows from the two conditions mentioned above; the third inequality follows from choosing v FK+1 1K11 11++10++11
1-
From previous proof, we know when u > k. by Lemma H.3, we have GD will enter {11zo]] Ilyl S } in finite steps with the decrease of ug in either one step or two steps. Then, up S A 2hp + 1-bh
for all i 2 k.
Let Ux 2x 2TyYK yku Vx TKi Wi = Vie yk- Then we can rewrite the iteration for the three variables
{
Uk+1 1111 hV%) + h1 1W)) + (1 VV h(VE Wk) + 12 VI+1 2hpUk + Vx- 2hV + (2 W + +VW22) WK+1 = 2hjUUx + We - 2hV.W + (12 - V + V2WA)
(10)
When h = 1 Nop or h = 1_ we have hu S 2/7
1 The following is the main lemma in phase 2.
22/p''
Lemma H.8. Given hp S - if GD enters || + llul s k.,, it converges to xTy = ||ا||| llyl =
i.e., the global minimum, inside this region except for a measure-O set of initial conditions.
Proof. This proof follows the same method as the scalar decomposition. We need to prove that all the conclusions in scalar case also holds in this rank one decomposition.
Consider u 2 u when o yk < -11 or F yk >
" 1 u = 11 Ib Uk ((4 huz) + hng (1) + h(4 - ( uk)² xI NAVE yn)
= 11( In ((4 hu yk + hugu + h(4 hu - V&W+)
I h(p IN. (w4 hug) yk hug
where the last expression is the same as scalar case and therefore under the conditions such that Mk+1 oI < 0 in scalar case, we also have uit u < 0 in rank-one approximation.
As in scalar case, we also denote 8% = hug 112 x²xx yk (u u < 2 extra terms of u2 - u compared to scalar case is
=x yx)- First consider 1 + 2hp² <
h. p S के yv < μ. ub+1 2 uh. and s S 1, consider u2z42 uz. From Lemma H.6, the
2 hu + ha( [z] yx) x L&bi 3k)
x (4 hu? + h² (2p It yu) (-hwū + + (-4 huk+ 2(4 -huht ) 2 yk yx)sk))
III
where M h² 12 of ux (I yx)² - 2x TRSI yx). Then we will prove that III positive and then all the extra terms will be less than O. By rewriting III in terms of xi yk. we get
III 2(xI )
21225, sx huk+1) + uI u 1 Gh (0 hhu 122-4 + hu
2h + 112 + 4h2 s4 4-44444-1 huy ))² + 2h²(-4 huk )²² +4 hui
> 4 huy + 12) (-1 4su) 12h 84 wh+
2 hut + 12h²2-11 4s 12h3 s4 122
hug + 12): sx(4 - -hu > 0,
where the first inequality is because it obtains the minimum at a. yk: - the second inequality 2. follows from u 2 ug; the last inequality is from the range of ui and sy. Therefore the extra terms of u²z42 ugg is always negative and then we have the same conclusion as scalar case, i.e., u? uht2 un -C( Ji )2 for some constant C > 0.
34

---

Published as a conference paper at ICLR 2022
Next, consider sk+1 when -p S z U I 3p and h + 2h42² u S 2/z which implies -1 h²p² Sk < O. The extra terms of Sx+1 compared to scalar case is
$4- S
(U? - V&W&)) (- hufe) + (-2x kx yh + (2h) (2 Ub - 1) + 12 + h-t x 24 Ux - 2p1)
IV
where U2 - V& S 0. Then consider the upper bound of IV
IV = -4 - 2 yk) 2 122ss
+ 2
yx yk (-hh 4 6h² sp) s4) + huz + 2h²22² - s
S -4 + 1 2 + 1-1²² - 41²²*x) < O,
where the first inequality follows from 2 y S 3p. Therefore the extra terms non-negative, namely all the lower bound for Sx+1 in the scalar case also holds for rank-one approximation.
Also we need to consider 8k42 when 8k > 1, -u S o S 3/,, and + 211²² < uh s x.- For
scalar case, from Lemma G.13 with c = #4+1 Uk++1 - 14, we have
8k+2 = sk+1 + (h2 k+1) 1) h13s h²² 2 + h2 3p Sk+1
= =3/2 + 82 x1 - 112 uuee 3h² e/ + 84+ 1 - le?e
Since the minimum point w.r.t 88+1 is ((--)euu) < -1 - hap² 2h
1 we have if 88+1 is larger, then 8k-2
also larger. Given the same value for sk for both scalar and rank-one cases, 8 larger from the above discussion and thus 8&42 is also larger, namely, the lower bound for 8842 also holds in rank-one cases.
Next consider ui < 2h12² where |sxl < 1 and we need the iteration to have certain restriction such that it will be bounded in region. If sk < 0, then it follows the same from the above discussion. If 8k: > and o yk > l or Tig yı -μ,, then by ub+t1 u < 0, it will stay in {z Uh > 14, u I 1 + 2hp²) until convergence. If sy > and -p S 2g yk < μs, similar to sealar case, we consider | F4 3/ ynl = VVx Wel and
Ve+1 Wk+1 = VV- W1 - 11 - APVAW + 2h 2h - 122
where Up = xr uk and U2 < Vi k. Then
1 - 1.VVWWa + 21: Un - 1/ < 122g + 21: 122 <1,
1 - WVV + 2h2 - 1222² 2 1 h2 _
1 2h² - 12pp 2 1- 11 2h2 212222?2 - -hh2p² 0.
4
Therefore if -u S z yh < and
uf
< 1 + 2hp2, we have |K4+1 Wh+1l < IV/ Wxl
meaning together with μ x 0k+1 convergence region.
P x yr Ta-1 and yk441 is bounded in the monotone
So far we retrieve all the conditions for convergence. Therefore, from the proof of the convergence in scalar case, we have that there exists constant K 0, s.t. |sk| 1 and 0 24x 26. yk < 2p for all k > K. Then let S₃ h2 h222 2 yk) and we have
144196+11 14 (x. yk - (1) - hu? 122 x. yk (1s xx yk
+ h2 12222pp - - v1) y2)2 InT JAVR yk)
[x] Uh 1)s8 + S2 - V2W+)
In fact 2iI yk - 1 - 0 as k + 0. First, since SU v&W&) - as + by Lemma H.9 and |sx| < 1, we have 2 8k - p is bounded. Also, from previous discussion, |su| < max Maxx(C2,1 C1 yh 1)²3 for some constant C22 C3 0. For any eo > O. there exists K₁ 0 and el < eo such that (U? V&WW)) < é for all k > K₁ and C2
Czef. Therefore 2. y/ / will
35

---

Published as a conference paper at ICLR 2022
decreases to O(1)). This is because
M1 S (1 Cac yu - n1) + 2 R1 - -VR, WK (1)
5 (x UK1 1)[(1 -
([(l1-)af]) C3e k-Ki
k
+ (VK, WK. UK) Σ
C
2li-kKi
-1-
Ki
$ k2 UK, - 10[(1 C3c
2h U(V, WK, UK ( K
where C4 max 1- - Cz < 1 and we have kCt + 0 as h + 00. Therefore there exists K2 2 K1 s.t. Tk,WKs- - F = O(e)). Then we will show for all k > K2, | u/ ul < 60- As is
shown before there exists K3 > K2 and E2 & 61 s.t. [Sx(U? - V/ < 62. Since |syl < 1, the increase of | yv - 1| is also ((e1) and thus |2g Uv 1 = ((1)) Eg for K2. Then we have the convergence [ yk ul +
In general, we have 2 yk + and cos (0s( + O, which implies GD converges to the global minimum x | ||
μ.
For the proof of alignment, we only need to consider when |xx1| +1yx S 7/ 2hp22211 + 1- Also, we have V& U2 and
Va+1 Wk+1 - 1 = (V&Wa, - U2) h(V + Wh) + WV - 11)1)2
Thus we denote 4e V We U2.
1(V2 Wx) + WV&VW n²) which characterizes the change of
Lemma H.9. If [ 2 yk 1 $ 2 2hp2 (1 (1+ + 1 then V&W Uă converges to 0 and
also cos(L(Ix: y1) converges to
Proof. By 0 S V. < ( W )2 and the boundedness theorem, we have
2 2hp + 1 122p²
V/2 W4 - h
and
2
1 = 1 N(V2. + W&) + +V 2 -1
(11)
1- 1-22
122 4 = 1 1(V + Wv) + +VVWW 13) - (V, - W2) -1VV - Wa) + +1 11122 -12p2
h1-h2p² 1
We will show that there exists > 0 and a constant C > only depending on hp, s.t. when k K.
V < 1 C.
If V2 + WR
< 2 14,2, then
K
4.
h(V2 + + -1) +2)>~11- WV -1.
(If V.W, = O. then V. - U2 = meaning it just converge.)
Therefore when V42 + W₁ 2 -hp², we have [/2 < 1. We only need to consider 4441 when
hy2 s Vv We 3 + 2hy x) Next replace lR Ve, We. Up by 1, V. W. U for
36

---

Published as a conference paper at ICLR 2022
simplicity.
1++1 = 1 h + Wx+1) + (Vi++ - -12)
- = 1 - h(V4+1 + W + W U1++1) + +12 - -22)
= 1 - h(V+++1 + WR+1) + +VW - 11 -12)
(0) 1+
-
+ ( + +W)
2hh (1+((((((+ -V) - +2(++++222)(1111-+2-11+"+)) 12x2)) (12)
If 2 p2 we have
= MM U22)
(F +W)
+ -2 - +22(1 21) -1 -11-
2
1- ())(((++))))))++)++) + 2h2p2) 11-1111-1111111 h22²21)
2 1 - 12 + () 10/))²)/8)
1
2 -44 4-h22²² 22 - 12 + ph + 1- h22z (9M
> 11,,
where the first inequality is because all the removed terms are positive when 3: - hy2 V <
3. + 2h2hh2211 + T- ); the second incquality follows from recollecting and take / from quadratic formula with the hV + W) taken the bound, and U >>> V+W, the third inequality follows from the bounds of (V + W) and I; the last inequality is from hy S 2/7
If < ph2 2 + 1 n²22 < By rewriting 4+1 in the following way 1x11 = 1+ h² - N(V + W) + (V + w) 4h 4h4 (1( + 2 - N(V + W) 2/ /²²) - 2(-1+1 12 2122
+ 13 h(V + W1 + 4h²"
we have that the minimum of 1++1 1 is achieved when U = +VVW. Thus we will consider two cases:
U 2 0 and U < O. Note we always have U² < VW (otherwise VW - U = 0 just converges) and hence 44+11 is larger than the corresponding value at U = +VVW. Let q = h|U,, = h41, 9 = cV for e 2 0. Then we have
g² = S - WW) x² <1, iee, c< 1
(13)
v.
Next, let
Yet1 = 1k41
(V (W))-
- < 2441 - 1211 + + - -t9).
First let U 2 and = hU < hvVW.. Choose g = hU = WV Then by
h(V + W) = 1-11 112 (VW - -n²) -1 -1-+
we have the minimum value of |++1 when /²0
4+1 2 1,41 = 1:/11=1110
(-+ ([++=+++0((((1111)+++++++++++++1
(14)
- ((11 + c) + +c² - -21+2cl)
+ (-1 (-1 00
1) When -1 <l< <11l== p4h2p² and
1, we have 4411 1/411 1 4.
37

---

Published as a conference paper at ICLR 2022
2) When -1 <k<<< < =4h²p²² and 1, the derivative of (14) with respect to is
d de 1/1 = (1 - 1)112 + (-2 - 12)² + 20 6lv 4n + 3r. 2 21v 4x
d
+ +46 + + 20 +1+ 12) 20 + 6lv + 66²),
which is a third order polynominal with negative coefficient of the highest degree term and has de k= = 21 + 1) > 0. Therefore, when 1 < c < 1 422 either increases or first increases then decreases, namely, the minimum of (41 is achieved at c = 1 or
root in [o, 1]. Also, when c = 1, d
c= 1. If c 1, by the previous discussion, 14411 = L. cf 1
(++ = 1 w)² - 12220²
+ +50 4u + +0 + +1(2- - 2v + 50² - -60 + 20
(-2- 24 + 44u- 25x² + 4v²) -1
4(-1+ v)²
where the first inequality follows from the property of quadratic function by taking =
(2 20- 2u0
2(-1+v) +20") Therefore when -1 <l<k< 2 and e 1, 1,4+11 > -1.
3) When -1 <k< -
2 and e < 1, rewrite 1/ with respect to I and we have
(+11 =
(-1+ (1 ( + +-11+ + +c)=)) (11 (-1 c)r (-1 + 2(-1 c) ))
where the minimum point is
1 < 1.
c/2 2 (1 c)o² <-
212 2
Therefore the minimum of 1/411 is obtained at = 11 -1, i.e,
h-1 2 - (-1+ (-1+ (3 - 2c 2)0² +-1+
2 - + (-1 + c) 30
where the inequality is from 0 S c < 1. Therefore when -1 < -4h²p² and c < 1, 1x+1 > -1.
4) When I s -1 and 2 2. consider 1/41 1 (15) and take the derivative de (%/11 1) de k+1- From previous discussion, consider de k+1 at 7. i.e.,
d
d 1/41 - 1/160² (48 + 8/2 23v² x² [(40 6o > 8² +161 > 0,
de
where the first inequality follows from > -1 - 2 by (11). Therefore the minimum of 1/41 is at c = _ or c
= 4. If c = 4.
1441 1 2 (160 + 161- - 41 + 81( - 18 +1+))
v²
(32- 705e² + 625m > 0
256
256
where the first inequality is from / > -1 - 6 by (11). cf 4
Yet 1 = (- -(- 2 (1- u) (1
2 + (-1 + (- 1-1 -1-1-1220 -30" + +00)
3v + - >00
00
where the first inequality is from / < -1. Therefore when / < -1 and e > 3. 441 4 >
min 256
2 (32 705 + 625c*), ), (1 - (1 + 30 + r²)} > 0.
In the next two cases c < and < c 4. we no longer assume g = hvVW but want the same
lower bound of k441- Since hU < hvVW, we have h(V W) > 1- - 1 + c2 - x2 > 0. By rewriting k to be
(441 =l - 4e0² +32 + + (1-1-111
+ +W2
+ 2 2) + (-u² + 2c0 (1 - 1 - 2 22 4u ))V() W),
38

---

Published as a conference paper at ICLR 2022
it can be seen from the minimum point w.r.t. h(V + W) that when h(V W) > 0 and 0 3 < 3. 1++1 decreases as h(V + W) decreases. Therefore by h(V + W) > 1- 1- o² - v², we have the
same expression for the lower bound of (++ but with U² i.,
h(1 4h x2 4+11 - = + ()) - U2) > 2 () - -U22,
(
-(-1+ c) + - + (-1 +
(-1 c)
5) When / S -1 and c S 1, consider 14+1 -1
4 - ( (11+
(15)
-11++))0+4-22+++2)) + (-1 + c)²²0
= ([11))) c) +2 - c)cu²)
+ (-1+c)30*)
where the minimum point is / 1/2 1- 1-(1-))++ +11 ) > - By 1 v -1 we have
1-c
- 2: 2)) (-1+c))+v²
= (10----00000--2<=c)))---------)- (-1+))))
2
(-1+0))) 20
Therefore when / 1 - and c 1, 4+1 4 133 + (VW (2) WVW CVVW-U? )
6) When / v -1 and 1 < c < - consider U. By h(v + W) - VVV
2², we have
Uk+1 h(1 - /V) + hyv - hw) U1 + hoW - N(V + +W) + )!²
= =m((c- 1)([+ )²) +1+ cu VW)
Thus denote hU++1 = c++1/41 c and we have
Cx+1 = (c - 1)(1 + x²) +1 - l2v
< (c - 1)( + x²) +1+ cu2 +1== 2202 <1
Then if [++1 - - 0, then 4442 - 1= 442 - 1k+1 + 1 4-2 - h+11 > 2VW - U²). Otherwise, we have 4++1 < and consider 22+2 Also, the distance between I and c++1 is larger than that of and i.e.,
-
1 1 Ck+1 - (c (c- 1) > (1 (c 1)(1+ +1+ (1 - (c - 1)
(16)
= 1 ++|+ x² - 20 > 0.
From previous discussion, 1,41 1 increases as 1 decreases. Also d. < 0 when 0 S < 1, s0 K441 1 increases as e decreases. By (16), we have ck+1 < - Then
1 - 1= 1/42 - 4+11 + 4,+1 > 1> 1411 + 1/
> ([1++0l(((111))+=22(1111))
+ +(1- (1--00((((441100022220000+11
=(=1-_(3=(-=2--222=1))-- + c)&09)
> 20 21) ((11)
= 20
0,
where the second inequality follows from c++1 < 2 - c and 4-11 < 1; the last inequality is by 1 < -1 and
< 3 Therefore when 1 < - and 1 < <
1' L - 14 WVW U or
4.
(11+
+ (-1 )
())4))
39

---

Published as a conference paper at ICLR 2022
Second, let U < 0 and q == -hU hyVW. Choose q= -hU = hvVW. Then similarly have the minimum value of 4x+1 when U < 0
1/41 ++ +1++++++++(0000) +
(1+ c) +
(17)
-21-2d))++
(1+0))+00((((+(1++0)))+++----+ (²
+(1-0000(((1++)))))(++11+- (-1 30 o22 - x² + +3u"))
2 -- (15 16c- 5c -8e² 2c
(18)
+
- -
2c 2)
where the inequality is because when > -1 2r + 202 (from (11)), 1/4 increases as I increases.
1) When c 2 1, since (-5 4e + 2c. + 22 2 0, we consider (-4 + 4e 362) + (15 + 16c
5c² Sc 2 denoted to be peart
d part de k+1
= (4 (4++6))) 6c)b² + (16 10c 24c² Sc²)
It has a root between -2 and 0. Also when 1, d part > 0; when +, d part d+1
Ampart
< 0. Thus, the
minimum of pport is achieved at e = 1 or L. i.e. pport 2 r² + 16x²)) Then
1+ 2 - - (3 + 16 + (-5 4c + 26² + 22)2 0.
Therefore when 2 lx+1 > 11
2) When S c < and > 1, from previous discussion 11 we have
141 2 -1+ 211 +
2 -1 (1 (1= 2c 2c + (1 + c
-11 6 -11
Therefore when 0 $ c < 1 and 11, > -1
3) When 0 < c < and -1, c 1/11 - 1. By (17),
14 - [(
+11+00000(111+++)))000+ -2 - +2+30*))
2 (0(-=))0-- / (1+c)2/6
where the first inequality is because the minimum point of is greater than -1. Therefore when 0se c < and < 1, 4++1 4 > 2 Gu?) vb.
Actually all the proofs of l -1 + 4+1 +1+ C' for some C 0 are valid for all < V2 + We < 2/2 + 2hp² (1 + ,.
In general, if 4 > 1, then there exists constant C > O only depending hp s.t. 1; -1 C for
all i > k. If 4. < 1,, then either (1) 14+1 increases at least by fixed value only depending on hu, or (2) 4++2 or 1++1 increases by (V U2). if keeps staying in case (2), then since 4 S -.
V& U will be larger and larger until I > -1 for some Therefore, there exists a K > 0, s.t.
when ho > K. lg > -1 + C. Then because 4 < 1 - h² let 0 < Co = max - C, - h2 p² <
and we have | < Co < for all k: K. Further,
V.W. U3 < CaCk- K)) (VxWK U2) + 0 as k 20,
i.e., 1 U8 V.WE
0 = cos( ((x) vk)) 1.
Otherwise, there exists K > 0, s.t., Vx Wx U3 = 0, then V&W, - -U2 = for all k: 2 K. There two cases. (i) FK and yk already aligned. (ii) one of Vx and W is 0. WOLG assume
40

---

Published as a conference paper at ICLR 2022
Vx= 0. Then from the GD update,
rk+1 Jk h(ll TAME 13k
kk+1 yk + h(pl 2 j=z
IK+1 and VK+1 will be aligned for both cases. Then for all 2 K 1, 24 and yi is aligned, i.e., cos ((rx, yi ) 1.
I PROOF OF THEOREM 5.
1.1 GENERAL RANK APPROXIMATION FOR NON-NEGATIVE DIAGONAL MATRIX
We first discuss easy where A is non-negative diagonal matrix (later on will see this is actually the canonical case) and consider
min IIA - 12//2 F.yRR"
(19)
P2lns
Assume A
where Ing is an identity matrix of dimension n2 ni.
Bmm Amlan
En =
pi + Hj for + j. Let S; = (1,2,...,,,) + Σÿ= ny. i.c., an index set describing the positional indices Inc. Let jmma = max (1. ... Mm and Smaz be the corresponding index set. Let [Nixes yoo] be fixed point of the GD map. Let 2,,00 and ya be the sth element of I and Yoo-
The following theorem characterizes the fixed points of the GD map.
Theorem I.1. The fixed points GD map satisfy E.es. 22.00 EvEs, 22 = 14, I1, = y1,00 = for 8 & S₁ === -,..., n. Thus || |Illyoo| = Mi vi 1,... n.
Proof. To solve the fixed points, we have Vi 1, ... n and x E S
{
(A Foo Woo Ayz (u Vo =
(A xoc Txxc A ATro (oo
i.e.
{
M.Ns,xc (W * 1i ( p:00,000 (oo
Obviously, Foo Yoo 0 is fixed point. If $s.00 * 0, then Js # 0 and have of (mT Foo (o.. Since 14 # μ1 for i + j. there exists most one i, s.t. 2n (ox and all the 2,,00 3s S.I. s E Sy. + zero.
This theorem identifies that each of these fixed points is concentrated in one of the positions of the eigenvalue blocks. Note the fixed points contain both stable and unstable ones, i.e., all the global minima and saddles are of the above form. Moreover, the global minima are the points obeying Exes.... 2² Exes v² pm Is,00 = ys = 0 for s & Smaz and also || [lllysol Mmaa- The saddles are the ones with 14 # Jmmaz 1,..,.....
2
Remark 1.2 (The alignment of Zoo and y at the global minimum). the global minimum of the objective (19) with diagonal and non-negative A defined above, Toe is the rank-1 approximation of A with the largest eigenvalue, i.e., we have Pmez = (x=30))))) = T. Voc. Also, from the above theorem, || |/o || = Pmaa- Therefore for each global minimum, there exists scalar / > 0, s.t., Joo Iyo.. i.c., Toe and 1/so are aligned at the global minimum.
Based on the analytical form of eigenvalues the Jacobian of GD map (19) in Theorem I.1, we can establish the following relation between &o and yoo at the global minimum via stability analysis.
41

---

Published as a conference paper at ICLR 2022
Theorem I.3, For almost all initial conditions, GD converges to minimum, then x: Yoc Pmoz and
2 h
I 112 + 113/ 12<
(20)
the extent of balancing is quantified by
2
1 Yoo 12=
2
(21)
Proof. Since each unstable fixed point has its stable set with negligible size when compared the stable set of stable fixed point, then for almost all initial conditions, if GD converges to global minimum, this minimum a stable fixed point of the GD map.
From the above theorem, we know the fixed points are pf (Ix MoToboo) Assume n²² (x. Voo)
-h0 hAT 2hyooo
hA 2hx I2n + Å, since the lower two =c0)
For the Jacobian J I2n blocks commute, we have
det(AT - A) = det()> + Ai + VooUlso In + 12 In A2
+ 1/2 +22 20
20 yo0
dct(>²I, Ah(x Vooy In h² In h22 A²
+ (2(A - zx 1o0 T + 2x xx 2/ 20 (A yoc 2c)))
Ie + A xo V In 1²222,, A²
II (x² + M1 xxx + vo Vo) ) + 12 (n² - pf)).
Hence the two values, and to + VooMoo), are eigenvalues of J each nonzero fixed point.
If (ss) then |1 - MI + vool) < > the eigenvalues are bounded by 1. Hence Too Noo f.
If + max(u:). then 1+ 1+ 1- Too +o) + (= too + V.. 4h²( n2))))
1 for μ4 2 μ.. It has at least one unstable direction. It's stable set is measure
The second inequality the theorem follows from x: I = μl at the global minimum because of diagonal and non-negative A and SVD.
L
1.2 GENERAL MATRIX FACTORIZATION FOR NON-NEGATIVE DIAGONAL MATRIX
In this section, we consider problem (5) via GD iteration but with A Rax be an arbitrary non-negative diagonal matrix.
Let μn 2 M2 > ... 2 > 0 be the diagonal elements of A. Let = rank(A) which of course satifies r < n. Also assume that ||A|]] does not scale with n or d (without loss of generality we can assume || = O())) Then we will have our balancing result in the following.
Theorem I.4. For almost all initial conditions, GD for (5) converges to a global minimum, then there exists = c(n, d) > co with constant Co > O independent of n, d, and learning rate h, such that, (X, Y) satisfies
x|1xx (Yo
h
and the extent of balancing is quantified by
min(d.r) Σ
-Yo <
-
Pi.
ch
1=1
42

---

Published as a conference paper at ICLR 2022
Proof. Let =rank(A) I Since each unstable fixed point has its stable set with size negligible when compared to the stable set of stable fixed point, then for almost all initial conditions, GD converges to global minimum, this minimum is a stable fixed point of the GD map.
For matrix X (x1 22
Ta) E Raxd, where æ; E IR" is the ith column vector, we vectorize the
21
22
variable and get vea(X)=
Then we can rewrite the GD iteration,
Id
Xk+1 Xx + +MA XNY
Yo+1 = Vs + VxXT)Xx
=f
(ee((x+1) = veel (xc( )+ 117 3
T(wee) T(vee(V ( (eec((K))
vec(Yx++1) vec(Yr) + 11/ & A - T (veel Xx )eecc(Y) ))ee((xs)
where & the Kronecker product, and Rndxad Rudxnd is linear operator, s.t.
M
Mid
MI
Mid
T
:
Mai
Maa
M
M
Ma
vivl
129l T
zavi
1/1//2
x292
way2
then
T(vec(Y) ((Fcc(()ue(x))))=
viVd
raya
The Jacobian of the vectorized GD map (replace X2 and Ys by X and Y) I2nd - hhM, where
Y In M (T(vec(X)uvcc)) + (YX A)
T(vec(Y (eecc( ()) ) + (XY A -
X
We would like obtain estimation of the eigenvalues of hM for stability analysis. Since M is the Hessian of the objective at the global minimum defined, all the eigenvalues are non-negative. Also, since || is independent of h, and d, can just assume without loss of generality ||A|| = ((1) and then take || and || to be O(1) at each global minimum. Then
tr(M) (I] + |
O()).
Next consider tr(M2). We only need the diagonal blocks of M The two diagonal blocks are the following
M1 = Y s9 1
+ A)/X((e((X)e<(())))111) - -A], M2 (X T x & Ln)²
+
+ ())
A)].
Since evaluate this matrix at the minimum, we have the gradient equals 0, i.c.,
(A-XYT)Y- 0, (A Yx By the mixed- mrxduuproduct property of Kronecker product, have
Mi (Y TY 8 J, + ((vee(Y)uec(()) (T(wee( (U)ec(())) + La 0 [A - (A--))(A))))) YXT)),
M₁ (X x)2 @ I, + T(vee(X))eeee (eec)))))))))))
La @ [4 14--Ya Y- (A-
43

---

Published as a conference paper at ICLR 2022
Then
tr(M²) = || MYll + +n[]xxXx x
|r + +d - -A
Also, this is the global minimum, meaning
= Ei d<r
|
00 d
Therefore, when d 2 r, we have
1r( lr(M²) 2 |x | - + (n)).
When d < r, we have
- = | Y F n X x || y 11 d A X
2 | YY nl X x | y
A XY (n)).
Therefore, the number of non-zero eigenvalues is = (n.. Let Amar be the largest eigenvalue of M. Then there exist a constant co > 0
Amaz Z tr(M)/N 2 co
From stability analysis, we need the absolute values of the eigenvalues of hM to be bounded by 1, i...
2 h
1 hco || 21 1 - hdmaz 2 -1 colI IM
Obviously, if we pick constant c = c(n,, d) for each and d instead of co. the above inequality also holds with c(n,, d) co.
For the derivation of the second inequality, since the global minimum tr(X Yo!) E 144 = EE Eiidddm) because for non-negative diagonal A, its SVD of the non-zero part satisfies Unan- zero Vnon- have
min(d.n3
2
1xx Yool 11 1| 2xr
Σ
Pi-
ch
1.3 FROM DIAGONAL MATRICES TO GENERAL MATRICES
Proof of Theorem 5.1. First all the minima this problem are global minima and all the saddles are unstable fixed points. Since each unstable fixed point has its stable set with size negligible when compared to the stable set stable fixed point, then for almost all initial conditions, if GD converges to point, for almost all situations, this point is stable fixed point of the GD map.
By singular value decomposition (SVD), A = UDVT, where U, D.V E BRxn U and V are orthogonal matrices, and is non-negative diagonal matrix. Let X₁+ U RR, Y2 V Sg. Then
{
X Xx h(A X&Y, YY Yx+1 = + h(1 ) T
UR = UR + --UDVT UR V
VS VSS +UUDVT - S V T
R&+1 = R4 + hhD SA S
Sk+1 = +S R R
Therefore, problem (5) is equivalent to the following problem solved by GD
min R.
|| | 11 /2.
(22)
44

---

Published as a conference paper at ICLR 2022
From Theorem 1.3 and I.4, obtain: if GD for (22) converges global minimum (R, then there exists a constant c > 0 independent of n, r, d, and h, s.t., the limiting minimum satisfies
2 ||S|i] h
cll R
and the extent of balancing is quantified by
min
R PR-S1p S|
14.
ch
t=1
Especially, when d = 1, E cc
Since X = UR, Y = VS + R = U X, S VVVY we have |R|| = || ||S|| = | F. and -
The we obtain the first and second inequalities in Theorem 5.1. Also, by SVD, |XY Emin(dn) v I || | we obtain the third inequality.
= || -UVVTY F.
45


Reviews:
[{"review_id": "btSaDN1IL-", "reviewer": "Reviewer_VWDy", "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": "Unfortunately, I feel that both the theory and the simulations in this paper do not provide sufficient evidence of the aforementioned claims to merit acceptance. Also I feel that the presentation of the paper could be improved.\n\nMy two major concerns are the following:\n\n1. I  feel that the theorems do not really support the claim that only large step size leads to balancing (in contrast to small step size). For example, Theorem 3.2 makes some statement provided the step size h is not too large. Then the theorem gives an upper bound on the balancing between x and y. This bound becomes stronger, if the step size is larger but how does one know that a similar bound is not also available for small step size? Even more importantly, Theorem 3.1 and 3.2 require an assumption on the step size h which depends on the initialization x_0 and y_0 (equation before l. 153). Note that the more unbalanced x_0 and y_0 are, the smaller the learning rate needs to be (and the weaker the statement in Theorem 3.2 becomes.) Hence, this result aper does not apply for unbalanced initialization and large learning rate. Analogous concerns hold for the theorems in Section 4 and Section 5. (One minor(?!) concern: Theorem 5.1 assumes already that there is convergence, i.e. the statement only holds provided that there is already convergence.)\n\n2. The authors could provide much more experimental support. To me it seems that the only experiments which document that larger step size leads to more balancing are provided in Figure 4. However, I feel that much more extensive experiments are needed. (A larger choice of different step sizes and also a larger amount of initializations, for example scale of initialization and balancing at initialization.) Moreover, I feel that these experiments could be made more convincing if not only matrix factorization would have been considered but also the more challenging problems of matrix completion or matrix sensing.\n\nFurther comments:\n\n-There is no labeling of the x-axis in Figures 2 and 4. I assume that this should be the number of iterations, right?!\n\n-In both the first and third figure, gradient descent does not converge to zero loss, but the loss does become constant after some amount of iterations. Is this due to the fact that GD has reached machine precision? How do you exclude that scenario? Also it might be made more clear in the caption that the left two figures correspond to one learning rate and the two figures on the right correspond to one learning rate.\n\n-l. 203 \" We expect the convergence in (4) is 204 more complicated than ...\". What does \"more complicated convergence\" mean?\n\n-I feel that the readability could be increased if Theorem 3.1 and Theorem 3.2 would have been combined, i.e. one theorem instead of two. The same is true for Theorem 4.1, 4.2, and 4.3.\n\n-I feel that the formulation of Theorem 1.1 is somewhat unclear. First of all, note that the variable \"A\" has been overloaded. It is the matrix in (1) as well as a scalar defined in Thm 1.1. But more importantly, the statement is unclear. For example, what happens if I set the scalar A=2/h. Then I obtained perfect balancing between X and Y, but this should not be possible?! \n\n", "summary_of_the_paper": "This paper is concerned with the non-convex matrix factorization problem. This paper considers the square loss, which is optimized via gradient descent. Due to symmetries of the problem, there are infinitely many different global minima. This paper aims to understand to which minima gradient descent with large learning rate (=step size) converges to. \n\nThe main claim of this paper is that gradient descent with large learning rate has an implicit regularization effect, meaning that it converges to factors of the underlying matrix, which are implicitly balanced in norm. To substantiate the claim, the paper provides several theoretical results as well as some numerical experiments.\n\n", "summary_of_the_review": "As both of theory and experiments do not substantiate the claims of the paper enough, I unfortunately cannot recommend acceptance. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "beL3Cgw52xM", "reviewer": "Reviewer_MuC1", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "I marginally recommend rejection.\n\nSTRENGTHS: This paper tackles an interesting question of whether large learning rate implicitly regularizes gradient descent, which has not  previously received much theoretical attention. For the 1xd and dx1 special cases of matrix factorization, experimental and (very involved) theoretical evidence is given for this regularization. The paper is for the most part very clearly written.\n\nWEAKNESSES: The main weakness, which the paper completely elides, is that the result does not actually extend to the general matrix factorization setting (the paper states \"We theoretically show the convergence of GD with large learning rate\", but I could not find a theorem statement corroborating this in the general case). In particular, the main theorem for the general case assumes that the learning rate is such that GD converges to a global minimum. This seems to ignore one of the main difficulties, which is proving that even with a large learning rate GD will converge (since classical optimization arguments break down for large learning rate, and it seems quite plausible that GD could have chaotic or periodic behavior). Indeed, under the assumption that GD converges, the proof of the theorem is simply a local argument about the curvature of the various critical points (the \"stability analysis\"), whereas I would expect that some global argument is necessary to get convergence.\n\nIn my opinion, the paper would be much stronger if convergence were properly addressed in the general case.\n\nOTHER COMMENTS:\n- The special case proofs are quite technically involved. Is there hope for any insights from these cases that might extend to the general matrix factorization problem?\n", "summary_of_the_paper": "This paper studies the properties of gradient descent with large learning rate in the matrix factorization problem. The goal is to understand when gradient descent converges to a global minimum where the two factors are roughly balanced in norm, which is a shallow minimum that may be hoped to generalize better. For small learning rates (i.e. where classical optimization results guarantee convergence to a critical point), this does not happen. Hence, this paper considers learning rates beyond this regime.\n\nFor two special cases (when the matrices are 1xd or dx1), it is shown that under a large learning rate, gradient descent still converges to a global minimum, and this minimum is roughly \"balanced\". For the general case, it is shown that for almost any initial point, if the learning rate is such that gradient descent converges to a global minimum, then this minimum is roughly balanced.", "summary_of_the_review": "Although this paper raises an interesting problem of implicit regularization in matrix factorization with large learning rate, and provides evidence in special cases, it does not live up to its claims for the general case: failure to converge is a well-known issue with large learning rates, so the results for the general case which assume convergence are somewhat incomplete. It's also not clear whether the proofs in the special cases can provide any insight for the general case.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "YKehPUgSbr", "reviewer": "Reviewer_C6VY", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "Strengths:\n--The paper is well-written and very clear. Intuition is given so as to help the reader dissect the results.\n--The theorems are interesting and tackle a nontrivial setting, since few works (to my knowledge) have derived strong results for convergence and implicit bias in this regime. They treat both convergence of the optimization but (interestingly) the balancing effect that occurs when using large learning rates.\n\nWeaknesses:\n--I could find no significant shortcomings in the paper.\n--However, I do think the citations need to be improved. In particular, a number of the findings & discussions in Lewkowycz, et al. (2020) have some overlap with the results proven here but are not cited. For example, Lewkowycz, et al. (2020) found (1) the upper stability limit h~4/L for gradient descent, and a catapult phase that occurs between h> 2/L and < 4/L that involves search (phase 1) & subsequent convergence to a flatter minimum (phase 2). (2) The case n=1, d>1 is essentially the same problem setting analyzed there. (3) The final paragraph in Sec. 6 (starting after L278), discussing relationships to two-layer linear neural networks, was the setting studied in Lewkowycz, et al. (In fact, the u, v notation is identical.)\n", "summary_of_the_paper": "This paper studies gradient descent optimization of matrix factorization (various forms, including the most generic case) under large learning rate. The authors prove convergence results that apply when the learning rate is larger than 2/L and up to ~4/L, and also show that optimization with large learning rates leads to dynamic balancing between the two matrix factors in the factorization, an effect that does not arise when using small learning rates. In proving some of the theorems, the authors observe the optimization can have two phases: one in which gradient descent is driven to search for flat regions, and a second phase near the global minimum where convergence occurs towards a balanced solution for the factorization problem. ", "summary_of_the_review": "I think this paper derives useful theoretical results on large learning rate optimization of matrix factorization that will be of interest to the community.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "3CmrT266tLh", "reviewer": "Reviewer_Xmww", "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": "The problem is interesting. The proofs seem to be nontrivial. The technical contribution looks significant. However, I am not able to give a recommendation of acceptance due to the following issue:\n\n* In line 160, the upper bound does not seem to be $\\frac{4}{L}$. It seems to be closer to $\\frac{2}{3L}$ because when $x_0, y_0$ are close to the solution, $x_0 \\approx y_0$ and so $L \\approx \\|x_0\\|^2  + \\|y_0\\|^2 = 2 \\langle x_0, y_0 \\rangle = 2 \\mu.$ Then the bound on $h$ in line 152 becomes $\\frac{1}{3\\mu} = \\frac{2}{3L}$.\n\nGiven this problem, I request the authors to argue how the proposed learning rate is large. Specifically, large learning rate compared to what?\n", "summary_of_the_paper": "The authors study the problem of minimizing matrix factorization squared error with gradient descent. They show convergence with larger learning rates than previously considered. They further show that gradient descent has an implicit bias towards finding matrix factors which are magnitude-balanced in a certain sense.\n\n", "summary_of_the_review": "With my current understanding, I recommend a reject. However, I am expecting that the authors will answer my question and I will be able to give a higher score.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies gradient descent for matrix factorization with a learning rate that is large relative to the a certain notion of the scale of the problem. In particular, they show that the use of large learning rates leads to balancing between the two factors in the factorization.

The discussion between the authors and the reviewers was fruitful in dispelling some of the reviewers' doubts and at the same time improving the paper.

The paper seems to make some contribution on a relevant problem for the ICLR community. However, even in the restricted settings they consider, the problem does not appear to be completely solved. That said, I agree with the majority of the reviewers that the step forward seems enough to warrant the acceptance.

I would still encourage the authors to take into account the reviewers' comments in preparing the camera-ready version. In particular, in the internal discussion it was suggested that the presentation of the paper could be improved by clearly stating the limitations of the current approach (e.g., the assumption of convergence in Theorem 5.1, a better discussion on large vs small learning rates w.r.t. the balancing effect).
Decision: Accept (Poster)