PaperlayerView exact revision on arXiv

Source-linked AI summary

No More Pesky Learning Rates

Tom Schaul, Sixin Zhang, Yann LeCun

arXiv:1206.1106v2stat.MLcs.LG

TL;DR

SGD performance depends on manually tuned learning rates and schedules, especially for non-stationary data. The paper derives adaptive rates from local gradient variation to minimize expected next-update loss, allowing rates to increase or decrease. Across convex and non-convex tasks, the method favorably matches systematically tuned SGD and adaptive methods while removing learning-rate tuning.

  • Problem

    SGD requires manual initial-rate and annealing-schedule tuning, while existing adaptive methods retain sensitive hyper-parameters and AdaGrad decreases rates monotonically.

  • Method

    The method derives and estimates global, per-parameter, or block-specific learning rates from gradient variance and local curvature to minimize expected loss after the next update.

  • Results

    Across convex and non-convex tasks, untuned methods compare favorably with systematically tuned ideal SGD and previous adaptive schemes.

  • Takeaways & Limitations

    The adaptive approach can increase rates when non-stationary data change and decrease them during stable periods, making SGD more robust without manual tuning.

  • Takeaways & Limitations

    The method’s curvature approximation can drive η∗ to infinity when curvature approaches zero, requiring a lower bound for numerical stability.

Abstract

from arXiv · show

The performance of stochastic gradient descent (SGD) depends critically on how learning rates are tuned and decreased over time. We propose a method to automatically adjust multiple learning rates so as to minimize the expected error at any one time. The method relies on local gradient variations across samples. In our approach, learning rates can increase as well as decrease, making it suitable for non-stationary problems. Using a number of convex and non-convex learning tasks, we show that the resulting algorithm matches the performance of SGD or other adaptive approaches with their best settings obtained through systematic search, and effectively removes the need for learning rate tuning.

1. Introduction

SGD scales well and can generalize effectively, but strong performance typically requires manually tuning initial and scheduled learning rates. The paper introduces tuning-free adaptive rates and reports favorable comparisons with optimally tuned alternatives.

  • SGD suits large-scale learning because it scales benignly with dataset size and parameter count while sometimes improving generalization over batch methods.
  • Good SGD performance requires manually adjusting each problem’s initial learning rate and designing an annealing schedule for stationary data.The tuning problem is particularly acute for non-stationary data.
  • The paper proposes automatically adjusting possibly different learning rates for parameters to minimize an estimate of expected loss at any one time.
  • The method derives learning rates from gradient-variance estimates and offers global, per-parameter, and block-level variants without parameter tuning.The derivation begins with quadratic, separable per-sample loss contributions; both sample variability and local curvature are estimated in practice.
  • Without manual tuning, the methods compare favorably with ideal SGD using systematically searched rates and with previous adaptive schemes across convex and non-convex tasks.

2. Background

SGD learning-rate schedules and adaptive methods address optimization sensitivity but retain tuning burdens and, in AdaGrad, irreversible decay. The paper instead targets a next-update-optimal rate that can respond to changing data.

  • SGD learning rates are commonly decreased with η(t) = η0(1 + γt)^−1, whose hyper-parameters affect convergence speed.
  • Adaptive approaches include global or diagonal preconditioning, natural-gradient updates, Natural Newton, and AdaGrad.These methods adapt rates using gradient statistics, curvature-related information, or worst-case analysis.
  • Existing adaptive methods retain sensitive hyper-parameters requiring tuning, while AdaGrad’s accumulated gradients force its learning rate to decrease monotonically.The monotonic decrease is especially problematic for non-stationary problems and can also hinder stationary optimization as landscape properties change.
  • The paper’s formula gives the learning rate that maximally decreases expected loss after the next update.Approximations based on gradient means and variances make the rate practical; it decreases toward zero near an optimum and grows when non-stationary data change.
  • The idealized loss illustration averages quadratic per-sample contributions whose minima surround θ∗, assuming identical curvatures.

