On Equivalence of Martingale Tail Bounds and Deterministic Regret Inequalities
This work provides theoretical tools for analyzing martingale tail bounds and regret inequalities, which is incremental for researchers in online learning and probability theory.
The paper establishes an equivalence between deterministic regret bounds in online learning, high-probability tail bounds for martingale suprema, and in-expectation bounds, enabling proofs of exponential tail bounds for Banach space valued martingales via online mirror descent with adaptive step sizes. It extends this to general function classes by defining a martingale type and linking it to sequential complexities, with results for classes of type 2.
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.