Locality Sensitive Teaching
Authors: Zhaozhuo Xu
Beidi Chen
Chaojian Li
Weiyang Liu
Le Song
Yingyan Lin
Anshumali Shrivastava
Venue: NeurIPS 2021 Poster (2021)
Keywords: Locality Sensitive Hashing
Machine Teaching
Internet-of-Things

Abstract: The emergence of the Internet-of-Things (IoT) sheds light on applying the machine teaching (MT) algorithms for online personalized education on home devices. This direction becomes more promising during the COVID-19 pandemic when in-person education becomes infeasible. However, as one of the most influential and practical MT paradigms, iterative machine teaching (IMT) is prohibited on IoT devices due to its inefficient and unscalable algorithms. IMT is a paradigm where a teacher feeds examples iteratively and intelligently based on the learner's status. In each iteration, current IMT algorithms greedily traverse the whole training set to find an example for the learner, which is computationally expensive in practice.  We propose a novel teaching framework, Locality Sensitive Teaching (LST), based on locality sensitive sampling, to overcome these challenges. LST has provable near-constant time complexity, which is exponentially better than the existing baseline. With at most 425.12x speedups and 99.76% energy savings over IMT, LST is the first algorithm that enables energy and time efficient machine teaching on IoT devices. Owing to LST's substantial efficiency and scalability, it is readily applicable in real-world education scenarios.

Locality Sensitive Teaching
Zhaozhuo Xu Rice University
Beidi Chen Stanford University Reidic@stanffrd edu
Chaojian Li Rice University chaojian. li@rice.edd
Ex22@rice.edi
Weiyang Liu
Le Song Biomap and MBZUAI
University of Cambridge and MPI-IS Tübingen w13960cam.c ac.uk
dasongle@gmail com
Yingyan Lin Rice University yingyan. lingrice.edu
Anshumali Shrivastava
Rice University and ThirdAl Corp. anshumali@rice. edu
Abstract
The emergence of the Internet-of-Thing: (IoT) sheds light applying the chine teaching (MT) algorithms for online personalized education on home de- vices. This direction becomes more promising during the COVID-19 pandemic when in-person education becomes infeasible. However, as one of the most influ- ential and practical MT paradigms, iterative machine teaching (IMT) is prohibited on IoT devices due to its inefficient and unscalable algorithms. IMT is a paradigm where teacher feeds examples iteratively and intelligently based the learner's status. In each iteration, current IMT algorithms greedily traverse the whole train- ing set to find an example for the learner, which is computationally expensive practice. We propose novel teaching framework, Locality Sensitive Teaching (LST),, based locality sensitive sampling, to overcome these challenges. LST has provable near-constant time complexity, which is exponentially better than the existing baseline. With at most 425. 125.12x speedups and 99.76% energy savings over IMT, LST is the first algorithm that enables energy and time efficient machine teaching on IoT devices. Owing to LST's substantial efficiency and scalability, it is readily applicable in real-world education scenarios.
1 Introduction
During the COVID-19 pandemic, there is an increasing demand for learning at home. Computer- based personalized education (CBPE) [1, 2, 3] on Internet-of- ofhinng (IoT) devices become essential as it improves the accessibility of students the educational resources and reduces the potential privacy risks. Due to the popularity of Coursera, Duolingo, and EdX, online on-device educa- tion has become increasingly more important nowadays. To better understand and improve the CBPE approaches in this context, we consider machine teaching (M') [4] as simplified yet helpful paradigm. Specifically, MT defines the problem where machine teacher constructs a minimal set of examples that allows student to learn target concept repeatedly. However, MT the loT device still prohibitive for two primary reasons: (1) MT technique does not allow real-time interaction between teachers and students. It is designed to work over static set and cannot incorporate real- time student feedback, (2) MT can not support on-device training due to the expensive cost spent in constructing this minimal teaching set.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Dataset
Teacher
Provide Information and Feedbacks
Student
8
A
Rx
LSH Sampler
00
00
Q0
01
1
00
10
Erplyy
Select Samples
1
0
Feod Samples
1
14
Data Preprocessing
2. Iterative Teaching
Figure I: A brief overview of the proposed LSTT algorithm. There two stages: 1) during data preprocessing. the indices of data samples are stored LSH hash tables. 2) during teaching stage, each iteration, the machine teacher uses the student's information to query an example from hash tables. Then the machine teacher feeds the example to the student.
As result, a more practical paradigm- - iterative machine teaching (IMT) [5, 6] has been proposed to achieve state-of-the-arr teaching performance. In IMT, the teacher interacts with the student in every iteration and aims teach the target concept with minimum number of iterations. Although IMT reduces both teaching set size and teaching iterations, it is still not efficient enough. The time and energy required by IMT are prohibitively expensive on IoT devices. There are two primary reasons: (1) IMT is not designed for real-time teaching. Current IMT uses a deterministic greedy algorithm, which traverses the entire dataset to find the optimal teaching example during each iteration. This linear time scan costs excessive time in real-world datasets, preventing more frequent interactions between machine teachers and students. (2) IMT has poor energy efficiency because the greedy scan requires scoring and ranking on the training examples. The energy budget of IoT devices such as integrated CPU-GPU System-on-Chinn Chipp (SoCs) cannot afford this expensive energy consumption in real-world teaching. Clearly, there is a gap between IMT and its deployment on IoT devices.
Contemporary IMT literature focuses on developing and analyzing theories. models, or paradigms in teaching. Few studies are addressing the trade-offs between teachability and efficiency. Although some IMT algorithms manage their potential applications in crowd-sourcing [7, 8, 9], personal edu- cation [4], or online data poison [10, 11], they do not consider the edge computing and IoT settings and ignore the substantial potential impact behind it.
Our work proposes a time and mefry--fffcciett IMT algorithm, namely Locality Sensitive Teaching (LST), that enables machine teaching on IoT devices. A real-life teaching observation inspires LST: a human teacher teaches a target concept to the student efficiently based on his or her knowledge in mind rather than brutal-force scan over all the course materials. Similarly, algorithm should provide optimal examples by looking up from a data structure rather than traversing the entire example set. Our LST algorithm effectively pre-indexes the teaching examples in hash tables. Then, given the student's current state at each iteration, we regard it as query and generate examples through efficient sampling using the hash tables [12]. Moreover, the time and energy efficiency by reducing the expensive linear scan into lightweight lookup in hash tables. As result, LST could be compatible with edge computing on IoT devices.
efficient IMT
significantly improve
Our proposal, LST, comes with three key questions: (1) how to reformulate the IMT problem as a sampling problem that involves efficient hash table data structures? (2) how maintain the identical teachability of IMT when utilizing the efficient hash table structures? (3) how to provide an efficient LST implementation loT devices that reduce energy and time consumption?
At a high level, we tackle these challenges as follows:
We reformulate IMT as an adaptive inner product sampling problem. We partition the teaching materials into two parts: (1) query: current state of student and the optimal model possessed by the machine teacher, (2) data: teaching examples denoted as feature-label pairs. We apply an asymmetric transformation that projects both parts as vectors. Then, we argue that the original IMT formula can be formulated as an adaptive inner product sampling. Given the query vector, the task is to sample data vectors with large inner products. Therefore, locality sensitive sampling can be introduced for efficient teaching examples generation.

