PaperlayerView exact revision on arXiv

Source-linked AI summary

De-biasing the Lasso: Optimal Sample Size for Gaussian Designs

Adel Javanmard, Andrea Montanari

arXiv:1508.02757v3math.STstat.MLstat.TH

TL;DR

The paper addresses high-dimensional inference when the distribution of estimators is difficult to characterize. It analyzes debiased Lasso estimators for Gaussian designs and establishes asymptotic Gaussianity under weaker sparsity conditions, while identifying limits for non-Gaussian designs.

  • Problem

    High-dimensional inference lacks precise estimator distributions, limiting confidence intervals and p-values for individual parameters.

    Source: §1.1 · p. 2

  • Method

    The paper analyzes a debiased Lasso estimator using Gaussian-design structure, including known and estimated covariance and leave-one-out arguments.

    Source: §1.2 · p. 4, §3.3.2 · p. 12, §4 · p. 14

  • Results

    Under known covariance and s0 = o(n/(log p)^2), the debiased estimator is asymptotically Gaussian, with analogous results under sufficiently sparse inverse covariance.

    Source: §1.2 · pp. 4–5

  • Takeaways & Limitations

    The results support high-dimensional confidence intervals under nearly optimal coefficient sparsity and clarify the trade-off between coefficient and inverse-covariance sparsity.

    Source: §1.2 · p. 5

    Extending the results beyond Gaussian designs to independent sub-Gaussian rows requires new leave-one-out proof ideas to handle dependencies between columns.

    Source: §1.3 · p. 6

Abstract

from arXiv · show

Performing statistical inference in high-dimension is an outstanding challenge. A major source of difficulty is the absence of precise information on the distribution of high-dimensional estimators. Here, we consider linear regression in the high-dimensional regime $p\gg n$. In this context, we would like to perform inference on a high-dimensional parameters vector $\theta^*\in{\mathbb R}^p$. Important progress has been achieved in computing confidence intervals for single coordinates $\theta^*_i$. A key role in these new methods is played by a certain debiased estimator $\hat{\theta}^{\rm d}$ that is constructed from the Lasso. Earlier work establishes that, under suitable assumptions on the design matrix, the coordinates of $\hat{\theta}^{\rm d}$ are asymptotically Gaussian provided $\theta^*$ is $s_0$-sparse with $s_0 = o(\sqrt{n}/\log p )$. The condition $s_0 = o(\sqrt{n}/ \log p )$ is stronger than the one for consistent estimation, namely $s_0 = o(n/ \log p)$. We study Gaussian designs with known or unknown population covariance. When the covariance is known, we prove that the debiased estimator is asymptotically Gaussian under the nearly optimal condition $s_0 = o(n/ (\log p)^2)$. Note that earlier work was limited to $s_0 = o(\sqrt{n}/\log p)$ even for perfectly known covariance. The same conclusion holds if the population covariance is unknown but can be estimated sufficiently well, e.g. under the same sparsity conditions on the inverse covariance as assumed by earlier work. For intermediate regimes, we describe the trade-off between sparsity in the coefficients and in the inverse covariance of the design. We further discuss several applications of our results to high-dimensional inference. In particular, we propose a new estimator that is minimax optimal up to a factor $1+o_n(1)$ for i.i.d. Gaussian designs.

1 Introduction

The paper studies Gaussian limits for debiased Lasso estimators and develops sharper sparsity conditions for high-dimensional inference. Its results cover known and unknown covariance, applications to confidence intervals, and a minimax-optimal thresholded estimator.

1.1 Background

  • High-dimensional inference seeks confidence intervals for individual parameters, but earlier debiased Lasso results required s0 = o(√n/ log p), stronger than the estimation condition s0 = o(n/ log p).The debiased estimator is designed to make coordinatewise inference possible, while the prior Gaussian-limit condition was more restrictive than consistent estimation.Source: §1.1 · pp. 2–3
  • The earlier ℓ1-ℓ∞ bias bound imposes s0 = o(√n/ log p) even when the precision matrix is known, because it does not exploit dependencies in random designs.The paper identifies dependence between the empirical covariance error and the Lasso error as the technical obstacle.Source: §1.1 · p. 3, §1.2 · p. 4

1.2 Main results

  • Leave-one-out analysis yields Gaussian limits for known covariance when s0 = o(n/(log p)^2), with √n(bθd − θ*) asymptotically represented by a conditional Gaussian vector.The proof removes a design column, analyzes the perturbation, and adds the column back; the Gaussian covariance is σ2ΩbΣΩ.Source: §1.2 · p. 4
  • For unknown covariance estimated by node-wise Lasso, the same Gaussian limit holds when s0 = o(n/(log p)^2) and min(sΩ, s0) = o(√n/ log p).If the precision matrix is sufficiently sparse, the coefficient sparsity condition reaches the nearly optimal rate; otherwise precision estimation can remain the bottleneck.Source: §1.2 · pp. 4–5