3. Optimal Adaptive Learning Rates

Under locally quadratic, separable assumptions, the paper derives greedy learning rates that minimize expected loss after the next SGD update. The rates can be estimated component-wise, globally, or by parameter blocks, and the resulting dynamics converge for the quadratic model.

  • The analysis derives an optimal learning-rate schedule for an idealized quadratic, separable loss while preserving SGD convergence guarantees.
  • The greedy rate η∗(t) minimizes expected loss after the next update, using the SGD update and the expected post-update loss.
  • 3.1. Noisy Quadratic Loss: Per-sample losses are modeled as smooth near minima and locally approximated by quadratic functions with sample-specific optima.The sample optima have mean θ∗ and variance Σ.
  • 3.1. Noisy Quadratic Loss: Assuming identical diagonal Hessians and ignoring off-diagonal variance terms reduces the analysis to independent one-dimensional problems.
  • Gradient variance lowers the rate below the noiseless optimum η∗(t) = h^−1, especially near an optimum, reducing expected error from gradient noise.
  • With η∗(t), the algorithm converges almost surely for the quadratic model.
  • The method supports individual, global, or block-specific learning rates, with block rates useful when gradient magnitudes differ across deep-learning layers.

4. Approximations

The method approximates optimal learning rates using online estimates of gradient statistics and curvature, with an adaptive memory that reduces tuning sensitivity.

  • The global learning-rate case requires estimating maximal curvature h+ = max_i(h_i).The paper notes that this can be done efficiently with diagonal Hessian estimates.
  • Optimal learning rates combine inverse curvature with gradient noise relative to the expected squared gradient norm.The paper calls the true-value version the “oracle” variant.
  • Online estimates of the required quantities use an exponential moving average with time-constant τ.The estimates include average gradient components, uncentered gradient variances, and squared gradient-vector length.
  • Adaptive memory increases when steps are small and decays quickly after a large, near-Newton step.This update is designed to track the appropriate recent-history size.
  • Adaptive memory removes one tuning-sensitive hyper-parameter, while the updates remain independent of local curvature and therefore scale-invariant.Initialization averages a small sample subset and uses a slow-start heuristic to improve estimate accuracy during startup.
  • The implementation uses bbprop for positive diagonal Hessian estimates and exponential averaging of these quantities.A lower curvature bound h_i ≥ ϵ can prevent η* from diverging, although it was unnecessary in the reported experiments because of L2 regularization.

5. Adaptive Learning Rate SGD

The paper presents global, local, and blockwise variants of variance-based SGD and compares them with fixed and cooling schedules on noisy and non-stationary losses.

  • vSGD views each parameter component in isolation, while the proposed variants span local, global, and block-specific learning rates.The variants address the trade-off between robust global estimates and less-robust dimension- or block-specific estimates.
  • In the noisy quadratic experiment, vSGD initially descends as fast as the largest fixed learning rate, then reduces its rate to damp oscillations and continue lowering loss.The tuned η = 1/t schedule outperforms vSGD, whereas η = 0.2/t produces catastrophic loss despite rates close to the oracle.
  • All vSGD variants have linear time and space complexity, with roughly a factor-two overhead from an additional bbprop pass.The extra cost can be trivially parallelized and skipped for some updates.
  • When the target changes every 300 steps, vSGD increases its learning rate after each abrupt change instead of remaining decayed.During static intervals it decays like 1/t, and its average loss is substantially better than any SGD cooling schedule.

6. Experiments

