PaperlayerView exact revision on arXiv

Source-linked AI summary

Confidence Intervals and Hypothesis Testing for High-Dimensional Regression

Adel Javanmard, Andrea Montanari

arXiv:1306.3171v2stat.MEcs.ITcs.LG

TL;DR

High-dimensional models lack generally accepted procedures for quantifying uncertainty because estimator distributions are often difficult to characterize. The paper develops an efficient de-biasing procedure for confidence intervals and p-values, achieving nearly optimal interval size and constant-optimal testing efficiency.

  • Problem

    High-dimensional statistics lacks broadly accepted procedures for constructing confidence intervals and p-values because estimator distributions are generally difficult to characterize.

  • Method

    The paper constructs de-biased estimators and selects a matrix M to control bias, non-Gaussian error, and variance without requiring special covariance structure.

  • Results

    The confidence interval size is of order σ/√n and constant-optimal testing efficiency is bounded below by 1/ηΣ,s0.

  • Takeaways & Limitations

    The procedure applies to general covariance structures under standard compatibility conditions and yields an asymptotically unbiased de-biased estimator.

  • Takeaways & Limitations

    Large-scale inference remains challenging because aggregating p-values across a growing number of coordinates requires additional treatment.

Abstract

from arXiv · show

Fitting high-dimensional statistical models often requires the use of non-linear parameter estimation procedures. As a consequence, it is generally impossible to obtain an exact characterization of the probability distribution of the parameter estimates. This in turn implies that it is extremely challenging to quantify the \emph{uncertainty} associated with a certain parameter estimate. Concretely, no commonly accepted procedure exists for computing classical measures of uncertainty and statistical significance as confidence intervals or $p$-values for these models. We consider here high-dimensional linear regression problem, and propose an efficient algorithm for constructing confidence intervals and $p$-values. The resulting confidence intervals have nearly optimal size. When testing for the null hypothesis that a certain parameter is vanishing, our method has nearly optimal power. Our approach is based on constructing a `de-biased' version of regularized M-estimators. The new construction improves over recent work in the field in that it does not assume a special structure on the design matrix. We test our method on synthetic data and a high-throughput genomic data set about riboflavin production rate.

1 Introduction

High-dimensional regularized estimators enable estimation when p exceeds n, but their bias and analytically intractable distributions make classical confidence intervals and p-values difficult. The paper develops a computationally efficient de-biasing procedure that achieves nearly optimal interval size and testing power under general covariance structures.

  • 1 Introduction: When p > n, rank deficiency prevents ordinary least squares, motivating biased sparse estimators such as the LASSO.The LASSO promotes sparse reconstructions through an ℓ1 penalty.
  • 1 Introduction: The LASSO can achieve near-oracle estimation error, but its distribution is generally intractable and its bias prevents simple confidence intervals and p-values.For n = Ω(s0 log p), its squared ℓ2 error is O(s0σ2(log p)/n).
  • 1 Introduction: The de-biased estimator is approximately Gaussian, enabling classical confidence intervals and p-values despite high dimensionality.Its construction controls both the bias and Gaussian variance through the choice of M.
  • 1 Introduction: 95% confidence intervals have size of order σ/√n, matching the minimum size achievable when the support is known in advance.The noise level σ may be replaced by a consistent estimator.
  • 1 Introduction: The method chooses M to minimize the de-biased estimator’s error and variance, so it applies to general covariance structures under standard compatibility conditions.Earlier approaches required sparse covariance or sparse inverse covariance assumptions.
  • 1 Introduction: The testing procedure has constant-optimal asymptotic efficiency for Gaussian random designs, while its power is established through a general lower bound.For random designs, detectable coefficients can be as small as c′(α, β)σ/√n.
  • 1 Introduction: The proofs require stricter sparsity, s0 = o(√n/log p), than consistency alone, and success under the weaker s0 = o(n/log p) regime remains open.This sparsity condition is also used in related work, sometimes with additional assumptions on Σ^-1.

2 Compensating the bias of the LASSO

The paper characterizes a de-biased LASSO estimator as a Gaussian term plus a controlled bias term, using a matrix chosen to manage both error and variance. Under suitable design and sparsity conditions, the estimator is asymptotically unbiased and improves on LASSO bias without requiring sparse inverse covariance.

  • Estimator characterization: Generalized coherence measures how effectively the pair (X, M) controls the de-biasing error.Its minimum can be computed efficiently because the associated optimization is convex, specifically a linear program.
  • Estimator characterization: The de-biased estimator is analyzed through a decomposition into a zero-mean Gaussian term and a bias term controlled by design-dependent quantities.The Gaussian term has covariance σ^2MΣ̂M^T, while the bias term depends on √n(MΣ̂−I)(θ0−θ̂n).
  • Random-design guarantees: For random designs, the compatibility and generalized coherence conditions hold with probability rapidly converging to one under subgaussian assumptions and sufficient sample size.The stated assumptions bound the covariance eigenvalues and require independent subgaussian rows after whitening.
  • Bias reduction: ∥∆∥∞ = O(s0 log p/√n) with high probability, and becomes o(1) when s0 = o(√n/log p), making θ̂u asymptotically unbiased.The paper also states that θ̂n is asymptotically biased while θ̂u is asymptotically unbiased in a corresponding identity-covariance setting.
  • Bias reduction: When s0 is significantly smaller than √n/log p, the de-biased estimator’s bias is much smaller than the LASSO estimator’s bias.For larger sparsity, the paper reports a different comparison in which the LASSO bias term can dominate.

3 Statistical inference

The paper develops asymptotically valid confidence intervals and hypothesis tests for high-dimensional linear regression by debiasing regularized estimators. Under sparsity and design assumptions, the tests achieve nearly optimal power, while confidence regions extend to low-dimensional projections; simultaneous large-scale inference remains challenging.

  • Confidence intervals: The procedure assumes sparsity s0 = o(√n/ log p) and constructs a debiased estimator using a matrix M obtained from a convex program.The convex program is computationally comparable to nodewise LASSO, while its objective minimizes the variance of the noise term.
  • Confidence intervals: The bias of bθu has largest entry of order (s0 log p)/n, which is compared with the estimator’s standard deviation.A consistent noise-level estimator is used in the asymptotic distribution and confidence-interval construction.
  • Confidence intervals: The method yields asymptotically valid confidence intervals for individual coefficients under the stated design assumptions and a consistent noise-level estimator.The assumptions include bounded covariance eigenvalues, subgaussian transformed design rows, and the sparsity condition.
  • Hypothesis testing: The testing framework evaluates H0,i: θ0,i = 0 against θ0,i ≠ 0 using p-values, with significance level and power defined through type I and type II errors.Nontrivial power requires alternatives bounded away from zero, |θ0,i| > γ.
  • Hypothesis testing: The test has nearly optimal power: it matches the power of any other test when that test uses a sample size increased by a factor ηΣ,s0.Equivalently, its asymptotic efficiency is at least 1/ηΣ,s0.
  • Simultaneous confidence intervals: The same lemma-based approach constructs valid confidence regions for low-dimensional projections, whereas large-scale inference with |R(n)| →∞ remains challenging because p-value aggregation is difficult.The paper explicitly identifies simultaneous large-scale inference as a more challenging regime.

4 Non-Gaussian noise

The paper extends its inference procedure beyond Gaussian noise by modifying the optimization problem to ensure a Lindeberg condition. Under moment and independence assumptions, the resulting coordinates are asymptotically Gaussian, supporting valid confidence intervals and p-values.

  • Non-Gaussian extension: Under the Lindeberg condition, the normalized noise contribution converges conditionally to N(0, 1), enabling valid p-values.The paper states that the proposed confidence intervals remain valid in this broader setting as well.
  • Non-Gaussian extension: For non-Gaussian noise, the optimization problem is modified to ensure that the Lindeberg condition holds.The noise variables are assumed independent, centered, have variance σ^2, and satisfy a bounded higher-moment condition.
  • Inference guarantees: For sparsity level s0 = o(√n/ log p), the method provides an asymptotic two-sided confidence interval for each θ0,i.The corresponding p-value is also constructed asymptotically under the same framework.

5 Numerical experiments

Synthetic and riboflavin experiments evaluate confidence-interval coverage, interval length, p-value calibration, false-positive control, and testing power. The proposed method produces approximately Gaussian statistics, uniformly distributed null p-values, and higher true-positive rates than conservative alternatives.

  • Synthetic data: The simulations use Gaussian designs, sparse coefficients, and 20 independent measurement-error realizations per configuration.The design covariance is circulant, coefficients are nonzero on a uniformly random support, and errors are Gaussian.
  • Synthetic data: The constructed 95% confidence intervals are evaluated by average length and empirical coverage for active and inactive parameters.Figure 1 displays intervals for 100 of 1,000 parameters in configuration (n, p, s0, b) = (1000, 600, 10, 1).
  • Synthetic data: The proposed method achieves false-positive rates close to α = 0.05 and higher true-positive rates than multisample-splitting and ridge-type projection.The competing methods are conservative: multisample-splitting has false-positive rate 0 across the reported configurations, while ridge-type projection remains below α.
  • Synthetic data: The Q-Q plot shows Z statistics close to the standard-normal reference line, supporting the claimed Gaussianity of their entries.The reported configuration is (n, p, s0, b) = (1000, 600, 10, 1).
  • Real data: At FWER-adjusted 5% significance, the proposed method identifies two riboflavin genes, compared with one for multisample-splitting and none for ridge-type projection.The two genes are YXLD-at and YXLE-at; the competing procedures produce more conservative, larger p-values in this example.

6 Proofs

The proofs decompose the de-biased estimator into a Gaussian component and a controlled error term, then establish the distributional results needed for inference. They use concentration bounds, restricted-eigenvalue arguments, and Gaussian or triangular-array central limit theorems under stated design and sparsity conditions.

  • Proof strategy: Substituting the linear model into the de-biased estimator separates it into a Gaussian term and an error term.For Gaussian noise, the Gaussian term is linear in W and has the stated covariance.
  • Proof strategy: Concentration and restricted-eigenvalue arguments bound the error term with high probability under the stated assumptions.The proof uses Bernstein-type inequalities and union bounds over coordinates or coordinate pairs.
  • Distributional result: The Gaussian component has conditional covariance σ2M bΣM^T, yielding asymptotically Gaussian coordinates for the de-biased estimator.The proof identifies Z = MX^TW/√n and establishes its coordinatewise limiting behavior.
  • Inference: The confidence intervals and p-values are valid because the normalized statistics converge to the standard normal distribution.The result is extended to independent non-Gaussian noise with bounded moments under the stated assumptions.
  • Assumptions: The proof requires sparsity condition s0 = o(√n/log p) and feasibility of the optimization problems defining M.The inverse covariance rows provide feasible solutions with high probability under the covariance and design assumptions.

A.1 Proof of Lemma 3.1

The proof bounds the optimization problem’s objective by examining feasible vectors and then optimizes the resulting scalar bound. The optimum is attained by a scaled coordinate vector.

  • Optimization bound: The constraint is reduced to a bound involving the i-th component by considering that component directly.This produces a feasible-point lower bound for the optimization problem.
  • Optimization bound: The minimum over the auxiliary vector is attained at m = c e_i/2.Substituting this choice reduces the bound to a scalar optimization over c.
  • Optimization bound: Optimizing over c gives the claimed bound with c = 2(1 − µ)/bΣii.The selected c is the optimal scalar for the derived bound.

A.2 Proof of Lemma 6.3

The proof establishes asymptotic normality for the normalized statistics under independent non-Gaussian errors. It verifies a Lindeberg condition and shows that the optimization problems are feasible with high probability.

  • Central limit theorem: Conditional on X, the summands in the normalized statistic are independent and centered.Their conditional structure supports application of a triangular-array central limit theorem.
  • Central limit theorem: The Lindeberg condition follows from bounded moments of the noise and a positive lower bound on the normalization factor.Under the stated assumptions, Zi|X converges weakly to the standard normal distribution.
  • Feasibility: The proof establishes feasibility of all p optimization problems by showing that rows of Σ−1 satisfy the constraints with high probability.This uses concentration of Σ−1bΣ around the identity.
  • Feasibility: The sparsity condition s0 = o(√n/log p) ensures the dimensional-growth relation needed for eventual almost-sure feasibility.The proof states that this condition implies p = e^{o(n^{2β})}.

B.1 Proof of Corollary 2.7

The proof applies Theorem 2.3 to obtain the stated result under the specified design conditions, then derives the probability estimate using Theorem 2.4 and a union bound.

  • Theorem 2.3 applies to designs in En(√Cmin/2, s0, 3/2) ∩ Gn(a).
  • The resulting expression coincides with Eq. (21).
  • The probability estimate in Eq. (22) follows from Theorem 2.4 using a union bound.

B.2 Proof of Corollary 2.8

The proof combines Theorem 2.4 with properties of the LASSO solution and the de-biased estimator to establish the stated bounds and probability result.

  • Theorem 2.4.(a) is applied with Cmin = Cmax = κ = 1.
  • The proof concludes with the desired probability bound in Eq. (24).
  • The LASSO solution bθn uses λ = σ(c2 log p)/n.
  • The de-biased estimator admits the representation bθ∗ = θ0 + 1/√n Z + 1/√n ∆, with Z|X ∼ N(0, σ2bΣ).
  • The proof reduces Eq. (23) to showing that ∥E{v(bθn)|X}∥∞ ≥ 2/3.
  • Equations (26) and (27) follow by substituting λ = cσ(c2 log p)/n into Eq. (23).

C Proof of Lemma 3.3

The lemma bounds the relevant terms uniformly over sparse parameter vectors under the event En and shows that both remaining error contributions vanish asymptotically.

  • The event En is defined using φ0 = C1/2 and K = 1.1 for sufficiently large n.
  • The argument assumes n ≥ ν0 s0 log(p/s0) and s0 = o(√n/ log p).
  • The first term is bounded uniformly over θ0 with ∥θ0∥0 ≤ s0 using a result from.
  • The right-hand side is independent of θ0, while its first and second terms vanish through Gaussian and chi-squared tail bounds.

D Proof of Theorem 3.9

The proof uses Bonferroni’s inequality and Gaussian normalization to control the target probability, while the remaining terms vanish by Theorems 2.4 and 2.5.

  • The argument works over Fp,s0 = {x ∈ Rp : ∥x∥0 ≤ s0} for fixed ε ∈ (0, 1/10).
  • Bonferroni’s inequality is applied with zα(ε) ≡ (1 − ε)Φ−1.
  • The normalized variable eZi is standard normal, and ∆i is specified by Eq. (16).
  • The proof uses [M bΣMT]i,i ≥ 1/(4bΣii) for sufficiently large n and µ = a(log p)/n → 0.
  • The second term vanishes by Theorem 2.4.(a), and the last term is zero by Theorem 2.5 under √n/ log(p) ≥ s0 ≥ 1.
  • The claim follows by letting ε → 0.
Loading 1306.3171v2…