# APP: Anytime Progressive Pruning

Diganta Misra
Mila - Quebec AI Institute, Landskape AI, UdeM
&Bharat Runwal11footnotemark: 1
Landskape AI, IIT-Delhi
Tianlong Chen
VITA, UT-Austin
&Zhangyang Wang
VITA, UT-Austin
&Irina Rish
Mila - Quebec AI Institute, UdeM
{diganta<EMAIL_ADDRESS>Equal contribution

###### Abstract

With the latest advances in deep learning, there has been a lot of focus on
the online learning paradigm due to its relevance in practical settings.
Although many methods have been investigated for optimal learning settings in
scenarios where the data stream is continuous over time, sparse networks
training in such settings have often been overlooked. In this paper, we
explore the problem of training a neural network with a target sparsity in a
particular case of online learning: the anytime learning at macroscale
paradigm (ALMA). We propose a novel way of progressive pruning, referred to as
Anytime Progressive Pruning (APP); the proposed approach significantly
outperforms the baseline dense and Anytime OSP models across multiple
architectures and datasets under short, moderate, and long-sequence training.
Our method, for example, shows an improvement in accuracy of $\approx 7\%$ and
a reduction in the generalization gap by $\approx 22\%$, while being $\approx
1/3$ rd the size of the dense baseline model in few-shot restricted imagenet
training. We further observe interesting nonmonotonic transitions in the
generalization gap in the high number of megabatches-based ALMA. The code and
experiment dashboards can be accessed at https://github.com/landskape-
ai/Progressive-Pruning and https://wandb.ai/landskape/APP, respectively.

##  1 Introduction

Figure 1: Non-Monotonic Transition: Generalization gap as a function of the
number of megabatches ($|S_{B}|=100$) in the long-sequence ALMA setting with
full replay for ResNet-50 backbone on the CIFAR-10 dataset. We observe that
APP consistently demonstrates the lower generalization gap compared to anytime
OSP and baseline models. The curve for APP showcases high oscillation in the
critical regime where the model starts overfitting, which can be attributed to
the regularization effect induced by the pruning at the start of each
megabatch.

Supervised learning has been one of the most well-studied learning frameworks
for deep neural networks, where the learner is provided with a dataset
$\mathcal{D}_{x,y}$ of samples($x$) and corresponding labels($y$); and the
learner is expected to predict the label $y$ by learning on $x$ usually by
estimating $p(y|x)$. In an offline learning setting Ben-David et al. (1997),
the learner has access to the complete dataset $\mathcal{D}_{x,y}$, while in a
standard online learning setting Sahoo et al. (2017); Bottou et al. (1998) the
data arrive in a stream over time, assuming that the rate at which samples
arrive is the same as that of the learner’s processing time to learn from
them. There are several fine-grained types of learning from a stream of data,
including but not limited to: continual learning Van de Ven and Tolias (2019);
Thrun (1995); Ring (1998), online active learning Baram et al. (2004); Settles
(2009), and anytime learning Grefenstette and Ramsey (1992); Ramsey and
Grefenstette (1994). In an anytime learning framework, the learner has to have
good performance at any point in time, while gradually improving its
performance over time upon observing new data that subsequently arrive.

Anytime Learning at Macroscale(ALMA) Caccia et al. (2021) recently introduced
a new subparadigm of learning inspired by anytime learning and transfer
learning Pan and Yang (2009). In ALMA, the time it takes for the model to be
trained on a set of samples called a megabatch is significantly shorter than
the interval between the arrival of two consecutive megabatch. Thus, ALMA
studies the optimal waiting time that corresponds to the mega-batch size to
ensure that the model is a good anytime learner. Caccia et al. Caccia et al.
(2021) abstractly define a learner trained in an ALMA setting as:

> _… a learner that i) produces high accuracy, ii) can make non-trivial
> predictions at any point in time, while iii) limits its computational and
> memory resources_

In this work, we are interested in exploring the training of sparse(pruned)
neural networks in the ALMA setting. Pruning Blalock et al. (2020); Luo et al.
(2017); Wang et al. (2021) of overparameterized deep neural networks has been
studied for a long time. Pruning deep neural networks leads to a reduction in
inference time and memory footprint. Pruning has gained prominence since the
inception of the lottery ticket hypothesis (LTH) Frankle and Carbin (2018);
Frankle et al. (2019a, b); Malach et al. (2020), which demonstrated the
existence of subnetworks (lottery tickets) within a dense network, which when
trained from random initialization under the same setting will match or
outperform the dense network. Although early pruning work focused exclusively
on pruning weights after pretraining the dense model for a certain number of
iterations, extensive research has recently been conducted on pruning the
model at initialization, that is, finding the lottery ticket from a dense
model at the start without pretraining the dense model Lee et al. (2018); Wang
et al. (2020a). However, few studies Chen et al. (2020) have investigated the
training of sparse(pruned) neural networks in online settings. Thus, our
objective is to answer the following question:

“ _Given a dense neural network and a target sparsity, what should be the
optimal way of pruning the model in ALMA setting?_ ”

Concisely, our contributions can be summarized by the following four points.

  1. $\ast$

We provide the first comprehensive study into pruning of deep neural networks
in ALMA setting. Specifically, we conclude via extensive empirical evaluation
that progressive pruning consistently outperforms different baselines. We
define the baselines used for comparison in section 3.

  2. $\ast$

We, thus, propose a novel approach of progressively pruning dense neural
networks in ALMA paradigm which we term as Anytime Progressive Pruning(APP).

  3. $\ast$

We further investigate into the training dynamics of APP as compared to the
baselines in ALMA setting with varied number of megabatches using CIFAR-10,
CIFAR-100 and Restricted ImageNet datasets, and, observe non-monotonic
transition graphs in their generalization gap during training.

  4. $\ast$

In addition, we do conclusive ablation studies into investigating the
different type of pruners that are compatible with APP and one-shot pruning
(OSP) models along with studying the effect of replay. We conclude that APP
outperforms OSP when all $t-1$ megabatches are replayed while training on the
$t$-th megabatch, however, OSP models outperform APP models when no replay
buffer is used.

In the following section, we provide concrete insights into the motivation of
the problem statement that we investigate in this paper, derived from the
foundations of active learning and practical data acquisition(collection,
annotation, and labeling).

###  1.1 Motivation

A well-accepted statement in deep learning states “ _Collection of unlabeled
data is relatively easy, however, labeling is costly and difficult._ ” This is
arguably true because labeling or annotating data requires a human in the loop
with extensive domain knowledge, which induces an additional cost in addition
to the cost in the form of computing power required to train the learner.
Active learning Baram et al. (2004); Settles (2009); Olsson (2009); Liu et al.
(2021); Dimitrakakis and Savu-Krohn (2008) is a well-studied domain in machine
learning that particularly investigates the training of data-efficient models
under cost constraints. Specifically, given a learner and a set of unlabeled
data, an active learning algorithm will select particular samples to label via
an oracle, under a predetermined cost budget, to maximize performance. This
framework is not only limited to the labeling of unlabeled data, but can also
be extended to label correction or reannotation of noisy labeled data. In
Bernhardt et al. (2021), the authors study optimal reannotation strategies
under resource constraints to achieve a maximal performance gain, which they
call active label cleaning. The authors of Settles et al. (2008) study the
annotation times and costs of different data sets in the real world domain.
They report the variation in cost and time required to label different sets of
unlabeled data.

Reiterating from the previous section, we are interested in understanding and
finding the optimal strategy for training sparse neural networks given a
target sparsity in the ALMA setting. Often, in industrial and practical
scenarios, there exists a fixed initial period for the collection of data,
which is subsequently labeled by an oracle. For this problem statement, we
assume knowledge of the total number of samples that the learner will observe,
which allows us to predetermine the required number of megabatches. We assume
that the complete stream of data is already acquired but unlabeled and that
the individual megabatches received in the stream by the learner are labeled
over time by an oracle. This allows us to optimally select the wait time
(megabatch size) and study the interesting properties of the training dynamics
of models trained on these megabatches in an ALMA setting.

##  2 Related Work

###  2.1 Pruning

Pruning LeCun et al. (1990); Han et al. (2015a) as one of the effective model
compression techniques is widely explored in the field of efficient machine
learning. It trims down the parameter redundancy in modern over-parameterized
deep neural networks, aiming at substantial resource savings and unimpaired
performance. Depending on the granularity of the removed network components,
classical pruning methods can be categorized into unstructured Han et al.
(2015a); LeCun et al. (1990); Han et al. (2015b) and structural pruning Liu et
al. (2017); Zhou et al. (2016), where the former removes parameters
irregularly and the latter discards substructures such as convolution filters
or layers. In addition to the above post-training pruning, it can also be
flexibly applied before network training, such as SNIP Lee et al. (2019),
GraSP Wang et al. (2020b) and SynFlow Tanaka et al. (2020) or during training
Zhang et al. (2018); He et al. (2017). The key factor in these methods is the
estimation of the importance of pruning targets, which can be learned Zhang et
al. (2018); He et al. (2017) using data-driven methods or approximated by some
heuristics of the training dynamics, including weight magnitude Han et al.
(2015a), gradient Molchanov et al. (2019), hessian LeCun et al. (1990).

Recent closely related work Chen et al. (2021) defines pruning in sequential
learning as a dynamical system and proposes two effective lifelong pruning
algorithms to identify high-quality subnets, leading to superior trade-offs
between efficiency and lifelong learning performance. Furthermore, Golkar et
al. (2019) prunes neurons with low activity and Sokar et al. (2020) compresses
the sparse connections of each task during training to overcome the problem of
forgetting.

###  2.2 Lifelong Learning

Lifelong learning Ring et al. (1994); Thrun (1995); Ring (1998); Thrun (1998)
has gained increasing attention from the deep learning community. Numerous
algorithms developed can be roughly divided into two categories: ($i$) one
group of methods Wang et al. (2017); Rosenfeld and Tsotsos (2018); Rusu et al.
(2016); Aljundi et al. (2017); Rebuffi et al. (2018); Mallya et al. (2018)
accommodate newly added tasks/classes by accordingly growing the network
capacity. However, it usually suffers from the explosive model size, which is
proportional to the number of classes. ($ii$) the other group of approaches
mainly takes advantage of advances in transfer learning Kemker and Kanan
(2017); Belouadah and Popescu (2018), where the quality of pre-trained
embeddings plays an essential role. In particular, Li and Hoiem (2017); Castro
et al. (2018); Javed and Shafait (2018); Rebuffi et al. (2017); Belouadah and
Popescu (2019, 2020) adopt replay methods with some stored past training data
to alleviate catastrophic forgetting in sequential learning. Furthermore, more
follow-ups use imbalance learning techniques He and Garcia (2009); Buda et al.
(2018) or knowledge distillation regularizations Li and Hoiem (2017); Castro
et al. (2018); He et al. (2018); Javed and Shafait (2018); Rebuffi et al.
(2017); Belouadah and Popescu (2019, 2020) to further improve its performance
on all learned tasks.

