Tight Bounds on Minimax Regret under Logarithmic Loss via Self-Concordance

[Note: This is joint work with Dylan Foster (also at Simons) and Blair Bilodeau (my graduate student, and visitor at Simons for one week to initiate this collaboration). This work was published at ICML 2020.] We consider the classical problem of sequential probability assignment under logarithmic loss while competing against an arbitrary, potentially nonparametric class of experts. We obtain tight 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 for which the (sequential) metric entropy grows as $\gamma^{-p}$, the minimax regret is at most $O(n^{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.