Impossible Tuning Made Possible: A New Expert Algorithm and Its Applications

Liyu Chen, Haipeng Luo, Chen-Yu Wei
Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:1216-1259, 2021.

Abstract

We resolve the long-standing "impossible tuning" issue for the classic expert problem and show that, it is in fact possible to achieve regret O(√(lnd)∑tℓ2t,i) simultaneously for all expert i in a T-round d-expert problem where ℓt,i is the loss for expert i in round t. Our algorithm is based on the Mirror Descent framework with a correction term and a weighted entropy regularizer. While natural, the algorithm has not been studied before and requires a careful analysis. We also generalize the bound to O(√(lnd)∑t(ℓt,i−mt,i)2) for any prediction vector mt that the learner receives, and recover or improve many existing results by choosing different mt. Furthermore, we use the same framework to create a master algorithm that combines a set of base algorithms and learns the best one with little overhead. The new guarantee of our master allows us to derive many new results for both the expert problem and more generally Online Linear Optimization.

Cite this Paper

BibTeX
@InProceedings{pmlr-v134-chen21f, title = {Impossible Tuning Made Possible: A New Expert Algorithm and Its Applications}, author = {Chen, Liyu and Luo, Haipeng and Wei, Chen-Yu}, booktitle = {Proceedings of Thirty Fourth Conference on Learning Theory}, pages = {1216--1259}, year = {2021}, editor = {Belkin, Mikhail and Kpotufe, Samory}, volume = {134}, series = {Proceedings of Machine Learning Research}, month = {15--19 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v134/chen21f/chen21f.pdf}, url = {https://proceedings.mlr.press/v134/chen21f.html}, abstract = {We resolve the long-standing "impossible tuning" issue for the classic expert problem and show that, it is in fact possible to achieve regret $O\left(\sqrt{(\ln d)\sum_t \ell_{t,i}^2}\right)$ simultaneously for all expert $i$ in a $T$-round $d$-expert problem where $\ell_{t,i}$ is the loss for expert $i$ in round $t$. Our algorithm is based on the Mirror Descent framework with a correction term and a weighted entropy regularizer. While natural, the algorithm has not been studied before and requires a careful analysis. We also generalize the bound to $O\left(\sqrt{(\ln d)\sum_t (\ell_{t,i}-m_{t,i})^2}\right)$ for any prediction vector $m_t$ that the learner receives, and recover or improve many existing results by choosing different $m_t$. Furthermore, we use the same framework to create a master algorithm that combines a set of base algorithms and learns the best one with little overhead. The new guarantee of our master allows us to derive many new results for both the expert problem and more generally Online Linear Optimization.} }
Endnote
%0 Conference Paper %T Impossible Tuning Made Possible: A New Expert Algorithm and Its Applications %A Liyu Chen %A Haipeng Luo %A Chen-Yu Wei %B Proceedings of Thirty Fourth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2021 %E Mikhail Belkin %E Samory Kpotufe %F pmlr-v134-chen21f %I PMLR %P 1216--1259 %U https://proceedings.mlr.press/v134/chen21f.html %V 134 %X We resolve the long-standing "impossible tuning" issue for the classic expert problem and show that, it is in fact possible to achieve regret $O\left(\sqrt{(\ln d)\sum_t \ell_{t,i}^2}\right)$ simultaneously for all expert $i$ in a $T$-round $d$-expert problem where $\ell_{t,i}$ is the loss for expert $i$ in round $t$. Our algorithm is based on the Mirror Descent framework with a correction term and a weighted entropy regularizer. While natural, the algorithm has not been studied before and requires a careful analysis. We also generalize the bound to $O\left(\sqrt{(\ln d)\sum_t (\ell_{t,i}-m_{t,i})^2}\right)$ for any prediction vector $m_t$ that the learner receives, and recover or improve many existing results by choosing different $m_t$. Furthermore, we use the same framework to create a master algorithm that combines a set of base algorithms and learns the best one with little overhead. The new guarantee of our master allows us to derive many new results for both the expert problem and more generally Online Linear Optimization.
APA
Chen, L., Luo, H. & Wei, C.. (2021). Impossible Tuning Made Possible: A New Expert Algorithm and Its Applications. Proceedings of Thirty Fourth Conference on Learning Theory, in Proceedings of Machine Learning Research 134:1216-1259 Available from https://proceedings.mlr.press/v134/chen21f.html.

Related Material