Progressive Knowledge Distillation:  Constructing Ensembles for Efficient Inference
Authors: Don Dennis
Abhishek Shetty
Anish Prasad Sevekari
Kazuhito Koishida
Virginia Smith
Venue: Submitted to ICLR 2023 (2023)
Keywords: progressive distillation
anytime inference
efficient inference
resource constrained ML
devices

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 distillation: Given a large, pretrained teacher model $g$, we seek to decompose the model into an ensemble of smaller, low-inference cost student models $f_i$. 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 $g$ 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.

Under review as a conference paper at ICLR 2023
PROGRESSIVE KNOWLEDGE DISTILLATION: BUILDING ENSEMBLES FOR EFFICIENT INFERENCE
Anonymous authors Paper under double-blind review
ABSTRACT
We study the problem of progressive distillation: Given a large, pre-trained teacher model g. we seek decompose the model into an ensemble of smaller, low- inference cost student models fi. The resulting ensemble allows for flexibly tuning accuracy vs. inference cost, which can be useful for multitude of applications in efficient inference. Our method, B- B-DISTIL, uses algorithmic procedure that uses function composition over intermediate activations to construct expressive ensembles with similar performance g, but with 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.
INTRODUCTION
Knowledge distillation aims to transfer the knowledge of large model into a smaller one (Buciluă al., 2006; Hinton et al., 2015). While this technique commonly used for model compression. one downside is that the procedure is fairly rigid- resultinu in a single compressed model of fixed size. In this work, we instead consider the problem of progressive distillation: approximating a large model via ensemble of smaller, low-latency models. The resulting decomposition is useful for number of applications in efficient inference. For example, components of the ensemble can be selectively combined to flexibly meet accuracy/latency constraints (Li et al., 2019; Yang & Fan, 2021), can enable efficient parallel inference execution schemes, and can facilitate early-exte exit (Bolukbasi et al., 2017; Dennis al., 2018) or anytime inference (Ruiz & Verbeck, 2021: Huang et al., 2017a) applications, which are scenarios where inference may be interrupted due to variable resource availability.
More specifically, we seek to distill large pre-trained model, 9. onto ensemble comprised of low- now-parameter count, low-latency models, fi. We additionally aim for the resulting ensemble to form decomposition, such that evaluating the first model produces a coarse estimate of the prediction (e.g.. covering common cases), and evaluating additional models improves on this estimate (see Figure 1). There are major advantages to such an ensemble for on-device inference: 1) inference cost vs. accuracy trade-offss can be controlled on-demand at execution time, 2) the ensemble can either be executed in parallel or in sequence, or possibly mix of both, and 3) we can improve upon coarse initial predictions without re-evaluation in response to resource availability.
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 (Mirzadeh et al., 2020; Gao et al., 2021). Moreover, distillation of a deep network onto a weighted sum of shallow networks rarely performs better than distillation onto a single model (Cho & Hariharan, 2019; Allen-Zie Zhu & Li, 2020). Our method exploits connections to minimax optimization and online learning (Schapire & Freund, 2013) to allow models in our ensemble to compose and reuse intermediate activation outputs of other models during inference. As long these composition functions are resource efficient, can increase base class capacity at roughly the same inference cost as a single model. Moreover, we show that our procedure retains the theoretical guarantees of these methods (Schapire & Freund, 2013). Concretely,
We formulate progressive distillation as two player zero-sum game, derive weak learning condition for distillation and present our algorithm, B- E-IISTIL, to approximately solve this game. To make the search for weak learners in low parameter count models feasible, we explicitly solve

---

