Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
main_review: Novelty:
The paper claims LST as the first algorithm that enables energy and time efficient machine teaching on IoT devices.

Strengths:
1. The paper focuses on 2 aspects - improving running metrics like speed, energy. And, overcoming greedy search of usual IMT systems.
2. The paper uses both theoretical and empirical approach as defense of the work. This seems to be concrete.
3. The paper's handling of concepts at mathematical rigor (backed by supplementary) is commendable.
4. Paper is well written.

Weakness:
1. Code is not available to check due to some permission issue.
2. 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.
3. The scalability section needs some validation - is this the correct approach to validate?
4. Adherence to practical usage (apart from Covid theme) should have increased the paper's value.
5. Mixing of IoT with the approach needs some more gelling from reader's continuity of flow perspective.

Relevance to NeurIPS:
More 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.

Effort: Significant effort has been done in thought process, however implementation wise would have like more rigor.

Suggestions:
1. Does the toy example in Fig.3 substantiate the approach's efficacy in terms of generalization? 
2. Some discussion on bias / priors will help clarify the learning part.
3. How collision in the hash table can downgrade performance? Any heuristics to support?
4. Can adversarial examples affect the algorithm?
5. "D Motivating Example Settings" - this could have been expanded more to get an insight in the practical application.
limitations_and_societal_impact: Not applicable, Skip.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: 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.
main_review: The paper is well organized and the writing is clear. The idea and derivation in each step is easy to follow.

Online 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.

I 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.

Detailed comments and questions:

1) Typos on line 115 and 195.

2) In Algorithm 1, $\pi$ is not defined in the first loop; In Alg 2, $|B|$ is not used.

3) Is (2) and Theorem 2 strict for both regression and classification? Is it possible to extend Theorem 2 to more models?
limitations_and_societal_impact: NA
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.  
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. 

Despite the above merits, the paper needs further improvements in the techniques and experiments to justify the claimed contributions. 

1.	The 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. 

2.	The 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. 

3.	The 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. 

[Comments regarding author response]
Thank 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. 
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_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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. 

Major question/concern:  
1.  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?
2.  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. 
3.  The test error for slice test in the plot (h) of figure 4 is way higher than the training error, why?

Minor comments:  
1.  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.
2.  You should link the reference by using cite, and ref the equations using eqref, e.g. in line 205.
3.  The order of figures 1,2,3 is inappropriate, as you mention figure 2,3 before figure 1.
4. 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.
limitations_and_societal_impact: The authors addressed them.
review_title: null

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)