1

Distribution Matching for Machine Teaching

Xiaofeng Cao and Ivor W. Tsang
Australian Artificial Intelligence Institute, University of Technology Sydney,
Australia.

Email<EMAIL_ADDRESS><EMAIL_ADDRESS>
You may need to know the following questions before reading our manuscript.

Q1: What is machine teaching?
Machine teaching is an inverse problem of machine learning that aims at
steering the student learner towards its target hypothesis, in which the
teacher has already known the student’s learning parameters. In simple terms,
machine teaching can help to find the best training data for student learners
automatically.

Q2: What is our research problem?
Previous machine teaching studies on machine teaching focused on balancing the
teaching risk and cost to find those best teaching examples deriving the
student model. This optimization solver is in general ineffective when the
student learner does not disclose any cue (i.e. a black-box) of the learning
parameters. To supervise such a teaching scenario, this paper presents a
distribution matching-based machine teaching strategy.

Q3: Why it is significant?
Our study will help machine learning to find the best teaching examples on a
black-box setting, then the training examples will be closed-form. In this
paper, we present a distribution matching perspective to resolve this issue
from optimization.

Q4: What is our novelty?
Technically, our strategy can be expressed as a cost-controlled optimization
process that finds the optimal teaching examples without further exploring in
the parameter distribution of the student learner.

Q5: What is the related study?
The most relevant machine learning study to machine teaching is active
learning. Its key assumption is that a student learner who frequently
interacts with a teacher (annotator) would do better or no worse than other
passive student learners who randomly solicit the training examples.
Generally, active learning forwardly updates the current training model into
its target, while the target is always agnostic.

Distribution Matching for Machine Teaching

Xiaofeng Cao and Ivor W. Tsang
Australian Artificial Intelligence Institute, University of Technology Sydney,
Australia.

Email<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Machine teaching is an inverse problem of machine learning that aims at
steering the student learner towards its target hypothesis, in which the
teacher has already known the student’s learning parameters. Previous studies
on machine teaching focused on balancing the teaching risk and cost to find
those best teaching examples deriving the student model. This optimization
solver is in general ineffective when the student learner does not disclose
any cue of the learning parameters. To supervise such a teaching scenario,
this paper presents a distribution matching-based machine teaching strategy.
Specifically, this strategy backwardly and iteratively performs the halving
operation on the teaching cost to find a desired teaching set. Technically,
our strategy can be expressed as a cost-controlled optimization process that
finds the optimal teaching examples without further exploring in the parameter
distribution of the student learner. Then, given any a limited teaching cost,
the training examples will be closed-form. Theoretical analysis and experiment
results demonstrate this strategy.

Keywords: Machine teaching, teaching risk, teaching cost, learning parameters,
surrogate.

##  1 Introduction

Machine learning (Mitchell ., 1997) is the study of artificial intelligent
algorithms that improve automatically through model construction and parameter
experience. Highly informative or representative training examples accelerate
the convergence of the learning model. However, how to control the machine
learning paradigm if there is a teacher who has already known the learning
parameters of the student and wants better training examples to improve its
generalization? This inverse question of machine learning was studied by
machine teaching (X. Zhu ., 2018), which explores the optimal training data
via driving the student learner to its target hypothesis. It has been shown
many promising paradigms ranging from a teaching scheme to a student learner
(W. Liu ., 2018) such as a curriculum to human education system in curriculum
learning (Matiisen ., 2019), an iterative query algorithm to an annotator in
active learning (Dasgupta ., 2019), etc. The key assumption is that the
teacher knows the target parameters of the student model e.g. a specified
hyperplane in SVM classifier, geometric properties of clustering centers, etc.
Typically, a machine teacher interacts with its student learner by exploring
those teaching examples that minimize the _parameter disagreement_
(difference) of the current training model and its desired (Gao ., 2017)
(Shinohara Miyano, 1991).

Figure 1: Label complexity of a student learner. Given an error $\epsilon$,
the passive learner needs $\mathcal{O}(1/\epsilon)$ data, and the active
learner needs $\mathcal{O}({\rm log}{1/\epsilon})$; the machine teacher only
needs two symmetrical examples $a$ and $b$ (black points) around $\theta^{*}$
to minimize the parameter disagreements: $\|\hat{\theta}-\theta^{*}\|$, where
the target parameter $\hat{\theta}$ is denoted by
$\hat{\theta}=\frac{a+b}{2}$, where $\|\cdot\|$ denotes an effective metric
over the parameter space.

In simple terms, machine teaching can help to find the best training data for
student learners automatically. With machine teaching, those teaching examples
can be closed-form to supervise the training model of a student learner. As
far as we know, the most relevant machine learning study to machine teaching
is active learning (Dasgupta ., 2008). Its key assumption is that a student
learner who frequently interacts with a teacher (annotator) would do better or
no worse than other passive student learners who randomly solicit the training
examples. Generally, active learning forwardly updates the current training
model into its target, while the target is always agnostic. We next employ a
threshold classifier to further explain active learning and machine teaching
following the survey of (X. Zhu ., 2018).

Considering an interval [-1,1] with positive and negative labels over a
uniform distribution $\mathop{P}$ (see Figure 1), the parameterized threshold
classifier at $\theta^{*}=0$ stipulates the classification function $f$ for
any $(x,y)\sim\mathop{P}$: $y=f(x)=+1,{\rm s.t.}\ x\geq\theta^{*}$,
$y=f(x)=-1,{\rm s.t.}\ x\leq\theta^{*}$, where $y$ denotes the label of $x$.
Drawing i.i.d. $n$ samples from $\mathop{P}$, a passive (random) learner will
make $n$ times of querying from $f(x)$ that yields a generalization error of
$\|\theta-\theta^{*}\|=\mathcal{O}(1/n)$ due to an average uniform spacing
$1/n$, where $\theta$ yields a passive learner. Given an error $\epsilon$, a
passive learner needs $\mathcal{O}(1/\epsilon)$ data sent to the classifier.
Specifically, the passive learner at least receives 10,000 samples from
$\mathop{P}$ to obtain a desired error 0.0001. For an active learner who
usually employs binary search, the learner halves the remaining interval and
removes the data over it, thereby receives around $\mathcal{O}({\rm
log}{1/\epsilon})$ samples to obtain an error $\epsilon$ because
$\|\theta-\theta^{*}\|=\mathcal{O}(1/2^{n})$. Specifically, the active learner
at least receives 13 samples from $\mathop{P}$ to obtain a desired error
0.0001. However, a machine teacher who knows $\theta^{*}$ only needs two
teaching examples to obtain $\epsilon$: $(\theta^{*}-\epsilon/2,-1)$, and
$(\theta^{*}+\epsilon/2,+1)$. Then, for any student learner, they will easily
achieve better performance using those teaching examples.

From a machine learning perspective, Eq. (1) firstly presents a general
strategy on active learning: optimizing a model parameter $\theta$ with
current training data $D_{0}\subset D$, subsequently updated by queries
$\hat{D}_{q}$:

$\begin{split}&\min_{\theta\in\Theta}R(\theta,D_{0}\cup\hat{D}_{q})+\Omega(\theta),\\\
&{\rm s.t.}\ \hat{D}_{q}\in\operatorname*{argmax}_{D_{q}\subset D\backslash
D_{0}}\Big{|}R(\theta,D_{0})-R(\theta,D_{0}\cup D_{q})\Big{|},\\\ \end{split}$
(1)

where $R(\cdot,\cdot)$ denotes the empirical risk function, $\Omega(\cdot)$
denotes the regularization constraint, $D$ denotes the full training data,
$D_{q}$ denotes the queries from $D\backslash D_{0}$ using active learning
which maximizes the risk disagreement, and $\Theta$ denotes the parameter
space. With the minimizer of the regulated learning risk, model parameter
$\theta$ derives the update on $D_{0}$ via merging $\hat{D}_{q}$.

Given a teacher who has already known the learning parameters, machine
teaching inversely optimizes the training data by estimating parameter
disagreements over the generalization models. X. Zhu (2015) proposed a more
general machine teaching formula based on Eq. (1),

$\begin{split}&\min_{D\subset\mathbb{D}}\mathcal{L}(\hat{\theta},\theta^{*})+\eta\mathcal{M}(D),\\\
&\text{s.t.}\ \hat{\theta}\in\text{arg
min}_{\theta\in\Theta}R(\theta,D)+\Omega(\theta),\\\ \end{split}$ (2)

where $\mathbb{D}$ denotes the complete or whole search space of $D$ that
covers all candidate training subsets, $\mathcal{L}(\cdot,\cdot)$ w.r.t.
parameter disagreement denotes the teaching risk, $\mathcal{M}(\cdot)$ denotes
the teaching cost of the input set, and $\eta$ denotes a balance coefficient.
Typically, $\mathcal{L}(\hat{\theta},\theta^{*})$ can be simply defined as the
indication disagreement $\mathbb{E}_{x\sim
P}\mathbbm{1}_{(\hat{\theta}(x)\neq\theta^{*}(x))}$, where $\mathbbm{1}$
denotes the indication function, and $\hat{\theta}$ denotes the desired
parameter. Teaching cost can be simply defined as the cardinality of $D$:
$\mathcal{M}(D)=\|D\|_{0}$, in which $\mathcal{M}(\mathbb{D})=2^{\|D\|_{0}}$
($\|\cdot\|_{0}$ denotes $L_{0}$
norm)111$2^{\|D\|_{0}}=\binom{\|D\|_{0}}{1}+\binom{\|D\|_{0}}{2}+...+\binom{\|D\|_{0}}{\|D\|_{0}}$,
where $\binom{\|D\|_{0}}{k}$ denotes the operation of selecting $k$ teaching
examples from the full training set $D$..

In this paper, we consider one challenging problem: how to teach a student
learner which does not disclose any cue (also termed as a black-box learner)
from the distribution of the parameters, i.e. estimating
$\mathcal{L}(\hat{\theta},\theta^{*})$ is inefficient due to improper
parameter disagreement or inestimable parameter space e.g. huge amounts of
parameters in a large neural network. Our main proposal to solving Eq. (2) in
such scenario is optimizing an approximated distribution for teaching.
Specifically, we 1) approximate $R(\theta,D)$ into a surrogate
$R(\theta,D^{\prime})$ by shrinking $D$ into its surrogate $D^{\prime}$ with
smooth boundary, and 2) then transform $\mathcal{L}(\hat{\theta},\theta^{*})$
as a distribution metric optimized in $D^{\prime}$ that assumes ${D}$ is
w.r.t. $\hat{\theta}$ and $\mathbbm{D}$ is w.r.t. $\theta^{*}$.

Our analysis based on importance sampling (Beygelzimer ., 2008) shows that
approximating the teaching risk by its surrogate is still guaranteed safely to
yield a tighter learning bound on label complexity (number of sampled data to
achieve a desired error). To implement the optimization of distribution
matching-based machine teaching, we employ the hyperbolic metric (Ganea .,
2018) that hierarchically ranks the transformed teaching risks. A Poincaré
measure $\mathbbm{h}(\cdot,\cdot)$ (Sarkar, 2011) is then utilized due to its
effectiveness in scattering those ranked features (Tay ., 2018) (Tran ., 2020)

