REVIEW 2 major objections 4 minor 2 references
Separating Oblivious and Adaptive Models of Variable Selection
T0 review · 2 major / 4 minor · reviewed 2026-08-02 · deepseek-v4-flash
Pith's one-line read Adaptive sparse recovery provably needs k^2 samples, versus k log d when the signal is oblivious.
desk verdict Worth engaging: a real separation result, but read the formal statements, not the abstract — the oblivious upper bound carries a √log factor relative to the exact benchmark. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
l_infinity-RIP: a bound on the largest row-sum of X^T X - I restricted to sparse submatrices, weaker than pairwise incoherence and satisfied by sub-Gaussian designs at about k^2 log(d/k) samples. The adaptive lower bound uses a Gram-inverse blow-up lemma: with n = o(k^2), the inverse of any k-by-k submatrix of X^T X has sup-norm operator norm about k/sqrt(n), producing an adversarial noise vector invisible to correlations. The oblivious upper bound combines iterative hard thresholding with thresholded support recovery and ordinary least squares on the learned support.
What would settle it
Simulate the lower-bound instance with n = k^{1.5} Gaussian measurements: build the adversarial noise xi = X v where v is supported on a random k-set and chosen so that X^T X v has sup-norm 1. If any estimator recovers the signal to sup-norm error O(1) with probability above 3/4—for example by detecting the planted v through residual correlations—the lower bound fails. Conversely, proving that n = o(k^2 log(d/k)) remains hard would close the log-factor gap.
Extended reading notes
Core claim
The paper establishes that the sample complexity of sup-norm sparse recovery jumps from about k log d to about k^2 when the unknown parameters are allowed to depend on the measurement matrix. For the adaptive model, the lower bound is information-theoretic: two distinct signal-plus-noise pairs produce identical observations, so no algorithm can distinguish them. The construction relies on a k-sparse vector v whose correlations with the design columns are tiny while its coordinates are large, so the noise xi = X v is invisible to any correlation test yet changes the signal in sup-norm. On the upper bound side, a new l_infinity-restricted-isometry property is shown to hold for Gaussian matrice
Load-bearing premise
The entire adaptive lower bound rests on measuring success by the correlation statistic ||X^T xi||_infinity; if the benchmark were instead the raw noise level ||xi||_infinity or ||xi||_2/sqrt(n), the quadratic separation collapses (Lemma 21 shows adaptive recovery is impossible in those metrics even with many samples).
Editorial extensions
If this is right
- Variable selection against an adaptive adversary requires quadratically more measurements than against an independent signal, even though l2 recovery pays no such gap.
- The k^2 sample complexity for adaptive sup-norm recovery is tight up to a log(d/k) factor; the paper conjectures the log factor is necessary as well.
- The new l_infinity-RIP condition and the sup-norm metric ||X^T xi||_infinity give a clean benchmark for noise in sparse linear regression.
- In a partially-adaptive model where the noise is independent but the signal may adapt, support recovery is possible with about k log d measurements when the learner can mask coordinates in new queries.
- Replacing a LASSO-based step with the paper's faster l_infinity recovery speeds up spike-and-slab posterior sampling from near-quadratic-in-d time to near-linear time.
Reading between the lines
- The separation suggests that any application reusing a fixed measurement matrix across adaptively chosen signals—such as bandit-style feature selection or wrapper-based hyperparameter search—should budget k^2 measurements for support recovery guarantees.
- The error metric choice is a modeling commitment; if success is measured by the raw noise level rather than design-noise correlations, the adaptive lower bound no longer applies, so the quadratic gap is specific to that metric.
- The recursive masking algorithm in Section 5 could serve as a template for adaptive measurement designs in other high-dimensional estimation problems where coordinates can be selectively observed.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies ℓ∞-error sparse recovery / variable selection and contrasts three generative models: the oblivious model (θ*, ξ independent of X), the adaptive model (arbitrary dependence), and a partially-adaptive model (ξ independent of X). The main claimed result is a quadratic sample-complexity gap: with n = Ω(k log d) samples, an oblivious algorithm can solve ℓ∞ recovery, while no adaptive algorithm can succeed when n = o(k²), and n = Ω(k² log d) suffices adaptively. A new ℓ∞-RIP condition is introduced to prove the adaptive upper bound, and the adaptive lower bound is built from an inverse-Gram lemma that produces sparse noise invisible to the measurements. A partial-adaptivity section gives a support-recovery algorithm that uses column-muting adaptive queries with ≈ k log d log k samples.
Significance. If the central theorems are correct, this is an important conceptual contribution: it is the first proven quadratic gap between oblivious and adaptive models for ℓ∞ sparse recovery/variable selection, and it shows that adaptivity of the unknown parameters matters more in ℓ∞ than in ℓ2. The paper also introduces a potentially useful notion, ℓ∞-RIP, and gives a clean indistinguishability lower-bound construction. The partially-adaptive masked-observation result is a valuable stepping stone. However, the formal oblivious upper bound, as stated, does not solve Problem 2: it carries a polylogarithmic overhead, and the proof of the key inequality (12) is invalid when d ≫ n. These issues are fixable, but they are load-bearing for the paper's headline claim.
major comments (2)
- [§3.3, Eq. (12); Theorem 3; Corollary 3] The bound ∥X^(i)⊤ξ^(i)∥∞ = O(∥ξ∥₂√(log(n/δ)/n)) is not valid: X^(i)⊤ξ^(i) has d coordinates, so a union bound gives √(log(d/δ)/n). Since the paper allows d ≫ n (e.g., k = 1, d = 2^n), the displayed comparison to ∥X^⊤ξ∥∞√(log n/δ) is false. Even if the union bound were over d, the proof would give a √log d factor relative to the benchmark, so Theorem 3/Corollary 3 do not establish the constant-factor guarantee of Problem 2. The abstract's 'optimal ℓ∞ error is attainable' is thus unsupported. The authors should either prove a block-comparison lemma showing max_i ∥X^(i)⊤ξ^(i)∥∞ ≤ C∥X^⊤ξ∥∞ with high probability under Model 1, or restate the main claims with an explicit polylog factor and adjust the lower-bound target accordingly.
- [§4.2, Lemma 17] Lemma 17 only controls the S×S block of I − X^⊤X, but the error vector (θ^{(t+0.5)} − θ*) can have nonzero coordinates outside S. For j ∉ S, the j-th coordinate is −Σ_{ℓ∈S} ⟨x_j, x_ℓ⟩ (θ^t − θ*)ₗ, and this is not bounded by (ε, 2k)-ℓ∞-RIP; pairwise blocks give only a factor-k bound, which breaks the contraction. The proof can be repaired by requiring (ε, 2k+1)-ℓ∞-RIP and applying it to blocks S ∪ {j}. Since Lemma 14 can be stated for 2k+1 with the same n = Ω(k² log(d/δ)) rate, Theorem 4 is likely salvageable, but the current statement and proof need correction.
minor comments (4)
- [§3.3, discussion after Theorem 3] The sentence about 'tight bounds for the maximum of k Gaussians in place of (12)' is confusing: the thresholding step considers d coordinates, not k. If the intended statement is about the in-support OLS step, it should be clarified; otherwise the d-union bound is the relevant one.
- [§4.3, Theorem 5 proof] The success-probability computation '1/2 + 1/2·1/2' is correct because Corollary 5 only succeeds with probability 1/2 over X, but the phrasing 'no algorithm can do better than random guessing' could mislead. It would be clearer to separate the two sources of randomness (draw of X and choice of instance).
- [Appendix A, Lemma 20] The lemma states (b) with √(log k/δ/n), but the proof of Theorem 3 invokes a similar bound with log n. Please reconcile the logarithmic factors and state explicitly whether the union is over d or k.
- [General] The abstract and introduction claim 'optimal ℓ∞ error' is attained with ≈ k log d samples; given Corollary 3, this should be qualified as 'up to polylogarithmic factors' throughout, unless the stronger guarantee is proven.
Circularity Check
No circular reduction in the main theorems; only a minor, non-load-bearing self-citation in an application appendix.
full rationale
After walking the derivation chain, I find no circular reduction in the central results. The oblivious upper bound (Theorem 3 / Corollary 3) is built on sub-Gaussian tail bounds, RIP (external [FR13]), the external IHT guarantee [Pri21], and the thresholding/OLS Lemmas 8-9; the threshold parameter is an assumed noise-level input that Algorithm 3 later removes via holdout, so it is not a fitted quantity masquerading as a prediction. The adaptive upper bound (Theorem 4) follows from the newly defined l_infinity-RIP (Lemma 14) and the contraction Lemma 17. The adaptive lower bound (Theorems 5-6) uses Lemma 18 / Corollary 5 to construct two observationally identical pairs (theta_bar, X v) and (theta_bar+v, 0) with ||X^T xi_1||_inf = 1 and ||X^T xi_2||_inf = 0; this is a standard indistinguishability argument and does not assume the target separation. The choice of ||X^T xi||_inf as the benchmark is a modeling decision defended in Appendix A via Lemma 20 (equivalences in the oblivious model) and Lemma 21 (impossibility for alternatives); it is not defined in terms of the results and is not a fitted input. The only overlap-authors citation, [KSTZ25], appears solely in the application appendix (Corollary 6) and is used as a black-box subroutine to state an improved runtime; it does not support the central separation theorems and is not a uniqueness/ansatz import. Therefore there is no circularity in the main derivation. I assign score 2 only to record the minor, non-load-bearing self-citation; if self-citations are ignored, the score would be 0. (The inequality (12) flagged by the skeptic is a potential correctness gap about the union bound over d, but a proof gap is not a circularity.)
Assumptions & free parameters
free parameters (1)
- Universal constants in Theorems 1, 2, 3, 5, 6, 7 and Problem 1 (C, c, c', C') =
unspecified positive constants
assumptions (5)
- standard math Standard sub-Gaussian concentration inequalities (Hoeffding, Hanson-Wright, Chernoff, Cantelli) and RIP facts are valid and applicable.
- domain assumption Model 3: the design matrix X has i.i.d. sub-Gaussian entries with variance 1/n and constant sub-Gaussian parameter C.
- domain assumption The l_infinity recovery benchmark is ||X^T xi||_infinity, as defined in Eq. (1) and Problem 2.
- domain assumption Model 2 permits (theta*, xi) to be chosen with full knowledge of X, with no independence assumptions.
- ad hoc to paper In the partially-adaptive model, the learner may mute selected columns of X in new observations (Algorithm 4).
Cite this review
Pith. "Pith review of Separating Oblivious and Adaptive Models of Variable Selection." pith.science (2026). https://pith.science/paper/B2EPUGSH
@misc{pith2026260216568,
author = {Pith},
title = {Pith review of: Separating Oblivious and Adaptive Models of Variable Selection},
year = {2026},
howpublished = {\url{https://pith.science/paper/B2EPUGSH}},
note = {Machine review of arXiv:2602.16568}
}
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 $\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.
Reference graph
Works this paper leans on
-
[2]
Finally, there is a constant probability that each such drawx⊤ i ξobeys the bound in(d), by the same proof strategy as used in establishing (21)
The maximum ofkof these variables can be bounded by Lemma 1 and a union bound, yielding(b). Finally, there is a constant probability that each such drawx⊤ i ξobeys the bound in(d), by the same proof strategy as used in establishing (21). Under the stated parameter range onk, the probability(d)fails underkindependent draws is at mostδ. We mention that both...
-
[3462]
[LDP07] Michael Lustig, David Donoho, and John M Pauly
PMLR, 2025. [LDP07] Michael Lustig, David Donoho, and John M Pauly. Sparse mri: The application of compressed sensing for rapid mr imaging.Magnetic Resonance in Medicine: An Official Journal of the International Society for Magnetic Resonance in Medicine, 58(6):1182– 1195, 2007. 31 [LM00] Béatrice Laurent and Pascal Massart. Adaptive estimation of a quadr...
arXiv 2025
Reviewed August 2, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.