A lower bound for a prediction algorithm under the Kullback-Leibler game

Raisa Dzhamtyrova, Yuri Kalnishkan
Proceedings of the Tenth Symposium on Conformal and Probabilistic Prediction and Applications, PMLR 152:39-51, 2021.

Abstract

We obtain a lower bound for an algorithm predicting finite-dimensional distributions (i.e., points from a simplex) under Kullback-Leibler loss. The bound holds w.r.t. the class of softmax linear predictors. We then show that the bound is asymptotically matched by the Bayesian universal algorithm.

Cite this Paper

BibTeX
@InProceedings{pmlr-v152-dzhamtyrova21a, title = {A lower bound for a prediction algorithm under the Kullback-Leibler game}, author = {Dzhamtyrova, Raisa and Kalnishkan, Yuri}, booktitle = {Proceedings of the Tenth Symposium on Conformal and Probabilistic Prediction and Applications}, pages = {39--51}, year = {2021}, editor = {Carlsson, Lars and Luo, Zhiyuan and Cherubin, Giovanni and An Nguyen, Khuong}, volume = {152}, series = {Proceedings of Machine Learning Research}, month = {08--10 Sep}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v152/dzhamtyrova21a/dzhamtyrova21a.pdf}, url = {https://proceedings.mlr.press/v152/dzhamtyrova21a.html}, abstract = {We obtain a lower bound for an algorithm predicting finite-dimensional distributions (i.e., points from a simplex) under Kullback-Leibler loss. The bound holds w.r.t. the class of softmax linear predictors. We then show that the bound is asymptotically matched by the Bayesian universal algorithm.} }
Endnote
%0 Conference Paper %T A lower bound for a prediction algorithm under the Kullback-Leibler game %A Raisa Dzhamtyrova %A Yuri Kalnishkan %B Proceedings of the Tenth Symposium on Conformal and Probabilistic Prediction and Applications %C Proceedings of Machine Learning Research %D 2021 %E Lars Carlsson %E Zhiyuan Luo %E Giovanni Cherubin %E Khuong An Nguyen %F pmlr-v152-dzhamtyrova21a %I PMLR %P 39--51 %U https://proceedings.mlr.press/v152/dzhamtyrova21a.html %V 152 %X We obtain a lower bound for an algorithm predicting finite-dimensional distributions (i.e., points from a simplex) under Kullback-Leibler loss. The bound holds w.r.t. the class of softmax linear predictors. We then show that the bound is asymptotically matched by the Bayesian universal algorithm.
APA
Dzhamtyrova, R. & Kalnishkan, Y.. (2021). A lower bound for a prediction algorithm under the Kullback-Leibler game. Proceedings of the Tenth Symposium on Conformal and Probabilistic Prediction and Applications, in Proceedings of Machine Learning Research 152:39-51 Available from https://proceedings.mlr.press/v152/dzhamtyrova21a.html.

Related Material