PaperlayerView exact revision on arXiv

Source-linked AI summary

An Exponential Learning Rate Schedule for Deep Learning

Zhiyuan Li, Sanjeev Arora

arXiv:1910.07454v3cs.LGstat.ML

TL;DR

The paper studies why exotic learning-rate schedules can work in normalized deep networks, addressing earlier analyses that omitted the usual combination of weight decay and momentum. It develops a trajectory-based equivalence between standard training and exponential learning-rate growth, then illustrates the interaction with a toy example and experiments. The results show that normalization makes these hyperparameters interdependent, while combined weight decay and normalization can prevent convergence in the toy setting.

  • Problem

    Earlier theoretical analyses of normalized networks did not rigorously account for the typical combination of weight decay and momentum, despite their common use with Batch Normalization.

  • Method

    The paper analyzes scale-invariant objectives and constructs equivalent exponential or tapered-exponential learning-rate schedules for SGD with momentum and weight decay.

  • Results

    The analysis rigorously replaces weight decay with exponential learning-rate growth, and the paper verifies the findings on CNNs and ResNets while showing joint weight decay and normalization can block toy-example convergence.

  • Takeaways & Limitations

    Learning-rate schedules, weight decay, momentum, and normalization should be analyzed jointly because their combined effects determine the optimization trajectory.

  • Takeaways & Limitations

    The equivalence requires λη to be below (1 − √γ)^2, and the paper presents hybrid exponential-cosine schedules as suggestive evidence for broader future theory.

Abstract

from arXiv · show

