Source-linked AI summary
On combinatorial testing problems
Louigi Addario-Berry, Nicolas Broutin, Luc Devroye, Gábor Lugosi
TL;DR
The paper asks when a Gaussian vector with a contaminated subset of coordinates can be distinguished from a standard normal vector. It derives general testability and impossibility conditions tied to the set class’s structure, and shows that optimal risk can fail to be monotone as the class grows.
Problem
The paper seeks the signal level μ at which testing a standard Gaussian vector against a shifted subset becomes possible, as a function of n, K, and the set class.
Source: §1 · pp. 1–2Method
The paper develops general sufficient conditions for testability and impossibility based on the combinatorial and geometric structure of the set class.
Source: §1 · p. 3Results
The optimal risk is not necessarily monotone with class size, although monotonicity holds under certain symmetry conditions.
Source: Plan of the paper · p. 4Takeaways & Limitations
For some nested classes, the optimal risks can be arbitrarily close to 1 and 0 at the same μ, so class structure matters to testing difficulty.
Source: §5 · p. 19The paper focuses on orders of magnitude rather than sharp constants, and polynomial-time near-optimal tests for larger k remain of interest.
Source: §4.1 · p. 12, §4.6 · p. 16
Abstract
from arXiv · showhide
We study a class of hypothesis testing problems in which, upon observing the realization of an $n$-dimensional Gaussian vector, one has to decide whether the vector was drawn from a standard normal distribution or, alternatively, whether there is a subset of the components belonging to a certain given class of sets whose elements have been ``contaminated,'' that is, have a mean different from zero. We establish some general conditions under which testing is possible and others under which testing is hopeless with a small risk. The combinatorial and geometric structure of the class of sets is shown to play a crucial role. The bounds are illustrated on various examples.
1. Introduction.
The paper studies testing whether an i.i.d. standard Gaussian vector instead contains a uniformly selected set of coordinates shifted to mean μ. It develops conditions for when testing is possible or hopeless, with thresholds depending on the combinatorial and geometric structure of the set class.
1. Introduction.
- The null is an i.i.d. standard normal vector, while under the alternative the coordinates in some set S∈C have mean μ.The sets have common size K, and the risk treats the alternative set as selected uniformly at random.Source: §1 · pp. 1–2
- The central goal is to estimate the critical μ at which the optimal test’s risk becomes small, as a function of n, K, and C’s structure.The paper describes general conditions for testability and impossibility and illustrates them with examples.Source: §1 · pp. 2–3
- For sets of very different sizes, the common-size assumption may change the picture because large sets are easier to detect and small sets can be ignored.The arguments extend without essential changes when set sizes are approximately equal.Source: §1 · p. 4
- The optimal risk need not decrease when the set class grows; under sufficient symmetry, however, monotonicity holds for subclasses.The paper reports that some nested classes can have risks arbitrarily close to 1 and 0 at the same μ.Source: Plan of the paper · p. 4
2. Simple tests and upper bounds.
The section presents averaging and maximum-based tests as simple alternatives to the optimal test. Their risk bounds reduce sufficient conditions for testability to properties of the signal and, for the maximum test, the expected maximum over the class.
2. Simple tests and upper bounds.
- The optimal test can be difficult to analyze or compute, while the simpler tests are often easier to analyze and can be near-optimal.The maximum test is not always computable in polynomial time.Source: §2 · p. 5, A test based on maxima · p. 6
- The averaging test uses the sum of coordinates, whose mean shifts from 0 to μK while its variance remains n; its risk is at most 2e^{-(μK)^2/(8n)}.The test compares the sum with μK/2.Source: A simple test based on averaging · p. 5
- The maximum test has low risk when μ is at least E0 max_{S∈C} X_S/K plus a constant over √K.Bounding the expected maximum helps identify sufficient conditions for testability.Source: A test based on maxima · pp. 6–7
- The expected maximum under the null can be bounded using Gaussian-process methods, including chaining bounds based on covering numbers of C.The section also notes that covering numbers can be bounded using the VC dimension.Source: A test based on maxima · p. 7
3. Lower bounds.
The section derives impossibility bounds from overlap properties of randomly selected sets, then sharpens them under symmetry and negative association. These bounds relate the class’s combinatorial geometry to the signal level needed for testing.
3. Lower bounds.
- Regardless of C, detection is hopeless when μ is of order K^-1/2.This universal lower bound applies without assumptions on the class.Source: §3 · p. 8, A universal lower bound · p. 8
- Bounds on the moment generating function of the overlap between two independent uniform sets in C yield lower bounds on the critical μ.This reduces the problem to a combinatorial quantity.Source: A lower bound based on overlapping pairs · p. 9
- Under symmetry conditions, the universal lower bound can improve by a factor of √log(1+n/K).The conditions include uniform conditional overlap distributions and inclusion probability K/n for each coordinate.Source: A lower bound for symmetric classes · pp. 9–10
- For many sufficiently small symmetric classes, the symmetric lower bound is close to optimal.The cited result considers classes with at most n^α elements.Source: A lower bound for symmetric classes · p. 10
- Negative association among membership indicators permits an improved lower bound for symmetric classes.The section notes this condition holds in several examples.Source: Negative association · p. 11
4. Examples.
The examples show how the critical signal level depends on the size and structure of the candidate-set class, with upper and lower bounds illustrated across several graph families. Their analyses also connect testing thresholds to overlap behavior and computational considerations.
4.1. Disjoint sets.
- For disjoint sets, the critical transition is of order √((1/K)log N), with the lower-bound calculation using overlap K with probability 1/N and zero otherwise.The paper notes that the leading constant in the lower bound is suboptimal and focuses on orders of magnitude.Source: §4.1 · p. 12
4.2. K-sets.
- For K-sets, the threshold is of order √log n when K = O(n^(1−ε)/2), and of order √(n/K²) when K²/n is bounded away from zero.The simple bound has the correct order in both regimes.Source: §4.2 · p. 13
4.3. Perfect matchings.
- For perfect matchings, the averaging test gives a sufficient condition for small risk, while symmetry and negative association support a corresponding lower bound.The overlap count has the distribution of the number of fixed points in a random permutation.Source: §4.3 · p. 13
4.4. Stars.
- A corrupted node in a pairwise-interaction network is modeled by a star, the set of all m−1 edges incident to one fixed vertex.The class comprises all stars in the complete graph.Source: §4.4 · p. 14
4.5. Spanning trees.
- For the complete graph, there are m^(m−2) spanning trees, each with m−1 edges; the averaging test is close to optimal despite the class lacking symmetry.The overlap indicators for a uniform random spanning tree are negatively associated.Source: §4.5 · pp. 14–16
4.6. Cliques.
- For cliques with k at most of order √m, the critical µ is of order (1/k)log(m/k); efficient near-optimal tests for larger k remain an open interest.The paper relates computational difficulty in this normal setting to the hidden-clique problem.Source: §4.6 · pp. 16–17
- The biclique variant has analogous analysis and bounds, while negative association fails for cliques and the biclique details are omitted.The paper notes that clique computation is more complex and discusses the connection to hidden-clique detection.Source: §4.6 · pp. 16, 19
5. On the monotonicity of the risk.
The section shows that optimal risk need not worsen when the candidate class grows: some nested classes have sharply reversed risks, while symmetry restores monotonicity. The same example also yields nonmonotonicity of the Bhattacharyya affinity.
5. On the monotonicity of the risk.
- For every ε in (0,1), nested classes can have optimal risks arbitrarily close to 1 for the smaller class and 0 for the larger class at the same µ.Thus, optimal risk is not generally monotone under class inclusion.Source: §5 · pp. 19–20
- When the larger class is symmetric, the optimal risk of any subclass is no smaller than that of the full class for every µ.The paper lists K-sets, stars, perfect matchings, and cliques as symmetric examples, but not spanning trees.Source: §5 · p. 19
- The same constructed example also gives nonmonotonicity of the Bhattacharyya affinity.The authors state that the example establishes this for sufficiently large n.Source: §5 · p. 21
6. Lower bounds on based random subclasses and metric entropy.
The section derives lower bounds on optimal risk from geometric features of the set class, including the separation of randomly sampled subclasses. For symmetric classes, packing numbers yield a direct alternative, and examples illustrate both approaches.
Random subclasses
- Theorem 6.1 lower-bounds optimal risk using t_C(M), the median minimum distance among M uniformly sampled elements of C.The bounds relate risk to geometric features of the class.Source: §6 · p. 22
- The median of the largest pairwise overlap in a sampled subclass captures finer class geometry than the pair-overlap moment generating function.The section notes that bounds on the moment generating function can also be combined with Theorem 6.1 using a union bound.Source: §6 · p. 22
Sub-squares of a grid
- log(n/(512K))/(2K) is the reported lower-bound scale for sub-squares of a grid, and the bound is of optimal order.The example uses a random-subclass size for which t_C(M)^2 = 2K.Source: §6 · pp. 22–23
Stars
- For stars, allowing overlap can still yield a better bound: choosing M = N = m gives K − t_C(M)^2/2 = 1.The theorem then implies a bound involving (1/K)log(m/16).Source: §6 · p. 23
Improvement by thinning
- Thinning a sampled subclass can increase t_C(M); when the increase is substantial, the resulting gain may also be substantial.The proof can use the thinned parameter after adjusting constants.Source: §6 · pp. 26–27
Symmetric classes and packing numbers
- For symmetric classes, a maximally sized t-separated subset lets the lower bounds use packing numbers instead of random subclasses.Packing and covering numbers satisfy N(t) ≤ M(t) ≤ N(t/2).Source: §6 · p. 27
- R* ≥ 1/2 whenever µ ≤ c√((V/K)log(n/K)) for classes with packing numbers M(t) ∼ (n/t²)^V.The bound closely matches the maximum-test bound obtained using Dudley’s chaining bound.Source: §6 · p. 28
7. Optimal versus maximum test: An analysis of the type I error.
The section bounds the type I error of the optimal test using the expected maximum of a Gaussian process over a sparse subset of C. This can be tighter than the maximum-test bound, but there is no analogous type II error bound in the supplied analysis.
Scope
- The analysis provides no analogous upper bound for the optimal test’s type II error.The authors say a similar type II analysis would be needed to verify their conjecture about cases where the maximum test is far from optimal.Source: §7 · pp. 28–29
Type I error bound
- The optimal test’s type I bound replaces the expected maximum over C with the expected maximum over a potentially much smaller subset A.The bound is sharp up to a constant factor by Sudakov’s minoration.Source: §7 · pp. 28–30
- A minimal t-cover of C supplies a finite subset A used to bound the Gaussian maximum in the type I analysis.The proof bounds the deviation between each set and its nearest cover element using their Hamming distance.Source: §7 · p. 30