Source-linked AI summary
Minimax rates of estimation for high-dimensional linear regression over $\ell_q$-balls
Garvesh Raskutti, Martin J. Wainwright, Bin Yu
TL;DR
The paper studies minimax estimation in high-dimensional linear regression when the regression vector lies in an ℓq-ball. It combines information-theoretic lower bounds with constructive least-squares upper bounds, determining ℓ2 and prediction minimax rates under suitable design conditions and comparing ℓ0 and ℓ1 methods.
Problem
High-dimensional regression with d ≥ n requires structural assumptions for consistent estimation, motivating minimax analysis under sparsity constraints.
Method
The paper derives lower bounds using Fano’s inequality and metric entropy of ℓq-balls, and upper bounds through direct analysis of least-squares over ℓq-balls.
Results
The ℓ2 and ℓ2-prediction minimax rates are determined up to constant factors, while lower bounds are established for ℓp losses with p ∈ [1, ∞] and p ≠ q.
Takeaways & Limitations
For q = 0, oracle least-squares over the ℓ0-ball can succeed under milder design conditions than computationally efficient ℓ1-based relaxations.
Takeaways & Limitations
The analysis assumes independent Gaussian noise; extensions to heavier-tailed or dependent noise remain open.
Abstract
from arXiv · showhide
Consider the standard linear regression model $\y = \Xmat \betastar + w$, where $\y \in \real^\numobs$ is an observation vector, $\Xmat \in \real^{\numobs \times \pdim}$ is a design matrix, $\betastar \in \real^\pdim$ is the unknown regression vector, and $w \sim \mathcal{N}(0, σ^2 I)$ is additive Gaussian noise. This paper studies the minimax rates of convergence for estimation of $\betastar$ for $\ell_\rpar$-losses and in the $\ell_2$-prediction loss, assuming that $\betastar$ belongs to an $\ell_{\qpar}$-ball $\Ballq(\myrad)$ for some $\qpar \in [0,1]$. We show that under suitable regularity conditions on the design matrix $\Xmat$, the minimax error in $\ell_2$-loss and $\ell_2$-prediction loss scales as $\Rq \big(\frac{\log \pdim}{n}\big)^{1-\frac{\qpar}{2}}$. In addition, we provide lower bounds on minimax risks in $\ell_{\rpar}$-norms, for all $\rpar \in [1, +\infty], \rpar \neq \qpar$. Our proofs of the lower bounds are information-theoretic in nature, based on Fano's inequality and results on the metric entropy of the balls $\Ballq(\myrad)$, whereas our proofs of the upper bounds are direct and constructive, involving direct analysis of least-squares over $\ell_{\qpar}$-balls. For the special case $q = 0$, a comparison with $\ell_2$-risks achieved by computationally efficient $\ell_1$-relaxations reveals that although such methods can achieve the minimax rates up to constant factors, they require slightly stronger assumptions on the design matrix $\Xmat$ than algorithms involving least-squares over the $\ell_0$-ball.
1 Introduction
The paper frames sparse high-dimensional linear regression as an inference problem where the dimension can match or exceed the sample size, then develops minimax analyses for general designs and ℓq-structured coefficients.
- Problem setting: High-dimensional inference studies estimation when the ambient dimension d is large relative to the sample size n.Without additional structure, consistent estimation is often impossible unless d/n converges to zero.
- Problem setting: Sparsity and related structural assumptions make inference with d ≥ n analyzable, motivating extensive study of ℓ1-based relaxations.The paper focuses on linear regression with a regression vector constrained by an ℓq-ball.
- Scope and contributions: The analysis applies to general design matrices X and recovers the Gaussian-sequence-model scaling when specialized to X = √n I_n.For general designs, ℓ2-loss and ℓ2-prediction loss can behave differently.
- Scope and contributions: For hard sparsity q = 0, ℓ1-methods can attain minimax ℓ2-rates but require stronger design conditions than least-squares over the ℓ0-ball.The comparison includes methods such as the Lasso and Dantzig selector.
2 Main results
The paper characterizes minimax estimation and prediction risks over ℓq-balls under design-matrix conditions, separating identifiability, curvature, and metric-entropy effects. It establishes matching ℓ2 rates under suitable assumptions and contrasts estimation with prediction, especially for hard sparsity.
- Problem and assumptions: The analysis targets d ≫ n linear regression with β∗ constrained to an ℓq-ball, 0 ≤ q ≤ 1.The paper specifies scaling conditions for q ∈ (0,1] and assumes normalized design columns throughout.
- Problem and assumptions: The Bq(Rq)-kernel diameter measures non-identifiability because indistinguishable parameters can differ by any kernel perturbation inside the ball.Restricted curvature also implies an upper bound on this ℓ2-kernel diameter, linking curvature to identifiability.
- ℓp-norm risks: Theorem 1 gives ℓp-risk lower bounds for p ∈ [1,∞), combining kernel diameter with a noise-and-metric-entropy term.The diameter captures non-identifiability, while the second term reflects the complexity of the ℓq-ball and often determines the rate.
- ℓ2-norm risks: Under column normalization and restricted curvature, Theorem 2 gives upper bounds for ℓ2-risk, including separate conditions for q ∈ (0,1] and q = 0.For q ∈ (0,1], the curvature remainder must satisfy fℓ(Rq,n,d) = o(Rq^1/2(log d/n)^1/2−q/4); hard sparsity requires fℓ(s,n,d) = 0.
- Prediction risks: Prediction-risk upper bounds require mild design conditions, whereas prediction-risk lower bounds require column normalization and restricted curvature.The paper emphasizes that prediction and ℓ2-norm risks can have similar rates while depending on design structure in different ways.
- Prediction risks: For q = 0, a degenerate design can yield Θ(1/n) prediction risk while making ℓ2 estimation unidentifiable and its minimax risk infinite.The prediction problem remains easy in this example, whereas the ℓ2 upper bound fails because restricted curvature is violated.
3 Some consequences
The paper connects its minimax results to the Gaussian sequence model and Gaussian random designs, then compares optimal ℓ0-based estimation with ℓ1-based methods.
- Gaussian sequence model: The Gaussian sequence model is a special case of linear regression with d = n, X = I_n×n, and σ² = τ².
- Gaussian sequence model: The paper recovers the Donoho–Johnstone minimax scaling for ℓ2-loss over ℓq-balls when q ∈ [0,1].
- Gaussian random designs: Gaussian random designs with independent rows and correlated columns satisfy the relevant assumptions with high probability under bounded maximal variance and a covariance eigenvalue condition.
- ℓ0 versus ℓ1 methods: For q = 0, least-squares over the ℓ0-ball requires no stronger design condition than the ℓ1-based analysis condition discussed in the paper.
- ℓ0 versus ℓ1 methods: A low-dimensional construction shows that an ℓ1-based method can fail to recover a 1-sparse parameter while an ℓ0-based algorithm succeeds exactly.
- ℓ0 versus ℓ1 methods: ℓ1-relaxations can achieve the minimax ℓ2-error rate up to constants, but their analyses impose stronger design assumptions than the optimal ℓ0-based estimator.
4 Proofs of main results
The proofs combine information-theoretic lower-bound arguments with constructive analysis of least-squares estimators over ℓq-balls. Metric entropy, packing, covering, and Gaussian-process bounds connect these arguments to the design matrix.
- Lower bounds: Lower bounds use Fano’s inequality together with metric-entropy characterizations of ℓq-balls.
- Lower bounds: The lower-bound construction starts with a packing set in the target loss metric and uses design assumptions to relate prediction and ℓ2 packings.
- Lower bounds: Fano’s inequality converts estimation into multi-way hypothesis testing, with the bound controlled by packing entropy and mutual information.
- Lower bounds: The mutual-information bound uses a prediction-norm covering set, then optimizes the packing and covering radii.
- Upper bounds: Upper bounds directly analyze least-squares over the ℓq-ball through a Gaussian empirical process over Bq(2Rq).
- Upper bounds: Bounding the Gaussian process uses covering numbers of ℓq-balls and their images under X, with chaining and peeling for q ∈ (0,1).
- Metric entropy and design: The design-dependent lower-bound analysis represents KL divergences through q-convex hulls of rescaled design columns and controls their metric entropy.
5 Discussion
The paper determines minimax rates across several loss functions and clarifies how design assumptions affect achievable guarantees. It also compares oracle least-squares over the ℓ0-ball with ℓ1-based relaxations and identifies independent Gaussian noise as a scope limitation.
- Minimax rates are analyzed under high-dimensional scaling, with lower bounds for ℓp-losses and ℓ2-prediction loss.
- Matching upper and lower bounds determine the minimax rates for both ℓ2-loss and ℓ2-prediction loss up to constant factors.The rates extend the Gaussian-sequence-model scaling to more general design matrices.
- Mild column-norm conditions suffice for ℓ2-risk lower bounds and ℓ2-prediction upper bounds, whereas the opposite guarantees require curvature over the ℓq-ball.The curvature condition is related to non-identifiability over the ℓq-ball.
- Assumption 2 holds with high probability for broad Gaussian random-matrix classes, including covariance structures richer than the standard Gaussian design.
- The analysis assumes independent Gaussian noise and leaves heavier-tailed or dependent noise models for future work.The authors also identify non-parametric sparse additive models as an extension.
B Proof of Lemma 3
This proof derives metric-entropy bounds for ℓq-balls by inverting dyadic entropy-number estimates. The inversion requires explicit restrictions on the entropy index and approximation radius.
- Known dyadic entropy numbers for d-dimensional ℓq-balls are inverted to obtain metric-entropy bounds in ℓp-norm.The argument applies for q ∈ (0, p) and incorporates the ball radius Rq.
- The upper-bound proof first establishes a metric-entropy inequality before solving it for k = log Np,q(ε).
- The lower-bound argument assumes a fixed ν ∈ (0, 1) such that k ≤ d^(1−ν).
- The inversion conditions require k ≥ log d and k ≤ d^(1−ν), enforced through restrictions on ε.
C Proof of Lemma 4
This proof establishes an intermediate metric-entropy claim by combining known results on dyadic entropy numbers and then inverting the resulting upper bound.
- The proof begins by establishing bounds on dyadic entropy numbers for the relevant ℓq-ball.
- Known results from Guédon–Litvak and Carl–Pajor are combined to derive the required entropy-number behavior.
- The operator norm |||X|||1→2 appears in the bound as the norm of X viewed from an ℓ1 domain to an ℓ2 codomain.
- Under the stated assumptions, the entropy-number bound is inverted using the procedure from Lemma 3.
D Proof of Lemma 5
This proof constructs a large separated subset of a Hamming-combinatorial set to establish a metric-entropy lower bound. Separation follows by controlling Hamming balls and iteratively adding distant elements.
- For even s, the proof defines a combinatorial set H used to construct separated points.
- Points in H differ in at most 2s coordinates, and Hamming distance ρH is used to measure their separation.
- The number of elements within Hamming distance s/2 of a fixed point is upper bounded by counting coordinate agreements and choices.
- Any set A of size at most m covers fewer than all elements of H through Hamming balls of radius s/2.
- Consequently, an element outside the covered region can be added repeatedly to form a set larger than m with pairwise Hamming distance greater than s/2.
- The construction relies on the monotonic decrease of the relevant combinatorial ratio as j increases.
E Proof of Proposition 1
The appendix proves Proposition 1 using Slepian’s lemma and Gordon’s extension for Gaussian processes, then combines expectation bounds, concentration, and peeling arguments to establish upper and lower bounds.
- Gaussian-process comparison: Slepian’s lemma and Gordon’s extension provide the comparison framework for the Gaussian-process bounds in Proposition 1.The proof verifies the required increment inequality and equality condition for the compared processes.
- Gaussian-process comparison: The random design is represented as X = WΣ^1/2, with W having i.i.d. standard Gaussian entries, and the processes are indexed over a unit sphere and a constrained vector set.The proof introduces the transformed vector and computes the process increments needed for comparison.
- Upper bound: The upper bound follows from Slepian’s inequality, Gaussian-maxima estimates, Lipschitz concentration, and a peeling lemma controlling the constrained supremum.The resulting event has probability bounded by c1 exp(−c2n) for numerical constants.
- Conclusion: The appendix concludes the claimed bounds, including the stated special-case result for q = 1 and the probability estimate established for the proposition.The final steps use the preceding expectation and concentration calculations.
- Lower bound: The lower bound applies Gordon’s inequality and analogous concentration and peeling arguments to the infimum over the constrained set.Rescaling extends the resulting inequality from normalized vectors to arbitrary vectors.
F Proof of Lemma 6
The proof of Lemma 6 constructs an ℓ2-cover for sparse vectors, controls Gaussian deviations over the cover, and uses a union bound to obtain a high-probability result.
- Covering construction: A covering set for S(s, r) is built by combining supports of size 2s with finite covers of Euclidean balls on each support.The resulting cover has cardinality controlled by the number of supports and the covering precision.
- Deviation control: For each fixed covered vector, the noise-design inner product is Gaussian with variance bounded using the assumed conditions on X.This enables a finite-maximum bound over all cover elements.
- Covering construction: The covering-number calculation uses standard binomial-coefficient bounds and yields logarithmic complexity proportional to s log(d/s).The argument assumes d/s ≥ 2 and uses n ≤ d in selecting the covering radius.
- Deviation control: The fixed-support argument is extended across supports by a union bound, producing the stated high-probability event.The probability is at least 1 − c1 exp(−c2 min{n, s log(d − s)}).
G.1 Proof of Lemma 7
The proof of Lemma 7 bounds a constrained Gaussian supremum through chaining and covering numbers in the ℓ2-prediction norm, together with concentration and a large-deviation lemma.
- Chaining and entropy: The chaining argument targets the supremum of the prediction-norm process over vectors satisfying the relevant constraint.The proof invokes a chaining result with specified accuracy and constant parameters.
- Concentration: Gaussian concentration is applied to establish tail control for the constrained supremum.The proof selects a deviation parameter and verifies the conditions required by the large-deviation argument.
- Conclusion: The covering-number bound is substituted into the chaining conditions, which hold when the radius is sufficiently large relative to the design-dependent scale.The proof concludes with a bound of the form Z(Rq, r) ≥ c3 r eκc occurring with exponentially small probability.
G.2 Proof of Lemma 8
The proof of Lemma 8 combines singular-value decomposition, χ2 concentration, union bounds, and a general peeling lemma for constrained random objectives.
- Fixed-support analysis: For each fixed support, singular-value decomposition reduces the design action to a diagonal-coordinate representation while preserving Gaussian noise coordinates.The transformed noise vector has independent N(0, σ^2) entries.
- Fixed-support analysis: χ2 tail bounds control the norm of the transformed noise on each support.The resulting fixed-support probability estimate is then prepared for aggregation across supports.
- Support aggregation: A union bound over all supports introduces the combinatorial support-count terms into the final probability estimate.The proof combines the fixed-support estimate with bounds involving binomial coefficients and logarithmic support complexity.
- Peeling argument: Lemma 9 bounds constrained optima by peeling the constraint radius into geometric shells and summing the corresponding tail probabilities.Its assumptions require an increasing function g bounded below by μ and a tail bound indexed by the radius.
- Peeling argument: The shell-wise inequalities yield the claimed result after a geometric-series bound, with χ2 large-deviation results supplying the needed concentration input.The proof relies on Laurent–Massart bounds for centralized χ2 variables.