Self-Normalized Resets for Plasticity in Continual Learning

## Abstract

Abstract Plasticity Loss is an increasingly important phenomenon that refers to the empirical observation that as a neural network is continually trained on a sequence of changing tasks, its ability to adapt to a new task diminishes over time. We introduce Self-Normalized Resets (SNR), a simple adaptive algorithm that mitigates plasticity loss by resetting a neuron’s weights when evidence suggests its firing rate has effectively dropped to zero. Across a battery of continual learning problems and network architectures, we demonstrate that SNR consistently attains superior performance compared to its competitor algorithms. We also demonstrate that SNR is robust to its sole hyperparameter, its rejection percentile threshold, while competitor algorithms show significant sensitivity. SNR’s threshold-based reset mechanism is motivated by a simple hypothesis test that we derive. Seen through the lens of this hypothesis test, competing reset proposals yield suboptimal error rates in correctly detecting inactive neurons, potentially explaining our experimental observations. We also conduct a theoretical investigation of the optimization landscape for the problem of learning a single ReLU. We show that even when initialized adversarially, an idealized version of SNR learns the target ReLU, while regularization based approaches can fail to learn.

## 1 Introduction

Plasticity Loss is an increasingly important phenomenon studied broadly under the rubric of continual learning (Dohare et al., ). This phenomenon refers to the empirical observation that as a network is continually trained on a sequence of changing tasks, its ability to adapt to a new task diminishes over time. While this is distinct from the problem of catastrophic forgetting (also studied under the rubric of continual learning (Goodfellow et al., ; Kirkpatrick et al., )), it is of significant practical importance. In the context of pre-training language models, an approach that continually trains models with newly collected data is preferable to training from scratch (Ibrahim et al., ; Wu et al., ). On the other hand, the plasticity loss phenomenon demonstrates that such an approach will likely lead to models that are increasingly unable to adapt to new data. Similarly, in the context of reinforcement learning using algorithms like TD, where the learning tasks are inherently non-stationary, the plasticity loss phenomenon results in actor or critic networks that are increasingly unable to adapt to new data (Lyle et al., ). Figure 1 illustrates plasticity loss in the ‘permuted MNIST’ problem introduced by Goodfellow et al. ().

One formal definition of plasticity measures the ability of a network initialized at a specific set of parameters to fit a random target function using some pre-specified optimization procedure. In this sense, random parameter initializations (eg. Lyle et al. ()) are known to enjoy high plasticity. This has motivated two related classes of algorithms that attempt to mitigate plasticity loss. The first explicitly ‘resets’ neurons that are deemed to have low ‘utility’ (Dohare et al., ; Sokar et al., ). A reset re-initializes the neurons input weights and bias according to some suitable random initialization rule, and sets the output weights to zero; algorithms vary in how the utility of a neuron is defined and estimated from online data. A second class of algorithms perform this reset procedure implicitly via regularization (Ash & Adams, ; Kumar et al., ). These latter algorithms differ in their choice of what to regularize towards, with choices including the original network initialization; a new randomly drawn initialization; or even zero. The aforementioned approaches to mitigating plasticity loss attempt to adjust the training process; other research has studied the role of architectural and optimizer hyper-parameter choices. Across all of the approaches to mitigating plasticity loss described above, no single approach is yet to emerge as both robust to hyper-parameter choices, and simultaneously performant across benchmark problems.

Given some point process consider the task of distinguishing between the hypotheses that this point process has a positive rate (the null hypothesis), or a rate that is identically zero with a penalty for late rejection or acceptance. An optimal test here takes the following simple form:
we reject the null hypothesis as soon as the time elapsed without an event exceeds some percentile of the inter-arrival time under the null hypothesis and otherwise accept immediately upon an event. Viewing the firing of a neuron as such a point process, we propose to reset a neuron based on a rejection of the hypothesis that the the neuron is firing at a positive rate. We use the histogram of past inter-firing times as a proxy of the inter-arrival time distribution under the null hypothesis. This exceedingly simple algorithm is specified by a single hyper-parameter: the rejection percentile threshold. We refer to this procedure as self-normalized resets (SNR) and argue this is a promising approach to mitigating plasticity loss:

- 1.
We demonstrate superior performance on four benchmark problems classes studied in (Dohare et al., ; Kumar et al., ). Interestingly, there is no single closest competitor to SNR across these problems. Many competing approaches also show significant sensitivity to the choice of hyper-parameters; SNR does not. We introduce a new problem to elucidate similar plasticity loss phenomena in the context of language models, and show similar relative merits for SNR.
- 2.
We conduct a theoretical investigation of the optimization landscape for the problem of learning a single ReLU. We show that while (an idealized version of) SNR learns the target ReLU, regularization based approaches can fail to learn in this simple setting.

### 1.1 Related Literature

The phenomenon of plasticity loss was discovered in the context of transfer learning (Ash & Adams, ; Zilly et al., ; Achille et al., ). Achille et al. () showed that pre-training a network on blurred CIFAR images reduces its ability to learn on the original images. In a similar vein, Ash & Adams () showed that pre-training a network on 50% of a training set followed by training on the complete training set reduces accuracy relative to a network that forgoes the pre-training step. More recent literature has focused on problems that induce plasticity loss while training on a sequence of hundreds of changing tasks, such as Permuted MNIST and Continual ImageNet in Dohare et al. (), capturing the necessity to learn indefinitely.

Correlates of Plasticity Loss. The persistence of plasticity loss across a swathe of benchmark problems has elucidated a search for its cause. Several correlates of plasticity loss have been well observed, namely neuron inactivity, feature or weight rank collapse, increasing weight norms, and loss of curvature in the loss surface (Dohare et al., ; Lyle et al., ; Sokar et al., ; Lewandowski et al., ; Kumar et al., ). The exact cause of plasticity loss remains unclear and Lyle et al. () have shown that for any correlate an experiment can be constructed in which its correlation with plasticity loss is negative. Nonetheless, these correlates have inspired a series of algorithms and interventions with varying degrees of success in alleviating the problem. However, none is consistently performant across architectures and benchmark problems.

Reset Methods. Algorithms that periodically reset inactive or low-utility neurons have emerged as a promising approach (Dohare et al., ; Sokar et al., ; Nikishin et al., ). Continual Backprop (CBP) (Dohare et al., ) is one such method which tracks a utility for each neuron, and according to some reset frequency $r$, it resets the neuron with minimum utility in each layer. CBP’s utility is a discounted average product of a neuron’s associated weights and activation, a heuristic inspired by the literature on network pruning. Another algorithm is ReDO (Sokar et al., ), where on every ${1}/{r}^{\text{th}}$ mini-batch, ReDO computes the average activity of each neuron and resets those neurons whose average activities are small relative to other neurons in the corresponding layer, according to a threshold hyperparameter. Two defining characteristics of CBP and ReDO are a fixed reset rate and that neurons are reset relative to the utility of other neurons in their layer. As we will see, these proposals result in sub-optimal error rates, in a sense we make precise later.

Regularization Methods. L2 regularization has been shown to reduce plasticity loss, but is insufficient in completely alleviating the phenomenon (Dohare et al., ; Lyle et al., ). While L2 regularization limits weight norm growth during continual learning, it can exacerbate weight rank collapse due to regularization towards the origin. One successful regularization technique is Shrink and Perturb (S&P) (Ash & Adams, ), which periodically scales the network’s weights by a shrinkage factor $p$ followed by adding random noise to each weight with scale $\sigma$. Another approach is to perform L2 regularization towards the initial weights referred to as L2 Init (Kumar et al., ). These methods can be viewed as variants of L2 regularization that regularize towards a random initialization and the original initialization, respectively. These methods limit the growth of weight norms while maintaining weight rank and neuron activity by regularizing towards a high-plasticity parameterization.

Architectural and Optimizer Modifications. Architectural modifications such as layer normalization (Ba et al., ) and the use of concatenated ReLU activations have been shown to improve plasticity to varying degrees across network architectures and problem settings (Lyle et al., ; Kumar et al., ). Additionally, tuning Adam hyperparameters to improve the rate at which second moment estimates are updated has been explored with some success in Lyle et al. ().

## 2 Algorithm

To make ideas precise, consider a sequence of training examples $(X_{t},Y_{t})\in\mathcal{X}\times\mathcal{Y}$, drawn from some distribution $\mu_{t}$. Denote the network by $f:\mathcal{X}\times\Theta\rightarrow\mathcal{Y}$, and let $l:\mathcal{Y}\times\mathcal{Y}\rightarrow\mathbb{R}$ be our loss function. Denote by $H_{t}\in\mathcal{H}_{t}$, the history of network weights and training examples up to time $t$, and assume access to an optimization oracle $O_{t}:\mathcal{H}_{t-1}\rightarrow\Theta$ that maps the history of weights and training examples to a new set of network weights. As a concrete example, $O_{t}$ might correspond to stochastic gradient descent.

Let $\theta^{*}_{t}$ minimize
$\mathbb{E}_{\mu_{t}}[l(f(X_{t};\theta),Y_{t})]$, denote $\Theta_{t}=O_{t}(H_{t-1})$, and consider average expected regret

$$ $\frac{1}{T}\sum_{t}\mathbb{E}_{\mu_{t}}[l(f(X_{t};\Theta_{t}),Y_{t})]-\mathbb{ E}_{\mu_{t}}[l(f(X_{t};\theta^{*}_{t}),Y_{t})]$ $$

Plasticity loss describes the phenomenon where, for certain continual learning processes $\Theta_{t}$, such as those corresponding to SGD or Adam, average expected regret increases over time, even for benign choices of $\mu_{t}$(^1^11such as a sequence corresponding to multiple epochs on a random sub-sample of a dataset followed by multiple epochs on a second random sub-sample; or Example 2.1). To make these ideas concrete, it is worth considering an example of the above phenomenon reported first by Dohare et al. ().

###### Example 2.1 (The Permuted MNIST problem) .

Consider a sequence of ‘tasks’ presented sequentially to SGD, wherein each task consists of 10000 images from the MNIST dataset with the pixels permuted. SGD trains over a single epoch on each task before the subsequent task is presented. Figure 1 measures average accuracy on each task; we see that average accuracy decreases over tasks. The figure also shows a potential correlate of this phenomenon: the number of ‘dead’ or inactive neurons in the network increases as training proceeds, diminishing the network’s effective capacity.

Figure: Figure 1: Illustration of plasticity loss and its mitigation by SNR during training of a multilayer perceptron on the Permuted MNIST problem for a single random seed. For this figure, a neuron is declared dead if it has not fired for the last 1000 consecutive training examples.
Refer to caption: x1.png

One hypothesis that seeks to explain plasticity loss is that the network weights obtained from minimizing loss over some task yield poor initializations for a subsequent task, leading to the inactive neurons we observe in the above experiment. On the other hand random weight initializations are known to work well (Glorot & Bengio, ), suggesting a natural class of heuristics: re-initialize inactive neurons. Of course, the crux of any such algorithm is determining whether a neuron is inactive in the first place, and doing so as quickly as possible.

To motivate our algorithm, SNR, consider applying the network $f(\cdot;\theta_{t}^{*})$ to a hypothetical sequence of training examples drawn i.i.d. from $\mu_{t}$. Let $Z^{\mu_{t}}_{s,i}$ indicate the sequence of activations of neuron $i$, and let let $A^{\mu_{t}}_{i}$ denote the random time between two consecutive activations over this hypothetical sequence of examples. Now turning to the actual sequence of training examples, let $a^{t}_{i}$ count the time since the last firing of neuron $i$ prior to time $t$. Our (idealized) proposal is then exceedingly simple: reset neuron $i$ at time $t$ iff $\mathbb{P}(A_{i}^{\mu_{t}}\geq a^{t}_{i})\leq\eta$ for some suitably small threshold $\eta$. We dub this algorithm Self-Normalized Resets and present it as Algorithm 1. The algorithm requires a single hyper parameter, $\eta$. Of course in practice, the distribution of $A_{i}^{\mu_{t}}$ is unknown to us, and so an implementable version of Algorithm 1 simply approximates this distribution with the histogram of inter-firing times of neuron $i$ prior to time $t$.(^2^22As opposed to tacking the histogram itself, we simply track the mean inter-firing time, and assume $A_{i}^{\mu_{t}}$ is geometrically distributed with that mean. This requires tracking just one parameter per neuron.)

Figure: Algorithm 1 SNR: Self-Normalized Resets

###### Example 2.1 (The Permuted MNIST problem) .

### 2.1 Motivating SNR and Comparison to Other Reset Schemes

Here we motivate the SNR heuristic and compare it to other proposed reset schemes. Consider the following simple hypothesis test: we observe a discrete time process $Z_{s}\in\{0,1\}$ which under the null hypothesis $H_{0}$ is a Bernoulli process with mean $p>0$. The alternative hypothesis $H_{1}$ is that the mean of the process is identically zero. A hypothesis test must, at some stopping time $\tau$, either reject ($X_{\tau}=1$) or accept ($X_{\tau}=0$) the null; an optimal such test would choose to minimize the sum of type-1 and type-2 errors and a penalty for delays:

$$ $\mathbb{P}(X_{\tau}=1|H_{0})+\mathbb{P}(X_{\tau}=0|H_{1})+\lambda\left(\mathbb {E}[\tau|H_{0}]+\mathbb{E}[\tau|H_{1}]\right)$ $$

Here $\lambda>0$ penalizes the delay in a decision. If $\lambda<p/2$, the optimal test takes a simple form: for some suitable threshold $\bar{T}$, reject the null hypothesis iff $Z_{s}=0$ for all times $s$ up to $\bar{T}$:

###### Proposition 2.1 .

Let $\bar{T}$ be the $1-\lambda(p-\lambda)^{-1}$ percentile of a Geometric$(p)$ distribution. Then the optimal hypothesis test takes the form $X_{\tau}=\mathbf{1}\{Z_{\tau}=0\}$ where $\tau={\rm min}(s:Z_{s}=1)\wedge\bar{T}$.

Notice that if $\lambda\propto p$, the percentile threshold above is independent of $p$. Applying this setup to the setting where under the null, we observe the firing of neuron $i$ under i.i.d. training examples from $\mu_{t}$, imagine that $p=\mathbb{P}(Z^{\mu_{t}}_{s,i}=1)$. Further, we assume $\lambda=\alpha p$; a reasonable assumption which models a larger penalty for late detection of neurons that are highly active.
It is then optimal to declare neuron $i$ ‘inactive’ if the length of time it has not fired exceed the $1-\alpha(1-\alpha)^{-1}$ percentile of the distribution of $A_{i}^{\mu_{t}}$. This is the underlying motivation for the SNR heuristic.

Comparison with Reset Schemes: Neuron reset heuristics such as Sokar et al. () define (sometimes complex) notions of neuron ‘utility’ to determine whether or not to re-initialize a neuron. The utility of every neuron is computed over every consecutive (say) $r$ minibatches, and neurons with utility below a threshold are reset. To facilitate a comparison, consider the setting where neurons that do not fire at all over the course of the $r$ mini batches are estimated to have zero utility, and that only neurons with zero utility are re-initialized.

This reveals an interesting comparison with SNR. The schemes above will re-initialize a neuron after inactivity over a period of time that is uniform across all neurons. In the context of the hypothesis testing setup above, this will result in sub-optimal error rates across neurons. On the other hand, SNR will reset a neuron after it is inactive for a period that is effectively normalized to the nominal firing rate of that neuron, while still only specifying a single hyperparameter for the network.

###### Proposition 2.1 .

## 3 Experiments

We evaluate the efficacy and robustness of SNR on a series of benchmark problems from the continual learning literature, measuring regret with respect to prediction accuracy $l(y,y^{\prime})=\mathbf{1}\{y\neq y^{\prime}\}$. As an overview, we will seek to make the following points:

Inactive neurons are an important correlate of plasticity loss: This is true across several architectures: vanilla MLPs, CNNs and transformers.
Lower average loss: Across a broad set of problems/ architectures from the literature, SNR consistently achieves lower average loss than competing algorithms.
No consistent second-best competitor: Among competing algorithms, none emerge as consistently second best to SNR.
Robustness to hyper-parameters: The performance of SNR is robust to the choice of its single hyper parameter (the rejection percentile threshold). This is less so for competing algorithms.

### 3.1 Experimental Setup

Each problem consists of tasks $\mathcal{T}_{1},\mathcal{T}_{2},\ldots,\mathcal{T}_{N}$, each of which contains training examples in $\mathcal{X}\times\mathcal{Y}$. A network is trained for a fixed number of epochs per task to minimize cross-entropy loss. We perform an initial hyperparameter sweep over 5 seeds to determine the optimal choice of hyperparameters (see Appendix C). For each algorithm and problem, we select the hyperparameters that attain the lowest average loss and repeat the experiment on 5 new random seeds. A random seed determines the network’s parameter initialization, the generation of tasks, and any randomness in the algorithms evaluated. We evaluate both SGD and Adam as the base optimization algorithm, as earlier literature has argued that Adam can be less performant than SGD in some continual learning settings (Dohare et al., ; Ashley et al., ). We evaluate on the following problems:

