Progressive Ensemble Distillation: Building Ensembles for Efficient Inference
Authors: Don Dennis
Abhishek Shetty
Anish Sevekari
Kazuhito Koishida
Virginia Smith
Venue: NeurIPS 2023 poster (2023)
Keywords: Edge computing
compression
efficient inference
distillation and inference
run-time tradeoff
inference-time tradeoff
on-device
user-side
client-side
TL;DR: A method to distill a large pretrained model onto a series on smaller ones that can be used to trade off accuracy for latency at runtime/inference time.

Abstract: Knowledge distillation is commonly used to compress an ensemble of models into a single model. In this work we study the problem of progressive ensemble distillation: Given a large, pretrained teacher model , we seek to decompose the model into an ensemble of smaller, low-inference cost student models . The resulting ensemble allows for flexibly tuning accuracy vs. inference cost, which can be useful for a multitude of applications in efficient inference. Our method, B-DISTIL, uses a boosting procedure that allows function composition based aggregation rules to construct expressive ensembles with similar performance as using much smaller student models. We demonstrate the effectiveness of B-DISTIL by decomposing pretrained models across a variety of image, speech, and sensor datasets. Our method comes with strong theoretical guarantees in terms of convergence as well as generalization.

Progressive Ensemble Distillation: Building Ensembles for Efficient Inference
Don Kurian Dennis Carnegie Mellon University
Abhishek Shetty
Anish Sevekari Carnegie Mellon University
University of California, Berkeley
Kazuhito Koishida
Virginia Smith Carnegie Mellon University
Microsoft
Abstract
We study the problem of progressive ensemble distillation: Given a large, pretrained teacher model g. we seek to decompose the model into smaller, fow-inference cost student models fi, such that progressively evaluating additional models in this ensemble leads to improved predictions. The resulting ensemble allows for flexibly tuning accuracy vs. inference applications in on-device inference. The method we propose, B-DISTIL, relies an algorithmic procedure that uses function composition activations to construct expressive ensembles with similar performance as J. but with smaller student models. We demonstrate the effectiveness of B-DISTIL by decomposing pretrained models across standard image, speech, and sensor datasets. We also provide theoretical guarantees in terms of convergence and generalization.
at runtime, which is useful for number of
intermediate
Introduction
Knowledge distillation aims to transfer the knowledge of a large model into smaller one [ 23 While this technique is commonly used for model compression, one downside is that the procedure fairly resulting in a single compressed model of fixed size. In this work, we instead consider the problem progressive ensemble distillation: approximating a large model via an ensemble of smaller, low-latency models such that such that progressively evaluating additional models in this ensemble leads to improved predictions. The resulting decomposition useful for many applications in on-device and low-latency inference. For example, components of the ensemble can be selectively combined to ficxibly meet accuracy/latency constraints [31] can enable efficient parallel inference execution schemes, and can facilitate early-exit 4 [ anytime inference [36] 28 applications, which are scenarios where inference may be interrupted due to variable resource availability.
More specifically, our work seeks distill large pretrained model, g. onto an ensemble of 'smaller' models, such that eval- uating the first model produces coarse estimate of the prediction (e.g., covering common cases), and evaluating additional models improves this estimate (see Figure Tp. There are major ad- vantages to such ensemble for on-device efficient inference.
Toocker Mocil
Studknn
g
Dudission
m
Figure 1: In progressive ensemble distillation, a large teacher model is distilled into ensemble of low inference cost models. The more student models evaluate, the closer the ensemble's 's decision boundary is the teacher model. Models on previously computed features to reduce overhead and inference cost.
ensemble are allowed depend
Corresponding author: Don Dennis <condennis@cmmu.ddn
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Concretely, (i) inference cost vs. accuracy trade-offss can be controlled on-demand at execution time, (ii) the ensemble can either be executed in parallel or in sequence, or possibly mix of both, and (iii) we can improve upon coarse initial predictions without re-evaluation at runtime.
While traditional distillation methods are effective when transferring information single model of similar capacity, it has been shown that performance can degrade significantly when reducing the capacity of the student model [34] [9]. Moreover, distillation of a deep network onto a weighted sum of shallow networks rarely performs better than distillation onto a single model [.
Our insight in this work is that by composing and reusing activations and by explicitly incentivizing models to be weak learners during distillation, we can successfully find weak learners even when the capacity gap is relatively large. As long as these composition functions are resource-efficien we are able to increase our hypothesis class capacity at roughly the same inference cost as a single model. Moreover, we show that our procedure retains the theoretical guarantees of classical boosting methods (39) Concretely, we make the following contributions:
We formulate progressive ensemble distillation as a two player zero-sum game, derive a weak learning condition for distillation, and present our algorithm, B B-DISTIL, to approximately solve this game. To make the search for weak learnrr in low parameter count models feasible, we solve log-barrier based relaxation of our weak learning condition. By allowing models to reuse computation from select intermediate layers of previously evaluated models of the ensemble, we can increase the model's capacity without significantly increasing inference cost.
We empirically evaluate our algorithm on synthetic and real-world classification tasks from com- puter vision, speech, and sensor processing with models suitable for the respective domains. We show that our ensemble behaves like decomposition, allowing a run-time trade-off between accuracy and computation, while retaining competitive performance with the teacher model.
We provide theoretical guarantees for our algorithm in terms of in-sample convergence and generalization performance. Our framework is not architecture or task specific and can recover existing ensemble models used in efficient inference; we believe our work thus puts forth general lens to view previous work and also to develop new, principled approaches for efficient inference.
2 Background and Related Work
Efficient Inference. Machine learning inference is often resource-constrainge when deployed in practical applications due to memory, energy, cost, latency constraints. This has spurred the development of numerous techniques for efficient inference. Pruning and approximations of pre- trained parameter tensors through low-rank, sparse and quantized representations (22] B [8] 20
have been effective is reducing resource requirements. There are also architecture and task specific techniques for efficient inference [12 45 K
In contrast compressing already trained model, algorithms have also been developed to train compressed models by incorporating resource constraints as part of their training routines 22 77 More recently, algorithms have been developed to search and
find smaller sub-models from a single pre-trained model [46 6).
Knowledge distillation. Knowledge distillation aims to transfer the knowledge of larger model (or model ensemble) to a smaller one [5] 23 Despite its popularity, performing compression via distillation has several known pitfalls. Most notably, it is well-documented that distillation performs poorly when there is a capacity gap, i.e., the teacher is significantly larger than the g
student [34] 19 [. When performing distillation onto a weighted combination of ensembles, it
has been observed that adding additional models into the ensemble does not dramatically improve performance over that of a single distilled model []. There is also lack of theoretical work characterizing when and why distillation is effective for compression (21). Our work aims to address these pitfalls by developing principled approach for progressively distilling a large model onto an ensemble of smaller, low-capacity ones. We defer readers to 21] for a recent survey on varied applications of and approaches for distillation at large.
Early exits and anytime inference. Many applications stand to benefit from the output of progres- sive ensemble distillation, which allows for flexibly tuning accuracy vs. inference cost and executing inference in parallel. Enabling trade-offs between accuracy and inference cost is particularly useful for applications that use early exit or anytime inference schemes. on-device continuous (online) inference settings, early exit models aim to evaluate common cases quickly in order to improve

---

energy efficiency and prolong battery life []] 4.. For instance, a battery powered device contin- uously listening for voice commands can use early exit methods improve battery efficiency by quickly classifying non-command speech. Many early exit methods are also applicable to anytime inference 228 36.. In anytime inference, the aim to produce a prediction even when inference is interrupted, e.g., due to resource contention or scheduler decision. Unlike early exit methods where the classifier chooses when to exit, anytime inference methods have no control over when they are interrupted. We explore the effectiveness of our method, B B-DISTIL, for such applications in Section 5
Two-player games, online optimization and boosting. In this work we formulate progressive ensemble distillation as a two player zero-sum game. The importance of equilibrium of two player zero-sum games have been recognized since the foundational work of von Neumann and Morgen- stern 42 Later applications by Schapire [S] and Freund [15], Freund and Schapire [16] identified close connections between boosting and two-player games. On the basis of this result, number of practical boosting- based learning approaches such as AdaBoost [17], gradient boosting [33), and XGboost 8 have been developed. Boosting has only recently seen success in modern deep learning applications. In particular, Suggala et al. [40] propose generalized boosting framework to train boosting based ensembles of deep networks. Their key insight is that allowing function compositions in feature space can help boost deep neural networks. Although they focus on training and do not produce decompositions of pretrained models, select intermediate layers connections between ensemble components (Section 3.3). A more general application of boosting that is similar our setup is by Trevisan et al. [41] They prove that given target bounded function 9 (e.g,, the teacher model) and class of candidate approximating functions f FF one can iteratively approximate g arbitrarily well with respect F using ideas from online learming and boosting. However, these results depend on the ability to find a function fr in iteration t that leads to at least small constant improvement a round-dependent approximation loss. A key contribution of our work is showing that such functions can be found for the practical application of progressive ensemble distillation by carefully selecting candidate models.
a similar approach in work to
3 Progressive Ensemble Distillation with B-DISTIL
As discussed, our goal in performing progressive ensemble distillation is to approximate large model via an ensemble of smaller, low-latency models so that we can easily trade-off between accuracy and inference-time/lateee at runtime. In this section formalize the problem of progressive ensemble distillation as a two player game and discuss our proposed algorithm, B-DISTIL.
3.1 Problem Formulation
Consider repeated plays of general two player zero-sum game with the pure strategy sets comprising of a hypothesis class FF and a probability distribution P. Given a loss function L, we let the loss (and
reward) of the players be given by F(f.P) p) = [Ex=pp[[[[ [=), and the minimax value of the game is: max min F (f.p).
(1)
pEP JEF
In the context of distillation, given a training set {x.). we can think of the role of the max player in Equation ( as producing distributions over the training set and the role of the min player as producing hypothesis that minimizes the loss on this distribution. In this setting, note that is the product of simplices in N x L dimensions, and
P = {p E R NNL: :Pjj 2 0 Vj EjE,rhs = 1]
(V, (U.)), Eprs Pis (f(aa) -9(x)))))))
Our goal is to produce an ensemble of predictors from the set of hypothesis classes {Fr)) to approximate g 'well'. We now appeal to tools from the framework of stochastic minimax optimization to approximately attain the value in Equation (I) (see Appendix ( for more involved discussion). As is common in this setup, we assume our algorithm is provided access weak gradient vector h such that, when queried at distribution p E P and for 3 > O.
(h. V,F (f.p)) 2 3.
(3)
We perform this construction iteratively by searching for weak learners or weak gradients in the sense of Equation 3 with respect to the target g in the class F... Conditioned on a successful search we can guarantee in-sample convergence to the minimax value in Equation (T) (Theorem [ and bound the excess risk of the ensemble (Theorem 2). Although Equation (3) is a seemingly easier notion than the full optimization, in many problems of interest even this is challenging. In fact, in the multilabel setting that we focus on, one of the main algorithmic challenges is to construct an algorithm that can reliably find low cost weak gradients/learners (see Section 3.3
3

---

Algorithm/ B-DISTIL: Main algorithm
Algorithm FIND-WL
Require: Target 9, rounds T, data {(ri, (
Require:
Probability matrices K+ K
learning rate 7,, model classes {F }m]m m=1
model class F parameterized by θ, hyperparameters for SGD
1: (i,j), K, (i.j) - 2N 2N v(i.j)
2: F.r, < 0, 1,
Obtain {Fr H by expanding F (Sec- tion 3.2).
3: while < R and & < 7 do
4:
ft = FIND-WI. ( K2- Fr)
2: for F (F,) do
5:
if ft is NONE then
6:
r r+r+1
3: Initialize initial parameter Og F".
7:
continue
4: for i {1,..., max-search) do
8:
end if
5: Randomly initialize Sa.-
9:
With 1 = ft 9, update K KT. v(i,j)
6: Run SGD to solve Equation (
(1,5( ( (i, exp( (x;1)))
(4)
7: if fa, is a weak learner then
K Kū (i exp(1) /- ((xx)))
(5)
8: Return fo:
9: end if
10:
Normalize K, K,.. -
F, FU [ft], t
10: end for
12: end while
11:
end for
Return F
Σ Si
12: Return NONE
3.2 B-DISTIL Algorithm
Concretely, at each round I, our proposed algorithm, B-DISTII, maintains matrices K2 E R and K, E RN of probabilities (in our setting, it turns out to be easier to maintain the positive errors
and the negative error separately). Note that the matrices K2 and K, are such that for all j E [L]. Σ, K (6.j)+K, (i. Moreover, for all (i.j) E [N] x [L], S K2 (i. K, (i. S The elements K2 (i, and K; (i,j) can be thought of as the weight on the residual errors f(-((x) gax) and ((x) fe-1(x) respectively, up- up-weigtting large deviations from the teacher model g(z). We formalize our notion weak learners in this setting using Definition [ which can seen as a natural extension of the standard weak learning assumption in the boosting literature.
Definition (Weak learning condition). Given a datasel ((xs, y:)
target function g : X RL and probability matrices Kr,KK, a function ft - R_ is said to satisfy the weak learning condition with respect to g. Vj. the following sum is strictly positive:
K, (1,5))(()) - g(x,)), K2 (i.j)(((x;) fe(x:));-
At each round I, with the current probability matrices K; K2* B-DISTIL performs two steps; first, it invokes a subroutine FIND-WL (discussed below) that attempts to find a classifier ft E F, satisfying the weak learning condition (Definition D). If such predictor is found,
add it to our ensemble and proceed to the second step, updating the probability matrices K, K2 based on errors made by ft- This is similar in spirit to boosting algorithms such AdaBoost [39] for binary classification. If no such predictor can be found, we invoke the subroutine with the next class, Fr+1, and repeat the search till weak leamner found or we have no more classes to search in.
3.3 Finding Weak Learners
As mentioned above, the main difficulty in provably approximating the teacher model in this setting
is in finding single learner fe at round f that satisfies our weak learning condition simultancously
for all labels Existing boosting methods for classification treat multi-class settings (L 1) as L instances of the binary classification problem (one vs. all) 39. They typically choose L different weak learners for each instance, which is unsuitable for resource efficient on-device inference. The difficulty is further increased by the capacity gap between the student and teacher models we consider for distillation. Thus, along with controlling temperature for distillation, we employ two additional strategies: 1) we use a regularizer in the objective FIND-WI. solves to promote weak learning and, 2) we efficiently reuse a limited number stored activation outputs previously evaluated models to increase the expressivity of the current base class.

---

Log-barrier regularizer. To find weak learner, the FIND-WE WL method minimizes the sum of two loss terms using stochastic gradient descent. The first is standard binary/multi-laas cross-entropy distillation loss [33 with temperature smoothing. The second term is defined in Equation (6):
lij log (1+ ((r)) 2B
1(x:)) 2B
Σ 4
+ +11 12) log
Here 1n == [KT (i > K, (i. B is an upper bound on the magnitude of the logits, and 1(x;) = f(x) - g(z)). To see the intuition behind Equation 6 assume the following holds; V(i, J).
(K (i.j) K, (f.j))(((z.) g(x:)), >
(7)
Summing over all 24, we can see that this is sufficient for f to be a weak learner with respect to g. Equation (6) is soft log-barrier version of the weak learning condition, that penalizes those (i.5) for which Equation (7) does not hold. By tuning Y we can increase the relative importance of the regularization objective, encouraging to be weak learner potentially at the expense of classification performance.
Intermediate layer connections and profiling. As discussed in Section 2, distillation onto linear combination of low capacity student models often offers no better performance than that any single model in the ensemble trained independently. For boosting, empirically weak learner has been found in some class Fm of low-capacity deep networks, is difficult to find a weak learner for the reweighed objective from the same class Fu. To work around this we let our class of weak learners at round t include functions that depend on the output of intermediate layers of previous weak learners [40]
that once the first
As a concrete example, consider a deep fully connected network with layers, parameterized as W Wov.. Here @isu can be thought of as feature transform on using the first layers into Rd and W E RdxxL is a linear transform. With two layer fully connected base model class Fo = (W 212 (()) E [Lxdd (dropping subscript m for simplicity), we define:
F, (W(n)/1210 + and, F,((()) (l (id + of") + o((-"))),
@2
with id(x:) == x. can be seen that {Fr} and {Fi} define variant of residual connection based networks (77. It can be shown that classes of function (Fr-} (and (F()) increase in capacity with r. Moreover, when evaluating sequentially the inference cost of a model from F, is roughly equal to that of F, since each subsequent evaluation reuses stored activations from previous evaluations. For this reason the parameter count of each F, remains the same as that of the base class. Note that by picking the base class dense networks various scales and connections as dense connections algorithm can recover MSDNets studied in (27]. Similarly, by picking the base class as root nodes, and connections binary connections, recover an HNE from (3).
We informally refer to the process of constructing {Fr} given a choice of base class Fo. the parameter R and the connection type as expanding Fo- Note that while intermediate connections help with capacity, they often reduce parallelizability as models become mutually dependent. As practical consequence dependencies activation outputs of later layers are preferred, and we use the Rasley al. 35 profiler to measure inference cost during training rounds and rank models (see Appendix C
4 Theoretical Analysis
In this section we provide theoretical analysis and justification for our method. First, we show that the ensemble output produced by algorithm converges to g at (1/VTT) rate, provided that the procedure FIND-Wi WLND-WL&A succeeds at every time t.
Theorem 1. Suppose the class FF satisfies that for all f F, ||f glooo < Goc. Let F = {fi be
the ensemble after T rounds of Algorithm ! with the final output F, & ET If Jt satisfies
eq. ? for all t S T then for T 2 In and d. /n2N, we have for all
In2N
[F., - 99 S Goo
(8)
T
where Fe,j and gj are the jth coordinates of the functions F; and g respectively.
5

---

We defer the details of the proof to the Appendix B The main idea behind the proof is to bound the rate convergence of the algorithm towards the minimax solution. This proceeds by maintaining potential function and keeping track of its progress through the algorithm. The bounds and techniques here are general in the sense that for various objectives and loss functions appropriate designed weak learners give similar rates of convergence to the minimax solution. Furthermore, a stronger version that shows exponential rates can be shown by additionally assuming an edge for the weak learner.
In addition to the claim above about the in-sample risk, we also show that the algorithm has a strong sut-of-sample guarantee. We show this by bounding the generalization error the algorithm in terms of the generalization eπror of the class F. In the following theorem, we restrict to the case of binary classification for simplicity, but the general result follow along similar lines. Let Cr denote the class of functions of the form
T
Fr(x) sign( 7 Σ f((x)),
2=1
where ft are functions in class F. We then have the following generalization guarantee:
Theorem (Excess Risk). Suppose data D contains of N iid samples distribution D and that the function g has e margin on data D with probability μs, i.e., PIa-D [[g(x)] < e) < Further, suppose that the class Cr has VC dimension d. Then, for T 4G In 2N/c2, with probability over the samples, the output Fr of algorithm satisfies:
crr(Fr) S GTT (g) (0) (v ddn(NN/d + In(1/6)
+ p.
Note that the above theorem can easily be adapted to the case of margins and VC dimension of the class Cr being replaced with the corresponding fat-shattering dimensions. Furthermore, in the setting of stochastic minimax optimization, one can get population bounds directly by thinking of sample losses and gradients stochastic gradients to the population objective. This is for example the view taken by [40). In our work, we separate the population and sample bounds to simplify the presentation and the proofs.
5 Empirical Evaluation
We now evaluate B-DISTII, on both real-world and simulated datasets and over a variety of architecture types. We consider six real world datasets across three domains-vision, speech and sensor-data-ae well as two simulated datasets. This allows us to evaluate our method on five architecture types: fully connected, convolutional, residual, densely connected networks and recurrent networks. Our code can be found at: gi github. com/metastaalll//ddi...
5.1 Dataset Information
For experiments with simulated data, construct two datasets. The first dataset, referred to as ellipsoid a binary classification dataset. Here the classification labels for each data point E R332 determined by the value of x² Ar for random positive semidefinite matrix A. The second simulated dataset, cube, is for multiclass classification with 4 classes. Here labels are determined by distance to vertices from {-1, 1] in R partitioned into 4 classes.
We also use six real world datasets for our experiments. Our image classification experiments use CIFAR-10. CIFAR- TinylmageNer and ImageNet datasets. For time-series classification tasks use the Google-13 speech commands dataset. Here the task is keyword detection: given one-second buffer of audio, need to identify if any of 13 predefined keywords have been uttered in this. Finally, we use the daily sports activities (DSA) dataset for experiments with sensor data. Here the task is identifying the activity performed by an individual from predefined set of sports activities, using sensor data. For detailed information of all datasets used see Appendix
5.2 Model Architecture Details
We use deep fully connected (FC) networks for classification Ellipsoid and convolutional networks for Cube. For image classification on CIFAR- 10 and ImageNer dataset we use publicly available, pretrained ResNet models. We train reference DenseNet models for the
Teacher models.

---

FC-32,32.64
FC-16,26,16
ResNet56
DenseNet121
95
Accuracy 1%)
90-
90
85
60-
80-
70
0.1
0.2
0.3
0.25
0.50
0.75
0.0
0.5
1.0
0.2
0,4
0.6
trac. inference time
trac. Inference time
frac. Inference time
trac. Inference time
(a) Cube
(b) Ellipsoid
(c) CIFAR-I0
(d) CIFAR- 100
ResNet110
ResNet1
GRU32
LSTM128
80
87.5
Accuracy (96)
80
60
85.0
NORESHED RESHED
Teacher
20
20
80.0
60
DSSTILL
1.0 frac. inference time
0.5
0.5 frac. Inference time
0.4 frac. inference time
0.2
0.2
0.6
frac. inference time
(e) Tiny ImageNt
(f) ImageNet-Ik
(g) DSA-19
(h) Google-13
Figure 2: Accuracy vs. inference-time trade-offs. Inference time is reported as fraction of teacher's inference time along with average ensemble accuracy and error bars. B-DISTIL performs this trade-off at runtime. The baseline NO-RESHED at inference time Tu (r-axis) is the accuracy of a single model that is allowed ( - -] time for inference. Similarly the baseline RESHED at Tw is the accuracy of an ensemble of models, where the model w is allowed [ Tw-1l time to perform its inferenee. This is also the latency between the successive predictions from B- B-DISTIL. We can see that B-DISTIL (green) remains competitive to the oraele baseline NO-RESCHED, blue) and outperforms weighted averaging (RESCHED, yellow).
CIFAR-I0N --0 dataset based on publicly available training recipes (see Appendix C As both spoken audio data (Google-13) and sensor-data (DSA-19) are time series classification problems, we use recurrent neural networks (RNNs). We train an LSTM-based architecture [4] on Google-13 and a GRU-based architecture [10] on DSA-19. Except for the pretrained ResNet models, all other teacher models are selected based on performance on validation data.
Student models. For all distillation tasks, for simplicity we design the student base model class from the same architecture type as the teacher model, but start with significantly fewer parameters and resource requirements. We train for at most T rounds, keeping 7) = in all our experiments. Whenever FIND-WL WI fails to find a weak learner, we expand the base class F using the connection specified as a hyperparameter. Since we need only at most T 7 weak learners, we can pick small values of R (say, 2). The details of the intermediate connections used for each dataset, hyperparameters such as the regularization parameter 7 in Equation and hyperparameters for SGD can be found in Appendix Cland D
5.3 Experimental Evaluation and Results
First, we present the trade-off between accuracy and inference time offered by B-DISTIL in the context of anytime inference and early prediction. We compare our models on top-1 classification accuracy and total floating point operations (FL.Pss) required for inference. We use a publicly available profiler (35 to measure floating point operations. For simplicity of presentation, we convert these to the corresponding inference times (7) on reference accelerator (NVIDIA 3090Ti).
Anytime inference. As discussed previously, in the anytime inference setting model is required to produce a prediction even when its execution is interrupted. Standard model architectures can only output a prediction once the execution is complete and thus are unsuitable for this setting. We instead compare against the idealized baseline where we assume oracle access to the inference budget which is usually only available after the execution is finished or is interrupted. Under this assumption, we can train a set of models suitable various inference time constraints, e.g., by training models at various depths, and then pick the one that fits the current inference budget obtained by querying the oracle. We refer to this baseline as NO-RESHED and compare B-DISTIL to it on both synthetic and real world datasets Figure 2 This idealized baseline can be considered an upper bound on the accuracy of B- B-DISTIL for fixed inference budget.
7

---

Dataset
Algorithm
Early-predice Acc
7 7= 50%
T
75%
7 = 100%
Acc (%)
Frac
Acc (%)
Frac
Acc (%)
Google-13
E-RNN
88.31
0.48
88.42
0.65
92.43
B-DISTIL
87.41
0.49
89.31
0.71
92.25
E-RNN
83.5
0.55
83.6
0.56
86.8
DSA-19
B-DISTIL
82.1
0.53
84.1
0.58
87.2
Table 1: Early prediction performance. Performance of the ensemble produced by B-DISTIL to the E-RNN algorithm .T The accuracy and the cumulative fraction of the data early predicted at 50%, 75% and 100% time steps are shown. At = 100, frac. evaluated is 1.0. The ensemble output by B- B-DISTIL with the preeeppreiitioon loss is competitive the E- E-RNN algorithm. Unlike RNN, method developed specifically for early prediction of RNNs, B-DISTILL is more generally applicable across model architecures and can also be used for offline.
B- B-DISTIL. can improve on its initial prediction whenever inference jobs are allowed to be rescheduled.
To contextualize this possible improvement, consider the case where the execution is interrupted and rescheduled (with zero-latency, for simplicity) at times {TI, T2...., TW }. We are required to output prediction
each Tw- As idealized baseline, assume points in advance. One possible solution then is as follows: select models with inference budgets mn), |T.//2220 7i ..l...., Tuu - -w- || Sequentially evaluate them and each interrupt Tios and output the (possibly weighted) average prediction of the w models. We call this baseline RESCHED. Since the prediction at Tw is a weighted average of models, we expect its performance to serve as a fower-bound for the performance of B-DISTIL. In the same figure (Figure 2 we compare B- B-DISTIL to RESHED.
know these interrupt
We see that at all interrupts points in Figure 2 the predictions provided by B-DISTIL are competitive to that of the idealized baseline RESHED which requires the inference budget ahead of time for model selection, while being able improve its initial predictions if rescheduled. For instance, for the CIFAR- 100 dataset and at the interrupt point at 0.5 on the z-axis, the predictions produced by B-DISTIL are comparable to single model of the same inference duration, while being able to allow interrupts at all the previous points.
Early prediction. To evaluate the applicability of our method for early prediction in online time- series inference, we compare the performance of B-DISTIL to that of E-RNN from [.]. Unlike B-DISTIL, which can be applied to generic architectures, E-RNN is a state-of-the-arr method for early prediction that was developed specifically for RNNs. When training, we set the classification loss to the carly-classification loss used in E-RNN training. We evaluate our method on the time-series datasets GoogleSpeech and DSA. The performance in terms of time-steps evaluated is compared in Table T Here, we see that B-DISTIL remains competitive to E-RNN for early prediction. Unlike E-RNN, B-DISTIL also offers early prediction for offline/batch evaluation time-series data. For such cases, a threshold can tuned similar to E-RNN and B-DISTIL. can evaluate the models in its ensemble in order of increasing cost, exiting when the prediction score crosses this threshold.
5.4 Training Considerations and Scalablility
Connections. Our method uses intermediate connections to improve its performance. Although these connections are designed to be efficient, they still have an overhead cost over an averaging based ensemble. The FLOPs required to evaluate intermediate connections corresponding to the distillation tasks in Figure 2 is shown in Figure 3 Here, we compare the FLOPss required to evaluate the model from round T to the FL.OPs required evaluate the intermediate connections used by this model. Note that summing up all the FLOPs up to a round T, in Figure 3 the total FLOPs required to for the ensemble with the first T' models. For all our models, the overhead of connections is negligible when compared to the inference cost of the corresponding model.To To evaluate the benefits offered by the intermediate connections, we can compare the results of B-DISTIL run with connections and B-DISTIL without connections. The latter case can be thought of as running the AdaBoost algorithm for distillation. Note that this is the same as the RESCHED baseline (weighted averaging).
On comparing the B-DISTIL plot in Figure the plot of RESCHED highlights the benefit of using intermediate connections. As in this work our focus is on finding weak learners in the presence of capacity gap, and we do not explore additional compression strategies like quantization, hard thresholding, low-rank projection that can further reduce inference cost.
8

---

LSTM128
GRU32
ResNet56
DenseNet121
Frac. flogs
0.2
Model
Cenr
0.2-
0.15
0.15
0.10
0.10
0.1
0.05
0.05
0.05
0.00
0.00
0.0
0.00
Round (7)
Round (7)
Round (T)
Round
(a) Google-13
(b) DSA-19
(c) CIFARIO
(d) CIFAR-I00
Figure 3: Overhead of connections. The floating point operations required to evaluate the model added in
round T, compared to that required to evaluate just the connections used by this model. We present the results corresponding datasets that have models with smaller required FLOPs overall. We see that even for these models the connections add relatively little overhead.
Overheads of traininggdissillatiinn B-DISTIL requires additional compute and memory compared single model's training. Maintaining the matrices K2 and K; requires an additional O(NL) memory. Even for relatively large datasets with, say, N = 10 samples and = 1000 classes, this comes few gigabytes. Note that the two matrices can be stored in disk and batch can be loaded into memory for loss computation asynchronously using data loaders provided by standard ML frameworks. Thus the additional GPU memory requirement is quite small, ((L) for mini-batch size b, same as the memory required to maintain one-hot classification labels for a mini-batch. Since gradient computation is required only for the model being trained in each round, which typically is smaller than the teacher model, the backward pass is relatively cheap. For large datasets, loading the data for the teacher model forward pass becomes the bottleneck. See Appendix D for discussion on data loading, training time, and resource requirements for a ImageNet distillation.
Sorting {F} using profiling. As mentioned in Section 3 B-DISTIL assumes the hypothesis classes in (F) are ordered on some metric, say, inference time. In practice, achieve this at run-time by starting with small base model, and profiling subsequent models considered in later rounds at run-time. For example, in PyTorch, we can use the torch. autograd. profiler module to profile the forward pass of a model. As a heuristic, we then sort the models in {F} based on the average inference time of the models in the ensemble.
6 Limitations, Broader Impact, and Future Work
In this paper we explore the problem of progressive ensemble distillation, in which the goal is to produce an ensemble of small weak learners from large model, where components of the ensemble enable progressively better results as the ensemble size increases. To address this problem we propose B-DISTIL, algorithm for progressive ensemble distillation, and demonstrate that can be useful for a number of applications in efficient inference. In particular, our approach allows for a straightforward way to trade off accuracy and compute at inference time, and critical for scenarios where inference may be interrupted abruptly or where variable levels of accuracy can be tolerated. We experimentally demonstrate the effectiveness of B-DISTIL by decomposing well-established deep models onto ensembles for data from vision, speech, and sensor domains. Our procedure leverages stochastic solver combined with log barrier regularization for finding weak learners, use profiling for model selection and use intermediary connections to circumvent the issue of model capacity gap.
key insight in this work is that posing distillation abstract away model architecture details into base class construction F. This means that, conditioned on finding 'weak learner' from the base class, retain the guarantees of the traditional boosting setup. Since these weak learners are only required to produce small improvements between rounds, we are able to reliably find such models. A caveat and potential limitation of this abstraction that the user must design F. Our research primarily focuses on on on-device continuous inference, but our distillation procedure also holds benefits for cloud/data-cent like fusion,, balaniinn,,,g, and improved resource utilization, which merit further investigation in future studies. Finally, it is important to mention that our work prioritizes optimizing model accuracy while enabling compressed forms. However, another area for future research is exploring
two player zero-sum game allows to
inference settings. This includes tasks
additional impacts of our approach on metrics such as fairness or robustness 25 26 32

---

7 Acknowledgements
This work was supported in part by National Science Foundation Grants IIS2145670 and CCF2107024, a Meta Faculty Award, and the Private Al Collaborative Research Institute. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the National Science Foundation or any other funding agency.
References
[1] Zeyuan Allen-Zhu and Yuanzhi Li. Towards understanding ensemble, knowledge distillation and celf-distillation in deep learning. In The Eleventh International Conference on Learning Representations, 2022.
[2] Jose M Alvarez and Mathieu Salzmann. Compression-aware training of deep networks. Ad- vances in Neural Information Processing Systems, 2017.
[3] 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, 2020.
[4] Tolga Bolukbasi, Joseph Wang. Ofer Dekel, and Venkatesh Saligrama. Adaptive neural networks for efficient inference. In International Conference on Machine Learning, 2017.
[5] Cristian Buciluă, Rich Caruana, and Alexandru Niculescu-Mizii. Model compression. In International Conference on Knowledge Discovery and Data aata-mining, 2006.
[6] Arnay Chavan, Zhiqiang Shen, Zhuang Liu, Zechun Liu, Kwang- Ting Cheng, and Eric P Xing. Vision transformer slimming: Multi-dimension searching in continuous optimization space. In Proceedings of the IEEE/CVF Conference on Computer Vision and Patlern Recognition, 2022.
[7] Changan Chen, Frederick Tung, Naveen Vedula, and Greg Mori. Constraint-aware deep neural network compression. In Proceedings of the European Conference on Computer Vision, 2018.
[8] Tianqi Chen and Carlos Guestrin. Xgboost: A scalable tree boosting system. In International Conference Knowledge Discovery and Data-mining, 2016.
[9] Jang Hyun Cho and Bharath Hariharan. On the efficacy of knowledge distillation. In Internationa Conference on Computer Vision, 2019.
[10] Kyunghyun Cho, Bart Van Merriënboer, Dzmitry Bahdanau, and Yoshua Bengio. On the properties of neural machine translation: Encoder-decoder approaches. arXiv preprint arXiv: /409. /259, 2014.
[11] Don Dennis, Chirag Pabbaraju, Harsha Vardhan Simhadri, and Prateek Jain. Multiple instance learning for efficient sequential data classification on resource-constrained devices. Advances in Neural Information Processing Systems, 2018.
[12] Don Dennis, Durmus Alp Emre Acar, Vikram Mandikal, Vinu Sankar Sadasivan, Venkatesh Saligrama, Harsha Vardhan Simhadri, and Prateek Jain. Shallow rnn: accurate time-series classification on resource constrained devices. Advances in Neural Information Processing Systems, 2019.
[13] Devvrit, Sneha Kudugunta, Aditya Kusupati, Tim Dettmerst, Kaifeng Chen, Inderjit Dhillon, Yulia Tsvetkov, Hannaneh Hajishirzi, Sham Kakade, Ali Farhadi, and Prateek Jain. Matformer: Nested transformer for elastic inference. arXiv preprint arXiv:2310.07700 2023.
[14] Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL http://///rr
ics.uci. edu/ml ml
[15] Yoav Freund, Boosting a weak learning algorithm by majority. In Workshop on Computational Learning Theory, 1990.
[16] Yoav Freund and Robert Schapire. Game theory, on-line prediction and boosting. Conference on Learning Theory, 2000.
10

---

[17] Yoav Freund and Robert E Schapire. A and an application to boosting. Journal of Computer and System Sciences, 1997.
generalization of on-line learning
[18] Trevor Gale, Erich Elsen, and Sara Hooker. The state of sparsity in deep neural networks. arXiv preprint 1rXiv:1902.09574 2019.
[19] Mengya Gao, Yujun Wang, and Liang Wan. Residual error based knowledge distillation. Neurocomputing, 2021.
[20] Amir Gholami, Schoon Kim, Zhen Dong, Zhewei Yao, Michael W Mahoney, and Kurt Keutzer. survey of quantization methods for efficient neural network inference. arXiv preprint 17X1:22033113600, 2021.
[21] Jianping Gou, Baosheng Yu, Stephen J Maybank, and Dacheng Tao. Knowledge distillation: A survey. International Journal of Computer Vision, 2021.
[22] Song Han, Jeff Pool, John Tran, and William Dally. Learning both weights and connections for efficient neural network. Advances in Neural Information Processing Systems, 2015.
[23] Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in a neural network. stat, 1050:9, 2015.
[24] Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural Computation, 1997.
[25] Sara Hooker, Aaron Courville, Gregory Clark, Yann Dauphin, and Andrea Frome. What do compressed deep neural networks forget? arXiv preprint 191 1.05248, 2019.
[26] Sara Hooker, Nyalleng Moorosi, Gregory Clark, Samy Bengio, and Emily Denton. Characteris- ing bias compressed models. arXiv preprint arXiv:2010003058, 2020.
[27] Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. In IEEE conference on Computer Vision and Pattern Recognition, 2017.
[28] Gao Huang. Danlu Chen, Tianhong Li, Felix Wu, Laurens van der Maaten, and Kilian Wein- berger. Multi-scale dense networks for resource efficient image classification. In International Conference Learning Representations, 2018.
[29] Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar- 10 (canadian institute for advanced research). URL http://ww// cs toronto...... wowoonoo.duuunaeett... wdw/ cifar html
[30] Ya Le and Xuan S. Yang. Tiny imagenet visual recognition challenge. 2015.
[31] Hao Li, Hong Zhang, Xiaojuan Qi, Ruigang Yang, and Gao Huang. Improved techniques for training adaptive deep networks. In International Conference on Computer Vision, 2019.
[32] Lucas Liebenwein, Cenk Baykal, Brandon Carter, David Gifford, and Daniela Rus. Lost in pruning: The effects pruning neural networks beyond test accuracy. Proceedings of Machine Learning and Systems, 2021.
[33] Llew Mason, Jonathan Baxter, Peter Bartlett, and Mareus Frean. Boosting algorithms as gradient descent. Advances in Neural Information Processing Systems, 1999.
[34] Seyed Iman Mirzadeh, Mehrdad Farajtabar, Ang Li, Nir Levine, Akihiro Matsukawa, and Hassan Ghasemzadeh. Improved knowledge distillation via teacher assistant. AAAI Conference on Artificial Intelligence, 2020.
[35] Jeff Rasley, Samyam Rajbhandari, Olatunji Ruwase, and Yuxiong He. Deepspeed: System optimizations enable training deep learning models with over 100 billion parameters. In International Conference on Knowledge Discovery & Data Mining, 2020.
[36] Adria Ruiz. and Jakob Verbeek. Anytime inference with distilled hierarchical neural ensembles.
In Proceedings of the AAAI Conference Artificial Intelligence, 2021.
11

---

[37] 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, 2015.
[38] Robert E Schapire. The strength of weak learnability. Machine learning, 1990.
[39] Robert E Schapire and Yoav Freund. Boosting: Foundations and algorithms. Kybernetes, 2013.
[40] Arun Suggala, Bingbin Liu, and Pradeep Ravikumar. Generalized boosting. Advances in Neural Information Processing systems, 2020.
[41] Luca Trevisan, Madhur Tulsiani, and Salil Vadhan. Regularity, boosting, and efficiently simulating every high-entropy distribution. In IEEE Conference on Computational Complexity, 2009.
[42] John von Neumann and Oskar Morgenstem. Theory of games and economic behavior, 1944.
[43] Pete Warden. Speech commands: A dataset for limite-voccbullan speech recognition, 2018.
[44] Li Yang and Deliang Fan. Dynamic neural network to enable run-time trade-off between accuracy and latency. In Asia and South Pacific Design Automation Conference. Association for Computing Machinery, 2021.
[45] Sean I Young, Wang Zhe, David Taubman, and Bernd Girod. Transform quantization for cmn compression. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021.
[46] Jiahui Yu, Linjie Yang, Ning Xu, Jianchao Yang, and Thomas Huang. Slimmable neural networks. In International Conference Learning Representations, 2018
12

---

A Two-Player Minimax Games
In this section, we will look at the setting of two-player minimax games more closely.
Consider a class of hypotheses F and class of probability distributions P. In addition, consider loss function L F x X' - R that is convex in its first argument. We consider two players whose pure strategy sets are F and P respectively. The loss and reward of the players is given by F(J, p)) Ex-pl and the minmax value of the game is
max min F (f.H). pEP FEF
Note that this game is convex in the hypothesis player and concave in the distribution player. The objective of the game for the hypothesis player trying to find a hypothesis that has low loss on the worst case distribution from class P. Conversely, the distribution player is trying to construct distribution that is as hard as possible for the hypothesis player to learn.
Also, note that under reasonable conditions on J and P, we have the minimax theorem holds (see Chapter 6, Schapire and Freund
max min Ex-n pEP FEF
[)] = min max max Em=plL(f,r)) SEA(F) PEp
(10)
Here, A (F) is the set distributions over functions F. From this, we can see that as long as we are allowed to aggregate functions from the base class, we have can do as well as we could if we had access to the distribution
The interesting algorithmic question would be to find distribution over hypotheses that achieves the minimum above. Note that the loss function is stochastic and thus, we need to formalize the access the player has the loss function. We will formulate this in the following stochastic way. Definition 2. An algorithm ORACLE is said to be (B,8) weak-gradies if
(ORACTE(S.)) F (f,p)) 2 3
(11)
with probability 1-
Here V denotes the functional gradient of F. This notion is similar to the weak learning assumptions usually used in the boosting literature. Given such an oracle one can ask for methods similar first order methods for convex optimization, such as gradient descent, to solve the minimax problem. These algorithms iteratively maintain candidate solutions for the both the players and update each of these using feedback from the state of the other player. In our particular setting, the hypothesis player updates using the vector in eq.
Motivating Example. Let F. be a class of hypotheses, let P is the set of all distributions over a finite sample set {ar1.... ] and let L be the 0-1 loss. Note that in this setting, the oracle from Definition is analogous to weak learning. In this setting, from the minmax theorem and the existence of weak learner, we get that there is single mixture of hypothesis of Σ, asfi such that loss under every distribution in P which corresponds to zero training error. Thus we can think of boosting algorithms as approximating this minmax equilibrium algorithnically. Similarly, the weak learning condition in
40 is similar in spirit to the condition above.
With the condition from Definition 2 one can consider many frameworks for solving minimax games. One general technique is to consider two no-regret algorithms for online convex optimization to play against each other. Let us briefly look at the definition of regret in this setting.
Definition 3 (No Regree)..) Let K, A be convex sets. At each time, a player observes point xa K and chooses an action ag E A. The regret of the algorithm defined as
T
T
max RT
(a, xz) - Σ
(ae, xx).
(12)
aEA
1=1
Online learning is well-studied area of machine learning with a rich set of connections to various areas in mathematics and computer science. In particular, there are frameworks in order to construct algorithms such as follow-the- www-tthh--ertubedd leader, folluw-the-regularized leader and mirror descent.
13

---

Our algorithm can be seen as a version of mirror descent with the entropy regularizer and Theorem | as a version of the regret guarantee for the algorithm. In addition to those mentioned above, there are several other frameworks considered to solve minimax games such as variational inequalities, extragradient methods, optimistic methods, etc. We believe this general framework is useful one to consider for many learning tasks, especially in settings where we have function approximation.
B Proofs of Main Theorems
Here, provide proof of Theorem [ which is restated below: Theorem. Suppose the class F satisfies that for all f E F, llf glooc I Go Let F {ffe be the ensemble after T rounds of Algorithm with the final output F; = T E St. Then for T 2 In 2N and
In 2N T
G
we have for all j
In 2N
T
[P, - gslloc S /
T Σ
where Fe.j and 9j the j coordinates of the functions Fr and g respectively.
Proof. For simplicity, we assume that fs and g are scalar valued functions, since the proof goes through coordinate- wise. At each time, define the edge of the weak learning algorithm to be
Y Σ (()((()))) g(x))) + Σ KE (1)()(z)) fx(x))
Let Z, denote the normalizing constant at time I, that is,
Z: Σ K (i) (-n (Se (m:) g(xx))) + KT (f) (n (0s) g(z;)))
From the update rule, we have
K (i)e((((a)))))
K (1)
ZT
exp (n1 (fr g(xi));)
II'-1 Z: (x)))exp (-1fT(Pr(xss - -g(xz))
II: Zr
and similarly
Kī (1) exp (FT((F((I,) -(T)))
K KT+1() (1)
[T Z,
First, we bound In(Z)):
In Zz) = In
Σ Kit exx(((())(((( g(xx))) + Σ K2 expp(((((a) - g(x;)))
< In
Σ (x) (1 (f) - g(xx)) + (f((z)) g(xx))²)
- + Σ K. (i) (1 - -((()))))(((()))))())()))))))))) + + (
- s(xx)))))
< In 1 - 11 Σ
(z)( - -g(x=)) + Σ K7 (T)(f((z)))))) g(x,)) + P2G2
$ 5-7% + 122 G2
14

---

where the second step follows from the identity exp(x) v 1 + r + x² for x I 1. provided that
n S Gx This gives us bound on regression error after T rounds:
T/T (Fr(x;) - 9(x;)) 1m ln( (i((k(
+ Σ ln(2,)
K7+1
1
+ 1=1
Mi + G
KJ (i)
In
+ TG
Σ 7t
KJ (i)
1=1
$ 1n2N + 17 TG2 - 7t
where the last bound follows since KT- 2N and KT I 1. Similarly, have the bound
T
n (Fr(2)) g(x))) = 1n 1f TG 17
7
Combining the two equations get that
In2N
T
sup|Fr((.) - -((,)) = || glloo I
+
G
Σ
1/T
T
we choose regression error:
22
to minimize this expression, then we get the following bound on T
Go0
T F. glx - + Go
7
Σ
In2N
which is exactly Equation (8 Note that the value of r only satisfies the condition vy S Gm when T In 2N, which is the horizon after which the bound holds. This finishes the proof of Theorem
Now, we provide proof of Theorem 2 which follows from the VC dimension bound and Theorem
Before we begin, setup some notation. Given function f. distribution 'D over space X' x ) where X' is the input space and y is the label space, and data D consisting of N iid samples (x. y) D, we define
err
Pr (i)gn(Fr(x) # v)] (x.
err(f)
Pr (F # v)] (#.y)~
Theorem (Excess Risk). Suppose data D contains of iid samples from distribution D. Suppose that the function g has large margin on data D, that is
[[g(t)) < <E)< <p D>D
Pr
Further, suppose that the class Cr has VC dimension d, then for
4G2
T2
with probability 1 - 8 over the draws of data D, the generalization error of the ensemble Fr obtained after round of Algorithm 7 bounded by
[dIn(N/d) In(1/8)
err(Fr) < Gr((g) +0
+
N
15

---

Proof. Recall the following probability bound Schapire and Freund 39 theorem 2.5] which follows Sauer's Lemma:
Pr Pr E Cr err(f) 2 err(f) + +
-me//32
which holds whenever D 2 follows that with probability ô over the samples, we have for all f E CT
(V (V ln(1/))
/ain(N/o) +
err(ʃ) S err +0
(13)
N
Since we choose T 4G3, 2N 2
by Theorem
we have
In 2N
Vr E D: F. - 1ll S G
T
2
Since g has margin on data with probability - we have
eTT(F,) - e (g) + 4
(14)
Combining eqs. 13 and 14 we get
+ In(110)
err Fr) S cr)(g) +0
+
N
which completes the proof.
C
Dataset Information and Training Recipe
We six publicly available real world datasets in experiments. The train-test splits for all the dataset as well as the sources are listed here:
C.1
Dataset
Dataset
Train-samples
Test/Val- Teet//Va-ssaplls
Num.-labels
Source
CIFAR-10
50000
10000
[9
CIFAR-100
50000
10000
100
29
DSA-19
6800
2280
19
[14]
Google-13
52886
6835
13
43
ImageNet-1k 1k
1281167
50000
1000
37
TinylmageNet-2000
100000
10000
200
30
We use two synthetic datasets in our experiments, ellipsoid and cube. To construct the ellipsoid dataset, we first sample 32 32 matrix B, each entry sampled iid. We define A := BT B as our positive semi-definite matrix, and / [x=" Ax 2 0) determines the label of a data point æ. We sample 10k points uniform randomly from [-1, 1| and determine their labels construct our data sample. We randomly construct 80-20 train-test split for our experiments.
To construct cube, first sample 16 vertices uniform randomly from [-1, 1| and split them into 4 equal sets, say (Si...., S4). As before, we sample 10k points uniformly from determine the label y(x) of each point based on the closest vertex in {S,,.., S4).
and
v(z) arg min min | E'ES;
x'1]-
C.2 Training Recepies
We use stochastic gradient descent (SGD) with momentum for all our experiements. For experiments on CIFAR100 and CIFARIO, we use learning rate of 0. momentum paramter 0.9, and weight decay of 5 x 10-4, We train for 200 epochs and reduce the learning rate by factor of 0.2 in after
16

---

Teacher model
Residual Blocks
Embedding dims
Strides
8
ResNet56
2.2
8,8
1,1
2,2
16.16
1,2
2,2,3
16,32.64
1,2,2
Table 2: Base model configuration used for ResNet56 distillation CIFAR- 10.
Teacher model
Blocks
growth-rate
4, 8
12
2enseNet121
4, 8, 8
8, 16, 12
Table Configuration used for DenseNet121 distillation CIFAR-100.
30,, 60% and 90% of the epoch execution. We perform 4-GPU data-parallel training for ImageNet with a per-gpu batch size of 256, learning rate 0.1, momentum 0.9, regularization y of 1.0, and a We train for 90 epochs with and discount the learning rate by factor of 0.1 at 30% and 60% epochs. For experiments with time series data, Google-13 and DSA-19, we use fixed learning rate of 0.05 and momentum of 0.9, We do not use weight decay learning rate scheduling for time-series data.
weight decaur of le
C.3 Profiling Based Model Selection
To estimate execution latency, we leverage third-party library, such the Deep Speed frame- work [35], which enables us to measure the total floating-point operations required for inference. By randomly initializing a single sample with a batch size 1, we obtain the FLOPS values for various real-world datasets. This profiling process serves as reliable indicator of real-world performance, allowing us to rank the models based on their profiles. Notably. the profiling results only need to hold relative to other candidate models. Furthermore, we can utilize existing profiling models, such as ARM Fast Models for ARM-based mobile platforms, QEMU for x86 platforms, NVIDIA NSight's GPU emulators for GPU platforms, to estimate the performance on different hardware architectures. However, it's important to note that these software-based solutions provide approximate performance estimates, and accurate evaluation of real performance requires access to the actual hardware. We are not restricted to latency based rankings. In fact, other useful metrics like throughput in sample processed per second, can also be used for candidate model selection.
D Base Model Configuration
The base class configurations used for our experiments Figure is provided in Tables and Note that we use standard model architectures implemented in Pytorch and the parameters correspond to the corresponding function arguments in these implementation. We use pretrained models from the torchvision library.
Teacher model
Residual Blocks
Embedding dims
Strides
2, 2
16, 16
1,2
2, 3
32. 64
1,2
ResNet1 10
2, 2, 3
16, 32, 64
1,1,2
2, 3, 3
16, 32. 64
1,2,2
Table 4: Base models for TinylmageNet.
17

---

Teacher model
Residual Blocks
Embedding dims
Strides
2,
16, 16
1,2
2, 3
32, 64
1,2
ResNet101
2, 2, 3
16, 32, 64
1,1,2
2, 3. 3
32, 32, 64
1,2,2
Table 5: Base models for ImageNet.
Teacher model
hid. dims.
Teacher model
hid. dims.
4,4
4,4
16,8
GRU32
8.16
LSTM128
20,12
16,
20,32
32,16
Table 6: Configuration used for LSTM128 distillation on Google-13.
Table Configuration used for GRU32 distillation
on DSA-19.
E
Additional Results
E.1
Connections and parallel execution schedules.
Our focus in this work has been sequential execution of the models. While reusing previously computed features is clearly beneficial for finding weak learners in this setup, the presence of connections across models prevent them from being scheduled together for execution whenever otherwise possible. To manage this trade off between parallelization and expressivity, we try to restrict the number connections to at most one between models, and further restrict the connection to later layers of the model. Connections in the later layers of networks impose fewer sequential blocks in inference and allows for better parallelization.
Let (xr) denote the activation produced at layer by the weak learner at round on data-point Then some of the connections we consider are
(z) ((1+1,1) (z), to learn the error in features at layer l.
(z)) + id(x), standard residual connection at layer 1.
01441.100110 (x) (x)), dense connections layer I across rounds.
Simple accumulation operations.
Recurrent networks: LSTM and GRU.
E.2 Training ImageNet and Throughput Optimization
Large datasets like ImageNet require additional care to ensure good resource utilization. Since the backward pass of our training only involve single student model, it can be computed quite efficiently even for large datasets. This particularly true in earlier rounds. For such cases we use simple producer consumer architecture where GPU is dedicated to producing and queuing data batches and target predictions produced by the teacher. Training routines running on separate GPUs consume these batches for their training.
As mentioned in Section 3 since B-DISTIL only cares that it is provided with an ordered list of candidates, we can modily the weak learning finding step to prefer weak learners that provide higher inference throughput, measured as samples processed per second. Throughput metric is more meaningful in the cloud inference deployment setting where batched inference is the norm. The ability to trade a small performance for the number of inference requests to process can be useful in such settings. Implementation details can be found in the included code base. We note that do not optimize for throughput and inference latency simultancously in this work, but is an interesting direction of future research.
18

---

(a) Sequential schedule
(b) Hybrid schedule
A schematic description of sequential exccution scheme for ensemble of four models, being evaluated one after other from left right. The last model in ensemble reuses the actions the previous one, causing a blocking dependency. Thus we cannot trivially execute models parallel. However, since connection is between the last layers of the network, we can construct hybrid execution schemes as in (b). Here, pairs of models are executed together.
Figure 4:
19


Reviews:
[{"review_id": "kVBlP9L89Q", "reviewer": "Reviewer_KanN", "summary": "The main focus of this paper is to address a problem in progressive knowledge distillation, which involves approximating a single large teacher model by utilizing an ensemble of multiple smaller student models. The authors propose an algorithm called B-DISTILL to tackle this specific problem. One notable advantage of this methodology is its capability to effectively balance the trade-off between cost and performance by adjusting the ensemble size of the student models.", "questions": "1. The proposed methodology is in line with the principles of slimmable networks (Yu et al., 2019), as it enables users to control the inference cost. Although there are distinctions in the primary categories of each approach, such as pruning and distillation, they share common properties in terms of model compression. Thus, it would be advantageous to include related works, such as slimmable networks, in the main text to ensure readers have a comprehensive understanding of the topic.\n2. Could we adapt the inference cost based on the \"difficulty\" of the input? Given that there might be instances where accurate predictions can be made without the need for additional student models, the idea of limiting the ensemble size based on the difficulty is highly appealing.\n\n__Miscellaneous:__  \n1. Typo: \"B-DSTILL\" in Figure 2.\n2. Adjust the legend in Figure 3.", "limitations": "The authors addressed the limitations.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The problem formulation of \"progressive knowledge distillation\" is intriguing and well-motivated. In conventional knowledge distillation approaches for model compression, small student models of fixed sizes are typically employed, resulting in a fixed inference cost. A notable advantage of the proposed methodology is its ability to dynamically adjust the inference costs based on the available resources, which is a clear strength of the approach.\n2. While the concept of approximating a function using a combination of multiple functions is not novel (as evident from classical boosting methods mentioned by the authors), this paper provides a distinct contribution by connecting these ideas to the field of knowledge distillation.", "weaknesses": "1. The scalability of the proposed methodology appears to be somewhat limited. It was anticipated that B-DISTILL would achieve a similar level of performance as the teacher model while utilizing the same inference cost. However, when applied to TinyImageNet and ImageNet datasets, B-DISTILL falls short of meeting this expectation.\n2. One important baseline is missing - deep ensembles using the model structure considered in B-DISTILL. Including this baseline would provide a clear motivation for the progressive formulation adopted in B-DISTILL.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful feedback and positive assessment of our work.\n\n**Scalability:** Although B-DISTIL takes additional inference time to make accurate predictions for ImageNet, the teacher models in this case have 100+ layers.  Tasks in efficient inference that rely on smaller models for image datasets, or scenarios (e.g., edge inference) involving sensor/audio data streams, are key application areas that stand to benefit from B-DISTIL. However, even at larger scales, where the data distribution during inference is skewed towards 'easier' samples, B-DISTIL can be advantageous in the average case, as the majority of the predictions can be completed quickly (Google-13, Table-1, T=50%). In fact our goal in providing the ImageNet scale experiments was to demonstrate scalability of our implementation, especially since maintaining and updating the weight-matrix of a 1000 class, 1M training image dataset can be non-trivial. We will clarify this in the main text and add a discussion about the techniques we use to manage compute requirements (e.g., streaming weights off-disk asynchronously [code: `ddist.data:DataFlowControl`], performing weight updates in log-space [code: `ddist:ClfPlayer.log_space_update()`], using a shared-memory object store [code: `ddist.dispatch` utilizing the `ray` parallelization library ]) in the appendix.\n\n\n**Baselines and slimmable networks**: Thank you for the reference on slimmable networks. We will include a discussion of this and similar works in the related work section. In particular,  slimmable networks take the approach of adjusting the width at inference time based on on-device resource constraints. While we focus more broadly on network hyperparameters, both approaches do share similar ideas when thinking of them as trading off on-device performance vs. inference cost. Regarding baselines, the current NO-RESCHED baseline does use the same model structure for end-to-end distillation as used by B-DISTIL, without any activation sharing/connections. We will clarify this in the main text. We will also add end-to-end distillation performance using the same network architecture along with connections to the appendix.\n\n**Adapting inference cost based on difficulty of input:** We agree that limiting the ensemble size based on difficulty of the input is an exciting prospect. In fact, the application of our method to early-prediction in sequential inference can be interpreted as classifying based on difficulty of the input (Table 1). However, this is an intuition based argument and we leave exploring if the samples classified early have some notion of 'simplicity' as an interesting direction of future work.\n"}, {"review_id": "XgwgNusOiQ", "reviewer": "Reviewer_2TpN", "summary": "The authors describe a new method for knowledge distillation with an ensemble of lower capacity student models, and draw connections between their method and classical boosting approaches. They provide a theoretical analysis of the risk of this method, and demonstrate the benefits of their approach in learning tasks with a limited inference budget, either in terms of computing cost or speed of inference. ", "questions": "- What is an (ordered) set of low inference cost hypothesis classes? (Lines 115-117). Does this correspond to an ensemble with an increasing number of member models? If so it should be clearly stated that this is the case. How does $\\mathcal{F}$ relate to $\\mathcal{F}_m$? (Line 121). \n- How does $\\mathcal{F}_r$ relate to $\\mathcal{F}_0$? How is $\\mathcal{F}'_r$ related to $\\mathcal{F}_r$? \n- On first glance, the weak learning condition (Definition 1) appears to me quite different from other weak learning conditions in the traditional boosting literature. Is there an interpretation of this condition that is consistent with other definitions of weak learning? This would be good to know. \n- The claim \"Existing boosting methods for classification treat multi-class settings (L > 1) as L in stances of the binary classification problem (one vs. all)\" (Lines 162-166) does not apply to Adaboost.M1. Are the weak learners that you study here unable to meet the weak learning condition for Adaboost.M1? If they meet this condition, it would be a useful baseline against which to compare the performance of this method. \n- In Figure 3, it would be useful to know the correspondence between the total number of FLOPS required by the ensemble, and the corresponding model accuracy. \n", "limitations": "As the authors state, some limitations of their methods include the need to design the class of student models, and the potential additional cost of evaluating models. ", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": " A compelling idea. Approaching the task of ensemble distillation through a boosting perspective is to my knowledge a novel idea, and the connections that can be made to the boosting literature as a result are quite interesting. At face value, the B-DISTIL algorithm does not seem limited to the distillation setting, and it would be interesting to understand how it compares more generally to other boosting algorithms. ", "weaknesses": "\nAs an overall weakness, I found the presentation of the paper to be very confusing. In particular: \n- The relationship between two-player games and boosting needs to be better described in the related work and problem formulation. Schapire and Freund do not simply \"show that weak learners can be aggregated to produce strong learners\" (lines 90,91) but rather establish key correspondences between the formulation of two player games and boosting algorithms. Language from this correspondence are used throughout section 3.1 (\"players,\", \"minimax value of the game\", \"ensemble of predictors\",\"weak learners\") without a clear description of how two player games and boosting relate to one another, and make the exposition difficult to follow. \n- Notation needs to be more carefully defined throughout the text. For example, the constants $L,M,N,R$ are all used without explicit reference to what they represent in the main text (see questions below for more notation issues). \n- It is unclear to me how student models are constructed. Do the configurations in Tables 2-7 provide specifications for the student models used? Or rather for $\\mathcal{F}_0$? Are the different rows of the table different base models, or do they somehow relate to the use of intermediate layer connections? How are intermediate connections implemented in each of the specific model architectures described? \n\nOverall, I believe that the quality of the paper suffers significantly from issues with presentation, and I am willing to reconsider my score if these issues are addressed. \n\nAnother weakness of this work is comparison to previous work with respect to experimental findings. It would be useful to know how the results in Figure 4 compare to anytime inference as described in Huang et al. 2018 or Ruiz and Verbeek, 2020 for image classification results. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your many great suggestions for improving the presentation of our work, particularly the problem formulation.\n\n**Boosting, two player games: relationship, terminology and notation.** Due to space limitations we shortened the exposition on boosting, zero-sum games and weak-to-strong learning. However we agree with the reviewer that the relationship between these notions are much deeper and intricate than just “aggregating weak learners to strong learners”. In fact, the connections between online and multi-objective optimization and model compression, as seen for example in dense model theorems and regularity lemmas from complexity theory (see exposition by Luca Trevisan [1] and Theorem 2 in particular) was a key motivation for our work. We will include a detailed discussion on the connections between these notions in the appendix with the aim both to improve exposition and also to encourage the flow of ideas between the communities. We will also include an introduction of these ideas in the main text, casting classical boosting as a two-player game with the aim of introducing the terminology and notation.\n\n**Student models: ordered classes, connections and model configurations.** The configurations specified in Tables 2-7 are of the *unique* student models used for the distillation run. Note that the same student model configuration may be reused in successive rounds. The corresponding hypothesis classes are ordered from low-inference latency to high when moving from top to bottom in these tables. The connections used are implemented by overloading the forward pass of the candidate models at training time [code: `ddist.candgen:op_add_connections`]. The connections themselves are all-reduce-like (stateless) operations [code: `ddistexps.autosearch.gen_fwds`]. $\\mathcal{F}_r$ and $\\mathcal{F'}_r$ are recursively defined with $r=0$ specified by $\\mathcal{F}_0$. We will update the tables to make this clear and include a discussion of how the connections are implemented to the appendix.\n\n**Weak learning condition and AdaBoost.M1.** At a conceptual level, both the notion used in our paper and the standard weak learning guarantees are very similar. Both guarantees require that for an arbitrary reweighting (represented by K in our papers) we are able to find correlations between the hidden function (represented by the labels in the usual boosting set up and by the teacher network in our set up). From this perspective, both algorithms can be seen as “boosting” weak correlations to strong correlations through iterative reweighting. For binary classification, B-DISTIL and AdaBoost can be shown to have the same weak learning condition. For multi-class settings, they have a similar weak learning condition, which strictly speaking is stronger than the weak learning condition used in the binary classification setting (see, Section 5 in [2]). The main difference between the methods is that while AdaBoost.M1 only considers the prediction outputs w.r.t labels, $I(y_i == h(x_i))$, we work with the teacher logits and the difference between the logits $f(x_i) - h(x_i)$.  Adaboost.M1 abstracts away the details of finding a weak learner for a particular data distribution as part of a subroutine WeakLearn [2]. As we note in the main draft, finding weak learners in this sense is difficult [3], but since we use a smooth loss and a weighting tied directly to logits, we enjoy the advantage of being able to employ distillation directly on the residuals and the weak learning condition (Equations 6-7) in FIND-WL. We will add the correspondence between the weak learning conditions into the appendix.\n\nWe will also modify Figure 3 to also include actual values; thank you for this suggestion. The required FLOPS values (in million FLOPS) profiled for one vision and time-series data in Figure 3 is provided below.\n\n*CIFAR10*\n\n| Model | Connections |\n|-----------|--------------|\n| 7.37    | 0.0                |   \n| 44.96  | 0.14            |\n| 63.2   | 0.71            |\n| 63.2 | 1.53             |\n| 63.2  |2.34.            |\n\n*Google-13*\n\n|Model | Connections |\n|---|--|\n|0.084 | 0.000 |\n|0.655 | 0.013 |\n|1.051 | 0.058 |\n|1.83. | 0.120 |\n|1.82  | 0.211 |\n\n**MSDNets and HNE:** Thanks for bringing up Huang et al. 2018 (MSDNets) and Ruiz and Verbeek, 2020 (HNE), which we cite in our related work. We do not compare to these directly as they can essentially be seen as restricted variants of our approach. By picking the base class as dense networks at various scales as in Figure 2 (Huang et al. 2018), and connections as dense connections our algorithm can recover MSDNets from Huang et al. 2018. Similarly, by picking the base class as root nodes (Figure 1 Ruiz and Verbeek, 2020), and connections as binary connections, we recover an HNE. Our method formalizes this intuition of a graph comprising of a base-class and a specific connection, and provides theoretically motivation within the framework of boosting and two player games for a training procedure to construct such structures. This allows us to generalize these notions, consider a broader set of connections (ex. residual connections) and base classes (ex. recurrent networks) and data modalities,  while taking into account their implementation costs when deciding on the final structure. The two mentioned works are closely tied to image datasets for anytime inference and are not readily applicable for sequential inference. They are also only designed to optimize for latency. Finally, we note that we do compare against the more related approach of E-RNN in our early-prediction experiments.\n\n*[1] Online Optimization:  Regularity Lemmas. Luca Trevisan, In-theory (Online), 2019.*\n\n*[2]: A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting. Yoav Freund and Robert E. Schapire . Journal of Computer and System Sciences (1996).*\n\n*[3]: Generalized Boosting. Arun Suggala, Bingbin Liu, Pradeep Ravikumar. NeurIPS (2020).*"}, {"review_id": "cwSfUPuO0u", "reviewer": "Reviewer_85M5", "summary": "This paper proposes B-DISTILL, a progressive distillation algorithm that allows for easy trade-off between accuracy and inference-time/latency at runtime. By modeling knowledge distillation as a zero-sum game problem, B-DISTILL utilizes the intermediary connection modules to train and aggregate the sub-student models progressively, resembling the traditional boosting methods. The paper provides mathematical proofs that guarantee the convergence and generalization of B-DISTILL. The experimental results demonstrate the efficiency of B-DISTILL in both anytime inference and early prediction tasks.", "questions": "1. I would like to know the role of knowledge distillation in this context. Why not directly use ground truth (gt) as the fitting target? \n2. What results would be obtained if the teacher model is directly replaced with softened labels?", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper presents a novel perspective by redefining the knowledge distillation problem and effectively applying it to the tasks of anytime inference and early prediction.\n2. The paper provides complete mathematical proof and experimental validation to support its claims.", "weaknesses": "1. While the method proposed in this paper introduces a novel perspective, its application scope and advantages appear to be quite limited. \n2. It seems that some dynamic network structures could potentially be used to address the anytime reference problem. However, it appears that the paper lacks a comparative analysis with relevant methods in terms of results.\n3. It might be worth considering modifying the title. B-DISTILL is more like a training method specifically designed for efficient inference rather than a knowledge distillation-related approach.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for constructive feedback and questions, which we hope we have addressed in our response below.\n\n**Application scope.** We kindly disagree with the reviewer that the scope and advantages of our work are quite limited. Due to resource constraints in efficient inference applications it is common to leverage small to medium scale models as a starting point, e.g., models with fewer than hundred layers for image tasks, or small models for sensior/audio data streams (see, e.g., [1, 2]). These are applications/scenarios that stand to benefit significantly from the flexibility and efficiency enabled by our approach, B-DISTIL. However, even at larger scales, where the inference time data distribution is skewed towards 'easier' samples, our results show that B-DISTIL can be advantageous in the average case, as the majority of the predictions can be completed quickly (see for example Google-13, Table-1, T=50%).\n\n**Dynamic Networks.** We thank the reviewer for pointing out dynamic networks, which is a broad term that can refer to many potential approaches for dynamically adjusting model structure or parameters (see e.g., the survey [3]). At a high level these are categorized into methods that depend on input samples, training procedure, or inference procedure. The most related works to ours are those that depend on samples and dynamically adjust the model architecture (e.g., early exit, layer skipping schemes). Relative to existing methods from this category, our work provides a principled way of performing decomposition in the presence of large capacity gaps and early exit requirements, which can apply to both anytime inference and early exit problems, and is not tied to a specific modality (e.g., image, language). We have already discussed some of the most related approaches from the broad class of dynamic networks in our related work section (e.g., Huang et al. 2018, Ruiz and Verbeek, 2020 (HNE)) and have compared empirically to E-RNN, a representative approach, but will include a broader discussion that better positions these methods in the context of dynamic networks more generally. \n\n**Role of distillation.** We employ distillation instead of just the ground-truth labels to make learning with smaller capacity models possible. The temperature smoothening step of distillation combined with directly optimizing on the results aids our training procedure, particularly in early rounds where the capacity gap between the teacher model and the student model is high. We could certainly replace the teacher model with the smooth labels produced by it for later rounds of B-DISTIL. However, by doing so we lose the effects of non-deterministic preprocessing steps, for instance random rotations and crops for images, on the teacher logits. Distillation is therefore a key component of our approach, as reflected in the title and algorithm name.\n\n\n*[1] Machine learning at the network edge: A survey. Murshed, MG Sarwar, et al. ACM Computing Surveys (2021)*\n\n*[2] Visual Wake Words Dataset. Aakanksha Chowdhery, Pete Warden, Jonathon Shlens, Andrew Howard, Rocky Rhode. Arxiv: 1906.05721 (2019).*\n\n*[3] Dynamic Neural Networks: A Survey. Yizeng Han, Gao Huang, Shiji Song, Le Yang, Honghui Wang, Yulin Wang. IEEE Transactions on Pattern Analysis and Machine Intelligence (2022).*\n"}, {"review_id": "3FKjgUfiJT", "reviewer": "Reviewer_nVQk", "summary": "This paper studies the problem of \"progressive distillation\": Given a large teacher model, the task is to decompose into smaller student model so that progressively evaluating additional models in this ensemble results into more accurate predictions. \n\nΤhe main contributions of this paper are:\n\n(i) A principled approach called B-DISTIL for approaching the progressive distillation problem: The authors formulate a two player zero-sum game, from which they derive a weak learning condition. B-DISTIL approximately solves this game.\n(ii) Theoretical guarantees for the proposed approach under certain assumptions.", "questions": "Is there a simple (maybe standard Knoweledge-Distillation-based) baseline that is meaningful to compare against?  \n\nFor example, in Lines 70-72 the authors mention that \"when performing distillation onto a weighted combination of ensembles, it has been observed that adding additional models into the ensemble does not dramatically improve performance over that of a single distilled model\".\n\nWhile this could be the case, could such an approach be used as a simple baseline for this setting, so that one could see what are the trade-offs between implementing a simple approach and potentially improving performance by implementing a more sophisticated one like the one proposed by the authors?  (I understand if the answer is \"there's no simple way to approach this problem\", but maybe then perhaps this should be mentioned more explicitly.)\n", "limitations": "The authors have explained the limitations of their work.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Principled approach with theoretical guarantees that seems to perform well in real-world settings.", "weaknesses": "The proposed approach seems somewhat sophisticated — perhaps not very easy to implement even. By reading the paper, it was not clear to me whether there exists a simpler (but non-idealized) baseline that could be used for comparison — mostly to reassure the reader that the introduced sophistication is actually necessary. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your helpful comments and feedback.\n\nAlthough our algorithm seems sophisticated, we note that most of the additional sophistication (on top of standard boosting) is restricted to FIND-WL sub-routine. Conceptually, the high-level algorithm has the same flavor as many boosting methods, where the existence of a subroutine equivalent to `FIND-WL` is assumed without specifying details.  However, scaling to large training datasets is non-trivial even for standard boosting due to the weight-matrices. The ImageNet scale experiments demonstrate the scalability of our implementation, where we use various techniques (example, streaming weights off-disk asynchronously [code: `ddist.data:DataFlowControl`], performing weight updates in log-space [code: `ddist:ClfPlayer.log_space_update()`], using a shared-memory object store [code: `ddist.dispatch` utilizing the `ray` backend]) to manage compute requirements.  \n\nRegarding baselines, a simple baseline that only uses traditional distillation is the baseline consisting of many small distilled models, sequentially evaluated till interrupted. We have included this baseline, which we call \"RESCHED\", in our experiments (Figure 2). Generally, such an approach, which is basically a weighted combination of distilled models, is known to be not very effective. We will make this more explicit in the main draft."}, {"review_id": "Pnb7Axcwpw", "reviewer": "Reviewer_HW4G", "summary": "The paper addresses the problem of obtaining an ensemble of small models suitable for flexible inference requirements and anytime inference, somewhat similar to cascading classifiers. A key contribution is the derivation of a weak learning condition for the distillation of a pre-trained to an ensemble of smaller students as well as an algorithm to obtain such an ensemble. The students are allowed to reuse intermediate activations of other students to efficiently expand the student model hypothesis set. The method is supported by theoretical results on the generalization error, and empirical results on classification tasks for both synthetic, vision, and sensor data.", "questions": "Generally, my largest concern is the lack of other baseline methods for the empirical results and the unclear computational requirements during training.\n\nAdditionally:\n- In Section 5.3 (and Figure 2) it appears that FLOPs are converted to inference time, but it is unclear how, and if this conversion actually holds for an actual implementation. Consider measuring the actual inference time instead.\n- Clarify the computational requirements during training. What is the overhead on memory and training speed when storing and loading activations and $K$-matrices?\n- Include common distillation techniques and other methods for early-exit or anytime inference as baselines. E.g. it is unclear how NO-RESHED compares to other distillation schemes with appropriately sized students, or if existing anytime inference techniques surpass the proposed.\n\nMinor:\n- Some dimensions of e.g. $x_i$ and $f(x_i)$ are not clear from the paper (but can be deduced), and e.g. in L119, what indices are $j$ summing over? Consider introducing dimensions more clearly early on.\n- Figure 2: Since the $x$-axis is the fraction of teacher inference time, the teacher should be marked by a dot and not a line, since the teacher is not able to perform inference at every possible inference time. It should be clear that the teacher is not flexible in inference time.", "limitations": "Sufficiently addressed.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well-written, clear, and well-organized. It is mostly easy to follow and understand the argumentation.\n- The proposed technique is supported both theoretically and empirically, which is a strong feature.", "weaknesses": "- The computational requirements during training are unclear. Since Algorithm 2 requires the fitting of potentially multiple models to obtain each student it appears to potentially be quite expensive (especially with large $R$ and/or large `max-search`), but this is not addressed explicitly in the paper\n- The dimensions of $K_t^-$ and $K_t^+$ are $N \\times L$ and especially for large $N$, this could be a bottleneck during training (granted, for a mini-batch this is less severe). Furthermore, while reusing stored activations of previous students in subsequent students might keep the parameter count stable, it also requires additional memory and carefulness in which activations to store. Thus there is some overhead on storing and loading activations and $K$-matrices throughout training.\n- The empirical results are weak at comparing to other baseline methods, and the method is struggling at the TinyImageNet and ImageNet-1k tasks, where additional inference time is required compared to the teacher.\n\nMinor:\n- L14/15: Claiming distillation is a rigid procedure seems too bold, as a multitude of distillation techniques exists providing options to obtain lots of different students. Granted, most are aimed at obtaining a single student, but distillation in general is very flexible.\n- L121: \"proabability\" -> \"probability\"\n- Algorithm 1: $R$ is not specified in the algorithm, but needs deduction from Section 3.3\n- Inconsistent use of RESCHED and RESHED\n- Formatting of B-Distill and E-RNN are inconsistent in different places in the paper (e.g. L300-309).\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive feedback and questions.\n\n**Inference time calculations.** The inference time numbers are end-to-end numbers reported by the DeepSpeed profiler on NVIDIA 3080Tis. The No-RESCHED baseline is used as an idealized baseline, and a modified version trained using distillation will improve on the numbers reported now. In both cases, we expect this baseline to be better than B-DISTIL. We use the training based baseline instead of the distillation as the teacher model is a natural case of baseline at `frac_inf = 1.0`.\nLarge values of `max-search` could indeed lead to an increase in training times if FIND-WL fails often, which is not typically a concern for larger models (later rounds). Models in earlier rounds are often relatively small, and we do see additional time required for training as for these models the data movement often becomes the training bottleneck.\n\n**Scalability and compute requirements.** Although B-DISTIL takes additional inference time to make accurate predictions for ImageNet, the teacher models in this case have 100+ layers. Tasks in efficient inference that rely on smaller models for image datasets, or scenarios (e.g., edge inference) involving sensor/audio data streams, are key application areas that stand to benefit from B-DISTIL. However, even at larger scales, where the data distribution during inference is skewed towards 'easier' samples, B-DISTIL can be advantageous in the average case, as the majority of the predictions can be completed quickly (Google-13, Table-1, T=50%). In fact our goal in providing the ImageNet scale experiments was to demonstrate scalability of our implementation, especially since maintaining and updating the weight-matrix of a 1000 class, 1M training image dataset can be non-trivial. We will clarify this in the main text and add a discussion about the techniques we use to manage compute requirements (example, streaming weights off-disk asynchronously [code: `ddist.data:DataFlowControl`], performing weight updates in log-space [code: `ddist:ClfPlayer.log_space_update()`], using a shared-memory object store [code: `ddist.dispatch` utilizing `ray` backend]) in the appendix.\n\n**Baseline methods.** The NO-RESCHED baseline is trained using standard distillation on the same model structure used by B-DISTIL. If we were to compare the models at fixed $T$, a single model trained using standard distillation techniques does outperform B-DISTIL (Figure 2) especially for later rounds. However, this baseline cannot be deployed in practice for anytime inference as it requires knowledge of available inference time upfront to pick the ‘right model’. We demonstrate that B-DISTIL remains competitive to this baseline while being realizable in practice. As for early prediction, the E-RNN method we compare against (Table 1) is a standard method used for early prediction in sequential inference. We will clarify these points in the main draft. \n\n\n**Minor.** Thank you for the suggestion on the horizontal line for the teacher model and other corrections/typos, which we will carefully address in our revision. We will also revise the draft to use only one unit of measurement, and improve and move details about the profiling step to the main draft. Thanks very much for these suggestions to improve presentation.\n"}]

Author rebuttal:

Meta-review: The paper studies the problem of progressive distillation which requires distilling a large pre-trained model into a series of smaller student models such that one can employ a composition of a subset of student models at the runtime to realize the desired inference cost vs. accuracy trade-off. Towards this, the authors propose B-Distill to progressively learn "weak learners" via distillation. Interestingly, the authors allow a particular student model in the progression to leverage the output of intermediate layers of the earlier models in the progression.

Both theoretical and empirical results validate the utility of the proposed progressive distillation method. B-Distill is evaluated on multiple real-life domains (vision, speech, and sensor data) and multiple model architectures are explored. The author presents results for both any-time prediction and early-exit settings. 

All of the reviewers acknowledged the value of the contributions in the submission. The reviewers were able to successfully address the key concerns/questions raised by the reviewers during the rebuttal phase. The reviewers made multiple suggestions to improve the quality of the presentation. The authors have promised to incorporate these suggestions in the revised version of the submission. They are strongly advised to act on these suggestions while preparing the camera-ready version. Some of the key points are as follows:

1) Expand the discussion of prior work to include results on pruning, e.g., slimmable networks.

2) Properly introduce various notations before their usage.

3) Provide the necessary background on the connection between boosting and two-player games, as well as how it precisely connects with the proposed method.

4) Improve the discussion of experimental results and highlight how various natural baselines suggested by the reviewers are already covered by the existing results.
Decision: Accept (poster)