1.3 Extensions and applications

  • The results support confidence intervals, semi-supervised precision estimation, and a thresholded Lasso estimator that is minimax optimal up to a factor 1 + o_n(1).The paper also discusses sample splitting, noise and regularization estimation, and expected extensions to non-Gaussian designs.Source: §1.3 · pp. 5–6, §1.4 · p. 6

1.4 Organization and contributions

  • The paper establishes a minimax lower bound for the non-Gaussian residual, showing that the Gaussian-limit results cannot be substantially improved.The lower bound targets the ℓ∞ norm of the residual component in the debiased estimator.Source: §1.4 · p. 6

2 Related work

Related work develops debiasing, sample-splitting, and selective-inference methods for high-dimensional models. The paper positions its contribution as stronger Gaussian inference for Gaussian designs, including uniform coordinatewise guarantees.

2 Related work

  • Selective-inference methods condition significance statements on a selected low-dimensional model, whereas this paper targets classical unconditional statements.The two approaches are described as broadly complementary.Source: §2 · p. 7
  • Sample splitting offers a general inference strategy but uses only part of the data and depends on the random split, making it potentially sub-optimal.The present paper discusses sample splitting as an alternative debiasing construction rather than its main focus.Source: §2 · p. 7
  • Inference without design assumptions can produce conservative confidence intervals, while node-wise Lasso implementations provide practical tools for debiasing.The paper also notes extensions to generalized linear models and robustness to model misspecification.Source: §2 · p. 7
  • Prior debiasing work established Gaussian limits under various settings, while this paper provides a stronger result holding uniformly over all coordinates.Earlier work sometimes guaranteed Gaussianity only for most coordinates or only on average over coordinates.Source: §2 · p. 7

3 Main results: Gaussian limit theorems

The results characterize debiased Lasso estimators for Gaussian designs with known and unknown covariance, establishing Gaussian limits under sparsity-dependent sample-size conditions and validating these patterns numerically.

3.3.1 Known covariance

  • n ≫ s0(log p)^2 makes the debiased estimator asymptotically unbiased and Gaussian when the precision matrix is known.The construction sets M = Ω, and the Gaussian noise term dominates the bias in this regime.Source: §3.3 · p. 10, §3.3.1 · p. 11
  • The known-covariance theorem decomposes √n(bθd − θ∗) into Gaussian noise plus a remainder under n = Ω(s0 log p).The noise covariance is σ^2ΩΣ̂Ω, while the remainder is controlled separately.Source: §3.3.1 · p. 11
  • The known-covariance result applies to bounded-block and circulant covariance matrices, including Σi,j = r^|i−j| for r ∈ (0,1).The assumptions also require eigenvalues bounded away from zero and infinity and a bounded covariance-dependent quantity ρ.Source: §3.3.1 · pp. 10–11
  • The distributional characterizations support confidence intervals and two-sided hypothesis tests for individual parameters using the scaled Lasso noise estimator.For unknown covariance, ΩΣ̂Ω is replaced by MΣ̂M^T.Source: §3.3.1 · pp. 11–12, §3.3.2 · p. 13
  • Sample splitting avoids one covariance assumption but increases variability and discards half of the response variables.The paper also notes that extending the analysis beyond Gaussian designs requires new leave-one-out arguments because column dependencies are not fully captured by Σ.Source: §3.3.1 · p. 12

3.3.2 Unknown covariance

  • For unknown covariance, node-wise Lasso constructs the debiasing matrix M by regressing each design column on the remaining columns.The resulting estimator has a Gaussian-plus-remainder representation with covariance σ^2MΣ̂M^T.Source: §3.3.2 · pp. 12–13
  • With unknown covariance, Gaussian limits require joint sparsity conditions involving coefficient sparsity s0, precision sparsity sΩ, and the covariance parameter ρ.The stated conditions include min(s0,sΩ) ≪ √n/log p and s0 ≪ n/[ρ(log p)^2].Source: §3.3.2 · p. 13

3.4 Numerical illustration

  • The numerical illustration finds δc = 0.57 at ε = 0.2 and shows δc scales roughly linearly with ε for known and unknown covariance.Thus, in the experiment, the required sample size scales approximately linearly with support size s0.Source: §3.4 · pp. 13–14

4 Minimax lower bound on the residual R

