# Sequential Probability Assignment with Binary Alphabets and Large Classes of Experts

arXiv: https://arxiv.org/abs/1501.07340 · HTML: https://mlsanity.com/paper/1501.07340/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Jan 2015.

## Built on by (most cited first, 11 of 11)

- [Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination](https://mlsanity.com/paper/2107.02237/) (2021)
- [Expected Worst Case Regret via Stochastic Sequential Covering](https://mlsanity.com/paper/2209.04417/) (2022)
- [Damped Online Newton Step for Portfolio Selection](https://mlsanity.com/paper/2202.07574/) (2022)
- [Smoothed Analysis of Sequential Probability Assignment](https://mlsanity.com/paper/2303.04845/) (2023)
- [Precise Regret Bounds for Log-loss via a Truncated Bayesian Algorithm](https://mlsanity.com/paper/2205.03728/) (2022)
- [Projection-Free Online Convex Optimization via Efficient Newton Iterations](https://mlsanity.com/paper/2306.11121/) (2023)
- [Sequential prediction under log-loss and misspecification](https://mlsanity.com/paper/2102.00050/) (2021)
- [Exploring Local Norms in Exp-concave Statistical Learning](https://mlsanity.com/paper/2302.10726/) (2023)
- [Sequential Probability Assignment with Contexts: Minimax Regret, Contextual Shtarkov Sums, and Contextual Normalized Maximum Likelihood](https://mlsanity.com/paper/2410.03849/) (2024)
- [Robust Online Classification: From Estimation to Denoising](https://mlsanity.com/paper/2309.01698/) (2023)
- [Online Distribution Learning with Local Private Constraints](https://mlsanity.com/paper/2402.00315/) (2024)

## Abstract (arXiv)

We analyze the problem of sequential probability assignment for binary outcomes with side information and logarithmic loss, where regret---or, redundancy---is measured with respect to a (possibly infinite) class of experts. We provide upper and lower bounds for minimax regret in terms of sequential complexities of the class. These complexities were recently shown to give matching (up to logarithmic factors) upper and lower bounds for sequential prediction with general convex Lipschitz loss functions (Rakhlin and Sridharan, 2015). To deal with unbounded gradients of the logarithmic loss, we present a new analysis that employs a sequential chaining technique with a Bernstein-type bound. The introduced complexities are intrinsic to the problem of sequential probability assignment, as illustrated by our lower bound. We also consider an example of a large class of experts parametrized by vectors in a high-dimensional Euclidean ball (or a Hilbert ball). The typical discretization approach fails, while our techniques give a non-trivial bound. For this problem we also present an algorithm based on regularization with a self-concordant barrier. This algorithm is of an independent interest, as it requires a bound on the function values rather than gradients.