Understanding the unstable convergence of gradient descent

2. Unstable GD Can’t Reach Stationary Points

• A quadratic cost diverges under GD if any eigenvalue of P exceeds 2/η; for convex quadratics, this condition is necessary and sufficient.The example confirms convergence below 2/L and divergence above 2/L.Source: §2 · pp. 2–3
• For C2 functions on X, under Assumption 1, GD avoids convergence to any stationary point in X from all but a measure-zero set of initializations, if each has negative minimum curvature or maximum Hessian eigenvalue > 2η.Source: §2 · p. 3
• Negative curvature or an eigenvalue above 2/η makes the GD update Jacobian have an eigenvalue with absolute value greater than one.Consequently, each stationary point has an unstable direction, which underlies the measure-zero convergence result.Source: §2 · p. 3
• The theorem applies even when stationary points are not isolated, and its eigenvalue condition can be relaxed if the open cover includes all stationary points.It excludes convergence even when just one eigenvalue exceeds 2/η.Source: §2 · p. 3

3.1. What Causes the Unstable Regime

• With weight decay and positive-homogeneous parameters, the loss has no stationary point when those parameters are nonzero; practical normalization can leave stationary points only near norm ε, with sharpness on the order of 1/ε.The authors conclude that a lack of flat, non-trivial stationary points near the GD trajectory can cause instability for practical step sizes.Source: §3.1 · p. 4

3.2. Causes for Convergence

• For the same unstable step size, applying tanh to a quadratic cost prevents divergence by flattening the landscape away from its minimum.This flattening makes a compact forward-invariant subset near the minimum possible.Source: §3.2 · p. 4
• In a single-neuron example, the linear network diverges, while the tanh network converges to a minimum whose sharpness is approximately 2/η.The authors suggest GD can travel along a valley of minima until it finds a flat enough minimum to stabilize.Source: §3.2 · p. 5
• On CIFAR-10, GD converges with tanh or ReLU activations but diverges without activations.The experiment uses full-batch GD with a fully connected network, two hidden layers of width 200, 5,000 examples, CrossEntropy loss, and η = 2/30.Source: §3.2 · p. 5
• Neural-network activation functions can create a compact forward-invariant set near minima, helping GD converge non-monotonically in the unstable regime.A forward-invariant set S satisfies F(S) ⊆ S for GD dynamics F(θ) = θ − η∇f(θ).Source: §3.2 · pp. 4–5

4.1.1. WARM-UP: THE STABLE REGIME

• In the stable-regime experiment, the relative progress ratio stays negative throughout, and the loss curve shows no non-monotonic behavior.The ratio's saturation around −1 was unexplained at first; the authors suspected rapid convergence of the GD trajectory to a single direction.Source: §4.1 · p. 5, §4.1.1 · p. 6

4.1.2. RELATIVE PROGRESS RATIO UNDER UNSTABLE CONVERGENCE

• In the unstable-regime experiment, the relative progress ratio saturates near zero, and larger step sizes appear to speed optimization, but η = 2/10 makes training loss diverge.The authors note that faster optimization under instability does not mean the step size can be increased without limit.Source: §4.1.2 · p. 6

4.2. Characteristics in Iterates Movement

• In the unstable regime, directional smoothness L(θt; η∇f(θt)) saturates around 2/η, indicating that gradient descent exhibits oscillating behavior.Source: §4.2 · p. 7

4.3. Relation between Relative Progress Ratio and Directionl Smoothness

• The single directional-smoothness value represents the weighted average well in Experiment 5, supporting the relation that oscillatory behavior produces a small relative progress ratio.The authors say this relation and experiment suggest that some form of Hessian Lipschitzness holds along the GD trajectory, even if gradient Lipschitzness is not a good neural-network assumption.Source: §4.3 · p. 7
• Under unstable convergence, RP(θt) oscillates near 0: it cannot stay positive because loss would not decrease in the long run, nor stay negative because GD iterates oscillate.Source: §4.3 · p. 8

4.3.1. ADDITIONAL EXPERIMENTS

• With ReLU activations and with two additional hidden layers, the results were largely similar to tanh experiments, and relation (4.3) held in all cases.Source: §4.3.1 · p. 8

4.4. Implications for Sharpness

• When the relative progress ratio oscillates around zero, the maximum sharpness along the iterate segment must frequently exceed 2/η, yielding the part A condition of edge of stability.Part B follows under the additional assumption that the gradient is approximately parallel to the Hessian's largest eigenvector.Source: §4.4 · p. 8

• Because SGD’s randomness prevents monotonic loss decrease, the expected relative progress ratio provides a more transparent way to define its unstable regime.The section introduces this as an extension of the relative-progress approach discussed in Subsection 4.1.Source: §5 · p. 8
• SGD’s expected relative progress ratio is not negative for a majority of iterations, even as loss decreases in the long run, suggesting unstable behavior and echoing Cohen et al. (2021).The authors note that this apparent contradiction was also observed in Cohen et al. (2021, Appendix H; Figures 25 and 26).Source: §5 · p. 9
• The authors establish an SGD analogue of relation (4.3), stated as relation (5.1).The derivation is given in Appendix A.Source: §5 · p. 9
• For CIFAR-10 ReLU experiments at η = 2/50, 2/100, and 2/150, the LHS and RHS of (5.1) are very similar; tanh results are similar.The comparisons are made at the end of each epoch.Source: §5 · p. 9

Better optimizer?

• Adjacent iterates have nearly opposite gradients in the unstable regime, challenging variance-reduced methods and motivating optimizers designed for this geometry.This implication follows from the paper’s characterization based on directional smoothness.Source: §6 · p. 9

Faster training under unstable convergence?

• Unstable convergence appears to accelerate training-loss convergence, prompting study of whether the relative-progress characterization explains this faster optimization.The observed faster convergence is described as a feature to investigate, not an established explanation.Source: §6 · p. 9

What assumptions are valid for neural network optimization?

• The widespread η < 2 L condition cannot explain unstable convergence; gradient Lipschitzness may be unsuitable for neural networks, while some Hessian Lipschitzness may be valid.The possible role of Hessian Lipschitzness is suggested by Experiment 5.Source: §6 · p. 9

Unstable regime for adaptive methods?

• The characterizations cover only constant-step-size (S)GD, leaving unclear how they extend to adaptive methods such as Adam and RMSProp.Studying adaptive methods could clarify how they differ from (S)GD in neural-network optimization.Source: §6 · p. 9

A. Proof of Theorem 2

• Rearranging the preceding expression yields the relation stated in Theorem 2.Source: A. Proof of Theorem 2 · p. 11
• The SGD case uses a similar derivation.Source: A. Proof of Theorem 2 · p. 11
• Taking expectation over stochastic-gradient randomness yields the desired equation after rearrangement.Source: A. Proof of Theorem 2 · p. 11