# Bregman Deviations of Generic Exponential Families

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 52 references that are in the map.
- First posted on arXiv 18 Jan 2022.

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

- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [Time-uniform, nonparametric, nonasymptotic confidence sequences](https://mlsanity.com/paper/1810.08240/) (2018)
- [Estimating means of bounded random variables by betting](https://mlsanity.com/paper/2010.09686/) (2020)
- [Improved Optimistic Algorithms for Logistic Bandits](https://mlsanity.com/paper/2002.07530/) (2020)
- [Information Directed Sampling and Bandits with Heteroscedastic Noise](https://mlsanity.com/paper/1801.09667/) (2018)
- [Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervals](https://mlsanity.com/paper/1811.11419/) (2018)
- [Thompson Sampling for 1-Dimensional Exponential Family Bandits](https://mlsanity.com/paper/1307.3400/) (2013)
- [Bootstrapping Upper Confidence Bound](https://mlsanity.com/paper/1906.05247/) (2019)
- [Upper-Confidence-Bound Algorithms for Active Learning in Multi-Armed Bandits](https://mlsanity.com/paper/1507.04523/) (2015)
- [Optimal Algorithms for Stochastic Multi-Armed Bandits with Heavy Tailed Rewards](https://mlsanity.com/paper/2010.12866/) (2020)
- [Streaming kernel regression with provably adaptive mean, variance, and regularization](https://mlsanity.com/paper/1708.00768/) (2017)
- [Large Deviation Methods for Approximate Probabilistic Inference](https://mlsanity.com/paper/1301.7392/) (2013)
- [Sub-sampling for Efficient Non-Parametric Bandit Exploration](https://mlsanity.com/paper/2010.14323/) (2020)
- [Near-Optimal Confidence Sequences for Bounded Random Variables](https://mlsanity.com/paper/2006.05022/) (2020)

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

- [A Unified Confidence Sequence for Generalized Linear Models, with Applications to Bandits](https://mlsanity.com/paper/2407.13977/) (2024)
- [Improved Regret Bounds of (Multinomial) Logistic Bandits via Regret-to-Confidence-Set Conversion](https://mlsanity.com/paper/2310.18554/) (2023)
- [ConjNorm: Tractable Density Estimation for Out-of-Distribution Detection](https://mlsanity.com/paper/2402.17888/) (2024)
- [Dealing with Unknown Variances in Best-Arm Identification](https://mlsanity.com/paper/2210.00974/) (2022)
- [Likelihood Ratio Confidence Sets for Sequential Decision Making](https://mlsanity.com/paper/2311.04402/) (2023)
- [Confidence Sequences for Generalized Linear Models via Regret Analysis](https://mlsanity.com/paper/2504.16555/) (2025)
- [Noise-Adaptive Confidence Sets for Linear Bandits and Application to Bayesian Optimization](https://mlsanity.com/paper/2402.07341/) (2024)
- [Bias-variance decompositions: the exclusive privilege of Bregman divergences](https://mlsanity.com/paper/2501.18581/) (2025)
- [Post-detection inference for sequential changepoint localization](https://mlsanity.com/paper/2502.06096/) (2025)
- [Sequential change detection via backward confidence sequences](https://mlsanity.com/paper/2302.02544/) (2023)
- [Entropy, concentration, and learning: a statistical mechanics primer](https://mlsanity.com/paper/2409.18630/) (2024)
- [Online Heavy-tailed Change-point detection](https://mlsanity.com/paper/2306.09548/) (2023)
- [Laws of thermodynamics for exponential families](https://mlsanity.com/paper/2501.02071/) (2025)

## Abstract (arXiv)

We revisit the method of mixture technique, also known as the Laplace method, to study the concentration phenomenon in generic exponential families. Combining the properties of Bregman divergence associated with log-partition function of the family with the method of mixtures for super-martingales, we establish a generic bound controlling the Bregman divergence between the parameter of the family and a finite sample estimate of the parameter. Our bound is time-uniform and makes appear a quantity extending the classical information gain to exponential families, which we call the Bregman information gain. For the practitioner, we instantiate this novel bound to several classical families, e.g., Gaussian, Bernoulli, Exponential, Weibull, Pareto, Poisson and Chi-square yielding explicit forms of the confidence sets and the Bregman information gain. We further numerically compare the resulting confidence bounds to state-of-the-art alternatives for time-uniform concentration and show that this novel method yields competitive results. Finally, we highlight the benefit of our concentration bounds on some illustrative applications.