Sequential Learning of Neural Networks for Prequential MDL
Authors: Jorg Bornschein
Yazhe Li
Marcus Hutter
Venue: ICLR 2023 poster (2023)
Keywords: mdl
continual-learning
deep-learning

Abstract: Minimum Description Length (MDL) provides a framework and an objective for principled model evaluation. It formalizes Occam's Razor and can be applied to data from non-stationary sources. In the prequential formulation of MDL, the objective is to minimize the cumulative next-step log-loss when sequentially going through the data and using previous observations for parameter estimation. It thus closely resembles a continual- or online-learning problem. In this study, we evaluate approaches for computing prequential description lengths for image classification datasets with neural networks. Considering the computational cost, we find that online-learning with rehearsal has favorable performance compared to the previously widely used block-wise estimation. We propose forward-calibration to better align the models predictions with the empirical observations and introduce replay-streams, a minibatch incremental training technique to efficiently implement approximate random replay while avoiding large in-memory replay buffers. As a result, we present description lengths for a suite of image classification datasets that improve upon previously reported results by large margins.

Published as a conference paper at ICLR 2023
SEQUENTIAL LEARNING OF NEURAL NETWORKS FOR PREQUENTIAL MDL
Jorg Bornschein bornsschein@deeemind..coom
Yazhe Li
Marcus Hutter
yazhe@deepmind.ccmm com
whutter@deepminne com.
ABSTRACT
Minimum Description Length (MDL) provides framework and an objective for principled model evaluation. formalizes Occam's Razor and can be applied data from non non-stationary sources. In the prequential formulation of MDL., the objective minimize the cumulative next-step log-loss when sequentially going through the data and using previous observations for parameter estimation. It thus closely resembles a continual- or online-learning problem. In this study, evaluate approaches for computing prequential description lengths for image classification datasets with neural networks. Considering the computational cost, we find that online-lcarning with rehearsal has favorable performance compared the previously widely used block-wise estimation. We propose forvard-calibration to better align the models predictions with the empirical observations and introduce replay-streams, a minibatch incremental training technique to efficiently implement approximate random replay while avoiding large in-memory replay buffers. As a result, we present description lengths for suite of image classification datasets that improve upon previously reported results by large margins.
INTRODUCTION
Within the field of deep learning, the paradigm of empirical risk minimization (ERM, Vapnik (1991)
together with model and hyper-parameter selection based on held-out data is the prevailing training and evaluation protocol. This approach has served the field well, supporting seamless scaling to large model and data set sizes. The core assumptions unknown distributions q(x) and 4(ylz) that represent the data setta-generatnng process for the problem under consideration; b) the goal is to obtain a function I = f(x 0*) that minimizes some loss C Ú) in expectation over the data drawn from q: and c) that are given set of (i.i.d.) samples from q use as training and validation data. Its simplicity and well understood theoretical properties make ERM attractive framework when developing learning machines.
ERM are: a) the existence fixed but
However, sometimes we wish to employ deep learning techniques in situations where not all these basic assumptions hold. For example, if do assume fixed data-generating distribution q enter the realm of continual learning, life long learning or online learning. Multiple different terms used for these scenarios because they operate under different constraints, and because there is some ambiguity about what problem exactly a learning machine is supposed to solve. A recent survey on continual- and life-long learning for example describes multiple, sometimes conflicting desiderata considered in the literature: nowwrdd-tansfeed backward- mackward-transfer, avoiding catastrophic forgetting and maintaining plasticity (Hadsell et al. 2020).
Another situation in which the ERM framework is not necessarily the best approach is when mini- mizing the expected loss not the only, or maybe not even the primary objective of the learning machine. For example, recently deep-learning techniques have been used aid structural and causal inference (Vowels et al.) (202)). ). In these cases, we are more interested in model selection or some aspect of the learned parameters 6* than the generalization loss L. Here have little to gain from the generalization bounds provided by the ERM framework and in fact some of its properties can be harmful.
Independent of ERM, compression based approaches to inference and learning such as Minimum Description Length (Rissanen) 1984 Grunwald 2004), Minimum Message Length (Wallace 2005)

---

