PaperlayerView exact revision on arXiv

Source-linked AI summary

Understanding Short-Horizon Bias in Stochastic Meta-Optimization

Yuhuai Wu, Mengye Ren, Renjie Liao, Roger Grosse

arXiv:1803.02021v1cs.LGstat.ML

TL;DR

Gradient-based meta-optimization often uses short horizons because each meta-update unrolls many training steps, though the goal is performance over much longer training. The paper analyzes this short-horizon bias on a noisy quadratic and tests offline and online meta-optimization, finding that short horizons favor small learning rates and can underperform hand-tuned training.

  • Problem

    Gradient-based meta-optimization unrolls the base training procedure thousands of times, so its meta-objective uses a much shorter horizon than the long training horizon of interest.

    Source: §1 · pp. 1–2

  • Method

    The paper analyzes short- and long-horizon learning-rate schedules on a noisy quadratic and tests offline schedule fitting and online learning-rate adaptation for neural-net training.

    Source: §1 · p. 2, §4 · p. 10

  • Results

    Short-horizon meta-optimizers can dramatically underperform a hand-tuned fixed learning rate; on stochastic, ill-conditioned quadratics, greedy schedules decay too quickly and achieve worse long-run performance.

    Source: §1 · p. 2, §4 · p. 11

  • Takeaways & Limitations

    Short-horizon meta-optimization should not be applied blindly; removing ill-conditioning or stochasticity may make it work well, but whether existing algorithms can do so remains uncertain.

    Source: §4 · p. 11

    The experiments give meta-optimizers sufficient time to optimize their objectives, unlike practical methods that may optimize them less thoroughly.

    Source: §3 · p. 7

Abstract

from arXiv · show

Careful tuning of the learning rate, or even schedules thereof, can be crucial to effective neural net training. There has been much recent interest in gradient-based meta-optimization, where one tunes hyperparameters, or even learns an optimizer, in order to minimize the expected loss when the training procedure is unrolled. But because the training procedure must be unrolled thousands of times, the meta-objective must be defined with an orders-of-magnitude shorter time horizon than is typical for neural net training. We show that such short-horizon meta-objectives cause a serious bias towards small step sizes, an effect we term short-horizon bias. We introduce a toy problem, a noisy quadratic cost function, on which we analyze short-horizon bias by deriving and comparing the optimal schedules for short and long time horizons. We then run meta-optimization experiments (both offline and online) on standard benchmark datasets, showing that meta-optimization chooses too small a learning rate by multiple orders of magnitude, even when run with a moderately long time horizon (100 steps) typical of work in the area. We believe short-horizon bias is a fundamental problem that needs to be addressed if meta-optimization is to scale to practical neural net training regimes.

1 INTRODUCTION

Because gradient-based meta-optimization makes long unrolls expensive, its objectives use much shorter horizons than practical neural-net training. The paper analyzes and demonstrates how this mismatch favors short-term loss reduction over long-run progress, while identifying few-shot learning as a setting where short horizons can be appropriate.

1 INTRODUCTION

  • Because gradient-based meta-optimization repeatedly unrolls base training, its expense forces meta-objectives to use horizons far shorter than those relevant to large-scale optimization.The paper names the resulting short-term versus long-term performance tradeoff short-horizon bias.Source: §1 · pp. 1–2
  • The analysis derives greedy-optimal learning rates and momentum in closed form and locally minimizes long-horizon loss to compare short- and long-horizon schedules.It uses a noisy quadratic cost function whose stochastic-gradient dynamics with momentum can be analyzed exactly.Source: §1 · p. 2
  • On stochastic, ill-conditioned quadratics, greedy schedules reduce high-curvature fluctuations but sacrifice low-curvature progress; aggressive learning rates followed by decay can ultimately achieve lower loss.Figure 2 also shows that short-lookahead fixed-rate objectives favor small rates, while trajectories followed by 50 decay steps favor higher rates.Source: §1 · p. 2, Figure 1 · p. 2, Figure 2 · p. 2
  • Short-horizon offline and online meta-optimizers dramatically underperform a hand-tuned fixed learning rate, sometimes slowing base-level progress to a crawl even at 100- or 1000-step horizons.The experiments give the meta-optimizers sufficient time to optimize their objectives, focusing the comparison on the objective horizon.Source: §1 · p. 2
  • Short-horizon meta-optimization can directly suit few-shot learning, but the paper identifies short-horizon bias as an obstacle to using meta-optimization for large-network training.The conclusion expects uncorrected meta-objectives to fail when run for much longer horizons than those on which they were trained.Source: §1 · pp. 2–3

