Total Variation Distance Meets Probabilistic Inference
Authors: Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel, Dimitrios Myrisiotis, A. Pavan, N. V. Vinodchandran
ICML 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we establish a novel connection between total variation (TV) distance estimation and probabilistic inference. In particular, we present an efficient, structure-preserving reduction from relative approximation of TV distance to probabilistic inference over directed graphical models. This reduction leads to a fully polynomial randomized approximation scheme (FPRAS) for estimating TV distances between same-structure distributions over any class of Bayes nets for which there is an efficient probabilistic inference algorithm. In particular, it leads to an FPRAS for estimating TV distances between distributions that are defined over a common Bayes net of small treewidth. Prior to this work, such approximation schemes only existed for estimating TV distances between product distributions. Our approach employs a new notion of partial couplings of highdimensional distributions, which might be of independent interest. |
| Researcher Affiliation | Academia | 1School of Computing, National University of Singapore, Singapore 2Department of Computer Science and Engineering, Indian Institute of Technology Kanpur, India 3Department of Computer Science, University of Toronto, Canada 4CNRS@CREATE LTD., Singapore 5Department of Computer Science, Iowa State University, USA 6School of Computing, University of Nebraska Lincoln, USA. |
| Pseudocode | Yes | Algorithm 1 FPRAS for d TV estimation using a probabilistic inference oracle. |
| Open Source Code | No | The paper does not contain any statements about releasing source code, nor does it provide links to a code repository. |
| Open Datasets | No | This is a theoretical paper focusing on mathematical reductions and approximation schemes; it does not involve empirical training on datasets. |
| Dataset Splits | No | This is a theoretical paper and does not discuss validation splits or methods for empirical data. |
| Hardware Specification | No | This is a theoretical paper and does not mention any hardware specifications used for experiments. |
| Software Dependencies | No | This is a theoretical paper and does not mention specific software dependencies with version numbers for empirical reproduction. |
| Experiment Setup | No | This is a theoretical paper and does not describe any empirical experiment setup details such as hyperparameters or training configurations. |