New Potential-Based Bounds for the Geometric-Stopping Version of Prediction with Expert Advice

Vladimir A. Kobzar, Robert V. Kohn, Zhilei Wang
Proceedings of The First Mathematical and Scientific Machine Learning Conference, PMLR 107:537-554, 2020.

Abstract

This work addresses the classic machine learning problem of online prediction with expert advice. A new potential-based framework for the fixed horizon version of this problem has been recently developed using verification arguments from optimal control theory. This paper extends this framework to the random (geometric) stopping version. To obtain explicit bounds, we construct potentials for the geometric version from potentials used for the fixed horizon version of the problem. This construction leads to new explicit lower and upper bounds associated with specific adversary and player strategies. While there are several known lower bounds in the fixed horizon setting, our lower bounds appear to be the first such results in the geometric stopping setting with an arbitrary number of experts. Our framework also leads in some cases to improved upper bounds. For two and three experts, our bounds are optimal to leading order.

Cite this Paper

BibTeX
@InProceedings{pmlr-v107-kobzar20a, title = {New Potential-Based Bounds for the Geometric-Stopping Version of Prediction with Expert Advice}, author = {Kobzar, Vladimir A. and Kohn, Robert V. and Wang, Zhilei}, booktitle = {Proceedings of The First Mathematical and Scientific Machine Learning Conference}, pages = {537--554}, year = {2020}, editor = {Lu, Jianfeng and Ward, Rachel}, volume = {107}, series = {Proceedings of Machine Learning Research}, month = {20--24 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v107/kobzar20a/kobzar20a.pdf}, url = {https://proceedings.mlr.press/v107/kobzar20a.html}, abstract = {This work addresses the classic machine learning problem of online prediction with expert advice. A new potential-based framework for the fixed horizon version of this problem has been recently developed using verification arguments from optimal control theory. This paper extends this framework to the random (geometric) stopping version. To obtain explicit bounds, we construct potentials for the geometric version from potentials used for the fixed horizon version of the problem. This construction leads to new explicit lower and upper bounds associated with specific adversary and player strategies. While there are several known lower bounds in the fixed horizon setting, our lower bounds appear to be the first such results in the geometric stopping setting with an arbitrary number of experts. Our framework also leads in some cases to improved upper bounds. For two and three experts, our bounds are optimal to leading order. } }
Endnote
%0 Conference Paper %T New Potential-Based Bounds for the Geometric-Stopping Version of Prediction with Expert Advice %A Vladimir A. Kobzar %A Robert V. Kohn %A Zhilei Wang %B Proceedings of The First Mathematical and Scientific Machine Learning Conference %C Proceedings of Machine Learning Research %D 2020 %E Jianfeng Lu %E Rachel Ward %F pmlr-v107-kobzar20a %I PMLR %P 537--554 %U https://proceedings.mlr.press/v107/kobzar20a.html %V 107 %X This work addresses the classic machine learning problem of online prediction with expert advice. A new potential-based framework for the fixed horizon version of this problem has been recently developed using verification arguments from optimal control theory. This paper extends this framework to the random (geometric) stopping version. To obtain explicit bounds, we construct potentials for the geometric version from potentials used for the fixed horizon version of the problem. This construction leads to new explicit lower and upper bounds associated with specific adversary and player strategies. While there are several known lower bounds in the fixed horizon setting, our lower bounds appear to be the first such results in the geometric stopping setting with an arbitrary number of experts. Our framework also leads in some cases to improved upper bounds. For two and three experts, our bounds are optimal to leading order.
APA
Kobzar, V.A., Kohn, R.V. & Wang, Z.. (2020). New Potential-Based Bounds for the Geometric-Stopping Version of Prediction with Expert Advice. Proceedings of The First Mathematical and Scientific Machine Learning Conference, in Proceedings of Machine Learning Research 107:537-554 Available from https://proceedings.mlr.press/v107/kobzar20a.html.

Related Material