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

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.

References in corpus (10)

• Online Learning with Predictable Sequences
• Fast Convergence of Regularized Learning in Games
• More Adaptive Algorithms for Adversarial Bandits
• A Second-order Bound with Excess Losses
• Tracking the Best Expert in Non-stationary Stochastic Environments
• Combining Adversarial Guarantees and Stochastic Fast Rates in Online Learning
• Lipschitz and Comparator-Norm Adaptivity in Online Learning
• Minimax Regret for Stochastic Shortest Path with Adversarial Costs and Known Transition
• Strongly Adaptive Online Learning
• Adaptive and Efficient Algorithms for Tracking the Best Expert

Cited by in corpus (5)

• Minimax Regret for Stochastic Shortest Path with Adversarial Costs and Known Transition
• Finding the Stochastic Shortest Path with Low Regret: The Adversarial Cost and Unknown Transition Case
• Universal Online Convex Optimization Meets Second-order Bounds
• Nonstochastic Bandits and Experts with Arm-Dependent Delays
• Adversarial Tracking Control via Strongly Adaptive Online Learning with Memory