Efficient Distance Approximation for Structured High-Dimensional Distributions via Learning


We design efficient distance approximation algorithms for several classes of structured high-dimensional distributions. Specifically, we show algorithms for the following problems:

Our results are the first efficient distance approximation algorithms for these well-studied problems. They are derived using a simple and general connection to distribution learning algorithms. The distance approximation algorithms imply new efficient algorithms for $tolerant$ testing of closeness of the above-mentioned structured high-dimensional distributions.

In Advances in Neural Information Processing Systems (NeurIPS)