###  2.3 Revisiting ALMA

In this section, we revisit the ALMA learning framework as conceptualized in
Caccia et al. (2021). Based on the reasoning provided in the original paper,
we explicitly focus on classification problems. In ALMA, the model
$f_{\theta}$ is provided with a stream of $S_{B}$ of $|S_{B}|$ consecutive
batches of samples under the assumption that there exists an underlying data
distribution $\mathcal{D}_{x,y}$ with input $x\in\mathbb{R}^{d}$ and target
labels $y\in\\{1,...,C\\}$. Each megabatch $\mathcal{M}_{t}$ consists of $N\gg
0$ i.i.d. samples randomly drawn from $\mathcal{D}_{x,y}$, for
$t\in\\{1,...,S_{B}\\}$. Therefore, the stream $S_{B}$ is the ordered sequence
$S_{B}=\\{\mathcal{M}_{1},....,\mathcal{M}_{|S_{B}|}\\}$ where $|S_{B}|$
represents the total number of megabatches in the stream. Thus, the model
$f_{\theta}:\mathbb{R}^{d}\rightarrow\\{1,...,C\\}$ is trained by processing a
mini-batch of $n\ll N$ samples at a specified time of each mega-batch
$\mathcal{M}_{t}$ and iterating multiple times over each mega-batch before
having access to the next mega-batch. In ALMA, it is assumed that the rate at
which megabatches arrive is slower than the training time of the model on each
megabatch and, therefore, the model can iterate over the megabatches at its
disposal based on its discretion to maximize performance. ALMA can be
considered a special case of continual learning (CL) or lifelong learning Ring
et al. (1994); Thrun (1995); Ring (1998); Thrun (1998), whose data
distribution across batches (or tasks) is considered stationary. Compared to
CL, the difficulty in ALMA is fewer data in each learning stage, while the
challenge in CL is the dynamic data distributions across different learning
stages. Meanwhile, ALMA is also loosely relevant to online learning Saad
(1998) with the key difference that ALMA receives large batch data
sequentially rather than in a stream manner.

In ALMA, one of the main aims was to study the effect of variation in waiting
time, which directly corresponds to the size of each megabatch, i.e. how long
one should wait to collect samples for a particular megabatch. Furthermore,
the authors conducted a conclusive study using different baselines, two of
them being (a) ensemble and (b) dynamic growing. In both cases, the complexity
of the model parameters was gradually increased to allocate sufficient
capacity to accommodate the newly arrived megabatches. However, in this paper,
we investigate the effect of progressively decreasing the parametric
complexity of the model via pruning and subsequently training a sparse neural
network in an ALMA setting.

##  3 Anytime Progressive Pruning

Figure 2: Overview of Anytime Progressive Pruning (APP) using full replay with
a given randomly initialized dense model $f_{\theta}$ and $|S_{B}|$ total
megabatches.

In this section, we formally introduce our proposed method Anytime Progressive
Pruning(APP). As demonstrated in Figure 2, given a randomly initialized dense
neural network $f_{\theta}$, a target sparsity $0.8^{\tau}\times 100\%$, and
the first megabatch $\mathcal{M}_{1}\in S_{B}$ containing $|\mathcal{M}_{1}|$
samples, we use $20\%$ random samples in $M_{1}$ denoted as $\pi_{1}$ and pass
them to SNIP Lee et al. (2018) together with $f_{\theta}$ and prune the model
to $0.8^{\delta_{1}}\times 100\%$ in one iteration at initialization. After
pruning, we take the pruned network $f_{\theta}^{1}$ and train it on
$\mathcal{M}_{1}$ for $k$ epochs. For the next sequence $\mathcal{M}_{2}$, we
first concatenate the entire previous megabatch $\mathcal{M}_{1}$ into the
current megabatch $\mathcal{M}_{2}$ that gives
$\mathcal{M}_{1}\cup\mathcal{M}_{2}$ and then take the best performing
checkpoint of the trained model on $\mathcal{M}_{1}$ \- $f^{1}_{\theta_{1}}$
and again use $20\%$ random samples in $\mathcal{M}_{1}\cup\mathcal{M}_{2}$
denoted as $\pi_{2}$ and pass them to SNIP to prune $f^{1}_{\theta_{1}}$ by
further $0.8^{\delta_{2}}\times 100\%$ and use the resultant model
$f^{2}_{\theta_{1}}$ to train it on $\mathcal{M}_{1}\cup\mathcal{M}_{2}$.

Algorithm 1 Training APP in the ALMA setting

1:$f_{\theta}^{t=0},\tau$, replay,
$S_{B}\Longleftrightarrow\\{\mathcal{M}_{1},....,\mathcal{M}_{|S_{B}|}\\}$

2:$t\leftarrow 1$

3:$\delta\leftarrow\\{start=1,end=\tau,steps=|S_{B}|\\}$ $\triangleright$
Pruning states at each megabatches

4:while $t\leq|S_{B}|$ do $\triangleright$ For each megabatch based training

5: SNIP set($\pi_{t}$) $\leftarrow\emptyset$

6: if replay then

7: $\mathcal{M}_{t}\leftarrow\bigcup\limits_{i=1}^{t}\mathcal{M}_{i}$

8: else

9: $\mathcal{M}_{t}\leftarrow\mathcal{M}_{t}$

10: end if

11: pruning state $\leftarrow{0.8^{\delta_{t}}}$ $\triangleright$ Target
Sparsity ($\times 100\%$) at each megabatch

12: SNIP set
$\leftarrow\pi_{t}\subset\mathcal{M}_{t}\mid\frac{|\pi_{t}|}{|\mathcal{M}_{t}|}=0.2$

13: $f_{\theta}^{t}\leftarrow$ SNIP($f_{\theta}^{t-1}$, SNIP set, pruning
state)

14: $f_{\theta}^{t}$.train($\mathcal{M}_{t}$) $\triangleright$ Fine-tune or
retrain from scratch

15:end while

Thus, for each megabatch $\mathcal{M}_{t}\in S_{B}$, we construct the replay
inclusive megabatch $\mathcal{M}_{t}$ by taking the union of all previous
megabatches along with the current megabatch and then create a small sample
set $\pi_{t}$ of size $0.2\ast|\mathcal{M}_{t}|$ to be used to prune the model
to $0.8^{\delta_{t}}\times 100\%$ sparsity. Here, $\delta_{t}$ is obtained
from a predetermined list $\delta$ of uniformly spaced values that denote the
target sparsity levels for each megabatch in the stream $S_{B}$. After pruning
the model, we train it on the $\mathcal{M}_{t}$ megabatch and evaluate it on a
holdout test set.

Note:

  1. *

The $|\cdot|$ operator denotes the size of a given set throughout this paper.

  2. *

$|\theta|$ denotes the number of trainable parameters in millions.

  3. *

By default, APP always uses full replay buffer.

  4. *

For all experiments, the scope of pruning was maintained to be Global.

  5. *

$0.8^{\tau}\times 100\%$ represents the fraction of weights left from the
initial dense model post pruning and not the fraction of weights pruned which
would be denoted as $(1-0.8^{\tau})\times 100\%$.

To evaluate APP, we use primarily 2 baselines:

  1. 1.

Baseline: This denotes the standard model (e.g., convolution neural network or
transformer) at full parametric capacity trained and fine-tuned on all
megabatches in the stream $S_{B}$ using stochastic gradient descent in an ALMA
setting.

  2. 2.

Anytime OSP: This denotes One Shot Pruning (OSP) to the target sparsity
$0.8^{\tau}\ \times 100\%$ at the initialisation of $f_{\theta}$ and then
subsequently training on all mega-batches in the stream $S_{B}$ in an ALMA
setting. Thus, Anytime OSP models have the lowest parametric complexity since
the start of training on the first megabatch in the stream $S_{B}$. We use the
same pruner of choice (SNIP) by default for both APP and Anytime OSP. Similar
to APP, we prune the model at initialisation using a small randomly selected
subset $\pi_{1}$ of the first megabatch $\mathcal{M}_{1}$ of size
$0.2\ast|\mathcal{M}_{1}|$.

We use the following metric along with the test accuracy and the
generalization gap to evaluate the methods specified above.

  1. 1.

Cummulative Error Rate (CER): This can be defined by the following equation:

$CER=\sum_{t=1}^{S_{B}}\sum_{j=1}^{|T_{x,y}|}\mathbbm{1}{(\mathcal{F}_{t}(x_{j})\neq
y_{j})}$ (1)

Here, $T_{x,y}$ represents the held-out test set used for evaluation,
$\mathcal{F}_{t}$ represents the trained model at $t$-th megabatch and
$\mathcal{F}_{t}(x_{j})$ represents the prediction on the $j$-th index sample
of the test set $T_{x,y}$ compared to the true label for that sample $y_{j}$.
CER provides strong insights into whether the learner is a good anytime
learner since it is expected to minimize CER at each megabatch training in the
stream $S_{B}$.

We follow the standard definition of the generalization gap as the difference
between the training and the validation accuracy. This gives a notion of
whether the model is over- or under-fitting.

##  4 Experiments

In this section, we provide in-depth details on the experimental setup, the
learning algorithms, and the data sets used in our empirical evaluation. We
further discuss the training dynamics observed under the variation of
$|S_{B}|$ and supplement our results with visualization of the training
curves.

#### Datasets

We empirically evaluated APP, Anytime OSP, and Baseline models on three
different data sets: (a) CIFAR-10 (C-10) Krizhevsky et al. (2009) (b)
CIFAR-100 (C-100) Krizhevsky et al. (2009) and (c) Restricted Imagenet
(balanced) Engstrom et al. (2019); Tsipras et al. (2018). Both C-10 and C-100
consist of 50,000 training images and 10,000 test images, each of size 32 x
32, divided into 10 and 100 classes, respectively. Restricted ImageNet
(balanced) is a subset of the original ImageNet data set Russakovsky et al.
(2015) consisting of 89517 training images and 3450 test images, each of 224 x
224 size divided into 14 classes consisting of five subclasses each. For our
experimental analysis, we conduct benchmarks on both the 224 x 224 size
version and additionally a 32 x 32 size version where we down-sample each
image using bilinear interpolation.

Taking into account the three datasets mentioned above, we construct
benchmarks for the evaluation of APP as follows: (1) we randomly partition the
data set into $|S_{B}|$ megabatches with an equal number of samples in each
megabatch, (2) for each megabatch $\mathcal{M_{T}}\in S_{B}$, we partition it
into a train set comprising 90% samples in $\mathcal{M}_{t}$ and a validation
set of the remaining 10% samples in $\mathcal{M}_{t}$, (3) from each megabatch
we randomly extract 20% of the training data to build the set $|\pi_{t}|$ used
for pruning via SNIP, and (4) we create the training pipeline where the
learner is pruned using $\pi_{t}$ and subsequently trained on the megabatch at
the current state for $k$ iterations. We keep a separate held-out test set,
which is not seen by the learner during training, but is used to evaluate the
model’s performance after completion of training on each megabatch.