$\begin{split}\mathcal{L}(\hat{\theta},\theta^{*})\approx\mathbbm{h}(D,\mathbbm{D}).\end{split}$
(3)

The main technical question of this paper is as follows: how to generalize Eq.
(3) with surrogate $R(\theta,D^{\prime})$. A distribution matching-based
machine teaching algorithm that transfers the disagreement estimation of
parameters into hypotheses, thereby approximating the hypothesis to
distribution, is then presented by narrowing the assumption of Eq. (3). Assume
$\theta^{*}$ is generalized from the optimal hypothesis $h^{*}$, i.e.
$R(\theta^{*},D)=R(h^{*},D)$, $\hat{\theta}$ is generalized from the
hypothesis $\hat{h}$, i.e. $R(\hat{\theta},D)=R(\hat{h},D)$, let
$D^{\prime}\subset\mathbb{D}$ be the optimal surrogate with respect to
$h^{*}$, let $\hat{D}\subset\mathbb{D}$ be the desired training set with
respect to $\hat{h}$, with the proposal of Eq. (3), we further have

$\min_{\hat{\theta}\in\Theta}\|\hat{\theta}-\theta^{*}\|=\min_{\hat{h}\in\mathcal{H}}\|\hat{h}-h^{*}\|\approx\min_{\hat{D}\in\mathbb{D}}\|\hat{D}-D^{\prime}\|_{\mathbbm{h}},$
(4)

where $\|\hat{D}-D^{\prime}\|_{\mathbbm{h}}:=\mathbbm{h}(\hat{D},D^{\prime})$.
In optimization of distribution matching-based machine teaching, minimizing
$\|\hat{D}-D^{\prime}\|_{\mathbbm{h}}$ is solved by controlling the teaching
cost, i.e. backwardly and iteratively halving $\mathcal{M}(D^{\prime})$. Then,
the final update on $D^{\prime}$ is defined as the teaching set $\hat{D}$.

Typical machine teaching mainly studies the optimal teaching set when the
student learner is a white-box whose underlying parameter distributions are
known, such as linear learners (J. Liu Zhu, 2016), sequential learner (Lessard
., 2019), Bayesian learners of the exponential family (J. Zhu, 2013), etc.
Theoretical discussion was the main trend in past decades. A complete teaching
theory such as teaching dimension and teaching complexity were proposed (Khan
., 2011). This paper focuses more on a black-box learner which further leads
to ineffective estimation on parameter disagreement for teaching risk. We thus
simplify the introduction of theoretical progress, and present related active
learning work. Finally, we contribute this work from the following highlights.

  * •

We introduce the idea of distribution matching for machine teaching a student
learner who does not disclose any cue of the learning parameters, i.e. a
black-box.

  * •

We present a cost-controlled optimization process that finds the optimal
teaching examples without further exploring in the parameter distribution.

  * •

We presents a distribution matching-based machine teaching strategy by
backwardly and iteratively performing the halving operation on the teaching
cost.

The organization of this paper is outlined as follows. The related work is
listed in Section 2. Section 3 presents the main theoretical results. Section
4 presents distribution matching-based machine teaching. Section 5 presents
experiments and Section 6 discusses the classifier perturbations to the
assumption of this work, followed by the conclusion in Section 7.

##  2 Related Work

###  2.1 Machine Teaching

When the training set of a model consists of plenty data from an underlying
distribution, a teacher always desires to pick up some teaching examples from
the original data set to supervise its student learner (X. Zhu ., 2018). In
this teaching process, the teacher can be generalized as a human expert, a
learning algorithm or system. Two factors are studied in the teaching process:
how to fix the size of the teaching set and whether the teacher knows the full
knowledge of the parameter distribution of the student model?

Early works answered the first problem by studying the teaching complexity.
Introducing a novel concept named teaching dimension (Khan ., 2011), the
complexity of teaching is characterized by the minimum number of teaching
examples must reveal to uniquely identify any hypothesis chosen from the
hypothesis class. If the teaching examples are selected independently from the
original data pool, the learner can cooperate with a teacher who supervises a
teaching set. Recently, machine teaching (Mei Zhu, 2015) studied the teaching
model when the learner was a convex minimizer, such as least square
regression, and simple support vector machine. In (W. Liu ., 2018), they
presented a theoretical interpretation against multiple-teacher teaching
rather than a single teacher. Under the joint teaching for conjugate Bayesian
learners, Zhu et al. (J. Zhu, 2013) proposed a new concept called class
teaching dimension. In this definition, the teacher independently picks up
some learners as a representation for the whole class of learners. Indeed, it
shrinks the original teaching dimension by the representation features of the
learner class.

In real-world applications, a variety of learning tasks involved with machine
teaching were studied. For instance, in curriculum learning (Bengio ., 2009),
human can intelligently annotate or recognize examples when the teaching
examples are not randomly presented but organized in a meaningful order. Those
orders help the teachers to optimize a group of teaching set for the
subsequent learning tasks. To improve the generalization of an active learner,
Dasgupta . (2019) proposed a black-box teaching scheme to shrink training sets
for any family of classifier by merely serving up the relevant examples
beforehand, and does not need to observe the feedback from the learner, where
“shrink” can be deemed as a typical distribution matching-based machine
teaching strategy.

###  2.2 Active Learning

Active learning (Cohn ., 1994) adopts the same sampling goal as machine
teaching to find the optimal training data, but forwardly updates the models.
In this task, the learners are given access to interactively query the labels
of a group of unlabeled data. The learning goal is that the queries can
substantially improve the performance of a learning model within a given
annotation budget. Theoretically, the learners always try to maintain a
version space (Beygelzimer ., 2010) which covers a series of candidate
hypotheses and shrinks its size via querying as few as possible data. However,
the version space-based learning theory unfortunately has drawbacks of
computational intractability (Dasgupta ., 2008), i.e., guaranteeing that only
hypotheses from this space are returned is intractable for nonlinear
classifiers.

To develop a new strategy which addresses the above limitations, Langley
(2006) and Hanneke (2007) constructed learning algorithms to predict which
data may significantly affect the subsequent hypothesis, thereby giving
different weight coefficients. The convergence guarantees, adopted from a PAC-
style222 PAC: Probably approximately correct. In computational learning
theory, the learner must select a generalization function i.e. the hypothesis
from a certain class of possible functions (also called hypothesis class). The
goal is that, with a high Probability, the selected function will have low
generalization error to be Approximately Correct. , is rigorous and tighter
than the generalized bounds of any supervised learning algorithms. The other
technique, termed as importance-weighted active learning (Beygelzimer .,
2008), provides an unbiased sampling approach with the loss-weighting and has
more practical use in observing the error and label complexity change.

In practical tasks, traditional active learning methods such as pool-based AL
(Tong Koller, 2001) samples the data that reduces the error rate in a descried
change by repeatedly visiting the unlabeled data pool. Usually, the learner is
given access to the hypothesis class easily, i.e. can favorably observe the
hypothesis updates by estimating the error disagreements (differences).
However, when supervising a black-box learner, obtaining precise details of
the prior labels and list of classifier parameters are not available, and only
the queries on labels are accessible. This makes many of the traditional
strategies, which estimate the error disagreements, are not applicable, or at
the least can not work well (Rubens ., 2011). To reduce the dependence on a
single classifier, query by committee algorithm (Seung ., 1992) uses a set of
classifiers to evaluate the error rate changes and selects the data which
maximize the disagreement among the committee members. However, estimating the
error rate changes in settings of single or multiple classifiers will cost
expensively on time and space complexities.

##  3 Main Theoretical Results

The main purpose of our theoretical study is to reconstruct the original
distribution by its surrogate with a smooth boundary. Section 3.1 introduces
importance sampling that used for approximating $R(\theta,D)$ and Section 3.2
provides the safety guarantee for its surrogate. Section 3.3 presents the
label complexity bounds of minimizing $R(\theta,D^{\prime})$. Section 3.4
generalizes the approximation of $D$ to $D^{\prime}$ in hyperbolic geometry.
Section 3.5 presents a case study of the approximation. Proof sketches of
Theorems 1 and 2 are presented in Appendix.

###  3.1 Importance Sampling

Importance sampling (Beygelzimer ., 2008) uses importance weighting to correct
sampling bias and rigorously observe the on-line error change for a machine
learning model. In this section, we find a surrogate $D^{\prime}$ to
approximate $R(\theta,D)$ by employing the importance sampling algorithm,
which further eliminates the noisy perturbations around the boundary of the
distribution.

In importance sampling, the machine learning algorithm assigns an unlabeled
data $x_{t}\in D$ with a probability $p_{t}$ to query its label $y_{t}$. The
underlying rule is: if $x_{t}$ is selected for querying at $t$-time of
sampling, its weight is set to $\frac{1}{p_{t}}$. Let $f(\cdot)$ denote the
mapping loss function from $D$ to $\mathcal{Y}$, given a classification
hypothesis $h:D\times\mathcal{Y}\rightarrow\mathbbm{R}$, where $\mathcal{Y}$
denotes the label space of $D$, let ${\rm err}_{T}(h)$ be the expected error
loss over $D$ of a hypothesis $h$ at query time $T$, the learning risk with
$T$ times of sampling from $D$ is defined as

$\begin{split}{R(h,D,T):=}\ {\rm
err}_{T}(h)=\frac{1}{T}\sum_{t=1}^{T}\frac{q_{t}}{p_{t}}f(h(x_{t}),y_{t}),\end{split}$
(5)

where $q_{t}$ denotes a Bernoulli distribution with $q_{t}\in\\{0,1\\}$,
$y_{t}\in\mathcal{Y}$, and it denotes the true label of $x_{t}$. Importance
sampling uses the probability weights to eliminate the sampling bias with
rigorous label complexity bounds to accelerate the convergence of the
minimization on $R(h,D)$, where label complexity denotes the number of the
sampled data to achieve a desired error. We next exploit the idea of
importance sampling to present the label complexity for the approximated
surrogate and its safety guarantee.

###  3.2 Safety Guarantee for Surrogate

In importance sampling, learning in surrogate $D^{\prime}$ can keep consistent
properties for the machine learning model but eliminates the noisy
perturbations from the boundary of the distribution i.e. its conceptual
version space. Theoretically, a desired safety guarantee (Beygelzimer ., 2008)
expects that the performance of a machine learning algorithm keeps a provably
consistency on its inherent optimal hypothesis.

Given an agnostic distribution ${P}$ maintaining a training set $D$ for
sampling, we define a subset $D^{\prime}$ with a smooth boundary as its
surrogate.

######  Definition 1.

Surrogate $D^{\prime}$ of $D$. Given a finite hypothesis class $\mathcal{H}$
with finite VC dimension 333Vapnik–Chervonenkis dimension. It is a measure of
the capacity such as complexity of a space of functions that can be learned by
a classification learning algorithm. In VC theory (Vapnik, 2013), the VC bound
is defined as the cardinality of the largest set of input training data that a
learning algorithm can shatter. bound $d$ that is uniquely associated with
$D$. Let $D^{\prime}$ be a surrogate of $D$ and $\mathcal{H}^{\prime}$ be the
shrunk hypothesis class over $D^{\prime}$. Assume that $d_{\mathcal{H}}(D)$
and $d_{\mathcal{H}^{\prime}}(D^{\prime})$ are the hypothesis diameters
(maximum hypothesis disagreement) of $\mathcal{H}$ and $\mathcal{H}^{\prime}$,
respectively, for any probability $\delta$, surrogate $D^{\prime}$ is one
subset from $D$ with a smooth boundary that satisfies