Under review as a conference paper at ICLR 2023
Teacher Model
Sludent Models
Progressive Distillatinn
N
Figure 1: In progressive distillation, large teacher model is distilled onto low inference cost models. The more student models we evaluate, the closer the ensemble's decision boundary is to that of the teacher model. Models in ensemble are allowed to depend on previously computed features.
a log-barrics based relaxation of our weak learning condition. Moreover, by allowing models to reuse computation from select intermediate layers of previously evaluated models of the ensemble, we are able to increase the model's 's capacity without significant increase in inference cost.
We empirically evaluate our algorithm on synthetic as well as real-world classification tasks from vision, speech and sensor data with models suitable for the respective domains. We show that our ensemble behaves like a decomposition, allowing a run-time trade-off between accuracy and computation, while remaining competitive to the teacher model.
We provide theoretical guarantees for our algorithm terms of in in-sample convergence and generalization performance. Our framework is not architecture or task specific and can recover existing ensemble models used in efficient inference, and we believe puts forth a general lens to view previous work and also to develop new, principled approaches for efficient inference.
BACKGROUND AND RELATED WORK
Knowledge distillation. Machine learning inference is often resource-consine constrceconsttraieed in practice due to requirements around metrics such as memory, energy, cost, or latency. This has spurred the develop- ment of numerous techniques for model compression. A particularly popular approach is knowledge distillation, which considers transferring the knowledge of larger model (or model ensemble) to a smaller one (Buciluă al., 2006; Hinton al., 2015). Despite its popularity, performing compression via distillation has several known pitfalls. Most notably, many have documented that distillation may not perform well when there is capacity gap between the teacher and student, i.e., the teacher is significantly larger than the student (Mirzadeh et al., 2020; Gao et al., 2021; Cho & Hariharan, 2019; Allen-Zhu & Li, 2020). When performing distillation onto weighted combination of ensembles. has been observed that adding additional models into the ensemble does not dramatically improve performance over that of single distilled model (Allen-Zhu & Li, 2020). There is also lack of theoretical work characterizing when and why distillation is effective for compression Gou et al. (2021). Our work aims address many of these pitfalls by developing a principled approach for progressively distilling large model onto an ensemble of smaller, low-capacity ones.
Early exits and anytime inference. Numerous applications stand to benefit from the output of progressive distillation, which allows for flexibly tuning accuracy vs. inference cost and executing inference parallel. Enabling trade-offs between accuracy and inference cost is particularly useful for applications that use early exit or anytime inference schemes. In 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 (Dennis al., 2018; Bolukbasi et al., 2017). For instance, a battery powered device continuously listening for voice commands can use early exit methods to improve battery efficiency by classifying non-command speech quickly. Many methods that produce early exit models are also applicable to anytime inference (Huang et al., 2017a; Ruiz & Verbeek, 2021). In anytime inference, the aim is to produce prediction even when inference is interrupted, say due to resource contention or a scheduler decision. Unlike early exit methods where the classifier chooses when to exit early, anytime inference methods have no control over when they interrupted. We explore the effectiveness of using our method, B- B-DISTIL, for such applications in Section 5.
2

---

Under review as a conference paper at ICLR 2023
Two-player games, online optimization and boosting. The importance of equilibrium of two player zero-sum games has been recognized since the foundational work of von Neumann and Morgenstem (von Neumann & Morgenstem, 1944). Their connections convex programming duality have lead to many developments in algorithm design, theoretical computer science and machine learning (Lugosi & Cesa-Bianchi, 2006; Goodfellow et al., 2014). One astounding application is by Schapire (1990) and Freund (1990) who showed that weak learners can be aggregated to produce strong learners. This has led many practical boosting based learning algorithms and software such as AdaBoost (Freund& & Schapire, 1997), gradient boosting (Mason et al., 1999), and XGboost (Chen Guestrin, 2016). An application of boosting that is similar to our setup is by Trevisan et al. (2009). They show that given a target bounded function y. and class of approximating functions F, one can approximate y arbitrarily well with respect to F using ideas from online learning and boosting. Although boosting has led to many theoretical and practical advances, these efforts have only recently seen success in deep learning applications. In particular, Suggala et al. (2020) propose a generalized boosting framework to extend boosting to deep networks using function compositions in feature space. The intermediate connections we (Section 3) is an extension of their approach.
3 PROBLEM FORMULATION AND ALGORITHM
We start by formulating our distillation task as a two player zero-sum game and introduce the framework of stochastic minimax optimization. Consider a class of hypotheses F, a class of probability distributions P and a loss function L that is convex in its first argument. We consider two players whose pure strategy sets are F and P respectively, with loss (and reward) of the players given by F Ff.p)) = Ex-p [x=ppA([ x)). This naturally leads to the definition of the minimax value of the game given by
max min F (J.p). PEP JEF
Note that this game is convex in the hypothesis player (min-player) and concave in the distribution player (max-player) and thus amenable to algorithmic approaches. An algorithm said to (ap- proximately) solve the above minimax problem if it produces a distribution over hypotheses and distribution that achieve the value in Equation (1). In order for the problem to be well-defined, we need to specify the access the algorithm has to the F and P. One general notion is to allow access to a weak gradient vector such that, when queried at distribution μ E P and for B > 0,
F ((.P)) 2 3,
The advantage of this lens is that many algorithms can be seen as implementing solutions to such minimax optimization problems. See Appendix A for a more involved discussion.
Although, eq. (2) is a seemingly easier notion than the full optimization, we emphasize that 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 reliable and efficiently finds these weak gradients. Our method FIND-WL provides a way to do this successfully as demonstrated in our experimental setup, across a variety of datasets.
For the setting of our interest, we will restrict our attention the case where P is the set of all distributions over a sample set drawn from a fixed distribution p and, differ the details of the general framework to the Appendix. As in traditional distillation we will work with the output of g, often referred to as logits. Our goal is to produce an ensemble of predictors from the set of hypothesis classes {Fim. } to approximate g 'well'. We will do this by searching for weak learners with respect to the target g in the class Fm. Whenever this search fails we restart the search, now allowing models in F.. to reuse features computed by previous models.
To cast our progressive distillation problem as a two player game, we start with a predictor (a model or an ensemble) g X' + 12_ already provided us along with a non empty set of low inference ' hypothesis class J We assume that {Fm} } is in increasing order of inference cost. The loss function of interest then is E.,s (J(x;) g(x;)) which is the total squared error between the
Useers can define 'inference cost' in terms of memory requirements compute requirements based on their use-case, We only assume (F,) is ordered on this metric.
3