#### Models

For our experiments, we use mainly four standard vision classifiers: (a)
ResNet-18 He et al. (2016), (b) ResNet-50 He et al. (2016), (c) VGG-16 (with
Batch Normalization) Simonyan and Zisserman (2014), and (d) Wide ResNet-50
Zagoruyko and Komodakis (2016). We specifically picked these models because of
their popularity in standard computer vision tasks and the extensiveness of
the studies conducted on these models for various learning paradigms. However,
for long sequence-based ALMA (high number of megabatches) and Restricted
ImageNet experiments, we only use ResNet-50 as the model of choice. In
addition, all models were trained from scratch and no pre-training was used.

#### Hyperparameters and learning setup

Here, we describe in detail the experimental setups that were used for the
reported results and discuss the difference in performance between APP,
Anytime OSP, and baseline models in different scenarios. As mentioned above,
for the experimental evaluation, we focus primarily on the task of image
classification using the models defined in Subsection 4. For all experiments
excluding a single VGG-16 + BN ablation study, we used a fixed target sparsity
$\tau=4.5$, which means, for all APP and Anytime OSP-based results, the model
was pruned to have only 36.63% remaining weights compared to the initial dense
baseline network which corresponds to $\approx\frac{1}{3}$rd model capacity
post pruning. We hardcoded $\tau$ to 4.5, as we observe an inconsistency in
performance for APP models at higher levels of sparsity, as reported in Table
2.

We use the following two learning setups for our empirical validation.

  1. 1.

SGD with multi-step decay at $\mathcal{M}_{1}$ only: All the results reported
in Table 2 were trained using Stochastic Gradient Descent (SGD) with a
momentum of $0.9$ and initial learning rate 0.1, along with multi-step decay
of learning rate by $\gamma=0.1$ at the 91st and the 136th epoch only for the
first megabatch ($\mathcal{M}_{1}$). For all subsequent megabatches
$\mathcal{M}_{2}...\mathcal{M}_{t}$, a constant learning rate of 0.001 was
maintained. Each megabatch was trained for $182$ epochs except the
$|S_{B}|=25$ run reported in Table 5.

  2. 2.

SGD with cyclic multi-step decay at every $\mathcal{M}_{t}$: All the results
in Table 4 (excluding the results highlighted in light yellow), 6 and 7 were
trained using SGD with the same initial parameters as described above.
However, after completion of training on each megabatch $\mathcal{M}_{t}$, the
learning rate was reset back to it’s initial state of $0.1$.

While we tested various pruning algorithms for the APP and Anytime OSP models
such as SNIP Lee et al. (2018), magnitude pruning, random pruning, IMP Frankle
and Carbin (2018), and GraSP Wang et al. (2020b), we use SNIP by default
because we observe higher stability and training performance when coupled with
APP. We use the default parameters for the pruning algorithms specified above
and provide additional details in the supplementary section.

###  4.1 Results

####  4.1.1 Ablation study with CIFAR-10 ALMA

We conducted initial experiments to validate the design choice used in the
default version of APP for all experiments conducted in this research. We used
the following different versions of APP for the experiment:

Note: All experiments were carried out using a ResNet-50 backbone on CIFAR-10
using a fixed target sparsity of $\tau=4.5$ with a total of 8 megabatches
consisting of each 6250 samples. Furthermore, all reported results were
obtained with a cyclic learning rate policy only for the first mega-batch
$\mathcal{M}_{1}$, and subsequent mega-batches had a fixed learning rate.

  1. 1.

APP Default: This is the default version of APP adopted throughout all
experiments in this manuscript. The exact algorithm is defined in Section 3.

  2. 2.

APP + WD (1e-4): This version of APP follows the same algorithm as that of the
default, however, adds a weight decay of 1e-4 to the weight updates at each
iteration.

  3. 3.

APP Final: In this version of APP, we apply the pruning at the end of each
megabatch training contrary to the default version where we prune the model at
the start of each megabatch.

  4. 4.

APP Warmup: In this version of APP, we apply the pruning after a few warm-up
epochs (20) at each megabatch contrary to the default version where we prune
the model at the start of each megabatch.

  5. 5.

APP no replay SNIP: In this version of APP, we construct the subset $\pi_{t}$
used by SNIP for pruning only from the current megabatch $\mathcal{M}_{t}$ and
do not include any samples from the megabatches in the replay buffer
$\mathcal{M}_{1}....\ \mathcal{M}_{t-1}$.

Figure 3: From left to right: (a) Generalization gap for various versions of
APP. (b) Validation loss for various versions of APP.

As shown in Table 1, APP + WD (1e-4) obtains the highest test accuracy, while
APP warm-up has the lowest generalization gap compared to the default version
of APP. However, we do not use weight decay by default due to inconsistent
results across various models and settings. While APP warm-up provides a drop
of the generalization gap by a margin of $2.64\%$ compared to APP default, we
do not use it as default due to the reduction in test accuracy by a margin of
$1.8\%$ compared to APP default, and additionally the training of the same was
extremely unstable, as shown in Fig. 3. Furthermore, we note that the training
collapses when used with APP Final version, while for the case of APP no-
replay SNIP, we observe a drop in both the test accuracy and the
generalization gap compared to APP default.

Table 1: Ablation study for the choice of APP design.

Method | Test Accuracy($\uparrow$) | Generalisation Gap($\downarrow$)
---|---|---
APP Default | 84.65% | 11.816%
APP + WD (1e-4) |  85.6%(+0.95 %) | 12.336%(+0.52 %)
APP Final | 37.2% | 65.333%†
APP Warm-up | 82.85%(-1.8 %) |  9.176%(-2.64 %)
APP no replay SNIP | 83.35%(-1.3 %) | 11.976%(+0.16 %)

####  4.1.2 Analysis of short sequence ALMA ($|S_{B}|=8$)

We start by analyzing the results reported in Table 2. All experiments were
conducted using full replay
($\mathcal{M}_{t}\leftarrow\bigcup\limits_{i=1}^{t}\mathcal{M}_{i}$) for a
total of 8 megabatches ($|S_{B}|=8$) with each megabatch containing
$|\mathcal{M}_{t}|=6250$ samples.

For ResNet-18 trained on C-10, we observe that APP (SNIP) decreases the test
accuracy by $0.68\%$ and decreases the generalization gap by $6.718\%$
compared to the baseline model. Although the Anytime OSP (SNIP) model
outperforms APP (SNIP) by a small margin of $0.21\%$, the former has a
significantly higher generalization gap compared to the latter by $6.867\%$.
For C-100, we observed a strong improvement in APP (SNIP) in test accuracy
compared to the baseline by a margin of $3.85\%$, while the generalization gap
was drastically reduced by $30.187\%$. Similar improvements were observed for
the CER metric as reported in the table, and the improvements were consistent
when using magnitude-based pruning for APP.

For ResNet-50, we observed an even greater performance improvement for APP
(SNIP) compared to the baseline and Anytime OSP models in all metrics: test
accuracy, CER, and generalization gap. For example, in C-10, the use of APP
(SNIP) improved the test accuracy by $5.46\%$, decreased the CER by $1278$,
and decreased the generalization gap by $7.393\%$ while the use of Anytime OSP
(SNIP) resulted in a decrease in the test accuracy by $3.1\%$, an increase in
the CER by $4268$, and an increase in the generalization gap by $3.11\%$
compared to the baseline model. We observed for C-10 that the use of APP
(SNIP) with a small weight decay of $1e-4$ results in an improvement of test
accuracy by $0.95\%$ compared to the version without weight decay. However, we
did not conduct extensive studies to validate the improvement caused by weight
decay, as it is beyond the scope of our experimental evaluation. We observe a
similar improvement in performance from baseline when coupled with weight
decay.

The improvement in performance is also observed in Wide ResNet-50 where for
C-10, APP (SNIP) outperforms the baseline model in test accuracy by $11.04\%$,
reduces CER by $6095$ and reduces the generalization gap by $12.007\%$.
However, for VGG-16 with batch normalization, we did not observe a significant
improvement in performance over the baseline model compared to its Anytime OSP
counterpart.

For all experiments, we observed strong results for APP when used with SNIP
and magnitude-based pruning. In our observations, while Anytime OSP is stable
and compatible with other pruning methods such as random pruning and GraSP,
APP causes a significant loss in performance when used with the same. This is
the reason why we chose to fix SNIP as the pruner of choice for APP. We
observe that APP with random pruning and GraSP continues to perform at par
with its SNIP and magnitude-based pruning counterparts for the initial
megabatches, but with increasing sparsity, causes a detrimental effect on the
accuracy curves, as shown in Fig. 6(a). Furthermore, for VGG-16 with batch
normalization, we conducted an experiment to study the effect of high sparsity
for C-10 training where we set $\tau=13$, which implies that the model had
$\approx 5.5\%$ remaining parameters after pruning. However, we observed that
APP causes a significant reduction in performance at this high level of
sparsity.

Table 2: Results on ALMA of C-10 and C-100. $\dagger$ denotes unstable
training. WD denotes a weight decay of 1e-4 being used during the training.