$\begin{split}&d_{\mathcal{H}}(D)-d_{\mathcal{H}^{\prime}}(D^{\prime})\leq\sqrt{2\Big{(}{\rm
In}\ d+{\rm In}\frac{2}{\delta}\Big{)}},\\\ &{\rm s.t.}\ D^{\prime}\subset
D,\|D^{\prime}\|_{0}=n^{\prime}<\|D\|_{0}=n,\\\ &d_{\mathcal{H}}(D):={\rm
max}\Bigg{\\{}\Big{|}{\rm err}_{D}(h^{+},x_{t}^{+})-{\rm
err}_{D}(h^{-},x_{t}^{-})\Big{|}_{\mathcal{H}}\Bigg{\\}},\\\
&d_{\mathcal{H}^{\prime}}(D^{\prime}):={\rm max}\Bigg{\\{}\Big{|}{\rm
err}_{D^{\prime}}(h^{+},x_{t}^{+})-{\rm
err}_{D^{\prime}}(h^{-},x_{t}^{-})\Big{|}_{\mathcal{H}^{\prime}}\Bigg{\\}},\\\
\end{split}$ (6)

where ${\rm err}_{D}(h^{+},x_{t}^{+})$ denotes the error of a subsequent
hypothesis $h^{+}$ over $D$ after adding and annotating $x_{t}$ with a
positive label, ${\rm err}_{D}(h^{-},x_{t}^{-})$ follows the annotation
assumption of a negative label, ${\rm err}_{D^{\prime}}(h^{+},x_{t}^{+})$ and
${\rm err}_{D^{\prime}}(h^{-},x_{t}^{-})$ also follow a surrogate
$D^{\prime}$, and $x_{t}$ is the sampled data from $D$ at $t$-time.

######  Definition 2.

Safety guarantee. Given $\mathbb{E}_{\theta\in\Theta}\ R(\theta,D^{\prime})$
be the expected empirical risk over surrogate $D^{\prime}$, let $d$ be the
finite VC dimension bound that is uniquely associated with $D$, for any
probability $\delta$, if

${\rm
Pr}\Bigg{\\{}|R(\theta,D)-\mathbb{E}_{\theta\in\Theta}R(\theta,D^{\prime})|\\!\leq\\!\\!\sqrt{2\Big{(}{\rm
In}\ d+{\rm In}\frac{2}{\delta}\Big{)}}\Bigg{\\}}\approx 1,$ (7)

any machine learning model that minimizes $R(\theta,D)$ is guaranteed safely
on minimizing $R(\theta,D^{\prime})$.

######  Assumption 1.

With importance sampling, assume that $\theta\in\Theta$ is respected to
$h\in\mathcal{H}$, recalling Eq. (4), approximating $R(\theta,D)$ into
$R(\theta,D^{\prime})$ is equivalent to approximating $R(h,D)$ into
$R(h,D,T)$, where $R(h,D,T)$ denotes error risk of $T$ times of importance
sampling w.r.t. Eq. (5) and $R(h,D)=\mathbb{E}_{(x,y)\sim{D}}f(h(x),y)$
without importance sampling.

Theorem 1 observes the ground-truth risk disagreement and its expectation,
where the risk disagreement is over the full training data and its surrogate.

######  Theorem 1.

With Assumption 1, given the training set ${D}$, for all finite hypothesis
class $\mathcal{H}$ with a VC dimension bound $d$, for any probability
$\delta>0$ and $p_{t}>\phi$, if a learning algorithm samples $T$ times to
obtain a surrogate of $D$, let R be the ground-truth risk disagreement of the
surrogate and its full training data that stipulates $\textbf{\rm
R}=|R(h,D,T)-R(h,D)|$, $\hat{\textbf{\rm R}}$ be the expected risk
disagreement that stipulates $\hat{\textbf{\rm
R}}=\mathbb{E}_{h\in\mathcal{H}}|R(h,D,T)-R(h,D)|$, with Definition 2, the
generalization probability bound of achieving a safe surrogate is

$\begin{split}{\rm Pr}\Bigg{\\{}|\textbf{\rm R}-\hat{\textbf{\rm
R}}|\\!\leq\\!\\!\sqrt{2\Big{(}{\rm In}\ d+{\rm
In}\frac{2}{\delta}\Big{)}}\Bigg{\\}}\\!\\!\leq\\!\exp\\!\Bigg{(}{\frac{-4({\rm
In}\ d+{\rm In}\frac{2}{\delta})}{T\phi^{-2}}}\Bigg{)}.\end{split}$ (8)

In brief, Theorem 1 shows that there exists nearly consistent hypothesis
diameters between the full training data and its surrogate, where the diameter
of surrogate is over its expectation.

######  Corollary 1.1.

In Theorem 1, R and $\hat{\textbf{\rm R}}$ denote the _maximum_ and _expected_
risk disagreement of the $T$ times importance sampling and full training data,
respectively. For a given hypothesis class $\mathcal{H}$ which covers all
feasible hypotheses, the maximum error disagreement is close to the hypothesis
diameter (Tosh Dasgupta, 2017) of $\mathcal{H}$. If the expected hypothesis
distance of a sub hypothesis class over $D^{\prime}$ is close to it, we say
sampling in $D^{\prime}$ yields consistency as sampling in $D$. Therefore,
with Definition 1, Theorem 1 has another equivalent form

${\rm Pr}\Bigg{\\{}|d_{\mathcal{H}}(D)-\mathbb{E}_{D^{\prime}\subset
D}d_{\mathcal{H^{\prime}}}(D^{\prime})|\\!\leq\\!\\!\sqrt{2\Big{(}{\rm In}\
d+{\rm In}\frac{2}{\delta}\Big{)}}\Bigg{\\}}\\!\\!\approx 1.$ (9)

Specifically, the probability bound of Eq. (8) approximates 1. With Assumption
1, approximating $R(\theta,D)$ into $R(\theta,D^{\prime})$ achieves safety
guarantee for any $\theta\in\Theta$ over $D^{\prime}$.

###  3.3 Label Complexity Bound for Minimizing $R(\theta,D^{\prime})$

We follow (Langley, 2006) to present the label complexity of minimizing
$R(\theta,D^{\prime})$.

######  Assumption 2.

Let $n$ denote the sample amount in $D$, its VC dimension bound $d$
approximates to $2^{n}$. By using importance sampling, $D^{\prime}$ is with a
VC bound $2^{T}$.

With Assumption 2, an upper bound of the label complexity of minimizing
$R(\theta,D^{\prime})$ is presented.

######  Theorem 2.

Given the slope asymmetry $K_{f}$ that bounds the loss function $f(h(x),y)$
w.r.t. Eq. (5) for any hypothesis $h$ over $D^{\prime}$: $K_{f}=\mathop{{\rm
sup}}\limits_{x_{t}^{\prime},x_{t}\in D^{\prime}}\left|\frac{{\rm max}\ {\rm
err}_{D^{\prime}}(h(x_{t}),\mathcal{Y})-{\rm
err}_{D^{\prime}}(h(x_{t}^{\prime}),\mathcal{Y})}{{\rm min}\ {\rm
err}_{D^{\prime}}(h(x_{t}),\mathcal{Y})-{\rm
err}_{D^{\prime}}(h(x_{t}^{\prime}),\mathcal{Y})}\right|$, considering a
disagreement coefficient
$\vartheta=\mathbb{E}_{x_{t}\in\mathcal{D}}\mathop{{\rm sup}}\limits_{h\in
B(h^{*},r)}\left\\{\frac{\ell(h(x_{t}),\mathcal{Y})-\ell(h^{*}(x_{t}),\mathcal{Y})}{r}\right\\}$,
if the learning algorithm uses $\vartheta$ to smooth those data of $D$ with
smaller hypothesis disagreements than $r$, with a probability $1-\delta$, at
$t$-time, minimizing $R(\theta,D^{\prime})$ into $R(\theta^{*},D^{\prime})$,
i.e. updating the current hypothesis $h$ into the optimal hypothesis $h^{*}$
in surrogate $D^{\prime}$, costs at most $4\vartheta\times
K_{f}\times\Bigg{(}R(h^{*},D^{\prime})+2\sqrt{\frac{8}{t-1}{\rm
In}\Big{(}\frac{2(t^{2}-t)\frac{d}{2^{n-T}}}{\delta}\Big{)}}\Bigg{)}$.

Note that $\vartheta$ is an error disagreement parameter that used to perform
the importance sampling. Any hypothesis $h$ holding a hypothesis disagreement
smaller than $r$ in terms of $\vartheta$, will be considered as a null
hypothesis which presents insignificant influence for updating the current
model, thereby being smoothed from the candidate hypothesis class. More
related analysis based on this class of error disagreement parameters can
refer to Hanneke’s work e.g. (Hanneke, 2007) (Hanneke ., 2014).

Note that $K_{f}$ is a constant that satisfies $K_{f}\geq 1$. Based on the
importance sampling of (Beygelzimer ., 2008), $K_{f}$ affects the label
complexity bound due to its “sensitivity”. For example, given a 0-1 loss for
$f(h(x),y)$, $K_{f}$ will be 1. However, for a hinge loss, $K_{f}$ will be
$\infty$. Therefore, for a sensitive loss function, the learning algorithm
will require a large number of importance sampling times to obtain a desired
hypothesis, then may lead to many ineffective queries. In other words, the
sensitive loss function usually presents a coarse estimation on hypothesis
disagreements. We here present a lemma to improve the generalization of
$K_{f}$.

######  Lemma 1.

Let $h$ be generalized as a logistic hypothesis that stipulates
$f(h(x),y):={\rm In}(1+e^{xy})$, assume that the label space
$\mathcal{Y}\in[-1,+1]$, if $x\in[-M,M]$, $K_{f}$ can be as large as
$(1+e^{M})$.

###  3.4 Approximating $D$ into $D^{\prime}$ using Poincaré Distance

Poincaré distance (Ganea ., 2018) of hyperbolic geometry has presented an
effective improvement in latent hierarchical tasks compared to Euclidean
distance ($\|\cdot\|_{2}$) such as ranking features (Tay ., 2018) (Tran .,
2020), embeddings (Nickel Kiela, 2018), non-linear gradient descending (Nitta
Kuroe, 2017), etc. To approximate $D$ into $D^{\prime}$, we need to rank one
property of all its members based specified estimations such as clustering
property, density characteristics, geometric structure, etc. Poincaré distance
thus is introduced to implement the ranking of the approximation progress.

Let $\mathcal{B}^{\bm{d}}=\\{x\in\mathbbm{R}^{\bm{d}},\|x\|_{2}<1\\}$ be an
open $\bm{d}$-dimensional unit Poincaré sphere ($\|\cdot\|_{2}$ denotes the
$L^{2}$ norm), $u$ and $v$ be any two vectors in the sphere, i.e.
$u,v\in\mathcal{B}^{\bm{d}}$, the Poincaré distance between them is defined as

