Sequential prediction under log-loss with side information

Alankrita Bhatt, Young-Han Kim
Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:340-344, 2021.

Abstract

The problem of online prediction with sequential side information under logarithmic loss is studied, and general upper and lower bounds on the minimax regret incurred by the predictor is established. The upper bounds on the minimax regret are obtained by constructing and analyzing a probability assignment based on mixture probability assignments in universal compression, and the lower bounds are obtained by way of a redundancy–capacity theorem. A tight characterization of the regret is provided in some special settings.

Cite this Paper

BibTeX
@InProceedings{pmlr-v132-bhatt21a, title = {Sequential prediction under log-loss with side information}, author = {Bhatt, Alankrita and Kim, Young-Han}, booktitle = {Proceedings of the 32nd International Conference on Algorithmic Learning Theory}, pages = {340--344}, year = {2021}, editor = {Feldman, Vitaly and Ligett, Katrina and Sabato, Sivan}, volume = {132}, series = {Proceedings of Machine Learning Research}, month = {16--19 Mar}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v132/bhatt21a/bhatt21a.pdf}, url = {https://proceedings.mlr.press/v132/bhatt21a.html}, abstract = {The problem of online prediction with sequential side information under logarithmic loss is studied, and general upper and lower bounds on the minimax regret incurred by the predictor is established. The upper bounds on the minimax regret are obtained by constructing and analyzing a probability assignment based on mixture probability assignments in universal compression, and the lower bounds are obtained by way of a redundancy–capacity theorem. A tight characterization of the regret is provided in some special settings.} }
Endnote
%0 Conference Paper %T Sequential prediction under log-loss with side information %A Alankrita Bhatt %A Young-Han Kim %B Proceedings of the 32nd International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2021 %E Vitaly Feldman %E Katrina Ligett %E Sivan Sabato %F pmlr-v132-bhatt21a %I PMLR %P 340--344 %U https://proceedings.mlr.press/v132/bhatt21a.html %V 132 %X The problem of online prediction with sequential side information under logarithmic loss is studied, and general upper and lower bounds on the minimax regret incurred by the predictor is established. The upper bounds on the minimax regret are obtained by constructing and analyzing a probability assignment based on mixture probability assignments in universal compression, and the lower bounds are obtained by way of a redundancy–capacity theorem. A tight characterization of the regret is provided in some special settings.
APA
Bhatt, A. & Kim, Y.. (2021). Sequential prediction under log-loss with side information. Proceedings of the 32nd International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 132:340-344 Available from https://proceedings.mlr.press/v132/bhatt21a.html.

Related Material