PaperlayerView exact revision on arXiv

Source-linked AI summary

Continual Backprop: Stochastic Gradient Descent with Persistent Randomness

Shibhansh Dohare, Richard S. Sutton, A. Rupam Mahmood

arXiv:2108.06325v3cs.LG

TL;DR

Non-stationary learning requires adaptation across many changes, but prior work tested relatively few such changes. This paper proposes Continual Backprop, which continually injects random features using generate-and-test; it reports that Backprop degrades over time while Continual Backprop adapts, though its tester is heuristic-based.

  • Problem

    Prior work on non-stationary problems had limited testing across many distribution changes, despite their relevance to real-world continual interaction.

    Source: §1 · p. 1

  • Method

    Continual Backprop extends initialization benefits throughout learning by continually injecting random features alongside gradient descent through a generate-and-test process.

    Source: §1 · p. 2

  • Results

    Backprop loses its ability to adapt over time in problems with many non-stationarities, whereas Continual Backprop is reported to adapt continually, including after thousands of changes.

    Source: §1 · p. 2, §6 · p. 8

  • Takeaways & Limitations

    The results identify decaying plasticity in Backprop and present Continual Backprop as an algorithm that extends initialization benefits throughout learning.

    Source: §6 · p. 8

    The Continual Backprop tester is heuristic-based, and the authors identify more principled testers as future work.

    Source: §6 · p. 8

Abstract

from arXiv · show

The Backprop algorithm for learning in neural networks utilizes two mechanisms: first, stochastic gradient descent and second, initialization with small random weights, where the latter is essential to the effectiveness of the former. We show that in continual learning setups, Backprop performs well initially, but over time its performance degrades. Stochastic gradient descent alone is insufficient to learn continually; the initial randomness enables only initial learning but not continual learning. To the best of our knowledge, ours is the first result showing this degradation in Backprop's ability to learn. To address this degradation in Backprop's plasticity, we propose an algorithm that continually injects random features alongside gradient descent using a new generate-and-test process. We call this the \textit{Continual Backprop} algorithm. We show that, unlike Backprop, Continual Backprop is able to continually adapt in both supervised and reinforcement learning (RL) problems. Continual Backprop has the same computational complexity as Backprop and can be seen as a natural extension of Backprop for continual learning.

1 INTRODUCTION

Backprop is effective on stationary problems but does not work well in non-stationary settings, where adapting to changes matters for applications such as robotics. This paper studies adaptation across many distribution changes and proposes Continual Backprop, which continually injects random features alongside gradient descent.

1 INTRODUCTION

  • The paper situates non-stationarity in applications such as robotics and identifies causes including complexity, partial observability, other actors, and environmental change.Prior methods addressed remembering information or adapting quickly, but the latter were not tested on many non-stationarities.Source: §1 · p. 1
  • Prior work on non-stationary problems was limited in its testing of many distribution changes: most studies considered fewer than ten, while Finn et al. (2019) studied up to a hundred.The paper notes that many changes matter for systems that continually interact with the real world.Source: §1 · p. 1
  • The paper focuses on adapting to changes rather than remembering previously learned information, and studies problems with thousands of non-stationarities.It introduces semi-stationary online supervised problems, where the input distribution changes while the target function stays fixed, and also studies non-stationary RL.Source: §1 · pp. 1–2
  • Backprop performs well initially in non-stationary problems but its performance degrades over time, while Continual Backprop is proposed to extend initialization benefits throughout learning.The authors hypothesize that degradation occurs because the benefits of the initial random distribution are not present at all times.Source: §1 · p. 2
  • Continual Backprop continually injects random features alongside SGD through a generate-and-test mechanism that replaces low-utility features with proposed new ones.The authors report that CBP can continually adapt in non-stationary problems, unlike Backprop.Source: §1 · p. 2

2 NON-STATIONARY PROBLEMS

The paper studies continual adaptation in semi-stationary supervised problems and non-stationary reinforcement learning, using online next-sample performance rather than retention of previously seen data. Its test problems include Bit-Flipping, permuted MNIST, and Slippery Ant.

2 NON-STATIONARY PROBLEMS

  • The experiments cover an idealized semi-stationary problem, online permuted-MNIST classification, and non-stationary reinforcement learning.The idealized problem is intended for inexpensive, extensive study without confounders of more complex problems.Source: §2 · p. 2

Performances measure in semi-stationary problems

  • Online performance is measured by loss on the next sample as learning and evaluation happen together; performance on old data is omitted because the study does not examine forgetting.This distinguishes the evaluation from offline learning followed by a separate evaluation phase.Source: Performances measure in… · p. 2

2.1 BIT-FLIPPING PROBLEM

  • In Bit-Flipping, consecutive samples depend on the previous sample, the target is more complex than the learner, and the best approximation continually changes as the input distribution is non-stationary.Source: §2.1 · p. 2
  • In Bit-Flipping, one of the first f bits is randomly selected and flipped every T time-steps, while each of the remaining m−f bits is sampled independently from U{0, 1} at every step.The experiments use m=20, f=15, and T=1e4; squared error measures performance on the scalar regression output.Source: §2.1 · p. 3