Backbone | Method | Pruner |  $|\theta|$($\downarrow$) | Test Accuracy($\uparrow$) | CER($\downarrow$) | Generalization Gap($\downarrow$)
---|---|---|---|---|---|---
|  |  |  | CIFAR-10 | CIFAR-100 | CIFAR-10 | CIFAR-100 | CIFAR-10 | CIFAR-100
ResNet-18 | Baseline | - | 11.51 M | 86.37% | 54.44% | 14618 | 42535 | 13.64% | 47.08%
- | Baseline (WD) | - | 11.51 M |  88.75%(+2.38 %) | 55.2(+0.76 %) | 11840(-2778) | 42269 (-266) | 11.0%(-2.64 %) | 46.553%(-0.527 %)
- | Anytime OSP | SNIP Lee et al. (2018) | 4.09 M |  85.9%(-0.47 %) | 54.09%(-0.35 %) | 14276 (-342) | 42785 (+250) | 13.789%(+0.149 %) | 47.753%(+0.673 %)
- | APP | SNIP Lee et al. (2018) | 4.09 M | 85.69%(-0.68 %) |  58.29%(+3.85 %) |  13476 (-1142) |  42442 (-93) |  6.922%(-6.718 %) |  16.893%(-30.187 %)
- | Anytime OSP | Magnitude | 4.09 M |  86.2%(-0.17 %) | 54.06(-0.38 %) |  14486 (132) | 42090 (-445) | 13.611%(-0.029 %) | 47.94%(+0.86 %)
- | APP | Magnitude | 4.09 M | 85.58%(-0.79 %) |  58.07%(+3.63 %) | 16109 (+1491) |  41966 (-569) |  10.76%(-2.88 %) |  22.676%(-24.404 %)
ResNet-50 | Baseline | - | 23.5 M | 79.19% | 44.6% | 19221 | 49241 | 19.209% | 56.631%
- | Baseline (WD) | - | 23.5 M |  83.15 %(+3.96 %) | 44.66%(+0.06 %) | 18143 (-1078) | 49879 (+638) | 16.991%(-2.218 %) | 57.233%(+0.602 %)
- | Anytime OSP | SNIP Lee et al. (2018) | 8.6 M | 76.09%(-3.1 %) | 41.07%(-3.53 %) | 23489 (+4268) | 51829 (+2588) | 22.32%(+3.11 %) | 59.853%(+3.222 %)
- | APP | SNIP Lee et al. (2018) | 8.6 M |  84.65%(+5.46 %) |  52.01%(+7.41 %) | 17943 (-1278) |  48164 (-1077) |  11.816%(-7.393 %) |  23.002%(-33.629 %)
- | APP (WD) | SNIP Lee et al. (2018) | 8.6 M |  85.6%(+6.41 %) | - |  | - | 12.336%(-6.873 %) | -
- | Anytime OSP | Magnitude | 8.6 M | 78%(-1.19 %) | 45.06%(+0.46 %) | 21365 (+2144) | 48859 (-382) | 19.83%(+0.621 %) | 56.356%(-0.275 %)
- | APP | Magnitude | 8.6 M |  83.63%(+4.44 %) |  51.94%(+7.34 %) | 19078 (-143) |  48032 (-1209) |  6.913%(-12.296 %) |  22.871%(-33.76 %)
- | Anytime OSP | IMP | 8.6 M | 78.99%(-0.2 %) | - | - | - | 20.227%(+1.018 %) | -
- | APP | IMP | 8.6 M |  83.63%(+4.44 %) | - | - | - |  6.913%(-12.296 %) | -
- | Anytime OSP | Random | 8.6 M |  75.59%(-3.6 %) |  47.07%(+2.47 %) | 23745 (+4524) |  47646 (-1595) | 23.333%(+4.124 %) |  54.787%(-1.844 %)
- | APP | Random | 8.6 M | 62.63%(-16.56 %) | ${1.67\%}^{\dagger}$ | 24390 (+5169) | 55163 (+5922) | ${7.373\%}^{\dagger}$ | ${35.004\%}^{\dagger}$
- | Anytime OSP | GraSP Wang et al. (2020b) | 8.6 M |  83.26%(+4.07 %) |  46.06%(+1.46 %) | 17442 (-1779) |  49244 (+3) |  16.862%(-2.347 %) |  55.52%(-1.111 %)
- | APP | GraSP Wang et al. (2020b) | 8.6 M | $10.0\%^{\dagger}$ | $2.04\%^{\dagger}$ | 33415 (+14194) | 56254 (+7013) | ${0.1556\%}^{\dagger}$ | ${35.582\%}^{\dagger}$
Wide ResNet-50-2 | Baseline | - | 68.9 M | 74.45% | 47.42% | 25299 | 47273 | 24.796% | 53.996%
- | Baseline (WD) | - | 68.9 M | 84.28%(+9.83 %) | 51.31%(+3.89 %) | 17782 (-7517) | 45232 (-2041) | 14.578%(-10.218 %) | 50.718%(-3.278 %)
- | Anytime OSP | SNIP Lee et al. (2018) | 25.2 M | 79.33%(+4.88 %) |  49.22%(+1.8 %) | 19815 (-5484) |  46052 (-1221) | 19.724%(-5.072 %) | 53.096%(-0.9 %)
- | APP | SNIP Lee et al. (2018) | 25.2 M |  85.49%(+11.04 %) | 48.18%(+0.76 %) |  19204 (-6095) | 48579 (+1306) |  12.789%(-12.007 %) |  38.64%(-15.356 %)
- | Anytime OSP | Magnitude | 25.2 M | 76.05%(+1.6 %) | 49.48%(+2.06 %) | 23900 (-1399) |  46174 (-1099) | 22.409%(-2.387 %) | 52.538%(-1.458 %)
- | APP | Magnitude | 25.2 M |  85.28%(+10.83 %) |  54.42%(+7.0 %) |  18675 (-6624) | 46697 (-576) |  12.291%(-12.545 %) |  43.096%(-10.9 %)
- | Anytime OSP | Random | 25.2 M |  81.43%(+6.98 %) |  44.5%(-2.92 %) |  18567 (-6732) | 49195 (+1922) |  18.396%(-6.4 %) |  57.393%(+3.397 %)
- | APP | Random | 25.2 M | 53.94%(-20.51 %) | 39.45%(-7.97 %) | 25673 (-374) |  48929 (+1656) | ${67.84\%}^{\dagger}$ | ${17.324\%}^{\dagger}$
- | Anytime OSP | GraSP Wang et al. (2020b) | 25.2 M |  81.49%(+7.04 %) |  48.54%(+1.12 %) |  18452 (-6847) | - |  17.311%(-7.485 %) | 53.902%(-0.094 %)
- | APP | GraSP Wang et al. (2020b) | 25.2 M | ${10.78\%}^{\dagger}$ | 26.27(-21.15 %) | 29621 (+4322) | 55129 (+7856) | ${63.273\%}^{\dagger}$ | ${41.589\%}^{\dagger}$
VGG-16-BN | Baseline | - | 138.42 M | 87.57% | 53.52% | 12412 | 42410 | 11.747% | 48.329%
- | Baseline (WD) | - | 138.42 M |  88.29%(+0.72 %) | 54.85%(+1.33 %) |  11828 (-584) | 41122 (-1288) | 11.451%(-0.296 %) | 45.767%(-2.568 %)
- | Anytime OSP | SNIP Lee et al. (2018) | 50.6 M |  87.59%(+0.02 %) | 52.51%(-1.01 %) |  12374 (-38) | 42575 (+165) | 12.24%(+0.493 %) | 47.811%(-0.518 %)
- | APP | SNIP Lee et al. (2018) | 50.6 M | 86.76%(-0.81 %) |  55.31%(+1.79 %) | 12782 (+370) |  41285 (-1125) |  10.113%(-1.634 %) |  30.942%(-17.387 %)
- | Anytime OSP | SNIP Lee et al. (2018) | 7.61 M |  86.75%(-0.82 %) | - |  13141 (+729) | - | 11.067%(-0.68 %) | -
- | APP | SNIP Lee et al. (2018) | 7.61 M | 59.5%(-28.07 %) | - | 20073 (+7661) | - | $-0.9733\%^{\dagger}$ | -
- | Anytime OSP | Magnitude | 50.6 M |  87.33%(-0.24 %) | 53.27%(-0.25 %) |  12551 (+139) |  42306 (-104) | 12.476%(+0.729 %) | 47.996%(-0.333 %)
- | APP | Magnitude | 50.6 M | 86.04%(-1.57 %) |  54.59%(+1.07 %) | 12943 (+531) | 42310 (-100) | 9.862%(-1.885 %) |  22.369%(-25.96 %)
- | Anytime OSP | Random | 50.6 M |  87.49%(-0.08 %) |  53.82%(+0.3 %) |  12539 (+127) |  41739 (-671) |  12.533%(+0.786 %) |  46.669%(-1.66 %)
- | APP | Random | 50.6 M | 68.56%(-19.01 %) | 35.01%(-18.51 %) | 16760 (+4348) | 46427 (+4017) | ${3.258\%}^{\dagger}$ | ${42.362\%}^{\dagger}$
- | Anytime OSP | GraSP Wang et al. (2020b) | 50.6 M |  87.04%(-0.53 %) |  54.55%(+1.03 %) |  12945 (+533) |  41449 (-961) | 13.476%(+1.729 %) |  47.189%(-1.14 %)
- | APP | GraSP Wang et al. (2020b) | 50.6 M | ${14.57\%}^{\dagger}$ | ${26.27\%}^{\dagger}$ | 24131 (+11719) | 48888 (+6478) | ${56.624\%}^{\dagger}$ | ${41.589\%}^{\dagger}$

Compared to the results reported in Table 2, we observe in Table 3 that using
the cyclic learning rate policy at each megabatch $\mathcal{M}_{t}$
significantly improves performance for the three models, baseline, Anytime OSP
and APP. For example, for ResNet-50, we note an improvement in test accuracy
for the baseline model by a margin of $6.51\%$ compared to the baseline model
trained with the cyclic learning rate policy only for the first megabatch
$\mathcal{M}_{1}$ as reported in Table 2. APP consistently outperforms the
baseline and anytime OSP models for each experiment conducted on CIFAR-100
with a significant drop in the generalization gap observed for the four
backbones used.

Table 3: Results on anytime learning of CIFAR-10 and CIFAR-100 using 8 mega-
batches with 6250 samples per mega-batch with replay. All APP and Anytime OSP
experiments used Snip Lee et al. (2018) as the pruner of choice. All
experiments also used an SGD + cyclic multistep decay LR at every
$\mathcal{M}_{t}$.

Backbone | Method |  $|\theta|$($\downarrow$) | Test Accuracy($\uparrow$) | CER($\downarrow$) | Generalisation Gap($\downarrow$)
---|---|---|---|---|---
|  |  | CIFAR-10 | CIFAR-100 | CIFAR-10 | CIFAR-100 | CIFAR-10 | CIFAR-100
ResNet-18 | Baseline | 11.51 M | 91.43% | 60.39% | 10545 | 38771 | 8.098% | 41.033%
- | Anytime OSP | 4.09 M | 90.56%(-0.87 %) | 60.44%(+0.05 %) | 11255 (+710) | 38755 (-16) | 8.778%(+0.68 %) | 40.567%(-0.472 %)
- | APP | 4.09 M | 90.06%(-1.37 %) |  63.61%(+3.22 %) |  10419 (-126) |  37048 (-1723) | 8.442%(+0.344 %) |  26.922%(-14.111 %)
ResNet-50 | Baseline | 23.5 M | 85.7% | 46.91% | 16821 | 49486 | 14.289% | 54.878%
- | Anytime OSP | 8.6 M | 88.61%(+2.91 %) | 53.76%(+6.85 %) | 14209 (-2612) | 45092 (-4394) | 11.336%(-2.953 %) | 49.182%(-5696 %)
- | APP | 8.6 M |  90.89%(+5.19 %) |  64.88%(+17.97 %) |  12294 (-4527) |  39559 (-9927) |  9.24%(-5.049 %) |  34.387%(-20.491 %)
Wide ResNet-50-2 | Baseline | 68.9 M | 89.65% | 52.73% | 13471 | 44866 | 10.398% | 49.931%
- | Anytime OSP | 25.2 M | 87.5%(-2.15 %) | 48.05%(-4.68 %) | 15717 (+2246) | 48978 (+4112) | 12.109% (+1.711 %) | 53.64%(+3.709 %)
- | APP | 25.2 M |  92.02%(+2.37 %) |  66.24%(+13.51 %) |  12808 (-663) |  40327 (-4539) |  7.976%(-2.422 %) |  34.791%(-15.14 %)
VGG-16-BN | Baseline | 138.42 M | 91.53% | 59.06% | 9950 | 38615 | 9.318% | 42.667%
- | Anytime OSP | 50.6 M | 90.63%(-0.9 %) | 57.98%(-1.08 %) | 10236 (+286) | 39024 (+409) | 9.187%(-0.131 %) | 43.102%(+0.435 %)
- | APP | 50.6 M | 89.82%(-1.71 %) |  62.51%(+3.45 %) | 10171 (+221) |  36831 (-1784) |  8.967%(-0.351 %) |  33.293%(-9.374 %)

