# Towards Understanding Knowledge Distillation

Mary Phuong  Christoph H. Lampert

# Supplementary Material

Mary Phuong  Christoph H. Lampert

Knowledge distillation, i.e. one classifier being trained on the outputs of
another classifier, is an empirically very successful technique for knowledge
transfer between classifiers. It has even been observed that classifiers learn
much faster and more reliably if trained with the outputs of another
classifier as soft labels, instead of from ground truth data. So far, however,
there is no satisfactory theoretical explanation of this phenomenon. In this
work, we provide the first insights into the working mechanisms of
distillation by studying the special case of linear and deep linear
classifiers. Specifically, we prove a generalization bound that establishes
fast convergence of the expected risk of a distillation-trained linear
classifier. From the bound and its proof we extract three key factors that
determine the success of distillation: _data geometry_ – geometric properties
of the data distribution, in particular class separation, has an immediate
influence on the convergence speed of the risk; _optimization bias_ – gradient
descent optimization finds a very favorable minimum of the distillation
objective; and _strong monotonicity_ – the expected risk of the student
classifier always decreases when the size of the training set grows.

Machine Learning, Deep Learning, Distillation, Theory

##  1 Introduction

In 2014, Hinton et al. (2014) made a surprising observation: they found it
_easier_ to train classifier using the real-valued outputs of another
classifier as target values than using actual ground-truth labels. Calling the
procedure _knowledge distillation_ , or _distillation_ for short, they noticed
the positive effect to occur even when the existing classifier (called
_teacher_) was trained on the same data as it used afterwards for the
distillation-training of the new classifier (called _students_). Since that
time, the positive properties of distillation-based training has been
confirmed several times: the optimization step is generally more well-behaved
than the optimization step in label-based training, and it needs less if any
regularization or specific optimization tricks. Consequently, in several
fields, distillation has become a standard technique for transfering the
information between classifiers with different architectures, such as from
deep to shallow neural networks or from ensembles of classifiers to individual
ones.

While the practical benefits of distillation are beyond doubt, its theoretical
justification remains almost completely unclear. Existing explanations rarely
go beyond qualitative statements, e.g. claiming that learning from soft labels
should be easier than learning from hard labels, or that in a multi-class
setting the teacher’s output provides information about how similar different
classes are to each other.

In this work, we follow a different approach. Instead of studying distillation
in full generality, we restrict our attention to a simplified, analytically
tractable, setting: binary classification with linear teacher and linear
student (either shallow or deep linear networks). For this situation, we
achieve the first quantitative results about the effectiveness of
distillation-based training. Specifically, our main results are: 1) We prove a
generalization bound that establishes extremely fast convergence of the risk
of distillation-trained classifiers. In fact, it can reach zero risk from
finite training sets. 2) We identify three key factors that explain the
success of distillation: _data geometry_ – geometric properties of the data
distribution, in particular class separation, directly influence the
convergence speed of the student’s risk; _optimization bias_ – even though the
distillation objective can have many optima, gradient descent optimization is
guaranteed to find a particularly favorable one; and _strong monotonicity_ –
increasing the training set always decreases the risk of the student
classifier.

##  2 Related Work

Ideas underpinning distillation have a long history dating back to the work of
Ba & Caruana (2014); Bucilua et al. (2006); Craven & Shavlik (1996); Li et al.
(2014); Liang et al. (2008). In its current and most widely known form, it was
introduced by Hinton et al. (2014) in the context of neural network
compression.

Since then, distillation has quickly gained popularity among practitioners and
established its place in deep learning folklore. It has been found to work
well across a wide range of applications, including e.g. transferring from one
architecture to another (Geras et al., 2016), compression (Howard et al.,
2017; Polino et al., 2018), integration with first-order logic (Hu et al.,
2016) or other prior knowledge (Yu et al., 2017), learning from noisy labels
(Li et al., 2017), defending against adversarial attacks (Papernot et al.,
2016), training stabilization (Romero et al., 2015; Tang et al., 2016),
distributed learning (Polino et al., 2018), reinforcement learning (Rusu et
al., 2016) and data privacy (Celik et al., 2017).

In contrast to the empirical success, the mathematical principles underlying
distillation’s effectiveness have largely remained a mystery. Only very works
examine distillation from a theoretical perspective. Lopez-Paz et al. (2016)
cast distillation as a form of learning using privileged information (LUPI,
Vapnik & Izmailov 2015), a learning setting in which additional per-instance
information is available at training time but not at test time. However, the
LUPI view concentrates on the aspect that the teacher’s supervision to the
student is noise-free. This argument fails to explain, e.g., the success of
distillation even when the original problem is noise-free to start with. The
only other theoretical analysis we are aware of is by Urner et al. (2011), who
study distillation as a form of semi-supervised learning. Specifically, they
show that a two-step procedure, consisting of first training a teacher on a
small labelled dataset and then training the student on a separate large
dataset labelled by the teacher, can be more effective than training the
student directly on the small labelled dataset. The paper’s focus is on the
semi-supervised aspect, i.e. the gains from having a large unlabelled dataset.

A more distantly related topic is _machine teaching_ (Zhu, 2015). In machine
teaching, a machine learning system is trained by a human teacher, whose goal
is to hand-pick as small a training set as possible, while ensuring that the
machine learns a desired hypothesis. Transferring knowledge via machine
teaching techniques is extremely effective: perfect transfer is often possible
from a small finite teaching set (Zhu, 2013; Liu & Zhu, 2016). However, the
price for this radical reduction in sample complexity is the expensive
training set construction. Our work shows that, at least in the linear
setting, distillation achieves a similar effectiveness with a more practical
form of supervision.

##  3 Background: Linear Distillation

We formally introduce distillation in the context of binary classification.
Let $\mathcal{X}\subseteq\mathbb{R}^{d}$ be the input space,
$\mathcal{Y}=\\{0,1\\}$ the label space, and $P_{\mathbf{x}}$ the probability
distribution of inputs. We assume $P_{\mathbf{x}}$ has a density.

The _teacher_ $h^{*}:\mathcal{X}\to\mathcal{Y}$ is a fixed linear classifier,
i.e.
$h^{*}(\mathbf{x})=\mathds{1}{\left\\{\mathbf{w}_{*}^{\intercal}\mathbf{x}\geq
0\right\\}}$ for some
$\mathbf{w}_{*}\in\mathbb{R}^{d}\setminus{\left\\{\mathbf{0}\right\\}}$, where
$\mathds{1}{\left\\{.\right\\}}$ returns 1 if the argument is true and 0
otherwise. The _student_ also is a linear classifier,
$h(\mathbf{x})=\mathds{1}{\left\\{\mathbf{w}^{\intercal}\mathbf{x}\geq
0\right\\}}$.

We allow the weight vector to be parameterised as a product of matrices,
$\mathbf{w}^{\intercal}=\mathbf{W}_{N}\mathbf{W}_{N-1}\cdots\mathbf{W}_{1}$
for some $N\geq 1$. When $N\geq 2$, this parameterisation is known as a _deep
linear network_. Although deep linear networks have no additional capacity
compared to directly parameterised linear classifiers
$(N=1;\mathbf{w}^{\intercal}=\mathbf{W}_{1})$, they induce different gradient-
descent dynamics, and are often studied as a first step towards understanding
deep nonlinear networks (Saxe et al., 2014; Kawaguchi, 2016; Hardt & Ma,
2017).

_Distillation_ proceeds as follows. First, we collect a _transfer set_
${\left\\{(\mathbf{x}_{i},y_{i})\right\\}}_{i=1}^{n}$ consisting of inputs
$\mathbf{x}_{i}$ sampled i.i.d. from $P_{\mathbf{x}}$, and _soft labels_
$y_{i}=\sigma(\mathbf{w}_{*}^{\intercal}\mathbf{x}_{i})$ provided by the
teacher, where $\sigma$ is the sigmoid function, $\sigma(x)=1/(1+\exp(-x))$.
The soft (real-valued) labels can be thought of as a more informative version
of the hard (0/1-valued) labels of the standard classification setting. We
write
$\mathbf{X}={\left[\mathbf{x}_{1},\dots,\mathbf{x}_{n}\right]}\in\mathbb{R}^{d\times
n}$ for the data matrix. Second, the student is trained by minimizing the
(normalized) cross-entropy loss,

$L^{1}(\mathbf{w})=-\frac{1}{n}\sum_{i=1}^{n}\Big{[}y_{i}\log\sigma(\mathbf{w}^{\intercal}\mathbf{x}_{i})\\\
+(1-y_{i})\log(1-\sigma(\mathbf{w}^{\intercal}\mathbf{x}_{i}))\Big{]}-L^{*},$
(1)

where $L^{*}$ is a normalization constant, such that the minimum of $L^{1}$ is
0. It only serves the purpose of simplifying notation and has no effect on the
optimization.

The student observes the loss as a function of its parameters, i.e. the
individual weight matrices,

$L(\mathbf{W}_{1},\dots,\mathbf{W}_{N}):=L^{1}((\mathbf{W}_{N}\mathbf{W}_{N-1}\cdots\mathbf{W}_{1})^{\intercal}),$
(2)

and optimizes it via gradient descent. For the theoretical analysis, we avoid
the complications of stepsize selection and adopt the notion of _infinitesimal
step size_ 111For readers who are unfamiliar with gradient flows, it suffices
to think of the stepsize as finite and ”sufficiently small”., which turns the
gradient descent procedure into a continuous _gradient flow_. We write
$\mathbf{W}_{i}(\tau)$ for the value of the matrix $\mathbf{W}_{i}$ at time
$\tau\in[0,\infty)$, with $\mathbf{W}_{i}(0)$ denoting the initial value, and
$\mathbf{w}(\tau)^{\intercal}=\mathbf{W}_{N}(\tau)\cdots\mathbf{W}_{1}(\tau)$.
Then, each $\mathbf{W}_{i}(\tau)$, for $i\in{\left\\{1,\dots,N\right\\}}$,
evolves according to the following differential equation.

${\frac{\partial\mathbf{W}_{i}(\tau)}{\partial\tau}}=-{\frac{\partial
L}{\partial\mathbf{W}_{i}}}(\mathbf{W}_{1}(\tau),\dots,\mathbf{W}_{N}(\tau)).$
(3)

The student is trained until convergence, i.e. $\tau\to\infty$. We measure the
_transfer risk_ of the trained student, defined as the probability that its
prediction differs from that of the teacher,

$R(h)=\operatorname*{\mathbb{P}}_{\mathbf{x}\sim
P_{\mathbf{x}}}{\left[h(\mathbf{x})\neq h^{*}(\mathbf{x})\right]}.$ (4)

In Section 4.2, we will derive a bound for the transfer risk and establish how
rapidly it decreases as a function of $n$.

##  4 Generalization Properties of Linear Distillation

This section contains our main technical results. First, in Section 4.1, we
provide an explicit characterization of the outcome of distillation-based
training in the linear setting. In other words, we identify _what the student
actually learns_. In particular, we prove that the student is able to
perfectly identify the teacher’s weight vector, if the number of training
examples ($n$) is equal to the dimensionality of the data ($d$) or higher. If
less data is available, under minor assumptions, the student finds the best
approximation of the teacher’s weight vector that is possible within the
subspace spanned by the training data.

In Section 4.2 we use these results to study the generalization properties of
the student classifier, i.e. we characerize _how fast the student learns_.
Specifically, we prove a generalization bound with much more appealing
properties than what is possible in the classic situation of learning from
hard labels. As soon as enough training data is available ($n\geq d$), the
student’s risk is simply $0$. Otherwise, the risk can be bounded explicitly in
a distribution-dependent way that, in particular, allows us to identify three
key factors that explain the success of distillation, and to understand when
distillation-based transfer is most effective.

###  4.1 What Does the Student Learn?

In this section, we derive in closed form the asymptotic solution to the
gradient flow (3) undergone by the student when trained by distillation. We
state the results separately for directly parameterized linear classifiers
$(N=1)$ and deep linear networks $(N\geq 2)$, as the settings require slightly
different ways of initializing parameters. Namely, in the former case,
initializing $\mathbf{w}(0)=\mathbf{0}$ is valid, while in the latter case,
this would lead to vanishing gradients, and we have to initialize with small
(typically random) values.

######  Theorem 1.