Permuted MNIST (PM) (Goodfellow et al., ; Dohare et al., ; Kumar et al., ): A subset of 10000 image-label pairs from the MNIST dataset are sampled for an experiment. A task consists of a random permutation applied to each of the 10000 images. The network is presented with 2400 tasks appearing in consecutive order. Each task consists of a single epoch and the network receives data in batches of size 16.
Random Label MNIST (RM) (Kumar et al., ; Lyle et al., ): A subset of 1200 images from the MNIST dataset are sampled for an experiment. An experiment consists of 100 tasks, where each tasks is a random assignment of labels, consisting of 10 classes, to the 1200 images. A network is trained for 400 epochs on each task with a batch size 16.
Random Label CIFAR (RC) (Kumar et al., ; Lyle et al., ): A subset of 128 images from the CIFAR-10 dataset are sampled for an experiment. An experiment consists of 50 tasks, where each tasks is a random assignment of labels, consisting of 10 classes, to the 128 images. An agent is trained for 400 epochs on each task with a batch size 16.
Continual Imagenet (CI) (Dohare et al., ; Kumar et al., ): An experiment consists of all 1000 classes of images from the ImageNet-32 dataset (Chrabaszcz et al., ) containing 600 images from each class. Each task is a binary classification problem between two of the 500 classes, selected at random. The experiment consists of 500 tasks and each class occurs in exactly one task. Each task consists of 1200 images, 600 from each class, and the network is trained for 10 epochs with a batch size of 100.
Permuted Shakespeare (PS): We propose this problem to facilitate studying the transformer architecture in analogy to the MNIST experiments. An experiment consists of 32768 tokens of text from Shakespeare’s Tempest. For any task, we take a random permutation of the vocabulary of the Tempest and apply it to the text. The network is presented with 500 tasks. Each task consists of 100 epochs and the network receives data in batches of size 8 with a context widow of width 128. We evaluate over 9 seeds.

This experimental setup, for all but Permuted Shakespeare, follows that of (Kumar et al., ), with the exceptions of Permuted MNIST which has its task count increased from 500 to 2400, Random Label MNIST which has its task count increased from 50 to 100, and Random Label CIFAR which has its dataset reduced from 1200 to 128 images. Lyle et al. () consider variants of the Random Label MNIST and CIFAR problems by framing them as MDP environments for DQN agents. During training, the DQN agents are periodically paused to assess their plasticity by training them on separate, randomly generated regression tasks using the same image datasets.

#### 3.1.1 Algorithms and Architetcures

Our baseline in all problems consist simply of using SGD or Adam as the optimizer with no further intervention. We then consider several interventions to mitigate plasticity loss. First, we consider algorithms that employ an explicit reset of neurons: these include SNR, Continual Backprop (CBP) (Dohare et al., ), and ReDO (Sokar et al., ). Among algorithms that attempt to use regularization, we consider vanilla L2 regularization, L2 Init (Kumar et al., ), and Shrink and Perturb (Ash & Adams, ). Finally, as a potential architectural modification we consider the use of Layer Normalization (Ba et al., ).

We utilize the following network architectures:
MLP: For Permuted MNIST and Random Label MNIST we use an MLP identical to that in Kumar et al. () which in turn is a slight modification to that in Dohare et al. ().
CNN: For Random Label CIFAR and Continual ImageNet we use a CNN architectures identical to that in Kumar et al. () which in turn is a slight modification to that in Dohare et al. ().
Transformer: We use a decoder model with a single layer consisting of 2 heads, dimension 16 for each head, and with 256 neurons in the feed forward layer with ReLU activations. We deploy this architecture on the Permuted Shakespeare problem using the GPT-2 BPE tokenizer (limited to the set of unique tokens present in the sampled text).

### 3.2 Results and Discussion

We separately discuss the results for the first four problems (PM, RM, RC, CI) followed by Permuted Shakespeare; we observe additional phenomena in the latter experiment which merit separate discussion.

**Table 1: Average accuracy on the last 10% of tasks for each algorithm on the benchmark continual learning problems Permuted MNIST (PM), Random Label MNIST (RM), Random Label CIFAR (RC), and Continual ImageNet (CI). Each algorithm is trained for 5 seeds, with both Adam and SGD, with its best performing hyperparameters after an initial hyperparameter sweep over 5 seeds.**
| Optimizer | SGD | Adam |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Algorithm | PM | RM | RC | CI | PM | RM | RC | CI |
| No Intv. | $0.71$ | $0.11$ | 0.18 | $0.78$ | $0.64$ | $0.11$ | 0.15 | $0.58$ |
| SNR | 0.85 | 0.97 | 0.99 | 0.89 | 0.88 | 0.98 | 0.98 | 0.85 |
| CBP | $0.84$ | $0.95$ | 0.96 | $0.84$ | 0.88 | $0.95$ | 0.33 | $0.82$ |
| ReDO | $0.83$ | $0.72$ | 0.98 | $0.87$ | $0.85$ | $0.67$ | 0.74 | $0.80$ |
| L2 Reg. | $0.82$ | $0.80$ | 0.95 | $0.83$ | 0.88 | $0.95$ | 0.97 | $0.80$ |
| L2 Init | $0.83$ | $0.91$ | 0.97 | $0.83$ | 0.88 | $0.96$ | 0.98 | $0.83$ |
| S&P | $0.83$ | 0.92 | 0.97 | $0.85$ | 0.88 | 0.96 | 0.97 | $0.81$ |
| Layer Norm. | $0.69$ | $0.14$ | 0.96 | $0.82$ | $0.66$ | $0.11$ | 0.96 | $0.58$ |

Table 1 shows that across all four problems (PM, RM, RC, CI) and both SGD and Adam, SNR consistently attains the largest average accuracy on the final 10% of tasks. For each competitor algorithm there is at least one problem on which SNR attains superior accuracy by at least 5 percentage points with SGD and at least 2 percentage points with Adam. We also see that there is no consistent second-best algorithm with the SGD optimizer while L2 Init is consistently the second-best with the Adam optimizer.

Another notable property of SNR is its robustness to the choice of rejection percentile threshold. In contrast, its competitors are not robust to the choice of their hyperparemter(s). On all but RM with SGD, SNR experiences a decrease of at most 2 percentage points in average accuracy when varying its rejection percentile threshold across the range of optimal thresholds found across experiments. On the other hand, increasing the hyperparameter strength by a single order of magnitude, as is common in a hyperparameter sweep, from the optimal value for L2 Init, S&P, and CBP results in a decrease in average accuracy by at least 72 percentage points. See Appendix C for detailed tables.

Next, we turn our attention to the Permuted Shakespeare problem. For the no intervention network with Adam, we see dramatic plasticity loss, as the average loss increases from about 0.15 on the first few tasks to 3.0242 on the last 50 tasks; see Figure 2. In Figure 4 and Figure 3 we see that this plasticity loss is correlated with increasing weight norms in the self-attention and feedforward layers, persistent neuron inactivity, and a collapse in the entropy of the self-attention probabilities.

**Table 2: Average loss measured on the final epoch of each task (mean $\pm$ standard deviation over 9 seeds) for different continual learning algorithms on the Permuted Shakespeare problem. Results are reported for the best performing hyperparameter(s) of each algorithm, selected after an initial hyperparameter sweep over 5 seeds.**
| Algorithm | All Tasks | First 50 Tasks | Last 50 Tasks |
| --- | --- | --- | --- |
| L2 | $0.2762\pm 0.0309$ | $0.1560\pm 0.0236$ | $0.3101\pm 0.0425$ |
| SNR+L2 | $\textbf{0.2177}\pm 0.0196$ | $\textbf{0.1370}\pm 0.0169$ | $\textbf{0.2551}\pm 0.0454$ |
| No Intv. | $2.7397\pm 0.0140$ | $1.8164\pm 0.0295$ | $3.0147\pm 0.0250$ |
| L2 Init | $1.5052\pm 0.0437$ | $1.2931\pm 0.0486$ | $1.5262\pm 0.0420$ |
| SNR | $2.6872\pm 0.0222$ | $1.7338\pm 0.0295$ | $3.0242\pm 0.0408$ |

Figure: Figure 2: Cumulative average of the loss measured on the final epoch of each task on the Permuted Shakespeare problem. Right panel zooms in to L2 and SNR+L2
Refer to caption: x3.png

We see that resets are by themselves insufficient in mitigating plasticity loss, providing at most a marginal improvement over no intervention. This is unsurprising since neurons are only present in the feedforward layers, unlike the MLP and CNN architectures in the earlier experiments. As such, regularization appears necessary and we see that, over the last 50 tasks, L2 regularization attains an average loss of 0.3101 in contrast to 3.0147 and 3.0242 for no intervention and SNR. This improvement in performance coincides with stable weight norms and non-vanishing average entropy of self-attention probabilities for L2 regularization. In contrast to the earlier problems, L2 Init fares worse than L2 regularization and experiences substantial loss of plasticity, although to a lesser extent than the no intervention network.

While L2 regularization addresses weight blowup, neuron death remains present; see Figure 3. The average loss with L2 increases from 0.1560, over the first 50 tasks, to 0.3101, over the final 50 tasks. This prompts us to consider using SNR in addition to L2 regularization. This largely eliminates neuron death (see the right panel of Figure 3), while stabilizing weight norms and maintaining entropy of self-attention probabilities, providing the lowest loss (0.2551) over the final 50 tasks.

Figure: Figure 3: The number of neurons that have been inactive for the last 5 consecutive batches on the Permuted Shakespeare problem, averaged over time steps within each epoch.
Refer to caption: x5.png

Figure: Figure 4: Parameter norms and attention-score entropy on the Permuted Shakespeare experiment.
Refer to caption: x7.png

#### 3.2.1 Scaled Permuted Shakespeare

While the scale of our Permuted Shakespeare problem serves as a simple benchmark problem for evaluating a series of continual learning algorithms and hyperparameter choices for language models, it is also of interest to investigate the effect of model and dataset scale on plasticity. To this end, we scale the number of non-embedding weights in our transformer network by a factor of $N=16$, increasing the number of heads to 8 and number of neurons to 1024. In line with scaling laws (Kaplan et al., ), we increase the size of our dataset by a factor of $16^{0.74}$, specifically to 254’976 tokens per task. The rest of the problem setup remains unchanged; we train the network for 100 epochs on 500 tasks in sequence. To facilitate the larger token count, we train on a sample of 254’976 tokens worth of text from the complete set of plays by William Shakespeare.

We limit our experiment to 4 random seeds, scales $N\in\{1,16\}$, evaluating only SNR+L2-regularization and L2-regularization with hyperparameters $\eta=0.05$ and $\lambda=10^{-4}$, presenting our results in Table 3. We first note that as model and dataset size grow, the gap in average loss between L2-regularization and SNR+L2-regularization grows substantially. Simultaneously, we see a dramatic increase in the proportion of inactive neurons with L2-regularization. At any time step, on average $0.06\%$ of neurons are inactive at scale $N=1$ while $32.9\%$ are inactive at scale $N=16$. These results suggest that resets can play a critical role in maintaining plasticity in large-scale language models.

**Table 3: Average loss measured on the final epoch of each task (mean $\pm$ standard deviation over 4 seeds) for the Permuted Shakespeare problem at scales $N\in\{1,16\}$ as well as the average proportion of neurons that have not fired within the last 5 mini-batches.**
| Algorithm | Loss (All Tasks) | Loss (Last 50 Tasks) | Dead Neuron Rate |
| --- | --- | --- | --- |
| L2 - Scale 1 | $0.159\pm 0.025$ | $0.152\pm 0.016$ | 0.06% |
| SNR+L2 - Scale 1 | $0.154\pm 0.008$ | $0.141\pm 0.031$ | 0.00% |
| L2 - Scale 16 | $0.377\pm 0.016$ | $0.410\pm 0.052$ | 32.9% |
| SNR+L2 - Scale 16 | $0.324\pm 0.028$ | $0.332\pm 0.073$ | $1.41\cdot 10^{-6}$% |

## 4 Theoretical Analysis of Learning a Single ReLU

We analyze the average expected regret for learning a single target ReLU in order to gain intuition as to why SNR achieves lower average expected regret relative to the regularization based algorithms in our set of continual learning experiments in Section 3. At a high level, our analysis provides the following conclusions.

- 1.
Learning a target ReLU with gradient descent and (an idealized) version of SNR has $O(\frac{1}{T})$ average expected regret. See Theorem 4.2 and Theorem B.2 for the full proof.
- 2.
Learning a target ReLU with gradient descent and L2 regularization or L2 Init has $\Omega(1)$ average regret with probability $\frac{1}{2}$ over initializations of the network weights. See Theorem 4.1 and Theorem B.1 for the full proof.

### 4.1 Preliminaries

We aim to learn a single ReLU activated neuron, parameterized by the family $\Theta=\mathbb{R}^{2}$.

$$ $f(x,v)=\sigma(\tilde{v}x+b_{v})=\begin{cases}\tilde{v}x+b_{v}&\text{if $\tilde {v}x+b_{v}\geq 0$}\\ 0&\text{if $\tilde{v}x+b_{v}<0$}\end{cases}$ $$

We refer to $v=(\tilde{v},b_{v})$ as the target parameters and $w=(\tilde{w},b_{w})$ as our network’s parameters.

###### Assumption 4.1 .

We sample data $x,y\in\mathbb{R}\times\mathbb{R}_{+}$ according to the distribution $\mu$ where $x\sim\text{ Uniform}(-L,L)$, for some positive constant $L$, and $y|x=f(x,v)$.

We analyze the average expected regret with respect to the squared error.

$$ $\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}_{\mu}[\frac{1}{2}(\sigma(\tilde{w_{t}}x+ b_{w_{t}})-\sigma(\tilde{v}x+b_{v}))^{2}]$ (1) $$

For notational brevity, we define

$$ $F(w)=\mathbb{E}_{\mu}[\frac{1}{2}(\sigma(\tilde{w}x+b_{w})-\sigma(\tilde{v}x+b _{v}))^{2}]$ $$

For convenience of analysis, we suppose that the optimization oracle $O_{t}$ performs gradient descent, rather than SGD, and has access to the oracle

$$ $\nabla F(w)=\mathbb{E}_{\mu}[(\sigma(\tilde{w}x+b_{w})-\sigma(\tilde{v}x+b_{v} ))\mathbf{1}\{\tilde{w}x+b_{w}\geq 0\}(x,1)]$ $$

Therefore, for a learning rate $\eta$, without any regularization or resets, $\{w_{t}\}_{t=0}^{T-1}$ satisfies

$$ $w_{t+1}=w_{t}-\eta\nabla F(w_{t})$ $$

###### Assumption 4.1 .

### 4.2 Gradient Descent with L2 Init and L2 Regularization

Given a regularization strength $\lambda\geq 0$, we consider the optimization oracle $O_{t}^{\text{L2 Init}}$ that performs gradient descent on the on the L2 Init regularized objective

$$ $\bar{F}(w)=\mathbb{E}_{\mu}[\frac{1}{2}(\sigma(\tilde{w}x+b_{w})-\sigma(\tilde {v}x+b_{v}))^{2}]+\frac{\lambda}{2}||w-w_{0}||^{2}$ $$

Then the L2 Init gradient descent update is simply

$$ $w_{t+1}=w_{t}-\eta\nabla F(w_{t})-\eta\lambda(w_{t}-w_{0})$ (2) $$

We can also consider the gradient descent update with vanilla L2 regularization

$$ $w_{t+1}=w_{t}-\eta\nabla F(w_{t})-\eta\lambda w_{t}$ (3) $$

###### Theorem 4.1 .

Suppose that $x,y$ are sampled according to Assumption 4.1 and that the target parameters $v=(\tilde{v},b_{v})$ satisfy $\tilde{v}>0$ and $b_{v}\leq 0$. Then applying gradient descent with L2 Init (2) or L2 regularization (3) with strength $\lambda\geq 0$ and learning rate $\eta>0$ satisfying

$$ $\displaystyle\eta$ $\displaystyle\leq\frac{1}{L^{2}+1}$ $\displaystyle\eta\lambda$ $\displaystyle<1$ $$

and with $w_{0}$ sampled uniformly from $\left([-1,-\tilde{w}_{\min})\cup(\tilde{w}_{\min},1]\right)\times\{0\}$, for any $\tilde{w}_{\min}>0$, then with probability $\frac{1}{2}$ over random initializations of $w_{0}$, the average regret is non-vanishing

$$ $\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}_{\mu}[\frac{1}{2}(\sigma(\tilde{w_{t}}x+ b_{w_{t}})-\sigma(\tilde{v}x+b_{v}))^{2}]\geq F(0)>0$ $$

###### Theorem 4.1 .

### 4.3 Gradient Descent with Resets

For any reset threshold $\epsilon>0$ we define a reset oracle $\mathcal{O}_{\epsilon}$ such that for any $w\in\mathbb{R}^{2}$

$$ $\mathcal{O}_{\epsilon}(w)=\begin{cases}\text{True}&\text{ if }\sup_{x\in[-L,L] }\tilde{w}x+b_{w}\leq\epsilon\\ \text{False}&\text{ if }\sup_{x\in[-L,L]}\tilde{w}x+b_{w}>\epsilon\end{cases}$ $$

We then consider the following gradient descent updates with resets

$$ $\displaystyle u_{t+1}$ $\displaystyle=w_{t}-\eta\nabla F(w_{t})$ (4) $\displaystyle w_{t+1}$ $\displaystyle=\begin{cases}u_{t+1}&\text{ if }\mathcal{O}_{\epsilon}(u_{t+1})= \text{ False}\\ \text{sample from Uniform}\left([-1,-\tilde{w}_{\min})\cup(\tilde{w}_{\min},1] \right)\times\{0\}&\text{ if }\mathcal{O}_{\epsilon}(u_{t+1})=\text{ True}\end {cases}$ (5) $$

###### Theorem 4.2 .

Suppose that $x,y$ are sampled according to Assumption 4.1 for any constant $L>0$ and that the target parameters $v=(\tilde{v},b_{v})$ satisfy $\tilde{v}\in[1,\tilde{v}_{\max}]$ and $-\frac{L}{6}\leq b_{v}\leq 0$ and we denote $v_{\max}=(\tilde{v}_{\max},-\frac{L}{6})$. Let $\epsilon>0$ be a reset threshold and suppose that the initial parameters $w_{0}$ are sampled uniformly from $\tilde{w}_{0}\sim[-1,-\tilde{w}_{\min})\cup(\tilde{w}_{\min},1]$ and $b_{w_{0}}=0$ such that

$$ $\tilde{w}_{\min}>\frac{12\tilde{v}_{\max}\epsilon}{L}$ $$

and

$$ $\frac{5}{2}L\geq\epsilon.$ $$

Then gradient descent with a constant learning rate of

$$ $\eta\leq\frac{\tilde{w}_{\min}^{3}L^{6}}{3\cdot 12^{2}\cdot 24^{3}(2+||v_{\max }||)^{5}(L^{2}+1)^{6}}$ $$

and with resets, i.e. (4) and (5), attains an average regret of

$$ $\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}_{\mu}[\frac{1}{2}(\sigma(\tilde{w_{t}}x+ b_{w_{t}})-\sigma(\tilde{v}x+b_{v}))^{2}]\leq\frac{C}{T}$ $$

where

$$ $C=\lceil\frac{32L^{2}F((-1,0))}{\eta\epsilon^{4}}\rceil F((-1,0))+\frac{3}{2 \eta^{2}}\left((\tilde{v}_{\max}-\tilde{w}_{\min})^{2})+(\frac{L}{6})^{2}\right)$ $$

###### Theorem 4.2 .

## Appendix A Proof of Proposition of 2.1

###### Proposition A.1 (Restatement of Proposition 2.1 ) .

Let $T$ be the $1-\frac{\lambda}{p-\lambda}$ percentile of a Geometric$(p)$ distribution. Then the optimal hypothesis test takes the form $X_{\tau}=\mathbf{1}\{Z_{\tau}=0\}$ where $\tau={\rm min}(s:Z_{s}=1)\wedge T$.

###### Proof.

We begin by assuming equal priors $\mathbb{P}(H_{0})=\mathbb{P}(H_{1})=\frac{1}{2}$. We note that for any time $s$, if $Z_{s}=1$ then any optimal hypothesis test must declare $X_{s}=0$ as $Z_{s}=1$ is impossible under $H_{1}$ and waiting to make a future declaration will incur additional cost of at least $\lambda$. Therefore, it remains for us to derive an optimal stopping time for the collection of states $\{Z_{1}=\ldots=Z_{s}=0:s\in\mathbb{Z}_{+}\}$.

Let $V(s)$ be the expected total future cost at time $s$ given that we have observed $Z_{1}=\ldots=Z_{s}=0$. We define

$$ $\displaystyle\pi_{s}$ $\displaystyle=\mathbb{P}(H_{0}|Z_{1}=\ldots=Z_{s}=0)$ $\displaystyle=\frac{\mathbb{P}(H_{0},Z_{1}=\ldots=Z_{s}=0)}{\mathbb{P}(Z_{1}= \ldots=Z_{s}=0)}$ $\displaystyle=\frac{(1-p)^{s}\mathbb{P}(H_{0})}{(1-p)^{s}\mathbb{P}(H_{0})+ \mathbb{P}(H_{1})}$ $\displaystyle=\frac{(1-p)^{s}}{(1-p)^{s}+1}$ by $\mathbb{P}(H_{0})=\mathbb{P}(H_{1})$ $$

If we stop at time $s$ and make a declaration, we choose the hypothesis with higher positive probability in order tom minimize the error probability

$$ $\mathbb{P}(X_{s}=1|H_{0})+\mathbb{P}(X_{s}=0|H_{1})$ $$

Thus, the expected cost of stopping is

$$ $C^{\text{stop}}(s)=\min\{\pi_{s},1-\pi_{s}\}$ $$

We can simplify this further by noting that $\pi_{s}\leq 1-\pi_{s}$. We note that

$$ $\displaystyle\frac{1}{2}(1-p)^{s}$ $\displaystyle\leq\frac{1}{2}$ $$

by $1-p\in[0,1]$. This is equivalent to

$$ $(1-p)^{s}\leq\frac{1}{2}((1-p)^{s}+1)$ $$

by adding $\frac{1}{2}(1-p)^{s}$, which in turn, is equivalent to

$$ $\pi_{s}=\frac{(1-p)^{s}}{(1-p)^{s}+1}\leq\frac{1}{2}$ $$

Therefore, $\pi_{s}\leq\frac{1}{2}\leq 1-\pi_{s}$ and so we have that

$$ $C^{\text{stop}}(s)=\min\{\pi_{s},1-\pi_{s}\}=\pi_{s}$ $$

This also implies that if we are to stop at some state $\{Z_{1}=\ldots=Z_{s}=0\}$, it is optimal to declare $X_{s}=1$.

If we continue at time $s$ to $s+1$, we incur an additional delay cost of $\lambda$, and the expected future cost depending on whether we see a $Z_{s+1}=1$ or $Z_{s+1}=0$.

- •
With probability $p\pi_{s}$ we obserbes $Z_{s+1}$, under $H_{0}$, and we stop the process with $X_{s+1}=0$, incurring zero error cost since $Z_{s+1}=1$ cannot occur under $H_{1}$.
- •
With probability $(1-p)\pi_{s}+(1-\pi)=1-p\pi_{s}$ we observe $Z_{s+1}=0$ and the process continues.

Therefore, the expected cost of continuing at time $s$ is

$$ $C^{\text{cont}}(s)=\lambda+(1-p\pi_{s})V(s+1)$ $$

Then the Bellman equation for the optimal cost-to-go function is

$$ $V(s)=\\ min\{C^{\text{stop}}(s),C^{\text{cont}}(s)\}$ $$

To determine an optimal stopping time, our goal is to find smallest $T$ for which

$$ $C^{\text{stop}}(T)\leq C^{\text{cont}}(T)$ (6) $$

Assuming we stop at time $T$,

$$ $V(T+1)=C^{\text{stop}}(T+1)=\pi_{T+1}$ $$

Therefore,

$$ $C^{\text{cont}}(T)=\lambda+(1-p\pi_{s})V(T+1)=\lambda+(1-p\pi_{s})\pi_{T+1}$ $$

and to establish (6) it suffices to show that

$$ $\pi_{T}\leq\lambda+(1-p\pi_{T})\pi_{T+1}$ (7) $$

First, we write $\pi_{T+1}$ in terms of $\pi_{T}$. Under the updating rule for the posterior probability, we have that

$$ $\displaystyle\pi_{T+1}$ $\displaystyle-\mathbb{P}(H_{0}|Z_{1}=\ldots=Z_{T+1}=0)$ $\displaystyle=\frac{\mathbb{P}(Z_{T+1}=0|H_{0})\mathbb{P}(H_{0}|Z_{1}=\ldots=Z _{T}=0)}{\mathbb{P}(Z_{T+1}=0|Z_{1}=\ldots=Z_{T}=0)}$ $\displaystyle=\frac{(1-p)\pi_{T}}{\mathbb{P}(Z_{T+1}=0|H_{0})\pi_{T}+\mathbb{P }(Z_{T+1}=0|H_{1})(1-\pi_{T})}$ $\displaystyle=\frac{(1-p)\pi_{T}}{(1-p)\pi_{T}+(1-\pi_{T})}$ $\displaystyle=\frac{(1-p)\pi_{T}}{1-p\pi_{T}}$ $$

Returning to (7), we need to show that

$$ $\pi_{T}\leq\lambda+(1-p\pi_{T})\frac{(1-p)\pi_{T}}{1-p\pi_{T}}=\lambda+(1-p) \pi_{T}$ $$

Simplifying the above inequality, we have that

$$ $\pi_{T}\leq\frac{\lambda}{p}$ $$

Substituting in our formula for $\pi_{T}$, the above is equivalent to

$$ $\frac{(1-p)^{T}}{(1-p)^{T}+1}\leq\frac{\lambda}{p}$ $$

which after simplification is equivalent to

$$ $(1-p)^{T}\leq\frac{\frac{\lambda}{p}}{1-\frac{\lambda}{p}}=\frac{\lambda}{p-\lambda}$ $$

Let $F$ be the CDF of the Geometric$(p)$ distribution. Let $T^{*}$ be the $1-\frac{\lambda}{p-\lambda}$ percentile of the Geometric$(p)$ distribution. Note, since $\lambda<\frac{p}{2}$ then $1-\frac{\lambda}{p-\lambda}\in(0,1)$ and is a valid percentile. Then for any $T\geq T^{*}$ we have that

$$ $\displaystyle 1-(1-p)^{T}$ $\displaystyle=F(T)$ $\displaystyle\geq F(T^{*})$ by $T\geq T^{*}$ $\displaystyle\geq 1-\frac{\lambda}{p-\lambda}$ by choice of $T^{*}$ $$

which is equivalent to

$$ $(1-p)^{T}\leq\frac{\lambda}{p-\lambda}$ $$

and therefore, the optimal hypothesis test is to declare $X_{T}=1$ for any $T\geq T^{*}$ if $Z_{1}=\ldots=Z_{T}=0$. Hence, the optimal hypothesis takes the form of

$$ $X_{\tau}=\mathbf{1}\{Z_{\tau}=0\}\text{ where }\tau=\min(s:Z_{s}=1)\land T^{*}$ $$

∎

###### Proposition A.1 (Restatement of Proposition 2.1 ) .

###### Proof.

## Appendix B Learning a Single ReLU

In this section we prove Theorem 4.1 and Theorem 4.2. For convenience, we use slightly different notation from Section 4.1, such as treating the training examples $x$ as two-dimensional vectors with the element fixed as 1. For completeness, we begin by restating Section 4.1.

### B.1 Preliminaries

We aim to learn a single ReLU-activated neuron with bias, or equivalently, the mapping $f_{v}:\mathbb{R}^{2}\to\mathbb{R}_{+}$ which we define as

$$ $f_{v}(x)=\sigma(v^{T}x)=\begin{cases}v^{T}x&\text{if $v^{T}x\geq 0$}\\ 0&\text{if $v^{T}x<0$}\end{cases}$ $$

We refer to $v=(\tilde{v},b_{v})$ as the target parameters where $\tilde{v}$ is the slope and $b_{v}$ is the bias of the linear map $x\mapsto v^{T}x$. Likewise, we denote our model’s parameters as $w=(\tilde{w},b_{w})$ where $\tilde{w}$ is the slope and $b_{w}$ is the bias.

We sample data $x=(\tilde{x},1)\sim\text{ Uniform}(-L,L)\times\{1\}$ such that the first coordinate $\tilde{x}$ is sampled uniformly from the domain $[-L,L]$ and the second coordinate is a constant 1 so as to model the bias term in a ReLU-activated neuron. We learn the target neuron with respect to the squared loss and we thus define the loss to be

$$ $F(w)=\mathbb{E}_{x}[\frac{1}{2}(\sigma(w^{T}x)-\sigma(v^{T}x))^{2}]$ (8) $$

Then the gradient of $F$ is simply

$$ $\nabla F(w)=\mathbb{E}_{x}[(\sigma(w^{T}x)-\sigma(v^{T}x))\mathbb{I}(w^{T}x \geq 0)x]$ (9) $$

where the above expectations are taken with respect to $x\sim$ Uniform$(-L,L)\times\{1\}$. We minimize $F$ using gradient descent with a constant learning rate $\eta$

$$ $w_{t+1}=w_{t}-\eta\nabla F(w_{t})$ (10) $$

We define the regret of learning a single ReLU with an iterative algorithm as

$$ $\mathbb{E}[R_{T}]=\mathbb{E}_{w_{0}}[\sum_{t=0}^{T-1}F(w_{t})]$ $$

where the randomness is over the initialization of $w_{0}$ and the potential reinitialization of $w_{t}$ due to resets. Then the average regret is simply

$$ $\frac{1}{T}\mathbb{E}[R_{T}]=\frac{1}{T}\mathbb{E}_{w_{0}}[\sum_{t=0}^{T-1}F(w _{t})]$ $$

For some constant $\tilde{v}_{\max}>1$ we suppose that $\tilde{v}\in[1,\tilde{v}_{\max}]$ and $b_{v}\in[-\frac{L}{6},0]$. While for some constant $\tilde{w}_{\min}<1$ we sample $\tilde{w}_{0}$ uniformly from $[-1,-\tilde{w}_{0})\cup(\tilde{w}_{0},1]$ and set $b_{w_{0}}=0$, as is customary to initialize neurons with zero bias.

#### B.1.1 L2 Init and L2 Regularization

Given a regularization strength $\lambda\geq 0$, we consider the loss with L2 Init regularization as

$$ $\bar{F}(w)=\mathbb{E}_{x}[\frac{1}{2}(\sigma(w^{T}x)-\sigma(v^{T}x))^{2}]+ \frac{\lambda}{2}||w-w_{0}||^{2}=F(w)+\frac{\lambda}{2}||w-w_{0}||^{2}$ $$

Then the gradient of $\bar{F}$ is simply

$$ $\nabla F(w)=\mathbb{E}_{x}[(\sigma(w^{T}x)-\sigma(v^{T}x))\mathbb{I}(w^{T}x \geq 0)x]+\lambda(w-w_{0})=\nabla F(w)+\lambda(w-w_{0})$ $$

Then the L2 Init gradient descent update is simply

$$ $w_{t+1}=w_{t}-\eta\nabla\bar{F}(w_{t})=w_{t}-\eta\nabla F(w_{t})-\eta\lambda(w _{t}-w_{0})$ (11) $$

Similarly, we can consider vanilla L2 regularization whose update is simply

$$ $w_{t+1}=w_{t}-\eta\nabla F(w_{t})-\eta\lambda w_{t}$ (12) $$

Note, if $\lambda=0$ then we simply retain the update of unregularized gradient descent (10). Then for any sufficiently small learning rate $\eta$ we attain non-vanishing average regret.

###### Theorem B.1 .

Suppose that $x$ is sampled according to $x\sim$ Uniform$(-L,L)\times\{1\}\subseteq\mathbb{R}^{2}$ and that the target parameters $v=(\tilde{v},b_{v})$ satisfy $\tilde{v}>0$ and $b_{v}\leq 0$. Then applying gradient descent with L2 Init (11) or L2 regularization (12), with regularization strength $\lambda\geq 0$ and learning rate $\eta>0$ such that

$$ $\displaystyle\eta$ $\displaystyle\leq\frac{1}{L^{2}+1}$ $\displaystyle\eta\lambda$ $\displaystyle<1$ $$

and with $w_{0}$ sampled uniformly from $\left([-1,-\tilde{w}_{\min})\cup(\tilde{w}_{\min},1]\right)\times\{0\}$, for any $\tilde{w}_{\min}>0$, then with probability $\frac{1}{2}$ over random initializations of $w_{0}$, the average regret is non-vanishing

$$ $\frac{1}{T}R_{T}\geq F(0)$ $$

###### Proof.

The proof follows immediately by Lemma B.4 for L2 Init. A trivial modification of Lemma B.4 yields an identical result for L2 regularization, which we omit for brevity.
∎

###### Theorem B.1 .

###### Proof.

#### B.1.2 Gradient Descent with Resets

For any reset threshold $\epsilon>0$ we define a reset oracle $\mathcal{O}_{\epsilon}$ such that for any $w\in\mathbb{R}^{2}$

$$ $\mathcal{O}_{\epsilon}(w)=\begin{cases}\text{True}&\text{ if }\sup_{x\in[-L,L] \times\{1\}}w^{T}x\leq\epsilon\\ \text{False}&\text{ if }\sup_{x\in[-L,L]\times\{1\}}w^{T}x>\epsilon\end{cases}$ $$

We consider the following gradient descent updates with resets

$$ $\displaystyle u_{t+1}$ $\displaystyle=w_{t}-\eta\nabla F(w_{t})$ (13) $\displaystyle w_{t+1}$ $\displaystyle=\begin{cases}u_{t+1}&\text{ if }\mathcal{O}_{\epsilon}(u_{t+1})= \text{ False}\\ \text{sample from Uniform}\left([-1,-\tilde{w}_{\min})\cup(\tilde{w}_{\min},1] \right)\times\{0\}&\text{ if }\mathcal{O}_{\epsilon}(u_{t+1})=\text{ True}\end {cases}$ (14) $$

###### Theorem B.2 .

Suppose that $x$ is sampled according to $x\sim$ Uniform$(-L,L)\times\{1\}\subseteq\mathbb{R}^{2}$ and the target parameters $v=(\tilde{v},b_{v})$ satisfy $\tilde{v}\in[1,\tilde{v}_{\max}]$ and $-\frac{L}{6}\leq b_{v}\leq 0$ and we denote $v_{\max}=(\tilde{v}_{\max},-\frac{L}{6})$. Let $\epsilon>0$ be a reset threshold and suppose that the initial parameters $w_{0}$ are sampled uniformly from $\tilde{w}_{0}\sim[-1,-\tilde{w}_{\min})\cup(\tilde{w}_{\min},1]$ and $b_{w_{0}}=0$ such that

$$ $\tilde{w}_{\min}>\frac{12\tilde{v}_{\max}\epsilon}{L}$ $$

and

$$ $\frac{5}{2}L\geq\epsilon.$ $$

Then gradient descent with a constant learning rate of

$$ $\eta\leq\frac{\tilde{w}_{\min}^{3}L^{6}}{3\cdot 12^{2}\cdot 24^{3}(2+||v_{\max }||)^{5}(L^{2}+1)^{6}}$ $$

and with resets, i.e. (13) and (14), attains an average regret of

$$ $\frac{1}{T}\mathbb{E}[R_{T}]\leq\frac{C}{T}$ $$

where

$$ $C=\lceil\frac{32L^{2}F((-1,0))}{\eta\epsilon^{4}}\rceil F((-1,0))+\frac{3}{2 \eta^{2}}\left((\tilde{v}_{\max}-\tilde{w}_{\min})^{2})+(\frac{L}{6})^{2}\right)$ $$

###### Proof.

The theorem is restated and proven as Theorem B.3.
∎

###### Theorem B.2 .

###### Proof.

### B.2 Proofs

#### B.2.1 Properties of the Loss Function

###### Lemma B.1 .

The ReLU activation function $\sigma(x)=\max\{0,x\}$ is 1-Lipschitz continuous.

###### Proof.

Let $x,y\in\mathbb{R}$ be arbitrary. Without loss of generality we suppose that $x\geq y$. We consider two cases. Firstly, if $x\geq 0$ then we have that