Table 4: Results on ALMA of C-10 and C-100 without replay using SGD with
cyclic multi-step decay at every $\mathcal{M}_{t}$. Rows highlighted in light
yellow represent runs done with SGD with multistep decay at $\mathcal{M}_{1}$
only.

Backbone | Method | Pruner |  $|\theta|$($\downarrow$) | Test Accuracy($\uparrow$) | CER($\downarrow$) | Generalization Gap($\downarrow$)
---|---|---|---|---|---|---
|  |  |  | CIFAR-10 | CIFAR-100 | CIFAR-10 | CIFAR-100 | CIFAR-10 | CIFAR-100
ResNet-18 | Baseline | - | 11.51 M | 87.42% | 53.4% | 12834 | 41919 | 13.76% | 45.44%
- | Anytime OSP | SNIP Lee et al. (2018) | 4.09 M |  87.72%(+0.3 %) |  54.32%(+0.92 %) | 13130 (+296) | 41989 (+70) |  13.28%(-0.48 %) | 47.36%(+1.92 %)
- | APP | SNIP Lee et al. (2018) | 4.09 M | 80.4%(-7.02 %) | 41.59%(-11.81 %) | 13939 (+1105) | 45885 (+3966) | 20.036%(+6.276 %) | 56.16%(+10.72 %)
ResNet-50 | Baseline | - | 23.5 M | 80.08% | 42.06% | 21436 | 51866 | 20.64% | 58.56%
- | Anytime OSP | SNIP Lee et al. (2018) | 8.6 M |  83.95%(+3.87 %) |  46.18%(+4.12 %) | 17521 (-3915) |  49083 (-2783) | 16.942%(-3.698 %) | 56.64%(-1.92 %)
- | APP | SNIP Lee et al. (2018) | 8.6 M | 80.86%(+0.78 %) |  36.78%(-5.28 %) |  17073 (-4363) | 51068 (-798) |  20.462%(-0.178 %) |  64.213%(+5.653 %)
ResNet-50 | Baseline | - | 23.5 M | 69.95% | 41.65% | 25744 | 50303 | 24.213% | 57.76%
- | Baseline (WD) | - | 23.5 M | 78.05%(+8.1 %) | 41.14%(-0.51 %) | 19925 (-5819) | 52049 (+1746) | 23.822%(-0.391 %) | 63.769%(+6.009 %)
- | Anytime OSP | SNIP Lee et al. (2018) | 8.6 M | 71.18%(+1.22 %) | 38.5(-3.15 %) | 25452 (-292) | 52953 (+2650) | 25.084%(+0.871 %) | 56.836%(-0.924 %)
- | APP | SNIP Lee et al. (2018) | 8.6 M | 67.69%(-2.26 %) | 21.12%(-20.53 %) | 23568 (-2176) | 59042 (+8739) | 31.236%(+7.023 %) | 52.356%(-5.404 %)
- | Anytime OSP | Magnitude | 8.6 M | 74.48%(+4.53 %) | 41.85%(+0.2 %) | 22922 (-2822) | 50932 (+629) | 25.689%(+1.559 %) | 58.827%(+1.067 %)
- | APP | Magnitude | 8.6 M | 61.31%(-8.64 %) | 20.96%(-20.69 %) | 28152 (+2408) | 59246 (+8943) | 13.351%(-10.862 %) | 33.956%(-23.804 %)
- | Anytime OSP | Random | 8.6 M | 70.66%(+0.71 %) | 44.08%(+2.43 %) | 25828 (+84) | 49006 (-1297) | 25.778%(+1.565 %) | 57.618%(-0.142 %)
- | APP | Random | 8.6 M | 28.01%(-41.94 %) | $1\%^{\dagger}$ | 36044 (+10300) | 62683 (+12380) | ${37.742\%}^{\dagger}$ | ${25.813\%}^{\dagger}$
- | Anytime OSP | GraSP Wang et al. (2020b) | 8.6 M | 80.14%(+10.19 %) | 41.56%(-0.09 %) | 18697 (7047) | 50867 (+564) | 19.876%(-4.337 %) | 53.564%(-4.196 %)
- | APP | GraSP Wang et al. (2020b) | 8.6 M | $10.0\%^{\dagger}$ | $3.51\%^{\dagger}$ | 41747 (+16003) | 62672 (+12369) | ${40.8\%}^{\dagger}$ | ${39.378\%}^{\dagger}$
Wide ResNet-50-2 | - | Baseline | 68.9 M | 84.08% | 47.17% | 17484 | 47725 | 16.8% | 53.44%
- | Anytime OSP | SNIP Lee et al. (2018) | 25.2 M | 81.43%(-2.65 %) | 42.58%(-4.59 %) | 18715 (+1231) | 52184 (+4459) | 18.382% (+1.582 %) | 57.28%(+3.84 %)
- | APP | SNIP Lee et al. (2018) | 25.2 M | 81.46%(-2.62 %) | 35.49%(-11.68%) | 18222 (+738) | 51062(+3337) | 18.72%(+1.92 %) | 64.587%(+11.147 %)
VGG-16-BN | Baseline | - | 138.42 M | 88.1% | 52.24% | 11796 | 41873 | 15.022% | 48%
- | Anytime OSP | SNIP Lee et al. (2018) | 50.6 M | 88.01%(-0.09 %) | 50.63%(-1.61 %) | 11874 (+78) | 42660 (+787) |  13.084%(-1.938 %) | 52.16%(+4.16 %)
- | APP | SNIP Lee et al. (2018) | 50.6 M | 81.74%(-6.36 %) | 41.62%(-10.62 %) | 13598 (+1802) | 44935 (+3062) | 19.449%(+4.427 %) | 61.991%(+13.991 %)

In Table 4, we conducted experiments to validate the effect of no replay for
APP, Anytime OSP, and the baseline models for different backbones. From the
experiments, we can conclude with high certainty that APP requires full replay
of megabatches to provide a performance improvement. As shown in the table, we
see that APP models cause a significant decrease in performance, while Anytime
OSP models improve performance compared to their baseline counterparts. We
hypothesize that the loss in performance is induced by the model restructuring
caused by pruning at the start of each megabatch, which can be attributed to
the loss in knowledge transfer while transitioning from one megabatch to the
next.

####  4.1.3 Analysis of moderate and long sequence ALMA ($|S_{B}|=25,50,100$)

For validation on variation of $|S_{B}|$, we conducted experiments using only
the ResNet-50 model with full replay and with SNIP as the pruner of choice for
both APP and Anytime OSP variants as reported in Table 5. Similarly to short-
sequence-based ALMA, we observed a strong improvement in performance while
using APP compared to the Anytime OSP and baseline models. In particular, when
$|S_{B}|=100$, where each megabatch has $|\mathcal{M}_{t}|=500$ samples, we
report an improvement in CER by 105277 compared to the baseline model, which
is equivalent to APP correctly classifying the test set $T_{x,y}$ of 10,000
samples 10 times compared to the baseline model throughout the training
process on the complete stream $|S_{B}|$. Interestingly, we find that the
performance of the baseline has a high variation caused by the change in
$|S_{B}|$ with a deviation in test accuracy of $\sigma=4.345\%$ while APP is
extremely stable and is less sensitive to the change in $|S_{B}|$ with a
deviation in test accuracy of $\sigma=1.743\%$ across $|S_{B}|$ values of 8,
25, 50 and 100. We further analyze and investigate the training dynamics
observed during training moderate- and long-sequence ALMA, which we discuss in
detail in Section 4.2.

Table 5: Results of ALMA training of C-10 models with varying $|S_{B}|$.

Backbone | Method | Pruner |  $|\theta|$($\downarrow$) | $|S_{B}|$ | $|\mathcal{M}_{t}|$ | Test Accuracy($\uparrow$) | CER ($\downarrow$) | Generalization Gap($\downarrow$)
---|---|---|---|---|---|---|---|---
ResNet-50 | Baseline | - | 23.5 M | 25 | 2000 | 82.69% | 118876 | 9.978%
- | Anytime OSP | SNIP Lee et al. (2018) | 8.6 M | 25 | 2000 | 78.86%(-3.83 %) | 110698 (-8178) | 16.284%(+6.306 %)
- | APP | SNIP Lee et al. (2018) | 8.6 M | 25 | 2000 | 79.73%(-2.96 %) |  104435 (-14441) |  2.916%(-7.062 %)
ResNet-50 | Baseline | - | 23.5 M | 50 | 1000 | 79.13% | 193384 | 20.971%
- | Anytime OSP | SNIP Lee et al. (2018) | 8.6 M | 50 | 1000 | 72.91%(-6.22 %) | 202212 (+8828) | 26.56%(-2.411 %)
- | APP | SNIP Lee et al. (2018) | 8.6 M | 50 | 1000 |  82.0%(+2.87 %) |  163503 (-29881) |  14.707%(-6.264 %)
ResNet-50 | Baseline | - | 23.5 M | 100 | 500 | 70.87% | 396572 | 28.971%
- | Anytime OSP | SNIP Lee et al. (2018) | 8.6 M | 100 | 500 | 78.51%(+7.64 %) | 315349 (-81223) | 20.133%(-8.838 %)
- | APP | SNIP Lee et al. (2018) | 8.6 M | 100 | 500 |  82.32%(+11.45 %) |  291295 (-105277) |  16.502%(-12.469 %)

####  4.1.4 Few shot experiments on Restricted ImageNet

Figure 4: Error rates on the test set of the trained model at each megabatch
$\mathcal{M}_{t}$ for Restricted Imagenet experiments reported in Table 6.
Figure 5: CER of the trained model at each megabatch $\mathcal{M}_{t}$ for
Restricted Imagenet experiments reported in Table 6.

In this section, we investigate the performance of APP compared to Anytime OSP
and the baseline models on Restricted Balanced ImageNet Engstrom et al.
(2019); Tsipras et al. (2018) using various few-shot learning settings. We
primarily conduct experiments using the following two few-shot settings:

  1. 1.

