Approximating the Total Variation Distance between Gaussians

Arnab Bhattacharyya, Weiming Feng, Piyush Srivastava
Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, PMLR 258:1846-1854, 2025.

Abstract

The total variation distance is a metric of central importance in statistics and probability theory. However, somewhat surprisingly, questions about computing it \emph{algorithmically} appear not to have been systematically studied until very recently. In this paper, we contribute to this line of work by studying this question in the important special case of multivariate Gaussians. More formally, we consider the problem of approximating the total variation distance between two multivariate Gaussians to within an $\epsilon$-relative error. Previous works achieved a \emph{fixed} constant relative error approximation via closed-form formulas. In this work, we give algorithms that given any two $n$-dimensional Gaussians $D_1,D_2$, and any error bound $\epsilon > 0$, approximate the total variation distance $D := d_{TV}(D_1,D_2)$ to $\epsilon$-relative accuracy in $\mathrm{poly}(n,\frac{1}{\epsilon},\log \frac{1}{D})$ operations. The main technical tool in our work is a reduction that helps us extend the recent progress on computing the TV-distance between \emph{discrete} random variables to our continuous setting.

Cite this Paper

BibTeX
@InProceedings{pmlr-v258-bhattacharyya25a, title = {Approximating the Total Variation Distance between Gaussians}, author = {Bhattacharyya, Arnab and Feng, Weiming and Srivastava, Piyush}, booktitle = {Proceedings of The 28th International Conference on Artificial Intelligence and Statistics}, pages = {1846--1854}, year = {2025}, editor = {Li, Yingzhen and Mandt, Stephan and Agrawal, Shipra and Khan, Emtiyaz}, volume = {258}, series = {Proceedings of Machine Learning Research}, month = {03--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v258/main/assets/bhattacharyya25a/bhattacharyya25a.pdf}, url = {https://proceedings.mlr.press/v258/bhattacharyya25a.html}, abstract = {The total variation distance is a metric of central importance in statistics and probability theory. However, somewhat surprisingly, questions about computing it \emph{algorithmically} appear not to have been systematically studied until very recently. In this paper, we contribute to this line of work by studying this question in the important special case of multivariate Gaussians. More formally, we consider the problem of approximating the total variation distance between two multivariate Gaussians to within an $\epsilon$-relative error. Previous works achieved a \emph{fixed} constant relative error approximation via closed-form formulas. In this work, we give algorithms that given any two $n$-dimensional Gaussians $D_1,D_2$, and any error bound $\epsilon > 0$, approximate the total variation distance $D := d_{TV}(D_1,D_2)$ to $\epsilon$-relative accuracy in $\mathrm{poly}(n,\frac{1}{\epsilon},\log \frac{1}{D})$ operations. The main technical tool in our work is a reduction that helps us extend the recent progress on computing the TV-distance between \emph{discrete} random variables to our continuous setting.} }
Endnote
%0 Conference Paper %T Approximating the Total Variation Distance between Gaussians %A Arnab Bhattacharyya %A Weiming Feng %A Piyush Srivastava %B Proceedings of The 28th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2025 %E Yingzhen Li %E Stephan Mandt %E Shipra Agrawal %E Emtiyaz Khan %F pmlr-v258-bhattacharyya25a %I PMLR %P 1846--1854 %U https://proceedings.mlr.press/v258/bhattacharyya25a.html %V 258 %X The total variation distance is a metric of central importance in statistics and probability theory. However, somewhat surprisingly, questions about computing it \emph{algorithmically} appear not to have been systematically studied until very recently. In this paper, we contribute to this line of work by studying this question in the important special case of multivariate Gaussians. More formally, we consider the problem of approximating the total variation distance between two multivariate Gaussians to within an $\epsilon$-relative error. Previous works achieved a \emph{fixed} constant relative error approximation via closed-form formulas. In this work, we give algorithms that given any two $n$-dimensional Gaussians $D_1,D_2$, and any error bound $\epsilon > 0$, approximate the total variation distance $D := d_{TV}(D_1,D_2)$ to $\epsilon$-relative accuracy in $\mathrm{poly}(n,\frac{1}{\epsilon},\log \frac{1}{D})$ operations. The main technical tool in our work is a reduction that helps us extend the recent progress on computing the TV-distance between \emph{discrete} random variables to our continuous setting.
APA
Bhattacharyya, A., Feng, W. & Srivastava, P.. (2025). Approximating the Total Variation Distance between Gaussians. Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 258:1846-1854 Available from https://proceedings.mlr.press/v258/bhattacharyya25a.html.

Related Material