Assume the student is a directly parameterised linear classifier $(N=1)$ with
weight vector initialised at zero, $\mathbf{w}(0)=\mathbf{0}$. Then, the
student’s weight vector fulfills almost surely

$\mathbf{w}(t)\to\hat{\mathbf{w}},$ (5)

for $t\to\infty$, with

$\hat{\mathbf{w}}=\left\\{\begin{array}[]{cl}\mathbf{w}_{*},&\ n\geq d,\\\
\mathbf{X}(\mathbf{X}^{\intercal}\mathbf{X})^{-1}\mathbf{X}^{\intercal}\mathbf{w}_{*},&\
n<d.\end{array}\right.$ (6)

Theorem 1 shows a remarkable property of distillation-based training for
linear systems: if sufficiently many (at least $d$) data points are available,
the student exactly recovers the teacher’s weight vector, $\mathbf{w}_{*}$.
This is a strong justification for distillation as a method of _knowledge
transfer_ between linear classifiers and the theorem establishes that the
effect occurs not just in the infinite data limit ($n\to\infty$), as one might
have expected, but already in the finite sample regime ($n\geq d$).

When few data points are available ($n<d$), the weight vector learned by the
student is simply the _projection of the teacher’s weight vector onto the data
span_ (the subspace spanned by the columns of $\mathbf{X}$). In a sense, this
is the best the student can do: the gradient descent update direction
${\frac{\partial\mathbf{w}(\tau)}{\partial\tau}}$ always lies in the data
span, so there is no way for the student to learn anything outside of it. The
projection is the best subspace-constrained approximation of $\mathbf{w}_{*}$
with respect to the Euclidean norm. The extent to which Euclidean closeness
implies closeness in predictions is a separate matter, and the subject of
Section 4.2.

###### Proof sketch of Theorem 1.

First, notice that $\hat{\mathbf{w}}$ is a global minimiser of $L^{1}$.
Moreover, when $n\geq d$, it is (almost surely wrt. $\mathbf{X}\sim
P_{\mathbf{x}}^{n}$) unique, and when $n<d$, it is (almost surely) the only
one lying in the span of $\mathbf{X}$ and thus potentially reachable by
gradient descent.

The proof consists of two parts. We prove that a) the gradient flow (3) drives
the objective value towards the optimum, $L^{1}(\mathbf{w}(t))\to 0$ as
$t\to\infty$, and b) the distance between $\mathbf{w}(t)$ and the claimed
asymptote $\hat{\mathbf{w}}$ is upper-bounded by the objective gap,

${\left\|\mathbf{w}(t)-\hat{\mathbf{w}}\right\|}^{2}\leq
cL^{1}(\mathbf{w}(t))$ (7)

for some constant $c>0$ and all $t\in[0,\infty)$.

For part a), observe that $L^{1}$ is convex. For any $\tau\in[0,\infty)$, the
time-derivative of $L^{1}(\mathbf{w}(\tau))$ is negative unless we are at a
global minimum,

$\displaystyle\begin{split}{\frac{\mathrm{d}}{\mathrm{d}\tau}}L^{1}(\mathbf{w}(\tau))&=\nabla
L^{1}(\mathbf{w}(\tau))^{\intercal}{\left({\frac{\partial\mathbf{w}(\tau)}{\partial\tau}}\right)}\\\
&=-{\left\|\nabla L^{1}(\mathbf{w}(\tau))\right\|}^{2},\end{split}$ (8)

implying that the objective value $L^{1}(\mathbf{w}(\tau))$ decreases
monotonically in $\tau$. Hence, if we denote by
$\mathcal{W}={\left\\{\mathbf{w}:L^{1}(\mathbf{w})\leq
L^{1}(\mathbf{0})\right\\}}$ the $L^{1}(\mathbf{0})$-sublevel set of the
objective, we know that $\mathbf{w}(\tau)\in\mathcal{W}$ for all
$\tau\in[0,\infty)$. One can show that on this set, $L^{1}$ satisfies strong
convexity, but only along certain directions: for some $\mu>0$ and all
$\mathbf{w},\mathbf{v}\in\mathcal{W}$ such that
$\mathbf{v}-\mathbf{w}\in\mathrm{span}(\mathbf{X})$,

$L^{1}(\mathbf{v})\geq L^{1}(\mathbf{w})+\nabla
L^{1}(\mathbf{w})^{\intercal}(\mathbf{v}-\mathbf{w})+\frac{\mu}{2}{\left\|\mathbf{v}-\mathbf{w}\right\|}^{2}.\\!\\!\\!\\!$
(9)

This allows us (via a technical derivation that we omit here) to relate the
objective gap to the gradient norm: it can be shown that there exists
$c^{\prime}>0$, such that

$c^{\prime}L^{1}(\mathbf{w})\leq\frac{1}{2}{\left\|\nabla
L^{1}(\mathbf{w})\right\|}^{2}.$ (10)

Applying the above to $\mathbf{w}(\tau)$ in (8), we are able to bound the
amount of reduction in the objective in terms of the objective itself,
ultimately proving linear convergence.

For part b), invoke (9) with $\mathbf{v}=\mathbf{w}(\tau)$ and
$\mathbf{w}=\hat{\mathbf{w}}$; this gives
$L^{1}(\mathbf{w}(\tau))\geq\frac{\mu}{2}{\left\|\mathbf{w}(\tau)-\hat{\mathbf{w}}\right\|}^{2}.$
∎

The full proof is given in the Supplementary Material.

The next results is the analog of Theorem 1 for deep linear networks. Here,
some technical conditions are needed because the parameters cannot all be
initialized at $0$.

######  Theorem 2.

Let $\hat{\mathbf{w}}$ be defined as in Theorem 1. Assume the student is a
deep linear network, initialized such that for some $\epsilon>0$,

$\displaystyle{\left\|\mathbf{w}(0)\right\|}<\min\Big{\\{}{\left\|\hat{\mathbf{w}}\right\|},\epsilon^{N}$
$\displaystyle{\left(\epsilon^{2}{\left\|\hat{\mathbf{w}}\right\|}^{-\frac{2}{N}}+{\left\|\hat{\mathbf{w}}\right\|}^{2-\frac{2}{N}}\right)}^{-\frac{N}{2}}\Big{\\}},$
(11) $\displaystyle L^{1}(\mathbf{w}(0))$ $\displaystyle<L^{1}(\mathbf{0}),$
(12) $\displaystyle\mathbf{W}_{j+1}(0)^{\intercal}\mathbf{W}_{j+1}(0)$
$\displaystyle=\mathbf{W}_{j}(0)\mathbf{W}_{j}(0)^{\intercal}$ (13)

for $j=1,\dots,N-1$. Then, for $n\geq d$, student’s weight vector fulfills
almost surely

$\mathbf{w}(t)\to\hat{\mathbf{w}},$ (14)

and for $n<d$,

${\left\|\mathbf{w}(t)-\hat{\mathbf{w}}\right\|}\leq\epsilon,$ (15)

for all $t$ large enough.

The interpretation of the theorem is analogous to Theorem 1. Given enough data
($n\geq d$), the student learns to perfectly mimic the teacher. Otherwise, it
learns an approximation at least $\epsilon$-close to the projection of the
teacher’s weight vector onto the data span.

The conditions (11)–(13) appear for technical reasons and a closer look at
them shows that they do not pose problems in practice. Condition (11) states
that the network’s weights should be initialised with sufficiently small
values. Consequently, this assumption is easy to satisfy in practice.
Condition (12) requires that the initial loss is smaller than the loss at
$\mathbf{w}=\mathbf{0}$. This condition guarantees that the gradient flow does
not hit the point $\mathbf{w}=\mathbf{0}$, where all gradient vanish and the
optimization would stop prematurely. In practice, when the step size is
finite, the condition is not needed. Nevertheless, it is also not hard to
satisfy: for any near-zero initialisation, $\mathbf{w}(0)=\mathbf{w}_{0}$,
either $\mathbf{w}_{0}$ or $-\mathbf{w}_{0}$ will satisfy (12), so at most one
has to flip the sign on one of the $\mathbf{W}_{i}(0)$ matrices. Finally,
condition (13) is called _balancedness_ (Arora et al., 2018) and discussed in-
depth in (Arora et al., 2019)). It simplifies the analysis of matrix products
and makes it possible to explicitly analyze the evolution of $\mathbf{w}$
induced by gradient flow in the $\mathbf{W}_{i}$’s. Assuming near-zero
initialization, the condition is automatically satisfied approximately and
there is some evidence (Arora et al., 2019) suggesting that _approximate
balancedness_ may suffice for convergence results of the kind we are
interested in. Otherwise, the condition can also simply be enforced
numerically.

###### Proof sketch of Theorem 2.

First, we establish convergence in the objective, $L^{1}(\mathbf{w}(t))\to 0$
as $t\to\infty$, similarly to the case $N=1$. Unlike that case, however, the
evolution of the end-to-end weight vector $\mathbf{w}(\tau)$ is governed by
complex mechanics induced by gradient flow in $\mathbf{W}_{i}$’s. A key tool
for analyzing this induced flow was recently established in (Arora et al.,
2018): the authors show that the induced flow behaves similarly to gradient
flow with momentum applied directly to $\mathbf{w}$. Making use of this
result, one can proceed analogously as in the case of $N=1$ to show
convergence in the objective.

Second, to show convergence in parameter space, we decompose $\mathbf{w}(t)$
into its projection onto the span of $\mathbf{X}$, and an orthogonal
component. The $\mathbf{X}$-component converges to $\hat{\mathbf{w}}$, by
strong convexity arguments as in the case $N=1$. It remains to show that the
orthogonal component is small. Now, recall that in the case $N=1$, we
initialise at $\mathbf{w}(0)=\mathbf{0}$ and move within the span, so the
orthogonal component is always zero. When $N\geq 2$, the situation is
different: a) we initialise with a potentially non-zero orthogonal component
(because we need to avoid the spurious stationary point
$\mathbf{w}=\mathbf{0}$), and b) the momentum term causes the orthogonal
component to grow during optimisation. Luckily, the rate of growth can be
precisely characterised and controlled by the initialisation norm
${\left\|\mathbf{w}(0)\right\|}$, so depending on how close to zero we
initialise, we can upper-bound the size of the orthogonal component. This
yields a bound on the distance
${\left\|\mathbf{w}(t)-\hat{\mathbf{w}}\right\|}$. ∎

For the formal proof, we refer the reader to the Supplemental Material.

###  4.2 How Fast Does the Student Learn?

In this section, we present our main quantitative result, a bound for the
expected transfer risk in linear distillation.

We first introduce some geometric concepts. For any
$\mathbf{u},\mathbf{v}\in\mathbb{R}^{d}\setminus\\{\mathbf{0}\\}$, denote by
$\bar{\alpha}(\mathbf{u},\mathbf{v})\in[0,\pi/2]$ the unsigned angle between
the vectors $\mathbf{u}$ and $\mathbf{v}$

$\bar{\alpha}(\mathbf{u},\mathbf{v})=\cos^{-1}\\!{\left(\frac{{\left|\mathbf{u}^{\intercal}\mathbf{v}\right|}}{{\left\|\mathbf{u}\right\|}\cdot{\left\|\mathbf{v}\right\|}}\right)}.$
(16)

A key quantity for us is the angle between $\mathbf{w}_{*}$ and a randomly
chosen $\mathbf{x}$, for $\mathbf{x}\sim P_{\mathbf{x}}$. For a given transfer
task $(P_{\mathbf{x}},\mathbf{w}_{*})$, we denote by $p$ the reverse cdf of
$\bar{\alpha}(\mathbf{w}_{*},\mathbf{x})$,

$p(\theta)=\operatorname*{\mathbb{P}}_{\mathbf{x}\sim
P_{\mathbf{x}}}[\bar{\alpha}(\mathbf{w}_{*},\mathbf{x})\geq\theta]\qquad\text{for}\quad\theta\in[0,\pi/2].$
(17)

$\mathbf{w}_{*}$$\mathbf{w}_{*}$$\mathbf{w}_{*}$$P_{\mathbf{x}}$$P_{\mathbf{x}}$$P_{\mathbf{x}}$Task
ATask BTask C
---

Figure 1: Schematic illustration of $p(\theta)$ for three different transfer
tasks. In Task A, the angular alignment between the data and the teacher’s
weight vector is high, so $p(\theta)$ is fast descreasing. In Task B, it is
also high, and in additional the classes are separated by a margin, so
$p(\theta)$ reaches $0$ before $\beta=\pi/2$. In Task C, the angular alignment
is low, so $p(\theta)$ decreases rather slowly.

