Nonparametric Teaching for Multiple Learners
Authors: Chen Zhang
Xiaofeng Cao
Weiyang Liu
Ivor Tsang
James Kwok
Venue: NeurIPS 2023 poster (2023)
Keywords: Nonparametric machine teaching
Multiple learners

Abstract: We study the problem of teaching multiple learners simultaneously in the nonparametric iterative teaching setting, where the teacher iteratively provides examples to the learner for accelerating the acquisition of a target concept. This problem is motivated by the gap between current single-learner teaching setting and the real-world scenario of human instruction where a teacher typically imparts knowledge to multiple students. Under the new problem formulation, we introduce a novel framework -- Multi-learner Nonparametric Teaching (MINT). In MINT, the teacher aims to instruct multiple learners, with each learner focusing on learning a scalar-valued target model. To achieve this, we frame the problem as teaching a vector-valued target model and extend the target model space from a scalar-valued reproducing kernel Hilbert space used in single-learner scenarios to a vector-valued space. Furthermore, we demonstrate that MINT offers significant teaching speed-up over repeated single-learner teaching, particularly when the multiple learners can communicate with each other. Lastly, we conduct extensive experiments to validate the practicality and efficiency of MINT.

Nonparametric Teaching for Multiple Learners
Chen Zhang' Xiaofeng Cao 1M44
Weiyang Liu Ivor W. Tsang' James T. Kwok School of Artificial Intelligence, Jilin University, China Max Planck Institute for Intelligent Systems, Germany, University of Cambridge, UK 'CFAR and IHPC, Agency for Science, Technology and Research (A*STAR), Singapore 'Hong Kong University of Science and Technology, Hong Kong. China u35678318comnee hku, hk, xiaxf rigooong edu. en, x13960cam ac. uk ivor tsangdcfar a-starr edu, ag, waw.aar.dd.....mssss......e jameskkdse.e.........e..o ust.hk
Abstract
We study the problem of teaching multiple leamners simultancously in the nonpara- metric iterative teaching setting, where the teacher iteratively provides examples to the learner for accelerating the acquisition of a target concept. This problem is motivated by the gap between current single-learner teaching setting and the real-world scenario of human instruction where a teacher typically imparts knowl- edge multiple students. Under the new problem formulation, we introduce a novel framework Multi-leamner Nonparametric Teaching (MINT). In MINT, the teacher aims to instruct multiple learners, with each learner focusing learning a scalar-valued target model. To achieve this, we frame the problem as teaching a vector-valued target model and extend the target model space from scalar-valuce reproducing kernel Hilbert space used in singlc-learner scenarios to a vector-valued space. Furthermore, we demonstrate that MINT offers significant teaching speed- up over repeated single-learne teaching, particularly when the multiple learners can communicate with each other. Lastly, we conduct extensive experiments validate the practicality and efficiency of MINT.
Introduction
Machine teaching [81, 83] considers the problem of how to design the most effective teaching set, typically with the smallest amount of (teaching) examples possible, facilitate rapid learning the target models by learners based on these examples. It can be thought of as an inverse problem of machine learning, the sense that the student aims learn target model on given dataset, while the teacher constructs such a (minimal) dataset. Machine teaching has many applications in computer vision [67, 68), crowd sourcing [59, 60, 78, 79] and cyber security [2, 3, 39, 53].
Roughly speaking, machine teaching can be carried out in a batch [80, 81, 33] or iterative [36, 37, 38, 52] fashion, depending on how teachers and learners interact with each other. Batch teaching focuses single-round interaction, that is, the most representative and effective teaching dataset are designed be fed the learner in one shot. After that, the leaner solely and assiduously learns target model from this dataset without further interaction. With practical considerations, iterative teaching extends such single-round mode multi-round one. It studies the case where the teacher feeds examples based on learners' status (current learnt models) round by round, such that the learner can converge to a target model within fewer rounds. The minimal count of such rounds (or iterations) is referred to as iterative teaching dimension [36, 37].
Considering that previous works on iterative machine teaching usually limit target models in parameterized family, that is, assuming the target model can be represented by some parameters, nonparametric iterative machine teaching [73] extends such single family general nonparametric one. This allows multiple possibility of the target model family. Specifically, by formulating nonparametric teaching in reproducing kernel Hilbert space (RKHS), [73] introduce various families of target models associated with kernels, e.g., Gaussian and Laplacian kernels in RKHS.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

