Uniformity Testing over Hypergrids with Subcube Conditioning

2023/02/17 by Xi Chen, Chen, Xi, Cassandra Marcussen +1 · 1 citation
Computer Science · #Adversarial Robustness in Machine Learning #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Machine Learning (cs.LG) #Machine Learning and Algorithms #Probability (math.PR) #Statistics Theory (math.ST)

paper · pdf · doi:10.48550/arxiv.2302.09013

openalex publication_date 2023/02/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We give an algorithm for testing uniformity of distributions supported on hypergrids [m₁] × ⋯ × [m_n], which makes \smash\widetildeO(poly(m)√(n)/ε²) many queries to a subcube conditional sampling oracle with m=max_i m_i. When m is a constant, our algorithm is nearly optimal and strengthens the algorithm of [CCK+21] which has the same query complexity but works for hypercubes \± 1\ⁿ only. A key technical contribution behind the analysis of our algorithm is a proof of a robust version of Pisier's inequality for functions over hypergrids using Fourier analysis.

Cited by

• Tight simulation of a distribution using conditional samples

Related

• Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning
• Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning
• A o(d) ⋅ polylog~n Monotonicity Tester for Boolean Functions over the Hypergrid [n]^d
• Faster Sublinear Algorithms using Conditional Sampling
• Optimal bounds for monotonicity and Lipschitz testing over hypercubes and hypergrids