Uniformity Testing over Hypergrids with Subcube Conditioning

Xi Chen, Cassandra Marcussen
2/17/2023
cs.DScs.ITcs.LG

No confident code implementation found for this paper.

Abstract

We give an algorithm for testing uniformity of distributions supported on hypergrids $[m_1] \times \cdots \times [m_n]$, which makes $\smash{\widetilde{O}(\text{poly}(m)\sqrt{n}/ε^2)}$ 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 $\{\pm 1\}^n$ 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.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning

83% match2025

Replicable Uniformity Testing

81% match2026

On Scalable Testing of Samplers

79% match1 repo142026

A Variance-Based Analysis of Sample Complexity for Grid Coverage

79% match2025

Instance-Optimal Uniformity Testing and Tracking

77% match2025

Statistical-Computational Trade-offs for Density Estimation

76% match2026

Cite this paper

@article{chen2023uniformity,
  title  = {Uniformity Testing over Hypergrids with Subcube Conditioning},
  author = {Xi Chen and Cassandra Marcussen},
  year   = {2023},
  eprint = {2302.09013},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2302.09013v2}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2302.09013.svg)](https://codeofpaper.com/paper/2302.09013)

Discussion