Tight Bounds on Minimax Regret under Logarithmic Loss via Self-Concordance
This provides foundational theoretical guarantees for online learning and prediction under logarithmic loss, with applications to nonparametric expert classes like Lipschitz functions.
The paper tackles the problem of sequential probability assignment under logarithmic loss against arbitrary expert classes, obtaining tight bounds on minimax regret by exploiting self-concordance, with results showing regret scales as O(n^{p/(p+1)}) for classes with metric entropy O(γ^{-p}).
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 with (sequential) metric entropy $\mathcal{O}(γ^{-p})$ at scale $γ$, the minimax regret is $\mathcal{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.