Workshop: Information-Theoretic Methods for Rigorous, Responsible, and Reliable Machine Learning (ITR3)

Active Sampling for Binary Gaussian Model Testing in High Dimensions

Javad Heydari · Ali Tajer

Abstract: A sample $X\in\R^{p}$ is generated according to one of the two known $p$-dimensional Gaussian models. This paper establishes the information-theoretic limits of {\bf actively} sampling the one-dimensional coordinates of $X$ for detecting its true model as $p\to\infty$. We address three questions pertinent to active model detecting. First, we establish conditions under which the problem is feasible under controlled error rates. Secondly, we characterize the information-theoretic lower bound on the coordinate-level sample complexity for model detection. Finally, we provide an active sampling algorithm that progressively identifies the coordinates to be sampled, and prove that this algorithm's sample complexity meets the information-theoretic limit in the asymptote of large $p$.

Chat is not available.