Continual Backprop: Stochastic Gradient Descent with Persistent Randomness — part 1/3

Cleaned-text code points [0, 15709). Bibliography omitted here; source.md includes it.

# Continual Backprop: Stochastic Gradient Descent with Persistent Randomness

###### Abstract

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 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

In the last decade, deep learning methods have been successful and become the state-of-the-art in many machine learning problems and applications, including supervised classification (Krizhevsky et al., 2012), reinforcement learning (Silver et al., 2016), and natural language processing (Brown et al., 2020). These methods learn the weights of an artificial neural network using Backprop, which is primarily applied to stationary problems. However, a primary challenge to leveraging the strengths of deep learning beyond current applications is that Backprop does not work well in non-stationary problems (McCloskey and Cohen 1989, French 1997, Sahoo et al. 2018), for example, a problem that consists a sequence of stationary problems.

Leveraging the strengths of deep learning methods in non-stationary problems is important as many real-world applications of machine learning like robotics involve non-stationrities. Non-stationarities can arise due to high complexity (Sutton et al., 2007), partial observability (Khetarpal et al., 2020), other actors (Foerster et al., 2018), or changes in the environment (Thurn, 1998). Prior works proposed methods to remember previously learned information (Kirkpatrick et al. 2017, Aljundi et al. 2018, Riemer et al. 2019). Some other works proposed to adapt fast to non-stationarities (Rusu et al. 2016, Al-Shedivat et al. 2018, Finn et al. 2019) although their methods were not tested on many non-stationarities. The number of non-stationarities refers to the number of times the data distribution changes. In this work, we focus on the problem of adapting to changes and not on remembering previous information.

Prior works on non-stationary problems are limited due to their lack of experiments with many non-stationarities. Most works only look at problems with less than ten non-stationarities (Rusu et al. 2016, Kirkpatrick et al. 2017, Al-Shedivat et al. 2018). Finn et al. (2019) studied problems with up to a hundred non-stationarities. Dealing with many non-stationarities is important for systems that continually interact with the real world as non-stationarities frequently occur in the world.

In this work, we study problems with a large number (thousands) of non-stationarities. We start with a special class of problems that we call semi-stationary problems. These are online supervised learning problems where the input distribution is non-stationary while the target function is stationary. The target function is the function being approximated, for example, the true regression function. These problems are a natural way to study many non-stationarities; a slowly changing input distribution in a large input space can cause thousands of non-stationarities. Semi-stationarities are especially relevant in the real world where inputs often depend on previous inputs, making the input distribution non-stationary. Finally, we study a non-stationary RL problem. This is a full non-stationarity problem as the input distribution changes when the agent’s behaviour changes and the target function—optimal policy—changes as the dynamics of the environment change.

We show that in non-stationary problems Backprop performs well initially, but surprisingly, its performance continues to degrade substantially over time. This drop in performance with a changing data distribution indicates that Backprop loses its ability to adapt in non-stationary problems. Backprop relies on proper random initialization for its effectiveness (Glorot et al. 2010, Sutskerver et al. 2013, He et al. 2015). However, randomization in Backprop only happens at the beginning. We hypothesize that Backprop’s ability to adapt degrades because the benefits of initial random distribution are not present at all times.

To extend the benefits of the initial randomization throughout learning, we propose the Continual Backprop (CBP) algorithm. CBP continually injects random features alongside SGD and uses a generate-and-test mechanism that consists of two parts: a generator proposes new features, and a tester finds and replaces low utility features with the features proposed by the generator. We show that unlike BP, CBP can continually adapt in non-stationary problems.

The first contribution of our work is to show that in non-stationary problems with many non-stationarities BP loses its ability to adapt over time. In other words, we contribute to the understanding of why BP and its variant Adam fails in non-stationary problems. Our second contribution is that we propose the CBP algorithm that extends the benefits of the initialization in BP to all times.

## 2 Non-stationary problems

We study Backprop, Continual Backprop, and other learning algorithms in semi-stationary and Reinforcement Learning (RL) problems. First, we consider a novel idealized semi-stationary problem. The strength of this problem is that in this problem we can study continual learning algorithms extensively and yet in a computationally inexpensive way and without the confounders that arise in more complex problems. Then we study the permuted MNIST problem, an online image classification problem, and a non-stationary RL problem. We demonstrate on these problems that the findings from the idealized problem scale to large neural networks in more realistic settings.

