# Separating Oblivious and Adaptive Models of Variable Selection

arXiv: https://arxiv.org/abs/2602.16568 · HTML: https://mlsanity.com/paper/2602.16568/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 58 references that are in the map.
- First posted on arXiv 18 Feb 2026.

## Builds on (most cited first, 8 of 8)

- [Controlling the false discovery rate via knockoffs](https://mlsanity.com/paper/1404.5609/) (2014)
- [An Introductory Guide to Fano's Inequality with Applications in Statistical Estimation](https://mlsanity.com/paper/1901.00555/) (2019)
- [On the Computational Complexity of High-Dimensional Bayesian Variable Selection](https://mlsanity.com/paper/1505.07925/) (2015)
- [High-Dimensional Regression with Binary Coefficients. Estimating Squared Error and a Phase Transition](https://mlsanity.com/paper/1701.04455/) (2017)
- [Semirandom Planted Clique and the Restricted Isometry Property](https://mlsanity.com/paper/2404.14159/) (2024)
- [Provably Efficient Posterior Sampling for Sparse Linear Regression via Measure Decomposition](https://mlsanity.com/paper/2406.19550/) (2024)
- [Spike-and-Slab Posterior Sampling in High Dimensions](https://mlsanity.com/paper/2503.02798/) (2025)
- [A Constructive Approach to High-dimensional Regression](https://mlsanity.com/paper/1701.05128/) (2017)

## Built on by (most cited first, 1 of 1)

- [High-Magnetization Sampling at Low Temperatures: Ising Models and Bayesian Sparse Linear Regression](https://mlsanity.com/paper/2609.08873/) (2026)

## Abstract (arXiv)

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, gtrsim k2 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.