PreprintarXiv licencearXiv
Optimal Support Size Testing
Abstract
We present an optimal tester for support size that determines whether an unknown probability distribution is supported on n elements or ε-far away (in total variation distance) with sample complexity Θ(n/εlog(n)), improving the prior best O(n/εlog(n) log(min{1/ε, n})) due to Ferreira Pinto Jr. and Harms (STOC 2025). As a generalization, we provide a pretty good lower bound on support size.
Related
- Uniform Discrete Diffusion Models are Minimax Optimal for Estimating Distributions with Small Effective Support Size
- Optimal square size for separating the operator and completely bounded norms of Schur multipliers on S^4
- PDE-Based Bounds on Optimal Exponents in Active Simple Hypothesis Testing
- Asymptotic Properties of Support Vector Machines in High-Dimension, Low-Sample-Size Settings under a Spiked Model
- Optimal Control of Traveler Testing in Epidemic Models
BibTeX
@misc{wang2026optimal,
title = {{Optimal Support Size Testing}},
author = {Qisheng Wang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.18723},
eprint = {2610.18723},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.18723},
}
RIS
TY - UNPB
TI - Optimal Support Size Testing
AU - Qisheng Wang
PY - 2026
DA - 2026/10/13
PB - arXiv
DO - 10.48550/arxiv.2610.18723
UR - https://arxiv.org/abs/2610.18723
AB - We present an optimal tester for support size that determines whether an unknown probability distribution is supported on n elements or ε-far away (in total variation distance) with sample complexity Θ(n/εlog(n)), improving the prior best O(n/εlog(n) log(min{1/ε, n})) due to Ferreira Pinto Jr. and Harms (STOC 2025). As a generalization, we provide a pretty good lower bound on support size.
ER -