The experiments evaluate vSGD variants against tuned SGD and adaptive methods across quadratic, convex, and non-convex tasks. Across benchmark setups, vSGD-l performs especially strongly without manual tuning, while non-stationary tests show adaptive rates responding to distribution changes.

  • Experimental scope: The experiments cover noisy quadratic problems, MNIST and CIFAR benchmarks, and convex and non-convex neural-network models.The benchmark suite includes logistic regression, multilayer perceptrons, and an autoencoder for classification and reconstruction.
  • Non-stationary quadratic: vSGD adapts learning rates during non-stationary training, initially moving quickly toward the optimum and responding automatically when the data distribution changes.Its learning rate decreases during stable periods and increases after abrupt changes in the optimum.
  • Figures: Figures 5–7 plot training versus test error, showing tuned settings as larger symbols and comparing local benchmark views with a global view.Figure 5 notes consistently good untuned vSGD performance on MNIST, while Figure 6 highlights more overfitting on CIFAR, including vanilla SGD.
  • Evaluation protocol: The evaluations average ten independent runs, while competing methods receive benchmark-specific hyperparameter tuning.The tables report training and test errors after 6 epochs and compare against tuned SGD, AdaGrad, SMD, Amari, and Almeida.
  • Results: vSGD-l is the best-performing vSGD variant across the reported benchmarks, using the most aggressive one-rate-per-dimension adaptation.It is almost always significantly better than best-tuned SGD or AdaGrad on training error and better or statistically equivalent to best-tuned SGD in 4 out of 6 test cases.
  • Results: The C0 test result is the main outlier, where aggressive element-wise learning rates led to overfitting, likely because the dataset was comparatively small.The passage connects this test behavior to the corresponding training error.

7. Conclusions

The paper derives adaptive learning rates from gradient statistics and validates them across classical learning problems. The resulting approach removes manual learning-rate search and adapts to changing data distributions and optimization conditions.

  • Method: The method derives an optimal per-update learning rate, optionally per parameter, from the expected gradient norm and expected squared gradient norm.The derivation begins with quadratic loss contributions and targets the expected loss after the next update.
  • Results: Experiments report that adaptive learning rates eliminate manual learning-rate tuning and systematic search for the best value.This conclusion is stated as confirmation of the theoretical prediction.
  • Practical consequence: In non-stationary online settings, the approach increases rates after distribution changes and decreases them during stable periods.The authors associate this behavior with robustness to dynamic optimization landscapes.
  • Practical consequence: Validation on varied classical large-scale learning problems is presented as supporting an out-of-the-box use of SGD.The authors frame this as a hoped-for practical outcome.

A. Convergence Proof

For the quadratic model, the adaptive learning-rate schedule preserves convergence: the loss forms a positive super-martingale and converges almost surely to the optimum.

  • A. Convergence Proof: The adaptive schedule yields almost-sure convergence for the quadratic model.The proof uses classical Lyapunov stability techniques.
  • A. Convergence Proof: J(θ(t)) is a positive super-martingale, so it converges almost surely to a limiting value J∞.
  • A. Convergence Proof: The limiting loss equals the optimum, J∞ = J(θ∗) = 1.
  • A. Convergence Proof: The telescoping sum implies E[η∗(t)] → 0, and therefore η∗(t) → 0 in probability.

B. Derivation of Global Learning Rate

The global learning-rate derivation provides an adaptive time-constant for the global case.

  • B. Derivation of Global Learning Rate: The global case uses an adaptive time-constant as part of the learning-rate construction.

C. SMD Implementation

The implementation section specifies updates for stochastic meta-descent using global learning rates and identifies its three hyper-parameters.

  • C. SMD Implementation: The SMD implementation uses updates based on global learning rates.
  • C. SMD Implementation: The three hyper-parameters are the initial learning rate η0, meta-learning rate µ, and time constant τ.The auxiliary vector v is updated using τ.

D. Sensitivity to Initialization

Initialization parameter C matters mainly through stability: values below a critical minimum are unstable, while sufficiently large values do not affect performance.

  • D. Sensitivity to Initialization: Once C is sufficiently large, changing it does not affect performance.Larger C values only slow initial steps while exponential averages become accurate.
  • D. Sensitivity to Initialization: C = d/10 is proposed as a safe rule-of-thumb choice for the initialization constant.It is ten times larger than the observed critical value for every benchmark.
  • D. Sensitivity to Initialization: Below a critical minimum value of C, the algorithm becomes unstable.
Loading 1206.1106v2…