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

Blair Bilodeau, Dylan J. Foster, Daniel M. RoyICML 2020 · OpenReview

Introduction

In sequential probability assignment, a learner predicts the probability of a binary outcome at each step, aiming to perform as well as the best "expert" in a reference class. Performance is typically measured by logarithmic loss—the negative log-likelihood of the observed outcome.

The gold standard for evaluating this performance is minimax regret: the worst-case difference between the learner's total loss and the best expert's total loss. While minimax regret is well-understood for simple, finite, or parametric expert classes, it has remained an open challenge for "rich" nonparametric classes, such as Lipschitz functions.

The fundamental difficulty lies in the fact that log loss is not Lipschitz continuous; its gradient explodes as predictions approach 0 or 1. Historically, researchers circumvented this by "truncating" predictions—forcing them to stay within a bounded range like $[\delta, 1-\delta]$. However, this workaround yields suboptimal regret bounds that fail to capture the true complexity of the problem. In this paper, Bilodeau, Foster, and Roy provide the first tight minimax regret bounds for sequential probability assignment under logarithmic loss for complex, nonparametric expert classes by entirely bypassing the need for truncation.

Methodology: Bypassing Truncation via Self-Concordance

The authors introduce a novel analysis technique that replaces truncation with a mathematical property known as self-concordance. Their approach unfolds across several key analytical steps:

  1. Leveraging Self-Concordance: Originally popularized in interior-point methods for optimization, a function is self-concordant if its third derivative is bounded by its second derivative. The authors demonstrate that log loss is self-concordant, allowing them to "linearize" the loss function using a local norm.
  2. The Offset Process: Using self-concordance, they derive a new "offset" process. Unlike previous "strong convexity" offsets that failed to neutralize the exploding gradients of the log loss, this self-concordant offset naturally scales with the loss's curvature. This effectively cancels out the unbounded values near the boundaries.
  3. Minimax Duality: The authors utilize a standard minimax theorem to transition to a "dual game," which allows them to analyze the problem as a dependent empirical process.
  4. Sequential Covering: Finally, they bound the complexity of the expert class using sequential metric entropy ($H_\infty$), a measure that accounts for the adaptive, tree-like nature of online learning.

Key Findings and Theoretical Results

As a theoretical paper focused on fundamental limits, the authors evaluate their bounds against mathematical constructions of expert classes rather than empirical datasets. These include nonparametric Lipschitz classes, infinite-dimensional linear predictors, and neural networks with Lipschitz activations and bounded weights.

Tight Bounds for Lipschitz Experts

The primary breakthrough of the paper is the realization that the unboundedness of the log loss is not a bug to be suppressed by truncation, but a feature that can be managed via second-order curvature.

The authors prove that for any expert class with sequential entropy $H_\infty(\mathcal{F}, \gamma, n) = O(\gamma^{-p})$, the minimax regret is bounded by $R_n(\mathcal{F}) \leq O(n^{p/(p+1)})$. Furthermore, they provide a matching lower bound for 1-Lipschitz experts, proving their rate is exactly $\Theta(n^{p/(p+1)})$. This resolves a specific open question posed by Rakhlin & Sridharan (2015).

Significant Improvements Over Prior Art

For complex classes where $p > 1$, this new rate is strictly better than previous state-of-the-art bounds. For example, if $p=2$, the previous best rate was roughly $O(n^{3/4})$, whereas the new self-concordant analysis yields a tighter $O(n^{2/3})$.

The Limits of Sequential Entropy

A surprising theoretical finding (Corollary 4) is that sequential entropy alone cannot perfectly characterize minimax regret for log loss. The authors demonstrate that two distinct expert classes can possess the exact same sequential entropy but exhibit different regret rates, indicating that entropy paints an incomplete picture of problem complexity.

Limitations and Future Directions

While the paper establishes foundational theoretical limits, it presents a few notable constraints:

  • Non-Constructive: The analysis focuses on the existence of a minimax bound rather than providing an efficient, computationally feasible algorithm to achieve it in practice.
  • Binary Outcomes: The current framework is restricted to binary outcomes $\{0, 1\}$. Extending these tight bounds to continuous outcomes—such as adversarial online density estimation—remains a significant open challenge.
  • Refining Complexity Measures: Because sequential entropy was proven insufficient to fully characterize log loss regret, the authors suggest that future research must develop new complexity measures specifically tailored to the self-concordant properties of the loss function.

Summary updated

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 bound...
BibTeX
@inproceedings{bilodeau2020tight,
  author = {Blair Bilodeau and Dylan J. Foster and Daniel M. Roy},
  title = {{Tight Bounds on Minimax Regret under Logarithmic Loss via Self-Concordance}},
  booktitle = {International Conference on Machine Learning},
  year = {2020},
  url = {https://openreview.net/forum?id=rqUZC8hvJGc},
}
Figure