Parameter-Free Online Linear Optimization with Side Information via Universal Coin Betting

Jongha J. Ryu, Alankrita Bhatt, Young-Han Kim
Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, PMLR 151:6022-6044, 2022.

Abstract

A class of parameter-free online linear optimization algorithms is proposed that harnesses the structure of an adversarial sequence by adapting to some side information. These algorithms combine the reduction technique of Orabona and Pal (2016) for adapting coin betting algorithms for online linear optimization with universal compression techniques in information theory for incorporating sequential side information to coin betting. Concrete examples are studied in which the side information has a tree structure and consists of quantized values of the previous symbols of the adversarial sequence, including fixed-order and variable-order Markov cases. By modifying the context-tree weighting technique of Willems, Shtarkov, and Tjalkens (1995), the proposed algorithm is further refined to achieve the best performance over all adaptive algorithms with tree-structured side information of a given maximum order in a computationally efficient manner.

Cite this Paper

BibTeX
@InProceedings{pmlr-v151-ryu22a, title = { Parameter-Free Online Linear Optimization with Side Information via Universal Coin Betting }, author = {Ryu, Jongha J. and Bhatt, Alankrita and Kim, Young-Han}, booktitle = {Proceedings of The 25th International Conference on Artificial Intelligence and Statistics}, pages = {6022--6044}, year = {2022}, editor = {Camps-Valls, Gustau and Ruiz, Francisco J. R. and Valera, Isabel}, volume = {151}, series = {Proceedings of Machine Learning Research}, month = {28--30 Mar}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v151/ryu22a/ryu22a.pdf}, url = {https://proceedings.mlr.press/v151/ryu22a.html}, abstract = { A class of parameter-free online linear optimization algorithms is proposed that harnesses the structure of an adversarial sequence by adapting to some side information. These algorithms combine the reduction technique of Orabona and Pal (2016) for adapting coin betting algorithms for online linear optimization with universal compression techniques in information theory for incorporating sequential side information to coin betting. Concrete examples are studied in which the side information has a tree structure and consists of quantized values of the previous symbols of the adversarial sequence, including fixed-order and variable-order Markov cases. By modifying the context-tree weighting technique of Willems, Shtarkov, and Tjalkens (1995), the proposed algorithm is further refined to achieve the best performance over all adaptive algorithms with tree-structured side information of a given maximum order in a computationally efficient manner. } }
Endnote
%0 Conference Paper %T Parameter-Free Online Linear Optimization with Side Information via Universal Coin Betting %A Jongha J. Ryu %A Alankrita Bhatt %A Young-Han Kim %B Proceedings of The 25th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2022 %E Gustau Camps-Valls %E Francisco J. R. Ruiz %E Isabel Valera %F pmlr-v151-ryu22a %I PMLR %P 6022--6044 %U https://proceedings.mlr.press/v151/ryu22a.html %V 151 %X A class of parameter-free online linear optimization algorithms is proposed that harnesses the structure of an adversarial sequence by adapting to some side information. These algorithms combine the reduction technique of Orabona and Pal (2016) for adapting coin betting algorithms for online linear optimization with universal compression techniques in information theory for incorporating sequential side information to coin betting. Concrete examples are studied in which the side information has a tree structure and consists of quantized values of the previous symbols of the adversarial sequence, including fixed-order and variable-order Markov cases. By modifying the context-tree weighting technique of Willems, Shtarkov, and Tjalkens (1995), the proposed algorithm is further refined to achieve the best performance over all adaptive algorithms with tree-structured side information of a given maximum order in a computationally efficient manner.
APA
Ryu, J.J., Bhatt, A. & Kim, Y.. (2022). Parameter-Free Online Linear Optimization with Side Information via Universal Coin Betting . Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 151:6022-6044 Available from https://proceedings.mlr.press/v151/ryu22a.html.

Related Material