Abstract: Given a sequential learning algorithm and a target model, sequential machine teaching aims to find the shortest training sequence to drive the learning algorithm to the target model. We present the first optimal control formulation of sequential machine teaching, applying the Pontryagin Maximum Principle to characterize the structure of optimal teaching sequences. Our analysis reveals that for least-squares learners, optimal trajectories are intrinsically low-dimensional, leading to significant efficiency gains over standard greedy heuristics.
Introduction
Machine teaching is the "inverse" of machine learning: given a target model, what is the minimum amount of data needed to make a learner arrive at that model? While "batch" teaching—providing all data at once—is well-studied, sequential teaching is significantly more complex. In this setting, a learner updates its state step-by-step, mirroring real-world scenarios like a student in a classroom or a model trained via Stochastic Gradient Descent (SGD).
Historically, sequential teaching has relied on "greedy" heuristics—selecting the single best data point to move the learner as close as possible to the target in the immediate next step. However, this short-sightedness often leads to a "greedy trap." Much like a hiker getting stuck in a thicket because they took the steepest path immediately available, greedy learners can be driven into "compressed directions" where gradients vanish and progress stalls.
Framing Teaching as Control
This research bridges the gap between machine learning and classical control theory by treating the machine learner as a "plant" (a dynamical system). In this framework, the model weights represent the "state," and the training data points serve as the "control inputs." To solve for the shortest training sequence, the authors employ several key methodologies:
- Pontryagin Maximum Principle (PMP): A cornerstone of control theory used to derive necessary conditions for an optimal training sequence, allowing for a deep analysis of the "geometry" of teaching.
- Nonlinear Programming (NLP): For discrete-time learners, the teaching task is formulated as a constrained optimization problem to find the exact shortest sequence.
- Continuous Nonlinear Programming (CNLP): By analyzing the "continuous limit" (where the learning rate $\eta$ is infinitesimal), the authors provide a smooth "ideal" trajectory. This version is computationally efficient and serves as a blueprint for discrete learners.
Key Insights: The Geometry of Teaching
A primary contribution of this work is the discovery of the 2D Subspace Miracle. For least-squares learners, the optimal teaching trajectory always lies within a 2D plane, regardless of the dimensionality of the model space. This implies that an optimal teacher only needs to maneuver the model within a specific slice of the high-dimensional space to reach the target most efficiently.
Furthermore, the authors identify five distinct "regimes" of motion (e.g., positive alignment, negative alignment, general positions). An optimal teacher strategically switches between these regimes based on the model's current state relative to the target, avoiding the pitfalls that plague greedy strategies.
Experimental Results
The authors evaluated their approach using synthetic experimental setups, allowing for precise control over dimensionality and data constraints. The results demonstrate that the NLP and CNLP approaches consistently find shorter sequences than greedy methods.
As shown in Figure 1, the NLP approach reached the target in 151 steps, while the GREEDY heuristic required 219 steps. This efficiency gap widens dramatically as the distance to the target increases; in some case studies, the GREEDY approach required over 10,000 steps to reach a target that the NLP method achieved in fewer than 350. While NLP can be computationally intensive for long sequences, the CNLP runtime remains independent of sequence length, offering a scalable solution for large-scale teaching problems.
Limitations and Future Directions
While this work provides a rigorous foundation for optimal teaching, several challenges remain:
- Robustness: The current methods produce "open-loop" sequences. In practice, numerical errors or learner variations could cause drift. Future work may utilize Model Predictive Control (MPC) to create a "closed-loop" system that re-calculates the path at every step.
- Complexity: The 2D subspace proof is currently specific to least-squares learners. Extending these structural insights to complex architectures like deep neural networks is a vital next step.
- Feedback Policies: Solving the Hamilton-Jacobi-Bellman (HJB) equation would provide a universal teaching policy, though this remains computationally daunting for high-dimensional models.
Summary updated