PaperlayerView exact revision on arXiv

Source-linked AI summary

Theoretical Analysis of Auto Rate-Tuning by Batch Normalization

Sanjeev Arora, Zhiyuan Li, Kaifeng Lyu

arXiv:1812.03981v1cs.LGstat.ML

TL;DR

Theoretical analyses of nonconvex gradient descent require learning rates set using a smoothness constant that is often unknown, while BN’s effects remain incompletely understood. This paper analyzes scale-invariance in BN networks and concludes that gradient methods can attain asymptotically best convergence rates without tuning learning rates for scale-invariant parameters.

  • Problem

    Nonconvex convergence analyses require a sufficiently small learning rate determined by a loss smoothness constant that is unknown in practice, and BN’s benefits are not fully understood theoretically.

    Source: §1 · p. 2

  • Method

    The paper analyzes how scale-invariance in neural networks with BN affects optimization and learning-rate tuning.

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

  • Results

    Gradient descent and stochastic gradient descent achieve asymptotically best convergence rates without tuning learning rates for scale-invariant parameters.

    Source: §5 · p. 9

  • Takeaways & Limitations

    The analysis suggests that BN-induced scale-invariance reduces the effort needed to tune learning rates to fit training data.

    Source: §5 · p. 9

    The analysis assumes a smooth loss and does not apply to ReLU networks, though it applies to the smooth approximation softplus.

    Source: §1.1 · p. 3

Abstract

from arXiv · show

Batch Normalization (BN) has become a cornerstone of deep learning across diverse architectures, appearing to help optimization as well as generalization. While the idea makes intuitive sense, theoretical analysis of its effectiveness has been lacking. Here theoretical support is provided for one of its conjectured properties, namely, the ability to allow gradient descent to succeed with less tuning of learning rates. It is shown that even if we fix the learning rate of scale-invariant parameters (e.g., weights of each layer with BN) to a constant (say, $0.3$), gradient descent still approaches a stationary point (i.e., a solution where gradient is zero) in the rate of $T^{-1/2}$ in $T$ iterations, asymptotically matching the best bound for gradient descent with well-tuned learning rates. A similar result with convergence rate $T^{-1/4}$ is also shown for stochastic gradient descent.

1 INTRODUCTION

The introduction asks whether BatchNorm’s scale invariance can be shown to reduce learning-rate tuning, a question left open amid incomplete theoretical explanations of BN. It presents convergence results for scale-invariant parameters and situates them among prior analyses of normalization and adaptive methods.

1 INTRODUCTION

  • BN makes layer outputs invariant to positive rescaling of weights, and the resulting gradient scales inversely with weight scale.The paper presents this relationship as an intuitive explanation for how BN can adapt the effective learning rate during training.Source: §1 · p. 2
  • The paper targets a gap in nonconvex convergence analyses, which require a learning rate small enough for an often-unknown loss smoothness constant, while explanations of BN’s benefits remain unsettled.Prior work cited in the introduction suggests BN may not reduce internal covariate shift, and proposes a smoothing effect as an alternative explanation.Source: §1 · p. 2

1.2 RELATED WORKS

  • Prior theory examined BN in shallow networks or task-specific training, while WNGrad had established related auto-tuning behavior without proving it for BN itself.Other cited work studied scale invariance or adaptive algorithms, providing context for this analysis.Source: §1 · p. 2, §1.2 · p. 3

1.1 OUR CONTRIBUTIONS

  • With smoothness and bounded-noise assumptions, scale-invariant parameters need no rate tuning when the learning rate for scale-variant parameters is set optimally.For full-batch gradient descent, the result holds no matter how the learning rates for scale-invariant parameters are set.Source: §1.1 · p. 2
  • O(T^-1/2) for full-batch gradient descent and O(T^-1/4 polylog(T)) for stochastic gradient descent match their respective optimally tuned rates asymptotically, up to a polylogarithmic factor for SGD.The results concern convergence to a first-order stationary point.Source: §1.1 · p. 3
  • The analysis assumes a smooth loss and does not apply to ReLU networks, though it applies to the smooth approximation softplus.The authors also describe a modification to BN’s smoothing constant that maintains scale invariance.Source: §1.1 · p. 3

2 GENERAL FRAMEWORK

The framework separates scale-invariant from scale-variant parameters and uses scale-invariance to analyze optimization on a normalized parameter domain. It connects weight growth to adaptive learning rates and convergence without tuning the scale-invariant parameters.

2.1 MOTIVATING EXAMPLES OF NEURAL NETWORKS

  • The illustrative BN network has scale-invariant layer weights, while scale and shift parameters are generally scale-variant; the analysis requires smooth activations rather than ReLU or Leaky ReLU.The motivating network uses a minibatch objective with learnable γ and β parameters.Source: §2.1 · p. 4

2.2 FRAMEWORK

  • The framework partitions parameters into scale-invariant weights W and remaining parameters g, then minimizes expected loss using separate SGD learning rates for the two groups.Each w(i) in W leaves every per-example loss unchanged when scaled by any c > 0.Source: §2.1 · p. 3, §2.2 · p. 4

