Separating Oblivious and Adaptive Models of Variable Selection (Extended Abstract)

Abstract

Sparse recovery is among the most well-studied problems in learning theory and high-dimensional statistics. In this work, we investigate the statistical and computational landscapes of sparse recovery with ℓ_∞ error guarantees. This variant of the problem is motivated by variable selection tasks, where the goal is to estimate the support of a k-sparse signal in ^d. Our main contribution is a provable separation between the oblivious (“for each”) and adaptive (“for all”) models of ℓ_∞ sparse recovery. We show that under an oblivious model, the optimal ℓ_∞ error is attainable in near-linear time with ≈ klog d samples, whereas in an adaptive model, ≳ k^2 samples are necessary for any algorithm to achieve this bound. This establishes a surprising contrast with the standard ℓ_2 setting, where ≈ k log d samples suffice even for adaptive sparse recovery. We conclude with a preliminary examination of a partially-adaptive model, where we show nontrivial variable selection guarantees are possible with ≈ klog d measurements.