By construction, $p(\theta)$ is monotonically decreasing, starting with
$p(0)=1$ and approaches $0$ for $\theta\to\pi/2$. Figure 1 illustrates this
behavior for three exemplary data distributions as _Tasks A,B and C_. In _Task
A_ , the probability mass is well aligned with the direction of the teacher’s
weight vector. The probability that a randomly chosen data point
$x\sim{P_{\mathbf{x}}}$ has a large angle with $\mathbf{w}_{*}$ is small.
Therefore, the value of $p(\theta)$ quickly drops with growing angle $\theta$.
In _Task B_ , the data also aligns well with $\mathbf{w}_{*}$, but in
addition, the data region remains bounded away from the decision boundary.
Therefore, certain large angles can never occur, i.e. there exists a value
$\theta_{0}<\pi/2$, such that $p(\theta)=0$ for $\theta\geq\theta_{0}$. In
_Task C_ , the situation is different: the data distribution is concentrated
along the decision boundary and the probability of a angle between
$\mathbf{w}_{*}$ and a randomly chosen data point $x\sim{P_{\mathbf{x}}}$ is
large. As a consequence, $p(\theta)$ drops more slowly with growing angle than
in the previous two settings.

We are now ready to state the main result. For improved readability, we phrase
it for a student with infinitesimally small initialization, i.e. $\epsilon\to
0$. The general formulation can be found in the supplemental material.

######  Theorem 3 (Transfer risk bound for linear distillation).

For any training set $\mathbf{X}\in\mathbb{R}^{d\times n}$, let
$\hat{h}_{\mathbf{X}}(\mathbf{x})=\mathds{1}{\left\\{\hat{\mathbf{w}}^{\intercal}\mathbf{x}\geq
0\right\\}}$ be the linear classifier learned by distillation from a teacher
with weight vector $\mathbf{w}_{*}$. Then, when $n\geq d$, it holds that

$\displaystyle\operatorname*{\mathbb{E}}_{\mathbf{X}\sim
P_{\mathbf{x}}^{\otimes n}}{\left[R\big{(}\hat{h}_{\mathbf{X}}\big{)}\right]}$
$\displaystyle=0.$ (18) For $n<d$, it holds for any $\beta\in[0,\pi/2]$ that
$\displaystyle\operatorname*{\mathbb{E}}_{\mathbf{X}\sim
P_{\mathbf{x}}^{\otimes n}}{\left[R\big{(}\hat{h}_{\mathbf{X}}\big{)}\right]}$
$\displaystyle\leq p(\beta)+p(\pi/2-\beta)^{n}$ (19)

Equation (18) is unsurprising, of course, because in Section 4.1 we already
established that for $n\geq d$ the student is able to perfectly mimic the
teacher.

Inequality (19), however, is –to our knowledge– the first quantitative
characterization how well a student can learn via distillation.

Before we provide the proof sketch, we present two instantiations of the bound
for specific classes of tasks that provide insight how fast the right hand
side of (19) actually decreases.

Figure 2: Examples of 2D distributions that fulfill the large-margin condition
(left) and the polynomial condition with different parameters (center, right).

The margin case. The first class of tasks we consider are tasks in which the
classes are separated by an _angular margin_ , illustrated in Figure 2 (left).
These tasks are characterized by a ‘wedge’ of zero probability mass near the
boundary222In bounded domains this condition is, in particular, fulfilled in
the _classical margin_ situation (Schölkopf & Smola, 2002), when the classes
are separated by a positive distance from each other.. For these tasks, we
obtain from Theorem 3 that the expected risk decays exponentially in $n$, up
to $n=d-1$.

######  Corollary 1 (Transfer risk of large-margin distributions).

If there exists $\beta\in[0,\pi/2]$ such that $p(\beta)=0$ and
$\gamma:=p(\pi/2-\beta)<1$, then

$\operatorname*{\mathbb{E}}_{\mathbf{X}\sim
P_{\mathbf{x}}^{n}}{\left[R\big{(}\hat{h}_{\mathbf{X}}\big{)}\right]}\leq\gamma^{n}.$
(20)

The polynomial case. The second class are tasks for which we can upper-bound
$p$ by a $\kappa$-order polynomial. This can be done trivially for any task by
setting $\kappa=0.0$, but that choice would yield a vacuous bound. Higher
values of $\kappa$ correspond to stronger assumptions on the distribution but
enable better rates. Figure 2 (center, right) shows examples of polynomial
distributions for $\kappa\in{\left\\{1.0,2.0\right\\}}$. The special case
$\kappa=1.0$ corresponds to a uniform angle distribution, while distribution
with $\kappa=2.0$ have low probability mass near the decision boundary, while
not necessarily exhibiting a margin.

The following corollary establishes that for tasks with polynomial behavior of
$p(\theta)$, the expected risk decays essentially at a rate of $(\log
n/n)^{\kappa}$ or faster.

######  Corollary 2 (Transfer risk of polynomial distributions).

If there exists a $\kappa\geq 0$ be such that $p(\theta)\leq
c\cdot(1-(2/\pi)\theta)^{\kappa}$ for all $\theta\in[0,\pi/2]$, then

$\operatorname*{\mathbb{E}}_{\mathbf{X}\sim
P_{\mathbf{x}}^{n}}{\left[R\big{(}\hat{h}_{\mathbf{X}})\right]}\leq
c\cdot\frac{1+(\log n)^{\kappa}}{n^{\kappa}}$ (21)

###### Proof.

We apply Theorem 3 and insert the polynomial upper bound for $p$. For the case
$n<d$, we get

$\displaystyle\operatorname*{\mathbb{E}}_{\mathbf{X}\sim
P_{\mathbf{x}}^{n}}{\left[R\big{(}\hat{h}_{\mathbf{X}}\big{)}\right]}$
$\displaystyle\leq(1-(2/\pi)\beta)^{\kappa}+(1-(2/\pi)(\pi/2-\beta))^{n\kappa}.$
(22) Setting $\beta=(\pi/2)\cdot n^{-1/n}$ and simplifying the resulting
expressions yields $\displaystyle\leq\big{(}1-e^{-\frac{\log
n}{n}}\big{)}^{\kappa}+n^{-\kappa}.$ (23)

Finally, we use the inequality $e^{x}\geq 1+x$ and the claim follows. ∎

Note that, in contrast to many results in statistical learning theory, the
bounds are far from vacuous, even when only little data is available. This can
best be seen in Corollary 1, where $\gamma<1$ and hence $\gamma^{n}$ is an
informative upper bound for the classification error. These observations
suggest that distillation operates in a very different regime from classical
hard-target learning. Standard bounds usually have little to say when $n<d$
and only start to be useful when $n\gg d$. In contrast, (linear) distillation
ensures perfect transfer when $n\geq d$ and non-vacuous bounds are possible
even when $n<d$.

###  4.3 Proof of Theorem 3

The case $n\geq d$ follows trivially from the result of Theorem 1 and 2. For
the case $n<d$, the following property turns out to be crucial for obtaining a
transfer rate of the form that we do.

######  Lemma 1 (Strong monotonicity).

Let $\hat{\mathbf{w}}(\mathbf{X})$ denote the distillation solution
$\hat{\mathbf{w}}$ as a function of the training data $\mathbf{X}$. Then, for
any full-rank datasets $\mathbf{X}_{-}\in\mathbb{R}^{d\times n_{-}}$ and
$\mathbf{X}_{+}\in\mathbb{R}^{d\times n_{+}}$ such that $\mathbf{X}_{-}$ is
contained in $\mathbf{X}_{+}$,

$\bar{\alpha}(\mathbf{w}_{*},\hat{\mathbf{w}}(\mathbf{X}_{+}))\leq\bar{\alpha}(\mathbf{w}_{*},\hat{\mathbf{w}}(\mathbf{X}_{-})).$
(24)

###### Proof.

If $n_{+}\geq d$, then the left-hand side of (24) is zero and the claim
follows. Otherwise, assume wlog that the first $n_{-}$ columns of
$\mathbf{X}_{-}$ and $\mathbf{X}_{+}$ coincide. Let
$\mathbf{Q}_{+}\mathbf{R}_{+}=\mathbf{X}_{+}$ be the QR factorisation of
$\mathbf{X}_{+}$ with $\mathbf{Q}_{+}\in\mathbb{R}^{d\times n_{+}}$ and
$\mathbf{R}_{+}\in\mathbb{R}^{n_{+}\times n_{+}}$, and similarly for
$\mathbf{X}_{-}$. Then
$\hat{\mathbf{w}}(\mathbf{X}_{+})=\mathbf{Q}_{+}\mathbf{Q}_{+}^{\intercal}\mathbf{w}_{*}$
and

$\displaystyle\cos(\bar{\alpha}(\mathbf{w}_{*},\hat{\mathbf{w}}(\mathbf{X}_{+})))$
$\displaystyle=\frac{\mathbf{w}_{*}^{\intercal}\mathbf{Q}_{+}\mathbf{Q}_{+}^{\intercal}\mathbf{w}_{*}}{{\left\|\mathbf{w}_{*}\right\|}\cdot{\left\|\mathbf{Q}_{+}\mathbf{Q}_{+}^{\intercal}\mathbf{w}_{*}\right\|}}$
(25)
$\displaystyle=\frac{{\left\|\mathbf{Q}_{+}^{\intercal}\mathbf{w}_{*}\right\|}}{{\left\|\mathbf{w}_{*}\right\|}},$
(26)

and an analogous statement holds for $\mathbf{X}_{-}$. Now, because the first
$n_{-}$ columns of $\mathbf{Q}_{+}$ coincide with $\mathbf{Q}_{-}$, we have
${\left\|\mathbf{Q}_{+}^{\intercal}\mathbf{w}_{*}\right\|}\geq{\left\|\mathbf{Q}_{-}^{\intercal}\mathbf{w}_{*}\right\|}$
and

$\cos(\bar{\alpha}(\mathbf{w}_{*},\hat{\mathbf{w}}(\mathbf{X}_{+})))\geq\cos(\bar{\alpha}(\mathbf{w}_{*},\hat{\mathbf{w}}(\mathbf{X}_{-}))).$
(27)

Taking $\cos^{-1}$ on both sides (and remembering that $\cos^{-1}$ is
decreasing) yields the claim. ∎

For the moment, think of $\bar{\alpha}(\mathbf{w}_{*},\hat{\mathbf{w}})$ as a
proxy for the transfer risk, i.e. the closer the trained student
$\hat{\mathbf{w}}$ is to the teacher $\mathbf{w}_{*}$ in terms of angles, the
lower the transfer risk. A direct consequence of Lemma 1, and the reason we
call it ‘strong mononoticity’, is that including additional data in the
transfer set can never harm the transfer risk, only improve it. This property
is specific to distillation; it does not hold in hard-target learning.

###### Proof of Theorem 3 $(n<d)$.

For nonzero vectors $\mathbf{u},\mathbf{v}\in\mathbb{R}^{d}$, we define
$\alpha(\mathbf{u},\mathbf{v})\in[0,\pi]$ as a variant of $\bar{\alpha}$
(Equation 16) that takes the sign of $\mathbf{u}^{\intercal}\mathbf{v}$ into
account,

$\alpha(\mathbf{u},\mathbf{v})=\cos^{-1}{\left(\frac{{\mathbf{u}^{\intercal}\mathbf{v}}}{{\left\|\mathbf{u}\right\|}\cdot{\left\|\mathbf{v}\right\|}}\right)}.$
(28)

We decompose the expected risk as follows:

