Locality Sensitive Teaching

Zhaozhuo Xu, Beidi Chen, Chaojian Li, Weiyang Liu, Le Song, Yingyan Lin, Anshumali ShrivastavaNeurIPS 2021 · OpenReview

Machine Teaching (MT) flips the traditional machine learning paradigm on its head: instead of a model passively learning from a massive dataset, a "teacher" actively selects the smallest, most effective set of examples to help a "student" (which could be a machine learning model or a human) grasp a specific concept.

The most effective version of this is Iterative Machine Teaching (IMT), where the teacher interacts with the student step-by-step, picking the next best example based on the student's current progress. However, there is a major bottleneck: current IMT algorithms are inherently "greedy." In every single iteration, the teacher must scan the entire dataset to find the optimal next example. This $O(N)$ computational complexity makes IMT virtually impossible to run on edge devices like tablets, phones, or IoT sensors, which are constrained by limited processing power and battery life.

To bridge the gap between high-quality personalized education and the resource-constrained reality of IoT hardware, researchers have introduced Locality Sensitive Teaching (LST). By replacing the computationally expensive greedy scan with a fast, hash-based sampling method, LST achieves up to 425x speedups and 99.76% energy savings on edge devices.

The Locality Sensitive Teaching Framework

LST fundamentally changes how teaching examples are selected by shifting from an exhaustive search to an efficient sampling strategy.

  1. Reformulation as Sampling: The researchers reformulate the optimization problem of finding the absolute "best" example into an Adaptive Inner Product Sampling (AIPS) problem. Essentially, they turn the task of "finding the best" into "sampling a very good one."
  2. Locality Sensitive Hashing (LSH): To solve the AIPS problem efficiently, LST leverages Locality Sensitive Hashing. During a one-time preprocessing step, the entire dataset is indexed into hash tables. Instead of scanning everything during the teaching phase, the teacher uses the student's current state as a "query" to quickly retrieve high-quality examples from specific hash buckets.
  3. Asymmetric Transformation: Because the teaching objective involves complex quadratic terms, the authors apply an asymmetric transformation to project data and queries into a space where simple inner products can be used for hashing.
The Locality Sensitive Teaching (LST) framework, illustrating how datasets are pre-hashed into buckets for rapid, near-constant time sample selection during the teacher-student interaction loop.

To ensure the algorithm is practically deployable, the researchers also designed a hardware-optimized hybrid system for integrated CPU-GPU chips (SoCs). The GPU handles the heavy lifting of random projections (matrix multiplication), while the CPU manages the memory-intensive hash table lookups.

Key Insights and Performance

By using hashing, the search time for an example drops from being dependent on the dataset size ($O(N)$) to being nearly independent of it ($O(1)$ in practice). This is the key to LST's massive scalability.

  • Massive Speedups: On a standard server, LST is over 2,000x faster than traditional IMT. When deployed on an NVIDIA Jetson TX2 (an IoT-class device), it achieved up to a 425.12x speedup.
  • Extreme Energy Efficiency: LST reduced energy consumption by up to 99.76% compared to IMT. This makes "always-on" personalized teaching a reality for battery-powered devices.

Surprisingly, LST often performs better than the standard greedy algorithm in terms of teaching quality. While the greedy approach can get stuck in "local optima" or repeatedly show the student the same two "best" examples, LST’s stochastic nature introduces diversity. This gives the student a broader, more plausible view of the concept.

Training loss versus iteration comparing the proposed AIPS method against the Greedy Teaching Algorithm (GTA) and the optimal baseline, demonstrating that LST maintains teaching effectiveness while drastically reducing computation.

Despite the massive reduction in computation, LST matched or exceeded the teaching performance (convergence rate) of the exhaustive greedy baseline across all tested datasets.

Datasets and Evaluation

The authors evaluated LST on several regression and classification benchmarks, including Abalone, Space_ga, MG, and Slice (a larger dataset with 53,500 training samples used to test scalability). They also utilized a COVID-19 CT Image dataset as a motivating example to demonstrate how LST could help a student distinguish between normal and COVID-infected lung scans.

Limitations and Future Work

While LST represents a massive leap forward for edge-based machine teaching, it does have limitations:

  • Omniscient Teacher Assumption: The current model assumes the teacher knows exactly what the student knows. In many real-world scenarios, the student is a "black box," and the teacher must estimate the student's state.
  • Model Complexity: The paper proves the concept for linear and logistic regression. Extending this to deep neural network "students" would require more complex transformations to maintain the efficiency of the LSH lookups.
  • Human-in-the-Loop: The authors suggest that the diversity provided by LST is better for human learners, but large-scale user studies with actual human students are needed to confirm this psychological benefit.

Summary updated

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.
BibTeX
@inproceedings{xu2021locality,
  author = {Zhaozhuo Xu and Beidi Chen and Chaojian Li and Weiyang Liu and Le Song and Yingyan Lin and Anshumali Shrivastava},
  title = {{Locality Sensitive Teaching}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=6o7PBF7ZPOn},
}
Figure