This section develops minimax lower bounds for the debiasing residual and shows how coefficient sparsity and precision-matrix sparsity jointly constrain Gaussian inference.

4 Minimax lower bound on the residual R

  • The unknown-covariance case requires a high-probability control of the residual term R through Theorem 3.13.Source: §4 · p. 14
  • The analysis defines confidence-interval minimax risk over parameter spaces containing sparse signals, sparse precision matrices, and bounded precision-matrix norms.Source: §4 · pp. 14, 16
  • Proposition 4.2 gives a minimax lower bound for confidence-interval length that explicitly accounts for sparsity in the precision matrix.It refines the earlier lower bound that omitted precision-matrix sparsity and an infinity-norm constraint.Source: §4 · pp. 16–17
  • The necessary condition for ||R||∞ → 0 is min(s0, sΩ) log p ≲ √n; otherwise the residual is at least of order min(s0, sΩ) log p/√n.Source: §4 · p. 17
  • The residual vanishes under the near-optimal condition s0 ≪ n/(log p)^2 when the precision matrix satisfies sΩ ≲ √n/log p.For sΩ ≪ √n/log p, the residual norm vanishes asymptotically under this coefficient-sparsity condition.Source: §4 · pp. 14, 17

5 Other applications

The paper applies its Gaussian-limit results to Lasso approximation, minimax estimation, and high-dimensional prediction-risk estimation, including a new near-minimax estimator and a high-dimensional SURE result.

5 Other applications

  • The applications include a Lasso denoising characterization, a thresholded estimator with near-minimax ℓ2 risk, and consistency of SURE for standard Gaussian designs.The thresholded estimator is minimax optimal up to a factor 1+o_n(1) for standard Gaussian designs.Source: §5 · p. 17

5.1 A probabilistic approximation result for the Lasso

  • The characterization improves the available Lasso ℓ2-error description by one order of magnitude under the theorem’s Gaussian-design conditions.Source: §5.1 · p. 18
  • The Lasso mean-square error equals the corresponding soft-thresholding denoising error up to higher-order terms, rather than merely satisfying an upper bound.For Σ = I, the associated denoising operator reduces to component-wise soft thresholding.Source: §5.1 · pp. 17–18

5.2 Minimax optimal estimation

  • The two-step estimator computes the Lasso, debiases it using the known precision matrix, and then applies component-wise soft thresholding at a smaller level.Source: §5.2 · p. 18
  • For Σ = I, the two-step estimator achieves minimax-optimal risk up to a factor tending to one, while extending the guarantee to more general Gaussian designs.Source: §5.2 · p. 19

5.3 SURE estimate of the prediction error

  • The paper presents the first proof of SURE consistency in high dimension, albeit in the restricted setting of Gaussian designs.Source: §5.3 · p. 19
  • SURE corrects the empirical prediction-risk estimate, and its error bound is smaller order than the usual correction of order s0σ2/n.Source: §5.3 · pp. 19–20
  • The SURE estimate is well defined for arbitrary covariance, while the proof of consistency applies to Σ = I and simulations support broader validity.The authors report excellent agreement between SURE and the actual prediction error in simulations.Source: §5.3 · p. 20

6 Proof of Theorem 3.8 (known covariance)

The known-covariance proof isolates the Gaussian component of the debiased estimator and controls the remaining terms using leave-one-out perturbation analysis and Lasso error bounds.

6.1 Outline of the proof

  • The proof focuses on one coordinate, removes its design column, and compares the ordinary Lasso solution with a perturbed solution.The perturbation analysis controls how adding the removed column changes the estimator.Source: §6.1 · pp. 20–22
  • The decomposition identifies a Gaussian term Z and separates the remainder into terms R(1), R(2), and R(3).The Gaussian component is Z = ΩXᵀw/√n, while the proof treats the remainder terms separately.Source: §6.1 · p. 22, §6.2 · p. 22

6.2 Technical steps

  • Independence between the residualized column and the reduced design enables conditional Gaussian control of the term involving the reduced Lasso error.Source: §6.1 · p. 22, §6.2 · pp. 23–24
  • Combining the bounds yields √n(bθd − θ*) = Z + R with a controlled remainder, establishing the known-covariance Gaussian-limit claim.Source: §6.2 · pp. 22, 24, 25
  • Corollary 6.2 and related concentration events provide the Lasso prediction-error bounds used to control R(2).Source: §6.2 · pp. 23–24
  • Lemma 6.3 bounds the distance between the ordinary and perturbed Lasso solutions, which controls R(3) after combining sparsity and compatibility arguments.Source: §6.2 · p. 24

