区分了变量选择的静态与动态模型，揭示其样本需求差异
Separating Oblivious and Adaptive Models of Variable Selection
- 提出静态与动态变量选择模型的理论区分
- 静态模型仅需约k log d个样本即可达标，动态模型需超k²样本
- 适用于高维统计与稀疏恢复的理论研究者
稀疏恢复是学习理论和高维统计中研究最深入的问题之一。本文研究在ℓ∞误差保证下的稀疏恢复的统计与计算边界。该问题源于变量选择任务，目标是估计ℝᵈ中k-稀疏信号的支持集。主要贡献在于严格分离了ℓ∞稀疏恢复的‘静态’（‘对每个’）与‘自适应’（‘对所有’）模型。我们证明，在静态模型下，最优ℓ∞误差可在近线性时间内用约k log d个样本实现；而在自适应模型下，任何算法均需至少≈k²样本才能达到此界。这一结果与标准ℓ₂情形形成鲜明对比——后者即使在自适应模型下，≈k log d样本也足够。最后，我们初步考察了‘部分自适应’模型，表明在约k log d次测量下仍可获得非平凡的变量选择保证。
原文摘要 · Abstract (English)
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 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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。