**A Lower Bound for a Prediction Algorithm under the Kullback-Leibler Game.** / Dzhamtyrova, Raisa; Kalnishkan, Yuri.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Published

**A Lower Bound for a Prediction Algorithm under the Kullback-Leibler Game.** / Dzhamtyrova, Raisa; Kalnishkan, Yuri.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Dzhamtyrova, R & Kalnishkan, Y 2021, A Lower Bound for a Prediction Algorithm under the Kullback-Leibler Game. in L Carlsson, Z Luo, G Cherubin & K An Nguyen (eds), *Conformal and Probabilistic Prediction and Applications 2021.* vol. 152, Proceedings of Machine Learning Research, pp. 39-51, 10th Symposium on Conformal and Probabilistic Prediction with Applications, COPA 2021, 8/09/21. <https://proceedings.mlr.press/v152/dzhamtyrova21a.html>

Dzhamtyrova, R., & Kalnishkan, Y. (2021). A Lower Bound for a Prediction Algorithm under the Kullback-Leibler Game. In L. Carlsson, Z. Luo, G. Cherubin, & K. An Nguyen (Eds.), *Conformal and Probabilistic Prediction and Applications 2021 *(Vol. 152, pp. 39-51). Proceedings of Machine Learning Research. https://proceedings.mlr.press/v152/dzhamtyrova21a.html

Dzhamtyrova R, Kalnishkan Y. A Lower Bound for a Prediction Algorithm under the Kullback-Leibler Game. In Carlsson L, Luo Z, Cherubin G, An Nguyen K, editors, Conformal and Probabilistic Prediction and Applications 2021. Vol. 152. Proceedings of Machine Learning Research. 2021. p. 39-51

@inproceedings{e28f861c72d54f2fa1ce3ffaa1f45b2f,

title = "A Lower Bound for a Prediction Algorithm under the Kullback-Leibler Game",

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.",

keywords = "online learning, competitive prediction, loss bounds",

author = "Raisa Dzhamtyrova and Yuri Kalnishkan",

year = "2021",

month = sep,

language = "English",

volume = "152",

pages = "39--51",

editor = "Lars Carlsson and Zhiyuan Luo and Giovanni Cherubin and {An Nguyen}, Khuong",

booktitle = "Conformal and Probabilistic Prediction and Applications 2021",

publisher = "Proceedings of Machine Learning Research",

note = "10th Symposium on Conformal and Probabilistic Prediction with Applications, COPA 2021, COPA 2021 ; Conference date: 08-09-2021 Through 10-09-2021",

}

TY - GEN

T1 - A Lower Bound for a Prediction Algorithm under the Kullback-Leibler Game

AU - Dzhamtyrova, Raisa

AU - Kalnishkan, Yuri

N1 - Conference code: 10th

PY - 2021/9

Y1 - 2021/9

N2 - 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.

AB - 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.

KW - online learning

KW - competitive prediction

KW - loss bounds

M3 - Conference contribution

VL - 152

SP - 39

EP - 51

BT - Conformal and Probabilistic Prediction and Applications 2021

A2 - Carlsson, Lars

A2 - Luo, Zhiyuan

A2 - Cherubin, Giovanni

A2 - An Nguyen, Khuong

PB - Proceedings of Machine Learning Research

T2 - 10th Symposium on Conformal and Probabilistic Prediction with Applications, COPA 2021

Y2 - 8 September 2021 through 10 September 2021

ER -