$\displaystyle\begin{split}\operatorname*{\mathbb{E}}_{\mathbf{X}\sim
P_{\mathbf{x}}^{n}}&{\left[R\big{(}\hat{h}_{\mathbf{X}}\big{)}\right]}=\operatorname*{\mathbb{P}}_{\begin{subarray}{c}\mathbf{X}\sim
P_{\mathbf{x}}^{n}\\\ \mathbf{x}\sim
P_{\mathbf{x}}\end{subarray}}[\mathbf{w}_{*}^{\intercal}\mathbf{x}\cdot\hat{\mathbf{w}}^{\intercal}\mathbf{x}<0]\\\
&=\int_{\mathbf{x}:\bar{\alpha}(\mathbf{w}_{*},\mathbf{x})\geq\beta}\operatorname*{\mathbb{P}}_{\mathbf{X}\sim
P_{\mathbf{x}}^{n}}[\mathbf{w}_{*}^{\intercal}\mathbf{x}\cdot\hat{\mathbf{w}}^{\intercal}\mathbf{x}<0|\mathbf{x}]\,\mathrm{d}P_{\mathbf{x}}\\\
&+\int_{\mathbf{x}:\bar{\alpha}(\mathbf{w}_{*},\mathbf{x})<\beta,\,\mathbf{w}_{*}^{\intercal}\mathbf{x}>0}\operatorname*{\mathbb{P}}_{\mathbf{X}\sim
P_{\mathbf{x}}^{n}}[\hat{\mathbf{w}}^{\intercal}\mathbf{x}<0|\mathbf{x}]\,\mathrm{d}P_{\mathbf{x}}\\\
&+\int_{\mathbf{x}:\bar{\alpha}(\mathbf{w}_{*},\mathbf{x})<\beta,\,\mathbf{w}_{*}^{\intercal}\mathbf{x}<0}\operatorname*{\mathbb{P}}_{\mathbf{X}\sim
P_{\mathbf{x}}^{n}}[\hat{\mathbf{w}}^{\intercal}\mathbf{x}>0|\mathbf{x}]\,\mathrm{d}P_{\mathbf{x}}.\end{split}$
(29)

Let us fix some $\mathbf{x}$ for which
$\bar{\alpha}(\mathbf{w}_{*},\mathbf{x})<\beta$ and
$\mathbf{w}_{*}^{\intercal}\mathbf{x}>0$ (i.e. an ‘easy’ positive test
example); for this $\mathbf{x}$ we have
$\alpha(\mathbf{w}_{*},\mathbf{x})=\bar{\alpha}(\mathbf{w}_{*},\mathbf{x})$.
Consider the situation where
$\bar{\alpha}(\mathbf{w}_{*},\mathbf{x}_{i})<\pi/2-\beta$ for some $i$ (i.e.
there is at least one good teaching point). Then, Lemma 1 with
$\mathbf{X}_{+}=\mathbf{X}$ and $\mathbf{X}_{-}=\mathbf{x}_{i}$ yields
$\bar{\alpha}(\mathbf{w}_{*},\hat{\mathbf{w}})\leq\bar{\alpha}(\mathbf{w}_{*},\mathbf{x}_{i})<\pi/2-\beta$.
Combined with the triangle inequality, we obtain

$\displaystyle\alpha(\hat{\mathbf{w}},\mathbf{x})$
$\displaystyle\leq\alpha(\mathbf{w}_{*},\hat{\mathbf{w}})+\alpha(\mathbf{w}_{*},\mathbf{x})$
(30)
$\displaystyle\leq\bar{\alpha}(\mathbf{w}_{*},\mathbf{x}_{i})+\bar{\alpha}(\mathbf{w}_{*},\mathbf{x})<\pi/2,$
(31)

which implies $\hat{\mathbf{w}}^{\intercal}\mathbf{x}>0$, i.e. a correct
prediction (same as the teacher’s). Conversely, an error can occur only if
$\bar{\alpha}(\mathbf{w}_{*},\mathbf{x}_{i})\geq\pi/2-\beta$ for all $i$.
Because $\mathbf{x}_{i}$ are independent, we have

$\displaystyle\begin{split}\operatorname*{\mathbb{P}}_{\mathbf{X}\sim
P_{\mathbf{x}}^{n}}[\hat{\mathbf{w}}^{\intercal}\mathbf{x}<&\,0|\,\mathbf{x}:\bar{\alpha}(\mathbf{w}_{*},\mathbf{x})<\beta,\,\mathbf{w}_{*}^{\intercal}\mathbf{x}>0]\\\
&\leq\operatorname*{\mathbb{P}}_{\mathbf{X}\sim
P_{\mathbf{x}}^{n}}[\forall_{i}:\bar{\alpha}(\mathbf{w}_{*},\mathbf{x}_{i})\geq\pi/2-\beta]\\\
&=p(\pi/2-\beta)^{n}.\end{split}$ (32)

By a symmetric argument, one can show that

$\operatorname*{\mathbb{P}}_{\mathbf{X}\sim
P_{\mathbf{x}}^{n}}[\hat{\mathbf{w}}^{\intercal}\mathbf{x}>0|\,\mathbf{x}:\bar{\alpha}(\mathbf{w}_{*},\mathbf{x})<\beta,\,\mathbf{w}_{*}^{\intercal}\mathbf{x}<0]\\\
\leq p(\pi/2-\beta)^{n}.$ (33)

Combining (29), (32) and (33) yields the result:

$\displaystyle\operatorname*{\mathbb{P}}_{\begin{subarray}{c}\mathbf{X}\sim
P_{\mathbf{x}}^{n}\\\ \mathbf{x}\sim P_{\mathbf{x}}\end{subarray}}$
$\displaystyle[\mathbf{w}_{*}^{\intercal}\mathbf{x}\cdot\hat{\mathbf{w}}^{\intercal}\mathbf{x}<0]\leq$
$\displaystyle\leq$
$\displaystyle\,\operatorname*{\mathbb{P}}_{\mathbf{x}}[\bar{\alpha}(\mathbf{w}_{*},\mathbf{x})\geq\beta]+\operatorname*{\mathbb{P}}_{\mathbf{x}}[\bar{\alpha}(\mathbf{w}_{*},\mathbf{x})<\beta]\cdot
p(\pi/2-\beta)^{n}$ $\displaystyle=$
$\displaystyle\,p(\beta)+(1-p(\beta))\cdot p(\pi/2-\beta)^{n}.$

∎

##  5 Why Does Distillation Work?

From the formal analysis in the previous section, three concepts emerge as key
factors for the success of distillation: _data geometry, optimization bias,
and strong monotonicity_. In this section, we discuss these factors and
provide some empirical confirmation how they affect or explain variations in
the transfer risk.

###  5.1 Data Geometry

From Theorem 3 we know that the data geometry, in particular the _angular
alignment_ between the data distribution and the teacher, crucially impact how
fast the student can learn. Formally, this is reflected in $p(\theta)$: the
faster it decreases, the easier it should be for the student to learn the
task.

To experimentally test the effect of data geometry on the effectiveness of
distillation, we adopt the setting of Corollary 2. We consider a series of
tasks of varying angular alignment, as measured by the degree, $\kappa$, of
the polynomial by which $p(\theta)$ is upper bounded.

Specifically, for any $\kappa$, the task
$(P_{\mathbf{x}}^{\kappa},\mathbf{w}_{*}^{\kappa})$ is defined by the
following sampling procedure. First, an angle $a$ is sampled from the
$\kappa$-polynomial distribution, i.e.
$\operatorname*{\mathbb{P}}{\left[a\geq\theta\right]}=(1-(2/\pi)\theta)^{\kappa}$
for $\theta\in[0,\pi/2]$. Then, a direction $\mathbf{z}$ is uniformly sampled
from all unit-length vectors that are at angle $a$ with the teacher’s weight
vector, $\bar{\alpha}(\mathbf{w}_{*},\mathbf{z})=a$. Finally,
$\mathbf{x}=\nu\mathbf{z}$ is returned for a random $\nu$, distributed as a
one-dimensional standard Gaussian.

We use an input space dimension of $d=1000$ and a transfer set size $n=20$.
Then, we train a linear student by distillation on each of the tasks and
evaluate its transfer risk on held-out data. Figure 3 shows the results. The
plot shows a clearly decreasing trend: on tasks with more favorable data
geometry (higher $\kappa$), transfer via distillation is more effective and
the student achieves lower risk.

Figure 3:  Transfer risk of linear distillation on tasks of varying angular
alignment.

###  5.2 Optimization Bias

A second key factor for the success of distillation is a specific optimization
bias. For $n<d$, the distillation training objective (1) has many minima of
identical function value but potentially different generalization properties.
Therefore, the optimization method used could have a large impact on the
transfer risk. As Theorems 1 and 2 show, gradient descent has a particularly
favorable bias for distillation.

To verify this observation experimentally, we consider learners that are
guided by an optimisation bias to different degrees: at one end of the
spectrum is the gradient-descent learner we have studied in previous sections,
while at the other end is a learner that treats all minimizers of the
distillation training loss equally, i.e. that has no bias toward any of the
solutions. Specifically, consider learners with weights of the form
$\mathbf{w}_{\delta}=\hat{\mathbf{w}}+\delta\frac{{\left\|\hat{\mathbf{w}}\right\|}}{{\left\|\mathbf{q}\right\|}}\mathbf{q}$,
where $\hat{\mathbf{w}}$ is the gradient-descent distillation solution and
$\mathbf{q}$ is a Gaussian random vector in the subspace orthogonal to the
data span, i.e. if $\mathbf{X}$ is the data matrix, then
$\mathbf{X}^{\intercal}\mathbf{q}=\mathbf{0}$. All learners of this form
globally minimize the distillation training loss, and depending on $\delta$,
they are more or less guided by the gradient-descent bias: $\delta=0$ and
${\left|\delta\right|}\to\infty$ represent the two extremes mentioned above.

We train the learners $\mathbf{w}_{\delta}$ for
$\delta\in{\left\\{0,10,\dots,90\right\\}}$ on the digits $0$ and $1$ of the
MNIST dataset, where inputs are treated as vectors in $\mathbb{R}^{784}$ and
the teacher $\mathbf{w}_{*}$ is a logistic regression trained to classify 0s
and 1s on an independent training set. We set the transfer set size to $n=100$
and evaluate the risk on the test set.

Figure 4 shows the result. There is a clear trend in favor of learners that
are more strongly guided by the gradient-descent bias (small $\delta$); these
learners generally achieve lower transfer risk. This result supports the idea
of optimization bias as a key component of distillation’s success.

Figure 4:  Transfer risk of linear distillation variants with different
degrees of optimization bias, on the digits $0$ and $1$ of MNIST.

###  5.3 Strong Monotonicity

The third key factor we identify is _strong monotonicity_ , as established in
Lemma 1: training the student on more data always leads to a better
approximation of the teacher’s weight vector.

Compared to data geometry and optimisation bias, strong monotonicity is less
amenable to experimental study because it is a downstream property that cannot
directly be manipulated. We therefore take an indirect approach. We consider a
set of learners including the gradient-descent distillation learner, the hard-
target learner, and several learners with reduced optimisation bias (as in
Section 5.2), and train them on the same task. For each learner, we note its
expected risk calculated on a held-out set, and its _monotonicity index_ ,
defined as the probability that an additional training example reduces the
angle between the student’s and the teacher’s weight vectors rather than
increasing it, i.e.

$m(\mathbf{w})=\operatorname*{\mathbb{P}}_{\begin{subarray}{c}\mathbf{X}\sim
P_{\mathbf{x}}^{n}\\\ \mathbf{x}\sim
P_{\mathbf{x}}\end{subarray}}{\left[\bar{\alpha}(\mathbf{w}_{*},\mathbf{w}([\mathbf{X},\mathbf{x}]))<\bar{\alpha}(\mathbf{w}_{*},\mathbf{w}(\mathbf{X}))\right]},$
(34)

where the student’s weight vector $\mathbf{w}$ is now treated as a function of
the training set. Thus, we can relate a learner’s risk and its monotonicity.

We train the learners on the polynomial-angle task
$(P_{\mathbf{x}}^{\kappa},\mathbf{w}_{*}^{\kappa})$ from Section 5.1, with
$\kappa=1,d=100$ and $n=5$. The expected risk as well as the monotonicity
index are estimated as averages over 1000 transfer sets.

The results are shown in Figure 5. There is a negative correlation between
monotonicity and transfer risk, which supports the intuition of monotonicity
as a desirable property and a possible explanation of distillation’s success.

However, a few reservations are in order. First, as mentioned above,
monotonicity cannot easily be manipulated, so its _effect_ on transfer risk
remains unknown. We can only measure correlation. Second, monotonicity is of
binary nature; it only captures _whether_ an extra data point helps or not.
Yet for a quantitative characterization of risk, one would have to capture _by
how much_ an extra data point helps. We leave more refined definitions of
monotonicity for future work.

