CS Paper Radar

Optimal Support Size Testing

Qisheng Wang

cs.IT cs.DSmath.ST ·submitted 2026-10-13 17:03 UTC · v1
theory

Abstract

We present an optimal tester for support size that determines whether an unknown probability distribution is supported on $n$ elements or $\varepsilon$-far away (in total variation distance) with sample complexity $Θ(\frac{n}{\varepsilon\log(n)})$, improving the prior best $O(\frac{n}{\varepsilon\log(n)} \log(\min\{\frac{1}{\varepsilon}, n\}))$ due to Ferreira Pinto Jr. and Harms (STOC 2025). As a generalization, we provide a pretty good lower bound on support size.

Comment
12 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Tight Bounds for Equivalence Testing with Non-Adaptive Conditional Samples

cs.DS cs.ITstat.ML ·2026-10-08 ·Gautam Kamath
theory similarity 0.64
Abstract

We study distribution testing with access to non-adaptive conditional samples. Specifically, we give tight bounds for equivalence testing, determining whether two unknown distributions are equal to or $\varepsilon$-far from each other in total variation distance. Our algorithm and lower bound show that $\tilde Θ\left(\frac{\log n}{\varepsilon^2}\right)$ queries are necessary and sufficient for this problem. These results demonstrate that the complexity of uniformity, identity, and equivalence testing with non-adaptive conditional samples are all $\tilde Θ(\log n)$.

0.20

A Tight Scale-Locality Bound for Partial Detection in Non-Adaptive Group Testing

cs.DS ·2026-08-12 ·Nader H. Bshouty
publishedtheory similarity 0.59
Abstract

We give a lower bound for randomized non-adaptive group testing when the goal is to find any $\ell$ defective items but the total number $d$ of defectives is unknown. Bshouty and Haddad-Zaknoon proved an upper bound of $O(\ell\log^2 n)$ tests and a lower bound of $$Ω\!\left(\frac{\ell\log^2 n}{\log \ell+\log\log n}\right).$$ We prove the matching lower bound. More generally, we show that every randomized non-adaptive algorithm that succeeds with constant probability for every defective set must use $$Ω\!\left(\ell\log^2(n/\ell)\right)$$ tests. The proof is as follows. At a fixed value of $d$, finding $\ell$ defectives requires about $\ell\log(n/d)$ bits of information. On the other hand, one fixed group test is informative only when its size is tuned to the scale of $d$; across all logarithmic scales of $d$, a single test contributes only $O(1)$ bits. Summing over all scales gives the lower bound. We also record the matching upper bound $$O\!\left(\ell\log^2(n/\ell)\right),$$ obtained by running the known-$d$ algorithm in parallel over dyadic guesses for $d$. Thus the randomized non-adaptive complexity of unknown-$d$ partial detection is $Θ\!\left(\ell\log^2(n/\ell)\right)$ for constant success probability.

0.22

Hypothesis Selection via Weighted Medians

cs.DS cs.LG ·2026-10-14 ·Liang-Yu Zou
similarity 0.58
Abstract · fix some typos

Given $n$ distributions (hypotheses) $\mathcal H=\{H_1,\ldots,H_n\}$ and samples from an unknown target distribution $P$, proper hypothesis selection seeks a distribution whose total variation distance to $P$ is close to the best achievable within the known distributions. We give an algorithm that, using $O(\varepsilon^{-2}\log(n/δ))$ target samples, running in $O(n\varepsilon^{-2}\log(n/δ))$ time, with probability at least $1-δ$, returns $H_{\hat i}$ satisfying $d_\mathrm{TV}(P,H_{\hat i})\leq 3\min_{i\in[n]}d_\mathrm{TV}(P,H_i)+\varepsilon.$ The algorithm achieves the optimal approximation factor and sample complexity. The running time improves the dependence on the failure probability from polynomial to logarithmic in the state-of-the-art bound $\tilde{O}(n\varepsilon^{-2}δ^{-1})$ of Aamand, Aliakbarpour, Chen, and Silwal (COLT 2026), thereby answering their Question~2.