Published as a conference paper at ICLR 2023
and Solomonoffs theory of inductive inference (Solomonoff 1964] Rathmanner & Hutter 2011
have been extensively studied. In practice, however, they have been primarily applied to small scale problems and with very simple models compared to deep neural networks. These approaches strive to find and train models that can compress the observed data well and rely on the fact that such models have a good chance of generalizing on future data. It is considered a major benefit that these approaches come with a clear objective and have been studied in detail even for concrete sequence of observations; without assuming stationarity or probabilistic generative process all (also called the individual sequence scenario). The individual sequence setting is problematic for ERM because the fundamental step of creating training and validation splits is not clearly defined. In fact, creating such splits implies making an assumption about what is equally distributed across training and validation data. But creating validation splits can be problematic even with (assumed) stationary distributions, and this becomes more pressing as MI. research moves from curated academic benchmark data sets to large user provided or web-scraped data.
In contrast to ERM, compression approaches furthermore include form of Occam's 's Razor, i.e. they prefer simpler models (according to some implicit measure of complexity) as long as the simplicity does not harm the model's predictive performance.
The literature considers multiple, subtly different approaches to defining and computing descrip- tion lengths. Most of them are intractable and known approximations break down for overpa- rameterized model families such as neural networks. One particular approach however, pre- quential MDL (Dawid & Vovk 1999. Poland & Hutter (2005), turns computing the description length L(DIM) = - log ( M) into a specific kind of continual or online learning problem: t= PM PM (m ( ((Dz))), where D= (=((,,, (O is the sequence of inputs 2, and associated prediction targets yo: Pas (y) (r,,)) 6) denotes a model family M and ((D=.) )) an associated parameter estimator given training data Det- In contrast to ERM which considers the performance of a learning algorithm on held-out data after training on a fixed dataset, prequential MDL evaluates learner by its generalization performance on Yr after trained on initially short but progressively longer sequences of observations Dzt- This resembles an online learning problem where a learner is sequentially exposed to new data (zt, 3r). however sequential learner is also allowed to revisit old data Ue for training and when making a prediction at time t>t'. We refer to (Bornschein & Hutter (023) for in-depth discussion of the benefits and challenges when using prequential MDL. with deep learning.
log (D))( >E=
Contributions. Previous work on computing prequential description lengths with neural networks relied on a block-wise (chunk-incrementaa) approximation: at some positions a model is trained from random initialization to convergence data Dec and then their prediction losses on the next intervals are combined (Blier & Ollivier 2018, Bornschein et al.) 2020. Jin et al. [021]] Bornschein et al. 202T; Perez al. 2021//Whitner et al.) 2020). We investigate alternatives that inspired by
continual-lerring (CL) based methods. In particular, chunk-incremental and mini-batch incremental fine-tuning with rehearsal. Throughout this empirical study, consider the computational costs associated with these methods.
We propose two new techniques: forvard-calibration and replay streams. Forward-calibratio improves the results by making the model's predictive uncertainty better match the observed distribu- tion. Replay streams makes replay for mini-batch incremental learning more scalable by providing approximate random rehearsal while avoiding large in in-memory replay-buffers We identify expo- nential moving parameter averages, label-smool smoothin and weiightstandardizattie techniques. As a result we present description lengths for suite of popular image classification datasets that improve upon the previously reported results (Blier & Ollivier 2018 [Brrsschein et al.. 2020) by large margins.
as generally useful
The motivation for studying prequential MDL stems from the desire to apply deep-learning techniques in situations violating the assumptions of ERM. In this work however we concentrate on established iid. datasets: stationarity is most challenging for a sequential learner, which has to uniformly learn from all previously examples, and it allows us to evaluate well known architectures and compare their held-out performance against ERM-based training. which has been the focus of the community for decades. We include additional experimental results on non-stationary data in Appendix C.7.3
2

---

Published as a conference paper at ICLR 2023
After ERM training
Prequential MDL training
label:
SRESS PeTIOy
1022 CNV
1400
20306
3400
2003
E.0%
2010
1red Setaro kthandd
Iosu Schancb)
14p4 Beszaaa (ChaEw
Fox: Nutuaa (charnn
Best performing ERM-trained models on held-out data. There is clear indication which conditioning should be preferred. Right: Log-loss and errors accumulated throughout the sequence. We observe that MDL based model selection provides strong evidence that the model conditioned the R-channel alone should be preferred. In all cases we randomly sampled 50 hyperparameters and use hootstrap-sampling to obtain 95% confidence intervals for the performance of the best performing model. See Figure for detailed regret plots.
Figure Left: Example images. Center:
Next step log-loss
Excess cumulative log-loss
log loss regret
logiloss
RG
400
2000
4000
20000
6000
8000 10000
Position Sequence
Position in Sequence
Left: Next-step neg. log-loss for the best performing models as a function of the position. The models are trained on all the previous examples. We observe that the models conditioned on the R, R and G, or R, and B channels all rapidly improve their predictive performance when trained on more data. Right: The cumulative neg. log-loss (= description length) relative to the best performing model which is conditioned on the R channel only. During the first ~ 2k examples the models conditioned on irrelevant channels accumulate hundreds of excess nats description length.
Figure 2:
An example: model selection using ERM v.s. MDL. To showcase the properties of prequential MDL and its bias towards simpler models, we generate images by randomly drawing 3 MNIST examples and superimposing them as red(R), green(G) and blue(B) channels. The label always associated with the red channel; green and blue are distractors. We train LeNet (LeCun al. 1989) convolutional neural network on 100k examples from this dataset; either within the ERM framework by drawing i.i.d. examples, training to convergence and validating held-out data, or within the MDL framework by treating the data as a sequence, training online with replay buffer (see Section for details) and recording the (cumulative) next-step prediction losses and errors. We compare different models: a model conditioned only on the R channel (MR). on the R and G (MRa), on R. G and B (MRG channels. Figure (middle) shows the validation-set performance of the best performing models after ERM training. Figure I (right) shows description lengths on the same data. It evident that ERM does not give a clear indication which conditioning should be preferred. However, MDL strongly prefers the model conditioned only on the R R-channel. Figure P shows more detailed analysis of the three differently conditioned models in the MDL scenario. We observe that prequential MDL identifies the minimal conditioning because it takes the small- data performance of the models into account. Given sufficient training data the three alternatives perform almost indistinguishable (as seen from their almost parallel regret curves). When we treat the description lengths as evidence for Bayesian model selection to choose between Mg. MRG and M(D] + p(P))((an)) Maan). With the description length log p( (D] MR) about 300 nats smaller than the ones for MRG and MRGB, we have s 1:e -30- -300 odds in favour of Mg. The Appendix C.1 contains additional experiments with more architectures and the experimental details; demonstrating that this is a robust result regardless of architectures and optimization hyperparameters.
MRGB obtain p MM D) p(D) (TP(M)/ppPP)A
ONLINE LEARNING APPROACHES TO PREQUENTIAL MDL ESTIMATION
In this section, we describe practical strategies for computing prequential description lengths with neural networks. Conceptually, computing the cumulative log-loss resembles a continual- or online- learning problem without constraints such as limiting access to previously observed data. In practice, however, some naive approaches such as retraining from scratch to convergence whenever new
3

---

Published as a conference paper at ICLR 2023
Algorithm 1 Mini-batch Incremental Training with Replay Streams
Require: data (It, Mt) )=i: augmentation Aug(,); number of replay streams K; EMA decay a 1: Initialize: parameters 8: EMA parameters 8 softmax temperature calibration 1;
Replay positions {px = k= Spreq = 0
2: for to T do
3: Compute next-step loss: La := - log Dogr(sy ((y Ut m4. 0)
4: Update cumulative loss: Lpreq < preq + f,
5: Update temperature calibration: B B Vg pogp(yy zr, 0)
6:
Update parameters: 0 4- 0 V log p(y, Wt [Tx, O, 1.). with T2- Aug(a:)
7:
Update EMA parameters: 0 + (1 a a
8:
for k = 1 to K do
9:
Get data from stream k: x f Tozi y t you. advance position Pk + Pk + 1 with ā = Aug(z)
10:
Update parameters: 0 4- 0 Vologp(y
11:
Update EMA parameters: 0 + (1 (1-a) a0 a
12: Maintain replay distribution: with probability Preset reset Pk: <- (see Equation !
13:
end for
14:
end for
15:
return Spreq
In practice we perform the algorithm with mini-batches instead of individual examples and use
gradient based optimizers such as Adam Loshhhhlov & Hutter 2019) instead of plain SGD,
example arrives are infeasible due to their high resource usage. In our study, we consider the compute requirements of each approach by counting the number of floating-pon point operations (FLOPs) until the learner reaches the end of the data sequence. We do not limit the learner's ability to access sample previously observed data because storing and reading from large datasets is generally not considered major technical bottleneck. However, in-memory (RAM) based implementations of replay-buffers for continual learning (rehearsal) suffer from limited capacity because data sets for training deep neural networks often exceed RAM sizes. Below we describe replay-streans, a simple approach to approximate random sampling for replay while only utilizing cheap sequential access to data on disk. With this approach, unlimited approximate random rehearsal from data on permanent storage becomes as easy as sampling from large datasets for ERM based optimization.
We compare the following approaches to compute prequential description lengths:
Chunk Incremental/ / From-Scrated (CI/FS): Variants of this approach have been used to compute
the recently reported description lengths for deep-learning models (Blier & Ollivier 2018 Bornschein jet al., [2000; Din et al.) 2021; Bornschein et al. [2021] Perez et al.) 2021). 1). The data-sequence is partitioned into K non-overlapping intervals: typically of increasing size (i.e. choosing exponentially spaced split points {**] 1K with 8& E [2,..., r2). 8% <88++ and 8 =N= For each k. a neural
network randomly initialized and trained to convergence on all the examples before the split point 8k and evaluated on the data between 8y and 8k+1- This corresponds to the block-wise approximation of K --1
the area under the curve: Σiz1 log p( ((xx)((De..) ((D..)) R > وير log (0(D <.y. )), where ((D) denotes parameters after training on data D. To ensure that the model produces calibrated predictions use softmax temperature calibration (Guo et al. 2017):: at each stage
when Dea. is small, split the data Des, into a 90% training and a 10% calibration data. Conceptually, we could perform post-calibration by first training the network to convergence and then, with all parameters frozen, replacing the output layer softmax(1) (h) with the calibrated output layer (oftmax(softlluss33))) where is scalar parameter chosen to minimize the loss on calibration data. In practice, we optimize 33 by gradient descent in parallel with the other model parameters. We alternate computing gradient steps for f, calculated from the training set and using the uncalibrated network (with final layer softmax(h)), with a gradient step on B, calculated from the validation set using the calibrated network (with final layer softmaxx (solppussspp be surprisingly effective at avoiding overfitting symptoms when training large neural networks on small datasets (Guo et al. 2017 Bornschein et al. 2020
This simple calibration procedure has proven to
Chunk Incremental/ / Continual Fine-tuning (CI/CF): Similar to CI/FS, the sequence is split into increasingly larger chunks. But instead of training the model from scratch at each stage, the network
4

---

Published as a conference paper at ICLR 2023
is continuously fine-tuned on the now larger dataset Deeg. We use the same calibration strategy as for CI/FS. We expect to save compute by avoiding training from scratch. However, recent research suggests that, when first trained data D and then trained on data DA J DD, deep-learning models struggle to converge to a solution that generalizes as well as training on D, A U 'D from scratch; even when both A and D are sampled from the same underlying distribution. In Assh & Adams (2020) and adding some noise after training on DA
the authors observe that shrinking the can improve the final generalization performance. We therefore run an ablation study and perform shrink & perturb operation whenever advancing to the next chunk k.
Mini-batch Incremental Replay-Buffer (MI/RB) This approach uses continual online mini- batch gradient descent with additional replay buffer to store previously seen examples. At each time 6, the learner performs a number of learning steps on data in the replay buffer. This could be all or subset of the data Dc depending on the capacity of the replay. We propose forward-calibration to optimize the calibration parameter 3: each new batch of examples is first used for evaluation, then used to perform a single gradient step to optimize B, and finally used for training the parameters and placed into the replay-buffer. Calibration is computationally almost free: the forward- pass for the calibration gradient step can be shared with the evaluation forward-pass paaaadd-pss,,aaa and baeckward-propaggaee for 3 ends right after the softmax layer. Appendix B.1 contains a more detailed description. If the replay buffer is limited by the memory capacity, we either use a FIFO pellacement-stratees or reserioir-sampling (iitter 1985) to maintain a fixed maximum buffer size.
Mini-batch Incremental / Replay-Streams (MI/RS) Implementing large replay buffers can be technically challenging: in-memory (RAM) replay buffers have limited capacity and random access and sampling from permanent storage is often slow. We propose simple yet effective alternative to storing replay data in-memory. We instead assume that the data is stored in its original order on permanent storage and we maintain K replay streams (pointers into the sequence), , each reading the data in-order from the sequence (z1, 8/1 ... (FT.3r)) Vr.) We can think of a replay-stream as a file-ham ailehaanle,, currently at position o E I.. A read operation yields (Iip= yp) and increments the position to f + 1. We denote the position of the kth replay-stream with Ps- Every time the learner steps forward from time / to i-/+1 we also read replay example from each of the K replay-streams and perform gradient steps on them. By stochastically resetting individual streams with probability Preset to position & + I, we can influence the distribution of positions p. If we wish to use uniform replay of previous examples we reset with probability Preset = 1/2. If instead we wish to prioritize recent examples and replay them according to Preplay (a), where a=i-i is the age of the example (z,, y:) relative to the current position of the learner t, we use
Σ Proplay (a)
Preser (1)
(1)
Ex'=o Proplay (a')
Note that Preplay can be an unnormalized distribution and that by setting Pioplay x 1 we recover Preset 1/2 for uniform replay. See Algorithm 1 for details.
3 EXPERIMENTS
We empirically evaluate the approaches from Section 2 on a suite of models and image classification data sets. We use MNIST (LeCun et al. 2010). EMNIST, CIFAR-1O, CIFAR-100 (Krizhevsky) 2009) and ImageNet (Russakovsky et al. 2015) and randomly shuffle each into fixed sequence of examples. With MDL, we do not require validation or test set and could merge it with the training data. But because the data is known to be i.idd. and we compare results with established ERM-based training, we instead maintain the standard test sets as held-out data. It must be emphasized that the primary objective throughout this study to minimize the description length. All hyperparameters are tuned towards that goal. When we report test set performance it should be considered a sanity check. For more detailed analyses we will plot the "regret" a method M, accumulates relative to some comparator method M.: (t(() := log P(Dcr MM)) + log (D MM).. We evaluate the following architectures: MLPs, VGG (Simonyan & Zisserman 2015). ResNets (He et al. 2016). WideResNets
(Zagoruyko & Komodakis 2016) and the transformer- based DeiT (Touvron et al. 2021) architecture. We refer to a variant of the VGG architecture with stight-standardized convolutions (Qiao et al. 2019) and with batch normalization (loffe & Szegedy 2015) as VGG++.
5

---

Published as a conference paper at ICLR 2023
EMNIST with LeNet
CIFAR-10 with VGG++
80.0k
43.0k
75.04
Descr. Length [nets] [nntgh
70.0k
65.0k
20.0k
25.0k
50.0k
20.0k
1012
10
10
10ts
10
Cumulative
Cumulative FLOPs
CIFAR- 100 with VGG++
ImageNet with ResNet50
120.0k
3.004
Length [nagth(natss]
Length [nets]
2.80M
100.0k
2.40M
90.0k
10th
10
10
10
10
Cumulative I'Opss
Cumulaaivve l'OPss
MI/RS
CICCF (8 chunks)
CI/CF (16 chunks)
CI/FS (8 resets)
CI/FS (16 resets)
Shortest description lengths function of compute resources consumed for different methods. For each method (in different colors) we run 250 (100 for ImageNet) independent exper- iments with randomly sampled hy hyperparameters. Each dot represents such an experiment and the solid lines show the Pareto-front of the best archived performance for different compute budgets. With the exception of CIFAR- 100 the large-FLOPs regime, the MI/RS results in the shortest description lengths.
Figure 3:
incremental appoach
For the bulk of our experiments, we use the Adam W (Loshchilov & Hutter 2019) as optimizer; a series of control experiments however suggest that the quantitative results generalize to optimizers such as RMSProp and simple mini-batch SGD with momentum. We identified the following techniques that consistently improve the results and use them throughout this paper if not mentioned otherwise:
Exponentially moving average (EMA) Similar to Polyak averaging (Polyak & Juditsky 1992). EMA maintains a moving average of the model parameters 0 and is used for next-step evaluations as well as when tuning the softmax temperature B.
Label smoothing (Szegedy et al. 2015) A reliable regularizer, label smoothing often helps for the continual fine-tuning methods such as MI/RB, MI/RS and CI/CF.
Weight standardization For the VGG architecture, weight standardized convolutions lead to signifi- cant improvements bigger than for conventional ERM-based training. For other architectures such as ResNets, the results are not conclusive.
3.1 COMPARISON OF ONLINE LEARNING APPROACUES.
To compare the effectiveness of the different approaches listed in Section 2 we run a broad random hyperparameter sweep for EMNIST with LeNet, CIFAR-10 and CIFAR- 100 with VGG++ and ImageNet with ResNet50. The hyperparameter intervals depend on the data and are detailed in Appendix B We sample learning rate, EMA step size, batch size, weight decay; but erucially also number of epochs (or, correspondingly, number of replay streams for MI/RS) and an overall scaling of the model width (number of channels). We thus cover a large range of computational budgets, spanning about 2 orders of magnitude. When the capacity of the replay-buffer matches the total length of the sequence. MI/RB and MI/RS are equivalent. In these cases we omit MI/RB and instead use MI/RS to represent online-learning with unlimited rehearsal. A study of replay buffer v.s. replay streams can be found in Section 3.1 We show the overall Pareto front for these experiments in Figure 3 Mini-batch incremental learning obtains the lowest description lengths for wide range

---

Published as a conference paper at ICLR 2023
MI/RS
ERM
Cumulative
Test
Test
Data
Model
Loss
Error
Loss
Erron(S)
OL.
Loss
Emor(())
FL.PPs
MNIST
LeNet
4,4k
1362
0.03
1.0
1.4e13
0.03
0.8
1.5e13
MNIST
MnistNet
2.1k
643
0.02
0.5
4.5c14
0.02
0.5
3.2e14
CIFAR-10
VGG++
22.1k
6.6k
0.24
5.8
5.9e15
0.21
6.9
8.0e15
CIFAR-10
WRN-28-10
22.9k
7.5k
0.23
74
3.7e16
0.20
6.7
5.4e16
CIFAR-100
VGG++
93.7k
23.1k
1.14
32.0
4.2c15
28.1
2.6e15
CIFAR-100
WRN-28-10
87.0k
22.3k
1.10
30,3
2.5e16
1,08
28.3
4,3e16
Net
VGG++
ImageNet
ResNet-34
2.35M
507k
1.30
30.9
1.fe188
1.25
29.9
7.0e17
ImageNet
R5
2.21M
496k
1.29
29.1
8.5e17
1.15
28.7
19:18
ImtgeNet
ResNet-50f
ImageNet
ResNet-101
1.97M
447k
1.20
28.2
3.1e18
1.10
26.6
4,6e18
ImageNet
DeiT-S
2.73M
588k
1.40
31.7
1.2c18
1.22
28.1
4.8c18
Prior Works:
(Bier & Ollivier 2018)
MaistNet 2: VGG++
2.8k
0.5
CIFAR Tullher Olliver 2018
31.4k
6.7
NotgeNot Bomschem et 2020
ResNer-50 3.32M
Table 1:
Left half of the table: Suite of results when applying MI/RS for description length estimation. Cummulative loss in nats; cumulative error counts the number of prediction errors after reaching the end of the sequence. The test set metrics report the performance of the model selected by lowest description length. Right half: Results when using the same architecture and hyperparameter-swegg for conventional ERM training. Manually tuned hyper parameters.
of computational budgets. Only for very large compute budgets on CIFAR-100 we observe that the block-wise approximation with training from scratch (CI/FS) has better results.
MDL for Deep Neural Networks. We apply MI/RS to wider range of architectures. For most experiments we again use random hyperparameter sweeps, this time however without scaling the size of the models and with an increased lower bound for the number replay streams (see Appendix B). We present results for the best run in each sweep and contrast them with previously reported description lengths from the literature Table [ We also show the test set performance of these models after they reached the end of training data. The rightmost columns show the test performance when performing the same hyperparameter sweep for conventional ERM training on the full data set. Note that these runs do not use any kind of learning rate annealing, which is otherwise often employed to improve results.
Based on these experiments plot regret comparison for different architectures trained on ImageNet in Figure (left). We observe that the additional depth and capacity of a ResNet101 is beneficial from the very beginning of the sequeee Figure 4 (right) shows the effect of scaling the number of channels of VGG++ architecture on CIFAR- 100 and it is evident that decreasing the model width has negative effects throughout the sequence and not just when the data gets larger.
ImageNet/ Architecture comparison
VSG++ on CIFAR-150/ 10/ Scaling mariel wirth
Length (ears)(
VBGG++
Ros Netthet-14
Desc. Length Regret [nats]]
15000
Scala
Scale 0.3
Ras
Scale 1.0
400000
10000
Scate
200000
5000
0.0
0.2
0.4
0.6
0.8
1.0
3.2
10000
20000
20000
40000
50000
Position Sequence
1wB
Position
Figure
Left: Comparing architectures on ImageNet. Right: Scaling the size of VGG++.
Replay Buffer and Replay Streams are equivalent for short data sequences, they differ when the length of sequence exceeds the capacity of the replay buffer. In this section, we study the effects of limiting the replay buffer size. Figure Ssows shows that reducing the capacity has significant negative effect on the results. In addition, the strategy of which samples to keep in the buffer plays an important role. Using reservoir sampling instead of a FIFO replacement policy leads to further severely degraded results. This is maybe not surprising because with reservoir-samie sampling insertion to the buffer stochastic; a fraction of the examples are thus never replayed at all. Appendix C.5 contains ablations for the number of replay-streams CIFAR-100 and ImageNet.
7

---

Published as a conference paper at ICLR 2023
Ablations. We provide ablations for using forward-calibrate label smoothing and weight stan- dardization in Table 2 It evident that each of these techniques helps obtaining better description lengths for the datasets and architectures under consideration. Regret plots for these ablations can be found in Appendix C
Data
Model
None
+FC
+LS
+WS 26.4k (-5.9k)
+ALL 23.3K (-9.0K)
CIFAR-10
VGG++
32.4k
31.8k (-0.6k)
32.1k (-0.3k)
CIFAR-100
VGG+
103.4k
100.7k (-2.7k)
102.8k (-0.6k)
93.1k (-10.2k)
89.1k (-14.2)
ImageNet
ResNet50
2.33M
2.27M (-60.0k)
2.28M (-50k)
2.21M (- (-120k)
Table 2: Description lengths (in nats) with various techniques added to the baseline model: forward- calibration (FC), label smoothing (LS) and weight standardization (WS).
Plasticity and the Warm-starting problem We take closer look at the Harge-FLOP regime for CIFAR-100 where CI/FS obtained better results than MI/RS. Figure 6 (left) shows the regret comparison between the best runs for each training method. The split positions 8μ; are clearly visible as kinks in the graph for CI/FS and CI/CF. For CI/CF the plot shows that right after fine-tuning, the predictive performance is approximately equal MI/RS. For CI/FS we see that the regret relative to MI/RS decreases: it has better predictive performance. This effect persists even after running extensive additional hyperparameter sweeps. We conjecture that this is a signature of the warm- starting problem described in (Ash & Adams 2020). Figure 6 (right) shows the Pareto front for the final test set accuracy of the best models (selected by their description length) over FLOPs. We observe a large gap between fine-tuning based methods and CI/FS; which is consistent with this hypothesis. Note that the last split-point 8 = implies that these models are effectively trained like in conventional ERM paradigm. Appendix C shows test set pareto fronts for range of datasets. Close inspection of various regret plots sometimes reveals the same signatures, suggesting that the effect is ubiquitous, but often much less pronounced. It is plausible that this also contributes to the gap in final test set performance in Table
4 DISCUSSION & RELATED WORK
Compression based approaches to inference and learning, such as Solomonoff induction (Solomonoti 1964). Minimum Message Length (Wallace 2005) and Minimum Description Length (Rissanen
1984 Grunwald 2004), have been extensively studied. The Bayesian and variational Bayesian approaches to estimating code lengths have been popular and, at least outside the field of deep learning, also been very successful. This line of work includes methods such as AIC and BIC, as well as more sophisticated approximations to the posterior distribution over model parameters for many kinds of models, including neural networks (Hinton & Van Camp 1993 MacKay (0003). The description length depends crucially on the quality of these posterior approximations. Unfortunately, estimating the parameter posterior for modern neural networks is notoriously hard and an area of active research (Izmailov et al.) 2021). Blier & Ollivier (2018) demonstrated that much shorter code lengths be achieved by using the prequential approach with standard neural network architectures and optimizers. The prequential perspective with the block-wise approximation technique have been
VGG+ on CIFAR-100 100 Replay Buffer Capacity
ImageNet/ / Replay
15000
MI 5K: RIFO buffer
Descrr Length Regree [nars]
199K
MI 110K RIFO butfer
Lengih Regret
10000
50k FIFO
FIFO
300000
100k Reservoir Buffer
FFO Bufeer
250k Reservoir Buffer
5000
200000
500k Reservoir Buffer
100000
10000
20000
3000C
40000
50000
0.0
0.2
0.4
0.6
0.8
1.0
2.2
Pozition
Sequence
Position Sequernce
Figure 5: The effect of reducing the rufley- capacity. Left: Regret for different replay buffer sizes for CIFAR-100. Right: Comparing buffer capacity and FIFO vs. reservoir sampling based replacement strategies for ImageNet with ResNet50.
8

---

Published as a conference paper at ICLR 2023
VGG++ + CIFAR-100/ / Training strategles and chunk-size
VGG++ on CIFAR-100 / Held-out performence vs. FLOPs
Deser, Length Regret (naiss
MURS
0.36
10.0k
CXCF chunks!
CVCT churies
9.34
CVCF (16 chumbs)
CXCF (8 chunbs)
1325 18 resets)
0.32
CVTS resels)
5.0K
FMF (16 ressis)
0.30
CWFS (16 resets)
0.28
0.0k
0.26
-5.0k
10000
30000
40000
50000
10
10t4
10
Position in Sequence
Curuuaative FLOPs
Figure 6: Left: Comparing the regret for CI/FS and CI/CF relative to MI/RS for CIFAR-100. Right:
Pareto-front for the test set performance after reaching the end of the sequence
successively used in the context of image-classfficttinn (Borschein et al. 2020), natural language
processing (Voita & Titov| 2020; Jin et al. 2021 Perez et al. 2021) and causal structure discovery (Bornschein et al. 2021).
With our work, we aim to simplify and improve prequential code length estimation for neural networks with insights from the field of continuous learning (CL). For CL, finc-tuning with rehearsal is considered a strong baseline and large number of methods have been proposed to maintain its benefits while minimizing the size of the replay buffer (Mnih et al. 2013; Delange et al., 202T). We instead propose a method that makes it practical and relatively cheap to work with full rehearsal. Caccia al. (2022) investigate very similar scenario ours; largely phrased around how long learner should wait and accumulate data when it is compute constraint; most experiments however consider the case without full rehearsal. He and Lin (He & Lin 2020) discuss the close relationship between prequential coding and CL, however focus on compressive replay instead of accessing previous data. In general, the literature on CL methods and evaluation metrics is too broad to be adequately discussed here (Hadsell et al.) 2020). However, we would not be surprised if some existing CL methods have the potential to vastly improve prequential MDL, computation. In this sense, we see our work as a step of bringing CL. and prequential MDL related works closer together.
Besides of taking inspiration from CL to improve description lengths, we believe that the MDL perspective can help guide future CL research: Much of the CL literature is rooted in an ERM-based perspective and thus considers distinct training, validation and test sets at different stages during learning. This has potentially played role in the proliferation of many different evaluation metrics and training protocols used in CL research (Hadsell et al., 2020). This heterogeneity of the evaluation metrics makes it challenging to compare results. trrasfrr is commonly used evaluation metric and it is closely related to prequential evaluation. However, it is often computed on separate held-out sets after training and does not take sample-efficiency into account as prequential MDL does. Recent work has embraced forward-validation in terms of average prediction-error on future training data as evaluation metric, thus bringing it closer to a prequential MDL based evaluation but without discussing the connection (Cai et al. 2021 [in et al.) (02T). MDL has been conceived and analyzed as a theoretically well motivated objective when dealing with non-stationary data; without reference to the practical difficulties of actually performing parameter estimates. It is a challenging objective even for learners without constraints on compute and (replay-) memory.
5 CONCLUSIONS & LIMITATIONS
In this paper, we compare different approaches computing prequential description lengths while considering their computational cost. We find that continual learning inspired mini-batch incremental training with full rehearsal is the preferred method over a wide range of computational budgets. We introduce two techniques that either improve results, or make it practical to apply full rehearsal even for very large data. As a result we report description lengths for a range of standard data sets that improve significantly over previously reported figures. Some of our results show that the warmstarting- effect can have a negative effect on the performance of continual fine-tuning. We also generally observe gap in the final held-out performance after training models within the prequental framework vs. training models with the ERM-based approach. We are not aware of any technique to reliably mitigate the impact. It would be important topic to tackle for future works. Furthermore,
9

---

Published as a conference paper at ICLR 2023
learning rate schedules such as cosine decay popular and effective techniques for achieving better performance in ERM-based training. It is not obvious how to best translate them to the prequential learning scenario the learner constantly receives new data.
REFERENCES
Jordan Ash and Ryan P Adams. On warm-starting neural network training. Advances in Neural Information Processing Systems, 13:3884-3899 2020.
Léonard Blier and Yann Ollivier. The description length of deep learning models. February 2018.
Jörg Bornschein and Mareus Hutter. Prequential MDL for deep learning. arXiv preprint, 2023.
Jörg Bornschein, Francesco Visin, and Simon Osindero. Small data, big decisions: Model selection in the small-data regime. International Conference on Machine Learning, pp. 1035-1044. PMLR, 2020.
Jörg Bornschein, Silvia Chiappa, Alan Malek, and Rosemary Nan Ke. Prequential MDL for causal structure learning with neural networks. In NeurlPS Workshop: Causal Inference & Machine Learning, 2021.
Caccia, Xu, Ott, MA Ranzato, and Denoyer. On anytime learning macroscale. In Conference on Lifelong Learning Agents (CoLLAs), 2022. URL https://arxiv..rrrt 2106. 09563
Zhipeng Cai, Ozan Sener, and Vladlen Koltun. Online continual learning with natural distribution shifts: An empirical study with visual data. August 2021.
Bilge Celik, Prabhant Singh, and Joaquin Vanschoren. Online automl: An adaptive automl framework for online learning. arXiv preprint arXiv:2201.0973 2022.
A. Philip Dawid and Vladimir G. Vovk. Prequential probability: principles and properties. Bernoulli. 5(1):125-162, 1999.
Matthias Delange, Rahaf Aljundi, Mare Masana, Sarah Parisot, Xu Jia, Ales Leonardis, Greg Slabaugh, and Tinne Tuytelaars. A continual learning survey: Defying forgetting in classification tasks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021.
Marco F Duarte and Yu Hen Hu. Vehicle classification in distributed sensor networks. Journal of Parallel and Distributed Computing, 64(7):826-88) 838, 2004.
Peter Grunwald. tutorial introduction to the minimum description length principle, 2004. URL org/abs////oooooooooo../aaoaaaaa
/ttts:://axxi //w.xvv..ivv.v//a org/ abs ma 0406077
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q. Weinberger. On calibration of modern neural networks. In International Conference Machine Learning, pp. 1321-1330, 2017.
Raia Hadsell, Dushyant Rao, Andrei A Rusu, and Razvan Pascanu. Embracing change: Continual learning in deep neural networks. Trends Cogn. Sci., 24(12))1028-11 1040,, December 2020.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Xu He and Min Lin. Continual learning from the perspective of compression. 4th Lifelong Machine Learning Workshop at ICML 2020. arXiv, 2020. doi: 1048550/ARXIV22006.55000 URL BtRlhhtts://axxii
15078
Geoffrey E. Hinton and Drew Van Camp. Keeping the neural networks simple by minimizing the description length the weights. In Conference on Computational Learning Theory, pp. 5-13, 1993.
10

---

Published as a conference paper at ICLR 2023
Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International conference on machine learning, pp. 448 456.. PMLR. 2015.
Pavel Izmailov, Sharad Vikram, Matthew D Hoffman, and Andrew Gordon Gordon Wilson. What are bayesian neural network posteriors really like? In International Conference Machine Learning, pp. 1629-4640. PMLR, 2021.
Zhijing Jin, Julius Kuegelgen, Jingwei Ni, Tejas Vaidhya, Ayush Kaushal, Mrinmaya Sachan, and Bernhard Schoelkopf. Causal direction data collection matters: Implications of causal and anticausal learning for NL.P. In Proceedings of the 202/ Conference on Empirical Methods in Natural Language Processing, EMNLP 2021. Association for Computational Linguistics, 2021.
URL https: BttLhhts:///axiiia /ttp:///axxiiv.o wtt.ab//g/aaaooeee http://////aaa....//////00000000 03618
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009.
Y. LeCun, B. Boser, S. Denker, D. Henderson, R. E. Howard, W. Hubbard, and L. D. Jackel. Backpropagation Applied to Handwritten Zip Code Recognition. Neural Computation, 1(4): 541-551, 12 1989, ISSN 0899-7667. doi: 10.1 10.11e2/n 1989.1.4.541. URL https://doi
1989.99.... 1.....1.555555. 541
Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. ATT Labs [Online]. Available: http://yann.lecunncco www..l/ccw..com/eebb/nnssss 2, 2010.
Zhiqiu Lin, Jia Shi, Deepak Pathak, and Deva Ramanan. The clear benchmark: Continual learning on real-world imagery. In Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2021.
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In International Confer- ence on Learning Representations, 2019. URL httpps://ppeeeeeeee...... net/ www.eeet..foimeeeooooo
Bkg6RicqY7
David C. MacKay. Information Theory, Inference and Learning Algorithms. Cambridge University
Press, 2003.
Volodymyr Mnih, Koray Kavukeuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning, arXiv preprint 10X.v:1312.5602, 2013.
Ethan Perez, Douwe Kiela, and Kyunghyun Cho. Rissanen data analysis: Examining dataset characteristics via description length. In International Conference on Machine Learning, pp- 8500 8513. PMLR, 2021.
Jan Poland and Marcus Hutter. Asymptotics discrete MDL for online prediction. IEEE Transactions Information Theory, 51(11):3780-379) 2005.
Boris Polyak and Anatoli Juditsky. Acceleration of stochastic approximation by averaging. SIAM Journal on Control and Optimization, 30:838-855 07 1992. doi: 10.
Siyuan Qiao, Huiyu Wang, Chenxi Liu, Wei Shen, and Alan Yuille. Weight standardization. arXiv preprint 19X.v:1903.10522 2019.
Samuel Rathmanner and Mareus Hutter. A philosophical treatise of universal induction. Entropy, 13 (6):10761136, 2011. ISSN 1099-4300. doi: 10.3390/c13061000
J Rissanen. Universal coding, information, prediction, and estimation. IEEE Trans. Inf. Theory, 30 (4):629-636 July 1984.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei. ImageNet Large Scale Visual Recognition Challenge. International Journal of Computer Vision (IJCV), 115 2015. doi: 10.1007/s 1263-015-0816-7

---

Published as a conference paper at ICLR 2023
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In International Conference on Learning Representations, 2015.
Ray J Solomonoff. A formal theory of inductive inference, part i. Information and control, 7(1):1-22,
1964.
Christian Szegedy, Vincent Vanhoucke, Sergey loffe, Jonathon Shlens, and Zbigniew Wojna. Re- thinking the inception architecture for computer vision. CoRR, abs/1512.00567,, 2015. URL
http://arxiv.co wttp://w.ww..aa//1/.//2
Hugo Touvron, Matthieu Cord, Matthijs Douze, Francisco Massa, Alexandre Sablayrolles, and Herve
Jegou. Training data-efficient image transformers & distillation through attention. In International Conference on Machine Learning, volume 139, pp- 10347-10357, July 2021.
V Vapnik. Principles of risk minimization for learning theory. In Proceedings of the 4th International Conference on Neural Information Processing Systems, NIPS'91, pp. 831-838, San Francisco, CA. USA, December 1991. Morgan Kaufmann Publishers Inc.
Jeffrey S. Vitter. Random sampling with reservoir. ACM Trans. Math. Softw, 11(1):37-57, mar 1985. ISSN 0098-3500. doi: 10.1145/3147.31555 BRI.https: //doi /ttp://...or1111111////3115 3165
Elena Voita and Ivan Titov. information- probing with minimum description length. CoRR, abs/2003. 1100003.12299 1298, 2020.
12298
Matthew J Vowels, Necati Cihan Camgoz, and Richard Bowden. D'ya like dags? survey on structure learning and causal discovery. arXiv preprint 1xXiv:2103.025880 2021.
CS Wallace, Statistical and Inductive Inference by Minimum Message Length. Springer Science & Business Media, December 2005.
William FF Whitney, Min Jae Song, David Brandfonbrener, Jaan Altosaar, and Kyunghyun Cho. Evaluating representations by the complexity of learning low-loss predictors. arXiv preprint arXiv:2009.07368,, 2020.
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. In Edwin R. Hancock Richard C. Wilson and William A. P. Smith (eds.). Proceedings of the British Machine Vision Conference (BMVC), pp. 87.1 12. BMVA Press, September 2016. ISBN 1-901725-59.4 doi: 10.5244/C. 30.87. URL https::t://ecc doi org wt...././...............
524 C0..8
12

---

Published as a conference paper at ICLR 2023
SEQUENTIAL LEARNING OF NEURAL NETWORKS FOR PREQUENTIAL MDL SUPPLEMENTARY MATERIAL
A PRELIMINARIES
Throughout the main paper and the appendix we use the following notation:
Symbol
Description
Example
21..T
Ordered sequence of observations; potentially multivariate
Images
81...T
Ordered sequence of prediction targets
Classification labels
Observed data for training
D= (I1...T,
DEt
Observed data up to Parametric model M Parametric model M with softmax temperature |
D (11...-11. (1....-)
pM (Y(X,0)
Neural network with softmax
pM OM((XX0,,8)
See (Guo et al. 2017)
((D)
Estimated model parameters after training 'D
Result of SGD training
@MLLE (D)
Maximum likelihood solution arg max II, Par (ye 0)
(p= lk=l
Position of K independent data readers for replay-stream training
See Algorithm
B EXPERIMENTAL DETAILS
B.1 FORWARD CALIBRATION
We train the neural network with standard cross-entropy loss and the categorical prediction-heat = soft where is a vector of logits generated by the neural network. When using the model for evaluation on next-step data or test set examples, replace with calibrated prediction head softmax (softauus (3) h), where / is scalar temperature parameter (Guo et al. (2017). We use optimize the calibration parameter each new batch of examples from the training sequence is used first for evaluation, then used to perform single gradient step to optimize 3, and finally used for a training to optimizer 0 and placed into the replay-buffed At the beginning of training we initialize 3 to 3o log( log(exp(1) 1) R 0.5416, such that softplus( (3o) 1. We use the same optimizer for the model parameters 8, however scale the learning rate by factor of VK, where K is the number of training steps per evaluation step forward (i.e., number replay-streams plus one). Calibration is computationally almost free: the forward-pass for the calibration gradient step can be shared with the evaluation forward-pass. and backward-propagattin for / ends shortly after the softmax layer.
bowwadd-calbrattie
B.2 MNIST, EMNIST AND RGB-MNIST HYPERPARAMETER,
We run experiments with various model architectures: a) MLP with 1, 2 or hidden layers, 512 units each, with dropout, and ReLU -ineainaasssss, b) LeNet (LeCun et al. 1989) and c) the VGG inspired architecture used by (Blier & Ollivier 2018), which we call MnistNet here.
We use the same hyperparameter and sampling intervals for all three model architectures. For the pareto front experiment we extend the number of replay-streams range 10. 100; otherwise use the same intervals.
Parameter
Distribution
Values Interval
Number of replay-streams
log-uniform
25 ... 100
Learning rate
log-uniform
le-4 3e-3
AdamWa
log-uniform
le-4
EMA step size (Polyak averaging)
log-uniform
le-3 le-1
Weight decay
log-uniform
le-4
Batch size
fixed
32
Label smoothing
fixed
0.001
13

---

Published as a conference paper at ICLR 2023
B.3 CIFAR-10 AND CIFAR-100 WITH VGG++, AND WIDERESNET HYPERPARAMETERS
We use the same hyperparmater sampling intervals for all model architectures. Following Zagoruyko & Komodakis we use only minimal augmentations during training: Images will be horizontally flipped with a probability of 0.5. For the pareto-front plots we extend the number of epochs (= number of replay-streams) range to 10. 100 and
Parameter
Distribution
Values Interval
Number of replay-streams
log-uniform
25 100
Learning rate
log-uniform
le-4 3e-3
AdamWe
log-uniform
le-4
EMA step size (Polyak averaging)
log-uniform
le-3 ... le-1
Weight decay
log-uniform
le-4 le-1
Batch size
uniform
[32. 64, 128)
Label smoothing
fixed
0.01
B.4 IMAGENET WITH VGG++ AND RESNETS HYPERPARAMETERS
We use randaugment for data augmentation and the same hyperparameter intervals for all experi- ments. For Pareto front experiments we additionally scale the architecture size (number of channels throughout) from 1/4x to 4x and extend the number of replay-streams interval to 10 100.
Parameter
Distribution
Values Interval
Number of replay-streams
log-uniform
25 100
Learning rate
log-uniform
le-4 ...4...3662 3e-3
AdamWe
log-uniform
le-4
EMA step size (Polyak averaging)
log-uniform
le-3 le-2
Weight decay
log-uniform
le-4 1.
Batch size
fixed
512
Label smoothing
fixed
0.01
We report additional baseline metries for the standard ResNet-50 model on ImageNet, obtained by running the same byperparameterrssoopp:
Replay Streams: pMDL score 2.21M
Replay Buffer (500k capacity): pMDL score 2.26M nats
fhunkwiis-from-scratee (16 split points, <1e19 FLOPs): pMDL score 2.52M nats,
Note that for chunkwise-frowt www.--frrom-eell- we use the techniques from Bornschein et (020). who report 3.32M nats. Using better (wider) hyperparameter search and using more pointss we thus found significantly better result for their method.
Using 4x wider architecture:
Replay Streams: PMDL score 2.18M nats
Replay Buffer (500k capacity): pMDL score 2.22M nats
Chunkwise-from-sratch (16 split points, 1e19 FLOPs): pMDL score 2. 28M nats,
B.5 CLOC WITH RESNETS HYPERPARAMETERS
We randaugment for data augmentation and the same hyperparameter intervals for all experiments.
14

---

Published as a conference paper at ICLR 2023
Parameter
Distribution
Values Interval
Number of replay-streams
log-uniform
10...25
Learning rate
log-uniform
le-4 ... 3e-3
EMA step size (Polyak averaging)
log-uniform
le-3 le-2
Batch size
fixed
128
Label smoothing
fixed
0.1
C ADDITIONAL EMPIRICAL RESULTS
C.I RGB-MNIST FEATURE SELECTION
To illustrate that the model-sclection property demonstrated in section is robust property of (prequential) MDL, we here present a suite results on different model architectures: 1) am MLP with 2 hidden layers, 512 units each; 2) the LeNet architecture from (LeCun et al. 1989): and 3) the much higher capacity and better tuned convnet from (Blier & Ollivier 2018).
In all cases for the best performing model each sweep relative to the model conditioned only on the channel. We PMDL. reliably and with confidence determines that the model conditioned R only is the most appropriate one for this data; and we see that the small-data performance at the beginning of the sequence is crucial the relative generalization performance becomes more similar as the length of the sequence increases:
the same hyperprameter sweep detailed in Appendix B We show the regret plot
MLP Regret Plot
Next step log-loss
cumulaaive log-loss
2000
channels
2500
RG
RGB
500
2000
6000
10000
2000
4000
6008
10000
Positton
Position Sequence
LeNet Regret Plot
Next step log-loss
Excess cumulative log-ioss
log fo--Koss regret
600
400
4000
6000
10000
2000
4000
6000
8000
10000
Position in Sequence
Position Sequence
MnistNet Regret Plot
Next stop log-loss
Excess cumulative log-loss
channels
log- -oss regret
300
R
200
RG
100
6000
4000
Position in Sequence
Position Sequence
15

---

Published as a conference paper at ICLR 2023
C.2 PARETO FRONTS
Left:
Description lengths as function of compute resources consumed for a selection of datasets and models. Right: Test set performance after reaching the end of the training data. We generally observe a gap between models that train from scratch (CI/FS) and continual finetuning methods. The gap is very pronounced for CIFAR-100. We do not observe a systematic gap between MI/RS and CI/CF/
MNIST with LeNet
Description length vs. FLOPs
Test Emror vs. FLOPs
8000
0.014
7000
0.012
6000
0.010
5000
Descr
0.008
4000
0.006
3000
10
10
10
1012
1014
1013
Cumulative FLOPs
Cumulaative FLOPs
EMNIST with LeNet
Description length vs. FLOPs
Test vs. FLOPs
80000
Length [nats]
70000
Text Fimr
0.16
60000
0.14
50000
0.12
10a4
10 Cumulative FLOPs
Cumulative PLOPs
CIFAR-10 with VGG++
Description length vs. FLOPs
Test Error vs. FLOPs
40.00 40.0k
0.14
Length
35.0k
0.12
30.0k
0.10
25.0k
0.00
0.06
20.0k
1034
10
1614
1034
104
1014
Cumulative FLOPs
Cumulative FLOPs
CIFAR-100 with VGG++
Description length vs. FLOPS
Test Error vs. FLOPS
Descr, Length [nats]
120.0k
0.35
110.0k
lest Error
100.0k
0.30
90.0k
0.25
80.0k
1035
1016
10
10ts
1016
1017
Cumulaatve FLOPs
Cumulative FLOPs
Imt with ResNet-50
Description Length FLOPs
FLOPs
3.25M
0.100
Longth [nats]
3.00M
0.375
2.75M
0.350
0.325
2.50M
2.25
0.275
2.00M
10
10a
Cumulative FLOPs
Cumulative FLOPs
MI/S
CI/CF (8 chunks)
CI/CF (16 chunks)
CI/FS (B resets)
CIFS (16 resets)
16

---

Published as a conference paper at ICLR 2023
C.3
MODEL DEPTH ABLATION
MNIST/ Model
MLPs on EMNIST / Model Depth
3.0%
Hiddin Layers
2.5k
Hidden Layers
Descr, Rogret
Descr. Regret
2.0%
Layers
Logistiic Regi maaion
2.0k
Hidden Layer Hidden Lager lidden Layer Logistic Regression
-200
0.5k
-400
0.0%
-0.kk
10000
20000
30000
40000
50000
60000
20000
4000C
60000
80000
100000
Position Sequence
Position
Sequerce
C.4
WEIGHH-STANDARRDZZATION ABLATION
VGG CIFAR-10 Weight Standardizotion
VGG++ on CIFAR-100 / Weight Standardization
Witn
8.0k
Without WS
Langth Regret
15.0k
Length Regret
With WS Without
10.0k
4.0k
2.0k
5.0k
0.0k
0.8k
10000
20000
30000
40000
50000
10000
20000
30000 40000
50000
Position in Sequence
Position Sequence
C.5 NUMBER OF REPLAY STREAMS
We run ablations for different number of replay-streams (K in Algorithm D on CIFAR-100 100 and ImageNet. The results on ImageNet show that performing too much replay (choosing K too large) can be harmful.
VGG++ CIFAR-100 100 Number of replay
ImageNet/ / Num Replay Streams
Longth Regret [nats]
8000
50 replpyy streams
seeley
80000
replay streamss
8000
replay
Regret
20000
50 replay streams
8000
10000
2000
-20060
-2000
-3000
10000
20000
30000
40000
50000
0.6
0.8
1.0
Position Sequence
Posttion Sequence
C.6 SCALE AND SHAPE OF THE REPLAY DISTRIBUTION
Besides of uniform replay for sttlay- training we experimented with alternative replay distribu- tions. Exponentially decaying replay (Preplay (a) À reservoir sampled replay buffers, but lead to significant longer description lengths and suboptimal results in our experiments.
is popular in continual -arinuualllearing with
As an compromise between uniform replay and exponential decay we experimented with long-tailed Pareto distributions: (re (a) [*/A] (a+IJ The scale parameter À determines to what extend old
examples are replayed and fixed shape parameter log, 5 Rs 1.16 for all out experiments:
17

---

Published as a conference paper at ICLR 2023
MniisNet on EMNIST/ Replay Scale
VSG++ CIFAR-100 Replay Scale
Descr Length Regret [hats]
2.5K
Raplay Scale 10k
2.0%
Replay Scale 10k
2.0k
Replay Scale e 23k
Replay
Lengüh Regret
1.5k
Replay Scale 50k
Replay Scale 25R
Replay Scale 100%
Replay Scale 5k
1.0k
0.3K
0.5K
0.0k
0
20000
40000
60000
80000 100000
10000
20003
30000
40000
50000
Position in Sequence
Position Sequence
Our experiments suggest that flat, almost uniform replay distributions lead to the shortest description lengths for the sequences from i.i.d. sources. On non-stationary sequences however, long-tailed replay that favours recent data, but maintains finite probability of replaying even the earliest examples works best.
C.7 NON-STATIONARY SEQUENCES
In this study we concentrate on data sequences from stationary (i.i.d) data sources to ensure we can compare results with established ERM based training heldout-data, and, because stationary data is arguably one of the most challenging scenarios for a sequential learner: there no benefit in focusing on recenly observed data and instead globally optimal predictive model must be learned.
over ERM is that it is well defined for individual and non- stationary sequences. We therefore present series of experiments non-stationary data. We leave it to future work to analyze and to improve online learners on non-stationary data more thoroughly.
Nevertheless, one major benefit of over
C.7.1 SPLIT CIFAR-10
We derive a non-stationary sequence from the CIFAR-10 dataset by treating as disjunct binary classification tasks between the CIFAR classes 0 vs. (Task-A), 2 vs. 3 (Task-B), ..... 9 vs 10 (Task-E). We train the model sequentially on examples from each task, however instead of evaluating forgetting on held-out data after each new task, which is the standard protocol in continual learaning, we here insert new examples from previous tasks into the non-stationary sequence. A learner therefore demonstrate good performance by rapidly re-adapting examples. The problem is task agnostic because we do not supply information about the current task-id to the learner. We concatenate unique examples from the tasks into a joint sequence: [0, 6000): Task-A, [6000, 13000): Task-B, [13000, 14000): Task-A, [ [14000, 22000): Task-C, [22000, 23000): Task-A, [23000, 24000): Task-B, [24000, 33000): Task-D, [33000, 34000): Task-A, [34000, 35000):
previous task from a few
Task-B, [35000, 36000): Task-C [36000, 46000): Task-E, [46000, 47000): Task-A, [47000, 48000);
Task-B, [48000, 49000): Task-C, [49000, 50000): Task-D
We run the broad random hyperparameter sweeps for the VGG++ model, however add the scale of the pareto-distributed replay distribution and the capacity of the replay buffer as an additional random hyperparameter between [1000 ... 50000). We show the next-step and cumulative next-step performance for the best performing replay-stream and replay buffer learners:
Split CIFAR-10 Next-step cross-entropy
Split CIFAR-10 Cumulative cross- ents-yy
RepleySuffor, 30k capacity
RuollayStramm, scale
12000
RepleyBu/fer, capecity
RepleySt ream. 3k scale
10000
Next-step
Curuu elvve
1.0
6000
6000
0.5
10000
20000
JU000
40000
50000
0
10000
20000
30000
40000
50000
Poshio in Sequence
Position in Sequence
18

---

Published as a conference paper at ICLR 2023
The regret plot for the same experiments show the difference more clearly. We also show the regret for the best replay-stream model with various techniques disabled:
Split CIFAR-10/ Replay Stream vs. Buffer
Split CIFAR-10 Ablations
2000
ByBuffer, capacity
Lemplh Reggel, [ndls]
1500
RegpleyStreat
1500
Rep ayStream, 3k scale
1000
Replayfinneem hadi
Heplaybitream, Nocate
RepleySkream NeWs
Length
500
500
-300
20000 30000
40000
50000
10000
30000
40000 50030
Position Sequence
Position Sequence
Like in the previous plots, the shaded areas indicate the 99% confidence intervals obtained from bootstrap sampling the experiments in the hyperparameter sweep. We see that multiple replay-stream learners have significantly better performance than the best replay-buffer learner. Given that this dataset is small and fits completely into RAM, we can close the gap between replay-streams and replay-buffers by configuring a replay-buffer with 50k capacity and using recency-biased sampling: which is the only difference between these learners.
Finally, we run an ablation study with 3 different scales for pareto-distributed replay; and the regret plot for 3 replay-buffer learners with 3 different capacities of the uniform sampled replay-buffed The results were obtained by running the same hyperparameter sweeps as before, however with the replay distribution or replay-capacity fixed to 1k, 3k or 10k respectively. We observe that the width of the replay distribution and the capacity of the replay-buffer trade-off between faster adopting to completely new tasks, and having better performance recurring tasks:
Split CIFAR- Replay Distribution Scale
Split CIFAR-10 Replay Buffer Capacity
Length Regret [nats]
1250
Rep syStream. 1k scale
Lengith Regret [nats]
RaplaySuffer. 10k capacity
1000
Rep eyStrcam. ccale
ReplsyBuffer. 1K capacity
ayStream. 10k
400
ReplaySuffer. 3k
750
200
400
250
-200
-250
-400
20000
30000 40000
50000
30000 Position Sequence
20000
Position Sequence
C.7.2 VEHICLE CLASSIHCATION DATA
We run experiments on the vehicle classification data sequence introduced by Duarte & Hu 2004)) The sequence consists of about 80k observations with 100 features each; the classification task is to predict the vehicle category. We use a 2 hidden-layer MLP as the model architecture with the same hyperparamter-sweer from the VGG++ experiments. We show the next-step performance, the corresponding regret plots for replay- stream vs replay-buffer training, and regret plots with label smoothing or forward calibration disabled.
Senself Vehicle/ / Next step cruss entropy
Serizllf Vehicle/ Next step error
RaplayBuffer, capacity
Raplay Buffer, capacity Streay, 50c scale
ReplayStream, 50k scale
step error
0.4
0.3
0.2
10000 20000 30000 40000 50000 6000O 70000
80000
0
10000
20000
40000 50000 50000 70000 80000 Position Sequence
30000
Position in Sequence
19

---

Published as a conference paper at ICLR 2023
Vehicce:: Replay Buffer vs. Replay Stream
Deser Length Regret [nnats]
600
RepleyBufter. 50k capacity
ReplayStream
RepleyStream 50k scale
2500
ReplayStream, nocalbb
Descc Regret
ReplayStream, nots
200
1500
500
10000 2000 J0000 40000 50000 00000 7000G 80000
10000 20003 30000 40000 50000 6000C 10000 80000 Position in Sequence
Position Sequence
Over the whole sequence we obtain an average forward validation error of 15.5% (84.5% accuracy). This is competitive with the more complex and ensemble-based methods described by Celik al. (2022) (85% accuracy), and an significant improvement over the baseline methods described therein ( 82% accuracy). We highlight that here essentially just train a neural network with fixed order of training examples, with recency biased rehearsal, label smoothing and forward-calibration.
Vehicle/ / Repley distribution scele
Vehicle Replay buffer capacity
ReplayStrent scale
RepleyBuffer, capacity
200
HeplayStreem, 13R scale
400
Repleytlutter. 25L capecity
Descr, Regrot
Htppayytteamm 25k scale
bength Regret,
Replavtiutter, S0x capacity
100
StrpaayStramm.... 53k scale
DeplayBuffer, 100k capacity
-200
10000 20000 30000 40000 50000 60000 70000 80000
10000 20000 30000 40000 50000 60000 70000 80000 Position in Sequence
Position in Sequence
C.7.3 CONTINUAL GEO-LOCALIZATION (CLOC)
We present results on the CLOC data introduced by Cai et al. 2021). CLOC is large scale, chrono- logically sorted image classification sequence consisting of R3 39M images with their geolocation as a categorical label. For zs 5% of the images we either received download errors, or the downloaded content could not be decoded as image data. In total were able to obtain 37,093,766 labeled images. Figure 2 in (Cai et al. 2222)) shows that the data is strongly non-stationary: and that traditional ERM training, which treats the data i.i.d., results in held-out error rate between 80 and 90%.
Cai et al. 2021) reserve the first 2M (5%) datapoints for pre-training the model statically before entering the online-phase, split-off 1% of the data throughout for validation purposes and only evaluate the images from the first new album in each mini-batch instead of all images. Their online- learning task and metric are thus in spirit similar to the prequential MDL problem we are tackling here, in detail however sufficiently different that the quantitative results are not directly comparable. Following (Cai et al. 202T) we use a standard ResNet50 architecture and rum experiments with replay buffers and replay streams. The hyperparameter sampling space is detailed in Appendix B.5 Note that we use batch size of 128 because small batch-sizes allow the model to more quickly adapt to changes in the data distribution; and relatively low number of 10 to 25 replay-steps replay-streams to limit the total computational cost due to the size of the data.
We observe that heavily recency biased replay leads to significantly improved results. For replay streams we experimented with uniform replay, replay with exponentially decaying priority and with replay governed by a heavy tailed Pareto distribution (see (.6p. From these the heavy tailed Pareto replay leads to the shortest description lengths. Even more than in the i.i.d case, calibratiin plays crucial role obtain good results.
20

---

Published as a conference paper at ICLR 2023
CLOC with Replay Streams: Next step neg. log ass
CLOC with Replay Streams: Next step error
(rolling DNG.
0.8
(tolling
0.7
0.5
Position in Sequence
Position in Sequence
Next-step performance We plot the 5k rolling average next-step performance of the best perform- ing model from our random hyperparameter sweep (K=22 Pareto distributed replay streams with scale of 180). The model obtains description length of 1.33G nats and next-step error-rate of typically 60 + 10%.
Ablations Left: We show the description length regret for the best replay-buffer training run relative to the best replay-stream training run. Both experiments consumed about 5 x 10 FLOPs. Right: Regret for replay-streams without forward calibration ralative to replay streams with forward calibration:
CLOC: Reploy Buffer Regret
1+7
Forward-Callbe CewarrdCallbration Regret
Descn. Lengthh Reirret [nats]]
Ropaly
Descr Lengtn Regret [nats]
colibbaatoonnnnn
Reclay Duffer
wio forwardicalltratoon
0.8
0.6
0.2
0.5
1,0
1.5
2.0
2.5
3.0
0.0
0.5
1.0
3.5
2.0
2.5
3.0
3.5
Position In Sequence
1e7
Positin Sequence
167
21


Reviews:
[{"review_id": "jnz4mgv98_o", "reviewer": "Reviewer_zftM", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes two new techniques: *forward-calibration* and *replay streams* for efficiently computing prequential description lengths. It particularly focuses on the computational costs associated with these methods and claims to show that they improve upon previously reported results by large margins.", "summary_of_the_review": "~The paper in its current state is hard to read and it is not clear that the improvements are significant. Therefore, I cannot recommend acceptance. However, if changes are made and my questions are clarified, I would be willing to change my mind.~\n\nSince the authors have improved their presentation and clarified several of my concerns, I am increasing my score to 6.", "strength_and_weaknesses": "**Strengths:**\n- The experiments compare several methods across multiple datasets and networks.\n- The paper does multiple ablation studies to better understand different components of the algorithm, although this study is relegated to the appendix.\n\n**Weaknesses:**\n1. The idea of replay streams has been well studied in the Reinforcement Learning literature but has not been cited in this work.\n2. The organization of the paper can be improved. Equations are introduced without defining all of the notations. I would recommend adding a preliminaries section where notations and prerequisites are first defined.\n3. The MDL principle and prequential description lengths are properly introduced only in the appendix. I would recommend a short version of this be introduced in the main text.\n4. Under $Chunk Incremental/Continual Fine-tuning (CI/CF)$, a claim is made \"However, recent research suggests that...\" - this statement does not have a reference. Also, following it, the authors state that they run an ablation study but do not state where this ablation study is, nor the results of it.\n5. Under *mini-batch incremental/replay streams* they make an assumption \"We instead assume that the data is stored in its original order in permananet storage and we maintain K replay streams...\" - this is an extremely strong assumption and cannot hope to hold in practice. The authors emphasize that this framework is for the setting where the i.i.d assumption fails, typically in streaming settings and therefore, I feel this assumption cannot hold in practice.\n6. Interpreration of Results:\n    - I am not sure what to take away from Table 1. It seems to me like ERM outperforms MI/RS in most settings which makes sense since these settings are artificially created from the i.i.d setting.\n    - In Figure 1, the scale of the loss as well as errors is different for ERM compared to Prequential MDL training. THerefore, I am unsure how to compare these two. It could be argued that the difference in the plots is purely due to scale since the absolutely differences is what we compare.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "hxA-_srZBWb", "reviewer": "Reviewer_7xY3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper investigates the problem of minimizing prequential description lengths for image datasets with neural networks, primarily dealing with the issue of computational overhead. The proposed method (Mini-batch Incremental Training with Replay Streams, MI/RS) is inspired by  continual learning and its effectiveness is demonstrated empirically across traditional image classification datasets and neural network architectures.", "summary_of_the_review": "See “Strength And Weaknesses” and “Clarity, Quality, Novelty And Reproducibility”.", "strength_and_weaknesses": "It makes an encouraging attempt to bridge the gap between theory and practice for minimum description length.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "QD074FAp3-y", "reviewer": "Reviewer_zGnF", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper studies the problem of training deep neural networks with the minimum description length objective. The paper connects the MDL objective training to the ERM objective training but under the settings of continual learning. The paper conducts extensive experiments and compares several methods to achieve the best MDL performance with FLOP cost constraints.", "summary_of_the_review": "The paper studies a practically very important problem, conducts extensive experiments, and provides convincing arguments to understand the experimental observations. The paper's presentation is very clear. The paper is weak on the methodology and novelty side, but still very useful given its strong and solid empirical results.", "strength_and_weaknesses": "Strengths:\n1. The paper studies the problem of MDL objective training. This setting addresses many problems in practice where assumptions for ERM objectives are not valid.\n\n2. The paper draws the connection between MDL objective training and ERM objective training under continual learning settings. \n\n3. The paper conducts extensive experiments and compares several methods training under the MDL objective. The paper also proposes a practical method to achieve approximate-random in rehearsal training. \n\n4. The paper gives a nice overview of MDL in the appendix.\n\n\nWeaknesses:\n1. The novelty and algorithmic contributions of the paper are limited. The proposed/studied methods are all existing approaches or simple modifications of existing ones. The paper also lacks theoretical justifications.\n\n2. As mentioned in the paper, the experiments do not account for the learning rate annealing, which is a widely used technique for ERM training and significantly affects the final performance.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Ehm3n7ZCV7e", "reviewer": "Reviewer_LsM9", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work extensively investigates continuous learning based methods for prequential minimum description length. \n\nMore precisely, the authors train MDL models using online learning with rehearsal, and propose two techniques for improving the results. \n- Forward-calibration, to optimize a calibration parameter $\\beta$ by using each new batch of samples for evaluation, then single gradient step on $\\beta$, then training the other parameters $\\theta$, before being placed in a replay buffer. \n- Replay streams, to avoid implementing large replay buffers. Replay streams rely on the data stored in its original order, and maintain K pointers to some positions in the ordered data. When the k-th replay stream is called, it yield the corresponding sample and increments the pointer by one. The authors also propose a mechanism to randomly reset the pointers depending on what's needed.\n\nThe authors extensively evaluate their method compared to classical prequential MDL (models trained from scratch or fine-tuned on increasingly larger chunks of data) and compare to ERM on various datasets and neural network architectures (without learning rate schedule). They show their method to perform reasonably well against ERM given the same computational budget and better than previous baselines for prequential MDL, and perform some ablations on techniques such as forward calibration, label smoothing and weight standardization.", "summary_of_the_review": "This work investigates an interesting alternative to ERM. It is well-written and the experimental protocol is thorough, although some baseline or experiments may be in my opinion missing to convince that the proposed method is very convincing. I wouldn't recommend acceptance for now but would increase my score if my concerns (add baselines or explain why they are not appropriate, meaning of the cumulative loss w.r.t. test accuracy) are answered.", "strength_and_weaknesses": "Strength:\n- Finding alternatives to ERM, whose central hypothesis is that data is i.i.d. is an important problem to apply machine learning in many interesting settings. This work investigates a potential candidate, namely prequential MDL.\n- The paper is very well-written and motivated.\n- The experimental protocol seems thorough: many different architectures and datasets are considered, and ablations are done.\n- Experimental results are promising: the proposed method performs better than other MDL baselines, and rival with ERM without learning schedule.\n\nWeakness:\n- It seems to me that some baselines are missing: it could be worth evaluating the test accuracy for MDL baselines on ImageNet, and mentioning the results of ERM with a learning schedule (I am surprised by the discrepancy of ERM results with/without learning schedule).\n- Although MNIST, CIFAR and ImageNet are iid, wouldn't it be possible to make it non-iid, train on a smaller number of epochs and see how your method performs vs. ERM? I think it may be a more appropriate setting to use continual learning.\n\nMinor:\n- Typo: negaive (last line before Figure 4).", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster