PaperlayerView exact revision on arXiv

Source-linked AI summary

Confidence Intervals for High-Dimensional Linear Regression: Minimax Rates and Adaptivity

T. Tony Cai, Zijian Guo

arXiv:1506.05539v2math.ST

TL;DR

The paper asks how short confidence intervals for high-dimensional linear regression functionals can be while maintaining coverage, especially when sparsity is unknown. It derives oracle minimax rates and studies adaptive procedures across sparsity levels. Adaptation generally fails because bias is difficult to learn accurately, though known covariance and noise can restore adaptation for sparse loadings.

  • Problem

    The paper investigates whether confidence intervals can achieve oracle-optimal lengths while maintaining coverage and adapting to unknown sparsity across nested sparse parameter spaces.

  • Method

    The paper derives minimax upper and lower bounds, constructs rate-optimal confidence intervals, and analyzes adaptive inference for sparse and dense linear-function loadings under stated design and noise conditions.

  • Results

    Adaptation is generally impossible across sparsity levels because confidence intervals must be long on a large subset of parameter space, while known Σ = I and σ = σ0 restore full-range adaptation for sparse loadings.

  • Takeaways & Limitations

    Confidence-interval construction is substantially harder than estimation, and prior knowledge of the design covariance and noise level is especially useful for sparse-loading functionals.

  • Takeaways & Limitations

    For dense loadings, de-biasing can inflate variance and produce unnecessarily long intervals; achieving minimax length in the middle loading-sparsity regime remains open.

Abstract

from arXiv · show

Confidence sets play a fundamental role in statistical inference. In this paper, we consider confidence intervals for high dimensional linear regression with random design. We first establish the convergence rates of the minimax expected length for confidence intervals in the oracle setting where the sparsity parameter is given. The focus is then on the problem of adaptation to sparsity for the construction of confidence intervals. Ideally, an adaptive confidence interval should have its length automatically adjusted to the sparsity of the unknown regression vector, while maintaining a prespecified coverage probability. It is shown that such a goal is in general not attainable, except when the sparsity parameter is restricted to a small region over which the confidence intervals have the optimal length of the usual parametric rate. It is further demonstrated that the lack of adaptivity is not due to the conservativeness of the minimax framework, but is fundamentally caused by the difficulty of learning the bias accurately.

1. Introduction.

The paper studies confidence intervals for sparse high-dimensional linear regression functionals, establishing oracle minimax lengths and limits of adaptation to unknown sparsity. It shows that adaptivity generally fails because accurately learning estimator bias is difficult, with important differences between sparse and dense loadings and between known and unknown design information.

  • Motivation: Confidence intervals require the stronger sparsity condition k ≪ √n log p, whereas point-estimation consistency only requires k ≪ n log p.This gap motivates studying inference in moderate-sparse regions where estimation remains consistent.
  • Scope: The paper develops confidence intervals for linear functionals T(β) = ξ⊺β, covering sparse loadings and dense loadings as distinct regimes.Individual coordinates β_i are prototypical sparse-loading functionals, while Pp i=1 βi represents a dense-loading case.
  • Oracle rates: In the oracle setting, the minimax expected length for confidence intervals for β_i is of order 1/√n + k log p/n, and honest rate-optimal intervals depending on k are constructed.The construction includes the moderate-sparse region log p ≪ k ≲ n log p.
  • Adaptivity: Adaptation to unknown sparsity is impossible for β_i except in the ultra-sparse region k ≲ √n log p, where the optimal interval length is the parametric rate 1/√n.For Pp i=1 βi, adaptation is impossible even in the ultra-sparse region.
  • Adaptivity: Strong non-adaptivity results show that long intervals are required on a large subset of parameter space, not merely at isolated worst-case points, because estimator bias is hard to learn accurately.This establishes that the limitation is not simply an artifact of minimax worst-case analysis.
  • General functionals and known information: Sparse and dense loadings exhibit different behavior: sparse-loadings permit ultra-sparse-only adaptation under unknown covariance and noise, whereas dense-loadings permit no adaptation even there.With known Σ = I and σ = σ0, sparse-loading rates lose their k dependence and adaptation is possible over k ≲ n log p, while dense-loading impossibility remains.

2. Formulation for adaptive confidence interval problem.

The paper formulates adaptive confidence intervals for linear functionals in a Gaussian-design high-dimensional regression model. It defines minimax expected-length benchmarks over nested sparsity spaces and asks whether intervals can adapt while retaining coverage.

  • 2.2. Framework for adaptivity of confidence intervals: The model has Gaussian random-design observations with unknown covariance-related precision matrix and unknown noise level.The regression signal, precision matrix, and noise level jointly form the parameter.
  • 2.2. Framework for adaptivity of confidence intervals: The target is the linear functional T(β) = ξ⊺β for a prespecified loading vector ξ ∈ R^p.The coordinate functional β_i is a special case when ξ is a standard basis vector.
  • 2.2. Framework for adaptivity of confidence intervals: A (1 − α)-level confidence interval must maintain coverage over Θ while its expected length is evaluated over the relevant parameter space.The interval length is defined as the upper endpoint minus the lower endpoint.
  • 2.2. Framework for adaptivity of confidence intervals: The adaptive benchmark L*α(Θ1, Θ, T) is the smallest maximum expected length over Θ1 among intervals valid over Θ.This quantity measures adaptation between nested spaces Θ1 ⊆ Θ.
  • 2.2. Framework for adaptivity of confidence intervals: Rate-optimal adaptation requires one interval to achieve the optimal expected-length rates on both nested spaces while preserving coverage over the larger space.If the adaptive benchmark exceeds the smaller-space minimax benchmark in rate, such adaptation is impossible.
  • 2.2. Framework for adaptivity of confidence intervals: Θ(k) denotes the class of k-sparse regression vectors under bounded-eigenvalue and bounded-noise regularity conditions.The parameter space also constrains the precision matrix eigenvalues and the noise level.
  • 2.2. Framework for adaptivity of confidence intervals: The paper asks for the oracle minimax length when k is known and whether intervals can adapt between Θ(k1) and Θ(k) when k1 ≪ k.The intended adaptive interval would automatically adjust its length to the true sparsity level.
  • 2.2. Framework for adaptivity of confidence intervals: The analysis distinguishes sparse and dense loading regimes because the minimax rate and adaptivity also depend on the sparsity of ξ.These regimes are treated separately in later sections.

3. Minimax rate and adaptivity of confidence intervals for sparse loading linear functionals.

For sparse-loading linear functionals, the paper derives minimax expected-length rates in the known-sparsity setting and constructs confidence intervals attaining them. The analysis establishes both lower and upper bounds under the stated sparsity regime.

  • 3. Minimax rate and adaptivity of confidence intervals for sparse loading linear functionals: The section derives minimax expected-length convergence rates for ξ⊺β when the regression sparsity k is known.Both minimax upper and lower bounds are established in the sparse-loading regime.
  • 3. Minimax rate and adaptivity of confidence intervals for sparse loading linear functionals: The sparse-loading regime is analyzed under k ≤ c min{p^γ, n log p} for constants c > 0 and 0 ≤ γ < 1.This condition defines the sparsity range used for the theorem.
  • 3. Minimax rate and adaptivity of confidence intervals for sparse loading linear functionals: Theorem 1 states the minimax expected-length rate for (1 − α)-level intervals over Θ(k) in the sparse-loading regime.The theorem provides the target rate for the construction that follows.
  • 3. Minimax rate and adaptivity of confidence intervals for sparse loading linear functionals: Theorem 1 is proved through separate minimax upper-bound and lower-bound arguments.The upper-bound step constructs an interval with the required coverage and controlled expected length.

2. Minimax lower bound: we show that for some constant c > 0

The paper constructs oracle confidence intervals and then studies whether their lengths can adapt to unknown sparsity. It finds that rate-optimal adaptation generally fails beyond the ultra-sparse region, with strong non-adaptivity across many parameter points.

  • 2. Minimax lower bound: we show that for some constant c > 0: The constructed interval is centered at a de-biased scaled Lasso estimator, with a length construction that differs from earlier procedures when k is larger.The estimator uses a constrained score vector and incorporates a bias-reduction term.
  • 2. Minimax lower bound: we show that for some constant c > 0: The oracle interval has the desired coverage property and achieves the minimax length in the sparse-loading regime.This completes the minimax upper-bound construction.
  • 2. Minimax lower bound: we show that for some constant c > 0: The oracle construction requires prior knowledge of k, motivating the question of adaptive intervals with guaranteed coverage and automatically adjusted length.This sparsity information is typically unavailable in applications.
  • 2. Minimax lower bound: we show that for some constant c > 0: For k1 ≪ k, rate-optimal adaptation is ruled out beyond the ultra-sparse region, while the ultra-sparse region remains the only possible adaptation range.The boundary is expressed through k ≲ √n log p.
  • 2. Minimax lower bound: we show that for some constant c > 0: In the ultra-sparse region k ≲ √n log p, optimal expected length is of order 1/√n and does not depend on the specific sparsity level.These adaptation facts are illustrated in Figure 1.
  • 2. Minimax lower bound: we show that for some constant c > 0: Strong non-adaptivity means that an interval cannot be simultaneously rate-optimal over Θ(k1) and Θ(k) when k lies in the moderate-sparse range.The impossibility applies despite the interval's required coverage over the larger parameter space.
  • 2. Minimax lower bound: we show that for some constant c > 0: The non-adaptivity is strong because intervals must be long on a large subset of parameter points, not merely at isolated unlucky points.The result is therefore not explained by minimax worst-case behavior at only a few points.
  • 2. Minimax lower bound: we show that for some constant c > 0: For the coordinate functional β1, the minimax length is parametric in the ultra-sparse region but is of order k log p/n in the moderate-sparse region.The moderate-sparse rate is larger than 1/√n, so parametric-length intervals can lose coverage there.

4. Minimax rate and adaptivity of confidence intervals for dense loading linear functionals.

For dense loading functionals, the paper establishes minimax expected-length results and shows that adaptation across substantially different sparsity levels is impossible. It also develops a computationally feasible construction under additional assumptions.

  • Minimax rate: Theorem 4 establishes the minimax expected length for confidence intervals of ξ^Tβ in the dense loading regime.The result applies under the stated sparsity and design assumptions.
  • Minimax rate: The dense-loading minimax rate differs significantly from the sparse-loading rate ∥ξ∥2(1/√n + k√(log p/n)).The paper explicitly contrasts the dense-loading result with the sparse-loading rate from Theorem 1.
  • Confidence-interval construction: A confidence interval achieving the dense-loading minimax rate is constructed and shown to have the desired coverage property.The construction is based on the definitions and estimators introduced in this section.
  • Confidence-interval construction: In the dense-loading regime, de-biasing is unsuitable because obtaining a near-unbiased estimator would substantially increase variance and produce an unnecessarily long interval.The dense-loading interval is therefore not centered at a de-biased estimator.
  • Adaptivity: Rate-optimal adaptation between sparsity levels k1 and k is impossible when k1 ≪ k, while adaptation is possible in the ultra-sparse region for sparse loadings.The paper identifies the moderate-sparse region as one where adaptation is not possible for sparse loadings.
  • Special case: sum of coefficients: The paper also treats the sum of all coefficients as a special dense-loading case and relates its minimax and adaptivity behavior to the general results.This case is discussed separately after the general dense-loading analysis.

5. Confidence intervals for linear functionals with prior knowledge Ω= I and σ = σ0.

With prior knowledge that Ω = I and σ = σ0, the paper compares minimax rates and adaptivity for sparse and dense loadings. Known design precision and noise level make sparse-loading intervals parametric and adaptive, but do not improve the dense-loading minimax rate.

  • Sparse loading: With Ω = I and σ = σ0 known, sparse-loading confidence intervals have minimax expected length at the parametric rate and do not depend on k.The result concerns confidence intervals for ξ^Tβ over Θ(k, I, σ0).
  • Sparse loading: Adaptive confidence intervals are possible over the full range k ≤ c n/log p in the known-Ω and known-σ sparse-loading setting.The paper contrasts this with the unknown-Ω and unknown-σ case.
  • Construction: A de-biasing construction based on sample splitting is shown to have valid coverage and achieve the known-parameter minimax length.The samples are split into two subsamples before constructing the interval.
  • Dense loading: In the dense-loading regime, knowing Ω = I and σ = σ0 does not improve the minimax rate, although it reduces the cost of adaptation.Adaptive confidence intervals remain impossible when k1 ≪ k.
  • Comparison: The paper concludes that knowledge of Ω and σ is highly useful for sparse loadings but of limited use for dense loadings.For dense loadings, the minimax rate and lack of adaptivity remain unchanged relative to the unknown-parameter case.