---

Under review as a conference paper at ICLR 2023
two predictors. Given training set {2,}, think of the role of the max player in eq. (1) to produce distributions over the training set and the role of the min player to produce hypothesis that minimizes the loss this distribution. In this setting, note that P {o RNxL, paj 2 0 Vj Pi. 1) the product of simplices in N x dimensions, and
(&PP(ID)) = Epss (f(ai) g(x)));
(3)
Algorithm B-DISTIL: Main algorithm
Require: Target 9, rounds 7', data {(T;, Wi) learn-
Algorithm 2 FIND-WI.
ing rate 17, model classes {Fm M
Require: Probability matrices K+ K- model class F parameterized by 0 E θ, hyper-parameters for SGD
1: K," (i, K, (i.5)= + 2N 2N
v(i,j)
2: F,r,t f 0, 1,
3:
while r < R and t < do
1: Obtain (FF)) by expanding F (sec- tion 3.2).
4:
fi FIND-WL(K,, (K, KT Fr)
5:
if ft NONE then
2: for F' E (FF) do
6:
r+
3: Initialize initial parameter 0g E F'.
7:
continue
4: for i {l...., max-search) do
8:
end if
9:
With | = fo 9, update KT. Kj. V(i,)
Randomly initialize fe. 6: Run SGD to solve Equation 6.
5:
K241 (1,5) + K2' (i, exp(px) ((x))))
(4)
fo, is a weak learner then; return fo. 9: end if
7:
8:
((.1(1))) Kū exp(1 (xx))))
(5)
10: end for
10: Normalize Ki+ K;.
11: F FU [fe),
11: end for
12: end while
return NONE
return |F EMA fr
Concretely, at each iteration I, the algorithm maintains a matrices K2 E RNXL and K2 E R 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 K2 are such that for all j E [L], Σ, Kt (i. + K, (i,j) 1. Moreover, for all (i.j) E [N] [L], S K (i, K2 (1,5) S The elements K2 (i,j) and K, (i,j) can be thought of as the weight on the residuals ft-1(x) - gg()) and g(x) f1-1 (z:) respectively, up-weighting large deviations from g(x).
)
In order make updates this vector, we need access to a weak gradient similar We formalize this using Definition I, which can be seen natural extension of the standard weak learning assumption the boosting literature to our setting.
Equation (2).
Definition 1 (Weak learning condition). Given dataset {( H target function g : X -+* R- and probability matrices K.,, KT, function Se. X + R$ is said to satisfy the weak learning condition with respect to g for j.
Ext -g())) ΣxT (1.)))())) 0
With the current probability matrices KT. K²" in each round t, B- B-DISTIL performs two steps; first, it invokes a subroutine FIND-WL that attempts to find classifier ft E F, satisfying the weak learning condition (Definition 1). If such predictor is found, we add it to our ensemble and proceed to the second step updating the probability matrices K; K2 based on errors made by ft. This similar in spirit to the boosting algorithms such as AdaBoost (Schapire & Freund, 2013) for binary classification. If no such predictor can be found, we invoke the subroutine with the next class, F,11 and repeat the search till weak learner is found or we have no more classes to search in.
3.1 FINDING WEAK-LEARNERS
As mentioned earlier, the real difficulty in provably boosting in this setting is in finding a single learner fi round / that satisfies weak learning condition simultaneously for all labels, j. Existing
4

