# Martingale Methods for Sequential Estimation of Convex Functionals and Divergences

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 104 references that are in the map.
- First posted on arXiv 16 Mar 2021.

## Builds on (most cited first, 18 of 18)

- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Statistical Aspects of Wasserstein Distances](https://mlsanity.com/paper/1806.05500/) (2018)
- [Estimating means of bounded random variables by betting](https://mlsanity.com/paper/2010.09686/) (2020)
- [lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits](https://mlsanity.com/paper/1312.7308/) (2013)
- [Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervals](https://mlsanity.com/paper/1811.11419/) (2018)
- [Admissible anytime-valid sequential inference must rely on nonnegative martingales](https://mlsanity.com/paper/2009.03167/) (2020)
- [Statistical Optimal Transport via Factored Couplings](https://mlsanity.com/paper/1806.07348/) (2018)
- [Testing randomness](https://mlsanity.com/paper/1906.09256/) (2019)
- [Sequential estimation of quantiles with applications to A/B-testing and best-arm identification](https://mlsanity.com/paper/1906.09712/) (2019)
- [Optimal Bounds between f-Divergences and Integral Probability Metrics](https://mlsanity.com/paper/2006.05973/) (2020)
- [On the bias, risk and consistency of sample means in multi-armed bandits](https://mlsanity.com/paper/1902.00746/) (2019)
- [Practical and Consistent Estimation of f-Divergences](https://mlsanity.com/paper/1905.11112/) (2019)
- [Minimax Confidence Intervals for the Sliced Wasserstein Distance](https://mlsanity.com/paper/1909.07862/) (2019)
- [Inference for Empirical Wasserstein Distances on Finite Spaces](https://mlsanity.com/paper/1610.03287/) (2016)
- [Sequential Nonparametric Testing with the Law of the Iterated Logarithm](https://mlsanity.com/paper/1506.03486/) (2015)
- [Off-policy Confidence Sequences](https://mlsanity.com/paper/2102.09540/) (2021)
- [Generalized Exponential Concentration Inequality for R'enyi Divergence Estimation](https://mlsanity.com/paper/1603.08589/) (2016)
- [Efficient functional estimation and the super-oracle phenomenon](https://mlsanity.com/paper/1904.09347/) (2019)

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

- [Optimal PAC Bounds Without Uniform Convergence](https://mlsanity.com/paper/2304.09167/) (2023)
- [E-detectors: a nonparametric framework for sequential change detection](https://mlsanity.com/paper/2203.03532/) (2022)
- [A unified recipe for deriving (time-uniform) PAC-Bayes bounds](https://mlsanity.com/paper/2302.03421/) (2023)
- [Time-Uniform Confidence Spheres for Means of Random Vectors](https://mlsanity.com/paper/2311.08168/) (2023)
- [Adaptive Principal Component Regression with Applications to Panel Data](https://mlsanity.com/paper/2307.01357/) (2023)
- [Anytime-Valid Inference for Double/Debiased Machine Learning of Causal Parameters](https://mlsanity.com/paper/2408.09598/) (2024)
- [Sequentially Auditing Differential Privacy](https://mlsanity.com/paper/2509.07055/) (2025)
- [Information Processing Equalities and the Information-Risk Bridge](https://mlsanity.com/paper/2207.11987/) (2022)
- [Sequential change detection via backward confidence sequences](https://mlsanity.com/paper/2302.02544/) (2023)
- [The extended Ville's inequality for nonintegrable nonnegative supermartingales](https://mlsanity.com/paper/2304.01163/) (2023)
- [On Learning-Curve Monotonicity for Maximum Likelihood Estimators](https://mlsanity.com/paper/2512.10220/) (2025)
- [A variational approach to dimension-free self-normalized concentration](https://mlsanity.com/paper/2508.06483/) (2025)
- [The Sample Complexity of Parameter-Free Stochastic Convex Optimization](https://mlsanity.com/paper/2506.11336/) (2025)
- [Hypothesis Testing for Generalized Thurstone Models](https://mlsanity.com/paper/2512.02912/) (2025)
- [Positive Semidefinite Matrix Supermartingales](https://mlsanity.com/paper/2401.15567/) (2024)
- [Set-Preserving Calibration from Conformal P-Values to E-Values](https://mlsanity.com/paper/2606.03600/) (2026)
- [Anytime-Valid Confirmation of Covariate Balance for Prespecified Corrections](https://mlsanity.com/paper/2607.23157/) (2026)
- [From Pixels to Privacy-Sensitive Features: An Information-Theoretic Framework for Reconstruction Bounds](https://mlsanity.com/paper/2610.13768/) (2026)

## Abstract (arXiv)

We present a unified technique for sequential estimation of convex divergences between distributions, including integral probability metrics like the kernel maximum mean discrepancy, varphi-divergences like the Kullback-Leibler divergence, and optimal transport costs, such as powers of Wasserstein distances. This is achieved by observing that empirical convex divergences are (partially ordered) reverse submartingales with respect to the exchangeable filtration, coupled with maximal inequalities for such processes. These techniques appear to be complementary and powerful additions to the existing literature on both confidence sequences and convex divergences. We construct an offline-to-sequential device that converts a wide array of existing offline concentration inequalities into time-uniform confidence sequences that can be continuously monitored, providing valid tests or confidence intervals at arbitrary stopping times. The resulting sequential bounds pay only an iterated logarithmic price over the corresponding fixed-time bounds, retaining the same dependence on problem parameters (like dimension or alphabet size if applicable). These results are also applicable to more general convex functionals -- like the negative differential entropy, suprema of empirical processes, and V-Statistics -- and to more general processes satisfying a key leave-one-out property.