$\begin{split}\mathbbm{h}(u,v)={\rm
arccosh}\Bigg{(}1+2\frac{\|u-v\|^{2}}{(1-\|u\|^{2})(1-\|v\|^{2})}\Bigg{)}.\end{split}$
(10)

Based on the work of Cao . (2018), noisy perturbations around the boundary
usually are characterized with low density observations. We thus estimate the
density of the data constrained within a fixed hypersphere

$\begin{split}&\mathbb{S}:=\\{v,\forall v\in D,\ {\rm s.t.}\
\psi(u,v)=1\\},\\\ &{\rm s.t.}\
\psi(u,v)=\left\\{\begin{array}[]{lr}0,&\mathbbm{h}(u,v)>\mathbbm{r},\\\
1,&0\leq\mathbbm{h}(u,v)\leq\mathbbm{r},\\\ \end{array}\right.\end{split}$
(11)

where $\mathbbm{r}$ denotes the radius of the hypersphere $\mathbb{S}$
centered with $u$. A more general equation that applies hypersphere
$\mathbb{S}$ to observe the density on $u$ is presented

$\begin{split}f_{\mathbb{S}}(u)=\frac{1}{\|\mathbb{S}\|_{0}}\sum_{v\in\mathbb{S}}\frac{1}{\sqrt{2\pi}^{\bm{d}}\mathbbm{r}^{\bm{d}}}{\rm
exp}\Bigg{[}-\frac{1}{2}\left(\frac{\mathbbm{h}(u,v)}{\mathbbm{r}}\right)^{2}\Bigg{]}.\end{split}$
(12)

(a) _digit_

(b)  _USPS_

(c) _FashionMnist_

(d)

Figure 2: Case study of clustering on surrogate with a smooth boundary to
improve clustering. $R(\theta,D)$ is generalized as (1-ARI) or (1-MI)
coefficients.

###  3.5 Case Study: Improving Clustering on Surrogate

This case study collects three real-world data sets and then compares the
clustering performance of three typical clustering baselines in $D^{\prime}$,
where $f_{\mathbb{S}}(u)$ is used to approximate $D$ into $D^{\prime}$. To
show the advantages of Poincaré distance in ranking, $f_{\mathbb{S}}(u)$ is
generalized into $F_{\mathbb{S}}(u)$ characterized with Euclidean distance,
which is further used to compare Eq. (12):

$\begin{split}F_{\mathbb{S}}(u)=\frac{1}{\|\mathbb{S}\|_{0}}\sum_{v\in\mathbb{S}}\frac{1}{\sqrt{2\pi}^{m}\mathbbm{r}^{\bm{d}}}{\rm
exp}\Bigg{[}-\frac{1}{2}\left(\frac{\|u-v\|_{2})}{\mathbbm{r}}\right)^{2}\Bigg{]}.\end{split}$
(13)

Datasets of the case study are _digit, USPS,_ and _FashionMnist_ , where all
the features of the data are scaled within an numerical unit of $10^{-5}$ to
satisfy $\|x_{i}\|_{2}<1$, $\forall x_{i}\in D$. The sizes of these data sets
are $3823\times 65$, $9,298\times 257$, and $70,000\times 784$, respectively.
$R(\theta,D)$ is generalized as (1-adjusted rand index (ARI))(Hubert Arabie,
1985) and (1-mutual information (MI))(Vinh ., 2010) coefficients.

Figure 2 presents the $R(\theta,D)$ values that yield 1) minimizing $R(h,D)$
by clustering baselines, 2) minimizing $R(h,D^{\prime})$ by clustering
baselines with $F_{\mathbb{S}}(u)$, and minimizing $R(h,D^{\prime})$ by
clustering baselines with $f_{\mathbb{S}}(u)$, where the clustering baselines
are generalized as $k$-means, hierarchical, and spectral clustering
algorithms, the parameters $\mathbbm{r}$ of Eqs. (11) and (12) are defined as
0.4, and $\|D\|_{0}-\|D^{\prime}\|_{0}=0.05n$, i.e. approximate $D$ into
$D^{\prime}$ by eliminating perturbations from $0.05n$ boundary examples.
Specifically, kernel function of spectral clustering is set as RBF, driving a
kernel parameter as 0.1 to construct an affinity matrix, where a $k$-means
clustering is used to assign labels in the embedding space of the kernel.

As the shown in Figure 2, the solid lines yield (1-ARI), and dash lines yield
(1-MI). $h\sim D$ denotes performing clustering in $D$, referring
$R(\theta,D)$ values on y-axis. $h\sim D^{\prime}$ includes $D^{\prime}\sim F$
and $D^{\prime}\sim f$, where $D^{\prime}\sim F$ denotes that $D^{\prime}$ is
approximated by $F_{\mathbb{S}}(u)$ w.r.t. Eq. (13), and $D^{\prime}\sim f$
denotes that $D^{\prime}$ is approximated by $f_{\mathbb{S}}(u)$ w.r.t. Eq.
(12). It is intuitively that clustering in $D^{\prime}$ yields
$R(h,D^{\prime})\leq R(h,D)$. Moreover, approximating $D$ into $D^{\prime}$
using $f_{\mathbb{S}}(u)$ ($D^{\prime}\sim f$) achieves lower empirical risks
than that of $F_{\mathbb{S}}(u)$ ($D^{\prime}\sim F$) due to its hierarchical
metric on ranking. This further demonstrates that density observations
employing Poincaré distance can yield more accurate surrogate than Euclidean
distance on eliminating the noisy perturbations around the boundary.

##  4 Distribution Matching-based Machine Teaching

Section 4.1 presents the assumption of the distribution matching-based machine
teaching. Section 4.2 presents the detailed optimization scheme by
generalizing $\mathbbm{h}(D,\mathbbm{D})$ in hyperbolic geometry. Section 4.3
describes the distribution matching-based machine teaching algorithm.

###  4.1 Assumption

With the effectiveness of approximating $R(\theta,D)$ in hyperbolic geometry,
the generalization of $\mathbbm{h}(D,\mathbbm{D})$ also follows this non-
Euclidean structure. Recalling Eq. (3), we here present a more formal
assumption against teaching a black-box learner: transfer the disagreement
estimation of parameters into hypotheses, thereby approximating the hypothesis
to distribution.

######  Assumption 3.

Assume that $\theta^{*}$ is generalized from the optimal hypothesis $h^{*}$,
i.e. $R(\theta^{*},D)=R(h^{*},D)$, $\hat{\theta}$ is generalized from the
hypothesis $\hat{h}$, i.e. $R(\hat{\theta},D)=R(\hat{h},D)$, let
$D^{\prime}\subset\mathbb{D}$ be the optimal surrogate with respect to
$h^{*}$, let $\hat{D}\subset\mathbb{D}$ be the desired training set with
respect to $\hat{h}$, with the proposal of Eq. (3), we further have

$\min_{\hat{\theta}\in\Theta}\|\hat{\theta}-\theta^{*}\|=\min_{\hat{h}\in\mathcal{H}}\|\hat{h}-h^{*}\|\approx\min_{\hat{D}\in\mathbb{D}}\|\hat{D}-D^{\prime}\|_{\mathbbm{h}},$
(14)

where $\|\hat{D}-D^{\prime}\|_{\mathbbm{h}}:=\mathbbm{h}(\hat{D},D^{\prime})$.

Another expression of Eq. (14) is
$\mathcal{L}(\hat{\theta},\theta^{*})=\min_{\hat{\theta}\in\Theta}\|\hat{\theta}-\theta^{*}\|\approx\mathbbm{h}(D,\mathbbm{D})$.
We thus have the following remark.

######  Remark 1.

With Assumption 3, the optimization of distribution matching-based machine
teaching over $\mathbbm{h}(D,\mathbbm{D})$ is generalized into
$\min_{\hat{D}\in\mathbb{D}}\|\hat{D}-D^{\prime}\|_{\mathbbm{h}}$. We thus
iteratively halve $\mathcal{M}(D^{\prime})$ i.e. $\|D^{\prime}\|_{0}$, which
linearly reduces the teaching cost. With iterative halving,
$\mathcal{M}(D^{\prime})$ varies from $n^{\prime}/2$ into
$n^{\prime}/4,n^{\prime}/8,n^{\prime}/16,...,n^{\prime}/{2^{l}}$, where $l$
denotes the halving frequency, $n^{\prime}/{2^{i}}=\lceil
n^{\prime}/{2^{i}}\rceil$, and the remaining examples after the $l$th halving
are the final teaching test if the learner does not control the output
$\mathcal{M}(D^{\prime})$. Specifically, the halving process is implemented
with the Poincaré distance of hyperbolic geometry. With iterative halving on
$D^{\prime}$, the final update on $D^{\prime}$ is defined as the teaching set
$\hat{D}$.

###  4.2 Cost-controlled Optimization

With Remark 1, the optimization of distribution matching-based machine
teaching over generalized
$\min_{\hat{D}\in\mathbb{D}}\|\hat{D}-D^{\prime}\|_{\mathbbm{h}}$ is solved by
controlling the teaching cost of $D^{\prime}$, that is performing a continuous
algorithmic halving on $D^{\prime}$, where the final update on $D^{\prime}$ is
the desired target $\hat{D}$.

The algorithm begins by generalizing $R(\theta,D)$. Let
$D’=\\{\mathcal{D}_{1},\mathcal{D}_{2},...,\mathcal{D}_{n^{\prime}}\\}\sim P$,
$R(\theta,\mathcal{D}_{i}):=\theta\mathcal{D}_{i}+\varepsilon_{i}$, where
$\varepsilon_{i}$ denotes a constant constraint on $\mathcal{D}_{i}$, machine
teaching with a black-box is to optimize $\theta^{*}$

$\theta^{*}=\operatorname*{argmin}_{\theta\in\Theta}\Bigg{\\{}\|\theta-\theta^{*}\|:=\sum_{i=1}^{n^{\prime}}\Big{\|}\theta\mathcal{D}_{i}-R(\theta,\mathcal{D}_{i})\Big{\|}^{2}\Bigg{\\}}.$
(15)

Recalling Eq. (1), we add a regularization constraint
$\Omega(\theta):=\eta\|\theta\|^{2}$ to Eq. (15)

$\begin{split}\theta^{*}=\operatorname*{argmin}_{\theta\in\Theta}\Bigg{\\{}\|\theta-\theta^{*}\|+\Omega(\theta):=\sum_{i=1}^{n^{\prime}}\Big{\|}\theta\mathcal{D}_{i}-R(\theta,\mathcal{D}_{i})\Big{\|}^{2}+\eta\|\theta\|^{2}\Bigg{\\}}.\end{split}$
(16)

Based on Assumption 3, estimating the parameter disagreement can be
transferred into distribution disagreement. We next introduce the Poincaré
distance $\mathbbm{h}(\cdot,\cdot)$ that stipulates
$R(\theta,\mathcal{D}_{i}):=\sum_{j=1}^{n^{\prime}/2}\alpha_{j}\mathbbm{h}(\mathcal{D}_{j},\mathcal{D}_{i})$,
then Eq. (16) is equivalent to

