An Optimal Control Approach to Sequential Machine Teaching

Laurent Lessard, Xuezhou Zhang, Xiaojin Zhu
Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, PMLR 89:2495-2503, 2019.

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 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 opti- mality of a training sequence. We present analytic, structural, and numerical implica- tions of this approach on a case study with a least-squares loss function and gradient de- scent learner. We compute optimal train- ing 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v89-lessard19a, title = {An Optimal Control Approach to Sequential Machine Teaching}, author = {Lessard, Laurent and Zhang, Xuezhou and Zhu, Xiaojin}, booktitle = {Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics}, pages = {2495--2503}, year = {2019}, editor = {Chaudhuri, Kamalika and Sugiyama, Masashi}, volume = {89}, series = {Proceedings of Machine Learning Research}, month = {16--18 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v89/lessard19a/lessard19a.pdf}, url = {https://proceedings.mlr.press/v89/lessard19a.html}, 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 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 opti- mality of a training sequence. We present analytic, structural, and numerical implica- tions of this approach on a case study with a least-squares loss function and gradient de- scent learner. We compute optimal train- ing 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.} }
Endnote
%0 Conference Paper %T An Optimal Control Approach to Sequential Machine Teaching %A Laurent Lessard %A Xuezhou Zhang %A Xiaojin Zhu %B Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Masashi Sugiyama %F pmlr-v89-lessard19a %I PMLR %P 2495--2503 %U https://proceedings.mlr.press/v89/lessard19a.html %V 89 %X 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 opti- mality of a training sequence. We present analytic, structural, and numerical implica- tions of this approach on a case study with a least-squares loss function and gradient de- scent learner. We compute optimal train- ing 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.
APA
Lessard, L., Zhang, X. & Zhu, X.. (2019). An Optimal Control Approach to Sequential Machine Teaching. Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 89:2495-2503 Available from https://proceedings.mlr.press/v89/lessard19a.html.

Related Material