$$ $\displaystyle|\sigma(x)-\sigma(y)|$ $\displaystyle=\sigma(x)-\sigma(y)$ by $x\geq y$ $\displaystyle=x-\sigma(y)$ by $x\geq 0$ $\displaystyle\leq x-y$ by $\sigma(y)\geq y$ $\displaystyle\leq|x-y|$ $$

As for the case of $x<0$ then we likewise have that $y<0$ and so

$$ $|\sigma(x)-\sigma(y)|=0\leq|x-y|$ $$

Thus, it follows that $\sigma(\cdot)$ is 1-Lipschitz continuous.
∎

###### Lemma B.2 .

Suppose that $x$ is sampled according to $x\sim$ Uniform$(-L,L)\times\{1\}\subseteq\mathbb{R}^{2}$ and that the target parameters $v=(\tilde{v},b_{v})$ satisfy $\tilde{v}>0$ and $b_{v}\leq 0$. Then for $w\leq 0$, $\nabla F(w)=\mathbb{E}_{x}[\sigma(w^{T}x)x]$.

###### Proof.

For almost every $\tilde{x}>0$, $w^{T}x=\tilde{w}\tilde{x}+b_{w}<0$ and so

$$ $\displaystyle(\sigma(w^{T}x)-\sigma(v^{T}x))\mathbb{I}(w^{T}x\geq 0)x$ $\displaystyle=0$ by $\mathbb{I}(w^{T}x\geq 0)=0$ $\displaystyle=\sigma(w^{T}x)x$ by $\sigma(w^{T}x)=0$ since $w^{T}x<0$ $$

As for $\tilde{x}<0$, we have that $v^{T}x<0$ since $\tilde{v}>0$ and $b_{v}\leq 0$, and so $\sigma(v^{T}x)=0$. Hence,

$$ $(\sigma(w^{T}x)-\sigma(v^{T}x))\mathbb{I}(w^{T}x\geq 0)x=\sigma(w^{T}x)\mathbb {I}(w^{T}x\geq 0)x=\sigma(w^{T}x)x$ $$

where the last equality follows by the fact that $\mathbb{I}(w^{T}x\geq 0)$ is redundant given that $\sigma(w^{T}x)=0$ if $w^{T}x<0$. Therefore, for almost every $x\in\text{ Uniform}(-L,L)\times\{1\}$, we have that

$$ $(\sigma(w^{T}x)-\sigma(v^{T}x))\mathbb{I}(w^{T}x\geq 0)x=\sigma(w^{T}x)x$ (15) $$

We recall that

$$ $\nabla F(w)=\mathbb{E}_{x}[(\sigma(w^{T}x)-\sigma(v^{T}x))\mathbb{I}(w^{T}x \geq 0)x]$ $$

and hence by (15)

$$ $\nabla F(w)=\mathbb{E}_{x}[\sigma(w^{T}x)x]$ $$

∎

###### Lemma B.3 .

Suppose that $x$ is sampled according to $x\sim$ Uniform$(-L,L)\times\{1\}\subseteq\mathbb{R}^{2}$ and that the target parameters $v=(\tilde{v},b_{v})$ satisfy $\tilde{v}>0$ and $b_{v}\leq 0$. then $\nabla F(\cdot)$ is $(L^{2}+1)$-Lipschitz continuous on $w\leq 0$. That is, for any $w,u\leq 0$, $||\nabla F(w)-\nabla F(u)||\leq(L^{2}+1)||w-u||$.

###### Proof.

By $w,u\leq 0$ and Lemma B.2 we have that $\nabla F(w)=\mathbb{E}_{x}[\sigma(w^{T}x)x]$ and $\nabla F(u)=\mathbb{E}_{x}[\sigma(u^{T}x)x]$. Then we establish the desired result as follows,

$$ $\displaystyle||\nabla F(w)-\nabla F(u)||$ $\displaystyle=||\mathbb{E}_{x}[\sigma(w^{T}x)x-\sigma(u^{T}x)x]||$ $\displaystyle\leq\mathbb{E}_{x}[||\sigma(w^{T}x)x-\sigma(u^{T}x)x||]$ by Jensen’s inequality $\displaystyle=\mathbb{E}_{x}[|\sigma(w^{T}x)-\sigma(u^{T}x)|\cdot||x||]$ $\displaystyle\leq\mathbb{E}_{x}[|w^{T}x-u^{T}x|\cdot||x||]$ by Lemma B.1 $\displaystyle\leq||w-u||\mathbb{E}_{x}[||x||^{2}]$ by Cauchy-Schwarz inequality $\displaystyle\leq(L^{2}+1)||w-u||$ by $x\in[-L,L]\times\{1\}$ $$

∎

###### Lemma B.1 .

###### Proof.

###### Lemma B.2 .

###### Proof.

###### Lemma B.3 .

###### Proof.

#### B.2.2 Convergence After a Negative Initialization

###### Lemma B.4 .

Suppose that $x$ is sampled according to $x\sim$ Uniform$(-L,L)\times\{1\}\subseteq\mathbb{R}^{2}$ and that the target parameters $v=(\tilde{v},b_{v})$ satisfy $\tilde{v}>0$ and $b_{v}\leq 0$. Then applying gradient descent with L2 Init regularization with strength $\lambda\geq 0$ according to equation (11) with $w_{0}$ satisfying $\tilde{w_{0}}\in[-1,0)$ and $b_{w_{0}}=0$ and learning rate $\eta=\frac{\alpha}{L^{2}+1}$ where $\alpha\in(0,1]$ such that $\eta\lambda<1$, then for any $t\geq 0$

$$ $\displaystyle\tilde{w}_{0}$ $\displaystyle\leq\tilde{w}_{t}\leq 0,$ (16) $\displaystyle b_{w_{t}}$ $\displaystyle\leq 0,$ (17) $\displaystyle F(w_{t})$ $\displaystyle\geq F(0)$ (18) $$

###### Proof.

We additionally prove the following invariant

$$ $\forall t\geq 0,w_{t}^{T}(-L,1)\geq 0$ (19) $$

For $t=0$ we have that $\tilde{w}_{0}\leq\tilde{w}_{0}\leq 0$ and $b_{w_{0}}\leq 0$ hold trivially by assumption. As for (19), we observe that

$$ $\displaystyle w_{0}^{T}(-L,1)$ $\displaystyle=-L\tilde{w}_{0}+b_{w_{0}}$ $\displaystyle=-L\tilde{w}_{0}$ since $b_{w_{0}}=0$ $\displaystyle\geq 0$ since $\tilde{w}_{0}\in[-L,0)$ $$

Therefore, we suppose that (16), (17), and (19) hold for some arbitrary $t$ and proceed to show that they hold for $t+1$. We begin with establishing, (17).

$$ $\displaystyle b_{w_{t+1}}$ $\displaystyle=b_{w_{t}}-\eta\nabla\bar{F}(w_{t})_{2}$ $\displaystyle=b_{w_{t}}-\eta\nabla F(w_{t})_{2}-\eta\lambda(b_{w_{t}}-b_{w_{0}})$ $\displaystyle=(1-\eta\lambda)b_{w_{t}}-\eta\nabla F(w_{t})_{2}$ by $b_{w_{0}}=0$ $\displaystyle=(1-\eta\lambda)b_{w_{t}}-\eta\mathbb{E}_{x}[\sigma(w^{T}_{t}x)]$ by Lemma B.2 given that $w_{t}\leq 0,\tilde{v}>0,b_{v}\leq 0$ $\displaystyle\leq(1-\eta\lambda)b_{w_{t}}$ since $\sigma(w_{t}^{T}x)\geq 0,\forall x$ $\displaystyle\leq 0$ since $b_{w_{t}}\leq 0$ and $\eta\lambda<1$ $$

Next, for (16) we have that $\tilde{w}_{t+1}\leq 0$ if $-L\tilde{w}_{t+1}+b_{w_{t+1}}=w_{t+1}^{T}(-L,1)\geq 0$ since $b_{w_{t+1}}\leq 0$. This is equivalent to showing that

$$ $(w_{t}-\eta\nabla F(w_{t})-\eta\lambda(w_{t}-w_{0}))^{T}(-L,1)\geq 0$ (20) $$

We proceed by bounding $\eta\nabla F(w_{t})^{T}(-L,1)$. Again invoking Lemma B.2, we have that

$$ $\displaystyle\eta\nabla F(w_{t})^{T}(-L,1)$ $\displaystyle=\eta\mathbb{E}_{x}[\sigma(w_{t}^{T}x)x]^{T}(-L,1)$ $\displaystyle=\eta\mathbb{E}_{x}[\sigma(w_{t}^{T}x)(-L\tilde{x}+1)]$ $\displaystyle\leq\eta\sigma(w_{t}^{T}(-L,1))(L^{2}+1)$ by assumption that $\tilde{w}_{t}\leq 0$ $\displaystyle=\alpha\sigma(w_{t}^{T}(-L,1))$ by choice of $\eta$ $\displaystyle=\alpha w^{T}_{t}(-L,1)$ by assumption of the invariant ( 19 ) $\displaystyle\leq w^{T}_{t}(-L,1)$ since $\alpha\leq 1$ $$

Then, we have that

$$ $\displaystyle(w_{t}-\eta\nabla F(w_{t})-\eta\lambda(w_{t}-w_{0}))^{T}(-L,1)$ $\displaystyle\geq(1-\eta\lambda)w_{t}^{T}(-L,1)+\eta\lambda w_{0}^{T}(-L,1)-w_ {t}^{T}(-L,1)$ $\displaystyle\geq(1-\eta\lambda)w_{t}^{T}(-L,1)+\eta\lambda w_{t}^{T}(-L,1)-w_ {t}^{T}(-L,1)$ $\displaystyle=0$ $$

where the second inequality above follows by $\tilde{w}_{0}\leq\tilde{w}_{t}\leq 0$ and $b_{w_{t}}\leq 0=b_{w_{0}}$. Therefore, it follows that $\tilde{w}_{t+1}\leq 0$. Moreover, this also establishes (19) for $t+1$. As for showing that $\tilde{w}_{t+1}\geq\tilde{w}_{0}$, in order to complete (16), we argue as follows.

$$ $\displaystyle\tilde{w}_{t+1}$ $\displaystyle=\tilde{w}_{t}-\eta\nabla\bar{F}(w_{t})_{1}$ $\displaystyle=\tilde{w}_{t}-\eta\nabla F(w_{t})_{1}-\eta\lambda(\tilde{w}_{t}- \tilde{w}_{0})$ $\displaystyle=(1-\eta\lambda)\tilde{w_{t}}+\eta\lambda\tilde{w}_{0}-\eta \mathbb{E}_{x}[\sigma(w^{T}_{t}x)\tilde{x}]$ by Lemma B.2 given that $w_{t}\leq 0,\tilde{v}>0,b_{v}\leq 0$ $\displaystyle\geq(1-\eta\lambda)\tilde{w_{t}}+\eta\lambda\tilde{w}_{0}$ since $\tilde{x}>0\Rightarrow\sigma(w_{t}^{T}x)=0$ by $w_{t}\leq 0$ $\displaystyle\geq(1-\eta\lambda)\tilde{w}_{0}+\eta\lambda\tilde{w}_{0}$ by $\tilde{w}_{t}\geq\tilde{w}_{0}$ and $\eta\lambda<1$ $\displaystyle=\tilde{w}_{0}$ $$

Therefore, (16) holds for $t+1$. As for (18), given that we have established (16) and (17) it follows that for any $t\geq 0$

$$ $\displaystyle F(w_{t})$ $\displaystyle=\mathbb{E}_{x}[\frac{1}{2}(\sigma(w^{T}_{t}x)-\sigma(v^{T}x))^{2}]$ $\displaystyle\geq\mathbb{E}_{x}[\frac{1}{2}(\sigma(w^{T}_{t}x)-\sigma(v^{T}x)) ^{2}\mathbb{I}_{\{\tilde{x}\geq 0\}}]$ $\displaystyle=\mathbb{E}_{x}[\frac{1}{2}(\sigma(v^{T}x))^{2}\mathbb{I}_{\{ \tilde{x}\geq 0\}}]$ since $w_{t}\leq 0$ and hence $\sigma(w_{t}^{T}x)\mathbb{I}_{\{\tilde{x}\geq 0\}}=0$ $\displaystyle=\mathbb{E}_{x}[\frac{1}{2}(\sigma(v^{T}x))^{2}]$ since $v_{t}^{T}x\leq 0$ for $\tilde{x}<0$ by $\tilde{v}>0$ , $b_{v}\leq 0$ $\displaystyle=F(0)$ $$

∎

###### Lemma B.4 .

###### Proof.

#### B.2.3 Resets After a Negative Initialization

###### Lemma B.5 .

Suppose that $x$ is sampled according to $x\sim$ Uniform$(-L,L)\times\{1\}\subseteq\mathbb{R}^{2}$ and that the target parameters $v=(\tilde{v},b_{v})$ satisfy $\tilde{v}>0$ and $b_{v}\leq 0$. Then applying gradient descent according to equation (10) with $w_{0}$ satisfying $\tilde{w_{0}}\in[-1,0]$ and $b_{w_{0}}=0$ and learning rate $\eta<\frac{1}{L^{2}+1}$, we have that for any threshold $\epsilon>0$, there exists some $t\in\{0,1,\ldots,T=\lceil\frac{16L^{2}C_{\eta}}{\epsilon^{4}}\rceil\}$, where $C_{\eta}=\frac{2}{\eta}F((-1,0))$, such that $\sup_{x\in[-L,L]\times\{1\}}\sigma(w_{t}^{T}x)\leq\epsilon$.

###### Proof.

If $\tilde{w}_{0}\in[-\frac{\epsilon}{L},0]$ then

$$ $\sup_{x\in[-L,L]\times\{1\}}\sigma(w_{t}^{T}x)=-L\tilde{w}_{0}\leq\epsilon$ $$

and so at $t=0$ we immediately have that $\sup_{x\in[-L,L]\times\{1\}}\sigma(w_{t}^{T}x)\leq\epsilon$. Therefore, we consider the case of $\tilde{w}_{0}\in[-L,-\frac{\epsilon}{L})$ and proceed as follows. According to Lemma B.4 and by the choice of learning rate $\eta$, we have that $\forall t\in\{0,1,\ldots,T\},w_{t}\leq 0$. Therefore by Lemma B.2, $\nabla F(\cdot)$ is $(L^{2}+1)$-Lipschitz continuous on the span of $\{w_{0},w_{1},\ldots,w_{T}\}$. Consequently, following the canonical analysis of gradient descent, we have that for any $t\geq 0$

$$ $\displaystyle F(w_{t+1})$ $\displaystyle\leq F(w_{t})+\nabla F(w_{t})^{T}(w_{t+1}-w_{t})+\frac{L^{2}+1}{2 }||w_{t+1}-w_{t}||^{2}$ $\displaystyle=F(w_{t})-(\eta-\frac{(L^{2}+1)\eta^{2}}{2})||\nabla F(w_{t})||^{2}$ $\displaystyle\leq F(w_{t})-\frac{\eta}{2}||\nabla F(w_{t})||^{2}$ $$

where the second line above follows by $w_{t+1}=w_{t}-\eta\nabla F(w_{t})$ and the last line above follows by the fact that

$$ $\displaystyle(\eta-\frac{L^{2}+1}{2}\eta^{2})-\frac{\eta}{2}$ $\displaystyle=\frac{1}{2}(\eta-(L^{2}+1)\eta^{2})$ $\displaystyle\geq\frac{1}{2}(\eta-\eta)$ by $\eta\leq\frac{1}{L^{2}+1}$ $\displaystyle=0$ $$

Then by a telescoping sum,

$$ $\displaystyle\sum_{t=0}^{T}||\nabla F(w_{t})||^{2}$ $\displaystyle\leq\frac{2}{\eta}(F(w_{0})-F(w_{T+1}))$ $\displaystyle\leq\frac{2}{\eta}F((-1,0))$ $$

where the second line follows by the fact that the loss $F(w_{0})$ is maximized at $w_{0}=(-1,0)$ (over the space of initializations of $w_{0}$) and by the fact that the loss $F(w_{T+1})$ is nonnegative. Then defining $C_{\eta}=\frac{2}{\eta}F((-1,0))$, we have that for some $t\in\{0,1,\ldots,T\}$, $||\nabla F(w_{t})||^{2}\leq\frac{C_{\eta}}{T}$. More precisely, we have that

$$ $||\mathbb{E}_{x}[(\sigma(w^{T}x)-\sigma(v^{T}x))\mathbb{I}(w^{T}x\geq 0)x]||^{ 2}\leq\frac{C_{\eta}}{T}$ $$

Given that $x\sim\text{ Uniform}(-L,L)\times\{1\}$, by considering the second element of the gradient, which corresponds to the constant component of $x$, this implies that

$$ $\mathbb{E}_{x}[(\sigma(w_{t}^{T}x)-\sigma(v^{T}x))\mathbb{I}(w^{T}x\geq 0)]^{2 }\leq\frac{C_{\eta}}{T}$ $$

Additionally, by Lemma B.4 we have that $\tilde{w}_{0}\leq\tilde{w}_{t}\leq 0$ and $b_{w_{t}}\leq 0$, and thus by Lemma B.2, we have that

$$ $\mathbb{E}_{x}[\sigma(w^{T}x)]^{2}=\mathbb{E}_{x}[(\sigma(w^{T}x)-\sigma(v^{T} x))\mathbb{I}(w_{t}^{T}x\geq 0)]^{2}\leq\frac{C_{\eta}}{T}$ $$

Hence,

$$ $\mathbb{E}_{x}[\sigma(w_{t}^{T}x)]\leq\sqrt{\frac{C_{\eta}}{T}}$ $$