2 NOISY QUADRATIC PROBLEM

The section models SGD with momentum on noisy quadratics, derives horizon-optimized and greedy schedules, and compares their behavior analytically and experimentally. In the stochastic, ill-conditioned case, greedy schedules decay too quickly, whereas the optimized schedule achieves a lower final expected loss.

2.1 BACKGROUND

  • Quadratic approximations underpin neural-network optimization methods, and deterministic quadratic objectives make greedy learning-rate and momentum choices optimal; this property fails in stochastic settings.Source: §2.1 · p. 3

2.2.1 NOTATIONS

  • Here, “velocity” names the gradient trace and “momentum” its decay constant; the analysis adapts scalar learning rate and momentum across dimensions.Source: §2.2.1 · p. 4, §2.2.3 · p. 4

2.2.2 PROBLEM FORMULATION

  • The noisy quadratic model samples a Gaussian-distributed minimum at each step, producing noisy gradient observations, and assumes diagonal Hessian and noise covariance.Source: §2.2.2 · p. 4

2.2.3 OPTIMIZED AND GREEDY-OPTIMAL SCHEDULES

  • The optimized schedule minimizes expected loss at a specified horizon, whereas the greedy schedule chooses learning rate and momentum to minimize next-step expected loss.The paper derives mean and variance recurrences, then uses them to fit the horizon-optimized schedule.Source: §2.2.3 · p. 5

2.2.4 UNIVARIATE AND SPHERICAL CASES

  • For a univariate noisy quadratic, the full-horizon optimal learning-rate sequence agrees with the greedy-optimal schedule derived by Schaul et al. (2013).Source: §2.2.4 · p. 5
  • Greedy schedules are optimal when the Hessian and gradient covariance are spherical; whether practical optimizers show this behavior remains an open question.A sufficiently good preconditioner could make them close to spherical.Source: §2.2.4 · pp. 5–6

2.3 EXPERIMENTS

  • 4.25 final expected loss for the optimized schedule, versus 63.86 for the greedy-optimal schedule and 42.19 for the fixed schedule.The optimized schedule maintains a high learning rate initially, allowing progress along low-curvature directions before decaying it after 50 iterations.Source: §2.3 · pp. 6–7
  • The optimized schedule matches the greedy schedule on the deterministic quadratic, while stochasticity is necessary for short-horizon bias to appear.The deterministic schedules are nearly flat, unlike the more complex stochastic schedules.Source: Figure 3 · p. 6, §2.3 · p. 7

3 GRADIENT-BASED META-OPTIMIZATION

The section examines how short lookahead horizons affect gradient-based meta-optimization of learning rates and momentum. In offline and online experiments, optimized learning rates or schedules vary with horizon, and short-horizon choices can slow later training.

3 GRADIENT-BASED META-OPTIMIZATION

  • The experiments use an idealized SMD that adapts learning-rate and momentum hyperparameters, with extra meta-optimization resources to focus on the meta-objective itself.The authors simplify the meta-model and algorithm, aiming to separate meta-objective deficiencies from incomplete meta-optimization.Source: §3 · p. 7, §3.1 · pp. 8–9
  • A schedule encoded implicitly in a learned optimizer can also be tuned for short-term performance, even without an explicit learning-rate parameter.The paper gives Adagrad as an example of an optimizer that implicitly uses a polynomial decay schedule.Source: §3 · p. 7

3.1 BACKGROUND: STOCHASTIC META-DESCENT

  • SMD performs gradient descent on differentiable hyperparameters by unrolling the optimizer and accumulating their gradients through the computation graph.Forward-mode autodiff is practical here because the experiments optimize only a small number of hyperparameters.Source: §3.1 · pp. 7–8

3.2 OFFLINE META-OPTIMIZATION

  • β differed by over two orders of magnitude between 100- and 20k-step horizons; longer-horizon schedules decayed more gradually and ultimately outperformed shorter-horizon training.The 100-step network was severely undertrained, while the 1k-step network had worse test error than longer-horizon networks.Source: Figure 6 · p. 9, §3.2 · pp. 9–10

3.3 ONLINE META-OPTIMIZATION

  • Online SMD quickly drove learning rates very small, leading to slow long-term progress.Runs began from widely varying hyperparameters but behaved similarly.Source: Figure 7 · p. 10, §3.3 · p. 10

4 CONCLUSION

