Efficient Robust Constrained Signal Detection via Kolmogorov Width Approximations
Authors
Yikun Li
Affiliation: Department of Statistics and Data Science, Northwestern University
Email: YikunLi2028@u.northwestern.edu
Matey Neykov
Affiliation: Department of Statistics and Data Science, Northwestern University
Email: mneykov@northwestern.edu
Abstract
Robust statistical inference often faces a severe computational-statistical gap when dealing with complex parameter spaces. We investigate minimax signal detection in the Gaussian sequence model under strong $\epsilon$-contamination, where the signal belongs to a general prior constraint $K$. Existing optimal tests require computing the exact Kolmogorov $k$-width of $K$, a computationally intractable task for general non-trivial sets. We bridge this gap by proposing a polynomial-time testing framework that universally applies to balanced, type-2, and exactly 2-convex constraints. By leveraging a semidefinite programming relaxation and a modified ellipsoid method equipped with an approximate subgradient oracle, we efficiently approximate the Kolmogorov widths. Remarkably, our unconditional efficient algorithm achieves a robust detection boundary that matches existing upper bounds up to a mere polylogarithmic factor. This establishes a computationally tractable testing solution for a broad class of structured signals without requiring prior knowledge of their exact geometric complexity.
Availability
You can find the up-to-date preprint PDF file of this work here.