Intriguing empirical evidence exists that deep learning can work well with exoticschedules for varying the learning rate. This paper suggests that the phenomenon may be due to Batch Normalization or BN, which is ubiquitous and provides benefits in optimization and generalization across all standard architectures. The following new results are shown about BN with weight decay and momentum (in other words, the typical use case which was not considered in earlier theoretical analyses of stand-alone BN. 1. Training can be done using SGD with momentum and an exponentially increasing learning rate schedule, i.e., learning rate increases by some $(1 +α)$ factor in every epoch for some $α>0$. (Precise statement in the paper.) To the best of our knowledge this is the first time such a rate schedule has been successfully used, let alone for highly successful architectures. As expected, such training rapidly blows up network weights, but the net stays well-behaved due to normalization. 2. Mathematical explanation of the success of the above rate schedule: a rigorous proof that it is equivalent to the standard setting of BN + SGD + StandardRate Tuning + Weight Decay + Momentum. This equivalence holds for other normalization layers as well, Group Normalization, LayerNormalization, Instance Norm, etc. 3. A worked-out toy example illustrating the above linkage of hyper-parameters. Using either weight decay or BN alone reaches global minimum, but convergence fails when both are used.

1 INTRODUCTION

The paper argues that normalization makes optimization and regularization inseparable, and rigorously links weight decay and momentum to exponentially increasing learning rates. It supports this view with a toy example and experiments on CNNs and ResNets.

  • Batch Normalization improves optimization and generalization, and is commonly combined with weight decay and momentum.
  • Normalization layers make the objective scale invariant, so rescaling trainable parameters does not change predictions.The paper discusses BatchNorm, GroupNorm, LayerNorm, and InstanceNorm.
  • The paper proves that SGD with momentum, weight decay, and a standard learning-rate schedule is equivalent to SGD with momentum and an exponentially increasing learning rate.The equivalent schedule multiplies the learning rate by (1 + α) each iteration, where α depends on momentum and weight decay.
  • For zero momentum, the equivalent schedule is ˜η_t = (1−λη)^−2t−1η.
  • The equivalence requires λη to be smaller than (1 − √γ)^2, a condition the paper states is almost always satisfied in practice.
  • A toy example shows that either weight decay or normalization alone reaches zero training error, whereas combining both prevents convergence to the global minimum.The paper also experimentally verifies its theoretical findings on CNNs and ResNets and explores hybrid exponential-cosine schedules.

2 DERIVING EXPONENTIAL LEARNING RATE SCHEDULE

The paper derives equivalences between weight decay and exponentially increasing learning rates for scale-invariant objectives, extending the analysis from momentum-free SGD to momentum and multi-phase schedules.

  • 2.1 Replacing WD by Exponential LR in Momentum-Free SGD: Scaling parameters by ρ corresponds to scaling the learning rate by ρ^-2 because scale invariance changes gradient magnitude while preserving direction.This maintains the ratio between the parameter and its gradient update.
  • 2.1 Replacing WD by Exponential LR in Momentum-Free SGD: Fixed learning rate with weight decay can be translated into an equivalent exponential learning-rate schedule when momentum is zero.The construction uses parameter rescaling and preserves the resulting network in function space.
  • 2.2 Replacing WD by Exponential LR: Case of Constant LR with Momentum: With momentum, Theorem 2.9 gives eη_t = η_0 α^(-2t−1), where α is a positive root of a quadratic determined by momentum, weight decay, and the initial learning rate.The two parameter sequences satisfy eθ_t = α^t θ_t and therefore represent the same networks in function space.
  • 2.3 Replacing WD by Exponential LR: Case of Multiple LR Phases: PreResNet32 trained with Step Decay and its corresponding Tapered-Exponential schedule has similar trajectories and performances.The schedule replaces weight decay during the relevant training phases while retaining momentum.
  • 2.3 Replacing WD by Exponential LR: Case of Multiple LR Phases: For multi-phase Step Decay, a Tapered-Exponential schedule with momentum correction at each phase boundary produces the same network trajectory in function space.An alternative TEXP++ schedule is exactly equivalent without one-time momentum corrections, and is close to TEXP under standard hyperparameters.

3 EXAMPLE ILLUSTRATING INTERPLAY OF WD AND BN

A toy example examines how weight decay and normalization interact during optimization. Either mechanism alone permits convergence, whereas using both together prevents convergence to sufficiently low training error.

  • Setting: The example considers fine-tuning the final linear layer for Gaussian binary classification with logistic loss, constant learning rate, weight decay, and no momentum.The input is assumed separable, with labels given by the sign of the first coordinate.
  • Case 1: WD alone: Weight decay alone allows large-batch SGD to approach the global minimum because the L2-regularized objective is strongly convex and smooth.The argument assumes a suitably small learning rate.
  • Case 2: BN alone: Batch normalization alone causes the parameter norm to grow, reducing the effective learning rate and allowing SGD to reach the unique global minimum.The gradient has a lower bound proportional to the parameter norm with constant probability.
  • Case 3: Both BN and WD: With both BN and weight decay, SGD fails to converge to any solution whose error is smaller than O(√ηλ), independently of batch-size noise.The theorem applies with high probability over the randomness of samples.
  • Case 3: Both BN and WD: The proof sketch attributes nonconvergence to insufficient norm growth to offset weight-decay shrinkage near the global minimum, forcing the weight to leave that region.As the norm shrinks, the gradient grows relative to it until the trajectory exits the local cone.

4 VIEWING EXP LR VIA CANONICAL OPTIMIZATION FRAMEWORK

The paper examines why exponentially increasing learning rates are difficult to explain using canonical first-order optimization theory, especially for scale-invariant networks. It argues that weight decay and scale invariance create dynamics requiring trajectory-based analysis rather than standard loss-decrease reasoning.

  • Exponential learning rates are mysterious under canonical optimization theory, which typically explains progress through per-step objective decrease and smoothness assumptions.The framework generally establishes convergence to stationary points for nonconvex objectives rather than explaining the observed efficacy of exponential schedules.
  • Scale invariance: Scale invariance makes the loss unchanged under positive parameter rescaling, while local smoothness decreases as parameter norms grow and is high near the origin.This complicates direct application of standard smoothness-based convergence arguments.
  • Scale invariance: Gradient descent with fixed learning rate and no weight decay grows parameter norms, thereby reducing smoothness and producing convergence behavior comparable to canonical nonconvex analyses.Prior work interpreted a related effect as objective smoothing due to Batch Normalization.
  • Weight decay: With weight decay, gradient flow follows the same trajectory as vanilla gradient flow up to an exponential reparameterization of time.This separates radial norm changes from tangential motion in the scale-invariant setting.
  • Weight decay: If local smoothness remains bounded by 2/η during constant-learning-rate updates with weight decay, the parameters converge to zero, contrary to typical observations that they remain bounded away from zero.The contrast indicates that the canonical smoothness condition does not always hold in practice with constant learning rate and weight decay.

5 EXPERIMENTS

The experiments test tapered exponential schedules and their simplified variants on PreResNet32 and CIFAR10, including settings with instantaneous learning-rate decay and a cosine-based schedule. They find that instant decay matters most when exponential growth is slow, while a cosine hybrid outperforms Step Decay on CIFAR10.

  • 5.1 THE BENEFIT OF INSTANT LR DECAY: TEXP combines an instantaneous learning-rate decay with a new exponential growth factor when entering each phase.The instantaneous decay is relatively small compared with the subsequent exponential growth, motivating tests of a simplified schedule without it.
  • 5.1 THE BENEFIT OF INSTANT LR DECAY: TEXP-- is approximately equivalent to a constant-learning-rate schedule whose weight-decay coefficient is reduced at each phase transition.The equivalence holds up to a momentum correction when entering a new phase.
  • 5.1 THE BENEFIT OF INSTANT LR DECAY: When learning-rate growth is large, instantaneous decay keeps the parameter near a good local minimum for only 1 epoch before divergence.The trajectory then behaves similarly to training without instantaneous decay.
  • 5.1 THE BENEFIT OF INSTANT LR DECAY: When learning-rate growth is very small, instantaneous decay is crucial: TEXP returns to equilibrium faster and achieves better test accuracy than TEXP--.In the second phase, the reduced growth takes 70 epochs to return to equilibrium; in the third phase, the much smaller growth would require hundreds of epochs.
  • 5.1 THE BENEFIT OF INSTANT LR DECAY: PreResNet32 trained with TEXP-- and Step Decay has similar trajectories and performances to constant learning rate with weight decay divided by 10 at epochs 80 and 120.This comparison is presented as following from the same equivalence argument as Theorem 2.12.
  • 5.2 BETTER EXPONENTIAL LR SCHEDULE WITH COSINE LR: On CIFAR10, a TEXP schedule built from cosine learning-rate changes performs better than Step Decay.Because cosine learning rate changes every epoch, the associated correction terms cannot be ignored; the finding requires verification on other datasets.

6 CONCLUSIONS

The paper rigorously connects exotic learning-rate schedules to normalization with weight decay and momentum, and experiments support the equivalence while motivating further schedule designs.

  • 6 CONCLUSIONS: Exponential learning-rate growth is rigorously derived from weight decay, with its precise expression also involving momentum.The analysis addresses the typical combination of normalization, weight decay, and momentum.
  • 6 CONCLUSIONS: Both Cosine and Step Decay schedules behave almost the same as their exponential counterparts, as predicted by the equivalence theorem.The exponential Cosine schedule achieves better test accuracy despite following a different trajectory.
  • 6 CONCLUSIONS: The analysis improves on earlier theoretical work by accounting for weight decay and momentum, which are routinely combined with normalization in practice.This addresses a gap in stand-alone normalization analyses.
  • 6 CONCLUSIONS: Hybrid exponential-and-cosine experiments suggest that additional learning-rate behaviors may remain undiscovered.The authors also suggest that analyzing linked hyperparameters could accelerate hyperparameter search.

A.2 OMITTED PROOFS IN SECTION 2.1

This appendix develops the map-based proof machinery for showing that tapered-exponential schedules reproduce the same network-function sequence as step-decay training, with phase-specific momentum corrections.

  • A.2 OMITTED PROOFS IN SECTION 2.1: Equivalent maps are defined up to a positive scalar factor, enabling the proof to compare update compositions across parameterizations.The appendix establishes shared outputs for several state coordinates before handling the first coordinate.
  • A.2 OMITTED PROOFS IN SECTION 2.1: The stronger theorem permits weight decay to change between phases while preserving equivalence through a tapered-exponential learning-rate schedule.The construction includes a one-time momentum correction at the first iteration of each phase.
  • A.2 OMITTED PROOFS IN SECTION 2.1: Canonicalization changes only the momentum component of the state, leaving the current parameters and learning rate unchanged.When consecutive learning rates are equal, the correction map becomes the identity.
  • A.2 OMITTED PROOFS IN SECTION 2.1: The proof constructs transformed parameters that remain proportional to the original parameters and therefore generate the same sequence of network functions.Momentum modifications occur only at phase boundaries in the constructed schedule.

A.5 OMITTED PROOFS OF THEOREM 2.13

The appendix proves the tapered-exponential schedule theorem by induction, establishing proportional parameter trajectories under conditions that ensure the defining recurrence remains valid.

  • A.5 OMITTED PROOFS OF THEOREM 2.13: The schedule uses free initial parameters α_0 and α_-1, while the equality eθ_t = P_tθ_t remains satisfied for different choices.This allows different transformed parameter trajectories under the same function-space equivalence.
  • A.5 OMITTED PROOFS OF THEOREM 2.13: Theorem 2.13 is proved by induction from matching initial states, showing that proportionality at iteration t implies proportionality at iteration t+1.The induction reduces the claim to matching coefficients in the recurrence, which follows from the definition of α_t.
  • A.5 OMITTED PROOFS OF THEOREM 2.13: Positivity of α_t is guaranteed under η_maxλ_max ≤ (1 −√γ)^2 together with the root-based definition of z_min.The stated condition ensures the relevant root exists and supports the recurrence analysis.
  • A.5 OMITTED PROOFS OF THEOREM 2.13: The transformed schedule matches the tapered-exponential schedule throughout each phase, while α_t geometrically converges toward a stable fixed value.When λ_maxη_max is small relative to 1−γ, z_min can be approximated by 1; the paper gives γ = 0.9, λ_max = 0.0005, and η_max = 0.1 as an example.

A.6 OMITTED PROOFS IN SECTION 3

These omitted proofs analyze a toy normalized model, establishing convergence for weight decay alone and examining why combining batch normalization with weight decay can induce persistent directional fluctuations.

  • A.6 OMITTED PROOFS IN SECTION 3: With weight decay alone, the strongly convex objective has a unique minimizer, and standard stochastic-gradient analysis bounds the eventual mean-squared parameter error.The minimizer is characterized by symmetry as w* = βe_1 for some β > 0.
  • A.6 OMITTED PROOFS IN SECTION 3: The combined BN-and-weight-decay case requires a lower bound on stochastic-gradient norms, established using concentration arguments for Gaussian projections.The proof organizes this analysis around a cone of directions near e_1.
  • A.6 OMITTED PROOFS IN SECTION 3: If training error remains small over the analyzed interval, successive parameter directions stay within an angular distance of at most 2ε.This follows from the spherical triangle inequality applied to two ε-optimal iterates.
  • A.6 OMITTED PROOFS IN SECTION 3: The stochastic-gradient lower bound implies that remaining inside the cone throughout the interval has limited probability.The proof combines the update-size requirement with a constant-probability gradient event at each iteration.
  • A.6 OMITTED PROOFS IN SECTION 3: At least once every 1/[2(ηλ−2ε^2)] ln(64∥w_T0∥^2ε/δ) iterations, the angle between successive parameters exceeds 2ε.The stronger statement applies whenever both iterates are ε-optimal and uses only that property of the global minimum.

A.7 OMITTED PROOFS IN SECTION 4

The appendix establishes non-convexity properties of scale-invariant losses and analyzes norm behavior under gradient descent with weight decay.

  • Scale-invariant losses are non-convex because they are undefined at the origin.
  • A scale-invariant loss cannot be locally convex on any ball containing the origin unless it is constant.
  • Under constant learning rate, no momentum, lower-bounded loss, and sufficient descent, gradient descent with weight decay drives parameter norms to zero.

B OTHER RESULTS

The appendix derives norm-growth identities for scale-invariant parameters and relates long-run update magnitudes to weight decay, learning rate, and momentum.

  • With zero weight decay, the norm change of a scale-invariant parameter satisfies R_t+1 − R_t = D_t + 2C_t.
  • The norm-growth analysis extends earlier vanilla-SGD results to momentum and normalization settings.
  • For general deep networks, the mean-square update is constant relative to the mean-square norm, with the constant mainly determined by ηλ.
  • Under constant learning rate, weight decay, and momentum, the limiting quantities satisfy (1 + γ)ηD_∞ = 2λR_∞.

C SCALE INVARIANCE IN MODERN NETWORK ARCHITECTURES

This section characterizes scale invariance in modern neural architectures using degree-of-homogeneity analysis, a DAG-based checking procedure, and examples across normalization layers and network families.

  • A network is scale invariant when its output has degree of homogeneity 0, meaning rescaling all parameters leaves the output unchanged.
  • C.1 NOTATIONS: The module analysis covers linear and bias layers, addition layers, and normalization layers with or without affine transformations.
  • C.1 NOTATIONS: Convolutional, fully connected, and diagonal linear layers have the same homogeneity effect because each increases the degree by 1.
  • BN and IN eliminate the effect of a preceding per-channel bias, whereas GN and LN do not generally provide this benefit.
  • Network architectures: The framework is applied to vanilla CNNs, fully connected networks, ResNet, and PreResNet, with additional shortcut normalization used to preserve scale invariance after downsampling.
  • The degree of homogeneity of a network can be checked by traversing its neural-network DAG in topological order and evaluating each module.
Loading 1910.07454v3…