Teacher Improves Learning by Selecting a Training Subset

arXiv:1802.08946v1 [stat.ML] 25 Feb 2018

Yuzhe Ma

Robert Nowak
Philippe Rigollet∗
Xuezhou Zhang
Xiaojin Zhu
∗
University of Wisconsin-Madison
Massachusetts Institute of Technology

Abstract
We call a learner super-teachable if a teacher can
trim down an iid training set while making the
learner learn even better. We provide sharp superteaching guarantees on two learners: the maximum likelihood estimator for the mean of a Gaussian, and the large margin classifier in 1D. For
general learners, we provide a mixed-integer nonlinear programming-based algorithm to find a super teaching set. Empirical experiments show that
our algorithm is able to find good super-teaching
sets for both regression and classification problems.

1

Introduction

Consider the following question: a learner receives an iid
training set S drawn from a distribution parametrized by θ∗ .
There is a teacher who knows θ∗ . Can the teacher select a
subset from S so the learner estimates θ∗ better from the
subset than from S?
This question is distinct from training set reduction (see
e.g. [19, 43, 42]) in that the teacher can use the knowledge
of θ∗ to carefully design the subset. It is, in fact, a coding
problem: Can the teacher approximately encode θ∗ using
items in S for a known decoder, which is the learner? As
such, the question is not a machine learning task but rather
a machine teaching one [47, 20, 45].
This question is relevant for several nascent applications.
One application is in understanding blackbox models such
as deep nets. Often observation to a blackbox model is
limited to its predicted label y = θ∗ (x) given input x. One
way to interpret a blackbox model is to locally train an
interpretable model with data points S labeled by the blackbox model around the region of interest [35]. We, however,
ask for more: to reduce the size of the training set S for
Proceedings of the 21st International Conference on Artificial Intelligence and Statistics (AISTATS) 2018, Lanzarote, Spain. PMLR:
Volume 84. Copyright 2018 by the author(s).

the local learner while making the learner approximate the
blackbox better. The reduced training set itself also serves
as representative examples of local model behavior. Another
application is in education. Imagine a teacher who has a
teaching goal θ∗ . This is a reasonable assumption in practice: e.g. a geology teacher has the knowledge of the actual
decision boundaries between rock categories. However, the
teacher is constrained to teach with a given textbook (or
a set of courseware) S. To the extent that the student is
quantified mathematically, the teacher wants to select pages
in the textbook with the guarantee that the student learns
better from those pages than from gulping the whole book.
But is the question possible? The following example says
yes. Consider learning a threshold classifier on the interval
[−1, 1], with true threshold at θ∗ = 0. Let S have n items
drawn uniformly from the interval and labeled according to
θ∗ . Let the learner be a hard margin SVM, which places the
estimated threshold in the middle of the inner-most pair in
S with different labels: θ̂S = (x− + x+ )/2 where x− is the
largest negative training item and x+ the smallest positive
training item in S. It is well known that |θ̂S − θ∗ | converges
at a rate of 1/n: the intuition being that the average space
between adjacent items is O(1/n).

-1

0

1

Figure 1: The original training set S with n = 6 items
(circles and stars; green=negative, purple=positive), and the
most-symmetric training set (stars) the teacher selects.

The teacher knows everything but cannot tell θ∗ directly to
the learner. Instead, it can select the most-symmetric pair
in S about θ∗ and give them to the learner as a two-item
training set. We will prove later that the risk on the most
symmetric pair is O(1/n2 ), that is, learning from the selected subset surpasses learning from S. Thus we observe
something interesting: the teacher can turn a larger training set S into a smaller and better subset for the midpoint
classifier. We call this phenomenon super-teaching.

Teacher Improves Learning by Selecting a Training Subset

2

Formal Definition of Super Teaching

3

