{"id":"arxiv/2602.16568","url":"https://arxiv.org/abs/2602.16568","tags":["math.ST","cs.DS","cs.LG","math.OC","stat.ML"],"score":0,"title":"Separating Oblivious and Adaptive Models of Variable Selection","domain":"math.ST","source":"arxiv","authors":["Ziyun Chen","Jerry Li","Kevin Tian","Yusong Zhu"],"reviews":0,"subject":"math.ST","summary":"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 $\\ell_\\infty$ error guarantees. This variant of the problem is motivated by \\emph{variable selection} tasks, where the goal is to estimate the support of a $k$-sparse signal in $\\mathbb{R}^d$. Our main contribution is a provable separation between the \\emph{oblivious} (``for each'') and \\emph{adaptive} (``for all'') models of $\\ell_\\infty$ sparse recovery. We show that under an oblivious…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-02-18","reactions":{}}