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

Raisa Dzhamtyrova; Yuri Kalnishkan

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

Raisa Dzhamtyrova
, Yuri Kalnishkan

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

4 Downloads (Pure)

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.

Original language	English
Title of host publication	Conformal and Probabilistic Prediction and Applications 2021
Editors	Lars Carlsson, Zhiyuan Luo, Giovanni Cherubin, Khuong An Nguyen
Publisher	Proceedings of Machine Learning Research
Pages	39-51
Number of pages	13
Volume	152
Publication status	Published - Sept 2021
Event	10th Symposium on Conformal and Probabilistic Prediction with Applications, COPA 2021 - Online Duration: 8 Sept 2021 → 10 Sept 2021 Conference number: 10th

Conference

Conference	10th Symposium on Conformal and Probabilistic Prediction with Applications, COPA 2021
Abbreviated title	COPA 2021
Period	8/09/21 → 10/09/21

Keywords

online learning
competitive prediction
loss bounds

Access to Document

https://proceedings.mlr.press/v152/dzhamtyrova21a.html

Cite this

@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.\textasciitilde{}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",

}

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>

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 proceeding › Conference contribution

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 -