$\begin{split}\min_{\alpha}\sum_{i=1}^{n^{\prime}/2}\Bigg{\|}\sum_{j=1}^{n^{\prime}/2}\alpha_{j}\mathbbm{h}(\mathcal{D}_{j},\mathcal{D}_{i})\\!&-\\!\theta\mathcal{D}_{i})\Bigg{\|}^{2}\\!+\\!\sum_{i=1}^{n^{\prime}/2}\sum_{j=1}^{n^{\prime}/2}\alpha_{i}\alpha_{j}\mathbbm{h}(\mathcal{D}_{i},\mathcal{D}_{j}),\\\
\end{split}$ (17)

where $\alpha=[\alpha_{1},\alpha_{2},...,\alpha_{n^{\prime}/2}]$. Let
$\textbf{H}_{ij}:=\mathbbm{h}(\mathcal{D}_{i},\mathcal{D}_{j})$,
$[\textbf{H}_{\hat{D^{\prime}}D^{\prime}}]_{ij}:=\mathbbm{h}(\hat{\mathcal{D}}_{i},\mathcal{D}_{j})$,
where $\hat{D^{\prime}}\subset D^{\prime},\ {\rm s.t.}\
\|\hat{D^{\prime}}\|_{0}=n^{\prime}/2$, with Definition 3.1 in (Yu ., 2006),
Eq. (17) is transferred as $\mathbbm{h}(\hat{D^{\prime}},D^{\prime})$ that can
be solved by transductive optimization

$\begin{split}\mathbbm{h}(\hat{D^{\prime}},D^{\prime}):=\min_{\hat{D^{\prime}}\subset
D^{\prime}}\textbf{Tr}\Bigg{[}\textbf{H}_{\hat{D^{\prime}}D^{\prime}}(\textbf{H}_{{D^{\prime}}D^{\prime}}+\eta\textbf{C})^{-1}\textbf{H}_{{D^{\prime}}\hat{D^{\prime}}}\Bigg{]},\end{split}$
(18)

where $\textbf{C}\varpropto{D^{\prime}}{D^{\prime}}^{T}$. To optimize
$\hat{D^{\prime}}$, let $\mathcal{D}$ be the last selected teaching example,
$\hat{D^{\prime}}_{i}$ subsequently is obtained by

$\begin{split}\hat{D^{\prime}}_{i}:=\operatorname*{argmin}_{\mathcal{D}\in
D^{\prime}}\textbf{Tr}\Bigg{[}\textbf{H}_{\hat{D^{\prime}}\mathcal{D}}(\textbf{H}_{\mathcal{D}\mathcal{D}}+\eta\textbf{C})^{-1}\textbf{H}_{\mathcal{D}\hat{D^{\prime}}}\Bigg{]},\end{split}$
(19)

where
$\textbf{H}=\textbf{H}-\textbf{H}_{\hat{D^{\prime}}\mathcal{D}}(\textbf{H}_{\mathcal{D}\mathcal{D}}+\eta\textbf{C})^{-1}\textbf{H}_{\mathcal{D}\hat{D^{\prime}}}$.

1 Input: Full training set $D$, $0\leftarrow j$.

2 Estimating $f_{\mathbb{S}}(\mathcal{D}_{i})$ for any $\mathcal{D}_{i}$:

3 $\\!\mathcal{F}(i)\leftarrow
f_{\mathbb{S}}(\mathcal{D}_{i})=\frac{1}{\|\mathbb{S}\|_{0}}\sum_{v\in\mathbb{S}}\frac{1}{\sqrt{2\pi}^{\bm{d}}r^{\bm{d}}}{\rm
exp}\Bigg{[}\\!-\frac{1}{2}\left(\frac{\mathbbm{h}(\mathcal{D}_{i},v)}{r}\right)^{2}\Bigg{]}$.

4 Keep top $n^{\prime}$ examples with large $\|\mathcal{F}\|_{1}$ to obtain
$D^{\prime}$.

5 while  _$j\leq l$_ do

6 for  _$i=1,2,...,\frac{n^{\prime}}{2^{l}}$ _ do

7 $\hat{D^{\prime}}_{i}=\operatorname*{argmin}_{\mathcal{D}\in
D^{\prime}}\textbf{Tr}\Bigg{[}\textbf{H}_{\hat{D^{\prime}}\mathcal{D}}(\textbf{H}_{\mathcal{D}\mathcal{D}}+\eta\textbf{C})^{-1}\textbf{H}_{\mathcal{D}\hat{D^{\prime}}}\Bigg{]}$,

8 s.t.
$\textbf{H}=\textbf{H}-\textbf{H}_{\hat{D^{\prime}}\mathcal{D}}(\textbf{H}_{\mathcal{D}\mathcal{D}}+\eta\textbf{C})^{-1}\textbf{H}_{\mathcal{D}\hat{D^{\prime}}}$.

9

10 end for

11

12 $D^{\prime}\leftarrow\hat{D^{\prime}}.$

13 $j\leftarrow j+1.$

14 end while

15

Output: the final teaching set $\mathcal{M}(\hat{D^{\prime}})$; if the student
learner controls the out $\mathcal{M}(\hat{D^{\prime}})$, performing
$k$-medoids on $\hat{D^{\prime}}$ to satisfy the request.

Algorithm 1 Distribution Matching-based Machine Teaching Algorithm

###  4.3 Distribution Matching-based Machine Teaching Algorithm

Our distribution matching-based machine teaching algorithm is presented in
Algorithm 1. Here, $l$ denotes the frequency of performing the halving
operation on $D^{\prime}$ with a default constraint of
$\mathcal{M}(D^{\prime})=n^{\prime}=0.95\|D\|_{0}$. Lines 2 to 4 approximate
$R(\theta,D)$ into $R(\theta,D^{\prime})$ by shrinking $D$ into its surrogate
$D^{\prime}$. Lines 5 to 12 perform the iterative halving process on
$D^{\prime}$. The final update on $D^{\prime}$ after $l$ times halving is the
machine teaching set $\hat{D^{\prime}}$. If the student learner controls the
output $\mathcal{M}(\hat{D}^{\prime})$, $k$-medoids is performed on the final
update of $\hat{D}^{\prime}$ to satisfy the student learner’s request.

##  5 Experiments

Typical machine teaching algorithms estimate the parameter disagreement of
models to generalize the teaching risk, where the teacher knows the desired
parameter, i.e. the learner is a white-box. When teaching a black-box learner,
parameter estimations may be inefficient due to improper parameter
disagreement or inestimable parameter space. We thus select a series of
supervised and unsupervised machine learning baselines, which can be
generalized as white-box teaching, to compare our distribution-based machine
teaching algorithm.

To solve Eq. (2) of general machine teaching, there exists three conditions
which can simply its optimization process: 1) control $\mathcal{M}(D)$ with
Eq. (1)’s solver of active learning, 2) reduce the search space for limited
risk minimization, and 3) fix $\mathcal{M}(D)$ with unsupervised machine
learning. To realize these conditions, three groups of experiments are
presented:

  * •

regulating $\mathcal{M}(D)$ to minimize the risk disagreement of
$\|R(\theta,D)-R(\theta^{*},D)\|$, i.e. supervised way;

  * •

reducing the search space of $\mathbbm{D}$ to observe the perturbations to
typical machine learning and our machine teaching algorithms;

  * •

minimizing $\|R(\theta,D)-R(\theta^{*},D)\|$ with quantitative
$\mathcal{M}(D)$, i.e. unsupervised way.

Data sets. The data sets used in the first two groups of experiments are the
full training data of _Adult_ , _Phishing_ , _Satimage_ , and _MNIST_ data
sets, where $\|R(\theta,D)-R(\theta^{*},D)\|$ is over those training data. The
sizes of these data sets are 11,055$\times$ 68, 1,605 $\times$ 14,
4,435$\times$36, and 60,000$\times$ 780, respectively. The data sets used in
the third group of experiment are CIFAR10 and CIFAR100, where
$\|R(\theta,D)-R(\theta^{*},D)\|$ is over their test data. The sizes of the
two data sets are all 60, 000 with 32$\times$32 pixels.

Baselines. Four supervised learning algorithms that regulate $\mathcal{M}(D)$
to minimize $\|R(\theta,D)-R(\theta^{*},D)\|$ are selected including expected
error reduction (ERR) (Roy McCallum, 2001), Pre-clustering (Dasgupta Hsu,
2008), transductive experimental design (TED) (Yu ., 2006) and self-paced
active learning (SPAL) (Tang Huang, 2019). Specifically, they are active
learning algorithms. Three typical unsupervised machine learning algorithms
that minimize $\|R(\theta,D)-R(\theta^{*},D)\|$ with quantitative
$\mathcal{M}(D)$ are selected: $k$-medoids, hierarchical, and spectral
clustering. Those baselines are finally used in experiment of teaching a deep
neural network. A case study of teaching on Gaussian data is firstly presented
before the experiments. Note that distribution-based machine teaching is
denoted as DM-based machine teaching in all experimental figures.

(a) Gaussian dataset $D$

(b)  Surrogate $D^{\prime}$ (blue examples) of $D$

(c) $\mathcal{M}(D^{\prime})=615$

(d) $\mathcal{M}(D^{\prime})=307$

(e) $\mathcal{M}(D^{\prime})=153$

(f)  $\mathcal{M}(D^{\prime})=76$

(g) $\mathcal{M}(D^{\prime})=38$

(h) $\mathcal{M}(D^{\prime})=19$

Figure 3:  2D visualizations of distribution matching-based machine teaching
on a Gaussian dataset $D$. In (b), circled data are boundary examples. In (c)
to (h), circled data with ‘+’ are teaching sets with different
$\mathcal{M}(D^{\prime})$

###  5.1 Case Study: Teaching on a 2D Gaussian Dataset

Figure 3 presents a case study of distribution matching-based machine teaching
on a 2D Gaussian dataset. The 2D visualizations dynamically show the iterative
halving process on surrogate $D^{\prime}$: 1) Figure 3(a) draws the full
training Gaussian data $D$, where $\mathcal{M}(D)=1400$; 2) Figure 3(b) draws
the surrogate of $D$, where the circled 170 data are boundary examples, the
remaining blue points are the data of $D^{\prime}$, and the parameter settings
are $r=0.4$, $\eta=1.0e-4$; 3) Figures 3(c) to 3(h) show the iterative halving
process, where $\mathcal{M}(D^{\prime})$ is continuously halved. The presented
teaching sets with different $\mathcal{M}(D^{\prime})$ properly match the
distribution of $D$ without noisy perturbations around boundary.

Specifically, all the teaching examples are distributed inside the clusters
with high densities due to the smooth boundary of the surrogate $D^{\prime}$
(w.r.t. Lines 1 to 4 of Algorithm 1). The iterative halving (w.r.t. Lines 5 to
12) is performed on the last update of $D^{\prime}$, which keeps consistent
distribution properties as its previous. Therefore, all the teaching sets with
different $\mathcal{M}(D^{\prime})$ yield consistent distributions as the
original distribution of $D$.

(a) _Adult_

(b)  _Phishing_

(c) _Satimage_

(d) _MNIST_

Figure 4: Regulating $\mathcal{M}(D)$ to minimize
$\|R(\theta,D)-R(\theta^{*},D)\|$ on _Adult, Phishing, Satimage_ , and _MNIST_
data sets.

###  5.2 Regulating $\mathcal{M}(D)$ to Minimize
$\|R(\theta,D)-R(\theta^{*},D)\|$

