Technical Summary: Separating Oblivious and Adaptive Models of Variable Selection

1. Problem Statement

This work investigates the statistical and computational landscapes of sparse recovery with $\ell_\infty$ error guarantees, a variant closely related to variable selection in high-dimensional linear models. The core problem is to recover a $k$-sparse signal $\theta^\star \in \mathbb{R}^d$ from $n$ linear measurements $y = X\theta^\star + \xi$, where $X \in \mathbb{R}^{n \times d}$ is a measurement matrix and $\xi$ is a noise vector.

The primary focus is on the $\ell_\infty$ norm of the estimation error, $\|\theta - \theta^\star\|_\infty$, rather than the standard $\ell_2$ norm. The authors argue that $\ell_\infty$ recovery is the correct metric for variable selection: achieving a small $\ell_\infty$ error allows for the identification of the support (the set of non-zero entries) of $\theta^\star$ via simple thresholding, provided the signal strength exceeds the noise level.

A central conceptual contribution of the paper is the distinction between two modeling assumptions regarding the relationship between the signal/noise and the measurement matrix:

• Oblivious Model (Model 1): The signal $\theta^\star$ and noise $\xi$ are chosen independently of the measurement matrix $X$. This is often described as a "for each" guarantee.
• Adaptive Model (Model 2): No independence assumptions are made; $\theta^\star$ and $\xi$ may be chosen adversarially based on $X$. This is described as a "for all" guarantee.

The paper aims to characterize the sample complexity ($n$ as a function of $k$ and $d$) required to achieve optimal $\ell_\infty$ error under these distinct models.

2. Methodology and Technical Framework

Error Metric Definition

The authors propose a canonical error metric for $\ell_\infty$ sparse recovery:
$$\text{err}(X, \xi) := \|X^\top \xi\|_\infty$$
They justify this metric by showing it is equivalent to other literature metrics in the oblivious model and is the tightest achievable bound in the adaptive model.

Oblivious Model ($\ell_\infty$ Sparse Recovery)

For the oblivious model, the authors propose a three-stage algorithm (Algorithm 2) that runs in nearly-linear time:

1. Warm Start: Use Iterative Hard Thresholding (IHT), an $\ell_2$ sparse recovery algorithm, to obtain an initial estimate $\hat{\theta}$.
2. Support Identification: Use a thresholding procedure on the residual $X^\top(y - X\hat{\theta})$ to identify a candidate support set $L$. This step crucially leverages the independence between $X$ and $\theta^\star$ to ensure that interference terms concentrate at the noise scale.
3. In-Support Estimation: Perform Ordinary Least Squares (OLS) restricted to the learned support $L$ to refine the estimate.

The analysis relies on standard Restricted Isometry Property (RIP) arguments and new technical lemmas showing that for independent vectors, the $\ell_\infty$ operator norm of the inverse Gram matrix restricted to a support set behaves favorably with $n \approx k \log d$ samples.

Adaptive Model ($\ell_\infty$ Sparse Recovery)

For the adaptive model, the authors introduce a new property called $\ell_\infty$-RIP (Definition 4), which bounds the $\ell_\infty \to \ell_\infty$ operator norm of the Gram matrix $X^\top X - I$ on sparse submatrices.

• Upper Bound: They show that if $X$ satisfies $\ell_\infty$-RIP, IHT converges to an $\ell_\infty$ error of $O(\|X^\top \xi\|_\infty)$. They prove that sub-Gaussian matrices satisfy $\ell_\infty$-RIP with high probability when $n = \Omega(k^2 \log d)$.
• Lower Bound: The authors construct an adversarial instance to prove that $n = \Omega(k^2)$ is necessary. The construction involves finding a $k$-sparse vector $v$ such that $\|v\|_\infty$ is large, yet $\|X^\top X v\|_\infty$ is small (effectively "killed" by the measurements). This relies on showing that the $\ell_\infty$ operator norm of the inverse Gram matrix is $\Omega(k/\sqrt{n})$ when $n = o(k^2)$, allowing an adversary to mask the true support.

Partially-Adaptive Model

The paper also examines a partially-adaptive model (Model 4) where the noise $\xi$ is independent of $X$, but the signal $\theta^\star$ may be adaptive. They propose an algorithm (Algorithm 5) that uses adaptive measurements (specifically, the ability to "mask" or mute specific coordinates of $X$ in subsequent queries). This algorithm iteratively identifies support elements, mutes them, and repeats, achieving variable selection with $n \approx k \log k \log d$ measurements.

3. Key Contributions and Results

1. Optimal Oblivious Recovery

The paper provides the first polynomial-time algorithm that achieves optimal $\ell_\infty$ error in the oblivious model using $n = O(k \log d)$ samples.

• Result: An estimator exists that solves the problem with high probability in nearly-linear time.
• Improvement: This improves upon prior LASSO-based guarantees (e.g., [Wai19]), which require $n = \Omega(k^2)$ to achieve comparable error rates in the oblivious setting.

2. Separation of Oblivious and Adaptive Models

The most significant finding is a provable separation in sample complexity between the oblivious and adaptive models for $\ell_\infty$ recovery:

• Oblivious: $n = O(k \log d)$ samples suffice.
• Adaptive: $n = \Omega(k^2)$ samples are necessary and sufficient (up to logarithmic factors).
• Contrast: This contrasts sharply with the $\ell_2$ setting, where $n \approx k \log d$ samples are sufficient even for adaptive recovery. The authors establish that adaptivity in the choice of the unknown parameters makes the $\ell_\infty$ problem statistically harder.

3. New Error Metric and Bounds

The authors establish $\|X^\top \xi\|_\infty$ as the correct error metric.

• They provide matching upper and lower bounds for the adaptive model under this metric.
• They demonstrate that other error quantities considered in prior literature are provably unattainable in the adaptive model.

4. Partial Adaptivity

The paper shows that nontrivial variable selection guarantees are possible in a partially-adaptive setting (where noise is benign) if the learner is allowed to mask coordinates during observation. This suggests that the quadratic lower bound of the fully adaptive model can be circumvented with specific structural assumptions or interaction capabilities.

4. Significance and Claims

The paper claims to resolve fundamental questions regarding the statistical landscape of learning sparse linear models in $\ell_\infty$ error. Specifically:

• It settles the computational and statistical complexity of adaptive $\ell_\infty$ sparse recovery, showing a quadratic dependence on sparsity $k$ ($n \sim k^2$) which is distinct from the linear dependence in $\ell_2$ recovery.
• It provides the first efficient algorithm for oblivious $\ell_\infty$ recovery that matches the optimal sample complexity of $\ell_2$ recovery ($n \sim k \log d$).
• It highlights that the "for all" (adaptive) guarantee is strictly more demanding than the "for each" (oblivious) guarantee for $\ell_\infty$ norms, a phenomenon not present in the standard $\ell_2$ setting.

The authors conclude that their work establishes a surprising contrast with standard sparse recovery theory and provides a new canonical framework for analyzing variable selection under different independence assumptions. They leave the extension of the lower bound to $n = o(k^2 \log d/k)$ as an open problem.