Timezone: »

 
Poster
Improved Bounds on Minimax Regret under Logarithmic Loss via Self-Concordance
Blair Bilodeau · Dylan Foster · Daniel Roy

Thu Jul 16 06:00 AM -- 06:45 AM & Thu Jul 16 05:00 PM -- 05:45 PM (PDT) @
in Poster Session 41 »
We consider the classical problem of sequential probability assignment under logarithmic loss while competing against an arbitrary, potentially nonparametric class of experts. We obtain improved bounds on the minimax regret via a new approach that exploits the self-concordance property of the logarithmic loss. We show that for any expert class with (sequential) metric entropy $\mathcal{O}(\gamma^{-p})$ at scale $\gamma$, the minimax regret is $\mathcal{O}(n^{\frac{p}{p+1}})$, and that this rate cannot be improved without additional assumptions on the expert class under consideration. As an application of our techniques, we resolve the minimax regret for nonparametric Lipschitz classes of experts.
Keywords: Statistical Learning Theory · Online Learning / Bandits · Online Learning, Active Learning, and Bandits

Author Information

Blair Bilodeau (University of Toronto)
Dylan Foster (MIT)
Daniel Roy (University of Toronto; Vector Institute)

More from the Same Authors