2.3 THE INTRINSIC OPTIMIZATION PROBLEM

  • The intrinsic problem restricts each scale-invariant weight to unit norm without changing the objective, and the paper studies stationary-point convergence there without tuning their learning rates.Scaling such weights can reduce gradient norms without reducing the loss, motivating optimization over normalized representatives.Source: §2.3 · pp. 4–5

2.4 ASSUMPTIONS ON THE LOSS

  • The analysis assumes differentiable losses, lower-bounded expected loss, smoothness bounds, bounded SGD gradient noise, and control of scale-variant parameter growth.The latter can be handled by projection to a bounded set or weight decay; the motivating network's smoothness bound can grow with depth and maximum width.Source: §2.4 · p. 5
  • The BN smoothing term is made proportional to the weight norm to preserve scale-invariance, while small smoothing has negligible effect when input variance is large.Smooth nonlinearities such as sigmoid, tanh, or softplus address the nonsmoothness of ReLU-based examples.Source: §2.4 · p. 5

2.5 KEY OBSERVATION: THE GROWTH OF WEIGHTS

  • Weight growth links scale-invariance to automatic learning-rate decay, and the effective learning rate for normalized weights depends on weight scale as well as the nominal rate.The paper states that initialization magnitude matters: multiplying a scale-invariant parameter's initialization by C is equivalent to dividing its learning rate by C^2.Source: §2.5 · p. 6
  • Gradient descent on the original problem is equivalent to an adaptive method on normalized weights, with a projected update that generalizes the WNGrad connection to normalization methods inducing scale-invariance.The effective learning rate depends on weight scale; scaling initialization by C is equivalent to dividing the learning rate by C^2.Source: §2.5 · p. 6

3 TRAINING BY FULL-BATCH GRADIENT DESCENT

The full-batch analysis separates scale-invariant parameters W from scale-variant parameters g and studies gradient descent using the full training set. With a carefully chosen learning rate for g and an arbitrary positive learning rate for W, it proves convergence to a stationary point at a rate matching the asymptotic rate of gradient descent with tuned learning rates.

3 TRAINING BY FULL-BATCH GRADIENT DESCENT

  • The analysis uses fixed learning rates for W and g, tuning ηg while allowing any positive ηw.Full-batch training uses the whole training set at each iteration.Source: §3 · p. 6, §3.1 · p. 7

3.1 SETTINGS AND MAIN THEOREM

  • With ηg = 2(1−cg)/Lgg and arbitrary ηw > 0, gradient descent converges to a stationary point at the asymptotic rate of GD by Carmon et al. (2018).The theorem's displayed rate is incomplete in the supplied passage; the passage supports the stationary-point conclusion and the asymptotic-rate comparison.Source: §3.1 · p. 7

3.2 PROOF SKETCH

  • The proof sketch bounds gradient norms through loss decrease and controls weight growth by splitting training into two effective-learning-rate phases.The phase distinction is whether ηw/∥w(i)∥² lies above or below a threshold.Source: §3.2 · p. 7

4 TRAINING BY STOCHASTIC GRADIENT DESCENT

For stochastic gradient descent, the paper lets the learning rate for scale-invariant parameters W be chosen rather freely while tuning the rate for scale-variant parameters g. Under the stated schedule, convergence matches SGD's asymptotic rate up to a polylog(T) factor.

4.1 SETTINGS AND MAIN THEOREM

  • The W learning rate may be any positive initial value and decay equally as or slower than the optimal SGD schedule, including a fixed rate when α = 0.The rate for g is scheduled as ηg,t = ηg·(t+1)^−1/2, with ηg tuned to (1−cg)/Lgg.Source: §4.1 · p. 8
  • With ηw,t = ηw·(t+1)^−α for 0 ≤ α ≤ 1/2 and the stated ηg schedule, SGD converges at a rate matching its asymptotic rate up to polylog(T).The supplied theorem passage gives the conclusion but not the full displayed rate.Source: §4.1 · p. 8

4.2 PROOF SKETCH

  • The proof sketch simplifies to one scale-invariant parameter, no g parameters, and α ∈ [0, 1/2), then bounds the effective learning rate for α < 1/2.It uses Taylor expansion and bounds the effective learning rate ηw,T∥wT∥² by ˜Ω(T^−1/2).Source: §4.2 · p. 8

5 CONCLUSIONS AND FUTURE WORKS

The paper concludes that scale-invariance associated with BN reduces the need to tune learning rates for scale-invariant parameters while retaining asymptotically best convergence rates under the analyzed settings. Its analysis is limited to smooth losses and gradient descent.

5 CONCLUSIONS AND FUTURE WORKS

  • Scale-invariance lets gradient descent achieve asymptotically best convergence rates without tuning learning rates for scale-invariant parameters.The authors say their analysis suggests BN-induced scale-invariance reduces the effort needed to tune learning rates to fit training data.Source: §5 · p. 9
  • The analysis covers smooth losses and gradient descent; the authors identify non-smooth losses and momentum methods as directions for further results.They note ReLU and Leaky ReLU are often used and make losses non-smooth.Source: §5 · p. 9

