Efficient and Optimal Fixed-Time Regret with Two Experts

Laura Greenstreet, Nicholas J. A. Harvey, Victor Sanches Portella
Proceedings of The 33rd International Conference on Algorithmic Learning Theory, PMLR 167:436-464, 2022.

Abstract

Prediction with expert advice is a foundational problem in online learning. In instances with \(T\) rounds and \(n\) experts, the classical Multiplicative Weights Update method suffers at most \(\sqrt{(T/2)\ln n}\) regret when \(T\) is known beforehand. Moreover, this is asymptotically optimal when both \(T\) and \(n\) grow to infinity. However, when the number of experts \(n\) is small/fixed, algorithms with better regret guarantees exist. Cover showed in 1967 a dynamic programming algorithm for the two-experts problem restricted to \(\{0,1\}\) costs that suffers at most \(\sqrt{T/2\pi} + O(1)\) regret with \(O(T^2)\) pre-processing time. In this work, we propose an optimal algorithm for prediction with two experts’ advice that works even for costs in \([0,1]\) and with \(O(1)\) processing time per turn. Our algorithm builds up on recent work on the experts problem based on techniques and tools from stochastic calculus.

Cite this Paper

BibTeX
@InProceedings{pmlr-v167-greenstreet22a, title = {Efficient and Optimal Fixed-Time Regret with Two Experts}, author = {Greenstreet, Laura and Harvey, Nicholas J. A. and Sanches Portella, Victor}, booktitle = {Proceedings of The 33rd International Conference on Algorithmic Learning Theory}, pages = {436--464}, year = {2022}, editor = {Dasgupta, Sanjoy and Haghtalab, Nika}, volume = {167}, series = {Proceedings of Machine Learning Research}, month = {29 Mar--01 Apr}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v167/greenstreet22a/greenstreet22a.pdf}, url = {https://proceedings.mlr.press/v167/greenstreet22a.html}, abstract = {Prediction with expert advice is a foundational problem in online learning. In instances with \(T\) rounds and \(n\) experts, the classical Multiplicative Weights Update method suffers at most \(\sqrt{(T/2)\ln n}\) regret when \(T\) is known beforehand. Moreover, this is asymptotically optimal when both \(T\) and \(n\) grow to infinity. However, when the number of experts \(n\) is small/fixed, algorithms with better regret guarantees exist. Cover showed in 1967 a dynamic programming algorithm for the two-experts problem restricted to \(\{0,1\}\) costs that suffers at most \(\sqrt{T/2\pi} + O(1)\) regret with \(O(T^2)\) pre-processing time. In this work, we propose an optimal algorithm for prediction with two experts’ advice that works even for costs in \([0,1]\) and with \(O(1)\) processing time per turn. Our algorithm builds up on recent work on the experts problem based on techniques and tools from stochastic calculus.} }
Endnote
%0 Conference Paper %T Efficient and Optimal Fixed-Time Regret with Two Experts %A Laura Greenstreet %A Nicholas J. A. Harvey %A Victor Sanches Portella %B Proceedings of The 33rd International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2022 %E Sanjoy Dasgupta %E Nika Haghtalab %F pmlr-v167-greenstreet22a %I PMLR %P 436--464 %U https://proceedings.mlr.press/v167/greenstreet22a.html %V 167 %X Prediction with expert advice is a foundational problem in online learning. In instances with \(T\) rounds and \(n\) experts, the classical Multiplicative Weights Update method suffers at most \(\sqrt{(T/2)\ln n}\) regret when \(T\) is known beforehand. Moreover, this is asymptotically optimal when both \(T\) and \(n\) grow to infinity. However, when the number of experts \(n\) is small/fixed, algorithms with better regret guarantees exist. Cover showed in 1967 a dynamic programming algorithm for the two-experts problem restricted to \(\{0,1\}\) costs that suffers at most \(\sqrt{T/2\pi} + O(1)\) regret with \(O(T^2)\) pre-processing time. In this work, we propose an optimal algorithm for prediction with two experts’ advice that works even for costs in \([0,1]\) and with \(O(1)\) processing time per turn. Our algorithm builds up on recent work on the experts problem based on techniques and tools from stochastic calculus.
APA
Greenstreet, L., Harvey, N.J.A. & Sanches Portella, V.. (2022). Efficient and Optimal Fixed-Time Regret with Two Experts. Proceedings of The 33rd International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 167:436-464 Available from https://proceedings.mlr.press/v167/greenstreet22a.html.

Related Material