Regulating $\mathcal{M}(D)$ is important for both machine teacher and student
learners due to over-fitting or computational overhead. With Assumption 3, the
goal of machine teaching is to minimize $\|R(\theta,D)-R(\theta^{*},D)\|$,
where $\theta^{*}$ is with respect to $D$. The experimental datasets are
_Adult, Phishing, Satimage,_ and the _MNIST_. We assume that $h$ is generated
from a SVM classifier with a RBF kernel. That means, $R(\theta^{*},D)=0.1200$
on _Adult_ , $R(\theta^{*},D)=0.1141$ on _Phishing_ , $R(\theta^{*},D)=0.0875$
on _Satimage_ , and $R(\theta^{*},D)=0.0009$ on _MNIST_ , where each $h^{*}$
is over the full training data.

The compared machine learning baselines are typical active learning algorithms
including ERR, Pre-clustering, TED and SPAL, where ERR maximizes the expected
error reduction over a SVM classifier, Pre-clustering employs the Hierarchical
clustering and the pruning budget is set from 100 to 1000 with a step of 100,
TED uses a hyperparameter $\sigma$=1.8 (kernel bandwidth parameter) to
generate the kernel matrix and vary $\lambda$ (kernel ridge regression) from
0.01 to 1 with a step of 0.01, and SPAL sets the paced learning parameter from
0.01 to 1 with a step of 0.01, etc. Before running those machine learning
baselines, we randomly select 10 data from each dataset to train an initial
hypothesis for them. For our distribution matching-based machine teaching
algorithm, $\mathcal{M}(D^{\prime})=n^{\prime}$, $n^{\prime}/n\in[0.85,0.95],$
$r=[0.1,0.5]$ $\eta=10e-4$, and $l$ is constrained by
$\mathcal{M}(D^{\prime})$ that satisfies
$\frac{n^{\prime}}{2^{l}}\geq\mathcal{M}(D^{\prime})$.

Figure 4 draws the learning curves of regulating $\mathcal{M}(D)$ to minimize
$\|R(\theta,D)-R(\theta^{*},D)\|$ into an expected risk across the best
parameter candidates of each baseline. From the test results in Figure 4, we
find that machine teaching algorithm can regulate $\mathcal{M}(D)$ better than
the machine learning baselines, i.e. spend fewer training data to obtain an
expected learning risk. Especially at the beginning of those curves,
$\mathcal{M}(D)$ of machine teaching is much smaller than that of the machine
learning baselines.

(a) _Adult_

(b)  _Phishing_

(c) _Satimage_

(d) _MNIST_

Figure 5:  Reducing the search space of $\mathbbm{D}$ to minimize
$\|R(\theta,D)-R(\theta^{*},D)\|$ on _Adult, Phishing, Satimage_ , and _MNIST_
data sets.

###  5.3 Reducing the Search Space of $\mathbbm{D}$

Reducing the search space of $\mathbbm{D}$ can relieve the minimization costs
of Eqs. (1) and (2) because estimating one data whether can be picked up as a
teaching example needs to access the whole unlabeled data pool. If the teacher
needs to give feedback for the learner in a limited budge cost e.g. time and
space, the teaching algorithm must help the teacher make a decision on which
example should be selected.

Given an access budget of $\lceil n/2\rceil$ to the unlabeled data pool one
time, the machine learning and teaching algorithms have to return one best
candidate teaching example. Figure 5 draws the $\mathcal{M}(D)$ curves by
progressively minimizing $\|R(\theta,D)-R(\theta^{*},D)\|$. Compared to the
results in Figure 4 with a full access budget, the $\mathcal{M}(D)$ of machine
learning baselines arise rapidly due to the greedy updates on $\theta$ to
$\hat{\theta}$ can not always be the optimal. This forces the learning
algorithm to request more data to reach an expected learning risk. However,
our machine teaching algorithm backward and iteratively halves $\theta^{*}$ to
$\hat{\theta}$ without greedy search in $D$, thereby lower perturbations to
the limited access budget are presented. Therefore, the generalized
distribution matching-based machine teaching algorithm could trust a black-box
student learner with inestimable teaching loss in real teaching tasks.

(a) _Adult_

(b)  _Phishing_

(c) _Satimage_

(d) _MNIST_

Figure 6: Minimizing $R(\theta^{*},D)-R(\theta,D)$ with quantitative
$\mathcal{M}(D)$, i.e. unsupervised machine learning.

(a) $\mathcal{M}(D^{\prime})$=500

(b) $\mathcal{M}(D^{\prime})$=1,000

(c) $\mathcal{M}(D^{\prime})$=2,000

(d) $\mathcal{M}(D^{\prime})$=3,000

Figure 7: 2D embeddings of distribution matching-based machine teaching sets
on _MNIST_ , which properly draws the 10 classes.

###  5.4 Minimizing $\|R(\theta,D)-R(\theta^{*},D)\|$ with Quantitative
$\mathcal{M}(D)$

Optimizing Eqs. (1) and (2) with a quantitative $\mathcal{M}(D)$ is also a
possible condition to simplify the minimization process. Then, Eq. (2) can be
solved by an unsupervised way. Therefore, unsupervised machine learning
algorithms such as clustering can be deemed as a special class of candidate
teaching methods with quantitative $\mathcal{M}(D)$.

In this group of experiments, we collect the learning risk change of
$\|R(\theta,D)-R(\theta^{*},D)\|$ with quantitative $\mathcal{M}(D)$ settings.
The compared three unsupervised algorithms are $k$-medoids, hierarchical, and
spectral clustering, where $\mathcal{M}(D)$ is set as the clustering numbers.
Specifically, kernel function of spectral clustering is set as RBF, driving a
kernel parameter as 0.1 to construct an affinity matrix, where a $k$-means
clustering is used to assign labels in the embedding space of the kernel. The
whole collected teaching results of the three baselines are drawn in Figure 6.
We intuitively find the performance of all the clustering algorithms are very
unstable. They show sensitive change on $\|R(\theta,D)-R(\theta^{*},D)\|$ in
term of the test set of _Adult_ and _Phishing_ since they are binary
classification data sets without strong clustering structures. We also find
Hierarchical clustering algorithm cannot decrease
$\|R(\theta,D)-R(\theta^{*},D)\|$ when setting $\mathcal{M}(D)$ be lower than
700. This is because that the two data sets have no intuitive tree structures.
For the _Satimage_ and _MNIST_ data sets with clear clustering structure,
unsupervised machine learning algorithms achieve better performance on
minimizing $\|R(\theta,D)-R(\theta^{*},D)\|$, even better than machine
teaching on _Satimage_.

Overall, the unsupervised machine learning approaches can be applied in
teaching a black-box learner, but show very unstable performance on minimizing
learning risk due to their local convergence conditions. A global strategy
should be considered to minimize $\|R(\theta,D)-R(\theta^{*},D)\|$ with
quantitative $\mathcal{M}(D)$. This also is the inherent reason why our
proposed distribution-based algorithm can be adopted in machine teaching with
inestimable teaching risk.

To visualize the distribution of the output teaching set of distribution
matching-based machine teaching algorithm, Figure 7 presents the 2D embeddings
of teaching sets of distribution matching-based machine teaching on _MNIST_
with different $\mathcal{M}(D^{\prime})$. The results show those teaching sets
can properly draw the 10 separable classes.

###  5.5 Teaching a Deep Neural Network

We compare the deep learning performance of our distribution matching-based
machine teaching algorithm to the supervised and unsupervised machine learning
models. Figure 8 presents the learning curves of regulating $\mathcal{M}(D)$
to minimize $\|R(\theta,D)-R(\theta^{*},D)\|$ following the experiments of
Sections V.A and V.B. The deep neural network is ResNet20 and the tested
datasets are CIFAR10 and CIFAR100. The hyperparameters of the network
architecture are batch size=32, epochs=200, depth =20, learning rate=0.001,
filter number=16, etc. The network architecture was implemented by Keras
2.2.3. The results show our machine teaching algorithm can still minimize
$R(\theta^{*},D)-R(\theta,D)$ faster than the compared supervised and
unsupervised machine learning baselines, where $R(\theta^{*},D)=0.9200$ over
_CIFAR10_ and $R(\theta^{*},D)=0.6729$ over _CIFAR100_. Figure 9 presents the
2D embeddings of distribution matching-based machine teaching sets on
_CIFAR10_ with different $\mathcal{M}(D^{\prime})$.

(a)  _CIFAR10_

(b) _CIFAR100_

Figure 8: Regulating $\mathcal{M}(D)$ to minimize
$\|R(\theta,D)-R(\theta^{*},D)\|$ on data sets _CIFAR10_ and _CIFAR100_.

(a)  $\mathcal{M}(D^{\prime})$=500

(b) $\mathcal{M}(D^{\prime})$=1000

Figure 9: 2D embeddings of distribution matching-based machine teaching sets
on _CIFAR10_ , which properly draws the 10 classes.

(a) KNR on _digit_

(b)  RandomForest on _digit_

(c) MLPClassifier on _digit_

(d) SVM on _digit_

(e) KNR on _USPS_

(f)  RandomForest on _USPS_

(g) MLPClassifier on _USPS_

(h)  SVM on _USPS_

(i) KNR on _FashionMnist_

(j) RandomForest on _FashionMnist_

(k) MLPClassifier on _FashionMnist_

(l) SVM on _FashionMnist_

Figure 10:  Learning curves of regulating $\mathcal{M}(\mathcal{D})$ to
minimize $R(\theta^{*},D)-R(\theta,D)$ on _digit, USPS,_ and FashionMnist data
sets, where $\theta^{*}$ is respect to $h^{*}$ generalized from different
classifiers.

##  6 Discussion on Our Assumption

This study is based on Assumption 3, which stipulates $R(\theta^{*},D)\approx
R(h^{*},D)$. Therefore, how to derive a more general hypothesis $h$ may have
perturbations to this assumption. In read-world, $h$ is usually generalized
from different classifiers. In this section, we collect different classifiers
to test the main technical steps of the iterative halving in distribution
matching-based machine teaching.

With this goal, we apply our machine teaching algorithm to derive teaching
sets as the labeled data for the subsequent supervised classification. The
candidate classifiers are $k$ Neighbors Regressor (KNR), Random Forest
(RandomForest), Multi-layer Perceptron classifier (MLPClassifier), and Support
Vector Machine (SVM). Figure 10 presents the learning curves of regulating
$\mathcal{M}(D)$ to minimize $\|R(\theta,D)-R(\theta^{*},D)\|$ on _digit,
USPS,_ and FashionMnist data sets, where $\theta^{*}$ is respect to $h^{*}$
generalized from different classifiers.

The training parameters of the four classifiers are described as follows: (1)
we set the $k$ nearest number as 10 for KNR; (2) we set the number of trees in
the RandomForest as 600; (3) for MLPClassifier, we set the size of the hidden
layers as 100, the maximum iteration number as 1000, the $L_{2}$ penalty
(regularization term) parameter as 0.0004, the optimization strategy as
stochastic gradient descent, and the learning rate as 0.001; (4) for the SVM
classifier, we set the penalty parameter as 1.0, the kernel type as RBF, the
degree of the kernel function as 3, and the tolerance for stopping criterion
as 0.003.