---

We demonstrate, both theoretically and empirically, that LST preserves the teachability of IMT. Theoretically, we prove the LST can achieve exponential teachability with high probability. Em- pirically, the experiments on real-world teaching indicate that LST matches or even exceed the teachability of original IMT.
We provide novel LST system design on integrated CPU-GPU SoC platforms that performs time and energy-efficient teaching in real-world settings. We re-partition the locality sensitive sampling procedure into two parts: GPU-friendly random projection and CPU-friendly hash table lookups. Then, we exploit the benefits of fast matrix multiplications on GPU and efficient hash table lookups implemented on CPUs. Therefore, our LST system takes full advantage of the memory-constrainee CPU-GPU SoCs.
Through extensive experiments in real-world teaching scenarios, we demonstrate that LST per- forms exponential teachability that matches or even exceeds IMT while achieving at most 425.12x speedups and 99.76% energy savings on IoT devices. On server-based evaluation, LST achieves more than x speedups over IMT.
2 Related Work and Preliminaries
2.1 Iterative Machine Teaching
In machine teaching, a machine teacher obtains a minimal training set for a student to learn a con- cept. [4, 13] introduce a general teaching framework and build its connections to curriculum learn- ing [14]. [15] studies the machine teaching for Bayesian learners in exponential family and provides the teaching example by solving an optimization problem. [16] gives the linear learners" teaching dimension. Machine teaching has been found useful in cybersecurity [17], buman-computer inter- action [18], and human education [19]. [20, 6, 21] study the teaching scenario where the teacher aims to teach multiple concepts to a forgetful learner. [22, 6] assume that the learner black-box and study how the teaching should be performed. [23, 6] discuss how the teacher can teach multiple different learners. [24, 25, 26] connect the machine teaching problem with inverse reinforcement learning by studying inverse reinforcement learner. [27, 2] consider the machine teaching from an interpretable perspective. [28, 29] discuss the teaching model with a version space learner. [3] provides machine teaching extensions in human-in-the-loop settings. [30, 31, 32] study the machine teaching in theory.
Previous machine teaching works focus the improvement of teachability. [5] proposes the iter- ative teaching paradigm. In this paradigm, an omniscient teacher model knows almost everything about the student. Then, the omniscient teacher provides training examples based the student's status. [33] further generalizes this teaching scenario and introduces an optimal control approach to address sequential machine teaching. Built upon the same framework as [5], [6] looks into the IMT problem when the learner becomes blac-box. [34] proposes to perform iterative teaching by label synthesis while still preserving the provable teaching speedup. In work, we address the scalability bottleneck of IMT by leveraging the power of locality sensitive hashing.
This paper follows the same teaching setting as [5]. Without loss of generality, we mainly discuss the omniscient teaching model where the teacher knows the learner's ' full information. We apply our LST to speed up the omniscient teacher. We note that it is straightforward to improve the teaching quality and efficiency of more advanced teaching models using our proposed method.
2.2 Hashing- Sampling
This section briefly describes the recent development of efficient sampling and estimation via local- ity sensitive hashing (LSH) [35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46). The intuition of LSH is to hash similar items into the bucket of a hash table via functions such as random projection. For details of LSH, we refer Appendix A.
We denote p as the collision probability of LSH function. Therefore, given a query, an item will be retrieved with probability p. The precise form of p is determined by the LSH function family. This sampling view of LSH has been used in a wide range of applications, such as neural networks training [47, 48], kernel density estimation [49], outlier detection [50], and optimization [51].
The success of L.SH efficient inner product search sheds light on its application in adaptive sam- pling. More specifically, in this paper, given collection C of input and query Q, candidates S are
3

---

