Bregman Deviations of Generic Exponential Families

Sayak Ray Chowdhury, Patrick Saux, Odalric-Ambrym Maillard, Aditya Gopalan

Abstract

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.

Introduction

In modern machine learning and sequential statistics—ranging from multi-armed bandits to reinforcement learning—researchers frequently need to estimate hidden parameters from a continuous stream of data. A fundamental challenge in these settings is determining the precision of an estimate at any given moment. While standard concentration inequalities like Hoeffding’s or Bernstein’s provide bounds for a fixed, pre-determined number of samples, they fail in sequential environments. In such cases, practitioners often "peek" at the data to decide when to stop or change strategies, a practice that invalidates fixed-sample bounds.

To address this, we require time-uniform concentration inequalities: confidence sets that remain valid with high probability simultaneously across all possible sample sizes. This paper, presented at COLT 2023, introduces a unified theoretical framework for creating these bounds across generic exponential families by leveraging the geometry of Bregman divergences and the "method of mixtures."

The Method of Mixtures and Bregman Geometry

Existing approaches to time-uniform bounds often rely on "stitching" (or peeling) techniques, which can result in loose, conservative bounds, or are restricted to simple distributions like Gaussians with known variance. This research revisits the method of mixtures (also known as the Laplace method) to provide a more elegant and tighter alternative.

Bregman Divergence

Rather than using standard Euclidean distance, the framework measures error using Bregman divergence. This is the natural geometric measure for exponential families (including Gaussian, Bernoulli, and Poisson distributions) because it accounts for the local curvature of the distribution space. By using the log-partition function of the family to define the divergence, the resulting bounds are intrinsically adapted to the distribution's shape.

Bregman Information Gain

A central contribution of this work is the introduction of the Bregman information gain (denoted as $\gamma_{n,c}$). This quantity extends classical information gain to the broader context of exponential families, quantifying how much information about a parameter is extracted from $n$ samples through the lens of Bregman geometry.

Conjugate Priors

By integrating over a mixture of martingales using a prior distribution, the authors simplify complex statistical tracking. Specifically, by choosing priors that are "conjugate" to the exponential family, the authors transform complex integrals into simple, closed-form parameter updates, making the bounds computationally efficient for practitioners.

Key Insights

  1. Natural Asymmetry: Because the framework utilizes Bregman divergences, the resulting confidence intervals are naturally asymmetric. For instance, in a Bernoulli distribution near the boundaries (0 or 1), the bound respects the $[0, 1]$ constraints without requiring manual clipping.
  2. Small-Sample Sharpness: While many statistical methods rely on asymptotic behavior (working well only with large datasets), this method is specifically designed to be "sharp" or tight in small-sample regimes.
  3. Anytime Validity: The bounds are valid for any random stopping time, making them ideal for "change detection" tasks where one must identify the exact moment a data stream's behavior shifts.
  4. Unified Theorem: Theorem 3 in the paper provides a single "recipe" for concentration. To derive a bound for a new distribution, a practitioner simply needs to plug in its specific log-partition function.

Empirical Results and Applications

The authors evaluated their framework using simulated data across a wide variety of distributions, including Gaussian (unknown mean and variance), Bernoulli, Poisson, Exponential, Gamma, Weibull, Pareto, and Chi-square. To support the community, they released concentration-lib, an open-source Python library containing these implementations.

Comparative Performance

The mixture-based approach consistently outperforms state-of-the-art "stitching" methods. It provides tighter confidence sets, particularly before the number of samples reaches large asymptotic scales.

Solving Open Problems

The theory was applied to solve a known open problem in Generalized Likelihood Ratio (GLR) tests: detecting changes in the variance of Gaussian distributions while maintaining a strictly controlled false-alarm rate. Additionally, in the context of linear bandits, the approach yields a tighter confidence ellipsoid than the classic Abbasi-Yadkori et al. (2011) bound, which has long been a standard in the field.

Limitations and Future Work

While the bounds are superior for small samples, they scale as $\log(n)/n$ asymptotically. Theoretical limits suggested by the Law of the Iterated Logarithm indicate that $\log \log(n)/n$ is possible, though often at the cost of performance in the small-sample regime. Furthermore, while many distributions yield closed-form solutions, complex cases like Poisson or Chi-square distributions may require numerical integration for the Bregman information gain.

Future research directions include exploring model misspecification—investigating how these bounds perform when the underlying data does not perfectly fit the assumed exponential family.

Summary updated

Abstract

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.
BibTeX
@inproceedings{chowdhury2023bregman,
  author = {Sayak Ray Chowdhury and Patrick Saux and Odalric-Ambrym Maillard and Aditya Gopalan},
  title = {{Bregman Deviations of Generic Exponential Families}},
  booktitle = {Conference on Learning Theory},
  year = {2023},
  url = {https://openreview.net/forum?id=eNt0Dnt5lY},
}
Figure