Then, noting that $\tilde{w}_{0}\leq\tilde{w}_{t}\leq 0$ and $b_{w_{t}}\leq 0$, we have that $2L\mathbb{E}_{x}[\sigma(w_{t}^{T}x)]$ is the area of the triangle formed by the line $w_{t}^{T}x$ over the $x$-axis with its base ranging from its $x$-intercept to $-L$. We denote the length of its base by $b$ and its height by $h$. Given that $\tilde{w}_{t}\leq 0$ it follows that $h=\sigma(w_{t}^{T}(-L,1))=\sup_{x\in[-L,L]\times\{1\}}\sigma(w_{t}^{T}x)$. Additionally, we have that $h=|\tilde{w}_{t}|b\leq|\tilde{w}_{0}|b\leq b$ given that $-1\leq\tilde{w}_{0}\leq\tilde{w}_{t}\leq 0$. Hence we have that

$$ $\frac{h^{2}}{4L}\leq\frac{bh}{4L}=\mathbb{E}_{x}[\sigma(w_{t}^{T}x)]\leq\sqrt{ \frac{C_{\eta}}{T}}$ $$

By the choice of $T$ we have that $4L\sqrt{\frac{C_{\eta}}{T}}\leq\epsilon^{2}$. Hence, we obtain

$$ $\sup_{x\in[-L,L]\times\{1\}}\sigma(w_{t}^{T}x)=h\leq\sqrt{4L\sqrt{\frac{C_{ \eta}}{T}}}\leq\epsilon$ $$

∎

###### Lemma B.5 .

###### Proof.

#### B.2.4 Convergence After a Positive Initialization

###### Lemma B.6 .

Suppose that $x$ is sampled according to $x\sim$ Uniform$(-L,L)\times\{1\}\subseteq\mathbb{R}^{2}$, the target parameters $v=(\tilde{v},b_{v})$ satisfy $\tilde{v}\in[1,\tilde{v}_{\max}]$ and $-\frac{L}{6}\leq b_{v}\leq 0$, and initial parameters $w_{0}$ satisfy $\tilde{w_{0}}\in(0,1]$ and $b_{w_{0}}=0$. Then there exists some $\delta\geq\frac{\tilde{w}_{0}L^{2}}{24}$ such that $F(w_{0})\leq F(0)-\delta$.

###### Proof.

$$ $\displaystyle F(w_{0})$ $\displaystyle=\mathbb{E}_{x}[\frac{1}{2}(\sigma(w_{0}^{T}x)-\sigma(v^{T}x))^{2}]$ $\displaystyle=F(0)+\frac{1}{2}\mathbb{E}_{x}[\sigma(w_{0}^{T}x)^{2}]-\mathbb{E }_{x}[\sigma(w_{0}^{T}x)\sigma(v^{T}x)]$ $\displaystyle=F(0)+\frac{\tilde{w}_{0}^{2}}{4L}\int_{0}^{L}x^{2}dx-\mathbb{E}_ {x}[\sigma(w_{0}^{T}x)\sigma(v^{T}x)]$ by $\tilde{w}_{0}\geq 0$ and $b_{w_{0}}=0$ $\displaystyle=F(0)+\frac{\tilde{w}_{0}^{2}L^{2}}{12}-\mathbb{E}_{x}[\sigma(w_{ 0}^{T}x)\sigma(v^{T}x)]$ $$

Therefore, we define $\delta=-\frac{\tilde{w}_{0}^{2}L^{2}}{12}+\mathbb{E}_{x}[\sigma(w_{0}^{T}x)
\sigma(v^{T}x)]$ and we proceed to show that $\delta\geq\frac{\tilde{w}_{0}L^{2}}{24}$. We let $z=-\frac{b_{v}}{\tilde{v}}$ so that $(z,1)$ is the $x$-intercept of the line $v^{T}x$. Then, $v^{T}x=\tilde{v}(\tilde{x}-z)$. Moreover, $z\in[0,\frac{L}{6}]$ since $b_{v}\in[-\frac{L}{6},0]$ and $\tilde{v}\geq 1$. Therefore, $\forall\tilde{x}\geq z,v^{T}x\geq 0$ and $\forall\tilde{x}<z,v^{T}x<0$. Since $b_{w_{0}}=0$ and $\tilde{w}_{0}\geq 0$, then $\forall\tilde{x}\geq 0,w_{0}^{T}x\geq 0$ and $\forall\tilde{x}<0,w_{0}^{T}x<0$. Thus,

$$ $\sigma(w_{0}^{T}x)\sigma(v^{T}x)=\begin{cases}\tilde{w}_{0}\tilde{x}\tilde{v}( \tilde{x}-z)&\text{if $\tilde{x}\geq z$}\\ 0&\text{if $\tilde{x}<z$}\end{cases}$ (21) $$

From here, we can bound the second term of $\delta$ as follows,

$$ $\displaystyle\mathbb{E}_{x}[\sigma(w_{0}^{T}x)\sigma(v^{T}x)]$ $\displaystyle=\frac{1}{2L}\tilde{w}_{0}\tilde{v}\int_{z}^{L}y^{2}-yzdy$ by ( 21 ) $\displaystyle=\frac{1}{2L}\tilde{w}_{0}\tilde{v}(\frac{L^{3}}{3}-\frac{L^{2}z} {2}+\frac{z^{3}}{6})$ $$

Then,

$$ $\displaystyle\delta$ $\displaystyle=-\frac{\tilde{w}_{0}^{2}L^{2}}{12}+\mathbb{E}_{x}[\sigma(w_{0}^{ T}x)\sigma(v^{T}x)]$ $\displaystyle=-\frac{\tilde{w}_{0}^{2}L^{2}}{12}+\frac{1}{2L}\tilde{w}_{0} \tilde{v}(\frac{L^{3}}{3}-\frac{L^{2}z}{2}+\frac{z^{3}}{6})$ $\displaystyle\geq-\frac{\tilde{w}_{0}L^{2}}{12}+\frac{1}{2L}\tilde{w}_{0} \tilde{v}(\frac{L^{3}}{3}-\frac{L^{3}}{12})$ by $\frac{\tilde{w}_{0}\tilde{v}}{2L}\geq 0$ , $z\in[0,\frac{L}{6}]$ $\displaystyle=-\frac{\tilde{w}_{0}^{2}L^{2}}{12}+\frac{\tilde{w}_{0}\tilde{v}_ {0}L^{2}}{8}$ $\displaystyle=\frac{\tilde{w}_{0}L^{2}}{4}(-\frac{\tilde{w}_{0}}{3}+\frac{ \tilde{v}}{2})$ $\displaystyle\geq\frac{\tilde{w}_{0}L^{2}}{24}$ by $\tilde{v}\geq 1$ , $\tilde{w}_{0}\leq 1$ $$

Thus,

$$ $F(w_{0})=F(0)-\delta=\leq F(0)-\frac{\tilde{w}_{0}L^{2}}{24}$ $$

∎

###### Lemma B.7 .

Suppose that $x$ is sampled according to $x\sim$ Uniform$(-L,L)\times\{1\}\subseteq\mathbb{R}^{2}$, the target parameters $v=(\tilde{v},b_{v})$ satisfy $\tilde{v}\in[1,\tilde{v}_{\max}]$ and $-\frac{L}{6}\leq b_{v}\leq 0$, and initial parameters $w_{0}$ satisfy $\tilde{w_{0}}\in(0,1]$ and $b_{w_{0}}=0$. Then there exists some $\delta\geq\frac{\tilde{w}_{0}L^{2}}{24}$ such that $F(w_{0})\leq F(0)-\delta$. Then defining $\gamma=\frac{\delta^{3}}{3\cdot 12^{2}(||w_{0}||+||v||+1)^{5}(L^{2}+1)^{4}}$ and applying gradient descent according to equation (10) with learning rate $\eta\leq\frac{\gamma}{(L^{2}+1)^{2}}$ we have that $\forall t\geq 0$

$$ $\displaystyle||w_{t}-v||^{2}$ $\displaystyle\leq(1-\eta\gamma)^{t}||w_{0}-v||^{2}$ (22) $\displaystyle F(w_{t})$ $\displaystyle\leq\frac{1}{2}(L^{2}+1)(1-\eta\gamma)^{t}||w_{0}-v||^{2}$ (23) $$

###### Proof.

By Lemma B.6, there exists some $\delta\geq\frac{\tilde{w}_{0}L^{2}}{24}$ such that $F(w_{0})\leq F(0)-\delta$. Then (22) follows by the latter inequality and a slight modification of the proof of Theorem 5.2 (along with Lemma D.2, Lemma D.4, and Lemma D.6) of Vardi et al. (), to extend the result to target parameters $v$ with arbitrary magnitudes. Specifically, a simple modification of the aforementioned proofs implies that setting $\gamma=\frac{\delta^{3}}{3\cdot 12^{2}(||w_{0}||+||v||+1)^{5}c^{8}c^{\prime 2}}$ where we take $c=\max_{x}||x||=\sqrt{L^{2}+1}$ and $c^{\prime}=1$ due to $x\sim\text{ Uniform}(-L,L)\times\{1\}$ guarantees (22). Finally, (23) follows by

$$ $\displaystyle F(w_{t})$ $\displaystyle=\mathbb{E}_{x}[\frac{1}{2}(\sigma(w_{t}^{T}x)-\sigma(v^{T}x))^{2}]$ $\displaystyle\leq\mathbb{E}_{x}[\frac{1}{2}(w_{t}^{T}x-v^{T}x)^{2}]$ by $\sigma(\cdot)$ 1-Lipschitz continuous, Lemma B.1 $\displaystyle\leq\frac{1}{2}||w_{t}-v||^{2}\mathbb{E}_{x}[||x||^{2}]$ by the Cauchy Schwarz inequality $\displaystyle\leq\frac{1}{2}(L^{2}+1)||w_{t}-v||^{2}$ by $x\in[-L,L]\times\{1\}$ $\displaystyle\leq\frac{1}{2}(L^{2}+1)(1-\eta\lambda)^{t}||w_{0}-v||^{2}$ by ( 22 ) $$

∎

###### Lemma B.6 .

###### Proof.

###### Lemma B.7 .

###### Proof.

#### B.2.5 No Resets After a Positive Initialization

###### Lemma B.8 .

Suppose that $x$ is sampled according to $x\sim$ Uniform$(-L,L)\times\{1\}\subseteq\mathbb{R}^{2}$, the target parameters $v=(\tilde{v},b_{v})$ satisfy $\tilde{v}\in[1,\tilde{v}_{\max}]$ and $-\frac{L}{6}\leq b_{v}\leq 0$. Let $\epsilon>0$ such that $3(L-z)\geq\frac{\epsilon}{\tilde{v}}$, then for any $w\in\mathbb{R}^{2}$ such that

$$ $\sup_{x\in[-L,L]\times\{1\}}w^{T}x\leq\epsilon\Rightarrow F(w)\geq F(0)-\frac{ \tilde{v}L}{2}\epsilon$ $$

###### Proof.

$$ $\displaystyle F(w_{t})$ $\displaystyle=\mathbb{E}_{x}[(\sigma(w^{T}x)-\sigma(v^{T}x))^{2}]$ $\displaystyle\geq\mathbb{E}_{x}[(\sigma(w^{T}x)-\sigma(v^{T}x))^{2}\mathbb{I}_ {\{v^{T}x\geq\epsilon\}}]$ $\displaystyle\geq\mathbb{E}_{x}[(\sigma(v^{T}x)-\epsilon)^{2}\mathbb{I}_{\{v^{ T}x\geq\epsilon\}}]$ by $\sup_{x\in[-L,L]\times\{1\}}w^{T}x\leq\epsilon$ $$

Let $z=-\frac{b_{v}}{\tilde{v}}$ such that $v^{T}(z,1)=0$. Then $v^{T}(z+\frac{\epsilon}{\tilde{v}},1)=\epsilon$ and since $\tilde{v}>0$ then $\forall\tilde{x}\geq z+\frac{\epsilon}{\tilde{v}}$ we have that $v^{T}(x,1)\geq\epsilon$. Therefore,

$$ $\displaystyle\mathbb{E}_{x}[(\sigma(v^{T}x)-\epsilon)^{2}\mathbb{I}_{\{v^{T}x \geq\epsilon\}}]$ $\displaystyle=\mathbb{E}_{x}[(v^{T}x-\epsilon)^{2}\mathbb{I}_{\{v^{T}x\geq \epsilon\}}]$ $\displaystyle=\frac{1}{2L}\int_{z+\frac{\epsilon}{\tilde{v}}}^{L}(\tilde{v}y+b _{v}-\epsilon)^{2}dy$ $\displaystyle=\frac{1}{2L}\int_{0}^{L-(z+\frac{\epsilon}{\tilde{v}})}(\tilde{v }y)^{2}dy$ since $\tilde{v}\geq 0$ $\displaystyle=\frac{\tilde{v}^{2}}{6L}(L-z-\frac{\epsilon}{\tilde{v}})^{3}$ $$

By a similar argument, we have that

$$ $\displaystyle F(0)$ $\displaystyle=\mathbb{E}_{x}[\sigma(v^{T}x)^{2}]$ $\displaystyle=\frac{1}{2L}\int_{z}^{L}(\tilde{v}y+b_{v})^{2}dy$ $\displaystyle=\frac{1}{2L}\int_{0}^{L-z}(\tilde{v}y)^{2}dy$ $\displaystyle=\frac{\tilde{v}^{2}}{6L}(L-z)^{3}$ $$

Then,

$$ $\displaystyle F(w)-F(0)$ $\displaystyle\geq\frac{\tilde{v}^{2}}{6L}((L-z-\frac{\epsilon}{\tilde{v}})^{3} -(L-z)^{3})$ $\displaystyle=\frac{\tilde{v}^{2}}{6L}(-3(L-z)^{2}\frac{\epsilon}{\tilde{v}}+3 (L-z)\frac{\epsilon^{2}}{\tilde{v}^{2}}-\frac{\epsilon^{3}}{\tilde{v}^{3}})$ $\displaystyle\geq-\frac{\tilde{v}}{2L}(L-z)^{2}\epsilon$ since $3(L-z)\geq\frac{\epsilon}{\tilde{v}}$ $\displaystyle\geq-\frac{\tilde{v}L}{2}\epsilon$ $$

Hence, we have that

$$ $F(w)\geq F(0)-\frac{\tilde{v}L}{2}\epsilon$ $$

∎

###### Lemma B.9 .

Suppose that $x$ is sampled according to $x\sim$ Uniform$(-L,L)\times\{1\}\subseteq\mathbb{R}^{2}$ and the target parameters $v=(\tilde{v},b_{v})$ satisfy $\tilde{v}\in[1,\tilde{v}_{\max}]$ and $-\frac{L}{6}\leq b_{v}\leq 0$. Let $\epsilon>0$ be a reset threshold and suppose that the initial parameters $w_{0}$ satisfy $\tilde{w}_{0}\in(\tilde{w}_{\min},1]$ and $b_{w_{0}}=0$ such that

$$ $\tilde{w}_{\min}>\frac{12\tilde{v}\epsilon}{L}$ (24) $$

and

$$ $3(L-z)\geq\frac{\epsilon}{\tilde{v}}.$ $$

Then there exists a $\delta\geq\frac{\tilde{w}_{0}L^{2}}{24}$ such that defining $\gamma=\frac{\delta^{3}}{3\cdot 12^{2}(||w_{0}||+||v||+1)^{5}(L^{2}+1)^{4}}$ and applying gradient descent with resets, according to (13) and (14), with learning rate $\eta\leq\frac{\gamma}{(L^{2}+1)^{2}}$ we have that $\mathcal{O}_{\epsilon}(u_{t+1})=$ False $\forall t\geq 0$.

###### Proof.

According to Lemma B.7, there exists some $\delta\geq\frac{\tilde{w_{0}}L^{2}}{24}$ such that

$$ $F(w_{0})\leq F(0)-\delta$ $$

Additionally, Lemma B.7, which utilizes a modified proof of Theorem 5.2 of Vardi et al. (), ensures that

$$ $F(u_{t+1})\leq F(0)-\delta,\forall t\geq 0$ $$

For the sake of contradiction, we suppose that for some $t\geq 0$, $\mathcal{O}_{\epsilon}(u_{t+1})=$ True, or equivalently, that

$$ $\sup_{x\in[-L,L]\times\{1\}}u_{t+1}^{T}x\leq\epsilon$ $$

Then according to Lemma B.8,

$$ $F(u_{t+1})\geq F(0)-\frac{\tilde{v}L\epsilon}{2}$ $$

However, we note that

$$ $\displaystyle\frac{\tilde{w}_{0}L^{2}}{24}$ $\displaystyle\geq\frac{\tilde{w}_{\min}L^{2}}{24}$ $\displaystyle>\frac{\tilde{v}L}{2}\epsilon$ by assumption ( 24 ) $$

Then we have that

$$ $\displaystyle-\frac{\tilde{w}_{0}L^{2}}{24}$ $\displaystyle\geq F(u_{t+1})-F(0)$ $\displaystyle\geq-\frac{\tilde{v}L}{2}\epsilon$ $\displaystyle>-\frac{\tilde{w}_{0}L^{2}}{24}$ $$

which is a contradiction. Therefore, it must follow that $\forall t\geq 0,\mathcal{O}_{\epsilon}(u_{t+1})=$ False.
∎

###### Lemma B.8 .

###### Proof.

###### Lemma B.9 .

###### Proof.

#### B.2.6 Proof of Theorem B.2

###### Theorem B.3 (Restatement of Theorem B.2 ) .

Suppose that $x$ is sampled according to $x\sim$ Uniform$(-L,L)\times\{1\}\subseteq\mathbb{R}^{2}$ and the target parameters $v=(\tilde{v},b_{v})$ satisfy $\tilde{v}\in[1,\tilde{v}_{\max}]$ and $-\frac{L}{6}\leq b_{v}\leq 0$, where we denote $v_{\max}=(\tilde{v}_{\max},-\frac{L}{6})$. Let $\epsilon>0$ be a reset threshold and suppose that the initial parameters $w_{0}$ are sampled uniformly from $\tilde{w}_{0}\sim[-1,-\tilde{w}_{\min})\cup(\tilde{w}_{\min},1]$ and $b_{w_{0}}=0$ such that