Performances measure in semi-stationary problems

In supervised learning, the task is to learn a function using examples of input-output pairs. This function is called the target function. In online supervised learning (Orabona, 2019), there is a stream of samples ( x t , y t ) (x_{t},y_{t}) , and the predictions have to be made sequentially. The performance measure is the loss on the next sample. Thus, learning and evaluation happen simultaneously. This is fundamentally different from offline supervised learning, where there are two separate phases, one for learning and another for evaluation. Another common measure in non-stationary problems is the performance on previously seen data. However, measuring performance on previously seen data is only meaningful when studying the catastrophic forgetting aspect of BP. As we do not study the forgetting problem, we do not measure the performance on old data.

### 2.1 Bit-Flipping problem

Our first problem is the Bit-Flipping problem . It differs slightly from most supervised learning in two ways. First, it is conventionally assumed that samples are independently and identically distributed, whereas we focus on the case where the sample at the current time-step depends on the previous sample. Second, it is often assumed that the learner has sufficient capacity to closely approximate the target function, whereas we assume that the target function is more complex than the learner. The best approximation continually changes in this problem as the input distribution is non-stationary, and the target function has high complexity. Therefore, there is a need for continual adaptation.

The target function in the Bit-Flipping problem is represented by a multi-layered target network . The target network has two layers of weights. We limit the learning networks to networks with the same depth. This allows us to control the relative complexity of the target function and learner. If the target network has a lot more hidden units than the learner, then the target function is more complex than the learner. We set the target network to be wider.

The input at time step t t , x t \textbf{x}_{t} , is a binary vector of size m m . Here, x t ∈ { 0 , 1 } m \textbf{x}_{t}\in{\{0,1\}}^{m} where each element, x i , t ∈ { 0 , 1 } x_{i,t}\in{\{0,1\}} for i i in 1 , … , m 1,...,m . After every T T time-steps, one of the first f f bits is randomly selected and its value is flipped; the values of these f f bits do not change at other times. We refer to the first f f bits as flipping bits . Each of the next m − f m\!-\!f bits is randomly sampled from U ​ { 0 , 1 } U{\{0,1\}} at every time-step. The value of T T allows us to control the correlation among the consecutive values of the input. Note that when a flipping bit flips, the input distribution changes. We use m = 20 m\!=\!20 , f = 15 f\!=\!15 , and T = 1 ​ e ​ 4 T\!=\!1e4 .

In the target network, all weights are randomly sampled from U ​ { − 1 , 1 } U\{-1,1\} . The activation function is a Linear Threshold Unit (LTU), McCulloch (1943). The output of an LTU, with input x t \textbf{x}_{t} is 1 1 if ∑ i = 0 m + 1 v i ​ x i , t > θ i \sum_{i=0}^{m+1}v_{i}x_{i,t}>\theta_{i} else 0 0 . Here, v is the input weight vector. We set θ i = ( m + 1 ) ∗ β − S i \theta_{i}=(m+1)*\beta-S_{i} , where S i S_{i} is the number of input weights with the value of − 1 -1 and β ∈ [ 0 , 1 ] \beta\in[0,1] . This form of LTU is taken from Sutton and Whitehead, (1994). We use β = 0.7 \beta=0.7 . The output of the network at time-step t t is a scalar y t ∈ ℝ y_{t}\in\mathbb{R} . Figure 1 shows the input and the target network. The Bit-Flipping problem is a regression problem; we use the squared error to measure performance.

### 2.2 Permuted MNIST

We use an online variant of the Permuted MNIST problem (Zenke et al., 2017). Zenke et al., (2017) used this problem with just 10 non-stationarities. This is an image classification problem with 10 classes. The images in permuted MNIST are generated from the images in the MNIST dataset by randomly permuting the pixels in the images. We present the images sequentially and measure online classification accuracy. The MNIST dataset has 60,000 images. We present these 60k images in random order, and after all the images have been presented, we use a single permutation to change all the images. This cycle of presenting all the 60k images and then changing the permutation of pixels can be continued indefinitely, which allows us to create a long-term continual learning problem.