0.33

Distributionally Robust Search: The Power of Information and the Limits of Moments

cs.DS cs.DM ·2026-11-03 ·Nicole Megow, Cliff Stein, Jose Verschae
theory similarity 0.58
Abstract · 43 pages, 5 figures

We study binary search for a target drawn from a distribution on $n$ ordered elements. The cost is the expected number of comparison queries. In our distributionally robust framework, the algorithm knows only an uncertainty set containing the distribution and minimizes its worst-case approximation ratio against an optimal strategy that knows the distribution. Collections of uncertainty sets capture different forms of information: quantiles, moments, general linear measurements, or approximate CDFs. This framework quantifies how much and what form of information is needed for near-optimal search. Our main result separates moments from general linear measurements. Although $n-1$ moments determine the distribution exactly, for every constant $δ\in(0,1)$, the first $n^{1-δ}$ exact moments can be as uninformative for search as no information: the worst-case approximation ratio remains $Ω(\log n)$. In contrast, for every constant $\varepsilon\in(0,1)$, $O(n^\varepsilon\log^4 n)$ suitably chosen linear measurements suffice for an $O(1/\varepsilon)$-approximation. The limitation lies in the measurements chosen, rather than linearity itself. Using LP duality and polynomial bounds of Rakhmanov and Bernstein, we construct distributions with identical moments and mass concentrated at different positions. For the upper bound, we combine dyadic sketches and Johnson--Lindenstrauss embeddings with a truncated median-search algorithm that converts uniform CDF approximation into search guarantees. Measuring information in bits, we prove a lower bound of $Ω(1/\varepsilon)$ on the approximation ratio for summaries of any form using at most $\frac12 n^\varepsilon\log n$ bits, for every sufficiently small constant $\varepsilon>0$. Quantiles match this within constant factors. For Kolmogorov balls of radius $n^{-\varepsilon}$ the optimal approximation ratio is $Θ(1/\varepsilon)$.

0.19

Derandomized Sunflowers and Radical Lower Bounds

cs.CC math.CO ·2026-11-17 ·Bruno Cavalar, Théo Borém Fabris, Partha Mukhopadhyay, Srikanth Srinivasan, Amir Yehudayoff
publishedtheory similarity 0.58
Abstract · Full version of FOCS 2026 paper

Robust Sunflower lemmas imply that any large enough monotone DNF of width $w$ contains a sunflower, i.e., a DNF equivalent to the conjunction of a common core with a DNF that is heavily biased towards $1$. While these lemmas are typically proved in the context of the uniform distribution or i.i.d. distributions, they also hold for $O(w^2)$-wise independent distributions by Bazzi's theorem (Bazzi (SICOMP 2009); Tal (CCC 2017)), which states that width-$w$ DNFs cannot distinguish between such distributions and the uniform distribution. We prove a derandomization of robust sunflower lemmas for $O(w)$-wise independent distributions, which recovers the derandomization above with slightly weaker parameters. Notably, our result also holds for distributions whose marginals are "locally independent" and "approximately identically" distributed. It is not known whether such distributions fool general DNFs, which makes the derandomization via DNF-fooling techniques unavailable. Our proof of this derandomization is via the method of moments, which might be of independent interest. We apply this result to obtain improved separations between non-monotone arithmetic circuits and the radical of monotone circuits. Specifically, we construct an explicit family of multilinear polynomials $P_n$ that have small non-monotone arithmetic circuits such that any power of $P_n$ cannot be computed by monotone arithmetic circuits of sub-exponential size. This improves on a recent result of Cavalar, Fabris, Mukhopadhyay, Srinivasan and Yehudayoff (STOC 2026), who proved a non-explicit separation that was quasipolynomial. Our construction uses Nisan-Wigderson designs with an additional linear-algebraic expansion property.

