Bregman Deviations of Generic Exponential Families

Sayak Ray Chowdhury, Patrick Saux, Odalric Maillard, Aditya Gopalan
Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:394-449, 2023.

Abstract

We revisit the method of mixtures, or Laplace method, to study the concentration phenomenon in generic (possibly multidimensional) exponential families. Using the duality properties of the Bregman divergence associated with the log-partition function of the family to construct nonnegative martingales, we establish a generic bound controlling the deviation between the parameter of the family and a finite sample estimate, expressed in the local geometry induced by the Bregman pseudo-metric. Our bound is time-uniform and involves 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 (including with unknown variance or multivariate), Bernoulli, Exponential, Weibull, Pareto, Poisson and Chi-square, yielding explicit forms of the confidence sets and the Bregman information gain. We further compare the resulting confidence bounds to state-of-the-art time-uniform alternatives and show this novel method yields competitive results. Finally, we apply our result to the design of generalized likelihood ratio tests for change detection, capturing new settings such as variance change in Gaussian families.

Cite this Paper

BibTeX
@InProceedings{pmlr-v195-chowdhury23a, title = {Bregman Deviations of Generic Exponential Families}, author = {Chowdhury, Sayak Ray and Saux, Patrick and Maillard, Odalric and Gopalan, Aditya}, booktitle = {Proceedings of Thirty Sixth Conference on Learning Theory}, pages = {394--449}, year = {2023}, editor = {Neu, Gergely and Rosasco, Lorenzo}, volume = {195}, series = {Proceedings of Machine Learning Research}, month = {12--15 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v195/chowdhury23a/chowdhury23a.pdf}, url = {https://proceedings.mlr.press/v195/chowdhury23a.html}, abstract = {We revisit the method of mixtures, or Laplace method, to study the concentration phenomenon in generic (possibly multidimensional) exponential families. Using the duality properties of the Bregman divergence associated with the log-partition function of the family to construct nonnegative martingales, we establish a generic bound controlling the deviation between the parameter of the family and a finite sample estimate, expressed in the local geometry induced by the Bregman pseudo-metric. Our bound is time-uniform and involves 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 (including with unknown variance or multivariate), Bernoulli, Exponential, Weibull, Pareto, Poisson and Chi-square, yielding explicit forms of the confidence sets and the Bregman information gain. We further compare the resulting confidence bounds to state-of-the-art time-uniform alternatives and show this novel method yields competitive results. Finally, we apply our result to the design of generalized likelihood ratio tests for change detection, capturing new settings such as variance change in Gaussian families.} }
Endnote
%0 Conference Paper %T Bregman Deviations of Generic Exponential Families %A Sayak Ray Chowdhury %A Patrick Saux %A Odalric Maillard %A Aditya Gopalan %B Proceedings of Thirty Sixth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2023 %E Gergely Neu %E Lorenzo Rosasco %F pmlr-v195-chowdhury23a %I PMLR %P 394--449 %U https://proceedings.mlr.press/v195/chowdhury23a.html %V 195 %X We revisit the method of mixtures, or Laplace method, to study the concentration phenomenon in generic (possibly multidimensional) exponential families. Using the duality properties of the Bregman divergence associated with the log-partition function of the family to construct nonnegative martingales, we establish a generic bound controlling the deviation between the parameter of the family and a finite sample estimate, expressed in the local geometry induced by the Bregman pseudo-metric. Our bound is time-uniform and involves 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 (including with unknown variance or multivariate), Bernoulli, Exponential, Weibull, Pareto, Poisson and Chi-square, yielding explicit forms of the confidence sets and the Bregman information gain. We further compare the resulting confidence bounds to state-of-the-art time-uniform alternatives and show this novel method yields competitive results. Finally, we apply our result to the design of generalized likelihood ratio tests for change detection, capturing new settings such as variance change in Gaussian families.
APA
Chowdhury, S.R., Saux, P., Maillard, O. & Gopalan, A.. (2023). Bregman Deviations of Generic Exponential Families. Proceedings of Thirty Sixth Conference on Learning Theory, in Proceedings of Machine Learning Research 195:394-449 Available from https://proceedings.mlr.press/v195/chowdhury23a.html.

Related Material