### 2.3 Slippery Ant

It is a non-stationary RL problems and is a continual variant of Pybullet’s (Coumans and Bai, 2016) Ant problem. Non-stationary variant is needed as the problems in Pybullet are stationary. In our problems the environment changes after a pre-specified time, making it necessary for the learner to adapt. In our problem, we change the friction between the agent and the ground of the standard Pybullet Ant problem. In the standard problem, the value of the friction is 1.5 1.5 . We change the friction after every 10M time-steps by log-uniformly sampling it from [ 1 ​ e − 4 , 1 ​ e ​ 4 ] [1e\!-\!4,1e4] .

## 3 Backprop loses the ability to adapt under extended tracking

In the Bit-Flipping problem, the learning networks is the network that is used to predict the output. This network has a single hidden layer with 5 hidden units, while the target network has one hidden layer but 100 hidden units. So, the target network is more complex than the learning network. Because the input distribution is changing over time and the target function is more complex than the learner, the best approximation continually changes and thus, there is a need to track the best approximation.

We first used Backprop to track the best approximation. Tracking with Backprop as the learning process in an online supervised learning problem consists of randomly initializing the weights and updating them after every example using the gradient with respect to the loss on the current example. That is, we used Backprop in an incremental manner without any mini-batches.

We studied learning networks with six different non-linear activations: tanh, sigmoid, ReLU (Nair and Hinton, 2010), Leaky-ReLU (Mass et al., 2013) with a negative slope of 0.01, ELU (Clevert et al., 2015), and Swish (Ramachandran et al., 2017). We studied all these networks when they learned using SGD or its variant Adam (Kingma and Ba, 2015).

We used uniform Kaiming distribution (He et al., 2015) to initialize the learning network’s weights. The distribution is U ⁡ ( − b , b ) U(-b,b) with bound, b = g ​ a ​ i ​ n ∗ 3 n ​ u ​ m ​ _ ​ i ​ n ​ p ​ u ​ t ​ s b=gain*\sqrt{\frac{3}{num\_inputs}} , where g ​ a ​ i ​ n gain is chosen such that the magnitude of inputs does not change across layers. For tanh, Sigmoid, ReLU, and Leaky-ReLU, g ​ a ​ i ​ n gain is 5/3, 1, 2 \sqrt{2} , and 2 / ( 1 + α 2 ) \sqrt{2/(1+\alpha^{2})} respectively. For ELU and Swish, we used g ​ a ​ i ​ n = 2 gain=\sqrt{2} , as was done in the original works by Clevert et al. (2016) and Ramachandran et al. (2017).

We used a linear tracker as a baseline in the Bit-Flipping problem. The linear tracker predicts that output as a linear combination of the inputs. The weights for the linear combination are learned with SGD. We chose the step-size parameter that had least total error.

We ran the experiment on the Bit-Flipping problem for 1M examples. For each activation and value of step-size, we performed 100 independent runs. For different activations and values of the step-size parameter, the same 100 sequences of data (input-output pairs) were used.

Figure 2 shows the squared error of different learning networks with different step-sizes during the first 1M examples. We bin the online error into bins of size 20k. The shaded region in the figure shows the standard error of the binned error. To display the degradation for step-size of 0.001 more clearly, we ran the experiment for 5M examples, and the results are presented in Appendix A. In Appendix A, we also show similar results when we used Adam instead of SGD.

In the permuted MNIST problem, we used a feed-forward network with three hidden layers with 2000 hidden units and ReLU activations and SGD for updates.

Figures 2 and 10 show that in the Bit-Flipping problem, for all reasonable step-sizes, the error with SGD either increases significantly. Figures 11 and 12 in the appendix show similar results with Adam. Figure 4 shows that in the permuted MNIST problem, the performance for all steps-sizes gets worse over time. The degradation in performance is slower for smaller step-sizes. From these results, we conclude that Backprop and its variants are not suitable for extended tracking as they continue to lose their ability to adapt over time.

Additionally, Figures 18 and 20 in the appendix show that the performance of Backprop drops for a wide range of rates of distribution change and a wide range of network sizes. These results mean that decaying plasticity is a very general phenomenon, and it happens for a wide range of network sizes and rates of distribution change.