Let Z be the data space: for unsupervised learning Z = X,
while for supervised learning Z = X × Y. Let pZ be the
underlying distribution over Z. We take a function view of
n
the learner: a learner A is a function A : ∪∞
n=0 Z 7→ Θ,
where Θ is the learner’s hypothesis space. The notation
n
∪∞
n=0 Z defines the “set of (potentially non-iid) training
sets”, namely multisets of any size whose elements are in Z.
n
Given any training set T ∈ ∪∞
n=0 Z , we assume A returns
a unique hypothesis A(T ) , θ̂T ∈ Θ. The learner’s risk
R(θ) for θ ∈ Θ is defined as:
R(θ) = EpZ [`(θ(x), y)] , or R(θ) = kθ − θ∗ k2 .

Analysis on Super Teaching for the MLE
of Gaussian mean

In this section, we present our first theoretical result on
super teaching, when the learner AM LE is the maximum
likelihood estimator (MLE) for the mean of a Gaussian. Let
Z = X = R, Θ = R, pZ (x) = N (θ∗ , 1). Given a sample S
of size n drawn from pZ , the learner
the MLE for
Pcomputes
n
the mean: θ̂S = AM LE (S) = n1 i=1 xi . We define the
risk as R(θ̂S ) = |θ̂S − θ∗ |. The teacher we consider is the
optimal k-subset teacher Bk , which uses the best subset of
size k to teach:

(1)

The former is for prediction tasks where `() is a loss function
and θ(x) denotes the prediction on x made by model θ;
the latter is for parameter estimation where we assume a
realizable model pZ = pθ∗ for some θ∗ ∈ Θ.
We now introduce a clairvoyant teacher B who has full
knowledge of pZ , A, R. The teacher is also given an iid
training set S = {z1 , . . . , zn } ∼ pZ . If the teacher teaches
S to A, the learner will incur a risk R(A(S)) , R(θ̂S ).
The teacher’s goal is to judiciously select a subset B(S) ⊂
S to act as a “super teaching set” for the learner so that
R(θ̂B(S) ) < R(θ̂S ). Of course, to do so the teacher must
utilize her knowledge of the learning task, thus the subset
is actually a function B(S, pZ , A, R). In particular, the
teacher knows pZ already, and this sets our problem apart
from machine learning. For readability we suppress these
extra parameters in the rest of the paper. We formally define
super teaching as follows.
Definition 1 (Super Teaching). B is a super teacher for
learner A if ∀δ > 0, ∃N such that ∀n ≥ N
h
i
PS R(θ̂B(S) ) ≤ cn R(θ̂S ) > 1 − δ,
(2)
iid

where S ∼ pnZ , B(S) ⊂ S, and cn ≤ 1 is a sequence we
call super teaching ratio.
Obviously, cn = 1 can be trivially achieved by letting
B(S) = S so we are interested in small cn . There are
two fundamental questions: (1) Do super teachers provably
exist? (2) How to compute a super teaching set B(S) in
practice?
We answer the first question positively by exhibiting super
teaching on two learners: maximum likelihood estimator for
the mean of a Gaussian in section 3, and 1D large margin
classifier in section 4. Guarantees on super teaching for general learners remain future work. Nonetheless, empirically
we can find a super teaching set for many general learners:
We formulate the second question as mixed-integer nonlinear programming in section 5. Empirical experiments
in section 6 demonstrates that one can find a good B(S)
effectively.

Bk (S) ∈ argminT ⊂S,|T |=k R(θ̂T ).

(3)

To build intuition,
√it is well-known that the risk of AM LE
under S is O(1/ n) because the variance under n items
shrinks like 1/n. Now consider k = 1. Since the teacher
B1 knows θ∗ , under our setting the best teaching strategy is
for her to select the item in S closest to θ∗ , which forms the
singleton teaching set B1 (S). One can show that with large
probability this closest item is O(1/n) away from θ∗ (the
central part of a Gaussian density is essentially uniform).
Therefore, we already see a super teaching ratio of cn =
1
n− 2 . More generally, our main result below shows that Bk
1
achieves a super teaching ratio cn = O(n−k+ 2 ):
Theorem 1. Let Bk be the optimal k-subset teacher.
∀ ∈ (0, 2k−1
4 h), ∀δ ∈ (0, 1), ∃N (k, ,iδ) such that ∀n ≥
N (k, , δ), P R(θ̂Bk (S) ) ≤ cn R(θ̂S )
cn =

> 1 − δ, where

k−
1
k√
n−k+ 2 +2 .
k

Toward proving the theorem, 1 we first recall the standard
1
rate R(θ̂S ) ≈ n− 2 if AM LE learns from the whole training
set S:
Proposition 2. Let S be an n-item iid sample drawn from
N (θ∗ , 1). ∀ > 0, ∀δ ∈ (0, 1), ∃N1 (, δ) such that ∀n ≥
N1 ,
h 1
i
1
P n− 2 − < R(θ̂S ) < n− 2 + > 1 − δ.
(4)
Proof. R(θ̂S ) = |θ̂S − θ∗ | and θ̂S − θ∗ ∼ N (0, n−1 ) =
p n − nx2
1
1
2 . Let α = n− 2 − and β = n− 2 + . We have
2π e
Z αr
h
i
n − nx2
P R(θ̂S ) ≤ α = 2
e 2 dx
2π
0
r
(5)
r
Z αr
n
n
2 −
dx = 2α
=
n ,
<2
2π
2π
π
0
1
Remark: we introduced an auxiliary variable  which controls the implicit tradeoff between cn , how much super teaching
helps, and N , how soon super teaching takes effect. When  → 0
1
the teaching ratio cn approaches O(n−k+ 2 ), but as we will see
N (k, , δ) → ∞. Similarly, k also affects the tradeoff: the teaching ratio is smaller as we enlarge k, but N (k, , δ) increases.

Yuzhe Ma, Robert Nowak, Philippe Rigollet∗ , Xuezhou Zhang, Xiaojin Zhu

Z

r
∞

n − nx2
e 2 dx
2π
β
Z ∞ r
Z ∞ r
x
n − nx2
1
n − ny
<2
e 2 dx =
e 2 dy (6)
β
2π
β
2π
2
β
β
r
r
r
1
1
2 − nβ2
2
2 −
=
e 2 <
=
n .
β nπ
β nπ
π
h
i
h
i
Thus P α < R(θ̂S ) < β = 1 − P R(θ̂S ) ≤ α −
q
h
i
P R(θ̂S ) ≥ β > 1 − 2 π2 n− . Let N1 (, δ) =
q
h
i
1
( 1δ π8 )  , then ∀n ≥ N1 , P α < R(θ̂S ) < β > 1 −
δ.
h
i
P R(θ̂S ) ≥ β = 2

We now work out the risk of AM LE if it learns from
the optimal k-subset teacher Bk . Theorem 4 says that
this risk is very small and sharply concentrated around
R(θ̂Bk (S) ) ≈ n−k . To prove Theorem 4, we first give
the following lemma.
 
n
Lemma 3. Denote Ckn =
. Let the index set I =
k
{1, 2, ...n} where n ≥ 4k. Consider all subsets of size k,
n
then there are at most 4k Ck2k C2k−1
ordered pairs of subsets
that are overlapping but not identical.
Proof. Let I1 and I2 be two subsets of size k and they
overlap on t indexes. Then the total number of distinct inn
dexes that appear in I1 ∪ I2 is 2k − t. There are C2k−t
ways of choosing such 2k − t indexes. Next we determine which t indexes are overlapping ones. We have
Ct2k−t ways of choosing such t indexes. Finally we have
2k−2t
Ck−t
ways of selecting half of the non-overlapping indexes and attribute them to I1 . Thus in total we have
2k−2t
n
Ot = C2k−t
Ct2k−t Ck−t
ordered pairs of subsets that
overlap on t indexes. By our assumption n ≥ 4k we
n
n
have C2k−t
≤ C2k−1
. Also note that Ct2k−t < Ct2k and
2k−2t
2k
n
Ck−t < Ck , thus Ot < C2k−1
Ct2k Ck2k . Therefore the
total number of ordered pairs of subsets that are overlapping
but not identical is
O=

k−1
X
t=1

<

2k
X

Ot <

k−1
X

n
C2k−1
Ct2k Ck2k

t=1

(7)

n
n
C2k−1
Ct2k Ck2k = 4k Ck2k C2k−1
.

t=0

(0, k), ∀δ ∈ (0, 1), ∃N2 (k, , δ) such that ∀n ≥ N2 ,


1 k
1 k
P √ ( )k+ < R(θ̂Bk (S) ) < √ ( )k− > 1 − δ.
k n
k n
(8)
Proof.
P Let I ⊆ ∗{1, 2, ..., n} and |I| = k, define γI =
√1
i∈I (xi − θ ). Let SI denote the subset indexed by
k
P
I. Note that θ̂SI = k1 i∈I xi and R(θ̂SI ) = |θ̂SI − θ∗ | =
P
| k1 i∈I xi − θ∗ | = √1k |γI |. Also note that R(θ̂Bk (S) ) =
inf I R(θ̂SI ) = √1k inf I |γI |. Thus to prove Theorem 4 it
suffices to prove


k k−
k k+
< inf |γI | < ( )
→ 1.
(9)
P ( )
I
n
n
Let α = ( nk )k+ and β = ( nk )k− . We first prove the lower
bound. Note that γI has the same distribution for all I. Thus
by the union bound,
h
i
P inf |γI | ≤ α = P [∃I : |γI | ≤ α] ≤ Ckn P [|γI1 | ≤ α] ,
I

(10)
where I1 = {1, 2, ..., k}. Since γI1 ∼ N (0, 1), we have
r
Z α
1 − x2
2
2
√ e
P [|γI1 | ≤ α] =
dx <
α.
(11)
π
2π
−α
k
Note that Ckn ≤ ( en
k ) . Thus,
r
r
h
i
en k 2
2 k k 
P inf |γI | ≤ α < ( )
α=
e ( ) → 0.
I
k
π
π
n
(12)
0
0
Thus ∃N2 (k, , δ) such that ∀n ≥ N2 ,
h
i δ
P inf |γI | ≤ α < .
(13)
I
2

To show the upper bound, we define tI = P
1 [|γI | < β],
where 1 [] is the indicator function. Let T = I tI . Then
it suffices to show limn→∞ P [T = 0] = 0. Note that
P [T = 0] = P [T − E [T ] = −E [T ]]


V [T ]
≤ P (T − E [T ])2 ≥ (E [T ])2 ≤
,
(E [T ])2

where the last inequality follows from the Markov inequality.
Now we lower bound E [T ].
"
#
X
X
E [T ] = E
tI =
E [tI ] = Ckn E [tI1 ]
I

=

Ckn P

[|γI1 | < β] =

I

Ckn

Z

β

−β

Now we prove the risk of the optimal k-subset teacher.
Theorem 4. Let Bk be the optimal k-subset teacher. Let
S be an n-item iid sample drawn from N (θ∗ , 1). ∀ ∈

(14)

(15)
x2
1
√ e− 2 dx.
2π
2

Note that  < k, thus β < 1. For x ∈ (−β, β),

x
√1 e− 2
2π

1
√1 e− 2
2π

thus

=

√1 .
2πe

Also note that

Ckn

n
1
E [T ] > ( )k √
2β =
k
2πe

>
r

( nk )k ,

2 n 
( ).
πe k

>

(16)

Teacher Improves Learning by Selecting a Training Subset

Now we upper bound V [T ].
X
Cov [tI , tI 0 ] =
V [T ] =
I,I

Now plug (24) and (16) into (14), we have
X
0

0

Cov [tI , tI 0 ] .
0

I,I ,|I∩I |≥1

(17)
Note that for Bernoulli random variable tI , V [tI ] ≤ E [tI ].
0
Thus if I = I , then
Cov [tI , tI 0 ] = V [tI ] ≤ E [tI ] = P [|γI | < β]
r
Z β
2 k k− (18)
1
1 − x2
√ e 2 dx < √ 2β =
( ) .
=
π n
2π
2π
−β
0

0

Otherwise 1 ≤ |I ∩ I | ≤ k − 1, that is, I and I overlap
but not identical, then
Cov [tI , tI 0 ] = E [tI tI 0 ] − E [tI ] E [tI 0 ] ≤ E [tI tI 0 ]
= P [|γI | < β, |γI 0 | < β] .
(19)
Note that γI and γI 0 are jointly Gaussian with covariance
1 X
Cov [γI , γI 0 ] =
Cov [xi − θ∗ , xi0 − θ∗ ]
k
0
0
i∈I,i ∈I

1
=
k

i∈I,i0 ∈I 0 ,i=i

Note that f (x, y) ≤

1
2π

p

1 − ρ2

√1
2π

1−ρ2

2 −2ρxy+y 2
2(1−ρ2 )

−x

e

ZZ

1

|x|<β,|y|<β

Since

2π

(21)

, thus

P [|γI | < β, |γI 0 | < β] ≤
=

.

2π

p

1 − ρ2

dxdy

1
2
p
(2β)2 = p
β2.
1 − ρ2
π 1 − ρ2

√2
π 1−ρ2

≤

√ 2
2
π 1−( k−1
k )

≤

π

q2

k
k2

=

√
2 k
π ,

(22)
thus

√
√
2 kβ 2
2 k k 2k−2
P [|γI | < β, |γI 0 | < β] ≤
=
( )
.
π
π n
(23)
n
According to Lemma 3, there are at most 4k Ck2k C2k−1
pairs
0
0
of I and I such that 1 ≤ |I ∩ I | ≤ k − 1. Thus,
X
X
V [T ] =
V [tI ] +
Cov [tI , tI 0 ]
I

I6=I 0 ,|I∩I 0 |≥1

√
2 k k−
2 k k 2k−2
k 2k n
≤
( )
+ 4 Ck C2k−1
( )
π n
π n
r
√
2 en k k k−
en 2k−1 2 k k 2k−2
k 2k
≤
( ) ( )
+ 4 Ck (
)
( )
π k
n
2k − 1
π n
r
√
2 k n  4 k 2k 2ek 2k−1 n 2−1
=
e ( ) +
Ck (
)
( )
.
π
k
π
2k − 1
k
(24)
r

Ckn

0

(26)

00

Let N2 (k, , δ) = max{N2 (k, , δ), N2 (k, , δ)}, combining (13) and (26) concludes the proof.
Now we can conclude super-teaching by comparing Theorem 4 and Proposition 2:
Proof of Theorem 1. Let α =
n

− 12 −

. By Proposition 2, ∀ ∈

∃N1 (,

δ
2)

√1 ( k )k− and
k n
(0, 2k−1
h4 ), ∀δ ∈

β =

(0,
i 1),
such that ∀n ≥ N1 , P R(θ̂S ) > β >

δ
h By Theorem 4,i ∃N2 (k, , 2 ) such that ∀n ≥
N2 , P R(θ̂Bk (S) ) < α
> 1 − 2δ .
Let cn =

|I ∩ I |
, ρ,
1=
k
0

(20)
where k1 ≤ ρ ≤ k−1
.
The
joint
PDF
of
two
standard
normal
k
distributions x, y with covariance ρ is
f (x, y) =

h
i δ
P inf |γI | ≥ β < .
I
2

1−

0

X

n
n
P [T = 0] ≤ a1 (k)( )− + a2 (k)( )−1 → 0, (25)
k
k
√
p π k+1
2ek 2k−1
where a1 = 2 e
and a2 (k) = 2 keCk2k ( 2k−1
.
)
00
00
Thus ∃N2 (k, , δ) such that ∀n ≥ N2 ,

δ
2.

k−
1
k√
n−k+ 2 +2 .
k

Since  < 2k−1
4 , cn is a decreasing
sequence in n with limn→∞ cn = 0. Let N3 (k, ) be
the first integer such that cN3 ≤ 1. Let N (k, , δ) =
δ
max{N1 (, 2δ ), N2 (k,
h , 2 ), N3 (k, )}. By a union
i bound

∀n ≥ N (k, , δ), P R(θ̂Bk (S) ) < α, R(θ̂S ) ≥ β > 1−δ.
h
i
Since α
=
c
,
we
have
P
R(
θ̂
)
≤
c
R(
θ̂
)
>
n
n
S
B
(S)
k
β
1 − δ, where cn ≤ cN3 ≤ 1.

4

Analysis on Super Teaching for 1D Large
Margin Classifier

We present our second theoretical result, this time on teaching a 1D large margin classifier. Let X = [−1, 1], Y =
{−1, 1}, Θ = [−1, 1], θ∗ = 0, pZ (x, y) = pZ (x)pZ (y | x)
where pZ (x) = U (X) and pZ (y = 1 | x) = 1 [x ≥ θ∗ ].
Let x− , maxi:yi =−1 xi and x+ , mini:yi =+1 xi be the
inner-most pair of opposite labels in S if they exist. We
formally define the large margin classifier Alm (S) as

 (x− + x+ )/2 if x− , x+ exist
−1
if S all positive
θ̂S = Alm (S) =

1
if S all negative.
(27)
The risk is defined as R(θ̂S ) = |θ̂S − θ∗ | = |θ̂S |. The
teacher we consider is the most symmetric teacher, who
selects the most symmetric pair about θ∗ in S and gives it
to the learner. We define the most-symmetric teacher Bms :

{(s− , −1), (s+ , 1)} if s− , s+ exist,
Bms (S) =
{(x1 , y1 )}
otherwise.
(28)

Yuzhe Ma, Robert Nowak, Philippe Rigollet∗ , Xuezhou Zhang, Xiaojin Zhu
0

∗
where (s− , s+ ) ∈ argmin(x,−1),(x0 ,1)∈S | x+x
2 − θ |.

Our main result shows that learning from the whole set
S achieves the well-known O(1/n) risk, but surprisingly
Bms achieves O(1/n2 ) risk, therefore it is an approximately
cn = O(n−1 ) super teaching ratio.
Theorem 5. Let S be an n-item iid sample drawn from
pZ h. Then ∀δ ∈ (0, 1), i∃N (δ) such that ∀n ≥ N ,
P R(θ̂Bms (S) ) ≤ cn R(θ̂S ) > 1 − δ, where cn =

32
nδ

ln 6δ .

Before proving Theorem 5, we first show that Bms is an
optimal teacher for the large margin classifier.
Proposition 6. Bms is an optimal teacher for the large
margin classifier θ̂S .
Proof. We show R(θ̂Bms (S) ) ≤ R(θ̂B(S) ) for any B and
any S.
If |Bms (S)| = 1, then S is either all positive or all negative.
In both cases R(θ̂B(S) ) = 1 for any B by definition. Thus
R(θ̂Bms (S) ) ≤ R(θ̂B(S) ).
Otherwise |Bms (S)| = 2, then if B(S) is all positive or all
negative, we have R(θ̂B(S) ) = 1 and thus R(θ̂Bms (S) ) ≤
B
R(θ̂B(S) ). Otherwise let xB
− , x+ be the inner most pair
B
B
of B(S). Since x− , x+ ∈ S, then by definition of Bms ,
+
R(θ̂Bms (S) ) = | s− +s
− θ∗ | ≤ |
2

B
xB
− +x+

2

− θ∗ | = R(θ̂B(S) ).

Now we show that learning on the whole S incurs O(n−1 )
risk. First, we give the following lemma for the exact tail
probability of R(θ̂S ).
Lemma 7. For the large margin classifier θ̂S , we have

1

 (1 − )n + ()n 0 <  ≤


2
h
i 
1
P R(θ̂S ) >  = ( 1 )n−1
<  < 1 (29)


2
2



0
 = 1.
The proof for Lemma 7 is in the appendix.
Now we show that R(θ̂S ) is O(n−1 ).
Theorem 8. Let S be an n-item iid sample drawn from pZ .
Then ∀δ ∈ (0, 1) and ∀n ≥ 2,


δ
P R(θ̂S ) >
> 1 − δ.
(30)
n

Now we work out the risk of the most symmetric teacher
Bms . To bound the risk of Bms we need the following key
lemma, which shows that the sample complexity with the
teacher is O(−1/2 ).
Lemma 9. Let n = 4m, where m is an integer. Let S be
an n-item iid sample drawn from pZ . ∀ > 0, ∀δ ∈ (0, 1),
3
1
3 12
∃M(, δ) = max{ ln 3e
4−1 ln δi, (  ln δ ) } such that ∀m ≥
h
M(, δ), P R(θ̂Bms (S) ) ≤  > 1 − δ.
Proof. We give a proof sketch and the details are in the
appendix. Let S1 = {x | (x, 1) ∈ S} and S2 = {x |
(x, −1) ∈ S} respectively. Then we have |S1 | + |S2 | = 4m.
Define event E1 : {|S1 | ≥ m ∧ |S2 | ≥ m}. Given that
3
δ
m ≥ ln 3e
4−1 ln δ , one can show P (E1 ) > 1 − 3 . Since
|S1 | + |S2 | = 4m, either |S1 | ≥ 2m or |S2 | ≥ 2m. Without
loss of generality we assume |S1 | ≥ 2m. We then divide the
interval [0, 1] equally into N = bm2 (ln 3δ )−1 c segments.
The length of each segment is N1 = O( m12 ) as Figure 2
shows.
1
-1

2

3

0

N
1

Figure 2: segments
Let No be the number of segments that are occupied by the
points in S1 . Note that No is a random variable. Let E2 be
the event that No ≥ m. Then one can show P (E2 ) > 1 − 3δ .
By union bound, we have P (E1 , E2 ) > 1 − 2δ
3 . Let
E3 be the following event: there exist a point x2 in S2
such that −x2 , the flipped point, lies in the same segment as some point x1 in S1 . One can show that P (E3 |
E1 , E2 ) > 1− 3δ . Thus P (E3 ) ≥ P (E1 , E2 , E3 ) = P (E3 |
E1 , E2 )P (E1 , E2 ) ≥ (1 − 3δ )(1 − 2δ
3 ) > 1 − δ. If E3 happens, then |x1 + x2 | = |x1 − (−x2 )| ≤ N1 . Note that
2
1
m ≥ ( 1 ln 3δ ) 2 and N = bm2 (ln 3δ )−1 c ≥ m2 (ln 3δ )−1 ,
thus N1 ≤ m22 ln 3δ ≤ 2. Therefore R(θ̂Bms (S) ) =
+
2
| s− +s
| ≤ | x1 +x
| ≤ .
2
2
Rewriting  in Lemma 9 as a function of n, we have the
following theorem.

(31)

Theorem 10. Let S be an n-item iid sample dawn from pZ ,
3
then ∃N1 (δ) = ln12e
4−1 ln δ such that ∀n ≥ N1 ,


16 3
P R(θ̂Bms (S) ) ≤ 2 ln
> 1 − δ.
(33)
n
δ

Note that n ≥ 2, thus nδ ≤ 21 . Let  = nδ in (31) we have


δ
δ
P R(θ̂S ) >
> 1 − n = 1 − δ.
(32)
n
n

3
Proof. Note that if n ≥ N1 (δ) = ln12e
4−1 ln δ , then m =
n
3e
3
4 ≥ ln 4−1 ln δ , thus the minimum  that satisfies m ≥
1
M(, δ) is m2 ln 3δ = n162 ln 3δ .

Proof. According to Lemma 7, for  ≤ 12 , we have
h
i
P R(θ̂S ) >  > (1 − )n > 1 − n.

Teacher Improves Learning by Selecting a Training Subset

Now we can conclude super teaching:

6

δ
to Theorem 10,
Proof of Theorem 5. According
h
i ∃N1 ( 2 )
such that ∀n ≥ N1 , P R(θ̂Bms (S) ) ≤ n162 ln 6δ > 1 − 2δ .
Note
h that N1 ≥ i2, thus according to Theorem 8, ∀n ≥ N1 ,
δ
32
P R(θ̂S ) > 2n
> 1 − 2δ . Let cn = nδ
ln 6δ and N2 (δ) =

We now apply the framework in section 5 to logistic regression and ridge regression, and show that the solver indeed
selects a super-teaching subset that is far better than the
original training set S.

32
δ

ln 6δ so that cN2 = 1. Let N (δ) = max{N1 (δ), N2 (δ)}.
By union bound, ∀n ≥ N , with probability at least 1 − δ,
δ
16
6
we have both R(
h θ̂S ) > 2n and R(θ̂Bms
i (S) ) ≤ n2 ln δ ,
which gives P R(θ̂Bms (S) ) ≤ cn R(θ̂S ) > 1 − δ, where
cn ≤ cN2 = 1.

5

An MINLP Algorithm for Super Teaching

6.1

Simulations

Teaching Logistic Regression Alr

Let X = Rd , Θ = Rd , θ∗ = ( √1d , ..., √1d ), pZ (x) =


N (0, I). Let pZ (y | x) = 1 x> θ∗ > 0 , which is deterministic given x. Logistic regression estimates θ̂S =
˜ i ) = log(1 +
Alr (S) with (34), where λ = 0.1 and `(z
>
exp(−yi xi θ)). In contrast, The teacher’sh risk
h is defined
ii
to be the expected 0-1 loss: R(θ̂) = EpZ 1 θ̂(x) 6= y ,

Although the problem of proving super teaching ratios for a
specific learner is interesting, we now focus on an algorithm
to find a super teaching set for general learners given a
training set S. That is, we find a subset B(S) ⊂ S so that
R(θ̂B(S) ) < R(θ̂S ). We start by formulating super teaching
as a subset selection problem. To this end, we introduce
binary indicator variables b1 , . . . , bn where bi = 1 means
zi ∈ S is included in the subset. We consider learners A
that can be defined via convex empirical risk minimization:
n
X

˜ zi ) + λ kθk2 .
A(S) , argminθ∈Θ
`(θ,
2
i=1

We formulate super teaching as the following bilevel combinatorial optimization problem:
R(θ̂)

min

arccos(

b∈{0,1}n ,θ̂∈Rd

s.t.

λθ̂ −

θ̂> θ∗

)/π
||θ̂|| · ||θ∗ ||
n
X
bi yi xi
i=1

(34)

For simplicity we assume there is a unique global minimum
which is returned by argmin. Note that we use `˜ in (34) to
denote the (surrogate) convex loss used by A in performing
empirical risk minimization. For example, `˜ may be the negative log likelihood for logistic regression. `˜ is potentially
different from ` (e.g. the 0-1 loss) used by the teacher to
define the teaching risk R in (1).

min

where θ̂(x) is the label of x predicted by θ̂. Since pZ is symmetric about the origin, the risk can be rewritten in terms of
θ̂ > θ ∗
the angle between θ̂ and θ∗ : R(θ̂) = arccos( ||θ̂||·||θ
)/π.
∗ ||
Instantiating (37) we have

1 + exp(yi x>
i θ̂)

(38)
= 0.

We run experiments to study the effectiveness and scalability of the NEOS MINLP solver on (38), specifically with
respect to the training set size n = |S| and dimension d.
In the first set of experiments we fix d = 2 and vary n =
16, 64, 256 and 1024. For each n we run 10 trials. In each
trial we draw an n-item iid sample S ∼ pZ and call the
solver on (38). The solver’s solution to b1 . . . bn indicates
the super teaching set B(S). We then compute an empirical
version of the super teaching ratio:
ĉn = R(θ̂B(S) )/R(θ̂S ).

(35)

b∈{0,1}n ,θ̂∈Θ

s.t.

θ̂ = argminθ∈Θ

n
X
i=1

˜ zi ) +
bi `(θ,

λ
kθk2 . (36)
2

Under mild conditions, we may replace the lower level optimization problem (i.e. the machine learning problem (36))
by its first order optimality (KKT) conditions:
min

R(θ̂)

(37)

b∈{0,1}n ,θ̂∈Θ

s.t.

n
X

˜ θ̂, zi ) + λθ̂ = 0.
bi ∇θ `(

i=1

This reduces the bilevel problem but the constraint is nonlinear in general, leading to a mixed-integer nonlinear program
(MINLP), for which effective solvers exist. We use the
MINLP solver in NEOS [15].

n = |S|
16
64
256
1024

Logistic Regression
ĉn |B(S)|/n time (s)
8.5e-4
0.50
3.4e-1
1.3e-3
0.69
3.5e+0
6.3e-3
0.67
6.0e+1
1.3e-2
0.86
1.4e+3

Ridge Regression
ĉn |B(S)|/n time (s)
7.8e-3
0.50
6.3e-1
7.5e-3
0.70
5.8e+0
5.6e-3
0.84
1.4e+2
4.1e-3
0.92
3.3e+3

Table 1: Super teaching as n changes.
In the left half of Table 1 we report the median of the following quantities over 10 trials: ĉn , the fraction of the training
items selected for super teaching |B(S)|/n, and the NEOS
server running time.
The main result is that ĉn  1 for all n, which means the
solver indeed selects a super-teaching set B(S) that is far

Yuzhe Ma, Robert Nowak, Philippe Rigollet∗ , Xuezhou Zhang, Xiaojin Zhu

d
2
4
8
16
32

Logistic Regression
ĉn |B(S)|/n time (s)
3.1e-3
0.67
5.4e-1
2.4e-3
0.44
8.5e+1
1.8e-1
0.39
4.1e+0
5.6e-1
0.42
5.1e+0
8.2e-1
0.58
1.0e+1

Ridge Regression
ĉn |B(S)|/n time (s)
3.3e-3
0.55
6.6e+0
7.2e-3
0.53
5.8e+1
1.5e-1
0.47
6.0e+0
4.3e-1
0.59
9.3e+0
6.4e-1
0.86
3.0e+0

3

3

0

0

-3
-3

Table 2: Super teaching as d changes.

0

(a) logistic regression

better than the original iid training set S. Therefore, MINLP
is a valid algorithm for finding a super teaching set.
Second, we note that the solver tends to select a large subset
since the median |B(S)|/n ≥ 1/2. This is interesting as
it is known that when S is dense, one can select extremely
sparse super teaching sets, as small as a few items, to teach
effectively [28]. Understanding the different regimes remains future work.
Finally, the running time grows fast with n. For example,
when n = 1024 it takes around half an hour to solve (38).
Future work needs to address this bottleneck in applying
MINLP to large problems.
In the second set of experiments we fix n = 32 and vary
d = 2, 4, 8, 16, 32. The left half of Table 2 shows the results. The empirical teaching ratio ĉn is still below 1 in all
cases, showing super teaching. But as the dimension of the
problem increases ĉn deteriorates toward 1. Nonetheless,
even when d = n we still see a median super teaching ratio
of 0.82; the corresponding super teaching set B(S) has only
58% training items than the dimension. It is interesting that
the MINLP algorithm intentionally created a “high dimensional” learning problem (as in higher dimension d than
selected training items |B(S)|) to achieve better teaching,
knowing that the learner Alr is regularized. The running
time does not change dramatically.
6.2

Teaching Ridge Regression Arr

Let X = Rd , Θ = Rd , θ∗ = ( √1d , ..., √1d ), pZ (x) =
N (0, I), pZ (y | x) = N (y; x> θ∗ , 0.1). Let the teaching risk be the parameter difference: R(θ̂) = kθ̂ − θ∗ k.
Given a sample S with n iid items drawn from pZ , ridge
regression estimates θ̂S = Arr (S) with λ = 0.1 and
˜ i ) = (x> θ̂ − yi )2 . The corresponding MINLP is:
`(z
i
||θ̂ − θ∗ ||

min

(39)

b∈{0,1}n ,θ̂∈Rd

s.t.

λθ̂ + 2

n
X

bi (x>
i θ̂ − yi )xi = 0.

i=1

We run the same set of experiments. Tables 1 and 2 show the
results, which are qualitatively similar to teaching logistic
regression. Again, we see the empirical super teaching ratio
ĉn  1, indicating the presence of super teaching.

3

-3
-3

0

3

(b) ridge regression

Figure 3: Typical trials from the MINLP algorithm

Finally, Figure 3 visualizes one typical trial each for teaching logistic regression and ridge regression. S consists of
both dark and light points, while the dark ones representing B(S) optimized by MINLP. The dashed line shows
θ̂S , while the solid lines shows θ̂B(S) . The ground truth
(x1 + x2 = 0 in logistic regression, y = x in ridge regression) essentially overlaps with the solid lines. Specifically,
the super taught models θ̂B(S) have negligible risks of 2.5e4 and 3.3e-3, whereas models θ̂S trained from the whole iid
sample S incur much larger risks of 0.03 and 0.16, respectively.

7

Related Work

There has been several research threads in different communities aimed at reducing a data set while maintaining its
utility. The first thread is training set reduction [19, 43, 42],
which during training time prunes items in S in an attempt
to improve the learned model. The second thread is coresets [22, 6], a summary of S such that models learned on
the summary are provably competitive with models learned
on the full data set S. But as they do not know the target
model pZ or θ∗ , these methods cannot truly achieve super
teaching. The third thread is curriculum learning [11] which
showed that smart initialization is useful for nonconvex optimization. In contrast, our teacher can directly encode the
true model and therefore obtain faster rates. The final thread
is sample compression [17], where a compression function
chooses a subset T ⊂ S and a reconstruction function to
form a hypothesis. Our present work has some similarity
with compression, which allows increased accuracy since
compression bounds can be used as regularization [26].
The theoretical study of machine teaching has focused on
the teaching dimension, i.e. the minimum training set size
needed to exactly teach a target concept θ∗ [20, 38, 46, 18,
29, 45, 16, 44, 48, 9, 3, 4, 21, 31, 8, 7, 25, 5, 36, 23, 10].
Most of the prior work assumed a synthetic teaching setting
where S is the whole item space, which is often unrealistic.
Liu et al. considered approximate teaching in the finite
S setting [30], though their analysis focused on a specific
SGD learner. Our super teaching setting applies to arbitrary

Teacher Improves Learning by Selecting a Training Subset

learners, and we allow approximate teaching – namely we
do not require the teacher to teach exactly the target model,
which is infeasible in our pool-based teaching setting with a
finite S.
Machine teaching applications include education [14, 33,
39, 27, 13, 34], computer security [2, 1, 32], and interactive
machine learning [40, 12, 24]. By establishing the existence
of super-teaching, the present paper can guide the process of
finding a more effective training set for these applications.

8

lc
If θ∗ = ∅, then trivially θ̂B(S)
= θ̂Slc = ∅.

Now assume θ∗ 6= ∅. If ∃(x, 1) ∈ B(S), let [a1 , b1 ] =
lc
θ̂B(S)
. Note that θ̂Slc 6= ∅ because B(S) ⊆ S and thus S has
at least one positive point. Let θ̂Slc = [a2 , b2 ]. Now a1 =
min{x | (x, 1) ∈ B(S)} ≥ min{x | (x, 1) ∈ S} = a2 ,
and b1 = max{x | (x, 1) ∈ B(S)} ≤ max{x | (x, 1) ∈
lc
S} = b2 . Thus we have θ̂B(S)
⊆ θ̂Slc . If @(x, 1) ∈ B(S),
lc
lc
θ̂B(S)
= ∅ and θ̂B(S)
⊆ θ̂Slc is always true.
lc
Thus θ̂B(S)
⊆ θ̂Slc ⊆ θ∗ for any B and any S.

Discussions and Conclusion

gc
The proof for Agc is similar by showing θ∗ ⊆ θ̂Sgc ⊆ θ̂B(S)
.

We presented super-teaching: when the teacher already
knows the target model, she can often choose from a given
training set a smaller subset that trains a learner better. We
proved this for two learners, and provided an empirical algorithm based on mixed integer nonlinear programming to
find a super teaching set.
However, much needs to be done on the theory of super
teaching. We give two counterexamples to illustrate that not
all learners are super-teachable.
Example 1 (MLE of interval). Let X = [0, θ∗ ], where θ∗ ∈
R+ . pZ (x) = U (X). Given a n-item training set S, the
MLE for θ∗ is θ̂S = Aint (S) = maxi=1:n xi . The risk is
defined as R(θ̂S ) = |θ̂S − θ∗ |. We show Aint is not superteachable. θ̂B(S) = maxxi ∈B(S) xi ≤ maxxi ∈S xi = θ̂S .
Since θ̂S ≤ θ∗ , R(θ̂B(S) ) = |θ̂B(S) − θ∗ | ≥ |θ̂S − θ∗ | =
R(θ̂S ).
We can generalize this to a classification setting, and show
that neither the least nor the greatest consistent hypothesis
is not super-teachable:
Example 2 (Consistent learners). Let X = [xmin , xmax ] ⊂
Z be an interval over the integer grid. The hypothesis
space is Θ = {[a, b] ⊆ X : y = 1 in [a, b] and −1 outside}.
θ∗ = [a∗ , b∗ ] ∈ Θ. pZ is uniform on X and noiseless y
labeled according to θ∗ . The risk R(θ̂S ) is the size of the
symmetric difference between the two intervals θ̂S and θ∗ ,
normalized by xmax −xmin . Given a sample S, the least consistent learner Alc learns the tightest interval over positive

items in S: θ̂Slc = Alc (S) , mini=1:n xi , maxi=1:n xi .
yi =1

yi =1

θ̂Slc

= ∅ if S does not contain positive items. The greatest
consistent learner Agc extends the hypothesis interval in
both directions as much as possible before hitting negative
points in S. If S has no positive we define θ̂Sgc = ∅, too.
Proposition 11. Neither Alc nor Agc is super-teachable.
Proof. We first show Alc is not super-teachable. Note that
Alc learns the tightest interval consistent with S, thus we
lc
always have θ̂Slc ⊆ θ∗ . Now we show that θ̂B(S)
⊆ θ̂Slc is
lc
always true so that R(θ̂Slc ) ≤ R(θ̂B(S)
) follows.

This leads to an open question: which family of learners are
super teachable? We offer a conjecture here: we speculate
that MLEs (and the derived MAP estimates or regularized
empirical risk minimizers) which satisfy the asymptotic normality conditions [41] are super teachable. This conjecture
is motivated by its similarity to the proof in section 3. Also
note that the two counterexamples are classic examples of
MLE that do not satisfy the asymptotic normality conditions.
Another open question concerns the optimal super-teaching
subset size k for a given training set of size n. For example,
our result on teaching the MLE of Gaussian mean indicates
that the rate improves as k grows. However, our analysis
only applies to a fixed k. Further research is needed to
identify the optimal k.
Acknowledgments: R.N. acknowledges support by NSF
IIS-1447449 and CCF-1740707. P.R. is supported in part by
grants NSF DMS-1712596, NSF DMS-TRIPODS-1740751,
DARPA W911NF-16-1-0551, ONR N00014-17-1-2147 and
a grant from the MIT NEC Corporation. X.Z. is supported in
part by NSF CCF-1704117, IIS-1623605, CMMI-1561512,
DGE-1545481, and CCF-1423237.

References
[1] S. Alfeld, X. Zhu, and P. Barford. Data poisoning
attacks against autoregressive models. AAAI, 2016.
[2] S. Alfeld, X. Zhu, and P. Barford. Explicit defense actions against test-set attacks. In The Thirty-First AAAI
Conference on Artificial Intelligence (AAAI), 2017.
[3] D. Angluin. Queries revisited. Theoretical Computer
Science, 313(2):175–194, 2004.
[4] D. Angluin and M. Krikis. Teachers, learners and
black boxes. COLT, 1997.
[5] D. Angluin and M. Krikis. Learning from different
teachers. Machine Learning, 51(2):137–163, 2003.

Yuzhe Ma, Robert Nowak, Philippe Rigollet∗ , Xuezhou Zhang, Xiaojin Zhu

[6] O. Bachem, M. Lucic, and A. Krause. Practical Coreset Constructions for Machine Learning. ArXiv eprints, Mar. 2017.

[20] S. Goldman and M. Kearns. On the complexity of
teaching. Journal of Computer and Systems Sciences,
50(1):20–31, 1995.

[7] F. J. Balbach. Measuring teachability using variants of
the teaching dimension. Theor. Comput. Sci., 397(13):94–113, 2008.

[21] S. A. Goldman and H. D. Mathias. Teaching a smarter
learner. Journal of Computer and Systems Sciences,
52(2):255–267, 1996.

[8] F. J. Balbach and T. Zeugmann. Teaching randomized
learners. COLT, pages 229–243, 2006.
[9] F. J. Balbach and T. Zeugmann. Recent developments
in algorithmic teaching. In Proceedings of the 3rd
International Conference on Language and Automata
Theory and Applications, pages 1–18, 2009.
[10] S. Ben-David and N. Eiron. Self-directed learning
and its relation to the VC-dimension and to teacherdirected learning. Machine Learning, 33(1):87–104,
1998.
[11] Y. Bengio, J. Louradour, R. Collobert, and J. Weston.
Curriculum learning. In L. Bottou and M. Littman,
editors, Proceedings of the 26th International Conference on Machine Learning, pages 41–48, Montreal,
June 2009. Omnipress.
[12] M. Cakmak and M. Lopes. Algorithmic and human
teaching of sequential decision tasks. In AAAI, 2012.
[13] M. Cakmak and A. Thomaz. Mixed-initiative active
learning. ICML Workshop on Combining Learning
Strategies to Reduce Label Cost, 2011.
[14] B. Clement, P.-Y. Oudeyer, and M. Lopes. A comparison of automatic teaching strategies for heterogeneous student populations. In Educational Data
Mining (EDM), 2016.
[15] J. Czyzyk, M. P. Mesnier, and J. J. Moré. The NEOS
server. IEEE Computational Science and Engineering,
5(3):68–75, 1998.
[16] T. Doliwa, G. Fan, H. U. Simon, and S. Zilles. Recursive teaching dimension, VC-dimension and sample
compression. Journal of Machine Learning Research,
15:3107–3131, 2014.
[17] S. Floyd and M. Warmuth. Sample compression, learnability, and the Vapnik-Chervonenkis dimension. Machine learning, 21(3):269–304, 1995.
[18] Z. Gao, C. Ries, H. U. Simon, and S. Zilles.
Preference-based teaching. Journal of Machine Learning Research, 18(31):1–32, 2017.
[19] S. Garcia, J. Derrac, J. Cano, and F. Herrera. Prototype selection for nearest neighbor classification:
Taxonomy and empirical study. IEEE Transactions on
Pattern Analysis and Machine Intelligence, 34(3):417–
435, 2012.

[22] S. Har-Peled. Geometric approximation algorithms,
volume 173. American mathematical society Boston,
2011.
[23] T. Hegedüs. Generalized teaching dimensions and the
query complexity of learning. In Proceedings of the
eighth Annual Conference on Computational Learning
Theory (COLT), pages 108–117, 1995.
[24] F. Khan, X. Zhu, and B. Mutlu. How do humans teach:
On curriculum learning and teaching dimension. NIPS,
2011.
[25] H. Kobayashi and A. Shinohara. Complexity of teaching by a restricted number of examples. COLT, pages
293–302, 2009.
[26] A. Kontorovich, S. Sabato, and R. Weiss. Nearestneighbor sample compression: Efficiency, consistency,
infinite dimensions. arXiv preprint arXiv:1705.08184,
2017.
[27] R. Lindsey, M. Mozer, W. J. Huggins, and H. Pashler.
Optimizing instructional policies. In C. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Weinberger,
editors, Advances in Neural Information Processing
Systems 26, pages 2778–2786. 2013.
[28] J. Liu and X. Zhu. The teaching dimension of linear learners. Journal of Machine Learning Research,
17(162):1–25, 2016.
[29] J. Liu, X. Zhu, and H. G. Ohannessian. The teaching
dimension of linear learners. In The 33rd International
Conference on Machine Learning (ICML), 2016.
[30] W. Liu, B. Dai, J. M. Rehg, and L. Song. Iterative
machine teaching. In ICML, 2017.
[31] H. D. Mathias. A model of interactive teaching. J.
Comput. Syst. Sci., 54(3):487–501, 1997.
[32] S. Mei and X. Zhu. Using machine teaching to identify
optimal training-set attacks on machine learners. AAAI,
2015.
[33] K. Patil, X. Zhu, L. Kopec, and B. C. Love. Optimal teaching for limited-capacity human learners.
Advances in Neural Information Processing Systems
(NIPS), 2014.

Teacher Improves Learning by Selecting a Training Subset

[34] A. N. Rafferty, E. Brunskill, T. L. Griffiths, and
P. Shafto. Faster teaching by POMDP planning. In
Proceedings of the 15th International Conference on
Artificial Intelligence in Education, AIED’11, pages
280–287, Berlin, Heidelberg, 2011. Springer-Verlag.
[35] M. T. Ribeiro, S. Singh, and C. Guestrin. Why should i
trust you?: Explaining the predictions of any classifier.
In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data
Mining, pages 1135–1144. ACM, 2016.
[36] R. L. Rivest and Y. L. Yin. Being taught can be faster
than asking questions. COLT, 1995.
[37] S. Shalev-Shwartz and S. Ben-David. Understanding Machine Learning: From Theory to Algorithms.
Cambridge University Press, New York, NY, USA,
2014.
[38] A. Shinohara and S. Miyano. Teachability in computational learning. New Generation Computing,
8(4):337—-348, 1991.
[39] A. Singla, I. Bogunovic, G. Bartok, A. Karbasi, and
A. Krause. Near-optimally teaching the crowd to classify. In ICML, pages 154–162, 2014.
[40] J. Suh, X. Zhu, and S. Amershi. The label complexity
of mixed-initiative classifier training. International
Conference on Machine Learning (ICML), 2016.
[41] H. White. Maximum likelihood estimation of misspecified models. Econometrica: Journal of the Econometric Society, pages 1–25, 1982.
[42] D. R. Wilson and T. R. Martinez. Reduction techniques for instance-based learning algorithms. Machine Learning, 38(3):257–286, 2000.
[43] X. Zeng and X.-w. Chen. SMO-based pruning methods
for sparse least squares support vector machines. IEEE
transactions on Neural Networks, 16(6):1541–1546,
2005.
[44] X. Zhu. Machine teaching for bayesian learners in the
exponential family. In Advances in Neural Information
Processing Systems (NIPS), pages 1905–1913, 2013.
[45] X. Zhu. Machine teaching: an inverse problem to
machine learning and an approach toward optimal education. AAAI, 2015.
[46] X. Zhu, J. Liu, and M. Lopes. No learner left behind:
On the complexity of teaching multiple learners simultaneously. In The 26th International Joint Conference
on Artificial Intelligence (IJCAI), 2017.
[47] X. Zhu, A. Singla, S. Zilles, and A. N. Rafferty. An
Overview of Machine Teaching. ArXiv e-prints, Jan.
2018. https://arxiv.org/abs/1801.05927.

[48] S. Zilles, S. Lange, R. Holte, and M. Zinkevich. Models of cooperative teaching and learning. Journal of
Machine Learning Research, 12:349–384, 2011.

Yuzhe Ma, Robert Nowak, Philippe Rigollet∗ , Xuezhou Zhang, Xiaojin Zhu

Supplemental Material
Lemma 7. For the large margin classifier θ̂S , we have


n
n

 (1 − ) + ()

h
i 
P R(θ̂S ) >  = ( 1 )n−1


2



0

0<≤

1
2

1
<<1
2
 = 1.

(29)

h
i
Proof. The risk is R(θ̂S ) = |θ̂S |. Define event E : {∃(x, −1) ∈ S ∧ ∃(x, +1) ∈ S}. P |θ̂S | ≤  can be decomposed into
two components depending on if E happens as (40) shows.
h
i
h
i
h
i
P |θ̂S | ≤  = P |θ̂S | ≤ , E + P |θ̂S | ≤ , E c .
(40)
h
i
h
i
h
i
P |θ̂S | ≤ , E c = P |θ̂S | ≤  | E c P [E c ]. Note that P [E c ] = ( 21 )n−1 , P |θ̂S | ≤  | E c is 0 if  < 1 and 1 if  = 1
because θ̂S = ±1 always holds given E c happens. Thus,
h

i

P |θ̂S | ≤ , E c =


0

if  < 1

 ( 1 )n−1
2

if  = 1.

(41)

h
i
Now we compute P |θ̂S | ≤ , E . Let n+ be the number of positive points in S. Define Ei : {n+ = i}. Note Ei ∩ Ej = ∅
if i 6= j and E = ∪n−1
i=1 Ei , thus
h
i n−1
i n−1
i
X h
X h
P |θ̂S | ≤ , E =
P |θ̂S | ≤ , Ei =
P |θ̂S | ≤  | Ei P [Ei ] .
i=1

(42)

i=1

h
i
h
i
+
P [Ei ] = Cin ( 21 )n . Note that P |θ̂S | ≤  | Ei = P | x− +x
| ≤  | Ei . To compute it, we first compute F−x− ,x+ (1 , 2 |
2
Ei ) = P [−x− ≤ 1 , x+ ≤ 2 | Ei ]. Given Ei happens, P [−x− ≤ 1 | Ei ] = 1 − (1 − 1 )n−i and P [x+ ≤ 2 | Ei ] =
1 − (1 − 2 )i . Also since −x− ≤ 1 and x+ ≤ 2 are independent given Ei happens, thus
F−x− ,x+ (1 , 2 | Ei ) = P [−x− ≤ 1 , x+ ≤ 2 | Ei ] = [1 − (1 − 1 )n−i ][1 − (1 − 2 )i ].

(43)

Take the derivative of F gives
f−x− ,x+ (1 , 2 | Ei ) = i(n − i)(1 − 1 )n−i−1 (1 − 2 )i−1 .

(44)

Note thath|θ̂S | ≤  ⇔ | i− x1 − x2 | ≤ 2. Therefore, we integrate f−x− ,x+ (1 , 2 | Ei ) over the region |1 − 2 | ≤ 2 to
obtain P |θ̂S | ≤  | Ei . However, note that 0 ≤ 1 , 2 ≤ 1, thus for  > 12 , the region |1 − 2 | ≤ 2 becomes the whole
h
i P
n−1
[0, 1] × [0, 1] and the integration is 1. Then (42) becomes P |θ̂S | ≤ , E = i=1 P [Ei ] = P [E] = 1 − ( 12 )n−1 . For
 ≤ 12 , by (42) we have
h

i

P |θ̂S | ≤ , E =

n−1
X
i=1
n−1
X

Z
P [Ei ]

i(n − i)(1 − 1 )n−i−1 (1 − 2 )i−1 d2 d1

|1 −2 |≤2

Z
1
Cin ( )n
i(n − i)(1 − 1 )n−i−1 (1 − 2 )i−1 d2 d1
2
|1 −2 |≤2
i=1
Z
n−1
X
1
= ( )n
Cin i(n − i)(1 − 1 )n−i−1 (1 − 2 )i−1 d2 d1 .
2
|1 −2 |≤2 i=1
=

(45)

Teacher Improves Learning by Selecting a Training Subset
n−2
Note that Cin i(n − i) = n(n − 1)Ci−1
, (45) becomes

Z
n−1
h
i
X
1
n−2
P |θ̂S | ≤ , E = n(n − 1)( )n
Ci−1
(1 − 1 )n−i−1 (1 − 2 )i−1 d2 d1
2
|1 −2 |≤2 i=1
Z
n−2
X
1
Cin−2 (1 − 1 )n−2−i (1 − 2 )i d2 d1
= n(n − 1)( )n
2
|1 −2 |≤2 i=0
Z
1 n
(2 − 1 − 2 )n−2 d2 d1
= n(n − 1)( )
2
|1 −2 |≤2
Z
Z
1 n
n−2
= n(n − 1)( ) [
(2 − 1 − 2 )
d2 d1 −
(2 − 1 − 2 )n−2 d2 d1 ].
2
[0,1]×[0,1]
|1 −2 |>2

(46)

Now we compute the two integration in (46)
Z
(2 − 1 − 2 )

n−2

Z1
d2 d1 =

[0,1]×[0,1]

Z1
=

1
(2 − 1 − 2 )n−1 |10 ]d1
n−1

[−
0

(47)

1
1
1
2n − 2
[(2 − 1 )n−1 − (1 − 1 )n−1 ]d1 = [−
(2 − )n +
(1 − 1 )n ] |10 =
.
n−1
n(n − 1)
n(n − 1)
n(n − 1)

0

For the second integration, note that it can decomposed as
Z

(2 − 1 − 2 )n−2 d2 d1 =

|1 −2 |>2

1−2
Z

0

Z1

(2 − 1 − 2 )n−2 d2 d1 +

1 +2

1 −2
Z1 Z
(2 − 1 − 2 )n−2 d2 d1 .

2

(48)

0

Since the two sub-integration’s are identical because the two sub regions are symmetric. We only show the computation for
the first.
1−2
1−2
Z
Z1
Z
1
n−2
(2 − 1 − 2 )
d2 d1 =
[−
(2 − 1 − 2 )n−1 |11 +2 ]d1
n−1
0

1 +2
1−2
Z

=

[−

0

1
2n−1
(1 − 1 )n−1 +
(1 − 1 − )n−1 ]d1
n−1
n−1

(49)

0

2n−1
1
(1 − 1 )n −
(1 − 1 − )n ] |1−2
0
n(n − 1)
n(n − 1)
2n−1
1
=
[n + (1 − )n ] −
.
n(n − 1)
n(n − 1)

=[

Thus we have
Z

n−2

(2 − 1 − 2 )

1−2
Z

Z1

d2 d1 = 2

|1 −2 |>2

0

(2 − 1 − 2 )n−2 d2 d1

1 +2

(50)

2n
2
=
[n + (1 − )n ] −
.
n(n − 1)
n(n − 1)
Combine (47) and (50), we can compute (46) as follows.
h
i
1
2n − 2
2n
2
P |θ̂S | ≤ , E = = n(n − 1)( )n [
−
(n + (1 − )n ) +
]
2 n(n − 1) n(n − 1)
n(n − 1)
2n − 2
1
=
− n − (1 − )n + ( )n−1
2n
2
= 1 − n − (1 − )n

(51)

Yuzhe Ma, Robert Nowak, Philippe Rigollet∗ , Xuezhou Zhang, Xiaojin Zhu

Therefore we have


n
n
if  ≤ 12
h
i  1 −  − (1 − )
P |θ̂S | ≤ , E =
 1 − ( 1 )n−1
if 21 <  ≤ 1.
2
Now combine (41) and (52) we have

n
n
if  ≤ 21
 1 −  − (1 − )

h
i 
1
P |θ̂S | ≤  = 1 − ( )n−1
if 21 <  < 1

2


1
if  = 1.

(52)

(53)

which is equivalent to (29).
Lemma 9. Let n = 4m, where m is an integer. Let S be an n-item
h iid sample drawn
i from pZ . ∀ > 0, ∀δ ∈ (0, 1),
3e
3
1
3 12
∃M(, δ) = max{ ln 4−1 ln δ , (  ln δ ) } such that ∀m ≥ M(, δ), P R(θ̂Bms (S) ) ≤  > 1 − δ.
Proof. Let S1 = {x | (x, 1) ∈ S} and S2 = {x | (x, −1) ∈ S} respectively. Then we have |S1 | + |S2 | = 4m. Define
event E1 : {|S1 | ≥ m ∧ |S2 | ≥ m}. Then we have
P [E1 ] = 1 − 2

m−1
X
i=0

1
Ci4m ( )4m .
2

(54)

where we rule out all possible sequences of 4m points which lead to |S1 | < m or |S2 | < m. By standard result [37] (Lemma
Pd
d
A.5) k=0 Ckm ≤ ( em
d ) , we have
P [E1 ] ≥ 1 − 2(

4em m−1 1 4m
1 em−1
m m−1
1 e
e
)
( ) =1−
(
)
≥ 1 − ( )m ≥ 1 − ( )m
m
m−1
2
2 4
m−1
2 4
4

(55)

1
3
where the 2nd-to-last inequality follows from the fact that e ≥ (1 + m−1
)m−1 . Note that by definition m ≥ ln 3e
4−1 ln δ >
1
3
e m
δ
δ
ln 4−1 ln δ , thus ( 4 ) < 3 and P [E1 ] > 1− 3 . Since |S1 |+|S2 | = 4m, then either |S1 | ≥ 2m or |S2 | ≥ 2m. Without loss
of generality we assume |S1 | ≥ 2m. We then divide the interval [0, 1] equally into N = bm2 (ln 3δ )−1 c segments. The length
3
3
of each segment is N1 = O( m12 ) as Figure 4 shows. Note that m ≥ ln 3e
4−1 ln δ > 3e ln δ , thus N ≥ b3emc > 2em > m.
1
-1

2

3

0

N
1

Figure 4: segments
Let No be the number of segments that are occupied by the points in S1 . Note that No is a random variable. Let E2
be the event that No ≥ m. Now we lower bound P [E2 ]. This is a variant of the coupon collector’s problem: there are
N distinct coupons, and in |S1 | trials we want to collect at least m distinct coupons. Note that P [E2 ] = 1 − P [E2c ] =
Pm−1
1 − i=1 P [No = i]. Let Ti be the number of all possible coupon sequences of S1 such that S1 occupies exactly i
segments (i.e. distinct coupons). We have Cin ways of choosing i segments among a total of N . Also, for each choice of i
segments, the number of all possible coupon sequences of S1 such that S1 fully occupies those i segments without empty is
upper bounded by i|S1 | . Thus Ti ≤ Cin i|S1 | and we have
P [No = i] =
Since m ≥

3e
ln 4−1

Ti
i
≤ Cin ( )|S1 | .
N
N |S1 |

(56)

ln 3δ > log2 3δ , |S1 | ≥ 2m, and N > 2em, thus
P [E2c ] =

m−1
X
i=1
m
X

P [No = i] ≤

m−1
X
i=1

Cin (

m−1
X
i |S1 |
m
)
≤
Cin ( )2m
N
N
i=1

m
eN m m 2m
em m
em m
1
δ
<
Cin ( )2m ≤ (
) ( ) =(
) <(
) = ( )m < .
N
m
N
N
2em
2
3
i=0

(57)

Teacher Improves Learning by Selecting a Training Subset

Thus P [E2 ] ≥ 1 − 3δ . Applying union bound, P [E1 , E2 ] ≥ 1 −

2δ
3 .

Let E3 be the following event: there exist a point x2 in S2 such that −x2 , the flipped point, lies in the same segment
as some point x1 in S1 . If E3 happens, then |x1 + x2 | = |x1 − (−x2 )| ≤ N1 . Note that P [E3 ] ≥ P [E1 , E2 , E3 ] =
P [E3 | E1 , E2 ] P [E1 , E2 ]. Now we lower bound P [E3 | E1 , E2 ]. Given E1 and E2 happen, we have |S2 | ≥ m and
No ≥ m. Since N = bm2 (ln 3δ )−1 c ≤ m2 (ln 3δ )−1 , we have
P [E3c | E1 , E2 ] = (1 −

m2
δ
No |S2 |
m
m
)
≤ (1 − )|S2 | ≤ (1 − )m ≤ e− N ≤ .
N
N
N
3

(58)

Thus, P [E3 | E1 , E2 ] = 1 − P [E3c | E1 , E2 ] > 1 − 3δ . P [E3 ] ≥ P [E1 , E2 , E3 ] = P [E3 | E1 , E2 ] P [E1 , E2 ] ≥
1
(1 − 3δ )(1 − 2δ
3 ) > 1 − δ. Thus with probability at least 1 − δ, there exist x2 ∈ S2 and x1 ∈ S1 such that |x1 + x2 | ≤ N .
We now bound
thus N1 ≤ 2.

1
N.

N = bm2 (ln 3δ )−1 c ≥ 12 m2 (ln 3δ )−1 . Therefore

1
N

≤

2
m2

1

ln 3δ . Recall by definition m ≥ ( 1 ln 3δ ) 2 ,

We now have |x1 + x2 | ≤ 2. Finally, since {s− , s+ } selected by teacher Bms is the most symmetric pair, it must satisfy
|s− + s+ | ≤ |x1 + x2 | ≤ 2. Putting together, with probability at least 1 − δ, R(θ̂Bms (S) ) = 12 |s− + s+ | ≤ .

