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

Ziyun Chen, Jerry Li, Kevin Tian, Yusong Zhu
Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:1113-1114, 2026.

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 $\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 $\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 model, the optimal $\ell_\infty$ error is attainable in near-linear time with $\approx k\log d$ samples, whereas in an adaptive model, $\gtrsim 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 \emph{partially-adaptive} model, where we show nontrivial variable selection guarantees are possible with $\approx k\log d$ measurements.

Cite this Paper

BibTeX
@InProceedings{pmlr-v336-chen26b, title = {Separating Oblivious and Adaptive Models of Variable Selection (Extended Abstract)}, author = {Chen, Ziyun and Li, Jerry and Tian, Kevin and Zhu, Yusong}, booktitle = {Proceedings of Thirty Ninth Conference on Learning Theory}, pages = {1113--1114}, year = {2026}, editor = {Hanneke, Steve and Lattimore, Tor}, volume = {336}, series = {Proceedings of Machine Learning Research}, month = {29 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v336/main/assets/chen26b/chen26b.pdf}, url = {https://proceedings.mlr.press/v336/chen26b.html}, 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 $\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 $\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 model, the optimal $\ell_\infty$ error is attainable in near-linear time with $\approx k\log d$ samples, whereas in an adaptive model, $\gtrsim 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 \emph{partially-adaptive} model, where we show nontrivial variable selection guarantees are possible with $\approx k\log d$ measurements.} }
Endnote
%0 Conference Paper %T Separating Oblivious and Adaptive Models of Variable Selection (Extended Abstract) %A Ziyun Chen %A Jerry Li %A Kevin Tian %A Yusong Zhu %B Proceedings of Thirty Ninth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Steve Hanneke %E Tor Lattimore %F pmlr-v336-chen26b %I PMLR %P 1113--1114 %U https://proceedings.mlr.press/v336/chen26b.html %V 336 %X 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 $\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 model, the optimal $\ell_\infty$ error is attainable in near-linear time with $\approx k\log d$ samples, whereas in an adaptive model, $\gtrsim 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 \emph{partially-adaptive} model, where we show nontrivial variable selection guarantees are possible with $\approx k\log d$ measurements.
APA
Chen, Z., Li, J., Tian, K. & Zhu, Y.. (2026). Separating Oblivious and Adaptive Models of Variable Selection (Extended Abstract). Proceedings of Thirty Ninth Conference on Learning Theory, in Proceedings of Machine Learning Research 336:1113-1114 Available from https://proceedings.mlr.press/v336/chen26b.html.

Related Material