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

Understand

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$.