$$ $\tilde{w}_{\min}>\frac{12\tilde{v}\epsilon}{L}$ $$

and

$$ $3(L-z)\geq\frac{\epsilon}{\tilde{v}}.$ $$

Then gradient descent with a constant learning rate of

$$ $\eta\leq\frac{\tilde{w}_{\min}^{3}L^{6}}{3\cdot 12^{2}\cdot 24^{3}(2+||v_{\max }||)^{5}(L^{2}+1)^{6}}$ $$

and with resets, i.e. (13) and (14), attains an average regret of

$$ $\frac{1}{T}\mathbb{E}[R_{T}]\leq\frac{C}{T}$ $$

where

$$ $C=\lceil\frac{32L^{2}F((-1,0))}{\eta\epsilon^{4}}\rceil F((-1,0))+\frac{3}{2 \eta^{2}}\left((\tilde{v}_{\max}-\tilde{w}_{\min})^{2})+(\frac{L}{6})^{2}\right)$ $$

###### Proof.

In order to apply Lemmas B.5, B.7, and B.9 we verify that

$$ $\eta\leq\frac{1}{L^{2}+1}$ (25) $$

and

$$ $\eta\leq\frac{\gamma}{(L^{2}+1)^{2}}$ (26) $$

where $\gamma=\frac{\delta^{3}}{3\cdot 12^{2}(||w_{0}||+||v||+1)^{5}(L^{2}+1)^{4}}$ and $\delta\geq\frac{\tilde{w}_{0}L^{2}}{24}$ and where $w_{0}$ is an arbitrary (re)initialization of $w$ given the prior distribution. For (25) we note that $\tilde{w}_{\min}\leq 1\leq 3\cdot 12^{2}\cdot 24^{3},(2+||v_{\max}||)$ and so

$$ $\displaystyle\eta$ $\displaystyle=\frac{\tilde{w}_{\min}^{3}L^{6}}{3\cdot 12^{2}\cdot 24^{3}(2+||v _{\max}||)^{5}(L^{2}+1)^{6}}$ $\displaystyle\leq\frac{L^{6}}{(L^{2}+1)^{6}}$ $\displaystyle\leq\frac{(L^{2}+1)^{3}}{(L^{2}+1)^{6}}$ $\displaystyle=\frac{1}{(L^{2}+1)^{3}}$ $\displaystyle\leq\frac{1}{L^{2}+1}$ $$

As for (26) we proceed as follows

$$ $\displaystyle\eta$ $\displaystyle=\frac{\tilde{w}_{\min}^{3}L^{6}}{3\cdot 12^{2}\cdot 24^{3}(2+||v _{\max}||)^{5}(L^{2}+1)^{6}}$ $\displaystyle\leq\frac{\tilde{w}_{0}^{3}L^{6}}{3\cdot 12^{2}\cdot 24^{3}(||w_{ 0}||+||v||+1)^{5}(L^{2}+1)^{6}}$ $\displaystyle\leq\frac{\delta^{3}}{3\cdot 12^{2}(||w_{0}||+||v||+1)^{5}(L^{2}+ 1)^{6}}$ by $\delta\geq\frac{\tilde{w}_{0}L^{2}}{24}$ $\displaystyle=\frac{\gamma}{(L^{2}+1)^{2}}$ $$

We continue by upper bounding the regret as follows

$$ $\displaystyle\mathbb{E}[R_{T}]$ $\displaystyle\leq\sum_{r=0}^{\infty}\mathbb{E}[R_{T}|\text{$r$ resets occur}]$ $$

By Lemma B.5 and Lemma B.9 and the choice of learning rate $\eta$, we only ever reset if $\tilde{w}_{t}$ is (re)initialized such that $\tilde{w}_{t}<0$. Conversely, if we (re)initialize the parameters such that $\tilde{w}_{t}>0$ then we never reset for subsequent gradient descent updates. Additionally, since $w_{t}$ is reinitialized by an independent draw from its initial distribution, then for any particular reset count $r$ we have that

$$ $\mathbb{P}(\text{$r$ resets occur})=\mathbb{P}(\tilde{w}_{0}<0)^{r}\cdot \mathbb{P}(\tilde{w}_{0}>0)=\frac{1}{2^{r+1}}$ $$

Where $\mathbb{P}(\tilde{w}_{0}<0)=\mathbb{P}(\tilde{w}_{0}>0)=\frac{1}{2}$ by the fact $\tilde{w}_{0}$ is sampled uniformly from $[-1,-\tilde{w}_{\min})\cup(\tilde{w}_{\min},1]$. Hence, we have that

$$ $\mathbb{E}[R_{T}|\text{$r$ resets occur}]\leq\mathbb{P}(\text{$r$ resets occur })(rM_{-}+M_{+})=\frac{1}{2^{r+1}}(rM_{-}+M_{+})$ (27) $$

Where $M_{-}$ is an upper bound on the total loss during any period of consecutive time steps $t$ to $t^{\prime}$ such that $w_{t}$ is a (re)initialization of $w$ such that $\tilde{w}_{t}<0$ and $t^{\prime}$ is the earliest reset after $t$. While $M_{+}$ is an upper bound on the total loss for time periods after and including $t$ where $w_{t}$ is a (re)initialization of $w$ such that $\tilde{w}_{t}>0$.

By the choice of learning rate $\eta$ and Lemma
B.5, if $w$ is (re)initialized such that $\tilde{w}_{t}<0$ then within $T_{\text{reset}}\leq\lceil\frac{32L^{2}F((-1,0))}{\eta\epsilon^{4}}\rceil$ gradient descent updates $w$ is reset. Moreover, the loss $F(w_{t^{\prime}})$ is at most $F((-1,0))$ for time steps $t^{\prime}$ preceding a reset of $w$ as loss is maximized at $w_{t}=(-1,0)$ over initializations and choosing learning rate $\eta$ at most $\frac{1}{L^{2}+1}$, the Lipschitz constant of $\nabla F$ (Lemma B.3), guarantees that loss never exceeds $F((-1,0))$. Thus,

$$ $M_{-}\leq T_{\text{reset}}F((-1,0))$ (28) $$

As for $M_{+}$ we can construct the following upper bound

$$ $\displaystyle M_{+}$ $\displaystyle\leq\mathbb{E}_{w_{0}}[\sum_{t=0}^{\infty}F(w_{t})|\tilde{w}_{0}>0]$ $\displaystyle\leq\sum_{t=0}^{\infty}(L^{2}+1)(1-\eta\gamma)^{t}\mathbb{E}_{w_{ 0}}[||w_{0}-v||^{2}|\tilde{w}_{0}>0]$ by Lemma B.7 $\displaystyle=\frac{L^{2}+1}{\eta\gamma}\mathbb{E}_{w_{0}}[||w_{0}-v||^{2}| \tilde{w}_{0}>0]$ by geometric series $\displaystyle\leq\frac{1}{\eta\gamma}(L^{2}+1)\left((\tilde{v}_{\max}-\tilde{w }_{\min})^{2}+(\frac{L}{6})^{2}\right)$ by assumption on $w_{0}$ , $v$ $\displaystyle\leq\frac{1}{\eta^{2}}\left((\tilde{v}_{\max}-\tilde{w}_{\min})^{ 2}+(\frac{L}{6})^{2}\right)$ by $\eta\leq\frac{\gamma}{L^{2}+1}$ $$

Where the use of the geometric series in the third line above is valid by

$$ $\eta\gamma<1$ $$

by the assumptions on $\eta$ and $\gamma$. Then returning to our goal of bounding the average regret, we observe that

$$ $\displaystyle\mathbb{E}[R_{T}]$ $\displaystyle\leq\sum_{r=0}^{\infty}\mathbb{E}[R_{T}|\text{$r$ resets occur}]$ $\displaystyle\leq\sum_{r=0}^{\infty}\frac{1}{2^{r+1}}(rM_{-}+M_{+})$ by ( 27 ) $\displaystyle=\frac{1}{2}M_{+}+(M_{-}+M_{+})\sum_{r=0}^{\infty}\frac{r}{2^{r+1}}$ $\displaystyle=\frac{1}{2}M_{+}+(M_{-}+M_{+})$ by arithmetico-geometric series $\displaystyle=M_{-}+\frac{3}{2}M_{+}$ $$

Then defining $C=M_{-}+\frac{3}{2}M_{+}$, we have the desired result of

$$ $\frac{1}{T}\mathbb{E}[R_{T}]\leq\frac{C}{T}$ $$

∎

###### Theorem B.3 (Restatement of Theorem B.2 ) .

###### Proof.

## Appendix C Additional Experimental Details and Hyperparameter Sweep

With SGD we train with learning rate $10^{-2}$ on all problems except Random Label MNIST, for which we train with learning rate $10^{-1}$. With Adam we train with learning rate $10^{-3}$ on all problems, including Permuted Shakespeare and we use the standard parameters of $\beta_{1}=0.9,\beta_{2}=0.999$, and $\epsilon=10^{-7}$. For Permuted Shakespeare we train our networks solely with Adam.

For each algorithm we vary its hyperparameter(s) by an appropriate constant over 7 choices, effectively varying the hyperparameters over a log scale. With the exception of the Permuted Shakespeare experiment, we limit over hyperparameter search to 5 choices. In Table 4 we provide the hyperparameter sweep for the 4 benchmark problems. CBP’s replacement rate $r$ is to be interpreted as one replacement per layer every $r^{-1}$ training examples, as presented in Dohare et al. (). ReDO’s reset frequency $r$ determines the frequency of resets in units of tasks, as implemented and evaluated in Kumar et al. ().

**Table 4: Hyperparameter sweep for the Permuted MNIST (PM), Random Label MNIST (RM), Random Label CIFAR (RC), and Continual ImageNet (CI) problems.**
| Hyperparameter Strength |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Algorithm | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| L2 Reg. ($\lambda$) | $10^{-6}$ | $10^{-5}$ | $10^{-4}$ | $10^{-3}$ | $10^{-2}$ | $10^{-1}$ | $10^{0}$ |
| L2 Init ($\lambda$) | $10^{-6}$ | $10^{-5}$ | $10^{-4}$ | $10^{-3}$ | $10^{-2}$ | $10^{-1}$ | $10^{0}$ |
| S&P (1-p) | $10^{-8}$ | $10^{-7}$ | $10^{-6}$ | $10^{-5}$ | $10^{-4}$ | $10^{-3}$ | $10^{-2}$ |
| S&P $(\sigma)$ | $10^{-6}$ | $10^{-5}$ | $10^{-4}$ | $10^{-3}$ | $10^{-2}$ | $10^{-1}$ | $10^{0}$ |
| CBP $(r)$ | $10^{-7}$ | $10^{-6}$ | $10^{-5}$ | $10^{-4}$ | $10^{-3}$ | $10^{-2}$ | $10^{-1}$ |
| ReDO $(\tau)$ | 0 | 0.01 | 0.02 | 0.04 | 0.08 | 0.16 | 0.32 |
| ReDO $(r)$ | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
| SNR $(\eta)$ | 0.08 | 0.04 | 0.02 | 0.01 | 0.005 | 0.0025 | 0.00125 |

**Table 5: Hyperparameter sweep for the Permuted Shakespeare problem. For the combination of SNR and L2 regularization we use the regularization strength of $10^{-4}$, the best performing regularization strength for L2 regularization, and vary the rejection percentile threshold $\eta$**
| Hyperparameter Strength |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- |
| Algorithm | 0 | 1 | 2 | 3 | 4 |
| L2 Reg. ($\lambda$) | $10^{-6}$ | $10^{-5}$ | $10^{-4}$ | $10^{-3}$ | $10^{-2}$ |
| L2 Init ($\lambda$) | $10^{-6}$ | $10^{-5}$ | $10^{-4}$ | $10^{-3}$ | $10^{-2}$ |
| SNR $(\eta)$ | 0.1 | 0.05 | 0.03 | 0.01 | 0.001 |
| SNR + L2 Reg $(\eta)$ | 0.1 | 0.05 | 0.03 | 0.01 | 0.001 |

**Table 6: Average loss of the final epoch of each task in Permuted Shakespeare, averaged over the final 50 tasks, reported as mean $\pm$ standard deviation over5 random seeds.**
| Hyperparameter Strength |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- |
| Algorithm | 0 | 1 | 2 | 3 | 4 |
| L2 Reg. ($\lambda$) | $1.284$ | $0.883$ | $0.348$ | $0.853$ | $4.269$ |
|  | $\pm 0.037$ | $\pm 0.059$ | $\pm 0.093$ | $\pm 0.061$ | $\pm 0.013$ |
| L2 Init ($\lambda$) | $1.791$ | $1.481$ | $1.641$ | $2.429$ | $5.598$ |
|  | $\pm 0.056$ | $\pm 0.050$ | $\pm 0.067$ | $\pm 0.124$ | $\pm 0.030$ |
| SNR $(\eta)$ | $3.034$ | $3.024$ | $3.012$ | $3.027$ | $3.025$ |
|  | $\pm 0.022$ | $\pm 0.041$ | $\pm 0.025$ | $\pm 0.029$ | $\pm 0.045$ |
| SNR + L2 Reg $(\eta)$ | $0.315$ | $0.276$ | $0.325$ | $0.293$ | $0.269$ |
|  | $\pm 0.084$ | $\pm 0.078$ | $\pm 0.068$ | $\pm 0.065$ | $\pm 0.025$ |

Figure: Figure 5: Permuted MNIST hyperparameter sweep results over 5 seeds.
Refer to caption: x11.png

Figure: Figure 6: Random LabeL MNIST hyperparameter sweep result over 5 seeds.
Refer to caption: x13.png

Figure: Figure 7: Random Label CIFAR hyperparameter sweep results over 5 seeds.
Refer to caption: x15.png

Figure: Figure 8: Continual ImageNet hyperparameter sweep results over 5 seeds.
Refer to caption: x17.png

**Table 7: Performance on Permuted MNIST with Different Hyperparameters**
|  | Hyperparameter Strength Log Scale |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Algorithm | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| SNR $(\eta)$ | 0.849 | 0.849 | 0.848 | 0.847 | 0.850 | 0.848 | 0.847 |
|  | $\pm$0.002 | $\pm$0.003 | $\pm$0.003 | $\pm$0.004 | $\pm$0.002 | $\pm$0.002 | $\pm$0.002 |
| L2 Init $(\lambda)$ | 0.716 | 0.731 | 0.790 | 0.827 | 0.824 | 0.758 | 0.288 |
|  | $\pm$0.001 | $\pm$0.001 | $\pm$0.001 | $\pm$0.002 | $\pm$0.001 | $\pm$0.001 | $\pm$0.017 |
| L2 Reg. $(\lambda)$ | 0.713 | 0.729 | 0.787 | 0.816 | 0.790 | 0.110 | 0.104 |
|  | $\pm$0.002 | $\pm$0.002 | $\pm$0.001 | $\pm$0.002 | $\pm$0.003 | $\pm$0.003 | $\pm$0.002 |
| S&P $(1-p)$ | 0.709 | 0.716 | 0.770 | 0.826 | 0.804 | 0.615 | 0.106 |
|  | $\pm$0.001 | $\pm$0.002 | $\pm$0.001 | $\pm$0.002 | $\pm$0.004 | $\pm$0.001 | $\pm$0.003 |
| S&P $(\sigma)$ | 0.823 | 0.823 | 0.825 | 0.826 | 0.784 | 0.110 | 0.110 |
|  | $\pm$0.001 | $\pm$0.002 | $\pm$0.002 | $\pm$0.002 | $\pm$0.002 | $\pm$0.002 | $\pm$0.002 |
| ReDO ($\tau$) | 0.710 | 0.832 | 0.817 | 0.742 | 0.743 | 0.743 | 0.743 |
|  | $\pm$0.007 | $\pm$0.001 | $\pm$0.011 | $\pm$0.018 | $\pm$0.018 | $\pm$0.018 | $\pm$0.018 |
| ReDO $(r)$ | 0.815 | 0.824 | 0.830 | 0.832 | 0.819 | 0.808 | 0.778 |
|  | $\pm$0.004 | $\pm$0.002 | $\pm$0.001 | $\pm$0.001 | $\pm$0.005 | $\pm$0.006 | $\pm$0.013 |
| CBP $(r)$ | 0.726 | 0.763 | 0.823 | 0.843 | 0.844 | 0.648 | 0.655 |
|  | $\pm$0.006 | $\pm$0.002 | $\pm$0.002 | $\pm$0.001 | $\pm$0.002 | $\pm$0.000 | $\pm$0.000 |
| Layer Norm | 0.689 | 0.689 | 0.689 | 0.689 | 0.689 | 0.689 | 0.689 |
|  | $\pm$0.003 | $\pm$0.003 | $\pm$0.003 | $\pm$0.003 | $\pm$0.003 | $\pm$0.003 | $\pm$0.003 |
| SGD | 0.710 | 0.710 | 0.710 | 0.710 | 0.710 | 0.710 | 0.710 |
|  | $\pm$0.007 | $\pm$0.007 | $\pm$0.007 | $\pm$0.007 | $\pm$0.007 | $\pm$0.007 | $\pm$0.007 |

