Stability of a Generalized Debiased Lasso with Applications to Resampling-Based Variable Selection

This paper introduces a generalized debiased Lasso estimator that leverages a stability principle to provide a computationally efficient, asymptotically accurate update formula for perturbed designs, thereby significantly reducing the cost of resampling-based variable selection methods like the conditional randomization test and local knockoff filter.

The Gist

The Big Picture: Finding the Needle in a Haystack

Imagine you are a detective trying to solve a crime. You have a massive list of 1,000 suspects (variables), but you know only a handful (maybe 20) actually committed the crime. Your goal is to identify the guilty ones without accusing innocent people.

In statistics, this is called Variable Selection. The tool you use is called the Lasso. Think of the Lasso as a very strict filter that tries to shrink the influence of innocent suspects to zero, leaving only the guilty ones.

However, the Lasso has a flaw: it's a bit "biased." It tends to shrink the guilty suspects' influence too much, making them look weaker than they really are. To fix this, statisticians invented the Debiased Lasso, which adds a correction factor to get the true strength of the suspects back.

The Problem: The "Re-do" Nightmare

Now, imagine you want to be extra sure about your verdict. You decide to run a "Resampling Test." This is like asking: "What if I slightly changed the evidence for Suspect #5? Would I still think they are guilty?"

To do this properly, you have to:

1. Change Suspect #5's evidence.
2. Run the entire Lasso calculation again from scratch.
3. Repeat this for Suspect #6, #7, and so on, up to #1,000.

The Catch: Running the Lasso calculation is like solving a giant, complex Sudoku puzzle. If you have to solve it 1,000 times, it takes forever. It's like baking a cake from scratch 1,000 times just to see if changing the amount of sugar in one batch changes the taste. It's computationally expensive and slow.

The Solution: The "Magic Update" Formula

This paper introduces a Generalized Debiased Lasso with a special "Stability Principle."

The Analogy:
Imagine you have a perfectly balanced mobile hanging from the ceiling. If you gently nudge one small weight (change one column of data), the whole mobile shifts slightly.

• The Old Way: To see how the mobile moves, you take it down, rebuild the whole thing, and hang it up again.
• The New Way (This Paper): The author discovered a "Magic Update Formula." Because the mobile is stable, you don't need to rebuild it. You just need to know the original position and apply a simple math trick to calculate exactly where the mobile will end up after the nudge.

What the Paper Proves:

1. It Works: When you change one piece of data, the new answer is almost exactly equal to the old answer plus a simple correction term.
2. It's Fast: Instead of solving the giant puzzle 1,000 times, you solve it once, and then use the "Magic Update" 999 times. This turns a task that takes hours into one that takes minutes.
3. It's Robust: This works even when the suspects (variables) are related to each other (correlated), which usually makes these calculations very messy.

Why This Matters: The "Local Knockoff" and "CRT"

The paper applies this speed boost to two famous methods for controlling false accusations (False Discovery Rate):

1. The Knockoff Filter: Imagine creating a "fake twin" for every suspect. You compare the real suspect to the fake twin. If the real one looks more guilty, you keep them.

   • The Flaw: Creating 1,000 fake twins and running the test on 2,000 suspects is slow and often less powerful (less likely to catch the real culprits).
   • The Fix: The paper suggests a "Local Knockoff" method. Instead of making twins for everyone at once, you just swap out one suspect at a time. This is much more powerful, but it used to be too slow to run. Now, with the "Magic Update," it's fast enough to use!

2. The Conditional Randomization Test (CRT): This is like a "What If?" game. "What if Suspect #5 was actually innocent? Would the data still look the same?"

   • The Fix: Using the paper's formula, we can simulate these "What If" scenarios instantly without re-running the whole model.

The "Stability" Secret

Why does this magic work? The authors found that the "signs" of the solution (whether a suspect is guilty or innocent) are stable.

