Efficient Distance Approximation for Structured High-Dimensional Distributions via Learning
Authors: Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S Meel, N. V. Vinodchandran
NeurIPS 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We design efficient distance approximation algorithms for several classes of wellstudied structured high-dimensional distributions. Specifically, we present algorithms for the following problems (where d TV is the total variation distance): [...] All our algorithms are based on a common framework. To approximate the distance between P D1 and Q D2, we first learn the model parameters for P D1 and Q D2 that are guaranteed to be close to P and Q respectively. It remains to compute d TV(P, Q). This is a computationally hard problem in general, but we use the fact that for D1, D2 of interest, we can efficiently approximate the mass functions for P and Q from their parameters. At this point, we invoke an estimator that approximates d TV(P, Q) using samples from P and the approximate mass functions for P and Q. |
| Researcher Affiliation | Academia | Arnab Bhattacharyya National University of Singapore arnabb@nus.edu.sg Sutanu Gayen National University of Singapore sutanugayen@gmail.com Kuldeep S. Meel National University of Singapore meel@comp.nus.edu.sg N. V. Vinodchandran University of Nebraska-Lincoln vinod@cse.unl.edu |
| Pseudocode | Yes | Algorithm 1: Distance approximation between P and Q |
| Open Source Code | No | The paper does not provide any links to source code or explicitly state that source code for their methodology is made available. |
| Open Datasets | No | The paper is theoretical, presenting algorithms and analyses for different distribution types. It does not describe experiments using specific datasets, thus no information on public dataset availability is provided. |
| Dataset Splits | No | The paper is theoretical and does not describe experiments with datasets, thus no information on training/validation/test splits is provided. |
| Hardware Specification | No | The paper is theoretical and does not describe experimental setups, thus no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not describe experimental implementations with specific software dependencies and versions. |
| Experiment Setup | No | The paper is theoretical and focuses on algorithm design and analysis, not on concrete experimental setups or hyperparameter details. |