[0908.3437] On combinatorial testing problems

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.

View PDF HTML (experimental) Abstract: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…

saved by

• Anna Brandenberger

related reading

• Observed Universality of Phase Transitions in High-Dimensional Geometry, with Implications for Modern Data Analysis and Signal Processingarxiv.org
• [2608.00140] Discrepancy Theory: An Algorithmic and Geometric Perspectivearxiv.org
• notes.pdfjingbol.web.illinois.edu
• [2605.01172] A Theory of Generalization in Deep Learningarxiv.org
• nullstellensatzweb.math.princeton.edu
• [2608.27540] Towards a mathematical theory of superpositionarxiv.org
• An optimization perspective on log-concave sampling and beyond | Sinho Chewichewisinho.github.io
• Geometry of random sections of isotropic convex bodiesarxiv.org
• [2408.05807] Kernel Density Estimators in Large Dimensionsarxiv.org
• rakhlin_mathstat_sp24.pdfmit.edu
• 1404.5236 Sum-of-Squares Proofs and the Quest toward Optimal Algorithmsarxiv.org
• The power of selectiontsvibt.blogspot.com