Think of it like a house of cards. If you have a very stable house, and you swap one card, the whole house doesn't collapse; it just shifts slightly. The paper proves that for the Debiased Lasso, the "house" is so stable that even if the data changes, the core structure (who is guilty) stays the same, and we can predict the new result with high accuracy using a simple formula.

Summary in One Sentence

This paper discovered a mathematical "shortcut" that allows statisticians to instantly update their results when data changes, turning a slow, impossible-to-run process into a fast, practical tool for finding the truth in massive datasets.

The Real-World Impact

• Faster Science: Researchers can analyze genetic data (like the Riboflavin and HIV datasets mentioned in the paper) much faster.
• Better Accuracy: Because the method is faster, we can run more tests, leading to more reliable discoveries and fewer false alarms.
• Accessibility: It makes advanced statistical tools usable on standard computers, not just supercomputers.

Technical Summary

1. Problem Statement

The paper addresses two interconnected challenges in high-dimensional statistics ($n, p \to \infty$ with $p/n \to \delta$):

1. Computational Bottleneck in Resampling: Resampling-based variable selection methods, such as the Knockoff Filter and the Conditional Randomization Test (CRT), require solving regression problems repeatedly (often $O(p)$ times) by perturbing individual features. In the Lasso setting, solving these problems from scratch is computationally expensive ($O(p^3)$ or higher per iteration), making these methods impractical for large-scale data.
2. Limitations of Asymptotic Normality: Traditional debiased Lasso estimators rely on asymptotic normality (Gaussian limits) to compute p-values. However, establishing these limits for correlated, non-Gaussian designs in the proportional growth regime remains an open theoretical problem. Existing proofs often require restrictive assumptions (e.g., independent entries or specific rotational invariance) that do not hold for general sub-Gaussian designs.

The core question is: Can we efficiently update a debiased Lasso estimator when a single column of the design matrix is perturbed, without re-solving the optimization problem, and does this update remain accurate under general conditions?

2. Methodology

A. Generalized Debiased Estimator

The author proposes a generalized debiased estimator, denoted as $\hat{\alpha}^U_j$, which extends the standard debiased Lasso (Javanmard & Montanari, 2014).

• Standard Debiased Lasso: $\hat{\alpha}^u = \hat{\alpha} + \frac{1}{n-k}\Sigma^{-1}A^\top(Y - A\hat{\alpha})$.
• Generalized Form: For a perturbed design matrix $B$ (differing from $A$ only in column $j$), the estimator is updated using a "residualized column" $\check{A}_{:j} = A_{:j} - \mu_{:j}$, where $\mu_{:j}$ is an arbitrary vector (often the conditional mean $E[A_{:j}|A_{:\setminus j}]$).
  $$\hat{\alpha}^U_j = \hat{\alpha}_j + \left( \frac{1}{n} \check{A}_{:j}^\top (I - P_A) A_{:j} \right)^{-1} \frac{\check{A}_{:j}^\top R}{n}$$
  Here, $P_A$ is the projection onto the active set of variables (those with non-zero signs in the subgradient).

B. The Stability Principle & Update Formula

The paper establishes that if the signs of the Lasso coefficients are stable under a single-column perturbation, the debiased estimator admits a simple, computable update formula.

• Key Insight: The update formula relies on the orthogonality principle. The error in the update is controlled by the inner product of two "incoherent" vectors: the residualized perturbed column and the change in the projection matrix.
• Approximation: The paper derives a formula to approximate the debiased statistic $t(j, B, Y)$ for the perturbed matrix $B$ using only the solution $\hat{\alpha}$ from the original matrix $A$:
  $$t(j, B, Y) \approx \frac{1}{n} \check{B}_{:j}^\top R + \frac{1}{n} \check{B}_{:j}^\top (I - P_A) A_{:j} \hat{\alpha}_j$$
  This avoids solving the Lasso for $B$ entirely.

C. Theoretical Framework

The proofs rely on concentration and anti-concentration arguments rather than precise Gaussian limit calculations.