Figure 5:  Expected transfer risk vs. monotonicity of different learners:
gradient-descent based distillation (blue), hard-target learner (orange), and
a series of distillation learners with reduced optimisation bias (green):
$\mathbf{w}_{\delta}$ for $\delta\in{\left\\{1/16,1/8,1/4,1/2,1\right\\}}$,
listed in order from left to right.

##  6 Conclusion

In this work, we have formulated and studied a linear model of knowledge
distillation. Within this model, we have derived a)  _a characterization of
the solution learned by the student_ , b)  _a bound on the transfer risk,
meaningful even in the low-data regime_ , and c)  _three key factors that
explain the success of distillation_. In doing so, we hope to have enriched
both the current intuitive and theoretical understanding of distillation, both
of which have only been weakly developed.

Our work paints a picture of distillation as an extremely effective method for
knowledge transfer that derives its power from an optimization bias of
gradient-based methods initialized near the origin, which in particular has
the effect that any additionally included training point can only improve the
student’s approximation of the teacher. Distillation further benefits strongly
from a favorable data geometry, in particular a margin between classes.

While we have supported this picture by theory and empirical work only in the
linear case, we hypothesize that similar properties also govern the behavior
of distillation in the nonlinear setting. If this hypothesis turns out to be
true, it would have implications for the design of transfer sets (a large
teacher model being stored along with only the minimal dataset necessary for
future transfer) or active learning (which samples are most informative to
have labeled by the teacher). Potentially, strong monotonicity could serve as
a leading design principle for new sample-efficient algorithms. We thus
consider the extension to nonlinear models the main direction for future work.

## References

  * Arora et al. (2018) Arora, S., Cohen, N., and Hazan, E.  On the optimization of deep networks: Implicit acceleration by overparameterization.  In _International Conference on Machine Learing (ICML)_ , 2018.
  * Arora et al. (2019) Arora, S., Cohen, N., Golowich, N., and Hu, W.  A convergence analysis of gradient descent for deep linear neural networks.  In _International Conference on Learning Representations (ICLR)_ , 2019.
  * Ba & Caruana (2014) Ba, J. and Caruana, R.  Do deep nets really need to be deep?  In _Conference on Neural Information Processing Systems (NIPS)_ , 2014\.
  * Bucilua et al. (2006) Bucilua, C., Caruana, R., and Niculescu-Mizil, A.  Model compression.  In _Conference on Knowledge Discovery and Data Mining (KDD)_ , 2006\.
  * Celik et al. (2017) Celik, Z. B., Lopez-Paz, D., and McDaniel, P.  Patient-driven privacy control through generalized distillation.  In _IEEE Symposium on Privacy-Aware Computing (PAC)_ , 2017.
  * Craven & Shavlik (1996) Craven, M. and Shavlik, J. W.  Extracting tree-structured representations of trained networks.  In _Conference on Neural Information Processing Systems (NIPS)_ , 1996\.
  * Geras et al. (2016) Geras, K. J., Mohamed, A.-R., Caruana, R., Urban, G., Wang, S., Aslan, O., Philipose, M., Richardson, M., and Sutton, C.  Blending LSTMs into CNNs.  In _International Conference on Learning Representations (ICLR) Workshop_ , 2016.
  * Hardt & Ma (2017) Hardt, M. and Ma, T.  Identity matters in deep learning.  In _International Conference on Learning Representations (ICLR)_ , 2017.
  * Hinton et al. (2014) Hinton, G., Vinyals, O., and Dean, J.  Distilling the knowledge in a neural network.  In _Deep Learning Workshop at NIPS_ , 2014.
  * Howard et al. (2017) Howard, A. G., Zhu, M., Chen, B., Kalenichenko, D., Wang, W., Weyand, T., Andreetto, M., and Adam, H.  MobileNets: Efficient convolutional neural networks for mobile vision applications.  In _arXiv:1704.04861_ , 2017.
  * Hu et al. (2016) Hu, Z., Ma, X., Liu, Z., Hovy, E., and Xing, E.  Harnessing deep neural networks with logic rules.  In _Annual Meeting of the Association for Computational Linguistics (ACL)_ , 2016.
  * Kawaguchi (2016) Kawaguchi, K.  Deep learning without poor local minima.  In _Conference on Neural Information Processing Systems (NIPS)_ , 2016\.
  * Li et al. (2014) Li, J., Zhao, R., Huang, J.-T., and Gong, Y.  Learning small-size DNN with output-distribution-based criteria.  In _Conference of the International Speech Communication Association (Interspeech)_ , 2014.
  * Li et al. (2017) Li, Y., Yang, J., Song, Y., Cao, L., Luo, J., and Li, L.-J.  Learning from noisy labels with distillation.  In _International Conference on Computer Vision (ICCV)_ , 2017.
  * Liang et al. (2008) Liang, P., Daumé III, H., and Klein, D.  Structure compilation: trading structure for features.  In _International Conference on Machine Learing (ICML)_ , 2008.
  * Liu & Zhu (2016) Liu, J. and Zhu, X.  The teaching dimension of linear learners.  _Journal of Machine Learning Research (JMLR)_ , 17(1):5631–5655, 2016.
  * Lopez-Paz et al. (2016) Lopez-Paz, D., Bottou, L., Schölkopf, B., and Vapnik, V.  Unifying distillation and privileged information.  In _International Conference on Learning Representations (ICLR)_ , 2016.
  * Papernot et al. (2016) Papernot, N., McDaniel, P., Wu, X., Jha, S., and Swami, A.  Distillation as a defense to adversarial perturbations against deep neural networks.  In _IEEE Symposium on Security and Privacy (S &P)_, 2016.
  * Polino et al. (2018) Polino, A., Pascanu, R., and Alistarh, D.  Model compression via distillation and quantization.  In _International Conference on Learning Representations (ICLR)_ , 2018.
  * Romero et al. (2015) Romero, A., Ballas, N., Kahou, S. E., Chassang, A., Gatta, C., and Bengio, Y.  Fitnets: Hints for thin deep nets.  In _International Conference on Learning Representations (ICLR)_ , 2015.
  * Rusu et al. (2016) Rusu, A. A., Colmenarejo, S. G., Gulcehre, C., Desjardins, G., Kirkpatrick, J., Pascanu, R., Mnih, V., Kavukcuoglu, K., and Hadsell, R.  Policy distillation.  In _International Conference on Learning Representations (ICLR)_ , 2016.
  * Saxe et al. (2014) Saxe, A. M., McClelland, J. L., and Ganguli, S.  Exact solutions to the nonlinear dynamics of learning in deep linear neural networks.  In _International Conference on Learning Representations (ICLR)_ , 2014.
  * Schölkopf & Smola (2002) Schölkopf, B. and Smola, A. J.  _Learning With Kernels_.  MIT Press, 2002.
  * Tang et al. (2016) Tang, Z., Wang, D., and Zhang, Z.  Recurrent neural network training with dark knowledge transfer.  In _IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2016.
  * Urner et al. (2011) Urner, R., Shalev-Shwartz, S., and Ben-David, S.  Access to unlabeled data can speed up prediction time.  In _International Conference on Machine Learing (ICML)_ , 2011.
  * Vapnik & Izmailov (2015) Vapnik, V. and Izmailov, R.  Learning using privileged information: similarity control and knowledge transfer.  _Journal of Machine Learning Research (JMLR)_ , 16(2):2023–2049, 2015.
  * Yu et al. (2017) Yu, R., Li, A., Morariu, V. I., and Davis, L. S.  Visual relationship detection with internal and external linguistic knowledge distillation.  In _International Conference on Computer Vision (ICCV)_ , 2017.
  * Zhu (2013) Zhu, J.  Machine teaching for Bayesian learners in the exponential family.  In _Conference on Neural Information Processing Systems (NIPS)_ , 2013\.
  * Zhu (2015) Zhu, X.  Machine teaching: An inverse problem to machine learning and an approach toward optimal education.  In _AAAI Conference on Artificial Intelligence_ , 2015.

We define here some notation in addition to that of Section 3 in the main
text. We denote by $\ell_{i}$ the per-instance loss,

$\displaystyle L^{1}(\mathbf{w})$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\ell_{i}(\mathbf{w}^{\intercal}\mathbf{x}_{i}),$
(35) $\displaystyle\ell_{i}(u)$
$\displaystyle=-y_{i}\log\sigma(u)-(1-y_{i})\log(1-\sigma(u))-\ell_{i}^{*},$
(36)

where $\ell_{i}^{*}$ are constants chosen such that the minimum of $\ell_{i}$
is 0, namely $\ell_{i}^{*}=-y_{i}\log y_{i}-(1-y_{i})\log(1-y_{i})$.

Slightly abusing notation, we write
$L(\tau)=L^{1}(\mathbf{w}(\tau))=L(\mathbf{W}_{1}(\tau),\dots,\mathbf{W}_{N}(\tau))$
for the objective value at time $\tau$.

Finally, for a full-rank matrix $\mathbf{A}\in\mathbb{R}^{d\times m}\ (m\geq
1)$, we denote by $\mathbf{P}_{\mathbf{A}}\in\mathbb{R}^{d\times d}$ the
matrix of projection onto the span of $\mathbf{A}$,

