PaperlayerView exact revision on arXiv

Source-linked AI summary

Large Learning Rate Tames Homogeneity: Convergence and Balancing Effect

Yuqing Wang, Minshuo Chen, Tuo Zhao, Molei Tao

arXiv:2110.03677v2cs.LGmath.DSmath.OC

TL;DR

The paper addresses the limited theory for large-learning-rate training in nonconvex settings. It analyzes GD on homogeneous matrix factorization and finds that larger rates can balance the factors, while proving convergence beyond the usual 2/L threshold in specified cases.

  • Problem

    Theoretical understanding of large-learning-rate benefits for nonconvex problems is limited, and convergence is not guaranteed; homogeneous models may also lack global smoothness.

    Source: §1 · p. 1

  • Method

    The paper analyzes GD on homogeneous matrix factorization, using convergence analysis for specified cases and discrete-time stability analysis for balancing in general matrix factorization.

    Source: §1 · p. 2, §5 · p. 7

  • Results

    For general matrix factorization, larger learning rates can increase balancing at convergence, while convergence to a global minimum is established for specified cases beyond the typical 2/L limit.

    Source: §1 · p. 2, §6 · p. 9

  • Takeaways & Limitations

    The balancing result offers an initial explanation for improved performance associated with large learning rates in the analyzed setting.

    Source: §6 · p. 9

    Rigorous analysis of whether similar balancing occurs in general deep linear or nonlinear networks remains future work.

    Source: §6 · p. 9

Abstract

from arXiv · show

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.

1 INTRODUCTION

The paper studies whether large-learning-rate GD can converge and whether it biases homogeneous matrix factorization toward balanced factors. It develops theory for convergence in specified cases and shows that larger rates can reduce factor imbalance, even from significantly unbalanced initializations.

1 INTRODUCTION

  • Large learning rates are motivated by empirical reports of improved testing performance, but theoretical understanding for nonconvex problems remains limited.The introduction notes that convergence under large learning rates is not guaranteed and that homogeneous models may lack global smoothness.Source: §1 · p. 1
  • The paper studies large-learning-rate GD on matrix factorization, allowing rates up to approximately 4/L, where L is the largest Hessian eigenvalue at initialization.The authors frame convergence and bias toward flatter, more balanced minima as their two questions.Source: §1 · pp. 1–2
  • For general matrix factorization, sufficiently large learning rates can shrink the factor difference at convergence, even from an initialization near an unbalanced global minimum.With a proper large learning rate, the limiting difference may decrease by an arbitrary factor.Source: §1 · p. 2
  • Convergence is proved for n = 1 or d = 1 with isotropic A, while the balancing effect is stated for general matrix dimensions and A.The convergence guarantee and the broader balancing result have different stated scopes.Source: §1 · p. 2
  • The analysis combines a problem-specific partition of the state space with discrete-time stability theory and geometric measure theory.The paper also describes dynamical transitions between regions as part of its analysis.Source: §1 · p. 2

2 BACKGROUND AND RELATED WORK

This section relates factor balance to curvature and explains why large learning rates are analyzed beyond standard smooth-optimization guarantees. It also contrasts the paper's approach with regularization, small-step GD, and prior large-rate studies.

Sharp and flat minima in (1)

  • At the simplified global minima, the largest Hessian eigenvalue is ∥x∥2 + ∥y∥2; balanced factor magnitudes correspond to flatter minima, while imbalance corresponds to sharper ones.The smallest eigenvalue is zero, consistent with global minima being non-isolated under homogeneity.Source: §2 · p. 3

Large learning rate

  • Classical GD theory guarantees convergence for h < 2/L under its assumptions, whereas this paper considers h ≈ 4/L for a nonconvex problem without global smoothness.The simplified factorization problems have unbounded Hessian eigenvalues.Source: §2 · p. 3
  • Unlike diminishing or infinitesimal learning rates, which maintain the initial magnitude gap, larger rates can shrink it; within the analyzed range, larger h gives a smaller limiting gap.The paper says well-balanced initial conditions do not require a large learning rate.Source: §2 · pp. 3–4

Related work

  • Prior approaches use explicit norm regularization or small learning rates to control factor magnitudes, while this work analyzes large-rate GD.Some cited regularizers penalize individual Frobenius norms; noise-based regularization has also been studied for reaching flat global optima.Source: §2 · pp. 3–4
  • Other large-rate studies examine annealing, neural-network behavior through the neural tangent kernel, or escape from local minima.The cited work by Lewkowycz et al. (2020) reports better testing performance empirically, while Kong & Tao (2020) study escape from local minima.Source: §2 · p. 4

3 OVERPARAMETERIZED SCALAR FACTORIZATION

The scalar factorization case studies whether gradient descent can converge with a large constant learning rate and whether that rate can reduce imbalance between the factors. The analysis describes a two-phase convergence path and quantifies balancing at the limit.

3 OVERPARAMETERIZED SCALAR FACTORIZATION

  • For almost all initial conditions, GD converges to a global minimum with a constant learning rate that can be nearly 4/L, beyond 2/L.The bound depends on initialization; the paper notes it is close to GD’s observed stability limit away from the origin.Source: §3 · p. 4
  • Large learning rates drive a two-phase path: GD searches for flatter regions, then converges near a global minimum with more balanced factor magnitudes.The objective need not decrease monotonically at the beginning of the large-rate cases.Source: §3 · pp. 4–5
  • Theorem 3.2 quantifies balancing at the limit, and larger learning rates can yield a smaller difference between the factors.The paper contrasts this with small learning rates, which maintain the magnitude difference.Source: §3 · p. 5
  • From a highly unbalanced initialization, the factor gap falls from approximately 17.9986 to 0.0154 under a proper large learning rate.The example uses h ≈ 0.0122.Source: §3 · p. 5, Figure 2 · p. 6
  • The proof handles convergence in two phases: the factor-norm sum has a decreasing trend during the search phase, and a state-space partition identifies a region of monotone convergence.The norm sum may decrease every iteration or every other iteration.Source: §3 · p. 6

4 RANK-1 APPROX. OF ISOTROPIC A (AN UNDER-PARAMETERIZED CASE)

For rank-1 approximation of an isotropic matrix, the paper analyzes an under-parameterized factorization distinct from the scalar case. It proves convergence and a balancing effect, using alignment of the factors as part of the convergence argument.

4 RANK-1 APPROX. OF ISOTROPIC A (AN UNDER-PARAMETERIZED CASE)

  • Unlike the scalar factorization, the rank-1 isotropic problem is under-parameterized when n > 1, and its global-minimum factors must be aligned.The scalar problem does not require this alignment.Source: §4 · p. 6
  • The analysis first proves factor alignment and then uses that result to establish convergence of the full iterates.The alignment step is described as new for this problem.Source: §4 · p. 7
  • For almost all initial conditions under the stated learning-rate conditions, GD converges to a global minimum in the rank-1 isotropic matrix problem.The convergence argument first establishes alignment between the factors, then uses it to prove convergence of the full iterates.Source: §4 · p. 7
  • Theorem 4.3 establishes balancing at the limit, with its extent quantified under the same initial-condition and learning-rate conditions as the convergence theorem.As in the scalar case, an unbalanced point near a minimum can lead to a more balanced limit.Source: §4 · p. 7

5 GENERAL MATRIX FACTORIZATION

Section 5 studies general matrix factorization with arbitrary square A and develops a balancing result for GD through stability analysis. The result covers any n and d when GD converges, with a sharper constant for rank one.

5 GENERAL MATRIX FACTORIZATION

  • For arbitrary square A and any n and d, the balancing theorem applies to almost all initial conditions whenever GD converges, with a constant bounded below independently of h, n, and d.For d = 1, the constant equals 1.Source: §5 · p. 8
  • The extent of balancing is quantified by the theorem, and for rank-one factorization of arbitrary A its constant is 1.The supplied passage introduces the quantification but does not include its formula.Source: §5 · p. 8
  • For general A, larger learning rates lead to a more balanced global minimizer, including when X and Y may align only after a fixed rotation of Y.The rotation is determined by A, not by the initial or final conditions.Source: §5 · p. 8, Figure 4 · p. 8
  • The proof rotates X and Y to form an equivalent problem, then uses stability analysis of GD as a discrete-time dynamical system.An SVD-based change of variables reduces the analysis to diagonal non-negative A.Source: §5 · pp. 8–9
  • The stability argument examines fixed points of the GD iteration, distinguishing stable from unstable points by the Jacobian eigenvalues.The paper states that unstable fixed points have negligible stable sets relative to stable fixed points.Source: §5 · p. 9

6 CONCLUSION AND DISCUSSION

The paper presents large-learning-rate GD as an implicit regularizer for homogeneous matrix factorization: it can reduce the difference between the factors while still converging to a global minimum beyond the typical 2/L limit. The authors connect this behavior to two-layer linear networks but caution that rigorous extension to general neural networks remains future work.

6 CONCLUSION AND DISCUSSION

  • Large-learning-rate GD can significantly reduce the difference between X and Y at convergence, with balancing increasing as the learning rate increases.The paper describes this as an implicit regularization effect for homogeneous matrix factorization.Source: §6 · p. 9
  • The convergence analysis allows learning rates beyond the typical 2/L limit, where L is the largest Hessian eigenvalue at initialization.Source: §6 · p. 9
  • For one-dimensional regression with a two-layer linear network, the factorization theory indicates that large-rate GD automatically balances u and v and yields a flat minimum.The authors say this may provide initial understanding of improved performance from large learning rates.Source: §6 · p. 9
  • The demonstrated theory does not rigorously extend to general deep linear or nonlinear networks, whose analysis is left for future work.Source: §6 · p. 9

A.1 MORE RESULTS FOR MATRIX FACTORIZATION

The experiments extend the balancing observations across scalar and general matrix factorization, matrix sensing, and matrix completion. They also report periodic GD orbits for the scalar objective at a specified step size.

A.1 MORE RESULTS FOR MATRIX FACTORIZATION

  • For scalar factorization, rates above 2/L shrink the norm gap; loss is initially non-monotone and later converges monotonically.For rates below 2/L, the norms barely change and loss decreases monotonically.Source: §A.1 · p. 13, Figure 5 · p. 13, Figure 6 · p. 14
  • In over- and under-parameterized matrix factorization, larger learning rates shrink the limiting norm gap, while overly large rates can make GD diverge.At sufficiently large rates, convergence has a two-phase pattern: initially non-monotone loss followed by convergence.Source: §A.1 · pp. 14–15, Figure 8 · p. 15, Figure 9 · p. 15

A.2 MATRIX SENSING AND MATRIX COMPLETION

  • In matrix sensing and completion, larger learning rates again bring X and Y norms closer at convergence, even when GD is non-monotone.The paper reports these balancing observations empirically for both problems.Source: §A.2 · pp. 16–17

B GD CONVERGING TO PERIODIC ORBIT

  • For the scalar objective (1 − xy)^2/2, GD with step size 1.9 can converge to periodic orbits of periods 2, 3, and 4.The figure marks xy = 1 as the global-minimum reference line.Source: B GD CONVERGING TO PERIODIC ORBIT · p. 17

C MODIFIED EQUATION FAILS FOR LARGE LEARNING RATES

The paper compares GD with a first-order modified equation and finds that the modified equation does not capture norm balancing at large learning rates. In the illustrated case, its solution remains far from the balanced minimizer approached by GD.

C MODIFIED EQUATION FAILS FOR LARGE LEARNING RATES

  • Backward error analysis motivates the modified equation as a way to approximate GD better than gradient flow.The paper cites Hairer et al. (2006, Chapter 9) for backward error analysis.Source: C MODIFIED EQUATION FAILS FOR LARGE… · p. 18
  • With x = 4, y = 10, and h = 0.026, GD nearly reaches a balanced minimizer, while the modified-equation solution remains near x ≈ 0.1 and y ≈ 9.The comparison uses absolute values because the global minima xy = 1 are symmetric.Source: C MODIFIED EQUATION FAILS FOR LARGE… · p. 18, Figure 16 · p. 19
  • Large learning rates fall outside the modified equation’s convergence domain, making it unsuitable for analyzing norm balancing in that regime.The figure compares trajectories over time t; GD’s kth step is plotted at time kh.Source: C MODIFIED EQUATION FAILS FOR LARGE… · p. 18

D PROOF OF PROPOSITION 2.1

The appendix connects Proposition 2.1 to two cited theorems, examines the scalar stability limit, and restates the over-parameterized objective using column vectors.

D PROOF OF PROPOSITION 2.1

E OVER-PARAMETRIZED SCALAR DECOMPOSITION: STABILITY LIMIT

  • For x0 = 20 and y0 = 0.07, GD converges at the stated upper-bound step size but blows up when h is slightly larger.The authors report that this bound is very close to the stability limit.Source: E OVER-PARAMETRIZED SCALAR… · p. 19

F OVERPARAMETRIZED OBJECTIVE: LARGE LEARNING RATE

F.1 EIGENVALUES OF HESSIAN

This appendix gives the Hessian eigenvalues for the over-parameterized objective, establishes local non-convexity near a global minimum, and recalls a convergence result for globally smooth objectives.

F.1 EIGENVALUES OF HESSIAN

  • For (μ − x⊤y)^2/2, the Hessian eigenvalues include ±(μ − x⊤y), each repeated n − 1 times; at x⊤y = μ, the nonzero eigenvalue is ∥x∥^2 + ∥y∥^2.At x⊤y = μ, zero has multiplicity 2n − 1.Source: §F.1 · p. 20

F.2 LOCAL NON-CONVEXITY NEAR THE GLOBAL MINIMUM

  • The objective is not locally convex in the stated neighborhood of a global minimum.Source: §F.2 · pp. 20–21

F.3 A REVIEW OF TRADITIONAL CONVERGENCE ANALYSIS OF GD UNDER L-SMOOTHNESS

  • For an L-smooth function, the recalled GD result guarantees convergence to a stationary point when h < 2/L.Source: §F.3 · p. 21

G PROOF OF THEOREM 3.1, THEOREM 3.2, AND COROLLARY 3.3

This section proves convergence by separating entry into a controlled norm region from convergence within it, including analysis of the Phase 2 region around u2. It establishes boundedness and uses monotonicity of imbalance and residual to constrain trajectories; in the scalar over-parameterized case, convergence is to bounded points with xᵀy = µ, except for measure-zero initializations.

G PROOF OF THEOREM 3.1, THEOREM 3.2, AND COROLLARY 3.3

  • The scalar over-parameterized theorems establish convergence to bounded points satisfying x^T y = µ, except for a measure-zero set of initializations.The two theorems cover their respective initialization regimes.Source: G PROOF OF THEOREM 3.1, THEOREM 3.2,… · p. 21

G.1 PHASE 1: 2

  • In phase 1, one- or two-step decreases in u_k^2 drive GD into the region ∥x∥^2 + ∥y∥^2 ≤ 2h, except for measure-zero initializations.The phase-1 result follows from the decay characterization and holds outside a null set.Source: §G.1 · p. 24

G.2 PHASE 2: u2

  • In phase 2, GD stays bounded and re-enters the region ∥x∥^2 + ∥y∥^2 ≤ 2h within finitely many steps, then converges to x^T y = µ when hµ ≤ 1/3, except for a null set.The number of steps to re-enter does not depend on the iteration number.Source: §G.2 · p. 26
  • When GD does not converge, u2_{k+2i} keeps decreasing for i ≥ 0 with s_{k+2i} ≤ −1; since s_k = 1 − h u2_k, some N > 0 has s_{k+2N} > −1.Source: §G.2 · p. 27
  • In the converging domain, GD stays bounded when u2_k ≤ 1/h + 2hμ^2 and |s_k| < 1 with s_k bounded away from 1.For s_k > 0, the proof uses decreasing |x_k − y_k| when |x^T y| < μ to keep the trajectory in the monotone-decreasing region.Source: §G.2 · p. 27
  • When |x_k^T y_k| < μ, |x_{k+1} − y_{k+1}| decreases, while |μ − x_k^T y_k| decreases monotonically toward a limit.If the residual limit is positive, the proof bounds s_k away from both −1 and 1; it also considers the case where the residual tends to zero.Source: §G.2 · p. 27

H PROOF OF THEOREM 4.1, THEOREM 4.2, AND THEOREM 4.3

This section proves convergence through a two-phase analysis, including eventual control of the iterates and alignment of the vectors. It also analyzes rank-1 approximation fixed points and establishes a balancing result for general matrix factorization under stated conditions.

H PROOF OF THEOREM 4.1, THEOREM 4.2, AND THEOREM 4.3

H.1 PHASE 1

  • GD enters {||x||^2 + ||y||^2 ≤ 2h} in finite steps, except for a measure-zero set of initial conditions.It does not converge to fixed points outside this region except for a measure-zero set.Source: §H.1 · p. 31

H.2 PHASE 2

  • After entering the phase-1 region, GD stays bounded and re-enters it within finite steps, with the number of steps independent of the iteration count.The stated outer bound is 2h + 2hμ^2(1 + 1/(1 − h^2μ^2)).Source: §H.2 · p. 33
  • Inside the phase-1 region, GD converges to the global minimum x^T y = ||x||||y|| = μ, except for a measure-zero set of initial conditions.The proof obtains x^T y → μ and uses this to establish convergence to the global minimum.Source: §H.2 · pp. 34, 36
  • Whenever l_k > -1, the passage guarantees a constant C > 0 depending only on hµ such that l_i > -1 + C for all i > k.Source: §H.2 · p. 40
  • Eventually, -1+C < l_k ≤ 1-h²μ², so |l_k|≤C0<1 for all sufficiently large k.The proof obtains this bound after showing that l_k above -1 stays bounded away from it, while values at or below -1 increase until they cross that threshold.Source: §H.2 · p. 40
  • For all k≥K+1, x_k and y_k are aligned, giving |cos(∠(x_k,y_k))|=1.Source: §H.2 · p. 41

I.1 GENERAL RANK 1 APPROXIMATION FOR NON-NEGATIVE DIAGONAL MATRIX

  • The general rank-1 approximation analysis first considers the case where A is a non-negative diagonal matrix, described as the canonical case.Source: §I.1 · p. 41
  • Fixed points concentrate in a single eigenvalue block; global minima use the largest eigenvalue, while fixed points associated with smaller eigenvalues are saddles.At a global minimum, the factors are aligned.Source: §I.1 · p. 41
  • For almost all initial conditions that converge to a minimum, the theorem analyzes the limiting factors’ alignment and extent of balancing.The supplied theorem statement does not include the precise alignment relation or balancing measure.Source: §I.1 · p. 42

I.2 GENERAL MATRIX FACTORIZATION FOR NON-NEGATIVE DIAGONAL MATRIX

  • For general matrix factorization with non-negative diagonal A, the theorem establishes a balancing result for almost all initial conditions when GD converges to a global minimum.It assumes ||A||_F = O(1) and states a constant c(n,d) > c0, with c0 independent of n, d, and learning rate h; the supplied passage omits the precise bound.Source: §I.2 · p. 42

I.3 FROM DIAGONAL MATRICES TO GENERAL MATRICES

The section reduces general-matrix factorization to a diagonal-coordinate GD problem via SVD, then transfers convergence and balancing bounds back to the original factors.

I.3 FROM DIAGONAL MATRICES TO GENERAL MATRICES

  • For almost all initializations, convergence—when it occurs—is to a stable fixed point, since all minima are global and saddles are unstable.Source: §I.3 · p. 44
  • SVD coordinates Xk = URk and Yk = VSk make problem (5) equivalent to the reduced problem solved by GD.Source: §I.3 · p. 44
  • Orthogonal transformations preserve the factors' Frobenius norms, enabling bounds in reduced coordinates to transfer to the original factors.Source: §I.3 · pp. 44–45
  • If GD for the reduced problem converges to a global minimum, the limiting solution obeys a balancing bound whose extent is quantified by the theorem.The supplied passages do not include the bound's explicit formula.Source: §I.3 · p. 45

Related papers

Loading 2110.03677v2…