6.3 Proof of Lemma 6.3 (perturbation bound)

  • The perturbation lemma is established through deterministic comparisons of the two Lasso objectives and probabilistic lower bounds on the residualized design-column norm.Source: §6.3 · pp. 25–27

7 Proof of Theorem 3.13 (unknown covariance)

The unknown-covariance proof decomposes the debiased estimator into the known-covariance bias plus errors caused by estimating the precision matrix, then bounds those errors using two complementary arguments.

7 Proof of Theorem 3.13 (unknown covariance)

  • The unknown-covariance decomposition separates the debiased estimator into three terms, with I1 equal to the known-covariance bias.Source: §7 · pp. 28–29
  • The additional term I2 is controlled first through duality, combining bounds on the empirical covariance-gradient and the precision-estimation error.Source: §7 · p. 28
  • A second bound on I2 uses a direct control of |MΣ̂ − I|∞ under sparsity of the precision matrix.Source: §7 · pp. 28–29
  • The proof combines the known-covariance result with these two I2 bounds to generalize the Gaussian-limit theorem to unknown sparse precision matrices.Source: §7 · p. 29

A Proof of Lemma 3.5

These appendices establish the lemmas by combining Lasso optimality conditions, restricted-eigenvalue controls, Gaussian-design bounds, and soft-thresholding arguments.

A Proof of Lemma 3.5

  • The Gaussian-design restricted-eigenvalue control follows by bounding fixed subsets and applying a union bound over all subsets of [p].The proof uses the increasing behavior of φmax(k) and a high-probability bound for each subset size.Source: A Proof of Lemma 3.5 · p. 34
  • Lasso stationarity and the event ∥X^T w∥∞ ≤ nλ/4 yield inequalities for the estimation error on the selected support.The proof introduces h = n^-1/2X(θ*−bθ) and combines coordinatewise stationarity with squared-sum bounds.Source: A Proof of Lemma 3.5 · p. 34
  • The proof controls the Lasso support using restricted-eigenvalue quantities and monotonicity of φmax(k), under n ≫ s0(log p)^2.The argument first bounds φmax(|bS|) through |bS| ≤ n, then refines the support-size bound using the sparsity assumption.Source: A Proof of Lemma 3.5 · pp. 34–35

B Proof of Lemma 3.7

F Proof of Preposition 6.7

The proposition proof decomposes the relevant bound into Gaussian and Lasso-error terms, then controls each term using independence, covariance conditions, and high-probability events.

F Proof of Preposition 6.7

  • The proof uses joint Gaussianity and an independent standard-normal vector to control stochastic terms in the proposition’s decomposition.Conditional Gaussian calculations identify z^Tζ_i as normal with variance ∥ζ_i∥^2.Source: F Proof of Preposition 6.7 · pp. 38–39
  • KKT conditions and event-based bounds control the Lasso terms, after which the component inequalities are combined to obtain the proposition’s result.The proof bounds terms individually on the event B and then combines the resulting inequalities.Source: F Proof of Preposition 6.7 · pp. 38–39
  • Covariance assumptions bound ∥Σ_i,T(Σ_T,T)^−1∥1 through a Schur-complement argument and control the associated conditional variance.The proof invokes Conditions (i) and (iii) to obtain the required norm and variance bounds.Source: F Proof of Preposition 6.7 · p. 39

G Proof of Corollary 6.8

The corollary follows by controlling the support sizes of the ordinary and auxiliary Lasso estimators and placing their difference in a restricted cone.

G Proof of Corollary 6.8

  • On the relevant event, the auxiliary Lasso has support size at most C*s0 while the ordinary Lasso has support size at most s0.The constant is C* = (16Cmax/Cmin)(1 − δ)^−2.Source: G Proof of Corollary 6.8 · p. 39
  • The support difference belongs to C((C*+1)s0, 3), which yields the claimed result under the corresponding restricted-event definition.The conclusion uses the fact that θ* is supported on T and the definition of Bδ(n, (C*+1)s0, 3).Source: G Proof of Corollary 6.8 · p. 39

H Sample splitting techniques

Sample splitting removes the dependence between the Lasso estimator and the data used for debiasing, simplifying the proof while retaining asymptotic Gaussianity under the target sparsity regime.

