mlsanityData to 7 Oct 2026

Complexity of High-Dimensional Identity Testing with Coordinate Conditional Sampling

arXiv 2207.09102 ↗First posted 19 Jul 2022cs.DS cs.LG math.PRcited by 4

Not on the map. Why?

Abstract (arXiv)

We study the identity testing problem for high-dimensional distributions. Given as input an explicit distribution μ, an varepsilon>0, and access to sampling oracle(s) for a hidden distribution π, the goal in identity testing is to distinguish whether the two distributions μ and π are identical or are at least varepsilon-far apart. When there is only access to full samples from the hidden distribution π, it is known that exponentially many samples (in the dimension) may be needed for identity testing, and hence previous works have studied identity testing with additional access to various "conditional" sampling oracles. We consider a significantly weaker conditional sampling oracle, which we call the mathsfCoordinate Oracle, and provide a computational and statistical characterization of the identity testing problem in this new model. We prove that if an analytic property known as approximate tensorization of entropy holds for an n-dimensional visible distribution μ, then there is an efficient identity testing algorithm for any hidden distribution π using tildeO(n/varepsilon) queries to the mathsfCoordinate Oracle. Approximate tensorization of entropy is a pertinent condition as recent works have established it for a large class of high-dimensional distributions. We also prove a computational phase transition: for a well-studied class of n-dimensional distributions, specifically sparse antiferromagnetic Ising models over +1,-1n, we show that in the regime where approximate tensorization of entropy fails, there is no efficient identity testing algorithm unless mathsfRP=mathsfNP. We complement our results with a matching Omega(n/varepsilon) statistical lower bound for the sample complexity of identity testing in the mathsfCoordinate Oracle model.

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Builds on 28 of its 71 references that are in the map. First posted on arXiv 19 Jul 2022.

Builds on

28 of 71 references.

References · 28

  1. 2017Learning Graphical Models Using Multiplicative Weightscited by 43
  2. 2013Optimal Algorithms for Testing Closeness of Discrete Distributionscited by 37
  3. 2015Optimal Testing for Properties of Distributionscited by 36
  4. 2016Testing Ising Modelscited by 23
  5. 2016Testing Bayesian Networkscited by 23
  6. 2020Optimal Testing of Discrete Distributions with High Probabilitycited by 15
  7. 2017Which Distribution Distances are Sublinearly Testable?cited by 14
  8. 2019Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioningcited by 13
  9. 2020Learning and Testing Junta Distributions with Subcube Conditioningcited by 13
  10. 2016Square Hellinger Subadditivity for Bayesian Networks and its Applications to Identity Testingcited by 11
  11. 2020Optimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional Expansioncited by 11
  12. 2022Sampling Approximately Low-Rank Ising Models: MCMC meets Variational Methodscited by 9
16 more
  1. 2021On Mixing of Markov Chains: Coupling, Spectral Independence, and Entropy Factorizationcited by 8
  2. 2015Faster Algorithms for Testing under Conditional Samplingcited by 7
  3. 2019Lower bounds for testing graphical models: colorings and antiferromagnetic Ising modelscited by 6
  4. 2020Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Modelcited by 5
  5. 2022Independence Testing for Bounded Degree Bayesian Networkcited by 5
  6. 2020Rapid Mixing of Glauber Dynamics up to Uniqueness via Contractioncited by 4
  7. 2020Rapid Mixing for Colorings via Spectral Independencecited by 4
  8. 2020On Distribution Testing in the Conditional Sampling Modelcited by 4
  9. 2020Testing Product Distributions: A Closer Lookcited by 4
  10. 2020Hardness of Identity Testing for Restricted Boltzmann Machines and Potts modelscited by 3
  11. 2022From algorithms to connectivity and back: finding a giant component in random k-SATcited by 3
  12. 2020Rapid mixing from spectral independence beyond the Boolean domaincited by 2
  13. 2021Spectral Independence via Stability and Applications to Holant-Type Problemscited by 2
  14. 2022Fast sampling of satisfying assignments from random k-SAT with applications to connectivitycited by 2
  15. 2021From Coupling to Spectral Independence and Blackbox Comparison with the Down-Up Walkcited by 1
  16. 2022Optimal Closeness Testing of Discrete Distributions Made (Complex) Simplecited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 3; 2026: 1.

4 papers.

  1. 2025Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioningcited by 2
  2. 2025Sampling and Identity-Testing Without Approximate Tensorization of Entropycited by 1
  3. 2025On approximating the f-divergence between two Ising modelscited by 0
  4. 2026Testing Distributions Against Bounded Distinguisherscited by 0