Sequential Probability Assignment with Binary Alphabets and Large
  Classes of Experts
  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.