$\alpha=270$: For this, we only keep 270 samples per class in the complete
dataset which essentially totals to 3780 samples for the complete dataset. We
test this using two different number of megabatches $|S_{B}|=30,70$ such that
each megabatch consists of $|\mathcal{M}_{t}|=126,54$ samples respectively.
For $|S_{B}|=30$, we conduct experiments on both the 224 x 224 and 32 x 32
size versions of the dataset. For $|S_{B}|=30$, we reduce the mini-batch size
of each megabatch $\mathcal{M}_{t}$ to 64 while for $|S_{B}|=70$, we reduce it
to 32.

  2. 2.

$\alpha=540$: For this, we only keep 540 samples per class in the complete
dataset which essentially totals to 7560 samples for the complete dataset. We
test this using three different number of megabatches $|S_{B}|=10,30,70$ such
that each megabatch consists of $|\mathcal{M}_{t}|=756,252,108$ samples
respectively. For $|S_{B}|=70$, we reduce the mini-batch size of each
megabatch $\mathcal{M}_{t}$ to 64.

As reported in Table 6, we observe that APP significantly reduces the
generalization gap for each model variant compared to the Anytime OSP and
baseline counterparts. Excluding $\alpha=270$ experiments on the 32 x 32
downsampled version of Restricted ImageNet, we observe a decrease in CER
compared to the baseline model. For example, for $\alpha=270$ with
$|S_{B}|=30$ on the 224 x 224 version of Restricted Imagenet, we observe that
APP reduces the CER by 5846 compared to baseline, which essentially means that
APP correctly classified $\approx 1.5\times$ the test set throughout training
on the full stream $S_{B}$. We also observe strong notable improvements in
test accuracy for anytime OSP models in the $\alpha=270$ setting, where it
records the highest test accuracy in all experiments.

We also visualize and compare the error rate on the test set and CER for each
megabatch for APP, Anytime OSP and baseline models in Fig. 4 and Fig. 5
respectively. We observe that while the final CER for APP with $\alpha=270$
and $|S_{B}|=70$ is higher than the baseline, this is caused by the higher
error rates at the initial megabatches for APP as shown in the fifth subplot
(2nd row, 2nd column) of Fig. 4, while APP at the final megabatches had a
lower error than the baseline. In both figures, we observe that APP
consistently retains both lower error and CER at mostly every megabatch in all
settings reported in Table 6.

Table 6: Results on Few-shot ImageNet Restricted ALMA using SGD with cyclic
multistep decay at every $\mathcal{M}_{t}$.

Method | Resolution | $|\mathcal{M}_{t}|$ | $|S_{B}|$ | $\alpha$ | Test Accuracy($\uparrow$) | CER($\downarrow$) | Generalisation Gap($\downarrow$)
---|---|---|---|---|---|---|---
Baseline | 32 x 32 | 126 | 30 | 270 | 40.811% | 75128 | 55.503%
Anytime OSP | - | - | - | - |  44.55%(+3.739 %) | 76871 (+1743) | 48.53%(-6.973 %)
APP | - | - | - | - | 44.11%(+3.229 %) |  73206 (-1922) |  34.423%(-21.08 %)
Baseline | - | 54 | 70 | 270 | 47.88% | 159204 | 45.03%
Anytime OSP | - | - | - | - |  51.449%(+3.569 %) |  158608 (-596) | 45.357%(+0.327 %)
APP | - | - | - | - | 48.898%(+1.018 %) | 162360 (+3156) |  30.744%(-14.286 %)
Baseline | - | 756 | 10 | 540 | 43.36% | 25328 | 17.394%
Anytime OSP | - | - | - | - |  47.246%(+3.886 %) | 24978 (-350) | 21.529%(+4.135 %)
APP | - | - | - | - | 40.40%(-2.96 %) |  24712 (-616) |  6.963%(-10.431 %)
Baseline | - | 252 | 30 | 540 | 48.03% | 68832 | 48.733%
Anytime OSP | - | - | - | - | 50.23%(+2.2 %) | 68765 (-67) | 45.288%(-3.445 %)
APP | - | - | - | - |  55.04%(+7.01 %) |  66239 (-2593) |  26.388%(-22.345 %)
Baseline | - | 108 | 70 | 540 | 61.391% | 140069 | 34.456%
Anytime OSP | - | - | - | - | 61.391%(0%) |  139152 (-917) | 32.979%(-1.477 %)
APP | - | - | - | - |  62.492%(+1.101 %) | 139963 (-106) |  17.5859%(-16.8701 %)
Baseline | 224 x 224 | 126 | 30 | 270 | 64.289% | 65525 | 32.149%
Anytime OSP | - | - | - | - |  65.623%(+1.334 %) | 61341 (-4184) | 33.435%(+1.286 %)
APP | - | - | - | - | 64.231%(-0.058 %) |  59679 (-5846) |  29.884%(-2.265 %)

####  4.1.5 Analysis of training curves and CER for C-10/100

In Fig 6(b) and Fig 6(c), we start by analyzing the learning curves,
specifically the training accuracy and validation loss curves on C-10 for APP,
Anytime OSP, and baseline models as a function of the total number of training
iterations on the complete stream of megabatches $|S_{B}|$. First, in Fig.
6(b), we observe a distinct oscillation in the training accuracy curve for
APP, which is caused by pruning at the start of training on each new megabatch
$\mathcal{M}_{t}$, resulting in a sharp drop in the initial point accuracy.
Second, we also observe in Fig 6(c), that the validation loss curve for APP
has a negative slope while approaching the completion of training over the
complete stream $S_{B}$, while the curves for Anytime OSP and baseline models
are significantly higher and plateauing, indicating saturation in learning
capacity.

Furthermore, we also visualize the best validation accuracy achieved for APP
with various pruners on a ResNet-50 backbone for C-10,100 with $|S_{B}|=8$ and
$\tau=4.5$. We observe that SNIP and magnitude-based pruning provide
consistent and stable performance improvements over each megabatch in the
stream $S_{B}$, while random pruning and GraSP cause instability and drop
performance by a significant margin during training on the final megabatches
in the stream $S_{B}$. Thus, we set SNIP to be the pruner of choice for APP by
default for all of our experiments.

Finally, we visualize the change in CER during the training for APP (SNIP),
Anytime OSP (SNIP), and baseline using a ResNet-50 on C-10 by varying the
total number of megabatches ($|S_{B}|$) in the stream $S_{B}$. As shown in
Fig. 7, APP (SNIP) consistently maintains a lower CER compared to its Anytime
OSP and baseline counterparts under short ($|S_{B}|=8$), moderate
($|S_{B}|=25$) and long ($|S_{B}|=50$) sequence ALMA.

(a) Best validation accuracy achieved at each $\mathcal{M}_{t}$ for APP with
various pruners on a ResNet-50 backbone for C-10,100 with $|S_{B}|=8$ and
$\tau=4.5$. (b) Comparison of train accuracy curves APP(SNIP), Anytime
OSP(SNIP) and Baseline with a ResNet-50 backbone trained with $|S_{B}|=50$ on
C-10.

(c) Comparison of validation loss curves APP (SNIP), Anytime OSP (SNIP) and
Baseline with a ResNet-50 backbone trained with $|S_{B}|=50$ on C-10. Figure
7: Change in CER during training of APP (SNIP), Anytime OSP (SNIP) and
Baseline using a ResNet-50 on C-10 with varying number of
megabatches($|S_{B}|$). X-axis represents the number of megabatches in the
entire stream $S_{B}$.

####  4.1.6 Restricted ImageNet full ALMA

Finally, we also conducted an experiment on the full Restricted ImageNet
Balanced dataset (32 x 32 downsampled version) using $|S_{B}|=3$ megabatches
with each megabatch containing $\mathcal{M}_{t}=29839$ samples on a ResNet-50
trained using SGD and cyclic multidecay learning rate policy at each megabatch
$\mathcal{M}_{t}$. As reported in Table 7, we observe that both APP and
Anytime OSP models cause a drop in test accuracy and an increase in CER
compared to the baseline model. However, APP reduces the generalization gap by
a margin of $1.845\%$ for $|S_{B}|=3$ and $6.077\%$ for $|S_{B}|=53$ compared
to the baseline.

Table 7: Results on Restricted ImageNet (32 x 32) ALMA using SGD with cyclic
multi-step decay at every $\mathcal{M}_{t}$.

Method | $|\mathcal{M}_{t}|$ | $|S_{B}|$ | Test Accuracy($\uparrow$) | CER($\downarrow$) | Generalisation Gap($\downarrow$)
---|---|---|---|---|---
Baseline | 29839 | 3 | 86.318% | 2046 | 10.792%
Anytime OSP | - | - | 84.55%(-1.768 %) | 2384 (+338) | 10.095%(-0.697 %)
APP | - | - | 84.49%(-1.828 %) | 2310 (+264) |  8.947%(-1.845 %)
Baseline | 1689 | 53 | 86.782% | 44702 | 8.546%
Anytime OSP | - | - | 86.492%(-0.29 %) | 47431 (+2729) | 7.179%(-1.367 %)
APP | - | - | 83.333%(-3.449 %) | 51728 (+7026) |  2.469%(-6.077 %)

###  4.2 Transitions in generalization gap

Figure 8: Generalization gap curves during training of APP (SNIP), Anytime OSP
(SNIP) and Baseline using a ResNet-50 on C-10 with varying number of
megabatches($|S_{B}|$) with full replay. X-axis represents the total number of
training iterations completed throughout the stream $S_{B}$. Figure 9:
Generalization gap curves during training of APP (SNIP), Anytime OSP (SNIP)
and Baseline for the experiments reported in Table 6.

While training the models for empirical validation, we observed a very
interesting trend in the training dynamics, precisely the generalization gap,
in the long-sequence ALMA. As defined in Section 3, the generalization gap is
the difference observed between the training and validation accuracy across
the complete training process over the stream $S_{B}$. The generalization gap
is used to conclude whether a model is overfitting or underfitting, thus
serving as an important criterion for the evaluation of models and
investigating failure modes during model training. Similarly to the results
reported in Nakkiran et al. (2021), we observe a non-monotonic transition in
the generalization gap across APP, Anytime OSP, and baseline models during
long-sequence ALMA training ($|S_{B}|=(50,100)$). In Fig. 8, we observe the
generalization gap as a function of training iterations over the entire stream
$S_{B}$ for APP, Anytime OSP and baseline models using ResNet-50 backbone on
C-10 with various number of megabatches ($|S_{B}|=(8,25,50,100)$). We observe
in both $|S_{B}|=50$ and $|S_{B}|=100$, a nonmonotonic transition in the
generalization gap where the model starts by underfitting, then sharply goes
into the critical regime of overfitting, and subsequently has a gradual
decrease in the generalization gap. We additionally observe that the
generalization gap curve for APP tends to oscillate heavily in the critical
regime, which might be attributed to pruning at the start of the megabatch
under fewer data scenarios. Additionally, we also observe that for
$|S_{B}|=25$, the generalization gap for the Anytime OSP and the baseline
model, rises sharply towards the end of training, while for APP it remains
relatively stable.

