On Equivalence of Martingale Tail Bounds and Deterministic Regret
  Inequalities
  We study an equivalence of (i) deterministic pathwise statements appearing in
the online learning literature (termed \emph{regret bounds}), (ii)
high-probability tail bounds for the supremum of a collection of martingales
(of a specific form arising from uniform laws of large numbers for
martingales), and (iii) in-expectation bounds for the supremum. By virtue of
the equivalence, we prove exponential tail bounds for norms of Banach space
valued martingales via deterministic regret bounds for the online mirror
descent algorithm with an adaptive step size. We extend these results beyond
the linear structure of the Banach space: we define a notion of
\emph{martingale type} for general classes of real-valued functions and show
its equivalence (up to a logarithmic factor) to various sequential complexities
of the class (in particular, the sequential Rademacher complexity and its
offset version). For classes with the general martingale type 2, we exhibit a
finer notion of variation that allows partial adaptation to the function
indexing the martingale. Our proof technique rests on sequential symmetrization
and on certifying the \emph{existence} of regret minimization strategies for
certain online prediction problems.