• Sign Stability: The authors prove that the number of sign changes in the Lasso solution ($\chi^\alpha$ vs $\chi^\beta$) is small (vanishing fraction) when the design matrix is perturbed, provided the design is sub-Gaussian with a well-conditioned covariance matrix.
• Non-asymptotic Bounds: Theorem 1 provides explicit error bounds for any given design matrix, showing the approximation error is controlled by the magnitude of the coefficients and the "incoherence" of the perturbation.
• Asymptotic Bounds: Theorem 4 and Theorem 5 show that for sub-Gaussian designs, the approximation error vanishes asymptotically for almost all coordinates ($1 - o(1)$ fraction).

3. Key Contributions

1. Generalized Debiased Estimator: Introduced a definition of the debiased estimator that is robust to general designs (correlated, non-Gaussian) and does not require the strict assumptions needed for asymptotic normality.
2. Stable Update Formula: Proved that the debiased estimator can be updated efficiently when a single feature is changed. The error of this update is negligible for almost all features in the proportional regime.
3. Relaxation of Assumptions: Unlike previous works requiring Gaussian designs or independent entries to prove asymptotic normality, this paper only requires sub-Gaussian designs with bounded condition numbers. It demonstrates that the update formula holds even when asymptotic normality fails (e.g., in specific orthogonal designs with non-Gaussian noise).
4. Computational Acceleration: The method reduces the complexity of resampling-based variable selection from $O(p \cdot L)$ (where $L$ is the cost of solving one Lasso) to $O(L + p^2)$, effectively eliminating the $p$-fold computational overhead.

4. Results

Theoretical Results

• Theorem 1 (Non-asymptotic): Establishes that for any fixed design matrices $A$ and $B$ differing by one column, the update formula approximates the true debiased statistic with an error bounded by $\Gamma D \sqrt{\epsilon} (|\hat{\alpha}_j| + |\hat{\beta}_j|)$, where $\epsilon$ is the fraction of sign changes.
• Theorem 4 & 5 (Asymptotic): Under sub-Gaussian assumptions, the approximation error vanishes as $O(n^{-1/18})$ for all but a vanishing fraction of coordinates.
• Theorem 7: Shows that for Gaussian designs, the generalized estimator converges to the standard debiased Lasso, validating the generalization.

Empirical Results

• Approximation Accuracy: Experiments on synthetic data show that the approximation error for the debiased estimator is consistently smaller than that of the standard Lasso, especially as feature correlation ($\rho$) increases.
• FDR Control:
  • Local Knockoff Filter: A variant that resamples one feature at a time. Using the update formula, it achieves the same statistical power as the full Knockoff filter but with significantly reduced runtime.
  • Conditional Randomization Test (CRT): The proposed "approx-CRT-db" method achieves FDR control comparable to the exact CRT but with drastically lower computational cost.
  • Real Data: Applied to Riboflavin and HIV drug resistance datasets, the debiased local knockoff and CRT methods showed higher statistical power than standard Knockoff filters while maintaining FDR control near the target level (0.1).

5. Significance and Impact

• Bridging Theory and Practice: The paper resolves a major computational barrier in high-dimensional inference. Methods like CRT and Local Knockoffs were previously considered too slow for large $p$; this work makes them feasible.
• Robustness to Design: By shifting the focus from "asymptotic normality" to "stability of the update," the paper provides a more robust theoretical foundation for debiased inference that applies to a wider class of real-world data (correlated, non-Gaussian).
• Algorithmic Stability: The work connects the concept of algorithmic stability (how an estimator changes with data perturbation) to statistical inference, suggesting that stability is a sufficient condition for valid resampling-based p-values, even when Gaussian limits are unknown.
• Future Directions: The authors suggest that these stability techniques could be extended to other regularizers, factor models, and potentially differential privacy guarantees.

In summary, this paper provides a computationally efficient and theoretically rigorous framework for performing variable selection with false discovery rate control in high-dimensional settings, overcoming the limitations of both traditional asymptotic theory and brute-force resampling.