$\mathbf{P}_{\mathbf{A}}=\left\\{\begin{array}[]{cl}\mathbf{I},&m\geq d,\\\
\mathbf{A}(\mathbf{A}^{\intercal}\mathbf{A})^{-1}\mathbf{A}^{\intercal},&m<d.\end{array}\right.$
(37)

##  Appendix A Properties of the Cross-Entropy Loss

######  Theorem A.1 (Gradient).

The gradient of the cross-entropy loss (35) takes the form

$\nabla
L^{1}(\mathbf{w})=\frac{1}{n}\sum_{i=1}^{n}(\sigma(\mathbf{w}^{\intercal}\mathbf{x}_{i})-y_{i})\cdot\mathbf{x}_{i}.$
(38)

It always lies in the data span, $\nabla
L^{1}(\mathbf{w})\in\mathrm{span}(\mathbf{X})$.

###### Proof.

Straightforward calculation. ∎

######  Theorem A.2 (Global minima).

The global minimum of the cross-entropy loss (35) is 0 and the set of global
minimisers is

${\left\\{\mathbf{w}\in\mathbb{R}^{d}:\mathbf{X}^{\intercal}\mathbf{w}=\mathbf{X}^{\intercal}\mathbf{w}_{*}\right\\}}.$
(39)

###### Proof.

We know that $L^{1}\geq 0$ and $L^{1}(\mathbf{w}_{*})=0$, so 0 is the optimal
objective value, and the set of global optima consists of all $\mathbf{w}$
such that $L^{1}(\mathbf{w})=0$. The last condition is equivalent to
$\forall_{i}:\ell_{i}(\mathbf{w})=0$, which in turn is equivalent to
$\forall_{i}:\sigma(\mathbf{w}^{\intercal}\mathbf{x}_{i})=\sigma(\mathbf{w}_{*}^{\intercal}\mathbf{x}_{i})$.
By monotonicity of $\sigma$, this is further equivalent to
$\forall_{i}:\mathbf{w}^{\intercal}\mathbf{x}_{i}=\mathbf{w}_{*}^{\intercal}\mathbf{x}_{i}$,
which is a restatement of (39). ∎

######  Theorem A.3 (Restricted strong convexity).

Assume $\mathbf{X}$ is full-rank. For any sublevel set
$\mathcal{W}={\left\\{\mathbf{w}:L^{1}(\mathbf{w})\leq l\right\\}}$, there
exists $\mu>0$ such that

$L^{1}(\mathbf{v})\geq L^{1}(\mathbf{w})+\nabla
L^{1}(\mathbf{w})^{\intercal}(\mathbf{v}-\mathbf{w})+\frac{\mu}{2}{\left\|\mathbf{v}-\mathbf{w}\right\|}^{2}$
(40)

for all $\mathbf{w},\mathbf{v}\in\mathcal{W}$ such that
$\mathbf{v}-\mathbf{w}\in\mathrm{span}(\mathbf{X})$.

###### Proof.

Consider the 2nd-order Taylor expansion of $L^{1}$ around $\mathbf{w}$,

$L^{1}(\mathbf{v})=L^{1}(\mathbf{w})+\nabla
L^{1}(\mathbf{w})^{\intercal}(\mathbf{v}-\mathbf{w})\\\
+\frac{1}{2}(\mathbf{v}-\mathbf{w})^{\intercal}[\nabla^{2}L^{1}(\bar{\mathbf{w}})](\mathbf{v}-\mathbf{w}),$
(41)

where $\nabla^{2}L^{1}(\bar{\mathbf{w}})$ is the Hessian of $L^{1}$ evaluated
at $\bar{\mathbf{w}}$, a point lying between $\mathbf{v}$ and $\mathbf{w}$. A
straightforward calculation shows that the Hessian takes the form

$\nabla^{2}L^{1}(\bar{\mathbf{w}})=\mathbf{X}\mathbf{D}_{\bar{\mathbf{w}}}\mathbf{X}^{\intercal},$
(42)

where

$\mathbf{D}_{\bar{\mathbf{w}}}=\mathrm{diag}[\sigma(\bar{\mathbf{w}}^{\intercal}\mathbf{x}_{1})(1-\sigma(\bar{\mathbf{w}}^{\intercal}\mathbf{x}_{1})),\\\
\dots,\sigma(\bar{\mathbf{w}}^{\intercal}\mathbf{x}_{n})(1-\sigma(\bar{\mathbf{w}}^{\intercal}\mathbf{x}_{n}))].$
(43)

We will now show that there is a constant $\omega>0$ such that

$\sigma(\bar{\mathbf{w}}^{\intercal}\mathbf{x}_{i})(1-\sigma(\bar{\mathbf{w}}^{\intercal}\mathbf{x}_{i}))\geq\omega$
(44)

for all $\bar{\mathbf{w}}\in\mathcal{W}$ and
$i\in{\left\\{1,\dots,n\right\\}}$, so that we can claim
$\mathbf{D}_{\bar{\mathbf{w}}}\succeq\omega\mathbf{I}$, or consequently
$\nabla^{2}L^{1}(\bar{\mathbf{w}})\succeq\omega\mathbf{X}\mathbf{X}^{\intercal}$.

Let $\mathbf{w}\in\mathcal{W}$. The bound on $L^{1}(\mathbf{w})$ implies a
bound on $\ell_{i}(\mathbf{w}^{\intercal}\mathbf{x}_{i})$ for all $i$,

$\ell_{i}(\mathbf{w}^{\intercal}\mathbf{x}_{i})\leq nL^{1}(\mathbf{w})\leq
nl.$ (45)

Because $\ell_{i}$ is convex and $\ell_{i}(u)\to\infty$ as $u\to\pm\infty$, we
know that $\ell_{i}^{-1}((-\infty,nl])$ is a bounded interval, and the finite
union $\cup_{i=1}^{n}\ell_{i}^{-1}((-\infty,nl])$ is also a bounded interval,
whose size depends only on $nl$ and the data. Hence, there exists $K>0$ such
that $\mathbf{w}^{\intercal}\mathbf{x}_{i}\in[-K,K]$ for all
$\mathbf{w}\in\mathcal{W}$ and $i\in{\left\\{1,\dots,n\right\\}}$. The
existence of $\omega>0$ satisfying (44) follows.

Now, let us apply
$\nabla^{2}L^{1}(\mathbf{w})\succeq\omega\mathbf{X}\mathbf{X}^{\intercal}$ to
lower-bound (41):

$L^{1}(\mathbf{v})\geq L^{1}(\mathbf{w})+\nabla
L^{1}(\mathbf{w})^{\intercal}(\mathbf{v}-\mathbf{w})\\\
+\frac{\omega}{2}(\mathbf{v}-\mathbf{w})^{\intercal}\mathbf{X}\mathbf{X}^{\intercal}(\mathbf{v}-\mathbf{w}).$
(46)

Consider two cases. If $n\geq d$, $\mathbf{X}\mathbf{X}^{\intercal}$ is full-
rank and
$\mathbf{X}\mathbf{X}^{\intercal}\succeq\lambda_{\mathrm{min}}\mathbf{I}$
holds, where $\lambda_{\mathrm{min}}>0$ is the smallest eigenvalue of
$\mathbf{X}\mathbf{X}^{\intercal}$. Combined with (46), this proves the claim
for $n\geq d$ and $\mu=\omega\lambda_{\mathrm{min}}$.

If $n<d$, $\mathbf{X}^{\intercal}\mathbf{X}$ is full rank. We can use the
assumption $\mathbf{v}-\mathbf{w}\in\mathrm{span}(\mathbf{X})$ to deduce

$\displaystyle\begin{split}{\left\|\mathbf{v}-\mathbf{w}\right\|}^{2}&={\left\|\mathbf{P}_{\mathbf{X}}(\mathbf{v}-\mathbf{w})\right\|}^{2}\\\
&=(\mathbf{v}-\mathbf{w})^{\intercal}\mathbf{X}(\mathbf{X}^{\intercal}\mathbf{X})^{-1}\mathbf{X}^{\intercal}(\mathbf{v}-\mathbf{w})\\\
&\leq\lambda_{\mathrm{max}}(\mathbf{v}-\mathbf{w})^{\intercal}\mathbf{X}\mathbf{X}^{\intercal}(\mathbf{v}-\mathbf{w}),\end{split}$
(47)

where $\lambda_{\mathrm{max}}>0$ is the largest eigenvalue of
$(\mathbf{X}^{\intercal}\mathbf{X})^{-1}$. Combined with (46), this proves the
claim for $n<d$ and $\mu=\omega/\lambda_{\mathrm{max}}$. ∎

######  Corollary A.1 (Restricted Polyak-Lojasiewicz).

Assume $\mathbf{X}$ is full-rank. For any sublevel set
$\mathcal{W}={\left\\{\mathbf{w}:L^{1}(\mathbf{w})\leq l\right\\}}$, there
exists $c>0$ such that

$cL^{1}(\mathbf{w})\leq\frac{1}{2}{\left\|\nabla
L^{1}(\mathbf{w})\right\|}^{2}$ (48)

for all $\mathbf{w}\in\mathcal{W}$.

###### Proof.

Let $\mathbf{w}\in\mathcal{W}$. (If $\mathcal{W}$ is empty, the claim is
trivially true.) Theorem A.3 applied to $\mathcal{W}$ implies that for some
$\mu>0$,

$L^{1}(\mathbf{v})\geq L^{1}(\mathbf{w})+\nabla
L^{1}(\mathbf{w})^{\intercal}(\mathbf{v}-\mathbf{w})+\frac{\mu}{2}{\left\|\mathbf{v}-\mathbf{w}\right\|}^{2}$
(49)

for all $\mathbf{v}\in\mathcal{W}\cap\mathcal{V}$ where
$\mathcal{V}={\left\\{\mathbf{v}:\mathbf{v}-\mathbf{w}\in\mathrm{span}(\mathbf{X})\right\\}}$.
Taking $\min_{\mathbf{v}\in\mathcal{W}\cap\mathcal{V}}$ on both sides, then
relaxing part of the constraint on the right-hand side yields

$\displaystyle\begin{split}&\min_{\mathbf{v}\in\mathcal{W}\cap\mathcal{V}}L^{1}(\mathbf{v})\\\
&\hskip
14.22636pt\geq\min_{\mathbf{v}\in\mathcal{W}\cap\mathcal{V}}L^{1}(\mathbf{w})+\nabla
L^{1}(\mathbf{w})^{\intercal}(\mathbf{v}-\mathbf{w})+\frac{\mu}{2}{\left\|\mathbf{v}-\mathbf{w}\right\|}^{2}\\\
&\hskip 14.22636pt\geq\min_{\mathbf{v}\in\mathcal{V}}L^{1}(\mathbf{w})+\nabla
L^{1}(\mathbf{w})^{\intercal}(\mathbf{v}-\mathbf{w})+\frac{\mu}{2}{\left\|\mathbf{v}-\mathbf{w}\right\|}^{2}.\end{split}$
(50)

Now, the minimum on the left-hand side is equal to 0 and is attained at
$\mathbf{v}=\mathbf{w}+\mathbf{P}_{\mathbf{X}}(\mathbf{w}_{*}-\mathbf{w})$, as
can be seen from Theorem A.2. For the right-hand side, we can substitute
$\mathbf{v}=\mathbf{w}+\mathbf{X}\mathbf{a}$ for $\mathbf{a}\in\mathbb{R}^{n}$
and find the unconstrained minimum with respect to $\mathbf{a}$. We get

$\displaystyle\begin{split}0&\geq L^{1}(\mathbf{w})-\frac{1}{2\mu}\nabla
L^{1}(\mathbf{w})^{\intercal}\mathbf{X}(\mathbf{X}^{\intercal}\mathbf{X})^{-1}\mathbf{X}^{\intercal}\nabla
L^{1}(\mathbf{w})\\\ &\geq
L^{1}(\mathbf{w})-\frac{\lambda_{\mathrm{max}}}{2\mu}{\left\|\nabla
L^{1}(\mathbf{w})\right\|}^{2},\end{split}$ (51)

where $\lambda_{\mathrm{max}}>0$ is the largest eigenvalue of
$\mathbf{X}(\mathbf{X}^{\intercal}\mathbf{X})^{-1}\mathbf{X}^{\intercal}$.
This yields the result with $c=\mu/\lambda_{\mathrm{max}}$. ∎

##  Appendix B Proof of Theorem 1

We will prove a supporting lemma, and then the theorem.

######  Lemma B.1.

Assume the student is a directly parameterised linear classifier $(N=1)$
initialised at zero, $\mathbf{w}(0)=\mathbf{0}$. Then,
$\mathbf{w}(\tau)\in\mathrm{span}(\mathbf{X})$ for $\tau\in[0,\infty)$.

###### Proof.

Let $\mathbf{q}\in\mathbb{R}^{d}$ be any vector orthogonal to the span of
$\mathbf{X}$. It suffices to show that
$\mathbf{q}^{\intercal}\mathbf{w}(\tau)=0$. For that, notice that
$\mathbf{q}^{\intercal}\mathbf{w}(0)=0$ and

${\frac{\mathrm{d}}{\mathrm{d}\tau}}(\mathbf{q}^{\intercal}\mathbf{w}(\tau))=-\mathbf{q}^{\intercal}\nabla
L^{1}(\mathbf{w}(\tau))=0,$ (52)

where the last equality follows from the fact that $\nabla
L^{1}(\mathbf{w}(\tau))\in\mathrm{span}(\mathbf{X})$ (Theorem A.1). The claim
follows. ∎

See 1

###### Proof.

Recall the time-derivative of $L$,

$L^{\prime}(\tau)=-{\left\|\nabla L^{1}(\mathbf{w}(\tau))\right\|}^{2}.$ (53)

The data matrix $\mathbf{X}$ is almost surely (wrt. $\mathbf{X}\sim
P_{\mathbf{x}}^{n}$) full-rank, we can therefore apply Corollary A.1 to
$\mathcal{W}={\left\\{\mathbf{w}:L^{1}(\mathbf{w})\leq
L^{1}(\mathbf{0})\right\\}}$ and $\mathbf{w}(\tau)$ to lower-bound the
gradient norm on the right-hand side of (53). We obtain $L^{\prime}(\tau)\leq-
cL(\tau)$ for some $c>0$ and all $\tau\in[0,\infty)$, or equivalently,

$\displaystyle(\log L(\tau))^{\prime}\leq-c.$ (54)

Integrating over $[0,t]$ yields $L(t)\leq L(0)\cdot e^{-ct}$, which proves
global convergence in the objective: $L(t)\to 0$ as $t\to\infty$.

Now invoke Theorem A.3 with $\mathcal{W}$ as above, $\mathbf{v}=\mathbf{w}(t)$
and $\mathbf{w}=\hat{\mathbf{w}}$ (we know that both
$\mathbf{w}(\tau),\hat{\mathbf{w}}\in\mathcal{W}\cap\mathrm{span}(\mathbf{X})$,
partly by Lemma B.1):

$L(t)\geq\frac{\mu}{2}{\left\|\mathbf{w}(t)-\hat{\mathbf{w}}\right\|}^{2}.$
(55)

Since $L(t)\to 0$ as $t\to\infty$, the theorem follows. ∎

##  Appendix C Proof of Theorem 2

See 2

For the proof, we will need a result by (Arora et al., 2018), which
characterises the induced flow on $\mathbf{w}(\tau)$ when running gradient
descent on the component matrices $\mathbf{W}_{i}$.

######  Lemma C.1 ((Arora et al., 2018, Claim 2)).

If the balancedness condition (13) holds, then

${\frac{\partial\mathbf{w}(\tau)}{\partial\tau}}=-{\left\|\mathbf{w}(\tau)\right\|}^{\frac{2(N-1)}{N}}\left(\nabla
L^{1}(\mathbf{w}(\tau))+\right.\\\
\left.(N-1)\cdot\mathbf{P}_{\mathbf{w}(\tau)}\nabla
L^{1}(\mathbf{w}(\tau))\right).$ (56)

###### Proof of Theorem 2.

Similarly to the case $N=1$, we start by looking at the time-derivative of
$L$,

$\displaystyle\begin{split}L^{\prime}(\tau)=&\nabla
L^{1}(\mathbf{w}(\tau))^{\intercal}{\left({\frac{\partial\mathbf{w}(\tau)}{\partial\tau}}\right)}\\\
=&-{\left\|\mathbf{w}(\tau)\right\|}^{\frac{2(N-1)}{N}}\left({\left\|\nabla
L^{1}(\mathbf{w}(\tau))\right\|}^{2}\right.\\\
&\left.+(N-1)\cdot{\left\|\mathbf{P}_{\mathbf{w}(\tau)}\nabla
L^{1}(\mathbf{w}(\tau))\right\|}^{2}\right)\\\
\leq&-{\left\|\mathbf{w}(\tau)\right\|}^{\frac{2(N-1)}{N}}\cdot{\left\|\nabla
L^{1}(\mathbf{w}(\tau))\right\|}^{2}.\end{split}$ (57)

It is non-positive, so $\mathbf{w}(\tau)$ stays within the $L(0)$-sublevel set
throughout optimisation,

$\mathbf{w}(\tau)\in\mathcal{W}={\left\\{\mathbf{w}:L^{1}(\mathbf{w})\leq
L(0)\right\\}}.$ (58)

Also, $\mathcal{W}$ is convex and by Assumption (12) it does not contain
$\mathbf{0}$. We can therefore take $\delta>0$ to be the distance between
$\mathcal{W}$ and $\mathbf{0}$, and it follows that
${\left\|\mathbf{w}(\tau)\right\|}\geq\delta$ for $\tau\in[0,\infty)$.

Now, noting that $\mathbf{X}$ is almost surely full-rank, apply Corollary A.1
to $\mathcal{W}$ and $\mathbf{w}(\tau)$ to upper-bound the right-hand side of
(57),

$L^{\prime}(\tau)\leq-c\delta^{\frac{2(N-1)}{N}}L(\tau).$ (59)

Letting $\tilde{c}=c\delta^{\frac{2(N-1)}{N}}$, we get $(\log
L(\tau))^{\prime}\leq-\tilde{c}$ and consequently $L(t)\leq L(0)\cdot
e^{-\tilde{c}t}$. This proves convergence in the objective, $L(t)\to 0$ as
$t\to\infty$.

To prove convergence in parameters, we decompose the ‘error’
$\mathbf{w}(\tau)-\hat{\mathbf{w}}$ into orthogonal components and bound each
of them separately,

${\left\|\mathbf{w}(\tau)-\hat{\mathbf{w}}\right\|}^{2}={\left\|\mathbf{P}_{\mathbf{X}}(\mathbf{w}(\tau)-\hat{\mathbf{w}})\right\|}^{2}\\\
+{\left\|\mathbf{P}_{\mathbf{Q}}(\mathbf{w}(\tau)-\hat{\mathbf{w}})\right\|}^{2},$
(60)

where the columns of $\mathbf{Q}\in\mathbb{R}^{d\times(d-n)}$ orthogonally
complement those of $\mathbf{X}$. If $n\geq d$, we simply bound the first term
and disregard the second one.

To bound the first term, invoke Theorem A.3 with $\mathcal{W}$,
$\mathbf{v}=\mathbf{P}_{\mathbf{X}}\mathbf{w}(\tau)$ and
$\mathbf{w}=\mathbf{P}_{\mathbf{X}}\hat{\mathbf{w}}$. One can check that
$L^{1}(\mathbf{P}_{\mathbf{X}}\mathbf{u})=L^{1}(\mathbf{u})$ for all
$\mathbf{u}\in\mathbb{R}^{d}$, so
$\mathbf{P}_{\mathbf{X}}\mathbf{w}(\tau)\in\mathcal{W}$ and our use of the
theorem is legal. We obtain

$L(\tau)\geq\frac{\mu}{2}{\left\|\mathbf{P}_{\mathbf{X}}(\mathbf{w}(\tau)-\hat{\mathbf{w}})\right\|}^{2}.$
(61)

Since $L(\tau)\to 0$, it follows that

${\left\|\mathbf{P}_{\mathbf{X}}(\mathbf{w}(\tau)-\hat{\mathbf{w}})\right\|}^{2}\to
0$ (62)

as $\tau\to\infty$.

For the second term, notice that
$\hat{\mathbf{w}}\in\mathrm{span}(\mathbf{X})$, so
$\mathbf{P}_{\mathbf{Q}}\hat{\mathbf{w}}$ vanishes and we are left with
${\left\|\mathbf{P}_{\mathbf{Q}}\mathbf{w}(\tau)\right\|}^{2}$. Denote this
quantity $q(\tau)$. Its time derivative is

$\displaystyle\begin{split}q^{\prime}(\tau)=&\
2(\mathbf{P}_{\mathbf{Q}}\mathbf{w}(\tau))^{\intercal}{\left({\frac{\partial\mathbf{w}(\tau)}{\partial\tau}}\right)}\\\
=&-2{\left\|\mathbf{w}(\tau)\right\|}^{\frac{2(N-1)}{N}}\bigg{(}\mathbf{w}(\tau)^{\intercal}\mathbf{P}_{\mathbf{Q}}\nabla
L^{1}(\mathbf{w}(\tau))+\\\
&\frac{(N-1)}{{\left\|\mathbf{w}(\tau)\right\|}^{2}}\cdot\mathbf{w}(\tau)^{\intercal}\mathbf{P}_{\mathbf{Q}}\mathbf{w}(\tau)\cdot\mathbf{w}(\tau)^{\intercal}\nabla
L^{1}(\mathbf{w}(\tau))\bigg{)}\\\
=&-2q(\tau)(N-1){\left\|\mathbf{w}(\tau)\right\|}^{-2/N}\mathbf{w}(\tau)^{\intercal}\nabla
L^{1}(\mathbf{w}(\tau)),\end{split}$ (63)

where we have used the fact that $\nabla
L^{1}(\mathbf{w}(\tau))\in\mathrm{span}(\mathbf{X})$ (Theorem A.1) and
$\mathbf{Q}$ is orthogonal to $\mathbf{X}$. Rearranging, we obtain

${\frac{\mathrm{d}}{\mathrm{d}\tau}}{\left(\frac{\log
q(\tau)}{2(N-1)}\right)}=-{\left\|\mathbf{w}(\tau)\right\|}^{-2/N}\cdot\mathbf{w}(\tau)^{\intercal}\nabla
L^{1}(\mathbf{w}(\tau)).$ (64)

It turns out that the right-hand side expression is integrable in yet another
way, namely

${\frac{\mathrm{d}}{\mathrm{d}\tau}}{\left(\frac{1}{2N}\log{\left\|\mathbf{w}(\tau)\right\|}^{2}\right)}=\\\
-{\left\|\mathbf{w}(\tau)\right\|}^{-2/N}\cdot\mathbf{w}(\tau)^{\intercal}\nabla
L^{1}(\mathbf{w}(\tau)).$ (65)

Equating the two and integrating over $[0,t]$ yields

$\log\frac{q(t)}{q(0)}=\frac{N-1}{N}\cdot\log\frac{{\left\|\mathbf{w}(t)\right\|}^{2}}{{\left\|\mathbf{w}(0)\right\|}^{2}},$
(66)

which implies

$\frac{q(t)}{{\left\|\mathbf{w}(t)\right\|}^{2}}\leq{\left(\frac{{\left\|\mathbf{w}(0)\right\|}}{{\left\|\mathbf{w}(t)\right\|}}\right)}^{2/N},$
(67)

because $q(0)\leq{\left\|\mathbf{w}(0)\right\|}^{2}$.

We now bound the norm of $\mathbf{w}(t)$. Starting from an orthogonal
decomposition similar to (60) and applying (62) with (67), we get

$\displaystyle\begin{split}{\left\|\mathbf{w}(t)\right\|}^{2}=&{\left\|\mathbf{P}_{\mathbf{X}}\mathbf{w}(t)\right\|}^{2}+{\left\|\mathbf{P}_{\mathbf{Q}}\mathbf{w}(t)\right\|}^{2}\\\
\limsup_{t\to\infty}{\left\|\mathbf{w}(t)\right\|}^{2}\leq&{\left\|\hat{\mathbf{w}}\right\|}^{2}+{\left\|\mathbf{w}(0)\right\|}^{\frac{2}{N}}\limsup_{t\to\infty}{\left\|\mathbf{w}(t)\right\|}^{2-\frac{2}{N}}.\end{split}$
(68)

Denote $\nu:=\limsup_{t\to\infty}{\left\|\mathbf{w}(t)\right\|}$. By the same
orthogonal decomposition, we also know that
$\nu^{2}\geq\limsup_{t\to\infty}{\left\|\mathbf{P}_{\mathbf{X}}\mathbf{w}(t)\right\|}^{2}={\left\|\hat{\mathbf{w}}\right\|}^{2}>0$,
so we can divide both sides above by $\nu^{2}$,

$1\leq\frac{{\left\|\hat{\mathbf{w}}\right\|}^{2}}{\nu^{2}}+\frac{{\left\|\mathbf{w}(0)\right\|}^{2/N}}{\nu^{2/N}}=:f(\nu).$
(69)

On the right-hand side, we now have a decreasing function of $\nu$ that goes
to zero as $\nu\to\infty$. However, evaluated at our specific $\nu$, it is
lower-bounded by $1$, implying an implicit upper bound for $\nu$.

How do we find this bound? Suppose we find some constant $K$ such that
$f(K)\leq 1$. Then, because $f$ is decreasing, it must be the case that
$\nu\leq K$. One such candidate for $K$ is

$K={\left\|\hat{\mathbf{w}}\right\|}\cdot{\left(1-\frac{{\left\|\mathbf{w}(0)\right\|}^{2/N}}{{\left\|\hat{\mathbf{w}}\right\|}^{2/N}}\right)}^{\frac{-N}{2(N-1)}}.$
(70)

(Here we have used condition (11):
${\left\|\mathbf{w}(0)\right\|}<{\left\|\hat{\mathbf{w}}\right\|}$.) To check
that indeed $f(K)\leq 1$, start from the inequality

${\left({{\left\|\hat{\mathbf{w}}\right\|}}/K\right)}^{\frac{2(N-1)}{N}}+\frac{{\left\|\mathbf{w}(0)\right\|}^{2/N}}{{\left\|\hat{\mathbf{w}}\right\|}^{2/N}}=1\\\
\leq{\left(1-\frac{{\left\|\mathbf{w}(0)\right\|}^{2/N}}{{\left\|\hat{\mathbf{w}}\right\|}^{2/N}}\right)}^{\frac{-1}{N-1}}=({\left\|\hat{\mathbf{w}}\right\|}/K)^{-\frac{2}{N}}.$
(71)

Taking the leftmost and rightmost expression and multiplying by
$({\left\|\hat{\mathbf{w}}\right\|}/K)^{2/N}$ yields

$f(K)=\frac{{\left\|\hat{\mathbf{w}}\right\|}^{2}}{K^{2}}+\frac{{\left\|\mathbf{w}(0)\right\|}^{2/N}}{K^{2/N}}\leq
1.$ (72)

Hence,

$\limsup_{t\to\infty}{\left\|\mathbf{w}(t)\right\|}\leq{\left\|\hat{\mathbf{w}}\right\|}\cdot{\left(1-\frac{{\left\|\mathbf{w}(0)\right\|}^{2/N}}{{\left\|\hat{\mathbf{w}}\right\|}^{2/N}}\right)}^{\frac{-N}{2(N-1)}}.$
(73)

Finally, let us turn back to our original goal of bounding
${\left\|\mathbf{w}(\tau)-\hat{\mathbf{w}}\right\|}^{2}$. With (60), (62),
(67) and (73), we now know that

$\displaystyle\limsup_{t\to\infty}{\left\|\mathbf{w}(\tau)-\hat{\mathbf{w}}\right\|}^{2}$
(74)
$\displaystyle\leq{\left\|\mathbf{w}(0)\right\|}^{\frac{2}{N}}{\left\|\hat{\mathbf{w}}\right\|}^{\frac{2(N-1)}{N}}{\left(1-\frac{{\left\|\mathbf{w}(0)\right\|}^{\frac{2}{N}}}{{\left\|\hat{\mathbf{w}}\right\|}^{\frac{2}{N}}}\right)}^{-1}$
(75)
$\displaystyle=\frac{{\left\|\hat{\mathbf{w}}\right\|}^{2+2/N}}{{\left\|\hat{\mathbf{w}}\right\|}^{2/N}-{\left\|\mathbf{w}(0)\right\|}^{2/N}}-{\left\|\hat{\mathbf{w}}\right\|}^{2}.$
(76)

Hence, if we initialise close enough to zero, as specified by condition (11),
we can ensure that

$\limsup_{t\to\infty}{\left\|\mathbf{w}(\tau)-\hat{\mathbf{w}}\right\|}^{2}<\epsilon^{2}.$
(77)

This concludes the proof. ∎

##  Appendix D Theorem 3 for Approximate Distillation

We extend Theorem 3 to the setting where the student learns the solution
$\hat{\mathbf{w}}=\mathbf{X}(\mathbf{X}^{\intercal}\mathbf{X})^{-1}\mathbf{X}^{\intercal}\mathbf{w}_{*}$
only $\epsilon$-approximately, as is the case for deep linear networks
initialised as in Theorem 2. When $n\geq d$, the teacher’s weight vector is
recovered exactly and the transfer risk is zero, even when the student is
deep. The following theorem therefore only covers the case $n<d$.

######  Theorem D.1 (Risk bound for approximate distillation).

Let $n<d$. For any training set $\mathbf{X}\in\mathbb{R}^{d\times n}$, let
$\hat{h}_{\mathbf{X}}(\mathbf{x})=\mathds{1}{\left\\{\hat{\mathbf{w}}_{\epsilon}^{\intercal}\mathbf{x}\geq
0\right\\}}$ be a linear classifier whose weight vector is $\epsilon$-close to
the distillation solution $\hat{\mathbf{w}}$, i.e.
${\left\|\hat{\mathbf{w}}_{\epsilon}-\hat{\mathbf{w}}\right\|}\leq\epsilon$,
where $\epsilon$ is a positive constant such that
$\epsilon\leq\frac{1}{2}{\left\|\hat{\mathbf{w}}\right\|}$. Define
$\delta:=\sqrt{\frac{2\pi\epsilon}{{\left\|\hat{\mathbf{w}}\right\|}}}$. Then,
it holds for any $\beta\in[0,\pi/2-\delta]$ that

$\operatorname*{\mathbb{E}}_{\mathbf{X}\sim P_{\mathbf{x}}^{\otimes
n}}{\left[R\big{(}\hat{h}_{\mathbf{X}}\big{|}P_{\mathbf{x}},\mathbf{w}_{*}\big{)}\right]}\leq
p(\beta)+p(\pi/2-\delta-\beta)^{n}.$ (78)

The result is very similar to Theorem 3 in the main text, the only difference
is the constant $\delta$ which compensates for the imprecision in learning
$\hat{\mathbf{w}}$ by pushing the bound up (recall that $p$ is decreasing).
However, as $\epsilon$ goes to zero, so does $\delta$ and we recover the
original bound.

For the proof, we start with a tool for controlling the angle between
$\hat{\mathbf{w}}$ and $\hat{\mathbf{w}}_{\epsilon}$. Recall that the angle is
defined as

$\alpha(\mathbf{w},\mathbf{v})=\cos^{-1}{\left(\frac{\mathbf{w}^{\intercal}\mathbf{v}}{{\left\|\mathbf{w}\right\|}\cdot{\left\|\mathbf{v}\right\|}}\right)}$
(79)

for
$\mathbf{w},\mathbf{v}\in\mathbb{R}^{d}\setminus{\left\\{\mathbf{0}\right\\}}$.

######  Lemma D.1.

Let $\mathbf{w},\mathbf{v}\in\mathbb{R}^{d}$ be such that
${\left\|\mathbf{w}-\mathbf{v}\right\|}\leq\epsilon$, where
$\epsilon\leq\frac{1}{2}{\left\|\mathbf{w}\right\|}$. Then
$\alpha(\mathbf{w},\mathbf{v})\leq\sqrt{\frac{2\pi\epsilon}{{\left\|\mathbf{w}\right\|}}}$.

###### Proof of Lemma D.1.

The first step is to lower-bound the inner product
$\mathbf{w}^{\intercal}\mathbf{v}$. To that end, we expand and rearrange
${\left\|\mathbf{w}-\mathbf{v}\right\|}^{2}\leq\epsilon^{2}$ to obtain

$2\mathbf{w}^{\intercal}\mathbf{v}\geq{\left\|\mathbf{w}\right\|}^{2}+{\left\|\mathbf{v}\right\|}^{2}-\epsilon^{2}.$
(80)

Now use the triangle relation
${\left\|\mathbf{v}\right\|}\geq{\left\|\mathbf{w}\right\|}-\epsilon$ squared
to lower-bound the right-hand side of (80) and get

$2\mathbf{w}^{\intercal}\mathbf{v}\geq
2{\left\|\mathbf{w}\right\|}^{2}-2\epsilon{\left\|\mathbf{w}\right\|},$ (81)

which implies

$\frac{\mathbf{w}^{\intercal}\mathbf{v}}{{\left\|\mathbf{w}\right\|}\cdot{\left\|\mathbf{v}\right\|}}\geq\frac{{\left\|\mathbf{w}\right\|}-\epsilon}{{\left\|\mathbf{v}\right\|}}\geq\frac{{\left\|\mathbf{w}\right\|}-\epsilon}{{\left\|\mathbf{w}\right\|}+\epsilon}\geq
1-\frac{2\epsilon}{{\left\|\mathbf{w}\right\|}}.$ (82)

Thus,

$1-\frac{2\epsilon}{{\left\|\mathbf{w}\right\|}}\leq\frac{\mathbf{w}^{\intercal}\mathbf{v}}{{\left\|\mathbf{w}\right\|}\cdot{\left\|\mathbf{v}\right\|}}=\cos(\alpha(\mathbf{w},\mathbf{v})).$
(83)

The left-hand side is by assumption non-negative, so we have
$\alpha(\mathbf{w},\mathbf{v})\in[-\pi/2,\pi/2]$. On this domain,

$\cos x\leq 1-\frac{x^{2}}{\pi},$ (84)

which lets us deduce

$1-\frac{2\epsilon}{{\left\|\mathbf{w}\right\|}}\leq
1-\frac{\alpha(\mathbf{w},\mathbf{v})^{2}}{\pi}.$ (85)

Rearranging yields the result. ∎

###### Proof of Theorem D.1.

We decompose the expected risk as follows:

$\displaystyle\begin{split}\operatorname*{\mathbb{E}}_{\mathbf{X}\sim
P_{\mathbf{x}}^{n}}&{\left[R\big{(}\hat{h}_{\mathbf{X}}\big{|}P_{\mathbf{x}},\mathbf{w}_{*}\big{)}\right]}=\operatorname*{\mathbb{P}}_{\begin{subarray}{c}\mathbf{X}\sim
P_{\mathbf{x}}^{n}\\\ \mathbf{x}\sim
P_{\mathbf{x}}\end{subarray}}[\mathbf{w}_{*}^{\intercal}\mathbf{x}\cdot\hat{\mathbf{w}}_{\epsilon}^{\intercal}\mathbf{x}<0]=\\\
&=\int_{\mathbf{x}:\bar{\alpha}(\mathbf{w}_{*},\mathbf{x})\geq\beta}\operatorname*{\mathbb{P}}_{\mathbf{X}\sim
P_{\mathbf{x}}^{n}}[\mathbf{w}_{*}^{\intercal}\mathbf{x}\cdot\hat{\mathbf{w}}_{\epsilon}^{\intercal}\mathbf{x}<0|\mathbf{x}]\,\mathrm{d}P_{\mathbf{x}}\\\
&+\int_{\mathbf{x}:\bar{\alpha}(\mathbf{w}_{*},\mathbf{x})<\beta,\,\mathbf{w}_{*}^{\intercal}\mathbf{x}>0}\operatorname*{\mathbb{P}}_{\mathbf{X}\sim
P_{\mathbf{x}}^{n}}[\hat{\mathbf{w}}_{\epsilon}^{\intercal}\mathbf{x}<0|\mathbf{x}]\,\mathrm{d}P_{\mathbf{x}}\\\
&+\int_{\mathbf{x}:\bar{\alpha}(\mathbf{w}_{*},\mathbf{x})<\beta,\,\mathbf{w}_{*}^{\intercal}\mathbf{x}<0}\operatorname*{\mathbb{P}}_{\mathbf{X}\sim
P_{\mathbf{x}}^{n}}[\hat{\mathbf{w}}_{\epsilon}^{\intercal}\mathbf{x}>0|\mathbf{x}]\,\mathrm{d}P_{\mathbf{x}}.\end{split}$
(86)

Let us fix some $\mathbf{x}$ for which
$\bar{\alpha}(\mathbf{w}_{*},\mathbf{x})<\beta$ and
$\mathbf{w}_{*}^{\intercal}\mathbf{x}>0$; for this $\mathbf{x}$ we have
$\alpha(\mathbf{w}_{*},\mathbf{x})=\bar{\alpha}(\mathbf{w}_{*},\mathbf{x})$.
Consider the situation where
$\bar{\alpha}(\mathbf{w}_{*},\mathbf{x}_{i})<\pi/2-\beta-\delta$ for some $i$.
Then by the triangle inequality, Lemma D.1 and Lemma 1,

$\displaystyle\alpha(\hat{\mathbf{w}}_{\epsilon},\mathbf{x})$
$\displaystyle\leq\alpha(\hat{\mathbf{w}}_{\epsilon},\hat{\mathbf{w}})+\alpha(\mathbf{w}_{*},\hat{\mathbf{w}})+\alpha(\mathbf{w}_{*},\mathbf{x})$
(87)
$\displaystyle\leq\delta+\bar{\alpha}(\mathbf{w}_{*},\mathbf{x}_{i})+\bar{\alpha}(\mathbf{w}_{*},\mathbf{x})$
(88) $\displaystyle<\pi/2,$ (89)

which implies $\hat{\mathbf{w}}_{\epsilon}^{\intercal}\mathbf{x}>0$, i.e. a
correct prediction (same as the teacher’s). Conversely, an error can occur
only if $\bar{\alpha}(\mathbf{w}_{*},\mathbf{x}_{i})\geq\pi/2-\delta-\beta$
for all $i$. Because $\mathbf{x}_{i}$ are independent, we have

$\displaystyle\begin{split}\operatorname*{\mathbb{P}}_{\mathbf{X}\sim
P_{\mathbf{x}}^{n}}[\hat{\mathbf{w}}_{\epsilon}^{\intercal}\mathbf{x}<&\,0|\,\mathbf{x}:\bar{\alpha}(\mathbf{w}_{*},\mathbf{x})<\beta,\,\mathbf{w}_{*}^{\intercal}\mathbf{x}>0]\\\
&\leq\operatorname*{\mathbb{P}}_{\mathbf{X}\sim
P_{\mathbf{x}}^{n}}[\forall_{i}:\bar{\alpha}(\mathbf{w}_{*},\mathbf{x}_{i})\geq\pi/2-\delta-\beta]\\\
&=p(\pi/2-\delta-\beta)^{n}.\end{split}$ (90)

By a symmetric argument, one can show that

$\operatorname*{\mathbb{P}}_{\mathbf{X}\sim
P_{\mathbf{x}}^{n}}[\hat{\mathbf{w}}_{\epsilon}^{\intercal}\mathbf{x}>0|\,\mathbf{x}:\bar{\alpha}(\mathbf{w}_{*},\mathbf{x})<\beta,\,\mathbf{w}_{*}^{\intercal}\mathbf{x}<0]\\\
\leq p(\pi/2-\delta-\beta)^{n}.$ (91)

Combining (86), (90) and (91) yields the result. ∎