# Testing Support Size More Efficiently Than Learning Histograms

arXiv: https://arxiv.org/abs/2410.18915 · HTML: https://mlsanity.com/paper/2410.18915/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 40 references that are in the map.
- First posted on arXiv 24 Oct 2024.

## Builds on (most cited first, 12 of 12)

- [The Optimal Sample Complexity of PAC Learning](https://mlsanity.com/paper/1507.00473/) (2015)
- [The Broad Optimality of Profile Maximum Likelihood](https://mlsanity.com/paper/1906.03794/) (2019)
- [VC Dimension and Distribution-Free Sample-Based Testing](https://mlsanity.com/paper/2012.03923/) (2020)
- [Local moment matching: A unified methodology for symmetric functional estimation and distribution estimation under Wasserstein distance](https://mlsanity.com/paper/1802.08405/) (2018)
- [Unified Sample-Optimal Property Estimation in Near-Linear Time](https://mlsanity.com/paper/1911.03105/) (2019)
- [Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism](https://mlsanity.com/paper/1607.03938/) (2016)
- [Estimating the Effective Support Size in Constant Query Complexity](https://mlsanity.com/paper/2211.11344/) (2022)
- [Testing Distributions of Huge Objects](https://mlsanity.com/paper/2212.12802/) (2022)
- [Testing Bipartitness in an Augmented VDF Bounded-Degree Graph Model](https://mlsanity.com/paper/1905.03070/) (2019)
- [Distribution Testing Under the Parity Trace](https://mlsanity.com/paper/2304.01374/) (2023)
- [Refining the Adaptivity Notion in the Huge Object Model](https://mlsanity.com/paper/2306.16129/) (2023)
- [Support Testing in the Huge Object Model](https://mlsanity.com/paper/2308.15988/) (2023)

## Abstract (arXiv)

Consider two problems about an unknown probability distribution p: 1. How many samples from p are required to test if p is supported on n elements or not? Specifically, given samples from p, determine whether it is supported on at most n elements, or it is "ε-far" (in total variation distance) from being supported on n elements. 2. Given m samples from p, what is the largest lower bound on its support size that we can produce? The best known upper bound for problem (1) uses a general algorithm for learning the histogram of the distribution p, which requires Theta(tfracnε2 log n) samples. We show that testing can be done more efficiently than learning the histogram, using only O(tfracnε log n log(1/ε)) samples, nearly matching the best known lower bound of Omega(tfracnε log n). This algorithm also provides a better solution to problem (2), producing larger lower bounds on support size than what follows from previous work. The proof relies on an analysis of Chebyshev polynomial approximations outside the range where they are designed to be good approximations, and the paper is intended as an accessible self-contained exposition of the Chebyshev polynomial method.