New Potential-Based Bounds for Prediction with Expert Advice

Vladimir A. Kobzar, Robert V. Kohn, Zhilei Wang
Proceedings of Thirty Third Conference on Learning Theory, PMLR 125:2370-2405, 2020.

Abstract

This work addresses the classic machine learning problem of online prediction with expert advice. We consider the finite-horizon version of this zero-sum, two-person game. Using verification arguments from optimal control theory, we view the task of finding better lower and upper bounds on the value of the game (regret) as the problem of finding better sub- and supersolutions of certain partial differential equations (PDEs). These sub- and supersolutions serve as the potentials for player and adversary strategies, which lead to the corresponding bounds. To get explicit bounds, we use closed-form solutions of specific PDEs. Our bounds hold for any given number of experts and horizon; in certain regimes (which we identify) they improve upon the previous state of the art. For two and three experts, our bounds provide the optimal leading order term.

Cite this Paper

BibTeX
@InProceedings{pmlr-v125-kobzar20a, title = {New Potential-Based Bounds for Prediction with Expert Advice}, author = {Kobzar, Vladimir A. and Kohn, Robert V. and Wang, Zhilei}, booktitle = {Proceedings of Thirty Third Conference on Learning Theory}, pages = {2370--2405}, year = {2020}, editor = {Abernethy, Jacob and Agarwal, Shivani}, volume = {125}, series = {Proceedings of Machine Learning Research}, month = {09--12 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v125/kobzar20a/kobzar20a.pdf}, url = {https://proceedings.mlr.press/v125/kobzar20a.html}, abstract = { This work addresses the classic machine learning problem of online prediction with expert advice. We consider the finite-horizon version of this zero-sum, two-person game. Using verification arguments from optimal control theory, we view the task of finding better lower and upper bounds on the value of the game (regret) as the problem of finding better sub- and supersolutions of certain partial differential equations (PDEs). These sub- and supersolutions serve as the potentials for player and adversary strategies, which lead to the corresponding bounds. To get explicit bounds, we use closed-form solutions of specific PDEs. Our bounds hold for any given number of experts and horizon; in certain regimes (which we identify) they improve upon the previous state of the art. For two and three experts, our bounds provide the optimal leading order term. } }
Endnote
%0 Conference Paper %T New Potential-Based Bounds for Prediction with Expert Advice %A Vladimir A. Kobzar %A Robert V. Kohn %A Zhilei Wang %B Proceedings of Thirty Third Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2020 %E Jacob Abernethy %E Shivani Agarwal %F pmlr-v125-kobzar20a %I PMLR %P 2370--2405 %U https://proceedings.mlr.press/v125/kobzar20a.html %V 125 %X This work addresses the classic machine learning problem of online prediction with expert advice. We consider the finite-horizon version of this zero-sum, two-person game. Using verification arguments from optimal control theory, we view the task of finding better lower and upper bounds on the value of the game (regret) as the problem of finding better sub- and supersolutions of certain partial differential equations (PDEs). These sub- and supersolutions serve as the potentials for player and adversary strategies, which lead to the corresponding bounds. To get explicit bounds, we use closed-form solutions of specific PDEs. Our bounds hold for any given number of experts and horizon; in certain regimes (which we identify) they improve upon the previous state of the art. For two and three experts, our bounds provide the optimal leading order term.
APA
Kobzar, V.A., Kohn, R.V. & Wang, Z.. (2020). New Potential-Based Bounds for Prediction with Expert Advice. Proceedings of Thirty Third Conference on Learning Theory, in Proceedings of Machine Learning Research 125:2370-2405 Available from https://proceedings.mlr.press/v125/kobzar20a.html.

Related Material