6. Discussion.

The discussion emphasizes that confidence-interval construction is harder than estimation because sparsity knowledge is generally needed for honest inference. It also distinguishes sparse from dense loadings and identifies open theoretical problems.

  • Adaptivity: For unknown Ω and σ, knowing the sparsity k is crucial for constructing honest confidence intervals, except in the ultra-sparse sparse-loading region.The paper characterizes the resulting adaptivity findings as largely negative.
  • Known parameters: With Ω = I and σ = σ0 known, sparse-loading intervals have length of order ∥ξ∥2/√n and adaptivity is achievable across the full allowed sparsity range.The dense-loading regime does not receive the same minimax improvement.
  • Construction: De-biasing is useful for sparse loadings but unsuitable for dense loadings because reducing bias substantially increases variance.The paper links this constructional difference to the distinct behavior of the two loading regimes.
  • Open problems: An open problem is constructing minimax-length confidence intervals when the loading sparsity q lies in the stated middle regime.The discussion specifies the range cp^γ ≤ q ≤ cp^(2γ+ς).
  • Open problems: The paper also calls for a general adaptation theory for confidence intervals in the non-convex high-dimensional setting.Existing adaptation theory cited in the discussion relies on convex parameter spaces.

7. Proofs.

The proofs combine a nested-space adaptivity lemma with transformations, mixture-distance control, and lower-bound arguments. They also establish coverage and expected-length properties for the constructed intervals.

  • Lower bounds: The central lower-bound tool compares two nested parameter spaces and converts distinguishability limits into a confidence-interval length lower bound.The lemma uses priors on the two spaces and total-variation distance between their induced marginal distributions.
  • Lower bounds: The lemma states that when the functional takes values μ0 and μ1 on the two spaces, expected interval length is at least |μ1 − μ0| under guaranteed coverage.This provides the basic separation argument used in the adaptivity proofs.
  • Transformation: The transformed parameterization maps the original regression problem to one involving ψ, Γ, and σ, preserving correspondence between confidence intervals for ξ^Tβ and ψ1.The first transformed coefficient satisfies ψ1 = ξ^Tβ/∥ξ∥2.
  • Dense-loading lower bound: For dense-loading lower bounds, the proof constructs an alternative hypothesis space, controls total variation through a mixture prior, and calculates the functional separation.The construction verifies that the alternatives remain in the target parameter space.
  • Parameter-space verification: Spectral-norm control and Weyl’s inequality establish that the constructed alternatives satisfy the required eigenvalue conditions.This is used to show that the alternative space is contained in the target class.
  • Upper bounds: The constructed confidence interval is proved to have the required coverage and minimax expected length under the stated sparsity condition.A proposition establishes both properties for the interval constructed in the proof.

SUPPLEMENTARY MATERIAL

The supplement provides detailed proofs for the adaptivity lower bound and minimax upper bound for confidence intervals targeting ξ⊺β with dense loading ξ. It establishes these rates and adaptivity properties under prior knowledge that Ω = I and σ = σ0.

  • Supplementary material: The supplement gives detailed proofs of the adaptivity lower bound for confidence intervals of ξ⊺β with dense loading ξ.The result is developed for the high-dimensional linear regression setting described in the paper.
  • Supplementary material: It also proves the minimax upper bound for confidence intervals targeting the same linear functional.The supplement focuses on the theoretical bounds underlying the paper’s confidence-interval results.
  • Supplementary material: The minimax rates and adaptivity results assume prior knowledge that Ω = I and σ = σ0.These conditions define the specialized setting treated in the supplement.
Loading 1506.05539v2…