# On Equivalence of Martingale Tail Bounds and Deterministic Regret Inequalities

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

## Key facts

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

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

- [Tight Concentrations and Confidence Sequences from the Regret of Universal Portfolio](https://mlsanity.com/paper/2110.14099/) (2021)
- [Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clipping](https://mlsanity.com/paper/2412.19529/) (2024)
- [Unlocking Tokens as Data Points for Generalization Bounds on Larger Language Models](https://mlsanity.com/paper/2407.18158/) (2024)
- [Improved Regret Bounds of (Multinomial) Logistic Bandits via Regret-to-Confidence-Set Conversion](https://mlsanity.com/paper/2310.18554/) (2023)
- [Dealing with unbounded gradients in stochastic saddle-point optimization](https://mlsanity.com/paper/2402.13903/) (2024)
- [Off-policy Confidence Sequences](https://mlsanity.com/paper/2102.09540/) (2021)
- [Online-to-PAC Conversions: Generalization Bounds via Regret Analysis](https://mlsanity.com/paper/2305.19674/) (2023)
- [A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Width](https://mlsanity.com/paper/2311.09197/) (2023)
- [Tighter PAC-Bayes Bounds Through Coin-Betting](https://mlsanity.com/paper/2302.05829/) (2023)
- [Confidence Sequences for Generalized Linear Models via Regret Analysis](https://mlsanity.com/paper/2504.16555/) (2025)
- [Bypassing the Noisy Parity Barrier: Learning Higher-Order Markov Random Fields from Dynamics](https://mlsanity.com/paper/2409.05284/) (2024)
- [Linear Bandits on Uniformly Convex Sets](https://mlsanity.com/paper/2103.05907/) (2021)
- [Noise-Adaptive Confidence Sets for Linear Bandits and Application to Bayesian Optimization](https://mlsanity.com/paper/2402.07341/) (2024)
- [In Defense of Defensive Forecasting](https://mlsanity.com/paper/2506.11848/) (2025)
- [Local and Global Uniform Convexity Conditions](https://mlsanity.com/paper/2102.05134/) (2021)
- [Better-than-KL PAC-Bayes Bounds](https://mlsanity.com/paper/2402.09201/) (2024)
- [The Stability of Online Algorithms in Performative Prediction](https://mlsanity.com/paper/2602.24207/) (2026)
- [Differentially Private Nonparametric Regression Under a Growth Condition](https://mlsanity.com/paper/2111.12786/) (2021)
- [Online-to-PAC generalization bounds under graph-mixing dependencies](https://mlsanity.com/paper/2410.08977/) (2024)
- [Distances for Markov chains from sample streams](https://mlsanity.com/paper/2505.18005/) (2025)
- [Eventually LIL Regret: Almost Sure lnln T Regret for a sub-Gaussian Mixture on Unbounded Data](https://mlsanity.com/paper/2512.12325/) (2025)
- [Explaining Fast Improvement in Online Imitation Learning](https://mlsanity.com/paper/2007.02520/) (2020)
- [Preparing for Black Swans: The Antifragility Imperative for Machine Learning](https://mlsanity.com/paper/2405.11397/) (2024)
- [Self-Normalized Martingales and Uniform Regret Bounds for Linear Regression](https://mlsanity.com/paper/2605.01628/) (2026)
- [C-IDS: Solving Contextual POMDP via Information-Directed Objective](https://mlsanity.com/paper/2602.03939/) (2026)
- [Operationalizing Stein's Method for Online Linear Optimization: CLT-Based Optimal Tradeoffs](https://mlsanity.com/paper/2602.06545/) (2026)
- [From Betting to Empirical Bernstein LIL](https://mlsanity.com/paper/2605.22124/) (2026)

## Abstract (arXiv)

We study an equivalence of (i) deterministic pathwise statements appearing in the online learning literature (termed 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 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 existence of regret minimization strategies for certain online prediction problems.