**Table 8: Performance on Permuted MNIST with Different Hyperparameters**
|  | Hyperparameter Strength Log Scale |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Algorithm | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| SNR $(\eta)$ | 0.887 | 0.885 | 0.880 | 0.876 | 0.872 | 0.867 | 0.872 |
|  | $\pm$0.002 | $\pm$0.001 | $\pm$0.002 | $\pm$0.002 | $\pm$0.001 | $\pm$0.002 | $\pm$0.012 |
| L2 Init $(\lambda)$ | 0.790 | 0.837 | 0.864 | 0.884 | 0.870 | 0.784 | 0.276 |
|  | $\pm$0.001 | $\pm$0.002 | $\pm$0.002 | $\pm$0.002 | $\pm$0.002 | $\pm$0.001 | $\pm$0.008 |
| L2 Reg. $(\lambda)$ | 0.792 | 0.837 | 0.858 | 0.878 | 0.859 | 0.365 | 0.103 |
|  | $\pm$0.002 | $\pm$0.002 | $\pm$0.002 | $\pm$0.002 | $\pm$0.004 | $\pm$0.008 | $\pm$0.002 |
| S&P $(1-p)$ | 0.638 | 0.858 | 0.877 | 0.876 | 0.768 | 0.105 | 0.102 |
|  | $\pm$0.005 | $\pm$0.002 | $\pm$0.002 | $\pm$0.002 | $\pm$0.001 | $\pm$0.003 | $\pm$0.001 |
| S&P $(\sigma)$ | 0.874 | 0.875 | 0.875 | 0.877 | 0.877 | 0.583 | 0.115 |
|  | $\pm$0.002 | $\pm$0.002 | $\pm$0.002 | $\pm$0.002 | $\pm$0.002 | $\pm$0.003 | $\pm$0.001 |
| ReDO ($\tau$) | 0.636 | 0.846 | 0.847 | 0.847 | 0.847 | 0.847 | 0.847 |
|  | $\pm$0.009 | $\pm$0.002 | $\pm$0.001 | $\pm$0.001 | $\pm$0.001 | $\pm$0.001 | $\pm$0.001 |
| ReDO $(r)$ | 0.830 | 0.837 | 0.842 | 0.845 | 0.847 | 0.841 | 0.825 |
|  | $\pm$0.004 | $\pm$0.002 | $\pm$0.002 | $\pm$0.002 | $\pm$0.001 | $\pm$0.001 | $\pm$0.001 |
| CBP $(r)$ | 0.723 | 0.773 | 0.817 | 0.857 | 0.876 | 0.733 | 0.720 |
|  | $\pm$0.012 | $\pm$0.004 | $\pm$0.002 | $\pm$0.002 | $\pm$0.002 | $\pm$0.001 | $\pm$0.008 |
| Layer Norm | 0.661 | 0.661 | 0.661 | 0.661 | 0.661 | 0.661 | 0.661 |
|  | $\pm$0.001 | $\pm$0.001 | $\pm$0.001 | $\pm$0.001 | $\pm$0.001 | $\pm$0.001 | $\pm$0.001 |
| Adam | 0.636 | 0.636 | 0.636 | 0.636 | 0.636 | 0.636 | 0.636 |
|  | $\pm$0.009 | $\pm$0.009 | $\pm$0.009 | $\pm$0.009 | $\pm$0.009 | $\pm$0.009 | $\pm$0.009 |

**Table 9: Performance on Random Label MNIST with Different Hyperparameters**
|  | Hyperparameter Strength Log Scale |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Algorithm | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| SNR $(\eta)$ | 0.975 | 0.975 | 0.974 | 0.974 | 0.974 | 0.973 | 0.973 |
|  | $\pm$0.001 | $\pm$0.001 | $\pm$0.000 | $\pm$0.000 | $\pm$0.001 | $\pm$0.001 | $\pm$0.001 |
| L2 Init $(\lambda)$ | 0.115 | 0.114 | 0.181 | 0.881 | 0.912 | 0.191 | 0.101 |
|  | $\pm$0.006 | $\pm$0.009 | $\pm$0.027 | $\pm$0.017 | $\pm$0.006 | $\pm$0.008 | $\pm$0.010 |
| L2 Reg. $(\lambda)$ | 0.115 | 0.115 | 0.115 | 0.126 | 0.801 | 0.113 | 0.108 |
|  | $\pm$0.006 | $\pm$0.006 | $\pm$0.006 | $\pm$0.013 | $\pm$0.010 | $\pm$0.007 | $\pm$0.009 |
| S&P $(1-p)$ | 0.112 | 0.161 | 0.138 | 0.550 | 0.924 | 0.114 | 0.109 |
|  | $\pm$0.008 | $\pm$0.009 | $\pm$0.008 | $\pm$0.023 | $\pm$0.003 | $\pm$0.006 | $\pm$0.009 |
| S&P $(\sigma)$ | 0.917 | 0.913 | 0.910 | 0.919 | 0.924 | 0.181 | 0.116 |
|  | $\pm$0.005 | $\pm$0.004 | $\pm$0.007 | $\pm$0.004 | $\pm$0.003 | $\pm$0.005 | $\pm$0.006 |
| ReDO ($\tau$) | 0.115 | 0.600 | 0.642 | 0.719 | 0.705 | 0.705 | 0.705 |
|  | $\pm$0.006 | $\pm$0.023 | $\pm$0.030 | $\pm$0.021 | $\pm$0.021 | $\pm$0.021 | $\pm$0.021 |
| ReDO $(r)$ | 0.111 | 0.111 | 0.109 | 0.116 | 0.117 | 0.233 | 0.719 |
|  | $\pm$0.008 | $\pm$0.008 | $\pm$0.008 | $\pm$0.019 | $\pm$0.019 | $\pm$0.022 | $\pm$0.021 |
| CBP $(r)$ | 0.389 | 0.931 | 0.945 | 0.953 | 0.929 | 0.115 | 0.115 |
|  | $\pm$0.031 | $\pm$0.051 | $\pm$0.012 | $\pm$0.005 | $\pm$0.002 | $\pm$0.006 | $\pm$0.006 |
| Layer Norm | 0.145 | 0.145 | 0.145 | 0.145 | 0.145 | 0.145 | 0.145 |
|  | $\pm$0.013 | $\pm$0.013 | $\pm$0.013 | $\pm$0.013 | $\pm$0.013 | $\pm$0.013 | $\pm$0.013 |
| SGD | 0.115 | 0.115 | 0.115 | 0.115 | 0.115 | 0.115 | 0.115 |
|  | $\pm$0.006 | $\pm$0.006 | $\pm$0.006 | $\pm$0.006 | $\pm$0.006 | $\pm$0.006 | $\pm$0.006 |

**Table 10: Performance on Random Label MNIST with Different Hyperparameters**
|  | Hyperparameter Strength Log Scale |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Algorithm | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| SNR $(\eta)$ | 0.979 | 0.981 | 0.979 | 0.978 | 0.976 | 0.969 | 0.966 |
|  | $\pm$0.001 | $\pm$0.001 | $\pm$0.002 | $\pm$0.001 | $\pm$0.002 | $\pm$0.001 | $\pm$0.003 |
| L2 Init $(\lambda)$ | 0.312 | 0.929 | 0.958 | 0.960 | 0.905 | 0.114 | 0.098 |
|  | $\pm$0.050 | $\pm$0.011 | $\pm$0.007 | $\pm$0.001 | $\pm$0.003 | $\pm$0.004 | $\pm$0.009 |
| L2 Reg. $(\lambda)$ | 0.243 | 0.918 | 0.946 | 0.944 | 0.506 | 0.113 | 0.107 |
|  | $\pm$0.038 | $\pm$0.008 | $\pm$0.009 | $\pm$0.004 | $\pm$0.043 | $\pm$0.007 | $\pm$0.009 |
| S&P $(1-p)$ | 0.115 | 0.955 | 0.946 | 0.931 | 0.114 | 0.109 | 0.102 |
|  | $\pm$0.006 | $\pm$0.004 | $\pm$0.008 | $\pm$0.005 | $\pm$0.006 | $\pm$0.009 | $\pm$0.004 |
| S&P $(\sigma)$ | 0.945 | 0.941 | 0.942 | 0.943 | 0.955 | 0.243 | 0.121 |
|  | $\pm$0.009 | $\pm$0.009 | $\pm$0.007 | $\pm$0.013 | $\pm$0.004 | $\pm$0.015 | $\pm$0.006 |
| ReDO ($\tau$) | 0.115 | 0.306 | 0.381 | 0.553 | 0.670 | 0.588 | 0.588 |
|  | $\pm$0.006 | $\pm$0.017 | $\pm$0.023 | $\pm$0.028 | $\pm$0.019 | $\pm$0.031 | $\pm$0.031 |
| ReDO $(r)$ | 0.115 | 0.115 | 0.120 | 0.109 | 0.112 | 0.122 | 0.670 |
|  | $\pm$0.006 | $\pm$0.006 | $\pm$0.009 | $\pm$0.008 | $\pm$0.008 | $\pm$0.028 | $\pm$0.019 |
| CBP $(r)$ | 0.124 | 0.199 | 0.482 | 0.922 | 0.949 | 0.115 | 0.115 |
|  | $\pm$0.030 | $\pm$0.055 | $\pm$0.077 | $\pm$0.007 | $\pm$0.004 | $\pm$0.006 | $\pm$0.006 |
| Layer Norm | 0.115 | 0.115 | 0.115 | 0.115 | 0.115 | 0.115 | 0.115 |
|  | $\pm$0.006 | $\pm$0.006 | $\pm$0.006 | $\pm$0.006 | $\pm$0.006 | $\pm$0.006 | $\pm$0.006 |
| Adam | 0.115 | 0.115 | 0.115 | 0.115 | 0.115 | 0.115 | 0.115 |
|  | $\pm$0.006 | $\pm$0.006 | $\pm$0.006 | $\pm$0.006 | $\pm$0.006 | $\pm$0.006 | $\pm$0.006 |

**Table 11: Performance on Continual ImageNet with Different Hyperparameters**
|  | Hyperparameter Strength Log Scale |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Algorithm | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| SNR $(\eta)$ | 0.887 | 0.888 | 0.893 | 0.886 | 0.886 | 0.886 | 0.886 |
|  | $\pm$0.009 | $\pm$0.007 | $\pm$0.006 | $\pm$0.004 | $\pm$0.004 | $\pm$0.004 | $\pm$0.004 |
| L2 Init $(\lambda)$ | 0.781 | 0.780 | 0.827 | 0.831 | 0.722 | 0.646 | 0.573 |
|  | $\pm$0.028 | $\pm$0.016 | $\pm$0.011 | $\pm$0.008 | $\pm$0.014 | $\pm$0.014 | $\pm$0.018 |
| L2 Reg. $(\lambda)$ | 0.775 | 0.800 | 0.833 | 0.819 | 0.488 | 0.488 | 0.491 |
|  | $\pm$0.010 | $\pm$0.013 | $\pm$0.012 | $\pm$0.007 | $\pm$0.000 | $\pm$0.000 | $\pm$0.001 |
| S&P $(1-p)$ | 0.778 | 0.784 | 0.752 | 0.815 | 0.853 | 0.488 | 0.488 |
|  | $\pm$0.023 | $\pm$0.024 | $\pm$0.073 | $\pm$0.010 | $\pm$0.008 | $\pm$0.000 | $\pm$0.000 |
| S&P $(\sigma)$ | 0.848 | 0.839 | 0.849 | 0.853 | 0.844 | 0.497 | 0.500 |
|  | $\pm$0.002 | $\pm$0.010 | $\pm$0.008 | $\pm$0.008 | $\pm$0.010 | $\pm$0.005 | $\pm$0.000 |
| ReDO ($\tau$) | 0.785 | 0.856 | 0.870 | 0.843 | 0.721 | 0.727 | 0.726 |
|  | $\pm$0.024 | $\pm$0.012 | $\pm$0.010 | $\pm$0.015 | $\pm$0.041 | $\pm$0.043 | $\pm$0.040 |
| ReDO $(r)$ | 0.827 | 0.824 | 0.844 | 0.870 | 0.867 | 0.864 | 0.836 |
|  | $\pm$0.027 | $\pm$0.038 | $\pm$0.029 | $\pm$0.010 | $\pm$0.016 | $\pm$0.011 | $\pm$0.009 |
| CBP $(r)$ | 0.777 | 0.791 | 0.792 | 0.837 | 0.840 | 0.488 | 0.488 |
|  | $\pm$0.022 | $\pm$0.016 | $\pm$0.013 | $\pm$0.012 | $\pm$0.008 | $\pm$0.000 | $\pm$0.000 |
| Layer Norm | 0.818 | 0.818 | 0.818 | 0.818 | 0.818 | 0.818 | 0.818 |
|  | $\pm$0.011 | $\pm$0.011 | $\pm$0.011 | $\pm$0.011 | $\pm$0.011 | $\pm$0.011 | $\pm$0.011 |
| SGD | 0.785 | 0.785 | 0.785 | 0.785 | 0.785 | 0.785 | 0.785 |
|  | $\pm$0.024 | $\pm$0.024 | $\pm$0.024 | $\pm$0.024 | $\pm$0.024 | $\pm$0.024 | $\pm$0.024 |

**Table 12: Performance on Continual ImageNet with Different Hyperparameters**
|  | Hyperparameter Strength Log Scale |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Algorithm | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| SNR $(\eta)$ | 0.840 | 0.840 | 0.839 | 0.839 | 0.840 | 0.840 | 0.840 |
|  | $\pm$0.002 | $\pm$0.005 | $\pm$0.006 | $\pm$0.006 | $\pm$0.006 | $\pm$0.006 | $\pm$0.006 |
| L2 Init $(\lambda)$ | 0.703 | 0.767 | 0.814 | 0.826 | 0.819 | 0.757 | 0.640 |
|  | $\pm$0.052 | $\pm$0.025 | $\pm$0.005 | $\pm$0.009 | $\pm$0.005 | $\pm$0.011 | $\pm$0.014 |
| L2 Reg. $(\lambda)$ | 0.767 | 0.791 | 0.802 | 0.797 | 0.749 | 0.492 | 0.492 |
|  | $\pm$0.018 | $\pm$0.013 | $\pm$0.012 | $\pm$0.009 | $\pm$0.021 | $\pm$0.001 | $\pm$0.000 |
| S&P $(1-p)$ | 0.506 | 0.813 | 0.811 | 0.787 | 0.492 | 0.492 | 0.492 |
|  | $\pm$0.025 | $\pm$0.010 | $\pm$0.008 | $\pm$0.008 | $\pm$0.001 | $\pm$0.000 | $\pm$0.000 |
| S&P $(\sigma)$ | 0.806 | 0.807 | 0.804 | 0.803 | 0.813 | 0.494 | 0.500 |
|  | $\pm$0.012 | $\pm$0.004 | $\pm$0.011 | $\pm$0.007 | $\pm$0.010 | $\pm$0.000 | $\pm$0.001 |
| ReDO ($\tau$) | 0.582 | 0.802 | 0.610 | 0.730 | 0.725 | 0.732 | 0.730 |
|  | $\pm$0.075 | $\pm$0.018 | $\pm$0.120 | $\pm$0.012 | $\pm$0.016 | $\pm$0.016 | $\pm$0.013 |
| ReDO $(r)$ | 0.763 | 0.775 | 0.788 | 0.796 | 0.801 | 0.802 | 0.790 |
|  | $\pm$0.033 | $\pm$0.018 | $\pm$0.013 | $\pm$0.007 | $\pm$0.008 | $\pm$0.018 | $\pm$0.006 |
| CBP $(r)$ | 0.562 | 0.747 | 0.770 | 0.802 | 0.819 | 0.677 | 0.712 |
|  | $\pm$0.087 | $\pm$0.032 | $\pm$0.014 | $\pm$0.004 | $\pm$0.003 | $\pm$0.092 | $\pm$0.039 |
| Layer Norm | 0.709 | 0.709 | 0.709 | 0.709 | 0.709 | 0.709 | 0.709 |
|  | $\pm$0.014 | $\pm$0.014 | $\pm$0.014 | $\pm$0.014 | $\pm$0.014 | $\pm$0.014 | $\pm$0.014 |
| Adam | 0.582 | 0.582 | 0.582 | 0.582 | 0.582 | 0.582 | 0.582 |
|  | $\pm$0.075 | $\pm$0.075 | $\pm$0.075 | $\pm$0.075 | $\pm$0.075 | $\pm$0.075 | $\pm$0.075 |

**Table 13: Performance on Random Label CIFAR with Different Hyperparameters**
|  | Hyperparameter Strength Log Scale |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Algorithm | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| SNR $(\eta)$ | 0.975 | 0.974 | 0.969 | 0.973 | 0.970 | 0.971 | 0.973 |
|  | $\pm$0.003 | $\pm$0.001 | $\pm$0.006 | $\pm$0.004 | $\pm$0.004 | $\pm$0.004 | $\pm$0.002 |
| L2 Init $(\lambda)$ | 0.313 | 0.366 | 0.818 | 0.977 | 0.979 | 0.966 | 0.141 |
|  | $\pm$0.076 | $\pm$0.096 | $\pm$0.165 | $\pm$0.005 | $\pm$0.003 | $\pm$0.004 | $\pm$0.006 |
| L2 Reg. $(\lambda)$ | 0.221 | 0.237 | 0.342 | 0.957 | 0.968 | 0.148 | 0.149 |
|  | $\pm$0.049 | $\pm$0.029 | $\pm$0.035 | $\pm$0.012 | $\pm$0.002 | $\pm$0.004 | $\pm$0.004 |
| S&P $(1-p)$ | 0.148 | 0.391 | 0.837 | 0.972 | 0.147 | 0.149 | 0.147 |
|  | $\pm$0.004 | $\pm$0.228 | $\pm$0.170 | $\pm$0.002 | $\pm$0.005 | $\pm$0.004 | $\pm$0.005 |
| S&P $(\sigma)$ | 0.971 | 0.972 | 0.971 | 0.967 | 0.966 | 0.570 | 0.148 |
|  | $\pm$0.004 | $\pm$0.002 | $\pm$0.002 | $\pm$0.009 | $\pm$0.004 | $\pm$0.039 | $\pm$0.008 |
| ReDO ($\tau$) | 0.148 | 0.207 | 0.314 | 0.209 | 0.687 | 0.594 | 0.741 |
|  | $\pm$0.004 | $\pm$0.115 | $\pm$0.330 | $\pm$0.079 | $\pm$0.125 | $\pm$0.089 | $\pm$0.128 |
| ReDO $(r)$ | 0.148 | 0.170 | 0.169 | 0.205 | 0.407 | 0.637 | 0.741 |
|  | $\pm$0.004 | $\pm$0.044 | $\pm$0.045 | $\pm$0.077 | $\pm$0.165 | $\pm$0.155 | $\pm$0.128 |
| CBP $(r)$ | 0.148 | 0.147 | 0.330 | 0.168 | 0.326 | 0.146 | 0.148 |
|  | $\pm$0.004 | $\pm$0.007 | $\pm$0.302 | $\pm$0.026 | $\pm$0.074 | $\pm$0.006 | $\pm$0.004 |
| Layer Norm | 0.958 | 0.958 | 0.958 | 0.958 | 0.958 | 0.958 | 0.958 |
|  | $\pm$0.006 | $\pm$0.006 | $\pm$0.006 | $\pm$0.006 | $\pm$0.006 | $\pm$0.006 | $\pm$0.006 |
| Adam | 0.148 | 0.148 | 0.148 | 0.148 | 0.148 | 0.148 | 0.148 |
|  | $\pm$0.004 | $\pm$0.004 | $\pm$0.004 | $\pm$0.004 | $\pm$0.004 | $\pm$0.004 | $\pm$0.004 |