2.2 PERMUTED MNIST

  • Online permuted MNIST presents 60,000 images in random order, then changes the pixel permutation before repeating the sequence.The images are classified into 10 classes, and online classification accuracy is measured.Source: §2.2 · p. 3

2.3 SLIPPERY ANT

  • Slippery Ant changes ground friction every 10M time-steps, sampling the new value loguniformly from [1e−4, 1e4].The task is a continual, non-stationary variant of Pybullet’s Ant problem, whose standard friction value is 1.5.Source: §2.3 · p. 3

3 BACKPROP LOSES THE ABILITY TO ADAPT UNDER EXTENDED TRACKING

Backprop loses its ability to adapt during extended tracking: performance worsens in Bit-Flipping and permuted MNIST, with related results reported for Adam and varied network sizes and change rates. The paper suggests that optimized weights lose useful properties of the initial random distribution.

3 BACKPROP LOSES THE ABILITY TO ADAPT UNDER EXTENDED TRACKING

  • The Bit-Flipping learner has one hidden layer with 5 units while the target network has 100, and the experiment compares multiple activations and step-sizes over 100 runs.The activations include tanh, sigmoid, ReLU, Leaky-ReLU, ELU, and Swish; SGD or Adam is used for updates.Source: §3 · p. 3
  • Backprop’s performance worsens over time for all step-sizes in Bit-Flipping and permuted MNIST, and the reported degradation also occurs with Adam.For ReLU on Bit-Flipping, performance becomes worse than the linear learner.Source: Figure 2 · p. 4, Figure 3 · p. 4, §3 · p. 4
  • Backprop’s performance drops across a wide range of network sizes and distribution-change rates, supporting the authors’ characterization of decaying plasticity as general.The appendix results are identified as Figures 18 and 20.Source: §3 · p. 4
  • After gradient updates, weights are optimized for the recent input distribution rather than remaining at their small random starting values, changing the starting point for the next solution.The authors hypothesize that initial random features, non-saturation, and small weight magnitudes may support fast adaptation.Source: §3 · p. 4

4 CONTINUAL BACKPROP

Continual Backprop (CBP) combines gradient descent with generate-and-test feature replacement to extend initialization’s random-feature benefits throughout learning. In the reported experiments, CBP maintains performance better than Backprop in semi-stationary and non-stationary reinforcement-learning problems.

4 CONTINUAL BACKPROP

  • Feature utility combines contribution to downstream units with adaptability, measured using mean-corrected activation contributions and inverse incoming-weight magnitude.The contribution term aggregates utility across outgoing connections; the adaptation term reflects how quickly the feature can change its represented function.Source: §4 · p. 5, Figure 4 · p. 5
  • CBP combines Backprop with generate-and-test, replacing low-utility features with random features from the initial distribution while keeping memory constant.New features’ outgoing weights are set to zero, and they are protected from replacement until they pass the maturity threshold.Source: §4 · pp. 4–6

Continual Backprop in semi-stationary problems

Continual Learning in a non-stationary RL problem

5 RELATED WORKS

Prior continual-learning work studied remembering past information and adapting to changing streams, but often used few non-stationarities or offline evaluation. Research on initialization established its importance for offline learning, while its benefits beyond initialization remained underexamined.

5 RELATED WORKS

  • Continual learning has two goals—remembering useful information and finding new information as data change—and this work focuses on the latter.Forgetting previously learned information remains an unsolved problem for current deep-learning methods.Source: §5 · p. 8
  • Most prior studies examined fewer than ten non-stationarities, while Finn et al. (2019) studied up to a hundred; none of the cited prior works studied thousands.Most works used offline learning and evaluation with only a handful of non-stationarities; Finn et al. (2019) studied a fully online setting but required storing all data seen so far.Source: §5 · p. 8
  • Initialization research established the importance of suitable weight scales for gradient flow and avoiding sigmoid saturation, but largely studied offline learning.The benefits of initialization beyond the beginning of learning had been overlooked.Source: §5 · p. 8

6 CONCLUSION AND LIMITATIONS

With many non-stationarities, Backprop’s performance degrades over time and it loses the ability to adapt. The paper proposes Continual Backprop, while identifying its heuristic tester as the main limitation.

6 CONCLUSION AND LIMITATIONS

  • Backprop’s performance degrades over time in problems with many non-stationarities, revealing a decaying-plasticity problem that can make it unsuitable for continual adaptation.The authors describe this as the first result showing degradation in Backprop’s ability to adapt.Source: §6 · p. 8
  • Continual Backprop continually combines gradient descent with random features through a generate-and-test process.The paper reports adaptation after thousands of non-stationarities and says its generate-and-test algorithm is the first compatible with modern deep learning.Source: §6 · p. 8
  • Backprop with L2 regularization adapts continually in some problems but fails in many others.Source: §6 · p. 8
  • The main limitation is that Continual Backprop’s tester is based on heuristics; more principled testers are proposed as future work to improve its foundations.Source: §6 · p. 8
  • The authors argue that current Backprop systems and variants are not stable in non-stationary problems and anticipate work on better Continual Backprop algorithms.Source: §6 · p. 8