We also visualize the generalization gap as a function of training iterations
in Fig. 9 for the experiments reported in Table 6. As demonstrated in Fig. 8,
we observe the same non-monotonic transition in the high number of megabatch
$|S_{B}|=30,70$ settings. In all subplots, it can be seen that APP
consistently maintains a lower generalization gap compared to its Anytime OSP
and baseline counterparts.

###  4.3 Layer-wise Pruning Distribution

In this section, we analyze the distribution of the pruned weights across the
layers when using different pruners of choice for APP. In the experiment, we
only visualize the difference between magnitude-based pruning and SNIP Lee et
al. (2018), since random pruning and GraSP Wang et al. (2020b) lead to
unstable training and therefore do not provide any meaningful insight. For the
backbone, we used a ResNet-50 with an SGD + multidecay learning rate policy
for the first megabatch $\mathcal{M}_{1}$ only. Both models were trained with
full replay for a total of $|S_{B}|=8$ megabatches, each megabatch
$\mathcal{M}_{t}$ having a total of $|\mathcal{M}_{t}|=6250$ samples.

As demonstrated in Fig. 10, we see that magnitude pruning leads to more
weights of the initial layers being pruned at the initial megabatches compared
to SNIP. Shang et al. (2016); Xiao et al. (2021) have demonstrated the
importance of early convolution layers in the performance of deep convolution
neural networks, and it is a well-accepted notion that early convolution
layers are responsible for learning low-level features, such as edges, while
later layers learn high-level features, such as texture. Since magnitude-based
pruning removes a significant amount of early layer weights, this causes a
drop in test accuracy compared to SNIP, which prunes more of the latter layers
at the initial megabatches.

Figure 10: Progressive amount of weights pruned at each megabatch
$\mathcal{M}_{t}$ for ALMA on ResNet-50 with APP for a total of $|S_{B}|=8$
megabatches on the CIFAR-10 dataset with full replay. For the experiment, we
used the SGD + cyclic learning rate policy at only the first megabatch
$\mathcal{M}_{1}$. Bars represent APP with SNIP as the pruner of choice while
Bars represent APP with magnitude pruning. Both pruners were used for the same
target sparsity $\tau=4.5$. In each subplot, each bar corresponds to each
layer of the network, and the y-axis represents the % of the weights pruned
for that layer.

##  5 Reproducibility Statement

To ensure fair and reproducible experiments throughout our work, we enforced
the following measures:

  1. 1.

Use of publicly available open source datasets: As defined in subsection 4,
throughout our research, we do empirical evaluation only using publicly
available datasets - (a) CIFAR-10 Krizhevsky et al. (2009), (b) CIFAR-100
Krizhevsky et al. (2009), and (c) Restricted ImageNet Tsipras et al. (2018).
In our code, we also provide predefined dataloaders and augmentations that
were used to construct the megabatches $\mathcal{M}_{t}$. None of the datasets
used in this work contain sensitive or private information pertaining to an
individual or a single entity against their consent.

  2. 2.

Use of open source frameworks and packages: For all empirical experiments, we
rely on packages and libraries that are accessible and available to the
general audience.

###  5.1 Hardware resources

For all experiments, we primarily used three different hardware
configurations, as listed below:

  1. 1.

1 NVIDIA A100 GPU accelerator with 20 CPUs and 24 GB memory.

  2. 2.

1 NVIDIA V100 GPU accelerator with 20 CPUs and 18 GB memory.

  3. 3.

1 NVIDIA RTX 8000 GPU accelerator with 8,20 CPUs and 12 GB memory.

All CIFAR-10 and CIFAR-100 experiments were conducted using the NVIDIA
RTX-8000 GPU, while the NVIDIA A100 and V100 were only used for the Restricted
ImageNet experiments. Finally, we also used Google Colaboratory for initial
proof-of-concept and ablation experiments.

##  6 Conclusion, Open Questions and Future Work

In this work, we introduced Anytime Progressive Pruning (APP), a novel way to
progressively prune deep networks while training in an ALMA regime. We
improvise on existing pruning at initialization strategies to design APP and
perform an extensive empirical evaluation to validate performance improvement
in various architectures and datasets. We found that pruning deep networks
with APP while training in an ALMA setting causes a significant drop in the
generalization gap compared to one-shot pruning methods and the dense baseline
model.

We conclude this research with the remark that our work serves to lay the
foundation for further exploration into dynamic and progressive pruning in
sequential learning regimes. Although our work provides constructive insights
into the training dynamics of progressive pruning, there are several questions
that we hope can be subsequently explored based on this work, which are as
follows.

  1. 1.

How to control the rate of pruning at each megabatch $\mathcal{M}_{t}$ given
no prior knowledge of the total number of megabatches in the stream $S_{B}$?

  2. 2.

What is the reason behind the non-monotonic transitions observed in the
generalisation gap?

  3. 3.

While we hypothesize that the reason behind the oscillation (drop in test
accuracy at the initial iteration of each megabatch) for APP to be because of
the regularisation effect induced due to the pruning, how can we formally
prove this phenomenon?

  4. 4.

Why does APP not work under no replay settings while Anytime OSP does?

In addition to the above questions, in future work, we aim to further improve
the performance of APP in no-replay settings by designing an optimal framework
for data-constrained progressive pruning. We also aim to improve the
performance of APP for greater target sparsity $\tau$ and simultaneously
perform a hyperparameter search to find the optimal hyperparameters for
progressive pruning using APP. Finally, we also aim to transfer the
progressive pruning setting to other tasks such as object detection and
semantic segmentation.

##  7 Acknowledgements

The authors express their sincere gratitude to Gintare Karolina Dziugaite
(Google Brain) and Himanshu Arora (Workday) for providing valuable initial
feedback in refining the idea, and to Ajay Arasanipalai (UIUC) for helping
with code review and ablation experiments.