The conclusion reports that short-horizon bias appears in both noisy-quadratic analysis and neural-net meta-optimization. It also identifies possible conditions for reducing the bias, while noting that their feasibility with existing algorithms remains unknown.

4 CONCLUSION

  • Figure 8 compares online SMD with five-step deterministic lookahead against a manually tuned fixed learning rate.The caption identifies the blue and red curves, respectively, and says the other settings match Figure 7.Source: Figure 8 · p. 11
  • The optimal noisy-quadratic schedule keeps learning rates high for progress on low-curvature directions, unlike the greedy schedule, and eventually achieves lower loss.The greedy schedule decays rapidly to reduce loss on high-curvature directions; the analysis attributes its poor performance to the combination of stochasticity and ill-conditioning.Source: §4 · p. 11
  • Offline and online gradient-based meta-optimization reproduce the toy problem’s fast learning-rate decay and poor long-run performance.Source: §4 · p. 11
  • Preconditioning or reducing stochasticity may bring short-horizon meta-optimization into a regime where it works well, but feasibility with existing algorithms remains open.Source: §4 · p. 11

A PROOFS OF THEOREMS

The appendix maps the proofs of three theorems to subsections A.1, A.2, and A.3.

A PROOFS OF THEOREMS

A.1 MODEL DYNAMICS

The model-dynamics subsection recalls the definition of stochastic gradient descent with momentum.

A.1 MODEL DYNAMICS

  • The subsection recalls that stochastic gradient descent with momentum is defined here.Source: §A.1 · p. 13
  • The recalled optimizer is stochastic gradient descent with momentum.Source: §A.1 · p. 13
  • This subsection’s stated focus is the definition of stochastic gradient descent with momentum.Source: §A.1 · p. 13

A.1.1 DYNAMICS OF THE EXPECTATION

This subsection addresses the mean velocity, introduces initial conditions, and refers to equations (10) and (11) for an expectation.

A.1.1 DYNAMICS OF THE EXPECTATION

  • The subsection calculates the mean of the next velocity, v(t+1).Source: §A.1.1 · p. 13
  • It introduces the initial conditions for the derivation.Source: §A.1.1 · p. 14
  • The passage states that Eqs. (10) and (11) describe how E, without providing further information about E or the equations in this excerpt.Source: §A.1.1 · p. 14

A.1.2 DYNAMICS OF THE VARIANCE

This section derives the time evolution of velocity variance and the covariance between parameters and velocity, using specified initial conditions to obtain the dynamics.

A.1.2 DYNAMICS OF THE VARIANCE

  • The section calculates how the variance of velocity v(t+1) changes over time.Source: §A.1.2 · p. 14
  • It also derives how the covariance of θ and v changes over time.Source: §A.1.2 · p. 14
  • The derivation assumes initial conditions and combines the preceding equations to obtain dynamics for t = 0, . . . , T −1.Source: §A.1.2 · p. 14

A.2.1 UNIVARIATE CASE

This section expresses the loss at the next time step and uses its derivatives with respect to learning rate and momentum to find settings that minimize it.

A.2.1 UNIVARIATE CASE

  • The section writes the loss at time step t before deriving settings for the next-step objective.Source: §A.2.1 · p. 15
  • It defines A(·) as the sum of the squared expectation and variance, E[·]^2 + V[·].Source: §A.2.1 · p. 15
  • The optimal learning rate and momentum for minimizing L(t+1) are found by differentiating with respect to α(t) and µ(t) and setting the derivatives to zero.Source: §A.2.1 · p. 15

A.2.2 HIGH DIMENSION CASE

The high-dimensional analysis sums loss across directions, while the following univariate SGD section uses dynamic programming and a recurrence for A(t) to derive the optimal learning-rate schedule.

A.2.2 HIGH DIMENSION CASE

  • In the high-dimensional case, the loss is the sum of losses along all directions.Source: §A.2.2 · p. 15

A.3 UNIVARIATE OPTIMALITY IN SGD

  • The univariate SGD analysis formulates schedule optimization by defining L_min as the minimum expected loss at the final step T.It uses a dynamic programming approach to optimize the sequence of learning rates.Source: §A.3 · p. 16
  • For univariate SGD, the analysis derives a recurrence relation for A(t) and expresses final loss in terms of A(T)_min.Source: §A.3 · pp. 16–17
  • Theorem 4 gives the optimal learning rate at timestep t for the univariate SGD schedule.The derivation proceeds by induction on k and differentiates the minimum loss with respect to the preceding timestep’s learning rate.Source: §A.3 · p. 17
Loading 1803.02021v1…