A MORE EXPERIMENTS WITH BACKPROP ON THE BIT-FLIPPING PROBLEM

Backprop’s performance worsens over time across activation functions and optimizers in the reported Bit-Flipping experiments. Longer runs reveal degradation even at a small step size.

A MORE EXPERIMENTS WITH BACKPROP ON THE BIT-FLIPPING PROBLEM

  • Figure 10 shows Backprop’s performance worsening over time for all tested activation functions on Bit-Flipping.Source: A MORE EXPERIMENTS WITH BACKPROP ON… · p. 11
  • For a step-size of 0.001, Backprop’s error for all activations increases significantly or stays high after tracking for 5M examples.Figure 2 and Figure 10 cover 1M examples; Figure 11 extends the small-step-size run to 5M and bins online prediction error into 20,000-example bins with standard-error shading.Source: A MORE EXPERIMENTS WITH BACKPROP ON… · p. 11
  • At step-size 0.001, after 5M examples Backprop’s error for all activations increases significantly or remains high, including with Adam.For Adam, the experiments used betas (0.9, 0.999).Source: A MORE EXPERIMENTS WITH BACKPROP ON… · p. 11
  • Backprop’s performance worsens over time with Adam across a wide range of step sizes and activation functions.Figure 12 reports the wide-range comparison; Figure 13 shows the longer 5M-example run at step-size 0.001.Source: A MORE EXPERIMENTS WITH BACKPROP ON… · p. 11

B MORE EXPERIMENTS WITH CBP ON THE BIT-FLIPPING PROBLEM

The additional Bit-Flipping experiments report that CBP with Adam outperforms Backprop with Adam across a wide range of replacement rates. The appendix also describes optimizer-state resets when features are replaced.

B MORE EXPERIMENTS WITH CBP ON THE BIT-FLIPPING PROBLEM

  • Figure 14 reports online performance and full-experiment average loss for remaining activation functions across CBP replacement rates and Backprop weight-decay values.The full experiment covers 1M examples.Source: B MORE EXPERIMENTS WITH CBP ON THE… · p. 11
  • When CBP replaces a feature under Adam, it resets that feature’s estimated gradient, squared-gradient estimate, and timestep to zero.Source: B MORE EXPERIMENTS WITH CBP ON THE… · p. 11
  • CBP with Adam performs significantly better than Backprop with Adam across a wide range of replacement rates.This comparison is reported in Figures 15 and 16.Source: B MORE EXPERIMENTS WITH CBP ON THE… · p. 11
  • The Figure 10 Bit-Flipping curve shows Backprop performing well initially before worsening over time for all tested activation functions.Source: Figure 10 · p. 12

C ABLATION STUDY FOR THE UTILITY MEASURE

The ablation compares utility measures in Bit-Flipping and Slippery Ant. On Slippery Ant, overall utility outperforms the other tested utility measure and remains close to its initial performance near the end.

C ABLATION STUDY FOR THE UTILITY MEASURE

D CONTINUAL PPO

The Continual PPO experiments specify policy and value network architectures and select the best-performing settings for CPPO and PPO+L2.

D CONTINUAL PPO

  • CPPO and PPO+L2 use separately selected best-performing settings; CPPO sweeps six replacement-rate and maturity-threshold pairs.Source: D CONTINUAL PPO · p. 12
  • The policy network uses two 256-unit tanh layers, a linear output, and a standard-deviation variable.Source: D CONTINUAL PPO · p. 12
  • The value network uses two 256-unit tanh layers and a linear output.Source: D CONTINUAL PPO · p. 12

E COMPUTE USED

Appendix experiments compare learning algorithms, report compute requirements, and test how distribution-change speed relates to performance decay.

E COMPUTE USED

  • Bit-Flipping experiments used around 12,960 CPU-days; Permuted-MNIST used 110 GPU-days, and non-stationary RL used 1,980 CPU-days.Source: E COMPUTE USED · pp. 12, 16
  • After 5M steps or examples, step-size 0.001 error either increases significantly or remains significantly higher for SGD, and increases for Adam.Source: Figure 11 · p. 13, Figure 13 · p. 14
  • After initially performing well, Adam error rises for all activation functions during extended tracking.Source: Figure 12 · p. 13
  • For SGD and Adam on Bit-Flipping, CBP and BP+L2 remain robust while other algorithms degrade; their relative performance varies with activation and hyperparameters.Source: Figure 14 · p. 14, Figure 15 · p. 15, Figure 16 · p. 15

F AFFECT OF THE SPEED OF THE DISTRIBUTION CHANGE ON DECAYING PLASTICITY

G A DEEPER LOOK IN THE NETWORKS: FEATURE SATURATION AND VANISHING GRADIENTS

The network analyses associate Backprop's later performance decline partly with feature saturation and smaller input-weight gradients, while showing that smaller networks decline faster.

G A DEEPER LOOK IN THE NETWORKS: FEATURE SATURATION AND VANISHING GRADIENTS

H AFFECT OF NETWORK SIZE ON DECAYING PLASTICITY

Related papers

Loading 2108.06325v3…