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

Conformal and Probabilistic Prediction and Applications 2021. ed. / Lars Carlsson; Zhiyuan Luo; Giovanni Cherubin; Khuong An Nguyen. Vol. 152 Proceedings of Machine Learning Research, 2021. p. 39-51.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Published

Standard

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

Conformal and Probabilistic Prediction and Applications 2021. ed. / Lars Carlsson; Zhiyuan Luo; Giovanni Cherubin; Khuong An Nguyen. Vol. 152 Proceedings of Machine Learning Research, 2021. p. 39-51.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Harvard

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>

APA

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

Vancouver

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

Author

Dzhamtyrova, Raisa ; Kalnishkan, Yuri. / A Lower Bound for a Prediction Algorithm under the Kullback-Leibler Game. Conformal and Probabilistic Prediction and Applications 2021. editor / Lars Carlsson ; Zhiyuan Luo ; Giovanni Cherubin ; Khuong An Nguyen. Vol. 152 Proceedings of Machine Learning Research, 2021. pp. 39-51

BibTeX

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

}

RIS

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 -