## References

  * Aljundi et al. [2017] Rahaf Aljundi, Punarjay Chakravarty, and Tinne Tuytelaars.  Expert gate: Lifelong learning with a network of experts.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 3366–3375, 2017.
  * Baram et al. [2004] Yoram Baram, Ran El Yaniv, and Kobi Luz.  Online choice of active learning algorithms.  _Journal of Machine Learning Research_ , 5(Mar):255–291, 2004.
  * Belouadah and Popescu [2018] Eden Belouadah and Adrian Popescu.  Deesil: Deep-shallow incremental learning.  In _Proceedings of the European Conference on Computer Vision (ECCV)_ , pages 0–0, 2018.
  * Belouadah and Popescu [2019] Eden Belouadah and Adrian Popescu.  Il2m: Class incremental learning with dual memory.  In _The IEEE International Conference on Computer Vision (ICCV)_ , October 2019.
  * Belouadah and Popescu [2020] Eden Belouadah and Adrian Popescu.  Scail: Classifier weights scaling for class incremental learning, 2020\.
  * Ben-David et al. [1997] Shai Ben-David, Eyal Kushilevitz, and Yishay Mansour.  Online learning versus offline learning.  _Machine Learning_ , 29(1):45–63, 1997.
  * Bernhardt et al. [2021] Melanie Bernhardt, Daniel C Castro, Ryutaro Tanno, Anton Schwaighofer, Kerem C Tezcan, Miguel Monteiro, Shruthi Bannur, Matthew Lungren, Aditya Nori, Ben Glocker, et al.  Active label cleaning: improving dataset quality under resource constraints.  _arXiv preprint arXiv:2109.00574_ , 2021.
  * Blalock et al. [2020] Davis Blalock, Jose Javier Gonzalez Ortiz, Jonathan Frankle, and John Guttag.  What is the state of neural network pruning?  _Proceedings of machine learning and systems_ , 2:129–146, 2020.
  * Bottou et al. [1998] Léon Bottou et al.  Online learning and stochastic approximations.  _On-line learning in neural networks_ , 17(9):142, 1998.
  * Buda et al. [2018] Mateusz Buda, Atsuto Maki, and Maciej A Mazurowski.  A systematic study of the class imbalance problem in convolutional neural networks.  _Neural Networks_ , 106:249–259, 2018.
  * Caccia et al. [2021] Lucas Caccia, Jing Xu, Myle Ott, Marc’Aurelio Ranzato, and Ludovic Denoyer.  On anytime learning at macroscale.  _arXiv preprint arXiv:2106.09563_ , 2021.
  * Castro et al. [2018] Francisco M Castro, Manuel J Marín-Jiménez, Nicolás Guil, Cordelia Schmid, and Karteek Alahari.  End-to-end incremental learning.  In _Proceedings of the European Conference on Computer Vision (ECCV)_ , pages 233–248, 2018.
  * Chen et al. [2020] Tianlong Chen, Zhenyu Zhang, Sijia Liu, Shiyu Chang, and Zhangyang Wang.  Long live the lottery: The existence of winning tickets in lifelong learning.  In _International Conference on Learning Representations_ , 2020.
  * Chen et al. [2021] Tianlong Chen, Zhenyu Zhang, Sijia Liu, Shiyu Chang, and Zhangyang Wang.  Long live the lottery: The existence of winning tickets in lifelong learning.  In _International Conference on Learning Representations_ , 2021.  URL https://openreview.net/forum?id=LXMSvPmsm0g.
  * Dimitrakakis and Savu-Krohn [2008] Christos Dimitrakakis and Christian Savu-Krohn.  Cost-minimising strategies for data labelling: optimal stopping and active learning.  In _International Symposium on Foundations of Information and Knowledge Systems_ , pages 96–111. Springer, 2008.
  * Engstrom et al. [2019] Logan Engstrom, Andrew Ilyas, Hadi Salman, Shibani Santurkar, and Dimitris Tsipras.  Robustness (python library), 2019.  URL https://github.com/MadryLab/robustness.
  * Frankle and Carbin [2018] Jonathan Frankle and Michael Carbin.  The lottery ticket hypothesis: Finding sparse, trainable neural networks.  _arXiv preprint arXiv:1803.03635_ , 2018.
  * Frankle et al. [2019a] Jonathan Frankle, Gintare Karolina Dziugaite, and M Daniel.  Roy, and michael carbin. the lottery ticket hypothesis at scale.  _arXiv preprint arXiv:1903.01611_ , 2(3), 2019a.
  * Frankle et al. [2019b] Jonathan Frankle, Gintare Karolina Dziugaite, Daniel M Roy, and Michael Carbin.  Stabilizing the lottery ticket hypothesis.  _arXiv preprint arXiv:1903.01611_ , 2019b.
  * Golkar et al. [2019] Siavash Golkar, Michael Kagan, and Kyunghyun Cho.  Continual learning via neural pruning.  _arXiv preprint arXiv:1903.04476_ , 2019.
  * Grefenstette and Ramsey [1992] John J Grefenstette and Connie Loggia Ramsey.  An approach to anytime learning.  In _Machine Learning Proceedings 1992_ , pages 189–195. Elsevier, 1992.
  * Han et al. [2015a] Song Han, Huizi Mao, and William J Dally.  Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding.  _arXiv preprint arXiv:1510.00149_ , 2015a.
  * Han et al. [2015b] Song Han, Jeff Pool, John Tran, and William Dally.  Learning both weights and connections for efficient neural network.  In _Advances in neural information processing systems_ , pages 1135–1143, 2015b.
  * He et al. [2018] Chen He, Ruiping Wang, Shiguang Shan, and Xilin Chen.  Exemplar-supported generative reproduction for class incremental learning.  In _British Machine Vision Conference_ , 2018.
  * He and Garcia [2009] Haibo He and Edwardo A Garcia.  Learning from imbalanced data.  _IEEE Transactions on knowledge and data engineering_ , 21(9):1263–1284, 2009.
  * He et al. [2016] 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_ , pages 770–778, 2016.
  * He et al. [2017] Yihui He, Xiangyu Zhang, and Jian Sun.  Channel pruning for accelerating very deep neural networks.  In _Proceedings of the IEEE International Conference on Computer Vision_ , pages 1389–1397, 2017.
  * Javed and Shafait [2018] Khurram Javed and Faisal Shafait.  Revisiting distillation and incremental classifier learning.  In _Asian Conference on Computer Vision_ , pages 3–17. Springer, 2018\.
  * Kemker and Kanan [2017] Ronald Kemker and Christopher Kanan.  Fearnet: Brain-inspired model for incremental learning.  _arXiv preprint arXiv:1711.10563_ , 2017.
  * Krizhevsky et al. [2009] Alex Krizhevsky, Geoffrey Hinton, et al.  Learning multiple layers of features from tiny images.  2009\.
  * LeCun et al. [1990] Yann LeCun, John S Denker, and Sara A Solla.  Optimal brain damage.  In _Advances in neural information processing systems_ , pages 598–605, 1990.
  * Lee et al. [2018] Namhoon Lee, Thalaiyasingam Ajanthan, and Philip HS Torr.  Snip: Single-shot network pruning based on connection sensitivity.  _arXiv preprint arXiv:1810.02340_ , 2018.
  * Lee et al. [2019] Namhoon Lee, Thalaiyasingam Ajanthan, and Philip H. S. Torr.  Snip: Single-shot network pruning based on connection sensitivity, 2019\.
  * Li and Hoiem [2017] Zhizhong Li and Derek Hoiem.  Learning without forgetting.  _IEEE transactions on pattern analysis and machine intelligence_ , 40(12):2935–2947, 2017.
  * Liu et al. [2017] Zhuang Liu, Jianguo Li, Zhiqiang Shen, Gao Huang, Shoumeng Yan, and Changshui Zhang.  Learning efficient convolutional networks through network slimming.  In _Proceedings of the IEEE international conference on computer vision_ , pages 2736–2744, 2017.
  * Liu et al. [2021] Zhuoming Liu, Hao Ding, Huaping Zhong, Weijia Li, Jifeng Dai, and Conghui He.  Influence selection for active learning.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV)_ , pages 9274–9283, October 2021.
  * Luo et al. [2017] Jian-Hao Luo, Jianxin Wu, and Weiyao Lin.  Thinet: A filter level pruning method for deep neural network compression.  In _Proceedings of the IEEE international conference on computer vision_ , pages 5058–5066, 2017.
  * Malach et al. [2020] Eran Malach, Gilad Yehudai, Shai Shalev-Schwartz, and Ohad Shamir.  Proving the lottery ticket hypothesis: Pruning is all you need.  In _International Conference on Machine Learning_ , pages 6682–6691. PMLR, 2020.
  * Mallya et al. [2018] Arun Mallya, Dillon Davis, and Svetlana Lazebnik.  Piggyback: Adapting a single network to multiple tasks by learning to mask weights.  In _Proceedings of the European Conference on Computer Vision (ECCV)_ , pages 67–82, 2018.
  * Molchanov et al. [2019] Pavlo Molchanov, Arun Mallya, Stephen Tyree, Iuri Frosio, and Jan Kautz.  Importance estimation for neural network pruning.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 11264–11272, 2019.
  * Nakkiran et al. [2021] Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and Ilya Sutskever.  Deep double descent: Where bigger models and more data hurt.  _Journal of Statistical Mechanics: Theory and Experiment_ , 2021(12):124003, 2021.
  * Olsson [2009] Fredrik Olsson.  A literature survey of active machine learning in the context of natural language processing.  2009\.
  * Pan and Yang [2009] Sinno Jialin Pan and Qiang Yang.  A survey on transfer learning.  _IEEE Transactions on knowledge and data engineering_ , 22(10):1345–1359, 2009.
  * Ramsey and Grefenstette [1994] Connie Loggia Ramsey and John J Grefenstette.  Case-based anytime learning.  In _Case Based Reasoning: Papers from the 1994 Workshop_ , pages 91–95. AAAI Press Menlo Park, California, 1994.
  * Rebuffi et al. [2017] Sylvestre-Alvise Rebuffi, Alexander Kolesnikov, Georg Sperl, and Christoph H Lampert.  icarl: Incremental classifier and representation learning.  In _Proceedings of the IEEE conference on Computer Vision and Pattern Recognition_ , pages 2001–2010, 2017.
  * Rebuffi et al. [2018] Sylvestre-Alvise Rebuffi, Hakan Bilen, and Andrea Vedaldi.  Efficient parametrization of multi-domain deep neural networks.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 8119–8127, 2018.
  * Ring [1998] Mark B Ring.  Child: A first step towards continual learning.  In _Learning to learn_ , pages 261–292. Springer, 1998.
  * Ring et al. [1994] Mark Bishop Ring et al.  Continual learning in reinforcement environments.  1994\.
  * Rosenfeld and Tsotsos [2018] Amir Rosenfeld and John K Tsotsos.  Incremental learning through deep adaptation.  _IEEE transactions on pattern analysis and machine intelligence_ , 2018.
  * Russakovsky et al. [2015] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al.  Imagenet large scale visual recognition challenge.  _International journal of computer vision_ , 115(3):211–252, 2015.
  * Rusu et al. [2016] Andrei A Rusu, Neil C Rabinowitz, Guillaume Desjardins, Hubert Soyer, James Kirkpatrick, Koray Kavukcuoglu, Razvan Pascanu, and Raia Hadsell.  Progressive neural networks.  _arXiv preprint arXiv:1606.04671_ , 2016.
  * Saad [1998] David Saad.  Online algorithms and stochastic approximations.  _Online Learning_ , 5:6–3, 1998.
  * Sahoo et al. [2017] Doyen Sahoo, Quang Pham, Jing Lu, and Steven CH Hoi.  Online deep learning: Learning deep neural networks on the fly.  _arXiv preprint arXiv:1711.03705_ , 2017.
  * Settles [2009] Burr Settles.  Active learning literature survey.  2009\.
  * Settles et al. [2008] Burr Settles, Mark Craven, and Lewis Friedland.  Active learning with real annotation costs.  In _Proceedings of the NIPS workshop on cost-sensitive learning_ , volume 1. Vancouver, CA:, 2008.
  * Shang et al. [2016] Wenling Shang, Kihyuk Sohn, Diogo Almeida, and Honglak Lee.  Understanding and improving convolutional neural networks via concatenated rectified linear units.  In _international conference on machine learning_ , pages 2217–2225. PMLR, 2016.
  * Simonyan and Zisserman [2014] Karen Simonyan and Andrew Zisserman.  Very deep convolutional networks for large-scale image recognition.  _arXiv preprint arXiv:1409.1556_ , 2014.
  * Sokar et al. [2020] Ghada Sokar, Decebal Constantin Mocanu, and Mykola Pechenizkiy.  Spacenet: Make free space for continual learning.  _arXiv preprint arXiv:2007.07617_ , 2020.
  * Tanaka et al. [2020] Hidenori Tanaka, Daniel Kunin, Daniel LK Yamins, and Surya Ganguli.  Pruning neural networks without any data by iteratively conserving synaptic flow.  _arXiv preprint arXiv:2006.05467_ , 2020.
  * Thrun [1995] Sebastian Thrun.  A lifelong learning perspective for mobile robot control.  In _Intelligent robots and systems_ , pages 201–214. Elsevier, 1995\.
  * Thrun [1998] Sebastian Thrun.  Lifelong learning algorithms.  In _Learning to learn_ , pages 181–209. Springer, 1998.
  * Tsipras et al. [2018] Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry.  Robustness may be at odds with accuracy.  _arXiv preprint arXiv:1805.12152_ , 2018.
  * Van de Ven and Tolias [2019] Gido M Van de Ven and Andreas S Tolias.  Three scenarios for continual learning.  _arXiv preprint arXiv:1904.07734_ , 2019.
  * Wang et al. [2020a] Chaoqi Wang, ChaoQi Wang, Guodong Zhang, and Roger B. Grosse.  Picking winning tickets before training by preserving gradient flow.  _ArXiv_ , abs/2002.07376, 2020a.
  * Wang et al. [2020b] Chaoqi Wang, Guodong Zhang, and Roger Grosse.  Picking winning tickets before training by preserving gradient flow.  _arXiv preprint arXiv:2002.07376_ , 2020b.
  * Wang et al. [2021] Huan Wang, Can Qin, Yulun Zhang, and Yun Fu.  Emerging paradigms of neural network pruning.  _arXiv preprint arXiv:2103.06460_ , 2021.
  * Wang et al. [2017] Yu-Xiong Wang, Deva Ramanan, and Martial Hebert.  Growing a brain: Fine-tuning by increasing model capacity.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pages 2471–2480, 2017.
  * Xiao et al. [2021] Tete Xiao, Piotr Dollar, Mannat Singh, Eric Mintun, Trevor Darrell, and Ross Girshick.  Early convolutions help transformers see better.  _Advances in Neural Information Processing Systems_ , 34, 2021.
  * Zagoruyko and Komodakis [2016] Sergey Zagoruyko and Nikos Komodakis.  Wide residual networks.  _arXiv preprint arXiv:1605.07146_ , 2016.
  * Zhang et al. [2018] Tianyun Zhang, Kaiqi Zhang, Shaokai Ye, Jian Tang, Wujie Wen, Xue Lin, Makan Fardad, and Yanzhi Wang.  Adam-admm: A unified, systematic framework of structured weight pruning for dnns.  _arXiv preprint arXiv:1807.11091_ , 2018.
  * Zhou et al. [2016] Hao Zhou, Jose M Alvarez, and Fatih Porikli.  Less is more: Towards compact cnns.  In _European Conference on Computer Vision_ , pages 662–677. Springer, 2016.