A PROOF FOR FULL-BATCH GRADIENT DESCENT

The appendix proof uses scale-invariance to work with normalized weights and derives bounds on gradients and weight scales. These bounds are combined to establish the full-batch result.

A PROOF FOR FULL-BATCH GRADIENT DESCENT

B PROOF FOR STOCHASTIC GRADIENT DESCENT

The appendix proof for stochastic gradient descent bounds separate contributions to the convergence argument and combines them to prove Theorem 4.2.

B PROOF FOR STOCHASTIC GRADIENT DESCENT

2. By Lemma B.1,

C PROOF FOR THE SMOOTHNESS OF THE MOTIVATING NEURAL NETWORK

This appendix verifies that the modified motivating network satisfies the smoothness assumptions used in the analysis, under stated conditions on the network, objective, activation, and regularization.

Assumptions and proof strategy

  • The smoothness argument assumes the smoothed BN network, a twice continuously differentiable lower-bounded Lipschitz objective, a twice continuously differentiable Lipschitz activation, and weight decay on g.The proof first establishes boundedness of g, then obtains smoothness using compactness.Source: C PROOF FOR THE SMOOTHNESS OF THE… · p. 18

Bounding the scale-variant parameters

  • With bounded initial g, the proof establishes that g remains bounded throughout training.It propagates bounds through the network using back-propagation, bounded gradients, and induction across layers.Source: C PROOF FOR THE SMOOTHNESS OF THE… · p. 19

Verifying smoothness

  • With bounded initial g, the modified objective Φ satisfies the assumptions in Section 2.4.The proof uses a compact parameter set containing the points between successive iterates to obtain uniform smoothness bounds.Source: C PROOF FOR THE SMOOTHNESS OF THE… · p. 19

D EXPERIMENTS

The experiments compare standard SGD with projected SGD to examine whether BN's auto rate-tuning behavior helps optimization in a modified VGGNet.

Experimental setup

  • The experiments use a modified VGGNet with BN before each ReLU and train it under standard SGD and projected SGD.The network includes convolutional and fully connected layers; its kernels are scale-invariant, while the final BN layer's β and γ parameters are scale-variant.Source: D EXPERIMENTS · p. 20

Experimental comparison

  • Projected SGD rescales each scale-invariant parameter after every step to preserve its pre-step norm, removing learning-rate adaptivity in the intrinsic optimization problem.The two training settings are compared to assess whether BN's auto-tuning behavior is effective in practice.Source: D EXPERIMENTS · p. 20
  • Figure 1 relates training loss to the scale-invariant learning rate while fixing the scale-variant learning rate at 0.1.Its left panel averages the last five epochs; its right panel shows each epoch.Source: Figure 1 · p. 20

D.1 SEPARATE LEARNING RATES

The experiments compare standard and projected SGD across separate and unified learning-rate settings. Standard SGD retains low training loss at larger learning rates, whereas projected SGD and SGD without BN fail to do so in the unified-rate setting.

D.1 SEPARATE LEARNING RATES

  • The experiments train both settings for 100 epochs with rates from 10^-2 to 10^2.The rates are varied for the scale-invariant parameters in the separate-rate setting and shared across parameter groups in the unified-rate setting.Source: §D.1 · p. 20, §D.2 · p. 22

D.2 UNIFIED LEARNING RATE

  • With a unified learning rate, standard SGD's training loss converges to zero, while projected SGD and SGD without BN fail at large rates, sometimes diverging or producing NaN.Figure 2 plots training loss against learning rate; for rates above 10, the projected-SGD and no-BN losses are too large or NaN to appear.Source: Figure 2 · p. 21, §D.2 · p. 22

D.1 SEPARATE LEARNING RATES

  • With separate rates and the scale-variant rate fixed at 0.1, standard SGD reaches zero training loss at all tested scale-invariant rates, while projected SGD becomes stuck at larger rates.At small rates such as 0.1, the two training processes are similar; the authors note the tested network's nonsmooth loss prevents direct application of their theory.Source: §D.1 · p. 22

D.3 GENERALIZATION

The settings can reach different convergence points despite convergence of training loss, and those differences are relevant to test performance. In the reported comparison, Setting 1 maintains higher test accuracy across learning rates while Setting 2 underfits at larger rates.

D.3 GENERALIZATION

  • Different convergence points can result despite training-loss convergence in Setting 1, and these points lead to different test-data performances.Source: §D.3 · p. 22
  • BN’s auto-tuning behavior is suggested to benefit generalization by allowing a wider range of learning rates while still converging to small test error.The passage attributes Setting 2’s poorer performance at large learning rates to failure to fit the training data well.Source: §D.3 · p. 22
  • Above 75%, Setting 1 test accuracy remains as the unified learning rate varies, while Setting 2 accuracy decreases when it exceeds 0.1.The comparison also includes separate learning rates with the scale-variant parameter rate fixed at 0.1.Source: §D.3 · p. 22

Related papers

Loading 1812.03981v1…