H Sample splitting techniques

  • Sample splitting has drawbacks: its conclusions depend on the random split and it uses the available samples sub-optimally.These limitations motivate the paper’s more careful dependence analysis in the main body.Source: H Sample splitting techniques · p. 40
  • The procedure uses one batch for the Lasso, another for the debiasing matrix, and the first batch again to implement debiasing.The analysis is presented with known precision matrix M = Ω, while extension to node-wise Lasso is stated as straightforward.Source: H Sample splitting techniques · p. 40
  • Splitting makes the design used for debiasing statistically independent of the Lasso estimator, which simplifies control of the remainder term.The responses in the first batch are not used in the stated construction.Source: H Sample splitting techniques · pp. 40–41
  • For s0 = o(n/(log p)^2), the sample-splitting debiased estimator is asymptotically Gaussian under the proposition’s Gaussian-design conditions.The result is stated for a covariance satisfying the technical conditions of Theorem 3.8.Source: H Sample splitting techniques · p. 40
  • The normalized estimator admits the decomposition √n(bθd − θ*) = Z + R, with Z conditionally Gaussian and covariance σ²ΩbΣΩ.The proof then bounds the remainder componentwise using sub-exponential and Bernstein-type inequalities.Source: H Sample splitting techniques · pp. 40–41

I.1 Proof of Proposition 4.1

  • The confidence-interval proof obtains unconditional coverage by integrating the conditional coverage bound over the design.The argument combines the event-based remainder bound with variance and noise-scale controls.Source: §I.1 · pp. 42–43

I.2 Proof of Proposition 4.2

The proof establishes a minimax lower bound by constructing null and alternative Gaussian-regression parameter spaces and comparing their induced data distributions. It also derives high-probability control of Lasso-based support and estimation errors for the subsequent results.

I.2 Proof of Proposition 4.2

  • The lower-bound construction uses s* = min(s0 − 1, sΩ) and a null model with identity precision, while alternatives perturb selected coordinates through a sparse vector δ.The alternatives are embedded through a one-to-one covariance-parameter map and are shown to remain in Γ(s0, sΩ, ρ) under constraints on ν and δ.Source: §I.2 · pp. 43–44
  • Under priors πH0 and πH1 induced from the constructed parameter spaces, the marginal data distributions f0 and f1 are compared using total variation and χ2 distances.The passages define f0 and f1 as marginal data densities under the respective priors.Source: §I.2 · pp. 44–45
  • The resulting expected confidence-interval length is bounded below at rate min(ρ√(log p/n), s*(log p/n)) together with the 1/√n lower-bound regime.Equation (156) applies over a large subset of Γ(s0, sΩ), making the statement stronger than a minimax lower bound applying only globally.Source: §I.2 · p. 45

J.1 Proof of Theorem 5.1

  • Theorem 5.1 controls the Lasso-based decomposition through KKT conditions, support-size bounds, and the remainder term R = √n(ΩΣ̂ − I)(θ* − θ̂).The proof concludes by applying Theorem 3.8 after bounding the supports of θ̂ and the auxiliary estimator θ̂0.Source: §J.1 · pp. 45–46

J.2 Proof of Corollary 5.2

  • Corollary 5.2 obtains concentration of the auxiliary estimator's error by combining support containment, soft-thresholding Lipschitzness, Gaussian isoperimetry, and spectral control of X_S.The argument uses the high-probability event ‖X_S‖2 ≤ 2(√s0 + √n) and bounds the resulting error around its expectation.Source: §J.2 · p. 47

K Proof of Theorem 5.3

These proofs control Gaussian-design error terms through soft-thresholding, concentration, and support-size bounds. They establish the required high-probability events and conclude that the remaining approximation error vanishes under the stated sparsity and logarithmic growth conditions.

K Proof of Theorem 5.3

  • Theorem 5.3's proof bounds the auxiliary supports by s0Ln with high probability and combines the resulting estimates with equations (192), (198), and (203).The same support argument is applied to both auxiliary estimators, while the variance terms use the χ2 distribution of normalized Gaussian quadratic forms.Source: K Proof of Theorem 5.3 · pp. 48, 50
  • Under the assumptions used for Theorem 5.3, Gaussian concentration and soft-thresholding arguments control the estimator's support and error terms with high probability.The proof uses Gaussian isoperimetry, the Bai–Yin law, chi-squared tails, and the condition log(p/s0)^3/n → 0.Source: K Proof of Theorem 5.3 · pp. 48–50

L Proof of Theorem 5.4

  • The proof analyzes term Δ1, computes its noise expectation using Stein’s lemma, and controls it via Gaussian concentration after a Lipschitz extension.Source: L Proof of Theorem 5.4 · pp. 52–54
  • The Gaussian-design proof of Theorem 5.4 is completed by choosing Ln = (n/(s0(log p)^2))^1/4, which makes εn → 0.The auxiliary design event satisfies P(X ∈ G1(M)) ≥ 1 − p^-10, and support containment holds with probability at least 1 − p^-3.Source: L Proof of Theorem 5.4 · pp. 51, 57

Related papers

Loading 1508.02757v3…