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

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 languageEnglish
Title of host publicationConformal and Probabilistic Prediction and Applications 2021
EditorsLars Carlsson, Zhiyuan Luo, Giovanni Cherubin, Khuong An Nguyen
PublisherProceedings of Machine Learning Research
Pages39-51
Number of pages13
Volume152
Publication statusPublished - Sep 2021
Event10th Symposium on Conformal and Probabilistic Prediction with Applications, COPA 2021 - Online
Duration: 8 Sep 202110 Sep 2021
Conference number: 10th

Conference

Conference10th Symposium on Conformal and Probabilistic Prediction with Applications, COPA 2021
Abbreviated titleCOPA 2021
Period8/09/2110/09/21
This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 42986097