However, existing nonparametric teaching only focuses on the single- learner setting (i.e., teaching a scalar-valued target model or func- tion to a single learner), and it is computationally inefficient to carry out this same single-learner teach- ing repeatedly for the multi-learner scenario, where the teacher needs to teach numerous realar-valued target functions to multiple learners and a single learner can only learn one. For example, when taking colored picture with three (RGB) channels a multi-learner target function! (e.g., [62, 20D, the iteration num- ber of repeatedly performing single- learner teaching for each channel intuitively triple that of carry- ing out them simultaneously. An- other example is the scenario where the single-learner target model hav- ing a large input space. Such a model can be divided into multiple smaller ones with an input space of appropriate size, and these smaller models can formulated together into multi-learner target model [7, 64, 66, 61, 74]. Concretely, one can divide a single nigh-revolution picture into multiple sub- regions, and the original single-lcaneer target function will become multi-learner one. These examples motivate us to study a generalized framework, called multi-lcarner nonparametric teaching (MINT), where vector-valued target model (instead of a scalar-valued model) is being taught. A comparison between single-learner teaching and MINT is illustrated in Figure 1.
Singlelramer oepuraamtrrc teaching
neget monoctrome
Multi meltt-leorner nomparametric teaching
The tngel ooloced one with RGB channels
(h2) Muttt-teerner nonparamettle teaching
The target colored oue
pieces
Figure I: Comparison hetween the single-learner teaching and MINT. (a) In order to facilitate single-learner teaching, it is imperative to transform colored image into grayscale format. (bl) MINT allows for the simultaneous teaching three scalar-values target models. which are three (RGB) channels of a colored image. (b2) Partitioning a single image into multiple pieces and teaching them concurrently is also considered as form of MINT.
It is therefore of great significance to generalize the recent single-learner nonparametric teaching [73] to MINT [11, 14, 77J. MINT is guided by the insight that repeatedly (or sequentially) teaching multiple scalar-valued target functions can be viewed as teaching a vector-valued target function. The theoretical motivation comes from the well-developed results of kernels for vector-valued functions [56, 44, 21]. important approach to deal with multiple data sources. This inspires to formulate MINT as a teaching problem of a vector-valued target function, where sequentially teaching multiple scaler-valued functions (for single-learner teaching) becomes special case of teaching vector- valued function [43, 21, 14]. We emphasize that, compared to the case where a single learner is learning vector-valued target function, the multi-learner setting offers general framework that can be generalized to more complicated scenarios, e.g., learners operate within different feature spaces, and learners are able to communicate with each other. We summarize our major contributions below:
By analyzing general vector-valued RKHS [10, 45, 4], we study the multi-learner nonparametric teaching (MINT), where the teacher selects examples based on vector-valued target function (each component of the vector-valued function a ecalar-vauued function for a single learner) such that multiple learners can learn their own target models simultaneously.
By enabling the communication among multiple learners, learners can update themselves with a linear combination of current learnt functions of all learners [23, 12). study communicated MINT where the teacher not only selects examples but also injects the guidance of communication.
Under mild assumptions, we characterize the efficiency of our multi-learner generalization of nonparametric teaching. More importantly, we also empirically demonstrate its efficiency.
'Each channel in colored picture be viewed as single- leamner valuue) target function whose inputs and outputs are the pixel location and values, respectively [73].
'When components of it are highly correlated with each other, the teacher in each iteration can select teaching set based one component, and use to teach all learners simultancously.

---

2 Related Works
Machine teaching. Recently, there has been a surge of interest in the field of machine teaching,
see [81, 83, 36, 37, 67] and references therein. Batch machine teaching has examined the behaviors of various types of learners, including linear learners [33], forgetful learners [27. 37], version space learners [13, 65], hypothesis learner [40] and reinforcement learners [29, 76]. Further, by
extending the single-round teaching mode to a multi-round one, iterative teaching has attracted
growing attention in recent studies [36, 37, 40, 50, 32, 38, 69, 52, 73J. Specifically, [38] focuses on label synthesis teaching, while [52] proposes generative teaching. Additionally, [73] relaxes target models and generalizes the previous iterative teaching to nonparametric iterative one [30, 51]. In contrast to previous works that mainly concentrate on the single-learner teaching, this work aims to address more practical task teaching multi-lcarner (vector-valued) target models. In this regard, the realistic practical scenario, classroom teaching [82, 711, is highly relevant, where it examines multiple learners by partitioning them into groups in batch and iterative setting, respectively. However, their works are also limited to the parametric setting, and their methods therefore are not immediately generalizable to nonparametric situations. In contrast, our work investigates multi-learner teaching in the nonparametric setting.
the parametric assumption
Multi-task functional optimization. Functional optimization [58, 6, 58, 22, 84, 63, 75] is fun- damental and significant task in various fields, such as variational inference [35, 34], barycenter problem [57, 70]. and Residual Networks [48, 49, 26]. It involves mapping from input to output without having pre-defined parameters, optimized over a more general function space such as the reproducing kernel Hilbert space (RKHS), Sobolev space [1, 46], and Fréchet space [47]. Notably, the functional gradient descent algorithm has been studied extensively for functional optimization in RKHS due to its regular properties [41, 42, 16, 35, 46, 5, 57]. Meanwhile, modeling in RKHS of vector-valued valued functions [56, 21, 44, 10, 9, 14, 19, 45] is an important approach to handle multi-task problem. Specifically, [21, 9, 4] focus on the analysis of the kernel and [28, 12] study multi-task versions of online mirror descent, which displays the similarity to multi-learner teaching in the sense of simultaneous execution. These theoretical and empirical works motivate to extend single-leamer teaching to a multi-lcarner one by analyzing functional gradient in vector-valued RKHS.
3 Background
Notation. Let X' C R. be n dimensional input (iee. feature) space and y C TK be a output (i.e., label) space. By X = Xi x ... x Xa S Raax we denote a d-learner input space, and let ndd -1 x ... x Va C Ied be d-larner output space. Let a d-dimensional column vector with a, entries indexed by i E Na (N₂ = (I. kk), be [a,] (a1,... "aa)""".,aa" (we may denote it by for simplicity), and a 1-vector of size d be [1] = (1, vector of matrix M, and let M(.)) be its i-th column vector. d-learner teaching sequence in size d x k is a collection of examples, notated as D = {(I,,), V1.)) E X y)3 with the learner index i Na and the example index j E N₂. We notate the collection of such teaching sequence candidates by Dd D. which is referred to as the knowledge domain of the teacher [36].
1)" E Rd. By M(s..) we denote i-th row
Let K(x, x') X x X' + be a scalar-valued positive definite kernel function, which can be K2 K=(x') = K=*(a), and one can abbreviate Kz(-) by Kz-
equivalently notated by K(x,, ((x,,'') The scalar- valued reproducing kernel Hilbert space (RKHS) H defined by K(x, x²) is the closure of linear span {f= f(.) = > K(K,, +), E R E N, E X} equipped with inner product (f, g) Rt = Enj 3, K(], 2,) when g = Σ, 3,Kay. We assume that given the scalar- valued target model fz E H. one can uniquely identify a teaching example by its æt for brevity, (0ttt)= (xt (xx)) Let Hd = H, ... Ha be a RKHS of vector-valued functions f = =[r]] Ei= (Si,gi) H. For simplicity, we use the vector-input K (x, x²)= = [K(2,,z)) = to denote kernels in vector-valued RKHS H.d For a functional F: Hd + R, its Fréchet derivative [16, 34, 57] is defined as following:
with / E H,', equipped with inner product (f,g)
'To avoid clutter in the notation, we assume that all learners share same input and output spaces, i..., X; = X and V. Y. The results for different input and output spaces can be derived by plugging into specific X, and yi directly.
'To simplify the notation, we assume that the RKHS of target models are the same for all learners, ie..
H. = H.
3

---

Definition 1. (Fréchet derivative in vector-valued RKHS) For vector-valued functional F
Hd + R, its Fréchet derivative V F(fi f HD is defined implicitly as Flf eg)
FVV 9) n ((2)) ( for any g E Hd and E R, which a function Hd.
Using the Riesz-Fréchht representation theorem [5], the evaluation functional of vector-valued functions is defined in the following:
Definition 2. For vector-valued reproducing kernel Hilbert space H with positive definite kernel
Ke E H. where æ = [1...1 E x and the example index ji E Nh. we define evaluation functional Ex [1] Hd + I8 as
[x (f, (n = CS,
Σ f(lrss) = (fi,'. fa)" E Hd.
(1)
Single-learner nonparametric teaching. [73] formulates the single-learner nonparametric teaching as functional minimization over leageer D in scalar-valued RKHS:
D arg min DED
M(f*, fr) + X len(D)
s.t. A(D)
(2)
where M is disagreement between fo and f (e.g., L2 distance defined in RKHS M(f
ff==f"llz len(-) is the length of the teaching sequence D (i.e., the ITD defined [36]) controlled by a regularized constant X, and A denotes the learning algorithm of learners. Usually, A(D) is taken as empirical risk minimization:
= arg min ((ew))-((a (C((())
(3)
FEH
with single-learner convex loss function C. As introduced in Section 1, iterative teaching [36, 37] focuses on some specific optimization algorithm that the learner adopts [38]. the nonparametric setting, we consider the functional gradient descent:
t f² - (D)
where I...., I' serves as an iteration index, 1/' 0 (i.e., small constant) denotes the learning rate for the t-th iteration, and G represents the gradient functional evaluated at D
Specifically, [73] investigates the teaching algorithms within a practical teaching protocol and gray- box setting. This involves a teacher that has no knowledge about the learner, including the learning rate and specific loss function, but still is able to keep track of the learnt model during each iteration. Two functional teaching algorithms are proposed: Random Functional Teaching (RFT) and Greedy FT (GFT). The former essentially adopts random sampling, and it serves as simple baseline, which can also be viewed as functional analogue of stochastic gradient descent [54, 25]. In contrast, GFT picks examples by maximizing the corresponding disagreement between the target and current models [5, 18], and has been shown to be more effective than RFT both theoretically and experimentally.
4 MINT: Multi-learner nonparametric teaching
In this section, we begin by defining multi-learner nonparametric teaching as functional min- imization in vector-valued RKHS. Next, we analyze vanilla MINT where multiple learners independently and simultaneously learns corresponding components of a vector-valued target func- tion. Lastly, we investigate communicated MINT where the teacher does not only provide examples but also guide multiple learners in the process of linearly combining present learnt functions.
4.1 Teaching settings
To define MINT, we expand scalar-valued target models in single-learner teaching to vector-valued ones and modify other notations to suit the multi-learner setting. More specifically, we redefine functional minimization of Eq. 2 as follows:
D' arg min
M(frf) + Ien s.t. f==A(D)
DeLd

---

where f H. refers to vector-valued target model, and other notations bear the same meaning as Eq. 2. The learning algorithm A arrives at the following solution:
f arg min (a.))) (=).
(6)
fEH
where (z, v) E X' x ya and (æ, y) ~ (2; ys y: Evaluated at an example vector (æ; y) [(ris (...,,,b....)) V6.. with the example index ji E Ne. the multi-learner convex loss therein
=
d
((f(x))))) Σ (. F.z
(7)
where L, is the convex loss for i-th learner. We can also express as {[1]4, (f (...)))))))))) ) where the vector [1] can be replaced by weight vector [w:] Rd adjust the significance of each learner relative to others. Under iterative setting [36, 37] which explores teaching algorithms from the viewpoint of optimization and approximation, we present vector-valued functional gradient descent:
fxt + A' f - ny' o g(C; A'
f';
(8)
where @ denotes the element-wise multiplication, ny' = [m: (1/1 ....... ma) T is a vector of learning that corresponds
learners and the communication matrix A arg min AgR || I' Ill signifies a matrix with row sums that are equal to one in order to maintain the output's
scale. Equivalently, by denoting that A (..) arg min ERIIA y [| (f.) f fill it can also be
expressed in learner-specific (i.e., component fashion f. f Ale.) ft (C:
f"; D"), where e Na is the learner index.
We investigate MINT in the gray-box setting, which is equivalent to the one considered in [73]. To facilitate the theoretical analysis, we adopt some moderate assumptions regarding L; and kernels, which align with those made [73].
Assumption 3. Each loss Li(J)), E Na is Lcc, -lipschi smooth, i.e., VSa E H. x, E & and i Nd
ER, [VC((f) Ez, (VC((fI) S Lc, Ex. [fi] Ez, [fill, where Lcc 2 is constant. simplify the notation, we assume that I.c, = for all E Na Assumption 4. Each kernel ((x,x') H is bounded, i.e., Vx, E X, K(x,x') s MR, where Mx 2 0 is constant.
With regards to diverse knowledge domains, narrow the scope of investigation in this study the synthesis-
teacher setting [36]. Furthermore, it's worth noting that by limiting the knowledge domain specific pool, it can result in multiple learners converging to suboptimal fr such findings of pool-based teachers are comparable and can be deduced accordingly, as discussed in Remark 7 of [73].
4.2 Vanilla multi-learner teaching
In tackling MINT, we begin by examining basic scenario which multiple learners concurrently learns corresponding components of a vector-valued target function without communication between them [28. 12], that is, A' in Eq. is assigned the identity matrix Ig. This simplifies Eq. 8 to
fi+1 + f n 2 (C: f DD;
In this vanilla setting, multiple learners do not linearly combine learned functions of all learners; rather, it updates its functions by Eq. alone.
In light of the definition of Fréchet derivative in vector-valued RKHS (as presented Defi. I), we present Chain Rule for vector-valued functional gradients [24] Lemma.
Lemma 5. (Chain rule for vector-valued functional gradients) For differentiable functions G R +
I that are functions of functionals F. G(F)f),, the expression
(G(F
G(F(())
f F[F]]]
(10)
is usually referred to the chain rule.
5

---

To obtain the derivative of the evaluation functional [16], we introduce Lemma 6, with the proof of this lemma deferred to Appendix B.
Lemma 6. For an evaluation functional in vector-valued RKHS Ex = Ei= f((2).,) Hd + where x= = [maaj.] E x2,, its gradient is a d-dimensional vector F = K = 5k 1 E Hd.
R
Using Lemma 5 and Lemma 6, we offer an expansion viewpoint on the vector- valued functional gradients of [41, 16]: Suppose we have a specific example vector (æz, y) = j I x² x ydd the gradient g of the multi-learner loss function L w.r.t. the vector-valued model f can be expressed by
( (x. = p
K Kanss
(11)
We also broaden the applicability of RFT and GFT from their single-learner versions [73] to multi-learner one. Under this context, RFT involves randomly picking examples for each learner, while GFT selects examples that satisfy
d Hd
x
arg max dex)
y" -
-"' 17
(12)
To avoid clutter in the notation, examination is restricted to the selection of a single example for each learner during every iteration, and we provide the pseudo code in Appendix A.
In the upcoming discussion, we shall present our theoretical examination of the convergence perfor- mance of multi-learner RFT and GFT. Our approach differs from [73] as we focus on RFT's average performance by introducing the expectation operation over random sampling. This helps gain valuable insights by averaging out the impact of randomness. Recall the teaching settings (Eq. 6, 9), we then proceed with our analysis of RFT's per-iteration reduction concerning L.
Lemma 7. (Sufficient Descent for multi-learner RFT) Suppose there are d learners, and the example mean for each learner is 44 (E,,- ((:))(,))) (I;) < cc, and the variance of (E,,P,((z) (az; 14)² o0, Na- Under the assumptions outlined in both 3 and 4, vh S 2Lee for all E Na then RFT teachers can, on average, reduce the multi-learner loss L(f) by:
7
(a(i)l (C(f++1)-((C) -
S
(ma,((a))
o?),
(13)
2
2=1
where of = minien, of and mi,((t) = ( (,)1(
Intuitively, (14) serves as measure of the gradient's magnitude (loss L. w.r.t. f for the i-th learner at the example mean μi in the 1-th iteration, and as J approaches fú, ( becomes increasingly small. According to Lemma 7, as proven in Appendix B, the average reduction of multi-learner loss C per iteration is constrained by a negative upper bound. To be more precise, this upper bound is determined by range of elements, such as the learning rate, the count of learners, the example variance o² and the gradient of L; at the example mean μ4: (i E Na), and these elements independent of each another. When the gradient each μ4 is large, RFT on average reduce C by a significant amount. Meanwhile, the variance also has an impact on the reduction and this is governed by diminutive constant of m (P..)2.
The least helpful teaching scenario in the I-th iteration across the d learners represented by minieN, (fa) + mn (1: (o /2), which has the smallest gradient at the example mean. It is observed from Lemma that the reduction of C per iteration is, at a minimum, d times greater than that of the worst-case scenario -n²² /2- min.eN, (m,)((p)) + m" ((. multi-learner RFT achieves a stationary point in the worst-case scenario. the multi-learner loss L reaches convergence as well. This indicates that the convergence rate of multi-learner RFT is at least as fast as in the single-learner worst-case scenario (also faster than repeatedly teaching).
(m,)a )oū /2). /2). In other words, when
Introducing the expectation operation enables us to eliminate the randomness that arises from random sampling. In contrast to [73], which determines the decrease based on the discrepancy at specific but randomly chosen example x! (involving randomness). we establish that the decrease on average determined by the mean and variance. This valuable insight important to understand the fundamentals of RFT, which is not considered in [73].

---

Theorem 8. (Convergence for multi-learner RFT) Suppose the vector-valued model for multiple learners is initialized with f E Hd and returns f HH' after iterations, we have the upper bound of minseN, (m) + m (14)00/2 w.r.l. t:
min (p:)) + m - (4())) S 2B [C(F9] /(dit), iENa
(14)
गे - 1/(2Lc Mk), and given a small constant > 0 it would take approximately (B..).) [c (fo)] /(drjc) iterations to reach a stationary point.
where 0 < <i
min (0)
The proof for Theorem can be found Appendix B. Theorem 8 tells that the minimum of the non- negative term within the upper bound in Theorem 7, which is minseN, (m,,)(4 + =m",, (1x)) is also upper bounded, and the iterative teaching dimension is 2[)x.)))( [C(f") /ddiee.
In comparison to RFT, GFT achieves a larger reduction in multi- loss & per iteration, suggesting a faster convergence rate and lesser number of iterations required to achieve convergence.
Lemma 9. (Sufficient Descent for multi-learner GFT) Under Assumption 3 and 4. if T S Mx for all i E Nd. the GFT teachers can achieve a greater reduction in the multi-learner loss L:
1
7
(.)() [C( [(F)] S
m
(15)
2 1=1
where ij and m.,e(.) retain their previous meaning.
The proof of the Lemma 9 is presented in Appendix B. GFT selects examples with the steepest gradient, which leads to (=. 2 (ma) + m (m.)o /2) for each learner. Consequently, it can be observed that per-iteration C reduction of GFT has a tighter bound compared to RFT. This is due the fact that GFT uses a greedy approach select examples that maximizes the norm of difference between the current and target models. This allows the learners to take a larger step forward f in per iteration. The tighter bound provides theoretical evidence supporting the effectiveness of GFT, which is consistent with the findings in the single-leamer teaching [73].
Theorem 10. (Convergence for multi-learner GFT) Suppose the vector-valued model for multiple learners is initialized with for E Hd and returns f E HD after t iterations, we have the upper bound of minign, ma,( w.r.l. t:
[-1 d
min M (x) 1x RENA
< -EE Bm- [c(
2 dijl.
+ di
||= - -millz)
(16)
t-
where i) has the same definition as before.
It follows from Lemma 7 and 9 that when x! is close to μ4; for i Na, then GFT and RFT perform similarly. In Theorem 10 (The proof is given in Appendix B), we theoretically show this relation by introducing the distance between 24" and μ4g, which provides deep insight of the difference between RFT and GFT that is not considered in [73]. Specifically, the per-iteration loss reduction under both RFT and GFT has negative upper bounds, and the difference between these two upper bounds can be seen by comparing Theorem 8 and Theorem 10. From a qualitative perspective, GFT can achieve better convergence speed-up because its negative upper bound can take smaller values than that of
RFT. This gap is characterized by 2 Σ'D Σ (Ia! - milla) which is the cumulative distance
between select of" and mean (4, for all learners and averaged over iterations. We emphasize that the purpose of our results is to show the difference between RFT and GFT, rather than proving that GFT always achieves better convergence than RFT (which is not always true). By comparing Theorem and Theorem 10, we can learn that it is possible for GFT to have larger per-iteration loss reduction than RFT. However, we also recognize the intrinsic difficulty to show the exact conditions such that GFT can always be better than RFT. In contrast to our results, the parametric case (e.g., [36] also has not obtained the necessary and sufficient conditions for greedy teaching to be better than random teaching. More generally, [38] also considers some alternative teaching strategies other than the greedy teaching, such as the parameterized teaching with multi-iteration reward function. Despite not being able to fully characterize the difference of convergence rate between GFT and RFT, our existing theoretical analysis still poses an important open problem: when and how can GFT provably achieve faster convergence than RFT?
7

---

L220
(a) Single-Iearner teaching
(b) Vanilla MINT
(c) Single-learner teaching
(d) Vanilla MINT
Figure 2: Comparison between single-learner teaching and MINT. (a) Repeatedly invoking single-learner GFT: teaching white tiger first and subsequently teaching cheetah. (h) Simultaneous teaching of white tiger a cheetah by GFT. (c) Single-learner teaching the lion. (d) Partitioning a single lion image into 16 pieces and teaching them concurrently.
Sigh de Naciia OFt
Derrtionn
E
Berabon
Roratient
(a) Tiger & cheetah.
(b) Gray lion.
(c) RGB lion.
Figure 3: Comparison of convergence performance between single-learner teaching and MINT. (a) is corre- sponding to (a)-(b) in Figure 2. (b) is for (c)-(d) in Figure 2. (c) pertains to teaching of a colored lion.
4.3 Communicated multi-learner teaching
An infant would often compose previously learnt knowledge in order to grasp new target concept, such as understanding what a zebra is by combining the learnt ideas of horses and black-and-wy -nd-whtte stripes. Such an efficient learning motivates us to explore the idea of communicated MINT, which enables the communication between learners. other words, multiple learners can execute linear combination on the currently learnt functions of all learners [21, 23, 77, 12], that is, A' is no longer constrained to be an identity matrix.
In practice, to direct this communication, the teacher can utilize a two-layer perceptron (MLP) to derive the matrix A' in Eq. 8 by searching a matrix A that minimizes ||Af Il as much as possible, which is an addition step beyond example selection in each iteration.
Proposition 11. the proximity between fs and f is sufficiently close, meaning that off--flle S where is a tiny positive constant, then A' equals the identity matrix Ia-
The proof of Prop.11 is given in Appendix B. This suggests that there is need for MLP to be used in solving matrix A in every iteration, but only at the beginning, because as the iterations progress, I will approach near f
Lemma 12. Under Assumption 3, the communication across learners will result in a reduction of the multi-learner corvex loss C by L(f') C(A' fO) < 2L fl
Proof of Lemma 12 is given in Appendix B. The difference in between the case where the communication exists and that where it doesn't 't is lower bounded by zero and upper bounded by the distance between f and f This suggests that if f is far from f*, then matrix A' can potentially decrease L significantly at the best case while not causing any increase at the worst case.
Theorem 13, Suppose the communication in the t-th iteration of multiple learners is denoted by the matrix A and returns firt E Hd, for both RFT and GFT we have:
Em-(P((a))) [C(ft)])= -(f*)) & Em [C( C(A' 5.
(17)
8

---

(a) Single-learne teaching.
(b) Vanilla MINT.
1-3000
1-99000 10200006
b-150900 1-22000
(c) Communicated MINT.
Figure 4: Visualization of ff taught by GFT. Starting from random initialization, the communicated multi-
leamner GFT help multiple learners learn a more clear image than the vanilla one followed by single-lcarner one.
Proof of Theorem 13 is in Appendix B. This shows that the addition communication has led to an improvement model updates, which evident from the larger loss discrepancy between f++1 and f compared to the difference observed between f and A A'
5 Experiments and Results
Testing the teaching of multi-learner (vector-valued) target model, MINT presents more satisfactory performance than repeatedly carrying out the single-learner teaching. which is consistent with our theoretical findings. Detailed configurations and supplementary experiments are given in the Appendix C.
MINT in gray scale. A grayscale figure can be viewed as 3D surface where the axis corresponds the level of gray, while the x, y axes depict the placement of pixels [73]. We consider two scenarios: one involves the simultancous teaching of a tiger and a cheetah figure, while the other focuses on the teaching of a lion. After comparing (a) and (b) in Figure 2, we see that when teaching two target functions by GFT simultaneously. the vanilla MINT requires almost half the number of cost iterations compared Ingle-learner teaching, which also evident from the loss plot shown in Figure 3 (a). By comparing (c) and (d) in Figure 2, we can observe that dividing single-learner target figure into smaller pieces and recasting them into MINT can significantly improve the efficiency, which also demonstrated by the loss plot in Figure 3 (b).
MINT in three (RGB) channels. To further demonstrate the benefits of communication, we examine with lion image with three channels in RGB format. The loss plot in Figure 3 (c) reveals that the efficient teaching is the communicated MINT for both RFT and GFT. The vanilla MINT and single-learner teaching follow in order of decreasing efficiency. Furthermore, as anticipated, the multi-learner GFT proves to be more efficient compared RFT. One intriguing observation that the communicated MINT leads to significant reduction in multi-learner loss at the outset, which aligns with our theoretical findings Lemma 12 and confirms the validity of Prop. 11 that A' could eventually become an identity matrix after numerous iterations. Figure compares the specific learnt f' for three versions of GFT during each iteration, wherein we observe that MINT consistently outperforms the single-lcarne one, and the learnt image under the communicated MINT is more clear compared to that the vanilla one. be more persuasive, we also offer detailed and additional
Our source code available https: httptttttt.t////////////tt com/
/MINT http:p///pnpttoooooooerrrrrroooo

---

experiments in Appendix, including channel-win wwse visualization of specific f (Figure 7), RFT-taught I' (Figure 8-9) and teaching multiple learners with a particular initialization of fr (Figure 11-10), which includes an extreme case that only one-time communication is sufficient to help multiple learners learn f (Figure 15).
Concluding Remarks and Future Work
In this paper, we seek to address a practical limitation of current nonparametric iterative machine teaching by enabling the teaching of multi-learner (vector-valued) target models. This generalization of teaching ability involves generalizing the model space from space of scalar-valued functions to that of vector-valued functions. order to address multi-learner nonparametric teaching, we start by analyzing vanilla MINT where the teacher picks examples based on vector-valued target function such that multiple learners can learn its components simultaneously. Additionally, we consider the communicated MINT (i.e., multiple learners allowed carry out linear combination current learnt functions) for further exploration. Through both theoretical analysis and empirical evidence, demonstrate that the communicated MINT more efficient than the vanilla MINT.
Moving forward, could be interesting to explore other practical aspects related to nonparametric teaching. This will involve deeper theoretical understanding and the development of more efficient teaching algorithms. Besides, would be intriguing to establish connections between MINT and multi-output neural networks, which can further enhance its practical applications such knowledge distillation. Moreover, generating teaching examples with surrogate objective that does not need target model (e.g., black-box teaching) is also important direction (e.g., [17, 72]). More generally, (iterative) machine teaching is intrinsically connected to the recent popular data-centric Al. Understanding data-centric learning (e.g., text prompting, data augmentation, data distillation) may require a deeper understanding towards (iterative) machine teaching.
Acknowledgements
This work was supported in part by National Natural Science Foundation of China (Grant Number: 62206108), in part by Maritime AI Research Programme (SMI-2022-MTP-O5 and AI Singapore OTTC Grant AC-SG2-TC-2022-0066 and in part by the Research Grants Council of the Hong Kong Special Administrative Region (Grant 16200021).
References
[1] Robert Adams and John JF Fournier. Soboler spaces. Elsevier, 2003. 3
[2] Scott Alfeld, Xiaojin Zhu, and Paul Barford. Data poisoning attacks against autoregressive models. In AAAI, 2016.
[3] Scott Alfeld, Xiaojin Zhu, and Paul Barford. Explicit defense actions against test-set attacks. In AAAI, 2017.
[4] Mauricio A Alvarez, Lorenzo Rosasco, Neil D Lawrence, et al. Kernels for vector-valued functions: A review. Foundations and Trendso in Machine Learning, 4(3):195-266, 2012. 2,
[5] Michael Arbel, Anna Korba, Adil Salim, and Arthur Gretton. Maximum mean discrepancy gradient flow. In NeurlPS, 2019. 3,
[6] Axel D Becke. Density- functional exchange-energy approximation with correct asymptotic behavior. Physical review A. 3806), 1988.
[7] Jon Louis Bentley. Multidimensional divide-and-conqueer Communications of the ACM, 23(4):214-229,
1980. 2
Dimitri P Bertsekas and John Tsitsiklis. Introduction to probability vol. 2002.
[9] Andrea Caponnetto, Charles A Micchelli, Massimiliano Pontil, and Yiming Ying. Universal multi-task kernels. The Journal of Machine Learning Research, 9:1615-1646. 2008.
[10] Claudio Carmeli, Ernesto De Vito, and Alessandro Toigo Vector valued reproducing kernel hilbert spaces of integrable functions and mercer theorem. Analysis and Applications, 4(04):377-40) 2006. 2,
10

---

[11] Rich Caruana. Multitask learning, Machine learning, 28:41-75, 1997. 2
[12] Nicolò Cesa-Bianche Bianchi, Pierre Laforgue, Andrea Paudice, et al. Multitask online mirror descent. Transactions of Machine Leariing Research. 2, 3,5, 5,8
[13] Yuxin Chen, Adish Singla, Oisin Mac Aodha, Pietro Perona, and Yisong Yue. Understanding the role of adaptivity in machine teaching: The case of version space learners, In NewrIPS, 2018.
[14] Carlo Ciliberto, Youssef Mrouch, Tomaso Poggio, and Lorenzo Rosasco. Convex lcarning of multiple tasks and their structure. /CML, 2015. 2,3
[15] Sebastian Claici, Edward Chien, and Justin Solomon. Stochastic wasserstein barycenters. In ICML, 2018.
23
[16] Rodney Coleman, Calculus normed vector spaces. Springer Science & Business Media, 2012. 3, 6, 16
[17] Katherine M Collins, Umang Bhatt, Weiyang Liu, Vihari Piratla, Ila Sucholutsky, Bradley Love, and Adrian Weller. Human-in-the-loop mixup. In UAI, 2023. 10
[18] Thomas H Cormen, Charles E. Leiserson, Ronald I. Rivest, and Clifford Stein. Introduction to algorithms. MIT press, 2022.
[19] Francesco Dinuzzo, Cheng Ong. Gianluigi Pillonetto, Peter V Gehler. Learning output kernels with block coordinate descent. In ICML, 2011. 3
[20] Emilien Dupont, Hyunjik Kim, SM Ali Eslami, Danilo Jimenez Rezende, and Dan Rosenbaum. From data to functa: Your data point function and you can treat it one. ICML, 2022. 2
[21] Theodoros Evgeniou, Charles A Micchelli, Massimiliano Pontil, and John Shawe-Taylor Learning multiple tasks with kemel methods. Journal of machine learning research, 6(4), 2005.
[22] Jerome H Friedman. Greedy function approximation: gradient boosting machine. Annals of statistics, pages 1189 1000-1222,2220 2001. 3
[23] Peter Gehler and Sebastian Nowozin. On feature combination for multiclass object classification. In ICCV, 2009. 2, 8
[24] Izrail Moiseevitch Gelfand, Richard A Silverman, et al. Calculus of variations. Courier Corporation, 2000.
5, 16
[25] Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize hetter: Stability stochastic gradient descent. In ICMI,, 2016. 4
[26] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In CVPR, 2016. 3
[27] Anette Hunziker, Yuxin Chen, Oisin Mac Aodha, Manuel Gomez Rodriguez, Andreas Krause, Pietro Perona, Yisong Yue, Adish Singla. Teaching multiple concepts to a forgetful learner. arXiv preprint 1tti::880500322.. 2018. 3
[28] Sham M Kakade, Shai Shalev-Shwartz and Ambuj Tewari. Regularization techniques for learning with matrices. The Journal of Machine Learning Research, (3())1886--880 2012. 3,5
[29] Parameswaran Kamalaruban, Rati Devidze, Volkan Cevher, and Adish Singla. Interactive teaching algorithms for inverse reinforcement learning. arXiv preprint arXiv: 11867, 2019.
[30] Akash Kumar, Hanqi Zhang, Adish Singla, and Yuxin Chen. The teaching dimension of kernel perceptron. In AISTATS, 2021.
[31] Peter D Lax. Functional analysis, volume 55. John Wiley & Sons, 2002. 4
[32] Laurent Lessard, Xuezhou Zhang, and Xiaojin Zhu, An optimal control approach to sequential machine teaching. In AISTATS, 2019. 3
[33] Ji Liu, Xiaojin Zhu, and Hrag Ohannessian. The teaching dimension of linear learners. In ICML, 2016.
[34] Qiang Liu. Stein variational gradient descent as gradient flow. In NewrlPS, 2017. 3
[35] Qiang Liu and Dilin Wang. Stein variational gradient descent: A general purpose bayesian inference algorithm. In NewrIPS, 2016.

---

[36] Weiyang Liu, Bo Dai, Ahmad Humayun. Charlene Tay. Chen Yu, Linda B Smith, James M Rehg. and Le Song. Iterative machine teaching. In JCML, 2017. 1,3, 4, 5.
[37] Weiyang Liu, Bo Dai. Xingguo Li, Zhen Liu, James Rehg, and Le Song. Towards black-box iterative machine teaching. In ICML, 2018. 3,3,4,
[38] Weiyang Liu, Zhen Liu, Hanchen Wang. Liam Paull, Bernhard Schölkopf, and Adrian Weller. Iterative teaching by label synthesis. In NeurlPS, 2021. 1, 1,7,4,7
[39] Yuzhe Ma, Xuezhou Zhang, Wen Sun, and Jerry Zhu. Policy poisoning in batch reinforcement learning and control. In NeurlPS, 2019.
[40] Farnam Mansouri, Yuxin Chen, Ara Vartanian, Jerry Zhu, and Adish Singla. Preference preference-based batch and sequential teaching: Towards a unified view of models. In NeurlPS, 2019.
[41] Llew Mason, Jonathan Baxter, Peter Bartlett, and Marcus Frean. Boosting algorithms gradient descent. In NeurIPS, 1999. 6,6
[42] Llew Mason, Jonathan Baxter, Peter L Bartlett, Marcus Frean, et al. Functional gradient techniques for combining hypotheses. In NewrlPS, 1999.
[43] Charles Micchelli and Massimiliano Pontil. Kernels for multi task learning. In NeurIPS, 2004. 2
[44] Charles A Micchelli and Massimiliano Pontil. On learning vector-valued functions. Neural computation, 17(1):177-244 2005. 3
[45] Ha Q Minh and Vikas Sindhwani. Vector-valued manifold regularization. In ICML, 2011. 2,
[46] Youssef Mrouch, Tom Sercu, and Anant Raj. Sobolev descent. AISTATS, 2019.
[47] Lawrence Narici and Edward Beckenstein. Topological vector spaces. Chapman and Hall/CRC, 2010.
[48] Atsushi Nitanda and Taiji Suzuki. Functional gradient boosting based on residual network perception. In ICML, 2018.
[49] Atsushi Nitanda and Taiji Suzuki. Functional gradient boosting for learning residual-like networks with statistical guarantees. In AISTATS, 2020. 3
[50] Tomi Peltola, Mustafa Mert Çelikok, Pedram Dace, and Samuel Kaski. Machine teaching of active sequential learners. In NeurlPS, 2019. 3
[SI] Hong Qian, Xu-Hui Liu, Chen-Xi Su, Aimin Zhou, and Yang Yu. The teaching dimension of regularized kernel learners. In ICML, 2022.
[52] Zeju Qiu, Weiyang Liu. Tim Z Xiao, Zhen Liu, Umang Bhatt. Yueen Luo, Adrian Weller, and Bernhard Schölkopf. Iterative teaching by data hallucination. In A/STATS, 2023. 1,
[53] Amin Rakhsha, Goran Radanovic, Rati Devidze, Xiaojin Zhu, and Adish Singla. Policy teaching via environment poisoning: Training-time time adversarial attacks against reinforcement learning. In ICML, 2020.
[54] Sebastian Ruder. An overview of gradient descent optimization algorithms. 160vv0660.044777 2016.
arXiv preprint
[55] Bernhard Schölkopf. Alexander Smola, Francis Bach, et al. Learning with kemels:: support vector
machines, regularization, optimization, and beyond. MIT press, 2002. 4
[56] Laurent Schwartz. Sous-cspaces hilbertiens d' d'espaces vectoriels topologiques et noyaux associés (noyaux reproduisants). Journal d' a'analyse mathématique, 13:115 256, 1964. 2, 3
[57] Zebang Shen. Zhenfu Wang. Alejandro Ribeiro, and Hamed Hassani. Sinkhorn barycenter via functional gradient descent. In NeurlPS, 2020.
[58] Ivan Singer. The theory of best approximation and functional analysis. SIAM, 1974. 3
[59] Adish Singla. Ilija Bogunovic. G Bartók, A Karbasi, and A Krause. On actively teaching the crowd to classify. In NIPS Workshop on Data Driven Education, 2013. 1
[60] Adish Singla, Iiiaa Bogunovic, Gábor Bartók, Amin Karbasi, and Andreas Krause. Near Neti-opt teaching the crowd to classify. In ICML, 2014.
12

---

[61] Sirotković, H Dujmić, and V Papić. Accelerating mean shift image segmentation with ifgt on massively parallel gpu. In International Convention on Information and Communication Technology, Electronics and Micrvelectronicx, 2013. 2
[62] Vincent Sitzmann, Julien Martel, Alexander Bergman, David Lindell, and Gordon Weizstein. Implicit neural representations with periodic activation functions. In NeurlPS, 2020.
[63] M Smanski, Swapnil Bhatia, Dehua Zhao, YongJin Park, Lauren BA Woodruff, Georgia Giannoukos. Dawn Ciulla, Michele Busby, Johnathan Calderon, Robert Nicol, et al. Functional optimization of gene clusters by combinatorial design and assembly. Nature biotechnology. 32(12):1241 2014. 3
[64] Douglas R Smith. The design of divide and conquer algorithms. Science of Computer Programming, 5:37-58, 1985. 2
[65] Behzad Tabibian, Utkarsh Upadhyay, Abir De, Ali Zarezade, Bernhard Schölkopf, and Manuel Gomez- Rodriguez. Enhancing human learning via spaced repetition optimization. Proceedings of the National Academy of Sciences, (16((1):3988-999)) 2019. 3
[66] David Tarditi, Sidd Puri, and Jose Oglesby. Accelerator: using data parallelism program gpus for general-purpose uses. ACM SIGPLAN Notices, 41(11):325-335, 2006. 2
[67] Pei Wang. Kabir Nagrecha, and Nuno Vasconcelos. Gradient-based algorithms for machine teaching. In CVPR, 2021. 3,3
[68] Pei Wang and Nuno Vasconcelos. A machine teaching framework for scalable recognition. In ICCV, 2021.
[69] Zhaozhuo Xu, Beidi Chen, Chaojian Li, Weiyang Liu, Le Song, Yingyan Lin, and Anshumali Shrivastava. Locality sensitive teaching. In NeurlPS, 2021. 3
[70] Jianbo Ye, Panruo Wu, James Z Wang, and Jia Li. Fast discrete distribution clustering using wasserstein barycenter with sparse support. IEEE Transactions on Signal Processing, 65(9))2317 233-2332,, 2017. 3
[71] Teresa Yco, Parameswaran Kamalaruban, Adish Singla, Arpit Merchant, Thibault Asselborn, Louis Faucon, Pierre Dillenbourg, and Volkan Cevher. Iterative classroom tcaching. In AAAI, 2019. 3
[72] Longhui Yu, Weisen Jiang, Han Shi, Jincheng Yu, Zhengying Liu, Yu Zhang, James Kwok, Zhenguo
Li, Adrian Weller, and Weiyang Liu. Metamath: Bootstrap your own mathematical questions for large language models. arXiv preprint arXiv:2309. 12284, 2023. 10
[73] Chen Zhang, Xiaofeng Cao, Weiyang Liu, Ivor Tsang, and James Kwok. Nonparametric iterative machine teaching. In ICML, 2023. 1, 2, 3, 4, 5, 6, 7, 23
[74] Chen Zhang, Guangyu Sun, Zhenman Fang. Peipei Zhou, Peichen Pan, and Jason Cong. Caffeine: Toward uniformed representation and acceleration for deep convolutional neural networks. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 38(1 2):2022-2085, 2018. 2
[75] Dinghuai Zhang, Mao Yc, Chengyue Gong, Zhanxing Zhu, and Qiang Liu, Black-box certification with randomized smoothing: A functional optimization based framework. In NewrIPS, 2020. 3
[76] Xuezhou Zhang, Shubham Kumar Bharti, Yuzhe Ma, Adish Singla, and Xiaojin Zhu. The sample complexity of teaching-hy-rreiffoccmm on q-learning. arXiv preprint 2eXiv:2006.09322 2020. 3
[77] Yu Zhang and Qiang Yang. survey on multi-task learning. IEEE Transactions on Knowledge and Data Engineering, 34(12):5586 000666569990000 2021. 2, 8
[78] Yao Zhou, Arun Reddy Nelakurthi, and Jingrui He. Unlearn what you have learne: Adaptive crowd teaching with exponentially decayed memory Iearners. SIGKDD, 2018
[79] Yao Zhou, Arun Reddy Nelakurthi, Ross Maciejewski, Wei Fan, and Jingrui He. Crowd teaching with imperfect labels. The Web Conference, 2020.
[80] Xiaojin Zhu. Machine teaching for bayesian learners in the exponential family. arXiv preprint arXiv: 306.4947, 2013.
[81] Xiaojin Zhu. Machine teaching: An inverse problem to machine learning and an approach toward optimal education. In AAAI, 2015. 3,
[82] Xiaojin Zhu, Ji Liu, and Manuel Lopes. No learner left behind: On the complexity of teaching multiple leamners simultaneously. In IJCAI, 2017.
13

---

[83] Xiaojin Zhu, Adish Singla, Sandra Zilles, and Anna N Rafferty. An overview of machine teaching. arXiv preprini arXiv: 801. 2018. 1,
[84] R Zoppoli, M Sanguineti, and Thomas Parisini. Approximating networks and extended ritz method for the solution of functional optimization problems. Journal of Optimization Theory and Applications. 112(2):403 440, 2002. 3
14

---

Appendix
A
Additional Discussions
Broader Impact
This paper is to address practical limitation of recently introduced Nonparametric Iterative Machine Teaching from the theoretical aspect, which is to enable multi-lcarner teaching. We also provide empirical evidence to demonstrate that multi-learner nonparametric teaching is effective in addressing such a limitation. Although we hope that the outcomes of this study will enlighten the theoretical community, do not expect any immediate effects society from this work.
Pseudo code for multi-learner RFT and GFT
The pseudo code for RFT and GFT in the vanilla and communicated MINT is given as following:
Algorithm Greedy (Random) Functional Teaching for the Communicated (Vanilla) MINT
Input: Target f E Hd, initial fo E Hdd small constants c, cp > 0 and maximal iteration numbers
T, To-
Set f t t= O.
while t < T and |lf - f 1a 2 c do
The teacher is not only to construct the communication matrix but alos to select the teaching set for multiple learners:
// Construction of the communication matrix.
Initialize two-layer perceptron with a linear layer, i.e., initialize the communication matrix with an indentity one (A = Ia), and set to = 0. while to S To and ||Af f l| co do Train the linear weight (A) of this two-layer perceptron, such that As 11 decreases. end
/* For the Vanilla MINT, omit the above procedure of solving for the communication matrix, just need to set A Ia.
// Selection of the teaching set.
Initialize the teaching set D 0; Pick 1 E X. e N& with the maximal difference between f and ft for multiple learners simultaneously:
arg max (51 (x)));
/* For random functional teaching, Pick xf" E N2 E Na randomly and concurrently.
*/
Add (at", ft (x!")) into the teaching set D.
Provide A and D to multiple learners
The learners update f based on received A = A and D' DD: fltt A' f n 2 G(C; A'. f¹;
Sett t ++1.
end
Further discussion about the idea behind MINT
In practical scenarios, it is a commonly accepted fact that a single object can possess multiple characteristics. For instance, when describing a fruit, we often take into account its various attributes such as shape, color, and texture. This highlights the notion that limiting oneself to scalar-vector functions in nonparametric iterative machine teaching would not be enough to capture the complexity of real-world data. We thus extend the current nonparametric teaching from the single-learner version to multi-learner one (MINT) by considering vector-valued functions. Compared to parameterized
15

---

Vantia fD
Epdare
Commantcarce MIST
fo
-1/2
Communication matrix
Figure 5: Comparison between vanilla and communicated MINT.
teaching, MINT can be seen as a type of extension which involves replacing the vector unit from values to functions.
The idea of communicated MINT partially comes from linear algebra. If f E H. forms a basis of Hd, and f can linearly expressed by this basis, then is noteworthy that learners can successfully learn f with only one-time communication.
Let consider scenario in which the components of fo are from different function families. Suppose we take fo (e", sin x)) and f = (2e sin x, sin x + 2x, -e" + +inn x + x)". it holds that
2c sin 1 sin + 2r e" sin x
2
11
0
sin
(18)
communication
which indicates that the teacher can teach f to multiple learners through providing the communica- tion matrix A within one iteration. To draw practical analogy, we view e denoting shape, sin ka indicating color, and 1/ representing texture.
Another scenario is when the components of fo belong to the same function family. Consider the scenario where two learners are familiar with the shapes of a circle and a square, respectively, and they need learn two different shapes as shown in Figure 5. In this case, we can model it by assuming that ff.j j N₂ belong to the cosine family, iee, fo (v2 cos(2 /2 cos(4 (T Here, f/ are not linearly related, which is a property of basis. The target function is denoted as f" (72202222 v2 (os(cATTT))) (00m)) cos(2Tr)) + v2 cos((AT.))) It is trivial to derive that
(v² cos(2 v2 cos (oTT)) ccos(2 + /2 cos (4Tx)
.V2
(11/= 1)) (
(v2 cos((2122) cos( (4Tz)
(19)
By referring the illustration in Figure 5, communicated MINT. can be observed that the communicated MINT is capable of helping to learn f within just one iteration, whereas the vanilla MINT requires numerous iterations achieve the same.
compare the performance of vanilla MINT and
B Detailed Proofs
Our suggestion for further reading on functional calculus would be to consult the literature [24, 16] and the references therein.
Proof of Lemma 6 We firstly define function q by adding small disturbance eg (e E IR g E Hd) to f E Hd. that is, q= eg. We see that q E Hd since vector-vatt veluer- RKHS closed under addition and scalar multiplication. For a evaluation functional F.z [f] = Σ fe(ri.))) Hd + IR
where x (. E xdd, we thus can evaluate at œ as
Ex
En[f + eg] Ex[f] + <E [g] +0
=
ExIf] + (x, ))g) H +0
(20)
16

---

Recall the definition of the Fréchet derivative in a vector-valued reproducing kernel Hilbert space (RKHS), which defined implicitly and can be found in Definition 1, Ex + eg] E [f]
9hH + O(e²), it follows from Eq. 20 that the gradient of evaluation functional in
vector-valued RKHS 7d is Ex = K = 5K..,, 1..
Proof of Lemma Note that one example (a, 3) ~ Q (2r, y) can be uniquely identified by its æ. we take expectation on PP(x)) only for the sake of simplicity. It follows from the convexity of L; and the definition of Fréchet derivative in Definition 1 that we have
(x)))
[c:( L.()))
s E (xn)))
(ft+1 - fi 5-
= (1,r))
|ny En! [)l((f))=1]
Eas (VC((f)) ] Bas V)c,())
V)C((M))= ]]
-nf REPPP(td
(21)
Under LipLsshhitz smooth Assumption 3 and bounded kernel function Assumption 4, we can show that
Exg [,((())== VyC,(D) 2 (3/4- (Mx))) "M Exi [(V,C.(0)==))
(22)
For succinctness, we define
(V)C((0))-))) =v3c)))))))
(23)
and
(,,)( = E& [3A(0)) |= =Fx Fx [F:((VCC(()))==
r-
(24)
Then, we can apply Taylor expansion for (x.) on 14 = E2g (2.)) and derives
m m",((1))
mx)) mas(u:) (x),( n.) +
(xt) ni)² + R2(x)),
(25)
2
where the remainder R2(x)) usually is omitted, and we assume e (xf)) is 2-times differentiable. We see that evaluated mean pas (p,(p:) is monotonically decreasing w.r.t. iteration t. Combining Eq. 21, 22 and 25, we have
ELN) (2 L.(Si)
s -n Ba(cP((t)) (3/4 (2 Eag [v94(0)))=1]]]
(Mx)) ( (us) + (((((a) o?)
= -n (3/4 122
(26)
2
where of (x, - 24)2 is the variance of x4. Therefore.
E (m [(( -((")]
a Σ ((fftt) - - c(ff))
Ea-))(.)))
1=1
E ExiPP((ss) -
mh (3/4 - L3 -22 (me,)(ps) + ((,((ss) 2 0z).
(27)
17

---

Hence, vi E Na. n/ S Mxx we have
(a)))( [ - L(S')]
8
7'
Σ
(meclp)) + miielh)) 07;)
2
2
ij'd
(,,,((H)) + (p(((())
min ieNa
2 0:
(28)
where 1j' min n/c-
Proof of Theorem
Recall Lemma 7, Vi E Nd. 11 S 2he we have
2 (mi,e(()) + m"e(Hs)
(x))) [ - [(f*)]
1
2 o,))
7'
mi,e((t)) + m((((H))
d min iENa
07)
(29)
2
2
where 1j' = min m/. Rearranging above, we have:
2E 2Bm-Pa(aat) [C(F') [(f+tt)
m),((us) + m/,((r))
min
o?
(30)
dijt
2
Equivalently, replace index t by 1, 2E ye (( mingeNa (ma,((s)) +
o?
did
2
Consequently, plugging = 0, 1 ....,,,. 1 in it and summing them up, hence have
(m,)(14)) + (H,(H)) 03)
min KENa
2
E (C(P)) [(
of
t=
Bm- [C( [(
(31)
where ńj
min UN
0. Expanding the r.h.s. term in Eq. 31 yields
2 1-1
P. [E(F)) - c(
dij
1=0
2 dij
E Ba),)) [C(F9) [(F')
<
E B [f(F-)]
(32)
dij
In terms of the l.h.s. term in Eq. 31, we must have
(mn](ps) + (4) oi
min min maa(()) m"o((t)
Σ min SENa
2 26-
2 0i
(33)
UN
IENa
Combining expression 32 and 33, thus have
m"((u)))
min U
min 1 SEN,
(m.((u)) +
o,
5
min mmr((u)) + iERa
2
2
1=0
<
E Em (F [c(FO]]
(34)
dij
18

---

Since (4,4 is monotonically decreasing w.r.t. iteration E, we have
min min (mzi(u4) + (m) (2)
min (mi,-1((4) + (H))))))))) ieNa
(E(0) 8 FEN
Therefore, we can derive
m 114 o3
2 diyl
min
mi,--1(4)) +
S BoMB.(C)) [c(r")]
(35)
seNa
2
when the returned vector-valued model for multiple learners is f* and index denotes the last iteration.
On the other hand, it follows from Eq. 32 and the fact that (1,)((5) is monotonically decreasing w.r.t. iteration that we have
dij
m/,(ue) of
(x [C(f) - [[F0)]
min i,
m4,((Hs)
1=0
dij
min m+ + 1 .
2 07
(36)
2
After rearranging, we obtain
(mi-- (1:) + m (H4i)
2 (T) -
min iEN
oi
2
dijt
dijt (.(a)))))) [c()))]
(37)
r.t.s..s of Eq. 37 be controlled by a small constant > we have
2
t dije (P. [
(38)
which means given small constant c > O it would take approximately
dijc Ea-Ra [E(T9)]
iterations to reach a stationary point.
Additionally, this suggests that multiple learners could achieve the stationary state as: In each iteration,
check (4.5-1(p4) + ((() af is small enough. Assuming this condition is satisfied, the learners will have already reduced the multi-learner loss acceptably low level, allowing them to send signal indicating termination back to the teachers. the condition is not fulfilled, the teachers will continue with the process. The termination occurs within diye (e. [C( iterations.
Proof of Lemma
Recall practical Greedy Functional Teaching in Eq. 12
arg max x'EX'
En:
[ Eme- (54)
(39)
Obviously, it is trivial to that Vxo E X.
Ezge-
[][([)
Fag [,,[())>=>]]]
(40)
Analogous to the Proof of Lemma 7 in B, we can derive
E Ex,P) [C.(ftt1) L.(f))
T/ Bej
Egg- V,c((D))= (|A(())))++]
- Ezg. [,(((f))==1 V)C((f)==)""
S Vi (3/4 (M()))())))))))))))))))) Ezt- [VRG,0))E
03/4 L3 (Mx) ma.e
(41)
19

---

where holds because selected z;" by GFT is determined. Therefore,
( [ [(f)]
n (3/4 L2((7)) m).l()))
(42)
Hence, if vi E Na. vh S 2Le.Mxx we have
17 Σ
n'd 2
[(F))
m m
min (,,
(43)
i=1
where 1j' min n/6 Note that GFT is to select examples such that the gradient is the steepest, (m))
thus minkeN, mi (af( 2 mingeNa (ms))((s))
Proof of Theorem 10
Recall the result of Lemma 7, when vi Na, S 2LC-MK
o,) S 2 P.(a))) [C(f*) - C(f(t1)
Σ (m)) + 2
(44)
where rj = miniee, T/c
Before converging to the stationary state, Eim1 mixe( > O. Therefore, we can express it as
(af") Ei (mi,e(us) + mga((r) o?) 2. [C(F' [(f++))]
(45)
Eim1 (x)""
1f
We see that Ed. (m: [lx) ((=) of)
measures the difference between two algorithms at iteration. And this is deterministic in each iteration, that is, this can be estimated before sampling, so we can see the superiority of GFT.
>i (z!"*
Σ (me)(u)) + mkelan)) o
Σ (a,e(a!")
mi m(r((r))
mialltt) (ui)
1=1
Σ Ei=1 mate(at")
d
||0
Mill2 ml(a(te)
Eim1 -imm,i,,1'' m2,
Σ 1=1 (1124 - melle)
(46)
Σ m4,(
where assume (z,( is Lipschitz continuous w.r.t input å to tract the relation between this quantity and the distance between μi; and xz{" Now, we have
ΣS (1+ - milla) < Ei (me,le)))) + (od o?) 11 E mz,(
(47)
Ed mi,exx!"
We that when selected xn by GFT is close to μ4 then RFT and GFT on average share the same performance. (show that if maximal model disagreement occurs at the mean of distribution, then such a greedy teacher may share similar performance with a random teacher on average.) This is important to gain an insight on when greedy teacher is better than random teacher. Then, we have
Σ (a)
Σ (1a5 millz)
Σ
(max(
|| -millz)
2 2 P.(a,)) [C(F9) C(f(tt)
<
(48)
7
20

---

d Σ mi,((x)") 2E (i(o))) [C(f*) [(ftt!)
d
|x - millz)
(49)
Therefore,
2B 2B (ar)) [E(F*) [(f+tt)]
Σ
||a Hills) 2
min ma,r(at") iENa
(50)
drj
Equivalently, replace index by 4, 2 Le (
E (|aa)" - polle) 2
dij'
mingeN, ma,(2 Consequently, plugging 0,1..., 1 in it and summing them up, hence have
min (x,(" NeNa
2
E BP (x,)) [C(F)) [(f(tt)
| - -aile)
17
1=0
t-1
1-1 d
R B (x,) (R(F)) - L(F +
Σ
|1a4* - mellz).
(51)
dij
1=0
1=0 i=1
where =
min
0. Expanding the r.h.s. term in Eq. 51 yields
le U N
2
E.- [R())) [(S++1)]
1-
(1a55 - milla)
+
drj
10
2
E (.xx)) -(f)))
(1ot -Halla)
dij
I=0 i=1
1-1 d
<
2 di P(
[C(F))
Σ
Σ
| - Hellz)
(52)
1=0 1=1
terms of the lh..s term in Eq. 51, we must have
Σ
min m, 2 t-
min min my (2. ) 1E(0)UN_ Ee
(53)
iNN
1=0
Combining expression 51, 52 and 53, we thus have
min (E)0) -
min EER
ma)()")
Σ
min (x!"
eNN
1=0
[-1
V^
E dñj
aa (..)) [c(F-)]
+ d
ΣΣ> Σ
(122** - Hilla) (54)
Im0 aml
Since ma,e(at") is monotonically non-increasing w.r.t. iteration t, we can derive
[-1 d
min 1 < drjt Ba ( [C(F])] + dt ieN
||a - H4ll2).
(55)
[=
when the returned vactor-valued model for multiple learners is ft.
To compare with RFT, we can plug the r.h.s. of Eq. 38 and see that the loss reduction more than (a. [C(]")] which indicates GFT needs less iterations converge and the efficiency of GFT. Compared with Eq. 35 and 55, we see that the inferiority RFT compared GFT comes from the cumulative distance between the example mean and the example selected by GFT.
21

---

Proof of Proportion 11 When the proximity between f and f is sufficiently close, have 6 < 6o where 6o is the pre-defined approximation error of employed two-layer perceptron. Take A Ta, then we have || f f* I f f* II f l
cn, which means that this perceptron have searched the matrix A = La that satisfies ||A f Il 60
Proof Lemma 12
Since the multi-learner convex loss L(f) will decrease input f close to f and matrix A' comes from A' = arg min| AAf' - f l, searching a matrix A to minimize the AERdxa
disagreement between A and f", it is trivial that
((f") ((A
(56)
Based on Assumption 3, derive that
IC(A' ((f*) I -f
(57)
and
12(F*) -(F") Iellf 1e..
(58)
Therefore, have
((A'))
E(F') + ('A
S IC(F') - -(f))++++++ +1((") - C(A'F))
s Le (1|'' - f + +If (()
- 2L || - -fa1,
(59)
which concludes the proof.
Proof of Theorem 13
Following the style of the previous proof, e.g., the proof of Lemma begin by investigating the reduction in the loss for single learner.
E (x,))
((( G.) + (((A)))))))) c.09 -C.0)))
(x.)P,(a.))
(G((2)) C(A((r))) p\]
+EINPI(E) -C -
E (p.)
(C()))))) - C.(A(a)))))
(60)
where it follows from Lemma that S holds. Therefore, we have
(a ( - [(5")]
E Ba-D)(
Σ - -
1=1
(1((2tt)) C.((3)
D Ea
(c.( - c,(A((,)))))
i=1
E
Ba- [C(P))]) - C(A+F') $0.
(61)
which completes the proof.
22

---

1- 10000
L-20000
1-30000
L-50000
1-699
1-70000
1- 50000
t-5000
b-10000
2- 2=12000
L-139999
t-140000
b- 50000
t-160000
t-170000
2- 100000000
t-209909
Figure 6: Extensive visualization of ft for single-learner teaching.
(a) Vanilla MINT.
(b) Communicated MINT.
Figure 7: The channel-wise visualization of specific f corresponding to Figure (b)-(c).
C Detailed Experiments and Extensions
Since computers operate in discrete manner, we employ dense pairwise points {xx,, (xN)),,,, to represent vcalur- function f and points {(<=:]]. [f(())] to represent vector-valued function f -[ Hd. To facilitate visualization, our experiments have utilized 2D (ID Gaussian data), 3D (a grayscale image) and 4D (a colored image) examples to demonstrate the insights obtained from our theoretical analysis. Generally, the domain of the functions being learned in 3D cases is determined by the r and y values, which represent the pixel locations, while the range is represented by the values, indicating the color levels. This comparable for 2D and 4D cases. Besides, for nigh-dimensional vision datasets that can be formulated as vector-valuee functions. the methodology developed in this work can be applied as well. For all experiments, we align with [73] to set RBF
K( exp --
as the kernel and take empirical (average) L2 norm defined in vector-valued Hilbert space measure the difference between Hd and f H..
d n
M(f.f)) |f f l4 dn
ΣΣ i= 1=
(fi(z1)) - f(
Our implementation relies on the Intel(R) Core(TM) i7-8750H processor and utilizes NVIDIA graphics cards, specifically the GTX 1050 Ti with Max-Q Design and RTX6000.
MINT in gray scale. For impartation of tiger" and cheetah [15], we assume the loss functions for both learners are square loss C, (y fz(x)) ,i E N2. For the monochrome lion divided into
phttps://wwe
/ic////////////////// gaze- gaze-white- thiite-tgger-ee original
23

---

Table
Peak signal-to-noise ratio (PSNR) corresponding to learnt f show in Figure 4.
0
10,000
50,000
100,000
150,000
210,000
Single-learner teaching
8.73
9.16
10.23
11.66
12.99
14.49
Vanilla MINT
8.73
10.01
13.19
16.27
18.98
22.00
Communicated MINT
8.73
12.38
15.62
18.74
21.50
24.58
Table PSNR corresponding to learnt ft show in Figure 8.
0
10,000
50,000
100,000
150,000
210,000
Single-learner teaching
8.73
8.87
9.45
10.17
10.89
11.75
Vanilla MINT
8.73
9.16
10.88
13.03
15.19
17.76
Communicated MINT
8.73
11.46
13.20
15.39
17.58
20.19
pieces, each piece is learnt by single learner whose loss function set to square loss, and all loss functions are the same, C; = (y - f((x))² N16. This enables the teaching of a single-learner target model having large input spaces.
MINT in three (RGB) channels. Three learners, each with their own randomly-initialin fo, are tasked with learning the three (RGB) channel lion image". Each learner is equipped with square loss function learn their respective channels. In the case of single-learner teaching, the teacher must repeatedly teach all three channels. In Vanilla MINT, the teacher can teach all three channels concurrently. In communicated MINT, the teacher uses a two-layer perceptron to solve for communication matrix A', with the linear layer initialized by an identity matrix. This allows the teacher to teach all three channels simultancously.
We present comprehensive visualization of f for Figure 4 (a) in Figure 6, while the channel-specific visualization of certain f corresponding to Figure (b)-(c) is exhibited Figure order to evaluate the quality of the learned f (as images), we utilize the Peak Signal-to-Noise Ratio (PSNR), and the results corresponding to Figure 4 are presented Table Meanwhile, Figure displays the specific learned f for RFT, and its corresponding PSNR is listed in Table 2. Additionally. Figures (a) and (b) respectively exhibit the -specfc- visualizations of vanilla (Figure 8 (b)) and communicated (Figure 8 (c)) MINT for RFT.
In addition, also investigate the performance of single-lcamer teaching, well vanilla and communicated MINT under a specific initialization of fo, which is obtained through a linear combination of f* using the inverse of matrix
1.26
2.22
3.60
2.47
-0.53
2.36
2.40
1.68
0.40/
Figure 10 displays the plot of the loss. Figure 11 showcases the specific learned fr for three versions of GFT throughout each iteration. From Figure 11, we can observe that MINT consistently outperforms the single-learner teaching. and additionally, communicated MINT exhibits better performance compared to vanilla MINT. Figure 12 presents the channel-specifte visualization of certain f that correspond Figure 11 (b)-(c), while Table 3 lists the PSNR for all comparable in Figure 11. Additionally. Figure 13 displays the specific leamned f for RFT, while the -hannel-specific visualization of certain f for MINT exhibited Figure 14. The corresponding PSNR values
http://www....iiuuuooooooore//// httpe/attaaaemmaooinnono/oonee/e wwwooooooooiooooeeoooeoooeoooe png
Table 3: PSNR corresponding to learnt f show in Figure 11.
0
2,000
10,000
20,000
50,000
90,000
Single-lcamer teaching
7.58
7.65
7.88
8.15
8.88
10.07
Vanilla MINT
7.58
7.82
8.56
9.35
11.37
13.68
Communicated MINT
7.58
16.29
17.12
17.98
20.19
22.75
24

---

Table PSNR corresponding to learnt f² show in Figure 13.
0
2,000
10,000
20,000
50,000
90,000
Single-learner teaching
7.58
7.72
7.87
8.33
8.92
Vanilla MINT
7.58
7.66
8.03
8.48
9.82
11.62
Communicated MINT
7.58
16.08
16.44
16.89
18.23
20.03
t-0
t-10000
t-20000
t-30000
t-50000
1-69939
t- 7-0000
80000
t-9000
t-100000
--120000
t-139999
t-140000
t- --100000
1-160000
t- 70000
--19000
t- 1-209999
(a) Single-learne teaching.
1-32006
D-200693
L-100003
2-221900
(b) Vanilla MINT.
1-30004
--30009
1-250083
1-238900
(c) Communicated MINT.
Figure 8: Visualization of f taught by RFT under the random initialization.
listed in Table 4. An interesting finding is that with this specific initialization, the teacher can assist the learners in directly learning f* by providing the communication matrix
1.27
2.22
3.60
2.47
-0.53
2.36
2.40
1.68
0.40/
which solved by a two-layer perceptron. In order to elaborate this observation, we offer an illustration in Figure 15.
Synthetic 1D Gaussian data. We use synthetic 1D Gaussian data set for teaching a single learner to demonstrate that the greater the distance between the example mean and the example selected by GFT, and ʃ = N(x; 0, 52).
more significant the difference between RFT and GFT. We set f where N(x;; /a, o²) represents the probability density function of Gaussian distribution with mean and standard deviation a. trivial to see that GFT will select examples primarily around x Looking at the loss depicted in Figure 16 (a), observe that GFT reduces the loss more rapidly than
25

---

(a) Vanilla MINT.
(b) Communicated MINT.
Figure 9: The channel wise visualization of specific f corresponding to Figure (b)-(c).
x10-
4.0
3.5
Single
Loss
2.5
Single laaeer teaching RFT
Vanila NINT, GFT
Vanila RFT
2.0
Commaniooed MINT, Commun caned MINT, RFT
1.0
200
400
600
800
Iteration t
X102
Figure 10: Convergence performance for teaching RGB lion under particular initialization of f
RFT in the settings of 0, -4, - (in order of decreasing speed). This is consistent with the observation Theorem 10. Additionally, we present the specific learned function f in Figure 16 (b).
Synthetic bivariate mixture Gaussian data. To further showcase the effectiveness of MINT, we utilize synthetic bivariate mixture Gaussian data. It is well-established that a bivariate Gaussian distribution fx, (11, .22) can be factored as the product of two independent univariate Gaussian distributions "x,.X, (#1, x2) fx, (21).xx (xz)² [8], regardless of whether X1 and X₂ are corre- lated, For simplicity, our primary focus is on the scenario where there is no correlation (p 0), and on GFT. We set
(21, f2, (x1) N(z; -2, (zx 2,1
and
(2, (I2)
2N 2, - (ox 12)/44
Figure 17 depicts the visualization of /x, xx, (x1, 22). One can also formulate such a single-learner target function into a multi-learner (vector-valued) one f. with the first component being fx, (x1) and represent
the second component being fx, (Ir2). Thus, the notation, we can represent it as f = (2) fe) In Figure 18, we can observe the specific learned f' of single-learner teaching, vanilla and communicated MINT. Based on the observations from Figure 18, it can be concluded that MINT method is much more effective in terms of efficiency when compared to single-learner teaching. Furthermore, for communicated MINT, the teacher can provide the communicated matrix to let ff being learnt within single iteration. Besides, Figure 19 shows the loss plot which tracks convergence performance.
f fx,)² To simplify
Synthetic ID data. We use synthetic one-dimensional data to evaluate when the communication matrix A, is advantageous. Specifically, our main focus is which refers the first iteration
http:: htttp::/athenasc..o http://chhenacccco///varraaaaase Normal pdf
26

---

L-00000
L-22923
(a) Single-learner teaching.
(b) Vanilla MINT.
(c) Communicated MINT.
Figure 11: Visualization f taught by GFT under a particular initialization.
(a) Vanilla MINT.
(b) Communicated MINT.
Figure 12: The channel-wise visualization of specific f corresponding to Figure 11 (b)-(c). The communicated
MINT exhibits better performance compared vanilla MINT.
27

---

(a) Single-learner teaching.
PS030
(b) Vanilla MINT.
(c) Communicated MINT.
Figure 13: Visualization of f taught RFT under particular initialization.
Vanilla MINT.
Communicated MINT.
Figure The channel-wise visualization of specific f corresponding to Figure (b)-(c).
28

---

F PRR
F RGR
MLP Solved
R
1.27
2.22
3.00
2.47
-0.33
2.36
2.40
1.68
0.40
Ground Truth A:
1.26
2.22
3.60
2.47
-0.33
2.36
2.40
1.68
0.40
Figure Illustration extreme case of teaching. The teacher can help the learners directly leam f through providing the communication matrix.
X32
1000
1500
300
Iteration
(a) Convergence performance
0th Iteration
500th Iteration
1000th Iteration
2000th Iteration 3000th Iteration
5000th Iteration
46
(b) Visualization of f and f
Figure Examination of relation between RFT and GFT.
(the results of > 1 can be derived similarly), where there are two learners attempting to learn separate target functions. We set f f2) (x, =²)" and f; (イz/2 7xx /2 + 7) cos x, 7x/3 + 2yx²/3 + (1 7) sin x)) 7 E [0, 1]. and we generate y by In Figure 20, present the corresponding || f; 2 against y. The observed trend is that as y increases, the distance between A, and f; decreases. This indicates that A, performs better when f can linearly expressed by f but poorly when f* cannot linearly expressed by f Moreover, A is beneficial when f can be partially expressed in linear manner by f
(-,,
29

---

[2(
0.25
0.20
0.15
0.10
2
22
Figure 17: The visualization a multivariate mixture Gaussian distribution fx1,x (2).
an 22)
fa m2)
(ay.
Single-leamer teaching.
0th Iteration
150th lteration
450th Iteration
1000th Iteration
2000th Iteration
3000th Iteration
(b) Vanilla MINT.
A
MLP Solved: 0.67
0.33
Converge
0.75
0.25
Ground Truth: 2/3
1/3
3/4
1/4
(c) Communicated MINT.
Figure 18: The specific learned f (..
30

---

x10
X10
Singel-leerner teaching, GFT
12
Vanila MINT, GFT
Communicated MINT.
0.5
0.8
LOSS
0,0
0.2
1000
2000
3000
4000
5000
Iteration t
Figure 19: Convergence performance for the synthetic bivariate mixture Gaussian data.
A f
0.0
0.2
0.4
0.6
0.8
1.0
7
Figure 20: The distance between A0 and f VS. 7.
31


Reviews:
[{"review_id": "e7NbaivZWH", "reviewer": "Reviewer_D1DQ", "summary": "This paper investigates the iterative machine teaching problem under the non-parametric learner setting with vector-valued target models, also known as multi-learner nonparametric teaching (MINT). The authors consider two teaching strategies: Random Functional Teaching (RFT) and Greedy FT (GFT). The authors first theoretically analyze the convergence behavior induced by the teaching strategies in the vanilla MINT setting, where there is no communication between the learners. Then, they study the teaching strategies in the communicated MINT setting. Finally, they empirically compare the effectiveness of different teaching strategies.", "questions": "The theoretical results in the paper are based on a synthetic example generation setting. If the teacher is restricted to choosing examples from a pool, that would result in different examples than the ideal one. Then, what would be the impact on the results?\n\nGiven that the teacher can freely synthesize examples to guide the learner toward a target model, can the results discussed be extended to learners with non-convex loss functions?", "limitations": "The paper is of an algorithmic/theoretical nature and does not have any direct potential negative societal impact.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is overall well-written, and the related work is extensively discussed. \n\nThe theoretical results in this paper seem correct; I haven’t checked the details of the proofs.", "weaknesses": "The availability of a powerful teacher with a vector-valued target model needs to be motivated with more realistic practical scenarios. \n\nThe novelty of the contributions of this work in comparison to “Nonparametric Iterative Machine Teaching (NIMT)”: the problem formulation/setup, RFT/GFT teaching strategies are extensions from the NIMT paper. Thus, it is important to clearly discuss how non-trivial these extensions are and how different the proof techniques are from those of the NIMT paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the useful comments. We are deeply appreciative of the reviewer’s efforts to improve our paper. We take all comments seriously and try our best to address every raised concern. We sincerely hope that our response resolves your concerns.\n\n**Q1**: An important problem towards realistic application in machine teaching lies in classroom teaching [a-b], where a teacher is responsible for teaching multiple learners. One motivation behind this work comes from exploration of such realistic multi-learner teaching, and we conduct investigation of multi-learner teaching based on nonparametric teaching. Specifically, we generalize the model space from space of scalar-valued functions to that of vector-valued functions. We will add more discussion on realistic practical scenarios in the revision.\n\n[a] Yeo et al. Iterative classroom teaching. AAAI 2019.  \n[b] Zhu et al. No learner left behind: on the complexity of teaching multiple learners simultaneously. IJCAI 2017.\n\n**Q2**: \n- In terms of contribution, we extend single-learner nonparametric teaching [c] to general multi-learner one. We achieve this by formulating multi-learner teaching as teaching of vector-valued functions under the framework of vector-valued functional optimization. Considering the correlation between the components of a vector-valued function has the potential to enhance the efficiency of teaching, we also investigate communicated teaching scenarios where multiple learners can execute linear combination on the currently learnt functions of all learners, which is more practical and non-trivial.\n\n- From a technical standpoint, we explain the difference in proof techniques between this work and single-learner teaching [c] in line 219 and 245. Specifically, we introduce the expectation operation over random sampling, which allows us to average out the impact of randomness. This also enables us to quantify the difference between RFT and GFT by introducing the distance between $ {x^t_i}^∗$ and $\\mu_i$ in Theorem 10, line 280, which is not considered in [c]. \n\n- In experiments, we conduct investigations in more comprehensive multi-learner teaching settings (e.g., RGB images and bivariate mixture gaussian data), demonstrating the effectiveness of multi-learner teaching and expanding the potential applications of nonparametric teaching.\n\nWe will further polish the presentation to highlight these in the revision.\n\n[c] Zhang et al. Nonparametric iterative machine teaching. ICML 2023.\n\n**Q3**: The teaching ability of pool-based teachers is limited due to their constrained knowledge domain, which is a subset of that of synthesis-based teachers. This constraint can result in the learner converging to a suboptimal ${f^*}’$, as mentioned briefly in line 190. We will add more discussion in the revision.\n\n**Q4**: Very inspiring question! In this work, the analysis of the loss function is conducted under the assumption of convexity, which serves as a stepstone towards handling nonconvex scenarios. It would be interesting to theoretically investigate the convergence performance and additional conditions of convergence for non-convex loss, as they may vary depending on the specific task at hand. \n\nFor instance, we can potentially treat a non-convex loss locally as a convex one [d], enabling us to apply the methodology developed in this work straightforwardly. By doing so, we can analyze the local convergence globally. Additionally, it might be a potential extension to make use of convex relaxation technique [e] to transform a non-convex problem into a convex one for handling nonconvex problems.\n\n[d] Razaviyayn et al. Parallel successive convex approximation for nonsmooth nonconvex optimization. NeurIPS 2014.  \n[e] Xie et al. Orthogonality-promoting distance metric learning: convex relaxation and theoretical analysis. ICML 2018.\n"}, {"review_id": "DnXoQtfytt", "reviewer": "Reviewer_JyMg", "summary": "The paper studied nonparametric teaching in the presence of multiple learners. Following prior works on nonparametric teaching, the paper extended to a scenario where multiple learners simultaneously learn a separate component of the joint model. The paper first analyzed the performance of the Random Functional Teaching (RFT) and the Greedy FT (GFT) strategy and showed that both teachers can successfully guarantee reduction in the loss function when the learners are completely independently, and no communication happens. Secondly, the authors studied the effect of communication between learners and show that an affine transformation of the joint model does not increase the loss but can significantly enhance the loss reduction in the beginning of the training phase. Experiments validated the discoveries in this paper.", "questions": "(1). What is the applicability of the theoretical results and the methodology developed in this paper? Is convexity a required property?\n\n(2). How does non-parametric teaching compare to vanilla learning without teaching. Does it help accelerate the learning process?", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "(1). The problem of teaching multiple learners itself is interesting and underexplored in the machine teaching community. This paper pushes the frontier of machine teaching in this aspect.\n\n(2). The paper theoretically analyzed the loss reduction of RFT and GFT teacher, and also the benefit of communication. The results show that non-parameter teaching with communication can indeed help with loss reduction.\n\n(3). The paper performed extensive empirical study of the teaching strategy, and the results are convincing.", "weaknesses": "(1). The assumption in the theoretical study is not clearly stated in the paper. For example, the theory seems to rely on the fact that the loss function must be convex, and this information should be made more prominent upfront. The authors may want to discuss the applicability of both the theory and the methodology developed in this paper. Does it apply with neural network model or only convex learners?\n\n(2). One thing missing from the discussion is that how does the teaching performance compare to vanilla learning. The non-parametric teacher only guarantees that the loss is always reduced. However, how does the loss reduction compare to standard learning process without teaching is an important topic to be discussed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the encouraging comments. We sincerely thank the reviewer's efforts for helping us improve the paper. We hope that our response resolves your concerns.\n\n**Q1**: Thanks for pointing it out. We introduce the convex loss assumption above Eq.(7), and in the revision, we will make sure to highlight prominent assumptions earlier. Currently, our results are derived based on convex learners, which serves as a crucial step towards non-convex cases (e.g., neural networks). And exploring the convergence conditions for neural networks is an intriguing avenue to pursue. For instance, investigating the condition under which neural networks converge to critical points [f] could involve employing non-convex optimization techniques. \n\nRegarding applicability, one potential application of this work could be in the field of knowledge distillation [g], where the teacher (cumbersome) model is to transfer knowledge to the learner (small) model by sharing “soft targets”. The idea in this study may serve as inspiration for future research on distilling a teacher's knowledge to multiple learners. Such knowledge transferring paradigms, in turn, can offer new insights and possibilities in various domains, including computer vision [h], Internet-of-Things [i], natural language processing [j] and decision-making tasks [k]. In the revised version, we will provide additional discussions to further explore these potential applications.\n\n[f] Diakonikolas et al. Sever: A robust meta-algorithm for stochastic optimization. ICML 2019.  \n[g] Hinton et al. Distilling the knowledge in a neural network. NeurIPS 2014 Deep Learning Workshop.  \n[h] Wang et al. Gradient-based algorithms for machine teaching. CVPR 2021.  \n[i] Xu et al. Locality sensitive teaching. NeurIPS 2021.  \n[j] Li et al. Blip: Bootstrapping language-image pre-training for unified vision-language understanding and generation. ICML 2022.  \n[k] Yengera et al. Curriculum Design for Teaching via Demonstrations: Theory and Applications. NeurIPS 2021.\n\n**Q2**: In essence, random functional teaching (RFT) employs a random sampling strategy and serves as a straightforward baseline that can be considered as the functional counterpart of stochastic gradient descent. As it randomly selects examples, RFT can also be seen as a form of \"learning without teaching\". On the other hand, the greedy functional teaching (GFT) teacher adopts a greedy approach by selecting examples that maximize the gradient. Through theoretical and empirical analysis, we have demonstrated that GFT outperforms RFT in terms of efficiency. In the revision, we will provide additional explanations to better illustrate these points.\n"}, {"review_id": "fZjWjKIAtq", "reviewer": "Reviewer_eAYw", "summary": "The paper extends non-parametric machine teaching to the case of multiple learners. In particular, each learner learns one component of a vector-valued function. The authors consider the case where learners have no communication with each other and the case where there is \"communication\" via a matrix transformation of the outputs of each individual learner.", "questions": "I thought the experiments section could be made clearer (I also looked at the additional details in the appendix but was still confused). What is the domain and range of the functions being learned? What are the examples (x and y) that the teacher is giving for each settting? Are they pixels?", "limitations": "I ask that the authors replace the Lenna image with any other image. There is no reason that this paper needs to use, of all images, the Lenna image, a cropped photo of a nude women from a Playboy centerfold. The continued unnecessary use of this image perpetuates an uninclusive environment.\n\nhttps://womenlovetech.com/losing-lena-why-we-need-to-remove-one-image-and-end-techs-original-sin/\nhttps://www.washingtonpost.com/opinions/a-playboy-centerfold-does-not-belong-in-tj-classrooms/2015/04/24/76e87fa4-e47a-11e4-81ea-0649268f729e_story.html\n\nLena herself has said that she no longer wants her image used: “I retired from modelling a long time ago,” said Lena in a new documentary film called Losing Lena. “It’s time I retired from tech, too. We can make a simple change today that creates a lasting change for tomorrow. Let’s commit to losing me.”", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "Originality: I am not an expert in machine teaching so I can't say how original the contribution is relative to prior work.\n\nQuality: The paper appears to be of good quality, though I did not check the proofs carefully.\n\nClarity: The paper was relatively clear, though with key exceptions referenced below\n\nSignificance: The paper appears to me to be an incremental step beyond the non-parametric single-learner setting.", "weaknesses": "I believe the paper needs more motivation and needs to contrast with the case where a single learner is learning a vector-valued function. Currently, the paper extends the scalar-valued single-learner setting to one where the teacher is teaching multiple learners---each outputting one component of a vector-valued output. In the introduction, the paper explains why teaching multiple learners at once would be better than teaching multiple learners separately. That seems quite clear, but then why not just teach one single learner that is learning a vector-valued function rather than multiple learners learning each component separately? The introduction seems to hint at computational issues but this should be made more explicit, and if computational issues are a critical motivation, then experiments showing the computational advantage should be included. \n\nEspecially because the paper also includes a section on \"communication\" between the learners and shows that they achieve better performance when communication is allowed. (By the way, the communication, in this case, is just a matrix that the teacher gives each learner.. the learners aren't learning to communicate with each other, so it seems clear from the outset that this would lead to improvement) So if communication leads to higher performance, then why not full \"communication\", i.e., one learner that outputs all components?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the useful comments. We are deeply appreciative of the reviewer’s efforts to help us improve our paper. We take all comments seriously and try our best to address every raised concern. We sincerely hope that our response can resolve your concerns. Any follow-up questions are welcome. \n\n**Q1**: Our motivation for teaching multiple learners, with each learner focusing on learning a separate component of a vector-valued function, stems from the need to align with the scenario described in [c], where a single learner is taught a scalar-valued target model or function. Additionally, teaching multiple learners is an important problem under exploration in machine teaching [a-b]. Interestingly, the mathematical framework of analysis for teaching a single learner that learns a vector-valued function and teaching multiple learners, each focusing on learning a specific component, should be essentially consistent. Both approaches address the question of how to effectively teach a vector-valued function under the framework of vector-valued functional optimization. The difference lies in the multi-learner approach, where each learner is connected to a specific component of the vector-valued function, whereas in the case of a single learner, the entire vector-valued function is connected to that learner.\n\nIn this work, “computationally wasteful” is used to describe that a larger number of iterations are required to achieve convergence for single-learner teaching than multi-learner one. We also illustrate the benefits of multi-learner teaching over single-learner teaching in terms of the loss plot, as demonstrated in figures such as Fig.3 and Fig.10. We will make a clearer presentation in the revision.\n\n**Q2**: “one learner outputs all components” may be a setting in the case where a single learner learns a vector-valued function and it makes sense within that context. Since the setting in this work is aligned with that in [c] where a single learner is taught a scalar-valued target function and our focus in this work is on teaching multiple learners, communication occurs among multiple learners. From a mathematical perspective, these two forms of communication should be essentially consistent since they both involve analyzing the relationships among the components of vector-valued target functions.\n\n**Q3**: In line 322, we provide an explanation that a grayscale image can be visualized as a three-dimensional surface, where the z-axis represents the level of gray, and the x and y axes indicate the pixel coordinates [c]. The domain is determined by the x and y values, which represent the pixel locations, while the range is represented by the z values, indicating the gray levels. In the case of RGB images, each color channel can also be visualized as a three-dimensional surface, similar to grayscale images. Again, the domain corresponds to the pixel locations, and the range represents the corresponding color values. As for Synthetic 1D Gaussian data, the domain is [-14,14], while the range corresponds to the values generated by the Gaussian distribution $\\mathcal{N}(x; 0, 5^2)$. We will further polish the presentation in the revision.\n\n**Q4**: The Lenna image used in Figure 1 and the experiments conducted in this theoretical work is merely an example of an RGB image, which we consider to be a well-known image in computer vision. As our attention mainly lies in theoretical machine learning community, we acknowledge that there is a possibility of us not being fully informed about all the news concerning Lenna. We apologize for any concerns caused by our lack of awareness regarding recent news about Lenna. Rest assured, we will replace the image with a different RGB image in the revision, while ensuring that it does not impact the theoretical findings presented in this work."}, {"review_id": "kzafH7NM99", "reviewer": "Reviewer_dq11", "summary": "This paper extends nonparametric teaching from the setting of teaching each learner independently to teaching multiple ones simultaneously. The method is about teaching a vector-valued model, which improves over existing methods when multiple learners can communicate with each other. There are both theoretical and experimental results validating the effectiveness of this method. ", "questions": "Can you elaborate on what other possible applications can benefit from the proposed approach?", "limitations": "N/A", "rating": 7, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper seems to have solid theoretical analysis; it's hard for me to judge as a non-expert.", "weaknesses": "Only one experiment on the RGB channels of images is shown in the paper. Another experiment in a different setting may help demonstrate the generalizability of the approach. As someone with no expertise in this area, I'll defer to others on the technical side of things. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive comments! We respond in detail to your specific concerns in the following.\n\n**Q1**: Due to the page limitation, we have provided two experiment results in the main paper. We also show additional performance evaluations of MINT under various settings and presented detailed demonstrations in the appendix. These include testing MINT with a specific initialization of $f^0$ in RGB teaching tasks, comparing RFT with GFT using channel-wise visualization, and conducting experiments with Synthetic Bivariate Mixture Gaussian data. All of these experiments align with our theoretical findings that highlight the superior efficiency of communicated MINT over the vanilla approach, which in turn outperforms single-learner teaching. We will improve our presentation to note our additional experiments in appendix.\n\n**Q2**: This theoretical work has the potential for application in the field of knowledge distillation [g], where the teacher (cumbersome) model is to transfer knowledge to the learner (small) model by sharing “soft targets”. The idea presented in this work could serve as inspiration for future investigations into distilling the knowledge of a teacher to multiple learners. Such a knowledge transferring framework, in turn, can open up new avenues of exploration and possibilities across different domains, such as computer vision [h], Internet-of-Things [i], natural language processing [j] and decision-making tasks [k]. In the revision, we will expand upon these potential applications by providing additional discussions to delve deeper into their implications.\n\n[g] Hinton et al. Distilling the knowledge in a neural network. NeurIPS 2014 Deep Learning Workshop.  \n[h] Wang et al. Gradient-based algorithms for machine teaching. CVPR 2021.  \n[i] Xu et al. Locality sensitive teaching. NeurIPS 2021.  \n[j] Li et al. Blip: Bootstrapping language-image pre-training for unified vision-language understanding and generation. ICML 2022.  \n[k] Yengera et al. Curriculum Design for Teaching via Demonstrations: Theory and Applications. NeurIPS 2021."}]

Author rebuttal:

Meta-review: The paper studied nonparametric teaching under the multiple learners setting. The paper extended the prior work to a scenario where multiple learners simultaneously learn a separate component of the joint model. The paper analyzed two approaches (no communication between learners): Random Functional Teaching (RFT) and the Greedy FT (GFT) strategy, with theoretical guarantee of reduction in the loss function when the learners are completely independently. On the top of that, the authors studied the effect of communication between learners and show that an affine transformation can significantly enhance the loss reduction in the beginning of the training phase. Empirical studies were also provided to validate the theoretical analysis. This paper studies an interesting/important problem in machine teaching and the theoretical results are sound and with valuable insights. We recommend to accept this paper. But in the meantime, this paper can be better motivated not just simply citing some other work, especially why not just teach one single learner that is learning a vector-valued function rather than multiple learners learning each component separately?
Decision: Accept (poster)