**Table 14: Performance on Random Label CIFAR with Different Hyperparameters**
|  | Hyperparameter Strength Log Scale |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Algorithm | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| SNR $(\eta)$ | 0.987 | 0.836 | 0.898 | 0.808 | 0.848 | 0.941 | 0.829 |
|  | $\pm$0.002 | $\pm$0.242 | $\pm$0.112 | $\pm$0.124 | $\pm$0.183 | $\pm$0.064 | $\pm$0.173 |
| L2 Init $(\lambda)$ | 0.207 | 0.182 | 0.268 | 0.594 | 0.968 | 0.943 | 0.156 |
|  | $\pm$0.040 | $\pm$0.012 | $\pm$0.068 | $\pm$0.135 | $\pm$0.004 | $\pm$0.007 | $\pm$0.005 |
| L2 Reg. $(\lambda)$ | 0.182 | 0.187 | 0.261 | 0.393 | 0.951 | 0.146 | 0.148 |
|  | $\pm$0.012 | $\pm$0.024 | $\pm$0.097 | $\pm$0.265 | $\pm$0.005 | $\pm$0.004 | $\pm$0.004 |
| S&P $(1-p)$ | 0.155 | 0.158 | 0.165 | 0.341 | 0.973 | 0.145 | 0.148 |
|  | $\pm$0.005 | $\pm$0.007 | $\pm$0.009 | $\pm$0.081 | $\pm$0.003 | $\pm$0.005 | $\pm$0.004 |
| S&P $(\sigma)$ | 0.951 | 0.960 | 0.963 | 0.965 | 0.973 | 0.185 | 0.100 |
|  | $\pm$0.007 | $\pm$0.006 | $\pm$0.004 | $\pm$0.003 | $\pm$0.003 | $\pm$0.068 | $\pm$0.014 |
| ReDO ($\tau$) | 0.184 | 0.942 | 0.984 | 0.975 | 0.962 | 0.841 | 0.840 |
|  | $\pm$0.013 | $\pm$0.054 | $\pm$0.004 | $\pm$0.020 | $\pm$0.038 | $\pm$0.039 | $\pm$0.057 |
| ReDO $(r)$ | 0.207 | 0.199 | 0.160 | 0.377 | 0.890 | 0.984 | 0.980 |
|  | $\pm$0.057 | $\pm$0.067 | $\pm$0.025 | $\pm$0.220 | $\pm$0.121 | $\pm$0.004 | $\pm$0.001 |
| CBP $(r)$ | 0.190 | 0.199 | 0.232 | 0.528 | 0.964 | 0.142 | 0.142 |
|  | $\pm$0.021 | $\pm$0.024 | $\pm$0.058 | $\pm$0.266 | $\pm$0.012 | $\pm$0.006 | $\pm$0.006 |
| Layer Norm | 0.958 | 0.958 | 0.958 | 0.958 | 0.958 | 0.958 | 0.958 |
|  | $\pm$0.008 | $\pm$0.008 | $\pm$0.008 | $\pm$0.008 | $\pm$0.008 | $\pm$0.008 | $\pm$0.008 |
| SGD | 0.184 | 0.184 | 0.184 | 0.184 | 0.184 | 0.184 | 0.184 |
|  | $\pm$0.013 | $\pm$0.013 | $\pm$0.013 | $\pm$0.013 | $\pm$0.013 | $\pm$0.013 | $\pm$0.013 |

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
questions: 1. Could you move other things to the appendix to make room for a conclusion / discussion section? The results section is meant to include the discussion, but I don't think it goes sufficiently deep into the discussion aspect of it. 

2. Can you run an ablation showing what happens if you only L2 the attention weights?
 
3. Can you provide some more insights in how the heuristic works better than the others? Is it that is resets less, therefore is less disruptive. Or the amount of reset correlates better with the firing rate of the unit? Or something else? 

4. There has been a bit of discussion in the papers that you cite (e.g. works from Lyle et al.) on the causes of the loss of plasticity. Can you somehow connect a bit more the heuristic and the causes of plasticity? Right now it feels like the heuristic is just more reliable at predicting when a unit is actually dormant rather then firing rarely. But maybe is not as much connected to the problem it tries to resolve, that of loss of plasticity.
soundness: 3
strengths: The method is simple, easy to implement. And empirically on the problems it has been applied to, it outperforms the existing baseline, which are similar reset methods that use more complex conditions to reset (basically define complex utility functions that are used to make this selection).
summary: The paper proposes a particular heuristic (SNR) to identify neurons that need to be reset in order to recover plasticity. They show that this particular choice of resetting neurons works very well. The work motivates intuitively how SNR compares to more complex utility measures proposed previously, and show results on a bunch of continual learning problems.
weaknesses: I'm somewhat concerned about the significance of the results. I think the method outperforms the baseline, but most more detailed results tend to be on permuted MNIST or permuted Shakespeare. I know previous work relied on similar small scale problems, and it feels unfair to punish this work, while the others got away with it. But at some point I'm worried that we are reading too much into these numbers. 

The authors have run on other tasks (Random Label Cifar, Continual ImageNet) but we can only see an aggregate result on those. And why they highlight specific conditions, they are still borderline as dataset (at least the random label cifar). I think some previous papers also showed results on atari which I think is a more complex setting. And previous works have not scaled things a lot more either. 

A second weakness is in my view, not sufficient analysis. E.g. trying to compare some of those utility functions with the SNR heuristic. How often they disagree. Is the intuition that some of these utility functions don't take into account the firing rate of the unit the answer (it the paper there is a suggestion in this direction). The paper argues that L2init is needed for Shakespeare because of the attention layer. Has this been ablated (e.g. apply L2 init just to attention weights?).  Or is the L2init within the MLP block important. And if so why? 

Putting them together, I feel that the main sales pitch is that it is a simpler utility function and it got better numbers, but there is less on understanding why this is the right thing to do. And I'm worried at such it might not have the impact on the community it should. 

Finally I find the lack of conclusion and discussion a bit strange. I understand that there was a page limit, but I find the solution of not providing a discussion suboptimal. I would urge the authors to find other ways to reduce the paper size.  

Overall I'm happy to increase my score if some of the questions are answered.

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 1
questions: - How do you reset the neurons that you select? Is it the same procedure as in ReDo?
- How does this method do at improving generalization/testing accuracy across distribution shifts?
soundness: 2
strengths: The paper’s new mechanism to select which neurons to reset seems interesting. The theory and intuition behind the method need to be explained more clearly, but the results do show a slight improvement on some settings for some datasets.
summary: This paper proposes a plasticity loss mitigation method called Self Normalized Resets (SNR). It proposes a new method to decide when a neuron should be reset. Specifically, for each neuron, it tracks the mean time between non zero activations of that neuron, models a geometric distribution with that mean, and resets the neuron if the probability that a random variable with this distribution is greater than the neuron’s current time without firing is less than some hyperparameter.

The paper performs some experiments on Permuted MNIST, Random Label MNIST, Random Label CIFAR10, Continual Imagenet, and Permuted Shakespeare, showing a slight improvement or matching previous baselines.
weaknesses: - This paper feels incomplete. The entire theory section in Section 4 is hard to follow and does not feel very motivated. It’s unclear why Section 4.2 is put in the paper. The paper then immediately ends after an equation, with no explanation of how it relates to the rest of the paper, and it is missing a conclusion section.
- The results in Table 1 are conducted over 5 seeds, but they are missing any error bars.
- Table 2 shows results on a task introduced in this paper, Permuted Shakespeare, but several of the baselines for earlier experiments are missing for this dataset.
- The caption for Figure 3 could be made clearer.
- The details on the hyperparameter search could be clearer.

---

confidence: 4
contribution: 4
initial_rating: 8
presentation: 3
questions: One issue with the tasks chosen is that they are entirely disjoint and do not test for robustness to distribution shifts or catastrophic forgetting - e.g. training on task A and B alternately and trying to maintain accuracy on A. Although out of the immediate scope of neural plasticity, I think these factors are important to consider for practical settings. How does SNR interact with catastrophic forgetting, i.e. does it make it better or worse?

Is L2+SNR competitive with SNR alone for the tasks other than Permuted Shakespeare? If so, it would be nice to promote L2+SNR as a "default" method that works for all tasks.
soundness: 4
strengths: __Originality:__ The idea of resetting neurons to avoid loss of plasticity is not particularly novel or surprising (as evidenced by the cited related work), but the proposed method appears novel and most importantly, satisfies multiple desiderata (simple, effective, robust) well beyond previous methods.

__Quality:__ Although on relatively small tasks, the experiments are thorough and convincing. The comparisons are made on a variety of datasets and consideration is made for hyperparameter tuning. A number of known covariates for plasticity loss (L2 complexity of parameters, dead neurons) are plotted to explain the effectiveness of SNR versus other methods.

__Clarity:__ The paper is overall well written and easy to understand (see Weaknesses for a few areas that need improvement).

__Significance:__ The results are only on small datasets, but nevertheless show promise (scaling Permuted Shakespeare gives a positive trend in terms of the method's superiority). The robustness of SNR to hyperparameter choice is very striking. To highlight this, I actually would recommend putting at least 1 figure or table in the main text to summarize one of the tables in Appendix C: for example, plotting hyperparameter strength vs accuracy on one CL task for the compared methods.
summary: This work presents a new method for avoiding plasticity loss in continual learning settings (where neural networks lose their ability to learn new tasks after being trained on other tasks). The proposed method is called Self-Normalized Resets (SNR) and simply involves choosing a threshold time of zero activations, so that any neuron that does not activate (has 0 output) for the threshold number of training iterations has its weights randomly reset during training. SNR is found to outperform other methods in a number of small continual learning image classification tasks, and combines with L2 regularization to outperform on a small natural language task.
weaknesses: This paragraph is confusing: "This reveals an interesting comparison with SNR. The schemes above will re-initialize a neuron after inactivity over a period of time that is uniform across all neurons. In the context of the hypothesis testing setup above, this will result in sub-optimal error rates across neurons. On the other hand, SNR will *reset a neuron after it is inactive for a period that is effectively normalized to the nominal firing rate of that neuron*, while still only specifying a single hyperparameter for the network." - referring to the italicized part of the last sentence, doesn't SNR also reset at a uniform rate of $\bar{T}$? The only difference I can tell is that in the previously described method, neurons are reset all at once every $r$ minibatches, and it is possible for a neuron to be inactive for anywhere between $r$ and $2r-1$ minibatches before reset. If $\bar{T} = r$ then SNR only differs in resetting neurons at exactly $r$ minibatches, and resetting individual neurons at different times during training. Could the authors please clarify this point?

In Permuted Shakespeare, what is the actual task being optimized (e.g. classification, next word prediction, etc.)?

Notes on the presentation:
- a discussion/conclusion section is missing
- some figures have too much noise to be easily readable (e.g. figure 3) and could either have a lower sampling rate for the displayed points, or use a confidence interval to cover the range of variability.
- typo on "hyperparemter(s)." (line 331)
- typo in appendix B "with the [second] element fixed as 1" (line 723)
- typo in appendix B: $w_0$ should be $w_{min}$ in the second part of "We sample $w_0$ uniformly from $[−1, w_0 ) \cup (w_0, 1]$" (line 755)

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 2
questions: - How would SNR's test accuracy (on the held-out dataset) compare to other reset methods? Recent works have been focusing on generalization performance showing that while reset-based methods may result in better training accuracy, they often struggle in terms of generalizability and are outperformed by regularization methods like L2 [1].
- Why do some of the methods in Table 1 results show a significant drop in performance compared to others? Is it dependent on the size/type of hyper-parameter search?

**I am willing to increase the score if the authors address the concerns and questions raised.**

[1] Hojoon Lee, Hyeonseo Cho, Hyunseung Kim, Donghu Kim, Dugki Min, Jaegul Choo, and Clare Lyle. Slow and steady wins the race: Maintaining plasticity with hare and tortoise networks. arXiv preprint arXiv:2406.02596, 2024.
soundness: 2
strengths: - As resetting neurons is a well-known technique in addressing plasticity loss, the main novelty of this paper lies in its exploration of the question of 'how to reset' the neurons. If I understood correctly, by focusing on the *recent* activity of a neuron rather than activity within a uniform period of time, SNR tries to answer the question by selecting individual neurons to reset by being more sensitive to the distribution shifts.
- Their empirical results (especially Table 1) clearly show better average accuracy on a variety of benchmarks. In addition, SNR is better in terms of robustness to its hyper-parameter as compared to other baselines.
summary: The authors introduce Self-Normalized Resets (SNR) which is an adaptive algorithm that resets neuron weights when there is a drop in its firing rate in order to reduce plasticity loss. They also conduct a theoretical investigation of the optimization landscape for learning a single ReLU neuron. Their empirical results show that while existing baselines struggle in terms of sensitivity and detecting inactive neurons, SNR is robust to hyperparameter tuning, and can result in better performance.
weaknesses: - While I understand the adaptive nature of SNR in selecting neurons, wouldn't it also result in over-dependence on the type of distribution shifts across tasks? The vision experiments, in particular, are primarily conducted on benchmarks where a task is uniformly sampled. As a result, the boundaries (or shifts) between consecutive tasks are relatively uniform as well. But what if instead of uniformly, the tasks arrive based on increasing/decreasing (or both) levels of noise and difficulty [1]? A controlled experiment could be conducted to analyze how the nominal firing rate of that neuron changes based on such distribution shifts. 
- The authors described their method SNR as an alternative way to pick neurons to reset them. However, in their experiments, they did not compare SNR with Redo and CBP in Table 2. Also, the standard deviation is crucially missing in Table 1. 
- The paper appears to be incomplete i.e., it ends abruptly after section 4 (with theorem 4.2) without providing any discussion points, limitations, and conclusion. 


There are several grammatical/clarity issues - 
- Line 215 - tacking the histogram
- Lines 57 - 60 can be explained better. 
- Line 269 - Shouldn't it be 1000 classes?
- Line 377 - seems redundant after the previous para

---

confidence: 3
contribution: 2
initial_rating: 3
presentation: 3
questions: Section 2 - Each (x_t, y_t) is drawn from a separate distribution \mu_t? Is there any relationship between the different \mu_t?
Line 134 - This looks like dynamic regret, why is that (pessimistic) objective considered?
Line 136 -  Is this the definition of plasticity? That the averaged dynamic regret grows faster than a constant?
Line 144 - What is the formal definition of a 'dead' or 'inactive' neuron?
Line 153/5 - The definitions of Z and A are unclear. What exactly is s indexing? Which two consecutive activations for A?
Line 155 - 'let let' typo
Line 194 - what guarantees do you have on this approximation? \mu_t seems to be the distribution at a particular time, for which you only have one sample or a batch of samples? Why is considering 'firing times' while training on different, past, tasks/distributions a principled thing to do?

How exactly is A_i^{\mu_t} approximated? I would like more detail than footnote 2.
soundness: 2
strengths: The proposed method appears to outperform the selected baselines on a variety of datasets and exhibits good dependence on its sole hyperparameter. The experiments also appear to be rather thorough. For that reason, I think the proposed method may be practical.

The writing is also strong.
summary: The paper presents a reset-based approach to continual learning, where a network's neurons are reset based on a function of their inactivity. A different threshold function is applied to each neuron. The proposed method is compared to other reset schemes as well as regularization-based approaches. Experiments show promising performance on several datasets (such as MNIST-adjacent ones). Some theory is presented in a setting for learning a single target ReLU.
weaknesses: The experiments appear to be in a rather small setting, which is a slight problem since I believe the paper's main contribution is an experimental one.

Section 4 (theoretical analysis) studies an exceedingly simplified setting. There is no notion of distribution shift or changing tasks (as the expectation is taken with respect to \mu rather than a \mu_t), and the algorithm is full gradient descent, which is not only impractical in real-world settings but impossible without knowledge of the underlying distribution. The second (subtracted) term in the regret also appears to be 0. The restrictions on v in Theorem 4.1 seem rather restrictive and I don't know if they are necessary. It's also unclear if the algorithm suggested in Theorem 4.2 is executable - are the variables with 'min' and 'max' known a priori? 

No conclusion section.

If the authors provide strong answers to my concerns, I would be happy to raise my score.

Meta-review: The paper introduces Self-Normalised Resets (SNR), a novel method to mitigate plasticity loss in continual learning by resetting neurons. The method is simple and requires minimal parameter tuning, yet it outperforms competing methods on standard benchmarks. The authors provide a theoretical argument that L2 regularisation alone is insufficient to prevent plasticity loss, whereas the proposed SNR effectively addresses this issue, offering better performance in maintaining plasticity over time.

Decision: Accept (Poster)