Sparse recovery is among the most well-studied problems in learning theory and high-dimensional statistics. This work investigates the statistical and computational landscapes of sparse recovery with $\ell_\infty$ error guarantees. This variant is motivated by variable selection tasks, aiming to estimate the support of a $k$-sparse signal in $\mathbb{R}^d$.
Our main contribution is a provable separation between the oblivious ("for each") and adaptive ("for all") models of $\ell_\infty$ sparse recovery. We show that under the oblivious model, the optimal $\ell_\infty$ error is attainable in near-linear time with $\approx k \log d$ samples, while in the adaptive model, $\geq k^2$ samples are necessary for any algorithm to achieve this bound.
This establishes a surprising contrast with the standard $\ell_2$ setting, where $\approx k \log d$ samples suffice even for adaptive sparse recovery. We conclude with a preliminary examination of a partially-adaptive model, where nontrivial variable selection guarantees are possible with $\approx k \log d$ measurements.
Blogger's Review: This paper reveals the fundamental differences between oblivious and adaptive models in sparse recovery, offering new insights into the complexities of variable selection problems, particularly in the context of high-dimensional data processing.