(a) Vanilla IMT
(b) Our Proposed LST
Figure 2: A motivating example on COVID-19 Teaching via CT images. The first 12 examples selected by IMT and LST examples presented on (a) and (b). We mark each COVID image with green circle and each regular image by the red cross. We observe that proposed LST selects diverse, confusing images while IMT keeps selecting same two images. Details are shown in Appendix
drawn from C, in which each 3; C. is sampled with p; 1, using LSH algorithm with special de- signed hashing [52]. Note here p; is a monotonically increasing function of Q Iz. Therefore, once that maps C into hash tables, the adaptive sampling for query Q
we pay linear preprocessing could be done via a few hash lookups. The LSH sampler component in Figure demonstrates the sampling process using LSH. Similar what has been mentioned in [51], the sampling scheme is is not
not valid distribution, i.e., Ex,er EC Pi * 1. Given query, the probability of sampling independent of the probability sampling 2y (i + j). However, we can still use it for unbiased
estimation. p3 is monotonic function of Q 24 because pt (1 (1 g(Q x.)) KY where g(Q x;) is the collision probability.
3 Locality Sensitive Teaching
This section first shows that finding a teaching example in the current IMT can be reformulated as an adaptive inner product sampling (AIPS) problem. Then we propose our LST algorithm to effectively and efficiently perform this adaptive sampling via Locality Sensitive Sampling (LSS).
3.1 A Motivating Example
To showcase the significance LST, we conduct an experiment on teaching students to recognize COVID-19 from CT images. We apply both LST and IMT binary-class CT image dataset [53] (labeled as normal or COVID-19, details are in Appendix D). After these 12 examples, LST achieves less loss than IMT. Figure shows the comparison of teaching examples. One observe that LST's teaching examples yield more diversity because of the randomness it introduces. In contrast, IMT simply repeats two examples without giving broader view of the other teaching set examples. This phenomenon suggests LST's potential to achieve more intuitively plausible teaching.
3.2 Reformulating IMT as Adaptive Sampling
Following a similar notation from [5], we denote N the number of samples, and S { ys ys) < i < N} as the input samples along with their labels Then, we construct a student model with loss function and learning rate 17. Given the model. we denote w; as the parameter of the student model at iteration i. w" is the optimal parameter obtained by the omniscient teacher. In each iteration, IMT selects an example by performing the following greedy algorithm:
Problem 1 (Greedy Teaching Algorithm (GTA) ). Given a large set S, the optimal parameter w and model parameter Wt, we want solve the following optimization problem:
a' *.v' arg min T7 ||iil 2n(wt w² w", VI
(x.y)eS
where we have VI Se((cr' .2)
Bur
This deterministic greedy algorithm usually sub-optimal. For illustration, we present toy ex- ample. We random sample 4 points from the synthetic dataset used by [5] and Section E. The data visualization is shown in Figure 3(a). Given the w" generated in [5], we perform logistic regression using IMT with GTA for 5 steps. We also perform brutal-force scan over all possible choices in

---

each iteration to find the optimal path in the first 5 steps. Train loss versus iterations is plotted in Figure 3(b). All methods are rerun 10 times. We observe that given the optimal path "AAAAA", GTA always chooses "CCCCC".
To tackle the issue, reformulate Problem 1 to Problem 2 via transformation functions f.g. We take linear regression and logistic regression classification as examples and derive corresponding f.g (shown in Appendix B). For other losses, we can derive f.g similarly when they are locally linearized. AIPS introduces randomness to help escape from local optima. As result, AIPS per- forms close to the optimal path on average. Here the parameter e determined by the LSH. In toy example, AIPS chooses among "AAAAA", "AAAAC" and "AACAA", which are near-optimal path. Therefore. the loss of AIPS in each iteration outperforms GTA in Figure 3(b).
Problem 2 (Adaptive Inner Product Sampling (AIPS)). Given a large set S and a query point q = g(w", w²), and O < < 1, we aim sample an example (x,, v) C S that for any (x', v²) S. f(z,y) y) g(w", w²) satisfies:
f(x, v) T g(w", w²) 2 e (I(a' (() g(w",,"" wd)).
(2)
where f and 9 are transformation functions with the same dimension.
3.3 Locality Sensitive Sampling as the Key Ingredient
Our algorithm uses LSS as an efficient sampler for Problem 2. Figure 1 shows the complete work- flow of the proposed LST. Note that Wy changes in every iteration, and for every iteration, ((V) computation is required to solve Problem 1. This time complexity is prohibitive in large-scale teach- ing problems. Therefore, we propose an efficient algorithm to perform IMT by sampling the trans- formed data vectors that produce large inner products f(r, y) g(w", w') at the cost of O(1).
Our algorithm guarantees to find an example for the student model that produces the maximum inner product of [xx y) " g(w",, ,,") with high probability. The LSS process is designed to sample from a weighted distribution. The prob- ability distribution function in this distribution monotonic function of the resulting inner product. We argue that such adaptive sampling should perform much better than random sam- pling. It is because the probability of selecting the correct sample is N for random sampling. On the other hand, for adaptive sampling, this N. because by
P
OTA
05
0.40
-22
0.67
016
65
1.5
(a)
(b)
Figure 3: A toy example. (a) visualization of data from 2 classes, red means 0, and blue is 1. (b) Performance after iterations of example path chosen by (1) GTA, (2) AIPS, (3) Optimal.
probability is much larger than 1. definition, the probability is monotonic to the value of the inner product.
Moreover, for any monotonic function, the sampling probability distribution changes according to the updates on w. Due to monotonicity, the highest probability of choosing the sample which pro- duces the maximum inner product in each iteration is always the highest. The key insight here is that there are two qualities
the inner product. f(x. y) and g(w", w²). With successive iteration, g(w", w²)) will change while f' [ax y) is always fixed. Therefore, we only need to perform one-time pre-processing to obtain [xx y) from all xr y pairs S and put f'xx, y) into the LSH tables. Then we can use g(w", w²) as the query for efficient LSS. Then in the following iterations, the hash table data structure remains the same while the query changes to g(w", w(+1). Therefore, a few hash table lookups are usually sufficient to perform the sampling. The guarantee of the query time is theoretically analyzed in section 4. The detailed sampling process is presented in Algorithm 2. The overall LST algorithm is put in Algorithm 1. In conclusion, after we pay one-time pre-processing effort of building the hash tables, we need a few or even one lookup in each iteration to obtain a high-quality teaching example, which is far better than random example and may outperform GTA example.
There are few technical subtleties due to the square of the gradient term. We present it in Equation 1. In Appendix B, we derive the full terms of fax y) and g(w=, w²) which is similar to a quadratic kernel. Both f and g are the corresponding feature expansion transformation. To increase the
5

---

efficiency of LST, we apply asymmetric transforms (details also in Appendix B) to deal with the quadratic terms and demonstrate its validated performance in practice (see experiments in section 6).
Algorithm 1: Locality Sensitive Teaching
Algorithm Locality Sensitive Sampling
(LSTT)
(LSS)
Result: Model
Result: Sample id
Input: D = {z, y). w", w',
Input: Query q
+ permute(1,L):
1 + 0;
for i in do hr...h.
π 5 permute(1. I.).;
for in π do
(fr. vi));
compute H (q) for hash table i; if Bucket for (q) is not Empty then
insert i (id) in L hash tables;
end
S - elements in in B;
I <-;; 0:
random(S);
while not converged do
else
j - (. (w= v²") (Algorithm2)) 2);
- + 1;
w 7( (VI(II)))))
end
end
end return id
return
Theoretical Insights and Discussions
As shown in section 3.2, we reformulate IMT an adaptive inner product sampling (AIPS) and provide LST. Here we provide comparison between LST and the current IMT. As shown in Appendix B, GTA used in IMT can be regarded as arg max; g(w", w) fxx; Vi), which is an exact maximum inner product search (MIPS) problem. [5, 6] only show improvements over SGD, suggesting that GTA local optimal solution.
Our AIPS algorithm introduces randomness to GTA. If both [ yolll and [|g(",, will are as- GTA and nearest neighbor search (NNS)
sumed to be the same constant, then from [52], problem are equivalent, formally,
arg max g(w", ,w) f(z, H.) zs arg min [lg("", ,w) - [[a,
Instead of doing exact MIPS, AIPS random samples above. The efficiency of AIPS is directly quantified by p log
approrimate nearest neighbor defined logg1 < 1, where Pt, P2 are defined in
Section 2.2. The space complexity grows as +n) while the query time grows as O(n log n),, where n is the size of the dataset. Thus, smaller indicates better theoretical performance.
Theorem 1. With a data-structure using functions from (So, cSo, PI, Pa),-PPP)ssiii LSH family H. takes query time Onn log n)) and space +P) to solve AIPS, where Tog
lo
Theorem shows the time and space complexity for AIPS. In section F, we provide an ablation study of efficiency and accuracy trade-off of our algorithm. Furthermore, asymmetric transformations can be used in accelerating AIPS. similar trade-off with proofs is shown in [52].
Theorem (Exponential Teachability of LST). Following the theoretical setting in the synthesis- based teaching [5], the teacher is assumed be able to provide any examples from
X' = {a E B.d. ||>||| < R):
y == (Classification) IR (Regression)
Let 1) + 0 denote the fixed learning rate of the student. Let E(.,-) denote the loss function. Moreover, ((---) has the following propriety: for any E Rd, there exists ry with y + 0 and ||yl|
R
[w
that, i >(w -w w²) and Y, we have
0 < vV (w. (100 1
(3)
Suppose for a (8,, cS. Pt. P2) -..pP--sensie sensitive hashing function family H. where So max; f fā, T) g(w", w²) and
7 (w' - -w") and
(4)

---

then LST can achieve exponential teachability with probability at least P1 in a single iteration.
Theorem 2 shows the condition and probability of LST achieve exponential teachability in each iteration. There is a probability P1 to perfectly imitate the omniscient teacher. More importantly, introduces some randomness into the teaching algorithm and therefore makes the teaching examples more diverse and plausible for humans. Note that, all Lipschitz smooth and strongly convex loss functions can satisfy Equation 3. Using Theorem 2, we can easily extend LST's exponential teacha- bility to the other teaching scenarios such as combination -obbbattion-bsedd teaching [5], (rescaled) pool-based teaching [5] and black-box teaching [6]. Detailed proofs are shown in Appendix C.
Time Complexity Analysis: Theorem and 2 provide the analysis for the LSS algorithm to achieve the exponential teachability with provably sub-linear time complexity. In practice,
need pay one-time pre-processing time O(NKI) to build the hash tables, where N is the number of samples, K" is the number of hash functions in each hash table, and L is the number of hash tables. During inference, we usually only use a few lookups (typically just one), i.e., (1) complexity, in each iteration to get a high-quality teaching example. We also conduct an empirical experiment show the dedicated trade-off between the accuracy and efficiency using different K and L. Therefore, LST reduces the time complexity for each teaching iteration from (NN) to (1) by hash table lookups.
5 Locality Sensitive Teaching on Integrated CPU-GPU SoC
In this section, we present the LST system implemented on an integrated CPU-GPU SoC platform. In recent machine learning based IoT applications such as autonomous driving, smart home, and intelligent robots, devices with integrated CPU-GPU architecture (e.g.. NVIDIA's Jetson [54] series) is gaining increasing preference. The smart co-optimization155, 56] of machine learning algorithms on CPU and GPU resources determines their overall performance on IoT deployment. In this work, our system design is based on two observations: (1) The CPU resourees could be more utilized on the integrated CPU-GPU SoC. For instance, a dual-core NVIDIA Denver 2 64-bit CPU and quad- core ARM C557ex-A57 are equipped on NVIDIA TX2 [57] SoC. Vision-based machine learning applications such as object detection [55] do not regard on-chip CPU as a computation resource. In our problem, if can migrate some of the computation to those powerful CPUs, the overall efficiency can be improved. (2) Hashing is cheap on CPU. Most GPUs suffer memory constraints. Although GPU-based LSH hash tables are 1.5x faster over CPU [58] in nearest neighbor search, stores the hash table entirely on GPU memory. As result, the availability of GPU for other machine learning operations is limited. To tackle the issue, hybrid CPU-GPU LSH systems [58, 59] become powerful in both academics and industry.
In our LST systems integrated CPU-GPU SoC, we implement LSH by separating the random projection and hash table lookups into GPU and CPU. We first generate hash codes of data vectors by cased random matrix multiplication via CuPy [60] and compiled CUDA kernels. Then, we insert the hash codes to hash tables built on the CPU. The query vector is transformed into hash codes in the query phase using the same random matrix in GPU. Then, the query hash codes are sent the CPU and perform hash table lookups. We provide Cython wrapping for the implementation to make PyTorch friendly. We believe this implementation would be more beneficial for the community as it can be easily plugged into any deep learning model.
6 Experiments
In this section, we experiment the effectiveness and efficiency of LST in various scenarios. We first perform the algorithmic level evaluation of LST on different datasets. There are three questions that we would like answer: (1) does the LST performs better or the same compared to the current IMT in teaching the learner model towards faster convergence in iteration-wise? (2) compared to the IMT, does the LST algorithm reduce the computation time when achieving the same performance? (3) is the proposed LST algorithm scalable in the dataset that the IMT is almost infeasible in practice? Next, we conduct experiments to demonstrate the scalability of LST on loT devices. There are two questions that we would like to answer: (1) does the LST's teachability robust to IoT devices? (2)
compared to IMT, is the LST energy efficient on loT devices? Note that we present the results of regression in this section. For classification results, please refer to Appendix E.
7

---

Tisle loss versun hersdcn
Test loss vertu herzzoe
Toil loss verte Persdon
Test lose vertes boysdon
Tronkes
500
1000
2000
(a) abalone train
(b) abalone test
(c) space ga train
(d) space ga test
Trsii
Tast loss hersttoe
Toxt loss hursioon
Tiee Bun
2.30
3.
130
206
40 130
300
50
150
53
02
150
200
(c) mg train
(f) mg test
(g) slice train
(h) slice test
Figure 4: Average train and test loss versus iteration of: abalone in (a) and (b), space- ga in (c) and (d), mg (e) and (f), slice (g) and (h). Results have demonstrated that both LST and the current IMT are superior to stochastic SGD in guiding the leamer model towards faster convergence. Meanwhile, LST has a similar performance with IMT as their train and test losses descend almost the same way.
Datasets. In the experiments, we use four regression datasets to demonstrate the performance of our LST. First, we use abalone, space ga [61] and mg dataset from LIBSVM [61] and UCI dataset [62]. The abalone dataset contains 4177 8-dimensional feature vectors. The space ga and mg datasets contain 3107 and 1385 7-dimensional vectors, respectively. Then we test LST's performance on large scale regression datasets to validate its scalability. We use slice dataset from UCI dataset [62]. slice dataset contains 53500 training samples and 42800 testing samples. Each sample is 74- dimensional vector. We use slice only for algorithm level evaluation as it causes memory exhaustion on loT devices. We randomly split 30% of samples in each dataset as test set while others are training set. All datasets are under MIT license.
6.1 Evaluation on Locality Sensitive Teaching
In this section, we present the performance of our proposed LST algorithm in teaching regression models towards fast convergence. The evaluation is on a server with 1 Nvidia Tesla V100 GPU and two 20-core/40-thread processors (Intel Xeon(R) E5-2698 v4 2.20GHz). Given the four regression datasets, we set the learner model as a linear regression model with Mean Square Error (MSE) loss to compare the performance of LST, IMT, and stochastic SGD. Here, we consider the stochastic SGD as a random teaching approach. In each step, the three algorithms above choose an example from the dataset and feed into the learner. The learner model then processes the example and performs AdaGrad[63] to update the weights accordingly. We use early stopping on the learner model to prevent overfitting. Details of LST for classification are in Appendix E.
Convergence. In Figure 4, we plot the train/test loss versus iteration for three teaching approaches mentioned above the regression dataset. From the (a), (b), (c), and (d), we observe that the LST and IMT [5] algorithm teaches the learner models that converge to optimum with much less iterations than stochastic SGD. This performance shows that both LST and IMT leads to faster iteration- wise convergence of learner models in train and test set. Moreover, in each step, the learners' train and test losses taught by LST are close or even better than IMT. In sub-figure (c) and (d), we show that LST also approximates IMT in teaching towards faster convergence even when the gap of train losses and test losses between IMT and stochastic SGD are small. This result demonstrates that LST's approximation eтror to the optimal path is affordable even in some settings that IMT only has few advantages towards stochastic SGD. In sub-figure (e) and (f), we demonstrate that LST and IMT share similar performance in large scale regression sets (e.g.slice) on average. Moreover, we observe that about 30% LST instances outperform IMT. The effectiveness experiment answers the first question. LST can achieve the same fast convergence effect in iteration wise when compared
8

---

Trats loss venso Srww
0.18
Trale loss versun Sine
Tran kow meraaa tire
Triis losa verse bew
43-
0:1-
0.0
0.04
30-
Tran tine
Tranntin
(a) abalone
(b) space_ga .g
(c) mg
(d) slice
Figure 5: Average train loss versus the train time (scconds in log scalc) of abalone in (a), space_gs -ane-gaadn in (b), mg (c), slice in (d). The time unit second. Results have shown that LST 2000x times faster than the current
IMT to achieve the same loss at each step.
to IMT. With non-negligible probability, LST's teachability outperforms IMT in teaching regression towards convergence with fewer iterations.
Speed. In Figure 5, we plot the train loss versus train time (seconds in log scale) for LST and IMT in four regression sets. In each iteration, record the time for teaching algorithms to select an example and the weight update time for the learners given this example. In the four sub-figures, we observe consistent gap between two approaches in time. At the same loss level during training, our LST teaches 2000 faster than IMT on average. For the large scale slice dataset, it takes 404.95 seconds average for IMT to finish online deployment at scale. Our LST tackles the issue by reducing the time to 0.196 seconds while preserving the same performance in iteration-wist wise. This significant acceleration makes LST scalable in large scale teaching scenarios. This experiment answers the second and third questions. LST is 2000 faster than IMT while achieving the same iteration-wise fast convergence. Moreover, LST is efficient in teaching when performed on large scale datasets. We also perform a parameter study in Appendix F.
iteration. This long-time prevents IMT from
6.2 Scalability on loT Devices
In this section, we compare LST and IMT Nvidia TX2 devices. For detailed settings, we refer to Ap- pendix G. We first observe that the iteration-wise performance remains identical to the evaluation on the server. This phenomenon answers the first ques- tion: LST's teachability is robust in IoT devices by achieving exactly the same iteration-wise conver- gence as server-based experiments. Then, in Table 1, we present the energy savings and speedups of LST over IMT four datasets. According the results, we observe that LST achieves least 98.73% energy savings and 117.20x speedups over IMT. In the synthetic classification dataset, LST is 306.12x faster than IMT with 99.67% energy savings. This performance gain is fewer than server-based experiments due to the less available resources on TX2 SoCs (e.g.. 105W power bud- get CPU in sever setting vs. 7.5W power budget in IoT setting). However, this improvement still promising and answer the second question: LST can gain at most 99.76% energy savings with over 100x speedups compared with IMT on IoT devices.
Dataset
Energy Savings
Speedups
abalone space ga
99.76%
425.12x
99.34%
149.07 x
mg
98.73%
117.20x
Table 1: Efficiency of LST over IMT on TX2
Concluding Remarks
The inefficiency of iterative machine teaching (IMT) prevents it from being used in loT-based teach- ing scenarios at home. There no sub-linear time iterative teaching algorithm that enables teaching in large-scale real-world settings before our work. The paper proposes practical and fast teach- ing approach. By reformulating IMT's optimization problem to an adaptive sampling problem, we propose a Locality Sensitive Teaching (LST) algorithm. LST achieves exponential teachability and reduces the time complexity each iteration from (N), where N the number of teaching exam- ples, to few O(1) ) lookups in hash tables. Moreover, we design an LST system that fully exploits the resources of integrated CPU-GPU SoCs on IoT devices. We demonstrate, both theoretically and em- pirically, LST's teachability improvements, speed acceleration, and tremendous energy reductions

---

over IMT during experiments on IoT devices. The development of LST makes teaching algorithms feasible on more on-device personalized education applications.
Acknowledgements
Zhaozhuo Xu and Anshumali Shrivastava supported by the National Science Foundation IIS- 1652131, SGGDATA-1838177 AFOSR-YDD YIP ONR BRC grant on Randomized Numerical Linear Algebra. Chaojian Li and Yingyan Lin are supported by the National Science Foundation EPCN under No. 1934767. Weiyang Liu is supported by a Cambridge- Tübingen Fellowship, an NVIDIA GPU grant, DeepMind and the Leverhulme Trust via CFI. We would like to thank Tracy Volz and Elizabeth Festa for great discussion on scientific writing.
the ONR DURIP Grant, and the
References
[1] Christos Athanasiadis, Enrique Hortal, Dimitrios Koutsoukos, Carmen Zarco Lens, and Stylianos Asteriadis. Personalized, affect and performance-drrven computer-based learning. In CSEDU (1), pages 132-139, 2017.
[2] Oisin Mac Aodha, Shihan Su, Yuxin Chen, Pietro Perona, and Yisong Yue. Teaching categories to human learners with visual explanations. In CVPR, 2018. 1,
[3] Edward Johns, Oisin Mac Aodha, and Gabriel J Brostow. Becoming the expert-interactive multi-class machine teaching. In CVPR, 2015. 1,
[4] Xiaojin Zhu. Machine teaching: An inverse problem to machine learning and an approach toward optimal education. In AAAI, 2015. 1,
[5] Weiyang Liu, Bo Dai, Ahmad Humayun, Charlene Tay, Chen Yu, Linda B. Smith, James M. Rehg, and Le Song. Iterative machine teaching. In ICML, 2017. 2, 3, 4, 6, 7, 8, 19
[6] Weiyang Liu, Bo Dai, Xingguo Li, Zhen Liu, James Rehg, and Le Song. Towards black-box iterative machine teaching. In ICML, 2018. 2, 2, 6.7
[7] Yao Zhou, Fenglong Ma. Jing Gao, and Jingrui He. Optimizing the wisdom of the crowd: Inference, learning, and teaching. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 3231-3232, 2019. 2
[8] Yikun Ban and Jingrui He. Generic outlier detection in multi-armed bandit. In Proceedings of the 26th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pages 913-923, 2020. 2
[9] Yao Zhou, Arun Reddy Nelakurthi, Ross Maciejewski, Wei Fan, and Jingrui He. Crowd teach- ing with imperfect labels. In Proceedings of The Web Conference 2020, pages 110-121, 2020. 2
[10] Scott Alfeld, Xiaojin Zhu, and Paul Barford. Data poisoning attacks against autoregressive models. In AAAI, 2016. 2
[11] Xuezhou Zhang, Xiaojin Zhu, and Laurent Lessard. Online data poisoning attacks. Learning for Dynamics and Control, pages 201-210, 2020. 2
[12] Ryan Spring and Anshumali Shrivastava. A unbiased and efficient class of Ish-based samplers and estimators for partition function computation in log-linear models. arXiv preprint arXiv:1703.05160. 2017. 2, 15
[13] Xiaojin Zhu, Adish Singla, Sandra Zilles, and Anna Rafferty. An overview of machine teaching. arXiv preprint 1801v=1801.05922 2018. 3
[14] Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. Curriculum learning- In ICML, 2009. 3
10

---

[15] Xiaojin Zhu. Machine teaching for bayesian learners in the exponential family. In NIPS, 2013.
3
[16] Ji Liu, Xiaojin Zhu, and H Gorune Ohannessian. The teaching dimension of linear learners. In ICML, 2016. 3
[17] Shike Mei and Xiaojin Zhu. Using machine teaching to identify optimal training-set attacks on machine learners. In AAAI, 2015.
[18] Christopher Meek, Patrice Simard, and Xiaojin Zhu. Analysis of design pattern for teaching with features and labels. arXiv preprint arXiv:/611.05950 2016. 3
[19] Faisal Khan, Bilge Mutlu, and Xiaojin Zhu. How do humans teach: On curriculum learning and teaching dimension. In NIPS, 2011. 3
[20] Anette Hunziker, Yuxin Chen, Oisin Mac Aodha, Manuel Gomez Rodriguez, Andreas Krause, Pietro Perona, Yisong Yue, and Adish Singla. Teaching multiple concepts to forgetful learner. In NewrIPS, 2019.
[21] Yao Zhou, Arun Reddy Nelakurthi, and Jingrui He. Unlearn what you have learned: Adaptive crowd teaching with exponentially decayed memory learners. In KDD, 2018.
[22] Sanjoy Dasgupta, Daniel Hsu, Stefanos Poulis, and Xiaojin Zhu. Teaching a black-box learner. In ICML, 2019.
[23] Teresa Yeo, Parameswaran Kamalaruban, Adish Singla, Arpit Merchant, Thibault Asselborn, Louis Faucon, Pierre Dillenbourg, and Volkan Cevher. Iterative classroom teaching. In AAAI, 2019. 3
[24] Luis Haug, Sebastian Tschiatschek, and Adish Singla. Teaching inverse reinforcement learners via features and demonstrations. In NeurIPS, 2018. 3
[25] Sebastian Tschiatschek, Ahana Ghosh, Luis Haug, Rati Devidze, and Adish Singla. Learner- aware teaching: Inverse reinforcement learning with preferences and constraints. arXiv preprint arXiv: 1906::/90600044 2019. 3
[26] Parameswaran Kamalaruban, Rati Devidze, Volkan Cevher, and Adish Singla. Interactive teaching algorithms for inverse reinforcement learning. In IJCAI, 2019.
[27] Yuxin Chen, Oisin Mac Aodha, Shihan Su, Pictro Perona, and Yisong Yue. Near-optimal machine teaching via explanatory teaching sets. In AISTATS, 2018. 3
[28] 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 NeurlPS, 2018.
[29] Mohamadreza Ahmadi, Bo Wu, Yuxin Chen, Yisong Yue, and Ufuk Topcu. Barrier certificates for assured machine teaching. In ACC, 2019.
[30] Ziyuan Gao, Hans Ulrich Simon, and Sandra Zilles. On the teaching complexity of linear sets. In ALT, 2015. 3
[31] Sandra Zilles, Steffen Lange, Robert Holte, and Martin Zinkevich. Teaching dimensions based on cooperative learning. In COLT, 2008. 3
[32] Rahim Samei, Pavel Semukhin, Boting Yang, and Sandra Zilles. Algebraic methods proving sauer's bound for teaching complexity. Theoretical Computer Science, 558:35-50, 2014.
[33] Laurent Lessard, Xuezhou Zhang, and Xiaojin Zhu, An optimal control approach to sequential machine teaching, arXiv preprint wrXiv:1810.06177 2018.
[34] Weiyang Liu, Zhen Liu, Hanchen Wang, Liam Paull, Bernhard Schölkopf, and Adrian Weller. Iterative teaching by label synthesis. In NewrIPS, 2021. 3

---

[35] Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: Towards removing the curse of dimensionality. In STOC, 1998. 3
[36] Piotr Indyk and David Woodruff. Polylogarithmic private approximations and efficient match- ing. In Theory of Cryplography. 2006. 3
[37] Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S Mirrokni. Locality-sensitivy hashing scheme based on p-stable distributions. In Proceedings of the twentieth annual symposium on Computational geometry (SoCG), pages 253-262, 2004, 3
[38] Alexandr Andoni, Piotr Indyk, Huy Nguyen, and Πya Razenshteyn. Beyond locality- sensitive hashing. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pages 1018-1022 1028. SIAM, 2014. 3
[39] Alexandr Andoni, Piotr Indyk, TMM Laarhoven, Ilya Razenshteyn, and Ludwig Schmidt. Practical and optimal Ish for angular distance. In Advances in Neural Information Process- ing Systems (NIPS), pages 1225-1233, Curran Associates, 2015.
[40] Alexandr Andoni and Ilya Razenshteyn. Optimal data-dependent hashing for approximate near neighbors. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing (STOC), pages 793-801, 2015.
[41] Piotr Indyk and Tal Wagner. Approximate nearest neighbors in limited space. In Conference On Learning Theory, pages 2012-2036. PMLR, 2018.
[42] Alexandr Andoni, Thijs Laarhoven, Ilya Razenshteyn, and Erik Waingarten. Optimal hashing- based time-space trade-offs for approximate near neighbors. In Proceedings of the Twenty- Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 47-66. SIAM, 2017. 3
[43] Alexandr Andoni, Piotr Indyk, and Ilya Razenshteyn. Approximate nearest neighbor search in high dimensions. arXiv preprint 1rXiv:/806.090 7, 2018. 3
[44] Yihe Dong, Piotr Indyk. Ilya Razenshteyn, and Tal Wagner. Learning space partitions for nearest neighbor search. In International Conference on Learning Representations, 2019.
[45] Hao Chen, Iaria Chillotti, Yihe Dong, Oxana Poburinnaya, Ilya Razenshteyn, and M Sadegh Riazi. (SANNS}: Scaling up secure approximate k-nearest neighbors search. In 29th (USENIX) Security Symposium ((USENIX) Security 20), pages 2111-2128, 2020. 3
[46] Xiaoyun Li and Ping Li. Rejection sampling for weighted jaccard similarity revisited. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), 2021. 3
[47] Ryan Spring and Anshumali Shrivastava. Scalable and sustainable deep learning via random- ized hashing. arXiv preprint arXiv: 1602008124444 2016. 3
[48] Beidi Chen, Tharun Medini, and Anshumali Shrivastava. Slide: In defense of smart al- gorithms over hardware acceleration for large-scale deep learning systems. arXiv preprint 19X:v:1903.03/29, 2019. 3, 15
[49] Benjamin Coleman and Anshumali Shrivastava. Sub-linear race sketches for approximate ker- nel density estimation on streaming data. In Proceedings of The Web Conference 2020, pages 1739-1749, 2020. 3
[50] Chen Luo and Anshumali Shrivastava. Arrays of (locality-sensitivee) count estimators (ace) anomaly detection on the edge. In Proceedings of the 2018 World Wide Web Conference, pages
2018.
[51] Beidi Chen, Yingchen Xu, and Anshumali Shrivastava. Fast and accurate stochastic gradient estimation. Advances in Neural Information Processing Systems, 1233999912334, 2019. 3,
4, 15
[52] Anshumali Shrivastava and Ping Li. Asymmetric Ish (alsh) for sublinear time maximum inner product search (mips). In NIPS, 2014. 4,
12

---

[53] Jinyu Zhao, Yichen Zhang. Xuehai He, and Pengtao Xie. Covid-ct-dataaee a ct scan dataset about covid-19. arXiv preprint arXiv:2003. 2020. 19
[54] Nathan Otterness, Ming Yang. Sarah Rust, Eunbyung Park, James H Anderson, F Donelson Smith, Alex Berg, and Shige Wang. An evaluation of the nvidia tx for supporting real-time computer-vision workloads. In 2017 IEEE Real-Time and Embedded Technology and Appli- cations Symposium (RTAS), pages 353-364. IEEE, 2017. 7
[55] Waqar Ali and Heechul Yun. Protecting real-time gpu applications integrated cpu-gpu soc platforms. ArXiv e-prints, 2017. 7
[56) Soroush Bateni, Zhendong Wang, Yuankun Zhu, Yang Hu, and Cong Liu. Co-optimizing per- formance and memory footprint via integrated cpu/gpu memory management, an implemen- tation autonomous driving platform. In 2020 IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), pages 310-323, IEEE, 2020. 7
[57] NVIDIA Inc. wwweeeaaahhhheeeeeeeeeeeeeeeeeee
NVIDIA Jetson TX2.
https:/ htops://www... http://www.viiiddd .wwiia..ia......... www.coom///me/ee en-ussuuu//// accessed 2020-09-01. 7,
21
[58] Yiqiu Wang, Anshumali Shrivastava, Jonathan Wang. and Junghee Ryu. Flash: Randomized al- gorithms accelerated over cpu-gpu for ultra-high dimensional similarity search. arXiv preprint arXiv:1709.01190, 2017.
[59] Nicholas Meisburger and Anshumali Shrivastava. Tera-slash: A distributed energy-efficient mpi based Ish system for tera-scale similarity search. arXiv preprint arXiv:2008.03260, 2020.
[60] Ryosuke Okuta, Yuya Unno, Daisuke Nishino, Shohei Hido, and Crissman Loomis. Cupy: A numpy-compatible library for nvidia gpu caleulations. In NIPS LearningSys Workshop, 2017. 7
[61] Chih-Chung Chang and Chih-Jen Lin. LIBSVM: library for support vector machines. ACM Transactions on Intelligent Systems and Technology, 2:27:1-27:27, 2011. Software available http:// //wb:://wwww csie. ntu edu. tw/-<jjlin/lbbavm 8, 19
[62] Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. 8
[63]
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learming Research, 120ul):2121-21599 2011.
8
[64] Moses S Charikar. Similarity estimation techniques from rounding algorithms. In STOC, 2002.
15
[65] Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely con- nected convolutional networks. Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4700 2017. 19
[66] Jan-Mark Geusebrock, Gertjan J Burghouts, and Amold WM Smeulders. The amsterdam
library of object images. IJCV, 2005. 19
[67] Siddharth Gopal. Adaptive sampling for sgd by exploiting side information. In ICML, 2016.
19
[68] Chaojian Li. Tianlong Chen, Haoran You, Zhangyang Wang, and Yingyan Lin. Halo: Hardware-aware learning to optimize. In Proceedings of the European Conference Com-
puter Vision (ECCV), September 2020. 21
[69] Diana Wofk, Fangchang Ma, Tien-Ju Yang, Sertac Karaman, and Vivienne Sze. Fastdepth: Fast monocular depth estimation on embedded systems. In 2019 International Conference on Robotics and Automation (ICRA), pages 6101-6108. IEEE, 2019. 21
13

---

[70] Patrick Mochel and Mike Murphy, sysfs The filesystem for exporting kernel objects. https: //www.kerneeee http://wwww...ooooooooaaaaatttta
txt, accessed 2019-11-
21. 21
[71] Texas Instruments Inc. INA3221 Triple-Channel, High-Side Measurement, Shunt and Bus Voltage Monitor. http://www ti. com/pproduct/NAA321, accessed 2019-11-21. 21
14


Reviews:
[{"review_id": "zD-Wg-v6foO", "reviewer": "Reviewer_2Qsa", "summary": "The paper proposes locality sensitive teaching (LST) which can be applied to IoT and online personalized education. In iterative machine teaching (IMT), the teacher selects example in each iteration for the student to learn, based on a greedy search algorithm which is expensive. The authors reformulate the optimization into a maximum inner product search problem, and use locality sensitive hashing (LSH) in the searching process to reduce the iteration-wise cost from $O(n)$ to $O(1)$. Theoretical analysis and practical hardware design are provided. Experiments validate the advantage of LST.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well organized and the writing is clear. The idea and derivation in each step is easy to follow.\n\nOnline machine teaching problem is important in practice and has many good applications. LSH is a classical method in information retrieval. Applying LSH to machine teaching leads to a substantial efficiency improvement, which is a solid contribution on this topic.\n\nI like this paper since the formulation of the original optimization objective to MIPS is interesting and novel. Then the idea to use LSH is straightforward and appropriate. The method is described clearly, and the theory is adequate to justify the proposed LST. Also, it is good to discuss the hardware (GPU-CPU) design, which leads to further practical benefit and is helpful for the practitioners. The experiments are convincing, and the speedup is significant. Thus, I think this work can make a good contribution to NeurIPS.\n\nDetailed comments and questions:\n\n1) Typos on line 115 and 195.\n\n2) In Algorithm 1, $\\pi$ is not defined in the first loop; In Alg 2, $|B|$ is not used.\n\n3) Is (2) and Theorem 2 strict for both regression and classification? Is it possible to extend Theorem 2 to more models?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "wfSQHeGZ0qn", "reviewer": "Reviewer_QqeN", "summary": "By reformulating Iterative Machine Teaching’s (IMT) optimization problem to an adaptive sampling problem, the papers proposes a Locality Sensitive Teaching (LST) algorithm. LST achieves exponential teachability and reduces the time complexity of each iteration from O(N), where N is the number of teaching examples, to few O(1) lookups in hash tables. They also attach the IoT perspective to the problem.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Novelty:\nThe paper claims LST as the first algorithm that enables energy and time efficient machine teaching on IoT devices.\n\nStrengths:\n1. The paper focuses on 2 aspects - improving running metrics like speed, energy. And, overcoming greedy search of usual IMT systems.\n2. The paper uses both theoretical and empirical approach as defense of the work. This seems to be concrete.\n3. The paper's handling of concepts at mathematical rigor (backed by supplementary) is commendable.\n4. Paper is well written.\n\nWeakness:\n1. Code is not available to check due to some permission issue.\n2. The performance objective of the task - its accuracy - how that can be improved is not focused on. The trade-off between time/energy and accuracy needs a discussion.\n3. The scalability section needs some validation - is this the correct approach to validate?\n4. Adherence to practical usage (apart from Covid theme) should have increased the paper's value.\n5. Mixing of IoT with the approach needs some more gelling from reader's continuity of flow perspective.\n\nRelevance to NeurIPS:\nMore relevant to ICML/AAAI/KDD type conferences in contrast to Neural Information Processing. In fact IoT and EdTech conferences will also appreciate this work. However, for a change of inter-disciplinary flavor, bringing in the IoT perspective in ML is appreciated.\n\nEffort: Significant effort has been done in thought process, however implementation wise would have like more rigor.\n\nSuggestions:\n1. Does the toy example in Fig.3 substantiate the approach's efficacy in terms of generalization? \n2. Some discussion on bias / priors will help clarify the learning part.\n3. How collision in the hash table can downgrade performance? Any heuristics to support?\n4. Can adversarial examples affect the algorithm?\n5. \"D Motivating Example Settings\" - this could have been expanded more to get an insight in the practical application.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not applicable, Skip.", "review_text": "", "extra_scores": {"ethical_concerns": "Paper plagiarism is 11% at Docoloc: https://www.docoloc.de/d88c4d5162dd4b21eeb6add446e2b5bbCEuFHG85rulAsphkx9/en/konto.hhtml?dogetresult=51. So it is OK - cleared as green signal.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "Rvo4tqiZbhW", "reviewer": "Reviewer_ycpC", "summary": "The paper applies locality sensitive hashing to online teaching, where the machine uses a student’s information to retrieve a data sample from hash tables. The paper claims several contributions. (1) Propose a novel teaching framework, called Locality Sensitive Teaching (LST) for the retrieval. (2) LST has provable near-constant time complexity and is exponentially better than existing baseline (i.e. linear scan) (3) LST achieves 425.12x speedup over the linear scan baseline.  ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "CT image, as in section 3.1 of the paper. Specifically, the paper formulates similar images retrieval regarding a query image as maximum inner product search of the query image and image database. With this formulation, the paper extends similarity retrieval to a practical domain. \n\nDespite the above merits, the paper needs further improvements in the techniques and experiments to justify the claimed contributions. \n\n1.\tThe paper claims LST is novel. But the paper does not explain the differences between LST and a related work ALSH. It seems that the paper simply applies ALSH asymmetric transformation to similar images retrieval. It will be good if the paper can explicitly point out the novel designs in LST that are not in ALSH. \n\n2.\tThe paper claims near-constant complexity of LST as a key contribution in the Abstract. I can only find two appearances of words “constant” in the paper and cannot find the proof for “near-constant complexity”. If the paper means “sub-linear complexity”, than it is the contribution of ALSH and many pioneering works in maximum inner product search. \n\n3.\tThe paper claims 425.12x speedup over baseline but only uses linear scan as baseline. Linear scan is a weak baseline in the field of maximum inner product search. The authors may compare LST with more state-of-the-art baselines such as ALSH. \n\n[Comments regarding author response]\nThank you for the author response. Maybe I was biased towards the baselines so I requested more experiments evaluating existing algorithms for MIPS in the original review. I have increased my rating from 5 to 6 and I am happy to see this paper accepted. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The proposed method has potential contributions to energy reduction and privacy preserving. The authors claimed no negative impact to the society. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "KBDR4edjc1c", "reviewer": "Reviewer_sssx", "summary": "This paper considers an iterative machine learning task of how an omniscient teacher choosing learning data optimally such that the student can learn fast from the data via gradient descent. It proposes an adaptive inner product sampling (AIPS) algorithm that uses locality-sensitive hashing-based sampling to make the search much more efficient than greedy approaches. The authors show the exponential teachability of their approach and provide empirical studies.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The main novelty of the work is to transform the iterative machine learning problem to an adaptive inner product sampling problem with transform functions f and g. Combined with hashing structure, the proposed algorithm only need to traverse the dataset in pre-processing step to calculate a feature representation $f(x_i,y_i)$ for each data point $(x_i,y_i)$, which enables the exponential teachability. \n\nMajor question/concern:  \n1.  When you say \"reformulate problem 1 to problem 2\" at Line 158, does that mean there always exists transformation functions f and g such that problem 2 is equivalent to problem 1? Is there an explicit way to construct f and g for general loss function l apart from MSE and logistic regression?\n2.  Presentation of the paper is incomplete, please define notations before using them even they are conventional, especially for key results. E.g., what does the notation permute(1, L) and function H(\\cdot) mean in Algorithm 2? What does $(S_0,cS_0,p_1,p_2)$-sensitive hashing function family mean in Theorem 2. \n3.  The test error for slice test in the plot (h) of figure 4 is way higher than the training error, why?\n\nMinor comments:  \n1.  It's not a good idea to mix related work and preliminaries, as preliminaries should give clear definitions and results as a basement for the work. Once you mix them it's hard for readers to find such information and the way you present them is not clear and rigorous.\n2.  You should link the reference by using cite, and ref the equations using eqref, e.g. in line 205.\n3.  The order of figures 1,2,3 is inappropriate, as you mention figure 2,3 before figure 1.\n4. Expressions like \"Following the theoretical setting in the synthesis-based teaching [5]\" should not show up in a Theorem. You can either explicitly state the setting outside the theorem and ref it in theorem, or explicitly state the setting inside the theorem. Either way, settings and assumptions should be explicitly stated in a rigorous way even it's brought somewhere else.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors addressed them.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents a faster algorithm for iterative machine teaching, which repeatedly traverses the training set to find samples for the learner. The improvement is obtained by replacing linear scan over the data set with a sampling approach based on locality-sensitive hashing. Empirical evaluation shows substantial speedups, up to 2-3 orders of magnitude, and similar energy savings.
Decision: Accept (Poster)