Distribution matching-based machine teaching significantly reduces the
expected learning risks with the increase of $\mathcal{M}(D)$. In the reported
results of the four classifiers, perturbations of
$\|R(\theta,D)-R(\theta^{*},D)\|$, i.e.

$\Big{(}\max{R(\theta^{*},D)-R(\theta,D)})-(\min{R(\theta^{*},D)-R(\theta,D)}\Big{)},$

which yields an interval of [0.06, 0.14], where $\mathcal{M}(D)/n$ yields an
interval of [0.1, 0.5]. Particularly, a part of learning curves don not keep
consistent decreasing with the increase of $\mathcal{M}(D)/n$ such as
MLPClassifier on _digit_ , RandomForest on _FashionMnist_ , etc. This explores
that the iterative halving may delay the decrease of the expected learning
risks, which further reduces the perturbations of having. Therefore, our
machine teaching algorithm keeps an uniform decrease on expected learning
risks, which also may delay its decrease to a lower loss. Besides this, SVM
achieves the lowest $\|R(\theta,D)-R(\theta^{*},D)\|$. Cooperating with a
solid classifier may further delay the decrease of the learning risks.

##  7 Conclusion

In this work, we proposed a distribution matching-based machine teaching
algorithm with regard to estimating a teaching risk on distributions against a
black-box learner. The analysis proved that the approximated surrogate had
safety guarantee. Case study further presented support for this theoretical
view and demonstrated that Poincaré distance of hyperbolic geometry could
yield a smoother boundary for learning a surrogate than Euclidean distance. We
thus projected the subsequent iterative halving in this geometry. Experiments
demonstrated distribution matching-based machine teaching outperformed the
supervised and unsupervised machine learning algorithms on minimizing expected
learning risk disagreement. Finally, this work leads to an open question: can
we co-teach the disagreement estimations on the distribution and model
parameters?

### Acknowledgments

This work was supported by Australian Research Council under Grant DP180100106
and DP200101328.

## Appendix

Proof of Theorem 1.

###### Proof.

Fix the input training data $D$, for any hypothesis $h_{i}\in\mathcal{H}$ over
$D$, we use passive sampling to weight the learning process of the importance
sampling algorithm. Let ${\rm err}_{T}(h)$ denote the important weighted error
at $T$-time of sampling, we define the risk of $T$ times of importance
sampling as ${R(h,D,T):=}{\rm
err}_{T}(h)=\frac{1}{T}\sum_{t=1}^{T}\frac{q_{t}}{p_{t}}f(h(x_{t}),y_{t})$,
and the risk of full training on $D$ $R(h,D):={\rm
err}_{D}(h)=\mathbb{E}_{(x,y)\sim{D}}f(h(x),y).$

Let $\mathcal{Y}$ be the label set of $D$, $f(\cdot)$ be a class of mapping
function involved with error measure from $D$ to $\mathcal{Y}$, such as the
best-in-class error or all-in-class error. Given any sampled example $x_{t}$
from $D$ which leads to a biased error at any $t$-th time of sampling, the
upper bound of errors of the $T$ times of sampling satisfies
$R(h,D,T)>R(h,D,t),\forall t<T$. That is to say,
$R(h,D,T)>R(h,D,1),R(h,D,T)>R(h,D,2),$ $...,$ $R(h,D,T)>R(h,D,T\textit{-}1).$
Therefore, the disagreement of the surrogate and its full training data in the
$T$ times of sampling satisfies

$\begin{split}\textbf{\rm R}&=|R(h,D,T)-R(h,D)|\leq R(h,D,T)\\\
&=\frac{1}{T}\sum_{t=1}^{T}\frac{q_{t}}{\phi}f\left(h(x_{t}),y_{t}\right),\\\
\end{split}$ (20)

then we have the following inequality about the upper bound of risk R

$\begin{split}\textbf{\rm
R}\leq\frac{1}{T}\sum_{t=1}^{T}\frac{q_{t}}{\phi}f\left(h(x_{t}),y_{t}\right),\end{split}$
(21)

where $q_{t}<\phi$ for any $t\leq T$.To produce a generalization on the above
risk disagreement, we need to estimate a more general _upper bound_ on
$\frac{1}{T}\sum_{t=1}^{T}\frac{q_{t}}{\phi}f\left(h(x_{t}),y_{t}\right)$.
Following importance sampling, we define $f(\cdot)$ be a 0-1 loss. Then, a
more general upper bound of
$\sum_{t=1}^{T}\frac{q_{t}}{\phi}f\left(h(x_{t}),y_{t}\right)$ is
$\sum_{t=1}^{T}\frac{q_{t}}{\phi}\times 1$. We here update Eq. (21) into

$\begin{split}\textbf{\rm R}\leq\frac{1}{\phi}.\end{split}$ (22)

Let $h_{1},h_{2},...,h_{T}$ be $T$ independent hypotheses over ${D}$ at
different sampling times, where $h_{t}$ is the hypothesis generated at the
$t$-time of sampling. We follow the result of Eq. (22) and know

$\begin{split}|R(h,D,T)-R(h,D)|\leq\frac{1}{\phi},\forall t<T.\end{split}$
(23)

Simply to say, $\frac{1}{\phi}$ can be a hypothesis diameter that covers the
hypothesis class of $\\{h_{1},h_{2},...,h_{T}\\}$. With this diameter
constraint, for any pair hypotheses $\\{h_{t},h_{t^{\prime}}\\}$, we conclude

$\begin{split}\Big{|}{\rm err}_{T}(h_{t^{\prime}})-{\rm
err}_{D}(h_{t})\Big{|}\leq\frac{1}{\phi},\forall t,t^{\prime}<T.\end{split}$
(24)

After applying the McDiarmid’s Inequality for Eq. (24), with definition 2, the
generalization probability bound of achieving a safety surrogate in the $T$
times of sampling is

$\begin{split}{\rm Pr}\Bigg{\\{}\Big{|}|{\rm err}_{T}(h)-{\rm
err}_{D}(h)|-\mathbb{E}[{\rm err}_{T}(h)-{\rm
err}_{D}(h)]\Big{|}\leq\lambda\Bigg{\\}}&\leq{\rm
exp}\left({\frac{-2\lambda^{2}}{\sum_{i=1}^{T}\phi^{-2}}}\right)\\\ &={\rm
exp}\left({\frac{-2\lambda^{2}}{T\phi^{-2}}}\right).\end{split}$ (25)

If we set $\lambda$ proportional to $\phi^{-1}$, then there exists a maximum
possible martingale value of $\Big{|}|{\rm err}_{T}(h)-{\rm
err}_{D}(h)|-\mathbb{E}[{\rm err}_{T}(h)-{\rm err}_{D}(h)]\Big{|}$. Following
the choice of slack variable in (Beygelzimer ., 2009), we set
$\lambda=\sqrt{2({\rm In}\ d+{\rm In}(2/\delta))}$ and $\hat{\textbf{\rm
R}}=\mathbb{E}_{h\in\mathcal{H}}|R(h,D,T)-R(h,D)|$, then the bound is as
stated. ∎

Proof of Theorem 2.

###### Proof.

Fix $\theta$, assume that ${D}$ is over a ball $B$ with radius $r$. Let
$h(x)\neq h^{*}(x)$, $h^{*}=\arg\inf\limits_{h\in\mathcal{H}}{\rm
err}_{{D}}(h),$ we define $\vartheta$ (Beygelzimer ., 2010) (Beygelzimer .,
2008) as

$\begin{split}&\vartheta=\mathbb{E}_{x_{t}\in\mathcal{D}}{\rm sup}_{h\in
B(h^{*},r)}\left\\{\frac{\ell(h(x_{t}),\mathcal{Y})-\ell(h^{*}(x_{t}),\mathcal{Y})}{r}\right\\},\end{split}$
(26)

where $\ell(h,\mathcal{Y})$ denotes the classification loss of a hypothesis
$h$ regarded with the label space $\mathcal{Y}$, and $r$ denotes the
hypothesis radius of $\mathcal{H}$.

To estimate the hypothesis radius $r$, we have $\ell(h,h^{*})\leq r$. For any
hypothesis $h$, we define the hypothesis distance $\ell(h,h^{*})$ as:
$\ell(h,h^{*})=\mathbb{E}_{x\in{D}}{\rm
max}|\ell(h(x_{t}),\mathcal{Y})-\ell(h^{*}(x_{t}),\mathcal{Y})|$. Then we have

$\begin{split}&\ell(h,h^{*})=\mathbb{E}_{x\in{D}}{\rm
max}|\ell(h(x_{t}),\mathcal{Y})-\ell(h^{*}(x_{t}),\mathcal{Y})|\\\
&\leq\mathop{{\rm sup}}\limits_{x_{t}^{\prime},x_{t}\in
D^{\prime}}\left|\frac{{\rm max}\
\ell(h(x_{t}),\mathcal{Y})-\ell(h(x_{t}^{\prime}),\mathcal{Y})}{{\rm min}\
\ell(h(x_{t}),\mathcal{Y})-\ell(h(x_{t}^{\prime}),\mathcal{Y})}\right|\times|\mathbb{E}_{x\in{D}}|\ell(h(x_{t}),\mathcal{Y})-\ell(h^{*}(x_{t}),\mathcal{Y})|\\\
&\leq
K_{f}\left|\mathbb{E}_{x\in{D}}\ell(h(x_{t}),\mathcal{Y})\right|+\left|\mathbb{E}_{x\in{D}}\ell(h^{*}(x_{t}),\mathcal{Y})\right|\\\
&\leq 2K_{f}\ell(h).\\\ \end{split}$ (27)

By Theorem 2 of (Beygelzimer ., 2008), we know that the risk disagreement of
$h$ and $h^{*}$ satisfies $\ell(h)\leq\ell(h^{*})+2\sqrt{\frac{8}{t-1}{\rm
In}\left(\frac{2(t^{2}-t)\frac{d}{2^{n-T}}}{\delta}\right)}$. Thus,

$\begin{split}\ell(h,h^{*})&\leq 2K_{f}\ell(h)\\\ &\leq
2K_{f}\left(\ell(h^{*})+2\sqrt{\frac{8}{t-1}{\rm
In}\left(\frac{2(t^{2}-t)\frac{d}{2^{n-T}}}{\delta}\right)}\ \right).\\\
\end{split}$ (28)

For any two hypotheses $h_{i}$, $h_{j}$, $\ell(h_{i},h_{j})\leq
2\ell(h,h^{*})$ over $B(h^{*},r)$. Therefore, updating the hypothesis $h$ into
the optimal hypothesis $h^{*}$ over $D^{\prime}$ costs at most
$2\ell(h,h^{*})$ at $t$-time. Here, we give a bound on $2\ell(h,h^{*})$ as
follows:

$\begin{split}&2\ell(h,h^{*})\\\ &\leq 2\vartheta r\leq 4\vartheta
K_{f}\left(\ell(h^{*})+2\sqrt{\frac{8}{t-1}{\rm
In}\left(\frac{2(t^{2}-t)\frac{d}{2^{n-T}}}{\delta}\right)}\ \right).\\\
\end{split}$ (29)

When we associate the loss function $\ell(h,\mathcal{Y})$ with ${\rm
err}_{D}^{\prime}(h)$ as a generalization, $\ell(h^{*})$ equals
$R(h^{*},D^{\prime})$. Theorem 2 then holds.

