Year: 2021

Abstract:
In real-world systems, models are frequently updated as more data becomes available, and in addition to achieving high accuracy, the goal is to also maintain a low difference in predictions compared to the base model (i.e. predictive “churn”). If model retraining results in vastly different behavior, then it could cause negative effects in downstream systems, especially if this churn can be avoided with limited impact on model accuracy. In this paper, we show an equivalence between training with distillation using the base model as the teacher and training with an explicit constraint on the predictive churn. We then show that distillation performs strongly for low churn training against a number of recent baselines on a wide range of datasets and model architectures, including fully-connected networks, convolutional networks, and transformers.

In real-world systems, models are frequently updated as more data becomes available, and in addition to achieving high accuracy, the goal is to also maintain a low difference in predictions compared to the base model (i.e. predictive “churn”). If model retraining results in vastly different behavior, then it could cause negative effects in downstream systems, especially if this churn can be avoided with limited impact on model accuracy. In this paper, we show an equivalence between training with distillation using the base model as the teacher and training with an explicit constraint on the predictive churn. We then show that distillation performs strongly for low churn training against a number of recent baselines on a wide range of datasets and model architectures, including fully-connected networks, convolutional networks, and transformers.
1 INTRODUCTION
Deep neural networks (DNNs) have had profound success at solving some of the most challenging machine learning problems. While much of the focus has been spent towards attaining state-of-art predictive performance, comparatively there has been little effort towards improving other aspects. One such important practical aspect is reducing unnecessary predictive churn with respect to a base model. We define predictive churn as the difference in the prediction of a model relative to a base model on the same datapoints. In a production system, models are often continuously released through an iterative improvement process which cycles through launching a model, collecting additional data and researching ways to improve the current model, and proposing a candidate model to replace the current version of the model serving in production. In order to validate a candidate model, it often needs to be compared to the production model through live A/B tests (it’s known that offline performance alone isn’t a sufficient, especially if these models are used as part of a larger system where the offline and online metrics may not perfectly align (Deng et al., 2013; Beel et al., 2013)). Live experiments are costly: they often require human evaluations when the candidate and production model disagree to know which model was correct (Theocharous et al., 2015; Deng & Shi, 2016). Therefore, minimizing the unnecessary predictive churn can have a significant impact to the cost of the launch cycle.
It’s been observed that training DNN can be very noisy due to a variety of factors including random initialization (Glorot & Bengio, 2010), mini-batch ordering (Loshchilov & Hutter, 2015), data augmentation and processing (Santurkar et al., 2018; Shorten & Khoshgoftaar, 2019), and hardware (Turner & Nowotny, 2015; Bhojanapalli et al., 2021)– in other words running the same procedure multiple times can lead to models with surprisingly amount of disagreeing predictions even though all can have very high accuracies (Bahri & Jiang, 2021). While the stability of the training procedure is a separate problem from lowering predictive churn, such instability can further exacerbate the issue and underscores the difficulty of the problem.
Knowledge distillation (Hinton et al., 2015), which involves having a teacher model and mixing its predictions with the original labels has proved to be a useful tool in deep learning. In this paper, we show that this surprisingly is not only an effective tool for churn reduction by using the base model as the teacher, it is also mathematically aligned with learning under a constraint on the churn. Thus, in addition to providing a strong method for low churn training, we also provide insight into the distillation.
Our contributions are as follows:
• We show theoretically an equivalence between the low churn training objective (i.e. minimize a loss function subject to a churn constraint on the base model) and using knowledge distillation with the base model as the teacher. • We show that distillation performs strongly in a wide range of experiments against a number
baselines that have been considered for churn reduction. • Our distillation approach is similar to a previous method called “anchor” (Fard et al., 2016),
which trains on the true labels instead of distilled labels for the incorrectly predicted examples by the base model. Our proposal outperforms it by a surprising amount. We present both theoretical and experimental results showing that the modification of anchor relative to distillation actually hurts performance.
2 RELATED WORKS
Prediction Churn. There are few works that address low churn training with respect to a base model. Fard et al. (2016) proposed an anchor loss which is similar to distillation when the base model’s prediction agrees with the original label, and uses a scaled version of the original label otherwise. In our empirical evaluation, we find that this procedure performs considerably worse than distillation. Cotter et al. (2019a); Goh et al. (2016) use constrained optimization by adding a constraint on the churn. We use some of the theoretical insights found in that work to show an equivalence between distillation and the constrained optimization problem. Thus, we are able to bypass the added complexity of using constrained optimization (Cotter et al., 2019b) in favor of distillation, which is a simpler and more robust method.
A related but different notion of churn that has been studied is where the goal is to reduce the training instability. Anil et al. (2018) noted that co-distillation is an effective method. Bahri & Jiang (2021) proposes a locally adaptive variant of label smoothing and Bhojanapalli et al. (2021) propose entropy regularizers and a variant of co-distillation. We tested many of the baselines proposed in these papers and adapt them to our notion of churn and showed that they were not effective at reducing predictive churn w.r.t. a base model.
Distillation. Distillation (Ba & Caruana, 2013; Hinton et al., 2015), first proposed to transfer knowledge from larger networks to smaller ones, has become immensely popular. Applications include learning from noisy labels (Li et al., 2017), model compression (Polino et al., 2018), adversarial robustness (Papernot et al., 2016), DNNs with logic rules (Hu et al., 2016), visual relationship detection (Yu et al., 2017), reinforcement learning (Rusu et al., 2015), domain adaptation (Asami et al., 2017) and privacy (Lopez-Paz et al., 2015). Our work adds to the list of applications in which distillation is effective.
The theoretical motivation of distillation however is less established. Lopez-Paz et al. (2015) studied distillation as learning using privileged information (Vapnik & Izmailov, 2015). Phuong & Lampert (2019) establishes fast convergence of the expected risk of a distillation-trained linear classifier. Foster et al. (2019) provides a generalization bound for the student with an assumption that it learns a model close to the teacher. Dong et al. (2019) argued distillation has a similar effect as that of early stopping. Mobahi et al. (2020) showed an equivalence to increasing the regularization strength for kernel methods. Menon et al. (2020) establish a bias-variance trade-off for the student. Our analysis provides a new theoretical perspective of its relationship to churn reduction.
3 DISTILLATION FOR CONSTRAINING CHURN
We are interested in a multiclass classification problem with an instance space X and a label space rms “ t1, . . . ,mu. Let D denote the underlying data distribution over instances and labels, and DX denote the corresponding marginal distribution over X . Let ∆m denote the pm ´ 1q-dimensional simplex with m coordinates. We will use p : XÑ∆m to denote the underlying conditional-class probabilities, where pypxq “ PpY “ y|X “ xq. We assume that we are provided a base classifier g : XÑ∆m that predicts a vector of probabilities gpxq P ∆m for any instance x. Our goal is to then learn a new classifier h : XÑ∆m, constraining it to have low predictive churn against g. We will measure the classification performance of a classifier h using a loss function ` : rms ˆ ∆mÑR` that maps a label y P rms and prediction hpxq P ∆m to a non-negative number `py, hpxqq, and denote the classification risk by Rphq :“ Epx,yq„D r`py,hpxqqs. We would ideally like to define predictive churn as the fraction of examples on which h and g disagree. For the purpose of designing a tractable algorithm, we will instead work with a softer notion of churn, which evaluates the divergence between their output distributions. To this end, we use a measure of divergence d : ∆m ˆ∆mÑ R`, and denote the expected churn between h and g by Cphq :“ Ex„DX rdpgpxq,hpxqqs. We then seek to minimize the classification risk for h, subject to the expected churn being within an allowed limit ą 0:
min h:XÑ∆m
Rphq s.t. Cphq ď . (1)
We consider loss and divergence functions that are defined in terms of a scoring function φ : ∆mÑRm` that maps a distribution to a m-dimensional score. Specifically, we will consider scoring functions φ that are strictly proper (Gneiting & Raftery, 2007; Williamson et al., 2016), i.e. for which, given any distribution u P ∆m, the conditional risk Ey„u rφypvqs is uniquely minimized by v “ u. The following are general loss and divergence functions derived from φ:
`φpy,vq :“ φypvq; dφpu,vq :“ ÿ
yPrms uypφypvq ´ φypuqq. (2)
e.g. cross-entropy, KL-divergence, and squared loss are special cases of this formulation.
3.1 BAYES-OPTIMAL CLASSIFIER
We show below that for the loss and divergence functions defined in (2), the optimal-feasible classifier for the constrained problem in (1) is a convex combination of the class probability function p and the base classifier g. Proposition 1. Let p`, dq be defined as in (2) for a strictly proper scoring function φ. Suppose φpuq is strictly convex in u. Then there exists λ˚ P r0, 1s such that the following is an optimal-feasible classifier for (1): h˚pxq “ λ˚ppxq ` p1´ λ˚qgpxq. Furthermore, if u ¨ φpuq is α-strongly concave over u P ∆m w.r.t. the Lq-norm, then λ˚ ď b
2 { ` αEx “ }ppxq ´ gpxq}2q ‰˘ .
The strong concavity condition in Proposition 1 is satisfied by the cross-entropy loss and KLdivergence for α “ 1 with the L1-norm, and by the squared loss and L2-distance for α “ 2 with the L2-norm. The bound suggests that the mixing coefficient λ˚ depends on how close the base classifier is to the class probability function p.
Algorithm 1 Distillation-based Churn Reduction 1: Inputs: Training sample S “ tpx1, y1q, . . . , pxn, ynqu, Grid of mixing coefficients Λ “ tλ1, . . . , λLu, Base classifier g, Constraint slack ą 0
2: Train a classifier hk for each λk P Λ by minimizing the distilled loss in (4):
hk P argminhPH pLλkphq
3: Find a convex combination of h1, . . . ,hL by solving following convex program in L variables:
min hPcoph1,...,hLq
pRphq s.t. pCphq ď
and return the solution ph
3.2 DISTILLATION-BASED APPROACH
Proposition 1 directly motivates the use of a distillation-based approach for solving the churnconstrained optimization problem in (1). We propose treating the base classifier g as a teacher model, mixing the training labels y with scores from the teacher gpxq, and minimizing a classification loss against the transformed labels:
Lλphq “ Epx,yq„D rpλey ` p1´ λqgpxqq ¨ φphpxqqs , (3) where ey P t0, 1um denotes a one-hot encoding of the label y P rms and φ is a strictly proper scoring function. It is straight-forward to show that when λ “ λ˚, the optimal classifier for the above distillation loss takes the same form in Proposition 1, i.e. h˚pxq “ λ˚ppxq ` p1´ λ˚qgpxq. While the optimal mixing parameter λ˚ is unknown, we propose treating this as a hyper-parameter and tuning it to reach the desired level of churn.
In practice, we do not have direct access to the distribution D and will need to work with a sample S “ tpx1, y1q, . . . , pxn, ynqu drawn from D. To this end, we define the empirical risk and the empirical churn as follows:
pRphq “ 1 n
n ÿ i“1 `φpyi,hpxiqq; pCphq “ 1 n n ÿ i“1 dφpgpxiq,hpxiqq,
where `φ and dφ are defined as in (2) for a scoring function φ. Our proposal is to then solve the following empirical risk minimization problem over a hypothesis class H Ă th : XÑ∆mu for different values of coefficient λk chosen from a finite grid tλ1, . . . , λLu Ă r0, 1s:
hk P argminhPH pLλkphq :“ 1
n
n ÿ i“1 pλkeyi ` p1´ λkqgpxiqq ¨ φphpxiqq. (4)
To construct the final classifier, we find a convex combination of the L classifiers h1, . . . ,hL that minimizes pRphq while satisfying the constraint pCphq ď , and return an ensemble of the L classifiers. The overall procedure is outlined in Algorithm 1, where we denote the set of convex combinations of classifiers h1, . . . ,hL by coph1, . . . ,hLq “ th : x ÞÑ řL j“1 αjhjpxq |α P ∆Lu.
The post-processing step in Algorithm 1 amounts to solving a simple convex program in L variables. This is needed for technical reasons in our theoretical results, specifically, to translate a solution to a dual-optimal solution to (1) to a primal-feasible solution. In practice, however, we do not construct an ensemble, and instead simply return a single classifier that achieves the least empirical risk while satisfying the churn constraint. In our experiments, we use the cross-entropy loss for training, i.e. set φypuq “ ´ logpuyq.
4 THEORETICAL GUARANTEES
We provide optimality and feasibility guarantees for the proposed algorithm and also explain why our approach is better-suited for optimizing accuracy (subject to a churn constraint) compared to the previous churn-reduction method of Fard et al. (2016).
4.1 OPTIMALITY AND FEASIBILITY GUARANTEES
We now show that the classifier ph returned by Algorithm 1 approximately satisfies the churn constraint, while achieving a risk close to that of the optimal-feasible classifier inH. This result assumes that we are provided with generalization bounds for the classification risk and churn. Theorem 2. Let the scoring function φ : ∆mÑRm` be convex, and }φpzq}8 ă B,@z P ∆m. Let the set of classifiersH be convex, with the base classifier g P H. Suppose C and R enjoy the following generalization bounds: for any δ P p0, 1q, w.p. ě 1´ δ over draw of S „ Dn, for any h P H,
|Rphq ´ pRphq| ď ∆Rpn, δq; |Cphq ´ pCphq| ď ∆Cpn, δq,
for some ∆Rpn, δq and ∆Cpn, δq that is decreasing in n and approaches 0 as nÑ8. Let rh be an optimal-feasible classifier in H, i.e. Cprhq ď and Rprhq ď Rphq for all classifiers h for which Cphq ď . Let ph be the classifier returned by Algorithm 1 with Λ “
maxt `2B , uu ˇ ˇu P t 1L , 2 L , . . . , 1u ( for some L P N`. For any δ P p0, 1q, w.p. ě 1´ δ over draw of S „ Dn,
Optimality : Rpphq ď Rprhq ` O `` 1` 2B ˘ ` ∆Rpn, δq ` ∆Cpn, δq ` BL ˘˘ ,
Feasibility : Cpphq ď ` ∆C pn, δq .
In practice, we expect the churn metric to generalize better than the classification risk, i.e. for ∆Cpn, δq to be smaller than ∆Rpn, δq. This is because the classification risk is computed on “hard” labels y P rms from the training sample, whereas the churn metric is computed on “soft” labels gpxq P ∆m from the base model. The traditional view of distillation (Hinton et al., 2015) suggests that the soft labels from a teacher model come with confidence scores for each example, and thus allow the student to generalize well to unseen new examples. A similar view is also posed by Menon et al. (2020) , who argue that the soft labels from the teacher have “lower variance” than the hard labels from the training sample, and therefore aid in better generalization of the student. See Appendix B for explicit bounds on ∆Cpn, δq and ∆Rpn, δq. In fact, for certain base classifiers g, generalizing well on “churn” can have the additional benefit of improving classification performance, as shown by the proposition below. Proposition 3. Let p`, dq be defined as in (2) for a strictly proper scoring function φ. Suppose φpuq is strictly convex in u, Φ-Lipschitz w.r.t. L1-norm for each y P rms, and }φpzq}8 ă B,@z P ∆m. Let λ˚ be the optimal mixing coefficient defined in Proposition 1. Let ∆Cpn, δq be the churn generalization bound defined in Theorem 2. Let rh be an optimal feasible classifier inH and ph be the classifier returned by Algorithm 1. Then for any δ P p0, 1q, w.p. ě 1´ δ over draw of S „ Dn:
Rpphq ´ Rprhq ď ` ∆Cpn, δq ` pB ` Φλ˚qEx„DX r}ppxq ´ gpxq}1s .
This result bounds the excess classification risk in terms of the churn generalization bound and the expected difference between the base classifier g and the underlying class probability function p. When the base classifier is close to p, low values of ∆Cpn, δq result in low classification risk.
4.2 ADVANTAGE OVER ANCHOR LOSS
We next compare our distillation loss in (3) with the previous anchor loss of Fard et al. (2016), which uses the base model’s prediction only when it agrees with the original label, and uses a scaled version of the original label otherwise. While originally proposed for churn reduction with binary labels, we provide below an analogous version of this loss for a multiclass setup:
Lancphq “ Epx,yq„D ra ¨ φphpxqqs , (5) where
a “ " αgpxq ` p1´ αqey if y “ argmaxk gkpxq ηey otherwise ,
for hyper-parameters α, η P r0, 1s and a strictly proper scoring function φ. Here, we have used argmax to denote ties being broken in favor of the larger class. While this helps us simplify the exposition, our results can be easily extended to a version of the loss which includes ties.
The anchor loss does not take into account the confidence with which the base model disagrees with the sampled label y. For example, if the base model predicts near-equal probabilities for all classes, but happens to assign a slightly higher probability to a class different from y, the anchor loss would still completely ignore the base model’s score (even though it might be the case that all the labels are indeed equally likely to occur). In some cases, this selective use of the teacher labels can result in a biased objective and may hurt the classifier’s accuracy.
To see this, consider an ideal scenario where the base model predicts the true conditional-probabilities ppxq and the student hypothesis class is universal. In this case, minimizing the churn w.r.t. the base model has the effect of maximizing classification accuracy, i.e. a classifier that has zero churn w.r.t. the base model also produces the least classification error. However, as shown below, even in this ideal setup, minimizing the anchor loss may result in a classifier different from the base model. Proposition 4. When gpxq “ ppxq,@x, for any given λ P r0, 1s, the minimizer for the distillation loss in (3) over all classifiers h is given by:
h˚pxq “ ppxq,
whereas the minimizer of the anchor loss in (5) is given by:
h˚j pxq “ zj ř
j zj where zj “
"
αp2j pxq ` p1´ αqpjpxq if j “ argmaxk pkpxq pη ` αmaxk pkpxqq pjpxq otherwise .
Unless α “ 0 and η “ 1 (which amounts to completely ignoring the base model) or the base model makes hard predictions on all points, i.e. pjpxq P t0, 1u,@x, the anchor loss encourages scores that differ from the base model p. For example, when α “ η “ 1 (and the base model makes soft predictions), the anchor loss has the effect of down weighting the label that the base model is most confident about, and as a result, encourages lower scores on that label and higher scores on all other labels. While one can indeed tweak the two hyper-parameters to reduce the gap between the learned classifier and the base model, our proposal requires only one hyper-parameter λ, which represents an intuitive trade-off between the one-hot and teacher labels. In fact, irrespective of the choice of λ, the classifier that minimizes our distillation loss in Proposition 4 mimics the base model p exactly, and as a result, achieves both zero churn and optimal accuracy.
We shall see in the next section that even on real-world datasets, where the base classifier does not necessarily make predictions close to the true class probabilities (and where the student hypothesis class is not necessarily universal and of limited capacity), our proposal performs substantially better than the anchor loss in minimizing churn at a particular accuracy. Figure 3 provides a further ablation study, effectively interpolating between the anchor and distillation methods, and provides evidence that using the true (hard) label instead of the teacher (soft) label can steadily degrade performance.
5 EXPERIMENTS
We now show empirically that distillation is an effective method to train models for both accuracy and low churn. We test our method across a large number of datasets and neural network architectures.
5.1 SETUP
Datasets and architectures: The following are the datasets we use in our experiments, along with the associated model architectures:
• 12 OpenML datasets using fully-connected neural networks. • 10 MNIST variants, SVHN, CIFAR10, 40 CelebA tasks using convolutional networks. • CIFAR10 and CIFAR100 with ResNet-50, ResNet-101, and ResNet-152. • IMDB dataset using transformer network.
For each architecture (besides ResNet), we use 5 different sizes. For the fully connected network, we use a simple network with one-hidden layer of 10, 102, 103, 104, and 105 units, which we call fcn-x where x is the respective size of the hidden layer. For the convolutional neural network, we start with the LeNet5 architecture (LeCun et al., 1998) and scale the number of hidden units by a factor of x for x “ 1, 2, 4, 8, 16, which we call ConvNet-x for the respective x. Finally, we use the basic
transformer architecture from Keras tutorial (Keras, 2020) and scale the number of hidden units by x for x “ 1, 2, 4, 8, 16, which we call Transformer-x for the respective x. Code for the models in Keras can be found in the Appendix. For each dataset, we use the standard train/test split if available, otherwise, we fix a random train/test split with ratio 2:1.
Setup: For each dataset and neural network, we randomly select from the training set 1000 initial examples, 100 validation examples, and a batch of 1000 examples, and train an initial model using Adam optimizer with default settings on the initial set and early stopping (i.e. stop when there’s no improvement on the validation loss after 5 epochs) and default random initialization, and use that model as the base model. Then, for each baseline, we train on the combined initial set and batch (2000 datapoints), again using the Adam optimizer with default settings and the same early stopping scheme and calculate the accuracy and churn against the base model on the test set. We average across 100 runs and provide the error bands in the Appendix. For all the datasets except the OpenML datasets, we also have results for the case of 10000 initial examples, 1000 validation examples, and a batch 1000. We also show results for the case of 100 initial samples, 1000 validation examples, and a batch of 1000 for all of the datasets. Due to space, we show those results in the Appendix. We ran our experiments on a cloud environment. For each run, we used a NVIDIA V100 GPU, which took up to several days to finish all 100 trials.
Baselines: We test our method against the following baselines. (1) Cold start, where we train the model from scratch with the default initializer. (2) Warm start, where we initialize the model’s parameters to that of the base model before training. (3) Shrink-perturb (Ash & Adams, 2019), which is a method designed to improve warm-starting by initializing the model’s weights to α ¨θbase` p1´αq¨θinit before training, where θbase are the weights of the base model, θinit is a randomly initialized model, and α is a hyperparameter we tune across t0.1, 0.2, ..., 0.9u. (4) Mixup (Zhang et al., 2017) (a baseline suggested for a different notion of churn (Bahri & Jiang, 2021)), which trains an convex combinations of pairs of datapoints. We search over its hyperparameter α P t0.1, ..., 0.9u, as defined in Zhang et al. (2017). (5) Label smoothing (Szegedy et al., 2016), which was suggested by Bahri & Jiang (2021) for the variance notion of churn, proceeds by training on a convex combination between the original labels and the base models’ soft prediction. We tune across the convex combination weight α P t0.1, 0.2, ..., 0.9u. (6) Co-distillation (Anil et al., 2018), which was proposed for the variance notion of churn, where we train two warm-started networks that train simultaneously on a loss that is a convex combination on the original loss and a loss on the difference between their predictions. We tune across the convex combination weight α P t0.1, 0.2, ..., 0.9u. (7) Anchor (Fard et al., 2016), which as noted in Section 4.2, proceeds by optimizing the cross-entropy loss on a modified label: we use the label αgpxq` p1´αqey when the base model g agrees with the true label y, and ηey otherwise. We tune across α P t0.1, 0.2, ..., 0.9u and η P t0.5, 0.7, 1u. For distillation, we tune the trade-off parameter λ across t0.1, 0.2, ..., 0.9u. Metric: All of the methods will produce a model that we evaluate for both accuracy and churn with respect to the base model on the test set. We consider the hard notion of churn, which measures the average difference in hard predictions w.r.t. the base classifier on a test set. We will see later that there is often-times a trade-off between accuracy and churn, and in an effort to produce one metric for quantitative evaluation, we propose churn at cold accuracy metric, which is defined as follows. Each baseline produces a set of models (one for each hyperparameter setting). We take the averaged churn and accuracy across the 100 runs and choose the model with the lowest churn that is at least as accurate as the cold-start model (it’s possible that no such model exists for that method). This way, we can identify the method that delivers the lowest churn but still performs at least as well as if we trained on the updated dataset in a vanilla manner. We believe this metric is practically relevant as a practitioner is unlikely to accept a reduction in accuracy to reduce churn.
5.2 RESULTS
The detailed results for the following experiments can be found in the Appendix. Given space constraints, we only provide a high level summary in this section
OpenML datasets with fully-connected networks: In Table 1 we show the results for the OpenML datasets using the fcn-1000 network. We see that distillation performs the well across the board, and for the other fully connected network sizes, distillation is the best in the majority of cases (84% of the time for initial batch size 1000 and 52% of time for initial batch size 100).
MNIST variants, SVHN, and CIFAR10 with convolutional networks: In Table 2, we show the results for 10 MNIST variants, SVHN and CIFAR10 using convnet-4. We see that distillation performs strongly across the board. We found that distillation performs best in 84% of combinations between dataset and network. When we increase the initial sample size to 10000 and keep the batch size fixed at 1000, then we found that label smoothing starts becoming competitive with distillation, where distillation is best 64% of the time, and label smoothing wins by a small margin all other
times. We only saw this phenomenon for a handful of the MNIST variants, which suggests that label smoothing may be especially effective in these situations. When we decreased the initial sample down to 100 and kept the batch size the same, we found that distillation was best 48% of the time, with Anchor being the second best method winning 24% of the time.
For SVHN and CIFAR10, of the 10 combinations, distillation performs the best on all 10 out of the 10. If we increased the initial sample size to 10000 and kept the batch size fixed at 1000, then we find that distillation still performs the best all 10 out of 10 combinations. If we decreased the initial sample size to 100 and kept the same batch size, then distillation performs the best on 8 out of the 10 combinations.
CelebA with convolutional networks: Across all 200 combinations of task and network, distillation performs the best 79% of the time. Moreover, if we increased the initial sample size to 10000 and kept the batch size fixed at 1000, distillation is even better, performing the best 91.5% of the time. If we decreased the initial sample size to 100, then distillation is best 96% of the time.
CIFAR10 and CIFAR100 with ResNet: Due to the computational costs, we only run these experiments for initial sample size 1000. In all cases (across ResNet-50, ResNet-101 and ResNet-152), we see that distillation outperforms the other baselines.
IMDB with transformer network: We experimented for initial batch size 100, 1000, and 10000. We found that distillation performed the best the majority of the time, where the only notable weak performance was in some instances where no baselines were even able to reach the accuracy of the cold starting method. In Figure 2 we show the Pareto frontiers of the various baselines as well as plotting cost of each method as we vary the trade-off between accuracy and churn. We see that not only does distillation do well in churn, but it performs the best at any trade-off between churn and accuracy for the cases shown.
6 CONCLUSION
We have proposed knowledge distillation as a new practical solution to churn reduction, and provided both theoretical and empirical justifications for the approach. Some directions for future work include investigating the interplay between churn and fairness. One way this connection may arise is that in trying to lower churn, some slices of the data may be disproportionately affected. Another way is if the teacher itself contains harmful biases, in which it makes sense to control what kind of churn should be minimized. Further work may also include combining distillation with other methods to achieve even stronger results.
Reproducibility Statement: All details of experimental setup are in the main text, along with descriptions of the baselines and what hyperparameters were swept across. Code can be found in the Appendix. All proofs are in the Appendix.
REFERENCES Shivani Agarwal. Surrogate regret bounds for bipartite ranking via strongly proper losses. The
Journal of Machine Learning Research, 15(1):1653–1674, 2014.
Rohan Anil, Gabriel Pereyra, Alexandre Passos, Robert Ormandi, George E Dahl, and Geoffrey E Hinton. Large scale distributed neural network training through online distillation. arXiv preprint arXiv:1804.03235, 2018.
Taichi Asami, Ryo Masumura, Yoshikazu Yamaguchi, Hirokazu Masataki, and Yushi Aono. Domain adaptation of dnn acoustic models using knowledge distillation. In 2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 5185–5189. IEEE, 2017.
Jordan T Ash and Ryan P Adams. On warm-starting neural network training. arXiv preprint arXiv:1910.08475, 2019.
Lei Jimmy Ba and Rich Caruana. Do deep nets really need to be deep? arXiv preprint arXiv:1312.6184, 2013.
Dara Bahri and Heinrich Jiang. Locally adaptive label smoothing for predictive churn. arXiv preprint arXiv:2102.05140, 2021.
Joeran Beel, Marcel Genzmehr, Stefan Langer, Andreas Nürnberger, and Bela Gipp. A comparative analysis of offline and online evaluations and discussion of research paper recommender system evaluation. In Proceedings of the international workshop on reproducibility and replication in recommender systems evaluation, pp. 7–14, 2013.
Srinadh Bhojanapalli, Kimberly Wilber, Andreas Veit, Ankit Singh Rawat, Seungyeon Kim, Aditya Menon, and Sanjiv Kumar. On the reproducibility of neural network predictions. arXiv preprint arXiv:2102.03349, 2021.
Andrew Cotter, Heinrich Jiang, Maya R Gupta, Serena Wang, Taman Narayan, Seungil You, and Karthik Sridharan. Optimization with non-differentiable constraints with applications to fairness, recall, churn, and other goals. Journal of Machine Learning Research, 20(172):1–59, 2019a.
Andrew Cotter, Heinrich Jiang, and Karthik Sridharan. Two-player games for efficient non-convex constrained optimization. In Algorithmic Learning Theory, pp. 300–332. PMLR, 2019b.
Alex Deng and Xiaolin Shi. Data-driven metric development for online controlled experiments: Seven lessons learned. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 77–86, 2016.
Alex Deng, Ya Xu, Ron Kohavi, and Toby Walker. Improving the sensitivity of online controlled experiments by utilizing pre-experiment data. In Proceedings of the sixth ACM international conference on Web search and data mining, pp. 123–132, 2013.
Bin Dong, Jikai Hou, Yiping Lu, and Zhihua Zhang. Distillation « early stopping? harvesting dark knowledge utilizing anisotropic information retrieval for overparameterized neural network. arXiv preprint arXiv:1910.01255, 2019.
Mahdi Milani Fard, Quentin Cormier, Kevin Canini, and Maya Gupta. Launch and iterate: Reducing prediction churn. In Advances in Neural Information Processing Systems, pp. 3179–3187, 2016.
Dylan J Foster, Spencer Greenberg, Satyen Kale, Haipeng Luo, Mehryar Mohri, and Karthik Sridharan. Hypothesis set stability and generalization. arXiv preprint arXiv:1904.04755, 2019.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pp. 249–256. JMLR Workshop and Conference Proceedings, 2010.
Tilmann Gneiting and Adrian E Raftery. Strictly proper scoring rules, prediction, and estimation. Journal of the American statistical Association, 102(477):359–378, 2007.
Gabriel Goh, Andrew Cotter, Maya Gupta, and Michael P Friedlander. Satisfying real-world goals with dataset constraints. In Advances in Neural Information Processing Systems, pp. 2415–2423, 2016.
Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in a neural network. arXiv preprint arXiv:1503.02531, 2015.
Zhiting Hu, Xuezhe Ma, Zhengzhong Liu, Eduard Hovy, and Eric Xing. Harnessing deep neural networks with logic rules. arXiv preprint arXiv:1603.06318, 2016.
Keras. Keras documentation: Text classification with transformer, 2020. URL https://keras. io/examples/nlp/text_classification_with_transformer/.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278–2324, 1998.
Yuncheng Li, Jianchao Yang, Yale Song, Liangliang Cao, Jiebo Luo, and Li-Jia Li. Learning from noisy labels with distillation. In Proceedings of the IEEE International Conference on Computer Vision, pp. 1910–1918, 2017.
David Lopez-Paz, Léon Bottou, Bernhard Schölkopf, and Vladimir Vapnik. Unifying distillation and privileged information. arXiv preprint arXiv:1511.03643, 2015.
Ilya Loshchilov and Frank Hutter. Online batch selection for faster training of neural networks. arXiv preprint arXiv:1511.06343, 2015.
Aditya Krishna Menon, Ankit Singh Rawat, Sashank J Reddi, Seungyeon Kim, and Sanjiv Kumar. Why distillation helps: a statistical perspective. arXiv preprint arXiv:2005.10419, 2020.
Hossein Mobahi, Mehrdad Farajtabar, and Peter L Bartlett. Self-distillation amplifies regularization in hilbert space. arXiv preprint arXiv:2002.05715, 2020.
Nicolas Papernot, Patrick McDaniel, Xi Wu, Somesh Jha, and Ananthram Swami. Distillation as a defense to adversarial perturbations against deep neural networks. In 2016 IEEE symposium on security and privacy (SP), pp. 582–597. IEEE, 2016.
Mary Phuong and Christoph Lampert. Towards understanding knowledge distillation. In International Conference on Machine Learning, pp. 5142–5151. PMLR, 2019.
Antonio Polino, Razvan Pascanu, and Dan Alistarh. Model compression via distillation and quantization. arXiv preprint arXiv:1802.05668, 2018.
Andrei A Rusu, Sergio Gomez Colmenarejo, Caglar Gulcehre, Guillaume Desjardins, James Kirkpatrick, Razvan Pascanu, Volodymyr Mnih, Koray Kavukcuoglu, and Raia Hadsell. Policy distillation. arXiv preprint arXiv:1511.06295, 2015.
Shibani Santurkar, Dimitris Tsipras, Andrew Ilyas, and Aleksander Madry. How does batch normalization help optimization? arXiv preprint arXiv:1805.11604, 2018.
Connor Shorten and Taghi M Khoshgoftaar. A survey on image data augmentation for deep learning. Journal of Big Data, 6(1):1–48, 2019.
Christian Szegedy, Vincent Vanhoucke, Sergey Ioffe, Jon Shlens, and Zbigniew Wojna. Rethinking the inception architecture for computer vision. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2818–2826, 2016.
Georgios Theocharous, Philip S Thomas, and Mohammad Ghavamzadeh. Ad recommendation systems for life-time value optimization. In Proceedings of the 24th International Conference on World Wide Web, pp. 1305–1310, 2015.
James P Turner and Thomas Nowotny. Estimating numerical error in neural network simulations on graphics processing units. BMC Neuroscience, 16(198), 2015.
Vladimir Vapnik and Rauf Izmailov. Learning using privileged information: similarity control and knowledge transfer. J. Mach. Learn. Res., 16(1):2023–2049, 2015.
Robert C Williamson, Elodie Vernet, and Mark D Reid. Composite multiclass losses. Journal of Machine Learning Research, 17:1–52, 2016.
Ruichi Yu, Ang Li, Vlad I Morariu, and Larry S Davis. Visual relationship detection with internal and external linguistic knowledge distillation. In Proceedings of the IEEE international conference on computer vision, pp. 1974–1982, 2017.
Hongyi Zhang, Moustapha Cisse, Yann N Dauphin, and David Lopez-Paz. mixup: Beyond empirical risk minimization. arXiv preprint arXiv:1710.09412, 2017.
A PROOFS
A.1 PROOF OF PROPOSITION 1
Proposition (Restated). Let p`, dq be defined as in (2) for a strictly proper scoring function φ. Suppose φpuq is strictly convex in u. Then there exists λ˚ P r0, 1s such that the following is an optimal-feasible classifier for (1):
h˚pxq “ λ˚ppxq ` p1´ λ˚qgpxq.
Furthermore, if u ¨ φpuq is α-strongly concave over u P ∆m w.r.t. the Lq-norm, then
λ˚ ď d
2
αEx “ }ppxq ´ gpxq}2q ‰ .
Proof. Let h˚ denote an optimal feasible solution for (1). We first note that
Rphq “ Ex,y r`py,hpxqqs “ Ex “ Ey|x r`py,hpxqqs ‰ “ Ex ” ÿ
iPrms pipxqφiphpxqq
ı
and Cphq “ Ex ” ÿ
iPrms gipxq pφiphpxqq ´ φipgpxqqq
ı
.
Because φi is strictly convex in its argument, both Rphq and Cphq are strictly convex in h. In other words, for any α P r0, 1s, and classifiers h1,h2, Rpαh1 ` p1´ αqh2q ă αRph1q ` p1´ αqRph2q, and similarly for C. Furthermore because Cpgq “ 0 ă , the constraint is strictly feasible, and hence strong duality holds for (1) (as a result of Slater’s condition being satisfied). Therefore (1) can be equivalently formulated as a max-min problem:
max µPR` min h Rphq ` µCphq,
for which there exists a µ˚ P R` such that pµ˚,h˚q is a saddle point. The strict convexity of Rphq and Cphq gives us that h˚ is the unique minimizer of Rphq ` µ˚Cphq. Setting λ˚ “ 11`µ˚ , we equivalently have that h˚ is a unique minimizer of the weighted objective λ˚Rphq ` p1´ λ˚qCphq. We next show that the minimizer h˚ is of the required form. Expanding the R and C, we have:
λ˚Rphq ` p1´ λ˚qCphq
“ Ex ” ÿ
iPrms
` λ˚pipxq ` p1´ λ˚qgipxq ˘ φiphpxqq ´ p1´ λ˚qgipxqφipgpxqq ı
“ Ex ” ÿ
iPrms
` λ˚pipxq ` p1´ λ˚qgipxq ˘ φiphpxqq ı ` a term independent of h
“ Ex ” ÿ
iPrms p̄ipxqφiphpxqq
ı
` a term independent of h, (6)
where p̄pxq “ λ˚ppxq ` p1´ λ˚qgpxq. Note that it suffices to minimize (6) point-wise, i.e. to choose h˚ so that the term within the expectation ř
iPrms p̄ipxqφiphpxqq is minimized for each x. For a fixed x, the inner term is minimized when h˚pxq “ p̄pxq. This is because of our assumption that φ is a strictly proper scoring function, i.e. for any distribution u, the weighted loss ř
i uiφipvq is uniquely minimized by v “ u. Therefore (6) is minimized by h˚pxq “ p̄pxq “ λ˚ppxq ` p1´ λ˚qgpxq. To bound λ˚, we use a result from Williamson et al. (2016); Agarwal (2014) to lower bound Cphq in terms of the norm difference }hpxq ´ gpxq}q. Define Qpuq “ infvP∆m u ¨ φpvq. Because φ is a proper scoring function, the infimum is attained at v “ u. Therefore Qpuq “ u ¨ φpuq, which recall is assumed to be strongly concave. Also, note thatQpuq “ infvP∆m u ¨φpvq is an infimum of “linear” functions in u, and therefore ∇Qpuq “ φpuq is a super-differential for Q at u. See Proposition 7 in Williamson et al. (2016) for more details.
We now re-write Cphq in terms of Q and lower bound it using the strong concavity property:
Cphq “ Ex ” gpxq ¨ pφphpxqq ´ φpgpxqqq ı
“ Ex ” hpxq ¨ φphpxqq ` pgpxq ´ hpxqq ¨ φphpxqq ´ gpxq ¨ φpgpxqq ı
“ Ex ” Qphpxqq ` pgpxq ´ hpxqq ¨∇Qphpxqq ´Qpgpxqq ı
ě Ex ”α
2 }hpxq ´ gpxq}2q
ı
,
where the last step uses the fact that Q is α-strongly concave over u P ∆m w.r.t. the Lq-norm. Since the optimal scorer h˚ satisfies the coverage constraint Cph˚q ď , we have from the above bound
Ex
”α
2 }h˚pxq ´ gpxq}2q
ı
ď . Substituting for h˚, we have:
Ex
„ pλ˚q2α 2 }ppxq ´ gpxq}2q  ď ,
or pλ˚q2 ď 2
αEx “ }ppxq ´ gpxq}2q ‰ ,
which gives us the desired bound on λ˚.
A.2 PROOF OF THEOREM 2
Theorem (Restated). Let the scoring function φ : ∆mÑRm` be convex, and }φpzq}8 ă B,@z P ∆m. Let the set of classifiers H be convex, with the base classifier g P H. Suppose C and R enjoy the following generalization bounds: for any δ P p0, 1q, w.p. ě 1 ´ δ over draw of S „ Dn, for any h P H, |Rphq ´ pRphq| ď ∆Rpn, δq; |Cphq ´ pCphq| ď ∆Cpn, δq, for some ∆Rpn, δq and ∆Cpn, δq that is decreasing in n and approaches 0 as nÑ8. Let rh be an optimal-feasible classifier in H, i.e. Cprhq ď and Rprhq ď Rphq for all classifiers h for which Cphq ď . Let ph be the classifier returned by Algorithm 1 with Λ “
maxt `2B , uu ˇ ˇu P t 1L , 2 L , . . . , 1u ( for some L P N`. For any δ P p0, 1q, w.p. ě 1´ δ over draw of S „ Dn,
Optimality : Rpphq ď Rprhq ` O `` 1` 2B ˘ ` ∆Rpn, δq ` ∆Cpn, δq ` BL ˘˘ ,
Feasibility : Cpphq ď ` ∆C pn, δq .
We first note that because }φpzq}8 ă B,@z P ∆m, both pRphq ă B and pCphq ă B. Also, because φi is convex, both pRphq and pCphq are convex in h. In other words, for any α P r0, 1s, and classifiers h1,h2, pRpαh1 ` p1 ´ αqh2q ď α pRph1q ` p1 ´ αq pRph2q, and similarly for pC. Furthermore, the objective in (4) can be decomposed into a convex combination of the empirical risk and churn:
pLλphq “ 1
n
n ÿ i“1 pλeyi ` p1´ λqgpxiqq ¨ φphpxiqq
“ λ pRphq ` p1´ λq pCphq ` 1´ λ n
n ÿ i“1 gpxiq ¨ φpgpxiqq.
Therefore minimizing pLλphq is equivalent to minimizing the Lagrangian function rLλphq “ λ pRphq ` p1´ λqp pCphq ´ q (7)
over h. Moreover, each hk minimizes rLλkphq. We also note that the churn-constrained optimization problem in (1) can be posed as a Lagrangian game between a player that seeks to minimize the above Lagrangian over h and a player that seeks to maximize the Lagrangian over λ. The next two lemmas show that Algorithm 1 can be seen as finding an approximate equilibrium of this two-player game.
Lemma 5. Let the assumptions on φ and H in Theorem 2 hold. Let ph be the classifier returned by Algorithm 1 when Λ is set to Λ “
maxt `2B , uu |u P t 1 L , . . . , 1u
(
of the range r `2B , 1s for some L P N`. Then there exists a bounded Lagrange multiplier λ̄ P r `2B , 1s such that pph, λ̄q forms an equilibrium of the Lagrangian min-max game:
λ̄ pRpphq ` p1´ λ̄qp pCpphq ´ q “ min hPcoph1,...,hLq λ̄ pRphq ` p1´ λ̄qp pCphq ´ q
max λPr0,1s
p1´ λqp pCpphq ´ q “ p1´ λ̄qp pCpphq ´ q.
Proof. The classifier ph returned by Algorithm 1 is a solution to the following constrained optimization problem over the convex-hull of the classifiers h1, . . . ,hL:
min hPcoph1,...,hLq
pRphq s.t. pCphq ď .
Consequently, there exists a λ̄ P r0, 1s such that: λ̄ pRpphq ` p1´ λ̄qp pCpphq ´ q “ min
hPcoph1,...,hLq λ̄ pRphq ` p1´ λ̄qp pCphq ´ q (8)
max λPr0,1s
p1´ λqp pCpphq ´ q “ p1´ λ̄qp pCpphq ´ q. (9)
To see this, note that the KKT conditions (along with the convexity of R and C) give us that there exists a Lagrange multiplier µ̄ ě 0 such that
ph P argmin hPcoph1,...,hLq pRphq ` µ̄p pCphq ´ q (stationarity)
µ̄p pCpphq ´ q “ 0 (complementary slackness). When pCpphq ď , µ̄ “ 0, and so (8) and (9) are satisfied for λ̄ “ 1. When pCpphq “ , then (8) and (9) are satisfied for λ̄ “ 11`µ̄ .
It remains to show that that λ̄ P r `2B , 1s. For this, we first show that there exists a h 1 P coph1, . . . ,hLq such that pCph1q ď {2. To see why, pick h1 to be the minimizer of the Lagrangian rLλphq over all h P H for λ “ `2B . Because rLλph
1q ď rLλpgq ď λB ´ p1´ λq , where g is the base classifier that we have assumed is inH, it follows that pCph1q ď λ1´λB ď {2.
Next, by combining (8) and (9), we have
λ̄ pRpphq ` max λPr0,1s p1´ λqp pCpphq ´ q “ min hPcoph1,...,hLq λ̄ pRphq ` p1´ λ̄qp pCphq ´ q.
Lower bounding the LHS by setting λ “ 1 and upper bounding the RHS by setting h “ h1, we get:
λ̄ pRpphq ď λ̄ pRph1q ´ p1´ λ̄q 2 ,
which gives us: {2 ď λ̄p {2` pRph1q ´ pRpphqq ď λ̄p {2`Bq.
Hence λ̄ ě `2B , which completes the proof.
Lemma 6. Let ph be the classifier returned by Algorithm 1 when Λ is set to Λ “ maxt `2B , uu |u P t 1L , . . . , 1u (
of the range r `2B , 1s for some L P N`. Fix δ P p0, 1q. Suppose R and C satisfy the generalization bounds in Theorem 2 with error bounds ∆Rpn, δq and ∆Cpn, δq respectively. Then there exists a bounded Lagrange multiplier pλ P r `2B , 1s such that pph, pµq forms an approximate equilibrium for the Lagrangian min-max game, i.e. w.p. ě 1´ δ over draw of sample S „ Dn,
pλRpphq ` p1´ pλqpCpphq ´ q ď min hPH pλRphq ` p1´ pλqpCphq ´ q
`O p∆Rpn, δq ` ∆Cpn, δq ` B{Lq (10) and
max λPr0,1s
p1´ λqpCpphq ´ q ď p1´ pλqpCpphq ´ q ` O p∆Cpn, δq ` B{Lq . (11)
Proof. We have from Lemma 5 that there exists λ̄ P r `2B , 1s such that
λ̄ pRpphq ` p1´ λ̄qp pCpphq ´ q “ min hPcoph1,...,hLq λ̄ pRphq ` p1´ λ̄qp pCphq ´ q (12)
max λPr0,1s
p1´ λqp pCpphq ´ q “ p1´ λ̄qp pCpphq ´ q. (13)
Algorithm 1 works with a discretization Λ “ maxt `2B , uu |u P t 1 L , . . . , 1u
(
of the range
r `2B , 1s. Allowing pλ to denote the closest value to λ̄ in this set, we have from (12):
pλ pRpphq ` p1´ pλqp pCpphq ´ q ď min hPcoph1,...,hLq pλ pRphq ` p1´ pλqp pCphq ´ q ` 4B L
“ min hPH pλ pRphq ` p1´ pλqp pCphq ´ q ` 4B L , (14)
where the last step follows from the fact that coph1, . . . ,hLq Ď H and each hk was chosen to minimize p1´ λkq pRphq ` λkp pCphq ´ q for λk P Λ. Similarly, we have from (13),
max λPr0,1s p1´ λqpCpphq ´ q ď p1´ pλqpCpphq ´ q ` B L . (15)
What remains is to apply the generalization bounds for R and C to (14) and (15). We first bound the LHS of (14). We have with probability at least 1´ δ over draw of S „ Dn:
pλ pRpphq ` p1´ pλqp pCpphq ´ q ě pλRpphq ` p1´ pλqpCpphq ´ q ´ pλ∆R pn, δq ´ p1´ pλq∆C pn, δq ě pλRpphq ` p1´ pλqpCpphq ´ q ´ ∆R pn, δq ´ ∆C pn, δq , (16)
where the last step uses the fact that 0 ď pλ ď 1. For the RHS, we have with the same probability:
min hPH
! pλ pRphq ` p1´ pλqp pCphq ´ q ) ` 4B{L
ď min hPH
! pλRphq ` p1´ pλqpCphq ´ q ` 4B{L ` pλ∆R pn, δq ` p1´ pλq∆C pn, δq )
ď min hPH
! pλRphq ` p1´ pλqpCphq ´ q ) ` 4B{L ` ∆R pn, δq ` ∆C pn, δq ,
where we again use 0 ď pλ ď 1. Combining (14) with (16) and (17) completes the proof for the first part of the lemma. Applying the generalization bounds to (15), we have with the same probability:
B{L ě max
λPr0,1s p1´ λqp pCpphq ´ q ´ p1´ pλqp pCpphq ´ q
ě max λPr0,1s
! p1´ λqpCpphq ´ q ´ p1´ λq∆C pn, δq ) ´ p1´ pλqpCpphq ´ q ´ p1´ pλq∆C pn, δq
ě max λPr0,1s p1´ λqpCpphq ´ q ´ p1´ pλqpCpphq ´ q ´ 2∆C pn, δq ,
which completes the proof for the second part of the lemma.
We are now ready to prove Theorem 2.
Proof of Theorem 2. To show optimality, we combine (10) and (11) and get:
pλ pRpphq ` max λPr0,1s p1´ λqpCpphq ´ q ď min hPH pλ pRphq ` p1´ pλqp pCphq ´ q
`O ´ ∆Rpn, δq ` ∆Cpn, δq ` B{L ¯ . (17)
We then lower bound the LHS in (17) by setting λ “ 1 and upper bound the RHS by setting h to the optimal feasible solution rh, giving us:
pλRpphq ď pλRprhq ` p1´ pλqp0q ` O ´ ∆R pn, δq ` ∆C pn, δq ` BL ¯ .
Dividing both sides by pλ,
Rpphq ď Rprhq ` 1 pλ O ´ ∆R pn, δq ` ∆C pn, δq ` BL ¯ .
Lower bounding pλ by `2B gives us the desired optimality result.
The feasibility result directly follows from the fact that Algorithm 1 chooses a ph that satisfies the empirical churn constraint pCpphq ď , and from the generalization bound for C.
A.3 PROOF OF PROPOSITION 3
Proposition (Restated). Let p`, dq be defined as in (2) for a strictly proper scoring function φ. Suppose φpuq is strictly convex in u, Φ-Lipschitz w.r.t. L1-norm for each y P rms, and }φpzq}8 ă B,@z P ∆m. Let λ˚ be the optimal mixing coefficient defined in Proposition 1. Let ∆Cpn, δq be the churn generalization bound defined in Theorem 2. Let rh be an optimal feasible classifier inH and ph be the classifier returned by Algorithm 1. Then for any δ P p0, 1q, w.p. ě 1´ δ over draw of S „ Dn:
Rpphq ´ Rprhq ď ` ∆Cpn, δq ` pB ` Φλ˚qEx„DX r}ppxq ´ gpxq}1s .
Proof. Let h˚ be the Bayes optimal classifier, i.e. the optimal-feasible classifier over all classifiers (not just those inH). We have:
Rpphq ´ Rprhq ď Rpphq ´ Rph˚q
“ Ex„DX ” Ey|x ” ey ¨ φpphpxqq ıı ´ Ex„DX “ Ey|x rey ¨ φph˚pxqqs ‰
“ Ex„DX ” ppxq ¨ φpphpxqq ı ´ Ex„DX rppxq ¨ φph˚pxqqs
“ Ex„DX ” ppxq ¨ ´ φpphpxqq ´ φpgpxqq ¯ı ´ Ex„DX rppxq ¨ pφph˚pxqq ´ φpgpxqqqs
ď Ex„DX ” ppxq ¨ ´ φpphpxqq ´ φpgpxqq ¯ı `
ˇ
ˇ
ˇ
ˇ
ˇ
ˇ
Ex„DX
»
–
ÿ
yPrms pypxq pφyph˚pxqq ´ φypgpxqqq
fi
fl
ˇ
ˇ
ˇ
ˇ
ˇ
ˇ
ď Ex„DX ” ppxq ¨ ´ φpphpxqq ´ φpgpxqq ¯ı ` Ex„DX
»
–
ÿ
yPrms pypxq
ˇ ˇφyph˚pxqq ´ φypgpxqq ˇ ˇ
fi
fl
ď Ex„DX ” ppxq ¨ ´ φpphpxqq ´ φpgpxqq ¯ı ` ΦEx„DX
»
–
ÿ
yPrms pypxq}h˚pxq ´ gpxq}1
fi
fl
ď Ex„DX ” ppxq ¨ ´ φpphpxqq ´ φpgpxqq ¯ı ` ΦEx„DX r}h˚pxq ´ gpxq}1s ,
where the second-last step follows from Jensen’s inequality, and the last step uses the Lipschitz assumption on φy .
We further have:
Rpphq ´ Rprhq
ď Ex„DX ” gpxq ¨ ´ φpphpxqq ´ φpgpxqq ¯ı ` Ex„DX ” pppxq ´ gpxqq ¨ ´ φpphpxqq ´ φpgpxqq ¯ı
`ΦEx„DX r}h˚pxq ´ gpxq}1s
ď Ex„DX ” gpxq ¨ ´ φpphpxqq ´ φpgpxqq ¯ı ` Ex„DX ” }ppxq ´ gpxq}1}φpphpxqq ´ φpgpxqq}8 ı
`ΦEx„DX r}h˚pxq ´ gpxq}1s
ď Ex„DX ” ppxq ¨ ´ φpphpxqq ´ φpgpxqq ¯ı ` BEx„DX r}ppxq ´ gpxq}1s
`ΦEx„DX r}h˚pxq ´ gpxq}1s
ď Ex„DX ” gpxq ¨ ´ φpphpxqq ´ φpgpxqq ¯ı ` BEx„DX r}ppxq ´ gpxq}1s
`λ˚ΦEx„DX r}ppxq ´ gpxq}1s “ Cpphq ` pB ` λ˚ΦqEx„DX r}ppxq ´ gpxq}1s ,
where the second step applies Hölder’s inequality to each x, the third step follows from the boundedness assumption on φ, and the fourth step uses the characterization h˚pxq “ λ˚ppxq`p1´λ˚qgpxq, for λ˚ P r0, 1s from Proposition 1. Applying Theorem 2 to the churn Cpphq completes the proof.
A.4 PROOF OF PROPOSITION 4
Proposition (Restated). When gpxq “ ppxq,@x, for any given λ P r0, 1s, the minimizer for the distillation loss in (3) over all classifiers h is given by:
h˚pxq “ ppxq,
whereas the minimizer of the anchor loss in (5) is given by:
h˚j pxq “ zj ř
j zj where zj “
"
αp2j pxq ` p1´ αqpjpxq if j “ argmaxk pkpxq p ` αmaxk pkpxqq pjpxq otherwise .
Proof. For the first part, we expand (3) with gpxq “ ppxq, and have for any λ P r0, 1s,
Lλphq “ Epx,yq„D rpλey ` p1´ λqppxqq ¨ φphpxqqs (18) “ λEpx,yq„D rey ¨ φphpxqqs ` p1´ λqEx„DX rppxq ¨ φphpxqqs “ λEx„DX “ Ey|x reys ¨ φphpxqq ‰
` p1´ λqEx„DX rppxq ¨ φphpxqqs “ λEx„DX rppxq ¨ φphpxqqs ` p1´ λqEx„DX rppxq ¨ φphpxqqs “ Ex„DX rppxq ¨ φphpxqqs . (19)
For a fixed x, the inner term in (19) is minimized when h˚pxq “ ppxq. This is because of our assumption that φ is a strictly proper scoring function, i.e. for any distribution u, the weighted loss ř
i uiφipvq is uniquely minimized by v “ u. Therefore (19) is minimized by h˚pxq “ ppxq,@x. For the second part, we expand (5) with gpxq “ ppxq, and have:
Lancphq “ Epx,yq„D ra ¨ φphpxqqs ,
where
a “ " αppxq ` p1´ αqey if y “ argmaxk pkpxq ey otherwise ,
For a given x, let us denote jx “ argmaxk pkpxq. We then have:
Lancphq “ Epx,yq„D rp1py “ jxq pαppxq ` p1´ αqeyq ` 1py ‰ jxqeyq ¨ φphpxqqs “ Ex„DX “ Ey|x rp1py “ jxq pαppxq ` p1´ αqeyq ` 1py ‰ jxqeyq ¨ φphpxqqs ‰
“ Ex„DX
«
ÿ
k
pkpxq pp1pk “ jxq pαppxq ` p1´ αqekq ` 1pk ‰ jxqekq ¨ φphpxqqq ff
“ Ex„DX
«
pjxpxq pαppxq ` p1´ αqejxq ¨ φphpxq ` ÿ
k‰jx
pkpxqφkphpxqq ff
“ Ex„DX „ pjxpxq pαpjxpxq ` p1´ αqqφjxphpxqq
` pjxpxq ÿ
k‰jx
αpkpxqφkphpxqq ` ÿ
k‰jx
pkpxqφkphpxqq 
“ Ex„DX
«
pjxpxq pαpjxpxq ` p1´ αqqφjxphpxqq ` pαpjxpxq ` q ÿ
k‰jx
pkpxqφkphpxqq ff
“ Ex„DX rrppxq ¨ φphpxqqs , (20)
where
rpspxq “ " αp2spxq ` p1´ αqpspxq if s “ jx pαpjxpxq ` qpspxq otherwise
“ " αp2spxq ` p1´ αqpspxq if s “ argmaxk pkpxq pαmaxk pkpxq ` qpspxq otherwise .
For a fixed x, the inner term in (20) is minimized when h˚pxq “ 1Zpxqrppxq, where Zpxq “ ř k rpkpxq. This follows from the fact that for a fixed x, the minimizer of the inner term rppxq ¨ φphpxqq is the same as the the minimizer of the scaled term 1Zpxqrppxq ¨ φphpxqq, and from φ being a strictly proper scoring function. This completes the proof.
B GENERALIZATION BOUNDS
We adapt a result from Menon et al. (2020) to provide generalization bounds for the classification risk and churn in terms of the empirical variance of the loss and churn values. Proposition 7 (Generalization bound for classification risk). Let the scoring function φ : ∆mÑRm` be bounded. Let Vφ Ď RX denote the class of loss functions vpx, yq “ `φpy,hpxqq “ φyphpxqq induced by classifiers h P H. LetMRn “ N8p 1n ,Vφ, 2nq denote the uniform L8 covering number for Vφ. Fix δ P p0, 1q. Then with probability ě 1´ δ over draw of S „ Dn, for any h P H:
Rphq ď pRphq ` O ˜ c VRn phq logpMRn {δq n ` logpM R n {δq n ¸ .
where VRn phq denotes the empirical variance of the loss computed on n examples teJyiφphpxiqqu n i“1. Proposition 8 (Generalization bound for churn). Let the scoring function φ : ∆mÑRm` be bounded. For base classifier g, let Uφ Ď RX denote the corresponding class of divergence functions upxq “ dφphpxq,gpxqq “ gpxqJ ` φphpxqq ´ φpgpxqq ˘
induced by classifiers h P H. Let MCn “ N8p 1n ,Uφ, 2nq denote the uniform L8 covering number for Uφ. Fix δ P p0, 1q. Then with probability ě 1´ δ over draw of S „ Dn, for any h P H:
Cphq ď pCphq ` O ˜ c VCn phq logpMCn {δq n ` logpM C n {δq n ¸ .
where VCn phq denotes the empirical variance of the churn values computed on n examples tgpxiqJ ` φphpxiqq ´ φpgpxiqq ˘ uni“1.
The term VCn captures the variance in the labels provided by the base model g. When this term is low (which is what we would expect in practice from a base model that makes soft-predictions), the churn metric enjoys a tight generalization bound. In contrast, the classification risk is evaluated on one-hot training labels and the variance term VRn there is not impacted by the base model’s scores.
C DEFINITIONS OF NETWORK ARCHITECTURES USED
C.1 FULLY CONNECTED NETWORK
FCN-x refers to the following model with size set to "x". In other words, it’s a simple fully connected network with one hidden layer with x units.
def get_fcn(n_columns, num_classes=10, size=100, weight_init=None):
model = None model = tf.keras.Sequential([
tf.keras.layers.Input(shape=(n_columns,)), tf.keras.layers.Dense(size, activation=tf.nn.relu), tf.keras.layers.Dense(num_classes, activation="softmax"),
])
model.compile( optimizer=tf.keras.optimizers.Adam(), loss=tf.keras.losses.CategoricalCrossentropy(), metrics=[tf.keras.metrics.categorical_accuracy])
return model
C.2 CONVOLUTIONAL NETWORK
Convnet-x refers to the following model with size set to "x". Convnet-1 is based on the lenet5 architecture LeCun et al. (1998).
def get_convnet( input_shape=(28, 28, 3), size=1, num_classes=2, weight_init=None):
model = tf.keras.Sequential() model.add(
tf.keras.layers.Conv2D( filters=16 * size, kernel_size=(5, 5), padding="same", activation="relu", input_shape=input_shape))
model.add(tf.keras.layers.MaxPool2D(strides=2)) model.add(
tf.keras.layers.Conv2D( filters=24 * size, kernel_size=(5, 5), padding="valid", activation="relu"))
model.add(tf.keras.layers.MaxPool2D(strides=2)) model.add(tf.keras.layers.Flatten()) model.add(tf.keras.layers.Dense(128 * size, activation="relu")) model.add(tf.keras.layers.Dense(84, activation="relu")) model.add(tf.keras.layers.Dense(num_classes, activation="softmax"))
model.compile( optimizer=tf.keras.optimizers.Adam(), loss=tf.keras.losses.CategoricalCrossentropy(), metrics=[tf.keras.metrics.categorical_accuracy])
return model
C.3 TRANSFORMER
Transformer-x refers to the following with size set to "x". It is based on keras tutorial on text classification (https://keras.io/examples/nlp/text_classification_ with_transformer/ licensed under the Apache License, Version 2.0).
def get_transformer(maxlen, size=1, num_classes=2, weight_init=None):
model = None
class TransformerBlock(tf.keras.layers.Layer):
def __init__(self, embed_dim, num_heads, ff_dim, rate=0.1, weight_init=None):
super(TransformerBlock, self).__init__() self.att = tf.keras.layers.MultiHeadAttention(
num_heads=num_heads, key_dim=embed_dim) self.ffn = tf.keras.Sequential([
tf.keras.layers.Dense(ff_dim, activation="relu"), tf.keras.layers.Dense(embed_dim),
]) self.layernorm1 = tf.keras.layers.LayerNormalization(epsilon=1e-6) self.layernorm2 = tf.keras.layers.LayerNormalization(epsilon=1e-6)
def call(self, inputs, training): attn_output = self.att(inputs, inputs) #attn_output = self.dropout1(attn_output, training=training) out1 = self.layernorm1(inputs + attn_output) ffn_output = self.ffn(out1) return self.layernorm2(out1 + ffn_output)
class TokenAndPositionEmbedding(tf.keras.layers.Layer):
def __init__( self, maxlen, vocab_size, embed_dim,
): super(TokenAndPositionEmbedding, self).__init__()
self.token_emb = tf.keras.layers.Embedding( input_dim=vocab_size, output_dim=embed_dim)
self.pos_emb = tf.keras.layers.Embedding( input_dim=maxlen, output_dim=embed_dim)
def call(self, x): maxlen = tf.shape(x)[-1] positions = tf.range(start=0, limit=maxlen, delta=1) positions = self.pos_emb(positions) x = self.token_emb(x) return x + positions
embed_dim = 32 * size # Embedding size for each token num_heads = 2 * size # Number of attention heads ff_dim = 32 * size # Hidden layer size in feed forward network inside transformer
inputs = tf.keras.layers.Input(shape=(maxlen,)) embedding_layer = TokenAndPositionEmbedding(maxlen, 20000, embed_dim) x = embedding_layer(inputs) transformer_block = TransformerBlock(embed_dim, num_heads, ff_dim,
weight_init) x = transformer_block(x) x = tf.keras.layers.GlobalAveragePooling1D()(x)
outputs = tf.keras.layers.Dense(num_classes, activation="softmax")(x)
model = tf.keras.Model(inputs=inputs, outputs=outputs) model.compile(
optimizer=tf.keras.optimizers.Adam(), loss=tf.keras.losses.CategoricalCrossentropy(), metrics=[tf.keras.metrics.categorical_accuracy])
return model
D MODEL TRAINING CODE
def model_trainer(get_model, X_train, y_train, X_test, y_test, weight_init=None, validation_data=None, warm=True, mixup_alpha=-1, codistill_alpha=-1, distill_alpha=-1, anchor_alpha=-1, anchor_eps=-1):
model = get_model() if weight_init is not None and warm: model.set_weights(weight_init)
if FLAGS.loss == "squared": model.compile(
optimizer=tf.keras.optimizers.Adam(), loss=tf.keras.losses.MeanSquaredError(), metrics=[tf.keras.metrics.categorical_accuracy])
callback = tf.keras.callbacks.EarlyStopping(monitor="val_loss", patience=3) history = None
if distill_alpha >= 0: original_model = get_model() original_model.set_weights(weight_init) y_pred = original_model.predict(X_train) y_use = distill_alpha * y_pred + (1 - distill_alpha) * y_train history = model.fit(
x=X_train, y=y_use,
epochs=FLAGS.n_epochs, callbacks=[callback], validation_data=validation_data)
elif anchor_alpha >= 0 and anchor_eps >= 0: original_model = get_model() original_model.set_weights(weight_init) y_pred = original_model.predict(X_train) y_pred_hard = np.argmax(y_pred, axis=1) y_hard = np.argmax(y_train, axis=1) correct = (y_pred_hard == y_hard) correct = np.tile(correct, (y_train.shape[1], 1)) correct = np.transpose(correct) correct = correct.reshape(y_train.shape) y_use = np.where(correct,
anchor_alpha * y_pred + (1 - anchor_alpha) * y_train, y_train * anchor_eps)
history = model.fit( x=X_train, y=y_use, epochs=FLAGS.n_epochs, callbacks=[callback], validation_data=validation_data)
elif mixup_alpha >= 0: training_generator = deep_utils.MixupGenerator(
X_train, y_train, alpha=mixup_alpha)() history = model.fit(
x=training_generator, validation_data=validation_data, steps_per_epoch=int(X_train.shape[0] / 32), epochs=FLAGS.n_epochs, callbacks=[callback])
elif codistill_alpha >= 0: teacher_model = get_model() if weight_init is not None and warm:
teacher_model.set_weights(weight_init) val_losses = [] optimizer = tf.keras.optimizers.Adam() global_step = 0 alpha = 0 codistillation_warmup_steps = 0
for epoch in range(FLAGS.n_epochs): X_train_, y_train_ = sklearn.utils.shuffle(X_train, y_train) batch_size = 32 for i in range(int(X_train_.shape[0] / batch_size)):
if global_step >= codistillation_warmup_steps: alpha = codistill_alpha
else: alpha = 0.
with tf.GradientTape() as tape: X_batch = X_train_[i * 32:(i + 1) * 32, :] y_batch = y_train_[i * 32:(i + 1) * 32, :] prob_student = model(X_batch, training=True) prob_teacher = teacher_model(X_batch, training=True) loss = deep_utils.compute_loss(prob_student, prob_teacher, y_batch,
alpha) trainable_weights = model.trainable_weights + teacher_model.trainable_weights grads = tape.gradient(loss, trainable_weights) optimizer.apply_gradients(zip(grads, trainable_weights))
global_step += 1 val_preds = model.predict(validation_data[0]) val_loss = np.sum(
deep_utils.cross_entropy(validation_data[1].astype("float32"), val_preds))
val_losses.append(val_loss) if len(val_losses) > 3 and min(val_losses[-3:]) > val_losses[-4]:
break
else: history = model.fit(
X_train, y_train, epochs=FLAGS.n_epochs, callbacks=[callback], validation_data=validation_data)
y_pred_train = model.predict(X_train) y_pred_test = model.predict(X_test) return y_pred_train, y_pred_test, model.get_weights()
E ADDITIONAL EXPERIMENTAL RESULTS
E.1 ADDITIONAL OPENML RESULTS
E.1.1 INITIAL SAMPLE 100, BATCH SIZE 1000, VALIDATION SIZE 100
In Tables 3 and 4, we show the churn at cold accuracy metric across network sizes (fcn-10, fcn-100, fcn-1000, fcn-10000, fcn-100000). Table 5 shows the standard error bars. They are obtained by fixing the dataset and model, and taking the 100 accuracy and churn results from each baseline and calculating the standard error, which is the standard deviation of the mean. We then report the average standard error across the baselines We see that distillation is the best 52% of the time.
E.1.2 INITIAL SAMPLE 1000, BATCH SIZE 1000, VALIDATION SIZE 100
In Tables 6 and 7, we show the churn at cold accuracy metric across network sizes (fcn-10, fcn-100, fcn-1000, fcn-10000, fcn-100000). We see that distillation consistently performs strongly across datasets and sizes of networks. Table 8 shows the standard error bars. We see that distillation is the best 84% of the time.
E.2 ADDITIONAL MNIST VARIANT RESULTS
E.2.1 INITIAL SAMPLE SIZE 100, BATCH SIZE 1000, VALIDATION SIZE 100
We show full results in Table 9. We see that distillation is the best for 24 out of the 50 combinations of dataset and network. Error bands can be found in Table 10.
E.2.2 INITIAL SAMPLE SIZE 1000, BATCH SIZE 1000, VALIDATION SIZE 100
We show full results in Table 11. We see that distillation is the best for 42 out of the 50 combinations of dataset and network. Error bands can be found in Table 12.
E.2.3 INITIAL SAMPLE SIZE 10000, BATCH SIZE 1000, VALIDATION SIZE 1000
We show full results in Table 13. We see that in this situation, label smoothing starts becoming competitive with distillation with either of them being the best. Distillation is the best for 32 out of the 50 combinations of dataset and network, and losing marginally to label smoothing in other cases. See Table 14 for error bands.
E.3 ADDITIONAL SVHN AND CIFAR RESULTS
E.3.1 INITIAL SAMPLE 100, BATCH SIZE 1000, VALIDATION SIZE 100
Results are in Table 15, where we see that distillation is best on 8 out of 10 combinations of dataset and network. Error bands can be found in Table 16.
E.3.2 INITIAL SAMPLE 1000, BATCH SIZE 1000, VALIDATION SIZE 100
The results can be found in Table 17. We include the error bands here in Table 18. Distillation is best in all combinations.
E.3.3 INITIAL SAMPLE 10000, BATCH SIZE 1000, VALIDATION SIZE 1000
Results are in Table 19, where we see that distillation is best on all combinations of dataset and network. Error bands can be found in Table 20.
E.4 ADDITIONAL CELEBA RESULTS
E.4.1 INITIAL SAMPLE 100, BATCH SIZE 1000, VALIDATION SIZE 100
Tables 21, 22, 23, and 24 show the performance of CelebA tasks when we instead use an initial sample size of 100. We see that across the 200 combinations of task and network, distillation is the best 192 of time, or 96% of the time. The error bands can be found in Table 25.
E.4.2 INITIAL SAMPLE 1000, BATCH SIZE 1000, VALIDATION SIZE 100
We show some additional CelebA results for initial sample 1000 and batch size 1000 in Tables 26, 27, 28, and 29 which show performance for each dataset across convnet-1, convnet-2, convnet-4, convent-8, convnet-16. This gives us 40 ¨ 5 “ 200 results, of which distillation performs the best 158 out of those settings, or 79% of the time. The error bands can be found in Table 30.
E.4.3 INITIAL SAMPLE SIZE 10000, BATCH SIZE 1000, VALIDATION SIZE 1000
Tables 31, 32, 33, and 34 show the performance of CelebA tasks when we instead use an initial sample size of 10000. We see that across the 200 combinations of task and network, distillation is the best 183 of time, or 91.5% of the time. The error bands can be found in Table 35.
E.5 CIFAR10 AND CIFAR100 ON RESNET
Results can be found in Table 36. We see that distillation outperforms in every case.
E.6 ADDITIONAL IMDB RESULTS
In Table 37, we show the results for the IMDB dataset and transformer networks for initial batch sizes of 100, 1000 and 10000 with the batch size fixed at 1000. The error bands can be found in Table 38. We see that for initial sample size of 100, distillation performs poorly for the smaller networks as the process of distillation hurts the performance with a weak teacher trained on only 100 examples, but performs well for the larger networks. For initial sample size of 1000 and 10000, distillation is the clear winner losing in only one instance. We show the full Pareto frontiers and cost curves in Figure 4.

Review summaries:
In real-life applications of predictive models, predictions often form a step of the process. Changes in the predictive model often need to be validated end to end using methods such as A/B tests before they can be used in production. Thus for certain class of problems, there is a need to control the churn or the difference in the predictive model due to retraining of the model towards a more robust pipeline. The authors present an approach to control this churn via a simple distillation method. They also show that their distillation method, under certain assumptions, is equivalent to a constrained optimization problem that explicitly constrains the "churn" without the added complexity of constrained optimization. They validated their method by conducting experiments on a number of baselines on a wide range of datasets and model architectures. 

This paper explores the relationship between the low-churn problem and distillation. The authors show that there is an equivalence between those two methods and that distillation performs particularly well on low-churn dataset tasks. The authors propose a novel churn reduction algorithm based on distillation which involves the training of a classifier by minimizing a distilled loss and solving a convex program. The authors  provide theoretical guarantees for the proposed algorithm and explain the advantages of the proposed approach compared to the anchor loss, another churn-reduction method.   The authors validate empirically their approach on 12 OpenML datasets, 10 MNIST variants, CIFAR10, CIFAR100 and IMDB.