0.55

Asymmetric Likelihood-Free Hypothesis Testing

cs.LG cs.DScs.ITmath.ST+1 ·2026-10-21 ·Gunjan Kumar, Yash Pote, Jonathan Scarlett
similarity 0.57
Abstract

In likelihood-free hypothesis testing (LFHT), given samples from two unknown distributions $P,Q$ on $[n]$ with $\mathrm{d_{TV}}(P,Q)\geq\varepsilon$, and from a third distribution $D\in\{P,Q\}$, the goal is to identify whether $D=P$ or $D=Q$. We study asymmetric likelihood-free hypothesis testing, where the sample budgets $s_P$ and $s_Q$ for $P$ and $Q$ may differ, and characterize the feasible triples $(s_P,s_Q,s_D)$ up to logarithmic factors. We establish that unequal reference budgets can give a polynomial saving. For instance, for constant separation, $n$ samples from $P$ and $n^{3/4}$ from $Q$ allow testing with $\widetilde O(n^{1/4})$ samples from $D$, whereas both existing baselines---symmetric LFHT and unequal-sample closeness testing---require $Ω(\sqrt n)$ samples from $D$. We further apply our results to non-adaptive distribution 2-clustering, where the sample allocation among $k$ distributions must be fixed before observing any data. We obtain matching upper and lower bounds for this problem up to logarithmic factors in terms of the domain size, number of distributions, smaller cluster size, and separation, both with one cluster distribution known and with both unknown. Comparing with known bounds for adaptive sample allocation gives a worst-case adaptivity gap of $\widetildeΘ(k^{1/4})$.

0.25

Sparse Priors for Efficient Distribution Learning

cs.LG math.ST ·2026-09-16 ·Saumya Goyal, Barnabás Póczos
theory similarity 0.56
Abstract

Despite the widespread use and success of generative AI techniques today, theoretical guarantees on learning a distribution supported in $d$ dimensions from $n$ samples degrade as $O(n^{-1/Θ(d)})$, though shown to be minimax optimal. We hypothesize that present bounds are too pessimistic because smoothness assumptions are not enough to capture the structure of distributions that often appear in real applications. Consequently, we introduce the class of sparse priors and define the "Sparse Dimension" as a measure of sparsity of a prior over the space of all distributions. We show that distribution learning under a $k$-sparse prior achieves a Bayesian risk lower bound of $Ω(\sqrt{k/n})$ under common distance metrics, and show a matching (up to logarithmic terms asymptotically in $n,k$) upper bound for the TV distance under mild additional assumptions. We show the statistical equivalence of distribution learning and learning to sample in the Bayesian setting so that our results apply to learning to sample as well. While $k$ can still depend on the dimension $d$, or a notion of intrinsic dimension, our results show that learning under an appropriate prior overcomes the curse of dimensionality with respect to the dependence on $n$.

0.33

Log-optimal two-sample testing by betting

cs.IT math.STstat.MEstat.ML ·2026-11-14 ·Aaditya Ramdas
similarity 0.55
Abstract · 55pgs

For each standard Borel observation space, we construct a single anytime-valid two-sample procedure that is asymptotically log-optimal for every pair of unknown probability laws and every limiting ratio of diverging sample sizes, including zero and infinity. For independent balanced pairs, the optimal log-wealth rate is $2\JS(P,Q)$, where $\JS$ is the Jensen--Shannon divergence. Unequal sizes yield weighted Jensen--Shannon information and the one-sample limit $\log W(n_1,n_2)/n_2\to\KL(Q\|P)$ when $n_1/n_2\to\infty$. Refining finite partitions and logarithmic-loss learning with measurable characteristic kernels provide universal constructions. Our main contribution is the generality of our construction, and its connections to classical batch efficiency notions. Practical implementations allow continuous classifier fine-tuning, as demonstrated on finite alphabets, Gaussian data, and handwritten digits.

0.17