An Optimal Control Approach to Sequential Machine Teaching

By Laurent Lessard, Xuezhou Zhang, Xiaojin Zhu. 2018

37 citations recorded by the source corpus.

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 principled way to find such shortest training sequences. Our key insight is to formulate sequential machine teaching as a time-optimal control problem. This allows us to solve sequential teaching by leveraging key theoretical and computational tools developed over the past 60 years in the optimal control community. Specifically, we study the Pontryagin Maximum Principle, which yields a necessary condition for optimality of a training sequence. We present analytic, structural, and numerical implications of this approach on a case study with a least-squares loss function and gradient descent learner. We compute optimal training sequences for this problem, and although the sequences seem circuitous, we find that they can vastly outperform the best available heuristics for generating training sequences.

Subfields: Artificial Intelligence, Computer Networks and Communications

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Tao Qin
2. Yingce Xia
3. Lijun Wu
4. Xuezhou Zhang
5. Jy-yong Sohn
6. Dimitris Papailiopoulos
7. Hongyi Wang
8. Yang Fan

In Computer Networks and Communications

1. Dimitris Papailiopoulos
2. Xiaojin Zhu
3. Xuezhou Zhang
4. Hongyi Wang
5. Shashank Rajput
6. Jiang Bian
7. Kangwook Lee
8. Suhas N. Diggavi

Citations in the corpus

• Attack of the Tails: Yes, You Really Can Backdoor Federated Learning (2020, methodology): “It is typically used to speed up training [59, 60, 61] by choosing the optimal training sequence.”
• Online Data Poisoning Attack (2019, methodology): “Greedy Attack: The greedy strategy is applied widely as a practical heuristic in solving sequential decision problems ([16, 13]).”
• Learning to Reweight with Deep Interactions (2021, background): “(Lessard, Zhang, and Zhu 2019) tackles a similar problem, which is about to find the shortest training sequence to drive the student model to the target one.”