---

Under review as a conference paper at ICLR 2023
boosting methods for classification treat multi-class settings (L > 1) L instances of the binary classification problem (one vs all) (Schapire & Freund, 2013). 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. In our work, we focus this aspect of the problem. Thus, along with controlling temperature for distillation, we employ two additional strategies; a) we use log-barrier regularizer in the objective FIND-WL solves promote weak learning and, b) reuse limited stored activation outputs of previously evaluated models to increase the expressivity of the current base class.
3.1.1 LOG-BARRIER REGULARIZER
To find a weak learner, the FIND-WL WL method solves the optimization program in Equation using stochastic gradient descent.
min
Σ Eunuu(((at))) fer
Σ γ
Jt log (1+
(xxi))
2B ) + (1 1 log (1 1(x;))
2B )
(6)
Here, we define 1 = I|K (1.5) BT max{ |[(x)]1 for all x, and ((x;)
fx;) - g(x)). The first term is task specific loss between f(x;) and g(x;). For our binary and multi-class experiments, we use the standard binary/multi-class cross-entropy distillation loss function (Hinton et al., 2015), with temperature smoothening. To see the intuition behind the second term, first assume the following is true for all (i.j).
(Kt (i.J) K2 (1, (I;)) g(z;)); > 0.
Summing over all data points zú, we can see that this sufficient for f to be a weak learner with respect to gi for all j.
Esst - KT (x)))))))()))) - -g(x))) >
(8)
- g(xi))s + EKT fx(x))) > 0.
The second term in Equation 6 is solving a soft log-barrier version of the weak learning condition of Equation 7, that penalizes those (i,j) for which Equation 7 does not hold. By tuning 7 we can increase the relative importance of the regularization objective, encouraging ft to be weak learner potentially at the expense of task performance.
3.1.2 INTERMEDIATE LAYER CONNECTIONS
As mentioned in Section 2, distillation onto linear combination of low capacity student models, often offers no better performance than that of any single model in the ensemble trained independently. For boosting, empirically we see that once the first weak learner has been found in some class Fm, of low-capacity deep networks, it is difficult to find weak learner for the reweighed objective from the same class Fm. To work around this we let our class of weak learners at around / to include functions that depend on output of intermediate layers of previous weak learners (Suggala et al., 2020).
As concrete example, consider a deep fully connected network with layers, parameterized as = W W&w.. Here @icu can be thought of as feature transform on using the first layers into Rd= and W E 1 is a linear transform. With two layer fully connected base model class Fo = (W( 100 ((() E RLLx22] (dropping subscript m for simplicity), define
J. = (w())))) (id ((= and F.P (W(r 02 (id + of² + 1 "
with id(z) : It can be seen that {F.} and {F.} define variant of residual connection based networks (Huang et al., 2017b). can be shown that classes function (F.) (and (F(} increase in capacity with r. Moreover, when evaluating sequentially the inference cost of 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.
5

---

Under review as a conference paper at ICLR 2023
We informally refer to the process of constructing {Frr given choice of base class Fu, the parameter R and the connection type as expanding Fu- In our experiments, we consider four connection functions: dense connections (He et al., 2016), gated-connections (Hochreiter & Schmidhuber, 1997) and GRU (Cho et al., 2014) gated connections and other accumulation operations, and consider R hyper-parameter.
(Huang et al., 2017b), LSTM
Note that while intermediate connections help with capacity, they often reduce parallelizability. For instance, weak learners from F" defined here depend on the output of (fixed) learner from F, and thus can only finish its inference after the previous models is evaluated. As practical consequence dependencies on activation outputs later layers are preferred, as this allows us more freedom in choosing execution schemes (see Appendix C).
4 THEORETICAL ANALYSIS
In this section, we provide theoretical analysis and justification for our method. We first prove in sample convergence guarantees; we will show that the ensemble output produced by algorithm 1 converges g at (1/VT) rate, provided that the procedure FIND-WL succeeds at every time t.
Theorem 1. Suppose the class F satisfies that for all f F, llf gll> S. G Let F = {fi} be
T the ensemble after T rounds of Algorithm with the final output F, } Et If ft satisfies
eq. for all t S ' then for T 2 In and = Go
1
1n
we have for all
In2N
|F. gilloo S Go0
(10)
T
where Fe, and gj are the jth coordinates of the functions Fe and g respectively.
We differ the details of the proof to the Appendix B. The main idea behind the proof is to bound the rate of 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, also show that the algorithm has strong out of sample guarantee. We show this by bounding the generalization error of 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 general result follow along similar lines.
Let Cr denote the class of functions of the form H(x) sign( + E'= (x)))) where by are functions in class F. Then we have the following generalization guarantee:
Theorem 2 (Excess Risk). Suppose data D contains of N iid sumples from distribution D. Suppose
that the function has margin on data D with probability μs, that is Prz [[g(z)] < < p.
Further, suppose that the class Cr has VC dimension d. Then, for T 2 4G2 In 2N/e" with probability over the samples, the output Fr of algorithm satisfies
err(Fr) S err(g) +0 (V (Valm(A/aa) N
ddln(//d) + lm(1/8) の
Note that the above theorem easily be adapted to the 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 as stochastic gradients to the population objective. This is for example the view taken by Suggala et (2020). our work, we separate the population and sample bounds to simplify the presentation and the proofs.
Remark 2.1. We further emphasize that though the exact bound that appear in Theorem and Theorem 2 depend on our particular algorithm, the forms and the general flavor of the guarantees of the theorems are general amongst algorithms solving stochastic minimax problems. For example, the theorems of Suggala et al. (2020) be captured by our framework.

---

Under review as a conference paper at ICLR 2023
5 EMPIRICAL EVALUATION
In this section, we evaluate B- B-DISTIL on both real world and simulated datasets, and over a variety of architecture types. We consider four real world datasets across three domains-visionn speech and sensor-data-as well two simulated datasets. This allows to evaluate our method on five of architecture types: fully connected networks, convolutional networks, residual networks, densely connected networks and recurrent networks.
5.1 DATASET INFORMATION
For experiments with simulated data, we construct two datasets. The first dataset, referred as ellipsoid is binary classification data set. Here the classification labels for each data point E IR:32 is determined by the value of x!' Axr for a random positive semidefinite matrix A. The second simulated dataset, cube, is for multiclass classification with 4 classes. Here labels are determined by distance to 16 randomly selected vertices from {-1, 1 R2 randomly partitioned into 4 classes.
We use four real world data sets for our experiments. Our image classification experiments use the CIFAR-IO and CIFAR-100 datasets. For spoken-audio classification tasks we use the Google-13 speech commands dataset. We use the daily sports activities (DSA) dataset for experiments with sensor data. Detailed information of all datasets used, including source, size and processing steps, along with synthetic data generation steps be found in Appendix C.
5.2 MODEL ARCHITECTURE DETAILS
Teacher models. We use deep fully connected (FC) networks for classification on Ellipsoid and convolutional networks for Cube. For image classification on CIFAR-1O dataset we use publicly available, pretrained ResNet models. We train reference DenseNet models for the CIFAR- R-0 dataset based on publicly available training recipes. As both spoken audio data (Google-13 133) and sensor-data (DSA-19) are time series classification problems, we use recurrent neural networks (RNNs) for these experiments. We train LSTM (Hochreiter & Schmidhuber, 1997) based architecture on Google-13 and GRU (Cho et al., 2014) based architecture on DSA-19. Except for the pretrained ResNet models, all other teacher models are selected based performance 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 starting with significantly fewer parameters and resource requirements. We train for at most T rounds, keeping 1) = in all our experiments. Whenever FIND-WL 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 small values of R (say, 2). The details of the intermediate connections used for each data-set and hyperparameters such as 7, hyper-parameters for SGD can be found in Appendix and D.
7 weak learners, we can pick
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 top-1 classification accuracy and total floating point operations (FI.Oss) required for inference. We use a publicly available profiler (Rasley al., 2020) measure floating point operations. For simplicity of presentation, we convert these to the corresponding inference times (T) on a reference accelerator (NVIDIA 3090Ti).
Anytime inference. As discussed previously, in the anytime inference setting model is required to produce prediction even when its execution 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 ahead of each execution. Under this assumption, we can train set of models suitable various inference time constraints, say by training models at various depths, and pick the one that fits the current inference budget obtained by querying the oracle. We refer to this baseline NO-RESHED and compare B D-DISTIL to it on both synthetic and real world datasets in Figure 2. This idealized baseline establishes upper bound on the accuracy of B-DISTII.
7

---

Under review as a conference paper at ICLR 2023
FC-32.32.64
FC-16,16,16
ResNet56
Accuracy (%6
90-
90
90
B DSTILL
NORESHED RESHED
80
85
80
Teacher
70
80
0.1
0.2
0.3
0.25
0.75 frac. inference time
0.50
0.0
0.5
1.0
frac. inference time
frac. inference time
(a) Cuhe
(b) Ellipsoid
(c) CIFAR-I0
DenseNet121
LSTM128
GRU32
Accuracy (%6
70
90-
86
80
84
60
70-
82
60
0.2
0.4
0.6
0.0
0.4
0.6
0.2
0.4
frac. inference time
frac. inference time
frac. inference time
(d) CIFAR-100
(c) Google-13
(f) DSA-19
Figure 2: Accuracy inference-tine trade-off. Inference time is reported as fraction of teacher's inference time. B-DISTIL performs this trade-off at runtime. The baseline NO-RESHED at inference time Tu (I-axiis) is the accuracy of a single model that allowed T - time for inference. Similarly the baseline RESHED at Tu is the accuracy of an ensemble of models, where the ensemble is such that model requires T Tw-1l time perform its inference. We that B-DISTIL remains competitive to the oralce baseline (NO-RESCHED) and outperforms weighted averaging (RESCHED).
Dataset
Algorithm
Early-prediction Acc
T
50%
T
75%
T
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 DISTIL the E-RNN algorithm (Dennis et al., 2018). The accuracy and the cummulative fraction of the data early predicted at 50%, 75% and 100% time steps shown. At T 100, frac. evaluated is 1.0. The ensemble output by B-DISTIL with the prey-prrdiotion loss is competitive to the E-RNN algorithm, method developed specifically for early prediction of RNNs.
B-DISTIL can improve on its initial prediction whenever inference jobs are allowed to be rescheduled. To contextualize this possible improvement, consider the where the execution is interrupted and rescheduled (with zero-latency, for simplicity) at times {T1, T2.... TW }. We are required to possible Tw--1-- Sequentially evaluate them and at each interrupt Tw. output the (possibly weighted) average prediction of the to models. We call this baseline RESCHED. Since the prediction at Tw is a simple average of models, we expect its performance serve lower-bound for the performance of B- DISTIL. In the same Figure (Figure 2) we compare B-DISTIL to the RESHED baseline. Note that both baselines require access inference budget ahead of time.
output prediction at each The Assuming know these interrupt points in advance,
baseline can be as follows: select models with inference budgets [m1], [72 - 7il....,ITu,
Early prediction. To evaluate the applicability of our method for early prediction in online time- series inference, compare the performance of B-DISTIL that of E-RNN from Dennis et al. (2018). Unlike B-DISTIL, which can be applied to generic architectures, E-RNN is a sfate-of-the-ee art method for early prediction that was developed specifically for RNNs. When training, set the task loss
8

---

Under review as a conference paper at ICLR 2023
ResNet56
DenseNet121
LSTM128
GRU32
1.00
Model
0.6
0.6
0.4
Accuaacy
0.4
0.50-
0.25
0.2
0.2
Round
Round (T)
Round (
Round (7)
(a) CIFAR-10
(b) SVNH-10
(c) Google-13
(d) DSA-19
Overhead of connections. The floating point operations required evaluate the model added in round T, compared to that required to evaluate just the connections used by this model, for each of the real-world dataset. FL.OPs are reported as a fraction of teacher model's FL.OPs. We see that the connections add relatively little overhead.
Figure 3:
Lusk in Equation (6) to the early-classification loss used in E-RNN training. We evaluate our method on the time-series datasets GoogleSpeech and DSA. The performance terms of time-steps evaluated is compared in Table 1. B-DISTIL remains competitive to E-RNN algorithm for early-prediction. Unlike E-RNN, B-DISTIL also offers early prediction for offline evaluation of time-series data when all of the data arrives at once. For such cases, a threshold can be tuned similar to E-RNN and B-DISTIL can evaluate the models in its ensemble in order of increasing inference cost, exiting as soon as the confidence-score crosses this threshold.
Overhead of connections. Our method uses intermediate connections to improve its performance. Although these connections are designed to be efficient, they still have overhead cost averaging based ensemble. The FLOPs required to evaluate intermediate connections corresponding to the distillation tasks in Figure is shown in Figure 3. Here, compare the FLOOPs required to evaluate the model that was added in a round to the FLOPs required evaluate the intermediate connections used by this model. Note that summing up all the FLOPs up a round T,, in Figure gives the total FLOPs required to for the ensemble constructed at the end of round T. For all our models, this overhead is negligible when compared to the inference cost of the corresponding model.
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 later case can be thought of as running the AdaBoost algorithm for distillation. Note that this is the same as the RESCHED baseline (simple averaging). Thus comparing the B-DISTIL plot Figure highlights the benefit of using intermediate connections. As in this work our focus is finding weak learners the presence capacity gap, and we do not explore additional compression strategies like quantization, hard thresholding, low-rank projection that can further reduce inference cost.
the plot of RESCHED
CONCLUSION AND FUTURE WORK
In this paper, propose B-DISTIL, an algorithm for progressive distillation. B-DISTIL produces an ensemble learners that provide efficient inference, with progressively better results as the ensemble size increases: this allows for straightforward way to trade off accuracy and compute at inference time, in cases where inference may be interrupted abruptly, or when variable levels of accuracy expected. We experimentally demonstrate the effectiveness of B-DISTIL by decomposing well established deeper models onto ensembles over a variety of problem domains. The procedure leverages stochastic solver combined with log barrier regularization for finding weak learners during distillation. Further, we circumvent the issue of model capacity by using intermediary connections.
key insight this work is that posing distillation as two player zero-sum game allows us to abstract away model architecture details into base class construction F. This means that, conditioned on us finding 'weak learner' from the base class, we retain the guarantees of the traditional boosting setup. A caveat of this abstraction is that the user must design F. In future work, we would like to extend these ideas by running boosting-lite together. Similar methods have recently found success in applications such hyperparameter tuning for federated learning (Khodak et al., 2021).
procedures on model and hyperparameters taken


Reviews:
[{"review_id": "tI2lT7TiiJ", "reviewer": "Reviewer_kWeE", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the problem of progressive distillation, which is defined as approximating a large model with an ensemble of multiple small models. The paper poses this problem as a two-player zero-sum game where a “distribution player” poses a distribution over example assignments to learners to maximize loss, and the “hypothesis player” chooses hypotheses for each learner to minimize loss.", "summary_of_the_review": "I think the problem setting and method is interesting, but the experimental evaluation is somewhat weak.", "strength_and_weaknesses": "The problem setting is interesting and well-motivated. Standard distillation (one big model to one small model) is likely to result in underfitting, whereas considering an ensemble of small models increases the capacity while ideal latency can be kept low through parallelization.\n\nThe intermediate layer connection idea (section 3.1.2) is interesting - instead of just considering a bigger model class, you can start from embeddings from previous generation nets; this is probably better for when you want to do early-exit or anytime inference with limited compute.\n\nIn experiments, the paper reports benefits in six different datasets, each with different network architectures. However, I think the evaluation would be more convincing if it considered more baselines such as a basic boosting algorithm.\n\nMinor comment: the paper says “SVNH dataset” repeatedly; is this a typo for SVHN (Street View House Numbers)?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "tAkbOlmVPl", "reviewer": "Reviewer_9Tcs", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper introduces a method (B-DISTILL) to distill an (expensive) trained model into an ensemble of weak learners. These learners are meant to provide efficient inference, with progressively better results as the ensemble size increases: this allows for a straightforward way to trade off accuracy and compute at inference time, in cases where inference may be interrupted abruptly, or when variable levels of accuracy are expected.\n\nThe distilled ensemble is obtained by solving a two player zero-sum game, with convergence and generalization bounds provided under weak assumptions. In order to the $n+1$-th model to refine the prediction of the previous $n$ models, the authors also allow each successive model to _reuse_ the feature transformation of the previous ensemble member.\n\nExperimentally, authors verify their method on simulated, vision, speech, and sensor-data classification tasks, and across a variety of architectures.", "summary_of_the_review": "This paper addresses an interesting problem (distilling a model into an ensemble of weak learners to control inference cost and accuracy trade-offs). Taking a game theory approach, authors introduce an algorithm with convergence guarantees, and show experimentally that their approach successfully trades off computational costs with model accuracy. \n\nHowever, I found it quite difficult to understand the detail of the experimental results, and of the baselines in particular. This work would be very much strengthened by a clearer experimental section, and the inclusion of baselines from the multiple-instance learning / anytime inference literature.", "strength_and_weaknesses": "# Strengths\n- The paper is very well written, and the exposition is overall clear (aside from issues with baselines and $K$ matrices mentioned below)\n- The method has a clear application and is of similarly clear value to the community (anytime and efficient inference).\n-  The authors provide convergence guarantees ($\\mathcal O(\\sqrt{\\ln 2N / T})$ for $T$ the ensemble size and $N$ the dataset size)\n\n# Weaknesses\n- The description of the experimental baselines should be much clearer. As it stands, I found it difficult to be certain whether the authors consider Fixed-model to be an ensemble (which appears to be the case), and how successive ensemble members differ from each other.\n- It does not appear that the authors included early exit baselines; it would strengthen the paper significantly to compare to work such as (Dennis et al., 2018), despite the fact that such work is not distillation based.\n- The Figures (and Figure 3 in particular) are difficult to view (due to size, even on a screen and zooming in), and to understand in general. Am I correct in understanding that round $T$ reports the FLOP percentage for an ensemble of size $T$ (assuming each round of FIND-WL succeeds)? For the FLOP analysis, can you confirm that distinction between fixed-model and B-Distill is inconsequential?\n\n# Questions to the authors\n- Could you clarify why you need to split the matrices $K$ into $K^+$ and $K^-$?\n- I'm confused about why $p$ in (3) has is of shape $N \\times L$. I understand that $N$ is for the distribution over samples of the dataset; is the $L$ dimension to reweight the loss for different logit dimensions on each sample?\n- In Theorem 2, is $\\mu$ a distribution (and the inequality stochastic dominance), or a scalar?\n- Experimentally, how often did FIND-WL fail?\n\n# Nitpicks\n- Please add a $y$-axis to Figure 5. Are you reporting accuracy?\n- Consider moving the legend above the sub-figures when possible, to improve readability. \n- Is there an extraneous index $j$ in (3)?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "AoAcBpPNRN", "reviewer": "Reviewer_GAfE", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors propose the problem of progressive distillation: approximating a large model with an ensemble of smaller models. They seek a solution that \\emph{decomposes} the large model, such that the quality of the approximation improves monotonically with the size of the ensemble. They formulate progressive distillation as a two player zero-sum game and present B-DISTIL, an algorithm for solving this game. One notable feature of their algorithm is that it allows models to reuse intermediate representations from other models in the ensemble. They evaluate their algorithm on image classification (ResNets on CIFAR10 and DenseNets on SVHN), speech classification (LSTM on Google-13), and sensor data (GRU on DSA-19). They find that their B-DISTIL-generated ensembles allow favorable tradeoffs between computation time and accuracy.", "summary_of_the_review": "Clever idea, needs more rigorous empirical evaluation. Could be publishable with more thorough experimentation.", "strength_and_weaknesses": "**Strengths**\n\nGood motivation\n\nClever method—reusing intermediate representations within an ensemble is an elegant idea.\n\n**Weaknesses**\n\nExperiments are not very convincing; baselines and benchmarks are insufficient.\n\nMinor clarity issues.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject