Abstract
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}(\gamma^{-p})$ at scale $\gamma$, 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.
Introduction
In the framework of online learning, the problem of sequential probability assignment involves a learner predicting the probability of binary outcomes at each time step. The learner's performance is measured by the cumulative logarithmic loss, defined as $-\log(p)$ for an outcome of 1 and $-\log(1-p)$ for 0. The objective is to minimize the minimax regret, the difference between the learner's total loss and the loss of the best-performing expert in a reference class $\mathcal{F}$ in hindsight.
While this problem is well-understood for finite or simple parametric expert classes, it becomes significantly more challenging for "rich" or nonparametric classes. The primary difficulty lies in the fact that the logarithmic loss is non-Lipschitz; as predictions approach the boundaries of 0 or 1, the loss and its gradient can explode to infinity. This paper introduces a novel approach to bypass traditional analytical bottlenecks, providing the first tight bounds for complex expert classes.
The Problem with Truncation
For decades, the standard technique for handling the non-Lipschitz nature of the log loss was "truncation." Researchers would artificially constrain predictions to a safe interval, such as $[\delta, 1-\delta]$, to prevent infinite losses. While truncation simplifies the mathematical analysis, it is a blunt instrument. For high-complexity expert classes—such as nonparametric Lipschitz functions—truncation leads to suboptimal regret bounds. It fails to capture the true relationship between the complexity of the expert class and the achievable regret, leaving a gap in the theoretical understanding of the problem.
Methods: Exploiting Self-Concordance
The core innovation of this work is the shift from treating log loss as a bounded Lipschitz function to exploiting its self-concordance. A function is self-concordant if its third derivative is controlled by its second derivative—a property central to the efficiency of interior-point methods in optimization. The log function is the prototypical example of such a function.
Dual Games and Offset Processes
The authors utilize a minimax theorem to transition to a "dual" version of the online game, which is more amenable to analysis. Within this dual framework, they develop a new technique involving offset sequential processes. While similar "offset" methods have been successful for square loss (which is strongly convex), they typically fail for log loss due to the unbounded gradient. By leveraging self-concordance, the authors create a "natural" offset that cancels out the extreme fluctuations of the log loss near the boundaries. This allows for a precise analysis of the regret without resorting to artificial truncation.
Sequential Complexity
The regret is ultimately characterized by the sequential metric entropy of the expert class, $H_\infty(\mathcal{F}, \gamma, n)$. This measure quantifies the number of representative experts needed to cover the class $\mathcal{F}$ across all possible sequences of outcomes. The paper demonstrates that for log loss, the minimax regret is not merely a function of the covering number, but is sensitive to the specific structural properties of the expert class that other loss functions might ignore.
Key Results
The paper establishes several landmark results for minimax regret under log loss:
- General Upper Bound: For any expert class with sequential entropy $\mathcal{O}(\gamma^{-p})$, the minimax regret is bounded by $R_n(\mathcal{F}) \leq \mathcal{O}(n^{p/(p+1)})$. This represents a strict improvement over previous state-of-the-art results for complex classes ($p > 1$).
- Tightness for Lipschitz Experts: The authors resolve a long-standing open question by providing a matching lower bound for nonparametric Lipschitz classes, proving that the rate $\Theta(n^{p/(p+1)})$ is optimal.
- Smooth Nonparametric Classes: For classes where the first $k-1$ derivatives are Lipschitz, the authors establish the optimal regret rate as $\tilde{\mathcal{O}}(n^{d/(d+k)})$, where $d$ is the dimension.
- Neural Networks: The framework provides new bounds for neural networks with Lipschitz activations and bounded weights, characterizing their performance in sequential probability assignment.
Conclusion and Future Work
By respecting the natural curvature of the logarithmic loss through self-concordance, this research provides a more refined and accurate characterization of minimax regret than previous truncation-based methods. However, several challenges remain. The current bounds rely on the $L_\infty$ (supremum) norm for sequential covering; a more tailored complexity measure might be required for a universal characterization across all expert classes. Additionally, extending these techniques from binary outcomes to infinite outcome spaces (adversarial online density estimation) and developing computationally efficient algorithms to achieve these theoretical limits are promising avenues for future research.
Summary updated