∎

## References

  * Bengio . (2009) bengio2009curriculumBengio, Y., Louradour, J., Collobert, R. Weston, J.  2009\.  Curriculum learning Curriculum learning.  Proceedings of the 26th annual international conference on machine learning Proceedings of the 26th annual international conference on machine learning ( 41–48).
  * Beygelzimer . (2008) beygelzimer2008importanceBeygelzimer, A., Dasgupta, S. Langford, J.  2008\.  Importance Weighted Active Learning Importance weighted active learning.  Proceedings of the 25th international conference on Machine learning.
  * Beygelzimer . (2009) beygelzimer2009importanceBeygelzimer, A., Dasgupta, S. Langford, J.  2009\.  Importance weighted active learning Importance weighted active learning.  Proceedings of the 26th Annual International Conference on Machine Learning Proceedings of the 26th annual international conference on machine learning ( 49–56).
  * Beygelzimer . (2010) beygelzimer2010agnosticBeygelzimer, A., Hsu, DJ., Langford, J. Zhang, T.  2010\.  Agnostic active learning without constraints Agnostic active learning without constraints.  Advances in Neural Information Processing Systems Advances in neural information processing systems ( 199–207).
  * Cao . (2018) cao2018multidimensionalCao, X., Qiu, B., Li, X., Shi, Z., Xu, G. Xu, J.  2018\.  Multidimensional Balance-Based Cluster Boundary Detection for High-Dimensional Data Multidimensional balance-based cluster boundary detection for high-dimensional data.  IEEE transactions on neural networks and learning systems3061867–1880.
  * Cohn . (1994) cohn1994improvingCohn, D., Atlas, L. Ladner, R.  1994\.  Improving generalization with active learning Improving generalization with active learning.  Machine learning152201–221.
  * Dasgupta Hsu (2008) dasgupta2008hierarchicalDasgupta, S. Hsu, D.  2008\.  Hierarchical sampling for active learning Hierarchical sampling for active learning.  Proceedings of the 25th international conference on Machine learning Proceedings of the 25th international conference on machine learning ( 208–215).
  * Dasgupta . (2019) DBLP:conf/icml/Dasgupta0PZ19Dasgupta, S., Hsu, D., Poulis, S. Zhu, X.  2019\.  Teaching a black-box learner Teaching a black-box learner.  Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA Proceedings of the 36th international conference on machine learning, ICML 2019, 9-15 june 2019, long beach, california, USA ( 1547–1555).
  * Dasgupta . (2008) dasgupta2008generalDasgupta, S., Hsu, DJ. Monteleoni, C.  2008\.  A general agnostic active learning algorithm A general agnostic active learning algorithm.  Advances in neural information processing systems Advances in neural information processing systems ( 353–360).
  * Ganea . (2018) ganea2018hyperbolicGanea, OE., Bécigneul, G. Hofmann, T.  2018\.  Hyperbolic Entailment Cones for Learning Hierarchical Embeddings Hyperbolic entailment cones for learning hierarchical embeddings.  Thirty-fifth International Conference on Machine Learning (ICML 2018).
  * Gao . (2017) gao2017preferenceGao, Z., Ries, C., Simon, HU. Zilles, S.  2017\.  Preference-based teaching Preference-based teaching.  The Journal of Machine Learning Research1811012–1043.
  * Hanneke (2007) hanneke2007boundHanneke, S.  2007\.  A bound on the label complexity of agnostic active learning A bound on the label complexity of agnostic active learning.  Proceedings of the 24th international conference on Machine learning Proceedings of the 24th international conference on machine learning ( 353–360).
  * Hanneke . (2014) hanneke2014theoryHanneke, S. .  2014\.  Theory of disagreement-based active learning Theory of disagreement-based active learning.  Foundations and Trends® in Machine Learning72-3131–309.
  * Hubert Arabie (1985) hubert1985comparingHubert, L. Arabie, P.  1985\.  Comparing partitions Comparing partitions.  Journal of classification21193–218.
  * Khan . (2011) khan2011humansKhan, F., Mutlu, B. Zhu, J.  2011\.  How do humans teach: On curriculum learning and teaching dimension How do humans teach: On curriculum learning and teaching dimension.  Advances in Neural Information Processing Systems Advances in neural information processing systems ( 1449–1457).
  * Langley (2006) AgnosticLangley, P.  2006\.  Agnostic active learning Agnostic active learning.  ICML.
  * Lessard . (2019) lessard2019optimalLessard, L., Zhang, X. Zhu, X.  2019\.  An optimal control approach to sequential machine teaching An optimal control approach to sequential machine teaching.  The 22nd International Conference on Artificial Intelligence and Statistics The 22nd international conference on artificial intelligence and statistics ( 2495–2503).
  * J. Liu Zhu (2016) liu2016teachingLiu, J. Zhu, X.  2016\.  The teaching dimension of linear learners The teaching dimension of linear learners.  The Journal of Machine Learning Research1715631–5655.
  * W. Liu . (2018) DBLP:conf/icml/LiuDLLRS18Liu, W., Dai, B., Li, X., Liu, Z., Rehg, JM. Song, L.  2018\.  Towards Black-box Iterative Machine Teaching Towards black-box iterative machine teaching.  Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018 Proceedings of the 35th international conference on machine learning, ICML 2018, stockholmsmässan, stockholm, sweden, july 10-15, 2018 ( 3147–3155).
  * Matiisen . (2019) DBLP:journals/corr/MatiisenOCS17Matiisen, T., Oliver, A., Cohen, T. Schulman, J.  2019\.  Teacher-Student Curriculum Learning Teacher-student curriculum learning.  IEEE Transactions on Neural Networks and Learning Systems.
  * Mei Zhu (2015) mei2015usingMei, S. Zhu, X.  2015\.  Using machine teaching to identify optimal training-set attacks on machine learners Using machine teaching to identify optimal training-set attacks on machine learners.  Twenty-Ninth AAAI Conference on Artificial Intelligence. Twenty-ninth aaai conference on artificial intelligence.
  * Mitchell . (1997) mitchell1997machineMitchell, TM. .  1997\.  Machine learning. 1997 Machine learning. 1997.  Burr Ridge, IL: McGraw Hill4537870–877.
  * Nickel Kiela (2018) nickel2018learningNickel, M. Kiela, D.  2018\.  Learning Continuous Hierarchies in the Lorentz Model of Hyperbolic Geometry Learning continuous hierarchies in the lorentz model of hyperbolic geometry.  Thirty-fifth International Conference on Machine Learning (ICML 2018).
  * Nitta Kuroe (2017) nitta2017hyperbolicNitta, T. Kuroe, Y.  2017\.  Hyperbolic gradient operator and hyperbolic back-propagation learning algorithms Hyperbolic gradient operator and hyperbolic back-propagation learning algorithms.  IEEE transactions on neural networks and learning systems2951689–1702.
  * Roy McCallum (2001) roy2001towardRoy, N. McCallum, A.  2001\.  Toward optimal active learning through sampling estimation of error reduction. Int. Conf. on Machine Learning. Toward optimal active learning through sampling estimation of error reduction. int. conf. on machine learning.  Morgan Kaufmann.
  * Rubens . (2011) rubens2011activeRubens, N., Sheinman, V., Tomioka, R. Sugiyama, M.  2011\.  Active Learning in Black-Box Settings Active learning in black-box settings.  Austrian Journal of Statistics401-2125–135.
  * Sarkar (2011) sarkar2011lowSarkar, R.  2011\.  Low distortion delaunay embedding of trees in hyperbolic plane Low distortion delaunay embedding of trees in hyperbolic plane.  International Symposium on Graph Drawing International symposium on graph drawing ( 355–366).
  * Seung . (1992) seung1992querySeung, HS., Opper, M. Sompolinsky, H.  1992\.  Query by committee Query by committee.  Proceedings of the fifth annual workshop on Computational learning theory Proceedings of the fifth annual workshop on computational learning theory ( 287–294).
  * Shinohara Miyano (1991) shinohara1991teachabilityShinohara, A. Miyano, S.  1991\.  Teachability in computational learning Teachability in computational learning.  New Generation Computing84337–347.
  * Tang Huang (2019) tang2019selfTang, YP. Huang, SJ.  2019\.  Self-paced active learning: Query the right thing at the right time Self-paced active learning: Query the right thing at the right time.  Proceedings of the AAAI Conference on Artificial Intelligence Proceedings of the aaai conference on artificial intelligence ( 33, 5117–5124).
  * Tay . (2018) tay2018hyperbolicTay, Y., Tuan, LA. Hui, SC.  2018\.  Hyperbolic representation learning for fast and efficient neural question answering Hyperbolic representation learning for fast and efficient neural question answering.  Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining Proceedings of the eleventh acm international conference on web search and data mining ( 583–591).
  * Tong Koller (2001) tong2001supportTong, S. Koller, D.  2001\.  Support vector machine active learning with applications to text classification Support vector machine active learning with applications to text classification.  Journal of machine learning research2Nov45–66.
  * Tosh Dasgupta (2017) tosh2017diameterTosh, C. Dasgupta, S.  2017\.  Diameter-Based Active Learning Diameter-based active learning.  International Conference on Machine Learning International conference on machine learning ( 3444–3452).
  * Tran . (2020) tran2020hypermlTran, LV., Tay, Y., Zhang, S., Cong, G. Li, X.  2020\.  HyperML: A Boosting Metric Learning Approach in Hyperbolic Space for Recommender Systems. Hyperml: A boosting metric learning approach in hyperbolic space for recommender systems.  WSDM Wsdm ( 609–617).
  * Vapnik (2013) vapnik2013natureVapnik, V.  2013\.  The nature of statistical learning theory The nature of statistical learning theory.  Springer science & business media.
  * Vinh . (2010) vinh2010informationVinh, NX., Epps, J. Bailey, J.  2010\.  Information theoretic measures for clusterings comparison: Variants, properties, normalization and correction for chance Information theoretic measures for clusterings comparison: Variants, properties, normalization and correction for chance.  The Journal of Machine Learning Research112837–2854.
  * Yu . (2006) yu2006activeYu, K., Bi, J. Tresp, V.  2006\.  Active learning via transductive experimental design Active learning via transductive experimental design.  Proceedings of the 23rd international conference on Machine learning Proceedings of the 23rd international conference on machine learning ( 1081–1088).
  * J. Zhu (2013) zhu2013machineZhu, J.  2013\.  Machine teaching for bayesian learners in the exponential family Machine teaching for bayesian learners in the exponential family.  Advances in Neural Information Processing Systems Advances in neural information processing systems ( 1905–1913).
  * X. Zhu (2015) zhu2015machineZhu, X.  2015\.  Machine teaching: An inverse problem to machine learning and an approach toward optimal education Machine teaching: An inverse problem to machine learning and an approach toward optimal education.  Twenty-Ninth AAAI Conference on Artificial Intelligence. Twenty-ninth aaai conference on artificial intelligence.
  * X. Zhu . (2018) zhu2018overviewZhu, X., Singla, A., Zilles, S. Rafferty, AN.  2018\.  An overview of machine teaching An overview of machine teaching.  arXiv preprint arXiv:1801.05927.