Correlated variables in regression: clustering and sparse estimation

Peter Bühlmann; Philipp Rütimann; Sara van de Geer; Cun-Hui Zhang

Source-linked AI summary

Correlated variables in regression: clustering and sparse estimation

Peter Bühlmann, Philipp Rütimann, Sara van de Geer, Cun-Hui Zhang

arXiv:1209.5908v1Sep 26, 2012stat.MEmath.ST

TL;DR

The paper addresses variable screening in high-dimensional linear models where strong correlations make individual variables difficult to identify. It clusters variables using canonical correlations, then applies cluster-representative Lasso or group Lasso. The methods provide optimal and consistent clustering, improve the group Lasso compatibility constant, and are empirically attractive for variable screening.

Problem
Strongly correlated variables make individual-variable identification difficult in high-dimensional regression, motivating cluster-based screening.
Method
The paper uses bottom-up canonical-correlation clustering followed by Lasso on cluster representatives or group Lasso using the inferred clusters.
Results
Canonical-correlation clustering is shown to be optimal and statistically consistent, while cluster Lasso methods are particularly attractive for variable screening compared with plain Lasso.
Takeaways & Limitations
Cluster Lasso methods can be attractive alternatives to plain Lasso for variable screening in strongly correlated high-dimensional data.
Takeaways & Limitations
The clustering threshold may be infeasible for any nontrivial partition, forcing the coarsest single-cluster solution.

Abstract

from arXiv · show

We consider estimation in a high-dimensional linear model with strongly correlated variables. We propose to cluster the variables first and do subsequent sparse estimation such as the Lasso for cluster-representatives or the group Lasso based on the structure from the clusters. Regarding the first step, we present a novel and bottom-up agglomerative clustering algorithm based on canonical correlations, and we show that it finds an optimal solution and is statistically consistent. We also present some theoretical arguments that canonical correlation based clustering leads to a better-posed compatibility constant for the design matrix which ensures identifiability and an oracle inequality for the group Lasso. Furthermore, we discuss circumstances where cluster-representatives and using the Lasso as subsequent estimator leads to improved results for prediction and detection of variables. We complement the theoretical analysis with various empirical results.

1 Introduction

High-dimensional regression becomes difficult when p greatly exceeds n and predictors are highly correlated, so the paper prioritizes screening active variables while tolerating some false positives. It proposes clustering variables before sparse estimation to address these identifiability challenges.

The screening objective is to select a set containing the active support S0 while keeping its size from becoming too large.
When p ≫ n, near non-identifiability and highly correlated or nearly dependent variables complicate variable screening.
The proposed strategy accepts more false positives to reduce false negatives and select groups containing active variables.
Clustering or grouping variables before selection can support screening by selecting whole clusters rather than individual variables.
Canonical-correlation clustering targets linear dependence, while the paper analyzes when subsequent estimation improves over standard Lasso and when it has limitations.

2 Clustering covariables

The paper constructs variable clusters using canonical correlations and a bottom-up agglomerative procedure, defining finest clusterings under a separation threshold. The procedure has optimality and consistency results, with a data-driven threshold rule, alongside ordinary correlation-based hierarchical clustering.

The clustering goal is to partition all covariables into disjoint groups satisfying separation criteria.
Canonical-correlation clustering is a novel alternative to standard correlation-based hierarchical clustering for finding suitable variable partitions.
A clustering has τ-separation when the maximum empirical canonical correlation between distinct clusters is at most τ.
When τ permits a nontrivial partition, the algorithm returns the finest clustering with τ-separation; otherwise, it returns the single-cluster solution.
The procedure is optimal and statistically consistent under stated conditions, and its threshold can be selected from the minimum observed path of maximum canonical correlations.
The bottom-up greedy algorithm merges the two clusters with highest canonical correlation and stops when the separation criterion is satisfied.

3 Supervised selection of clusters

After inferring clusters, the paper selects them group-wise using either Lasso on cluster representatives or the cluster group Lasso. Selected variables are the union of selected clusters.

Cluster-based selection chooses entire clusters, so every variable in a selected cluster enters the selected variable set.
The cluster representative Lasso applies ordinary Lasso to one representative variable from each cluster.
The cluster group Lasso partitions coefficients by clusters and selects groups through a group-wise penalty.
The group Lasso has a group selection property: each cluster is either selected as a whole or omitted as a whole.

4 Theoretical results for cluster Lasso methods

The paper develops supporting theory for the cluster group Lasso and cluster representative Lasso. This theory addresses compatibility, bias, and detection in subsequent cluster-based estimation.

The theoretical analysis covers the cluster group Lasso and the cluster representative Lasso.
The analysis examines theoretical properties of cluster-based estimation after the clustering step.
Bias and detection are among the issues addressed for subsequent cluster representative estimation.

4.1 Cluster group Lasso (CGL)

The cluster group Lasso uses clustered variables as groups, with canonical-correlation structure supporting compatibility and selection guarantees under eigenvalue and incoherence conditions.

Canonical correlations between groups are used to establish a well-behaved compatibility constant for the original design matrix.The clustering algorithm is designed to create groups with small canonical correlations.
The group Lasso analysis assumes a positive smallest eigenvalue and incoherence conditions involving group correlations.These conditions include bounds involving the active-group set and canonical correlations between groups.
Small canonical correlations between groups ensure the incoherence assumptions needed for the group Lasso compatibility condition.The canonical-correlation clustering algorithm is tailored to this setting.
Under the theorem’s eigenvalue and incoherence conditions, a group irrepresentable condition yields no false positive selection of groups with large probability.This extends the corresponding Lasso selection result to groups.
Known group Lasso results can then be applied to obtain an oracle inequality under the stated fixed-design Gaussian-model assumptions.The estimator uses groupwise prediction penalties and requires λ ≥ 2λ0 in the supplied proposition setup.

4.2 Linear dimension reduction and subsequent Lasso estimation

Linear dimension reduction replaces the original predictors with a lower-dimensional design, after which Lasso estimation has improved compatibility and logarithmic factors but incurs approximation bias.

Linear dimension reduction maps the p predictors to q predictors through a matrix A with q < p.Cluster representatives are a special case, formed by averaging variables within each cluster.
For cluster representatives, the reduced design is Z = (X̄(1), ..., X̄(q))^T, and the Lasso estimates the reduced coefficients γ0.The cluster representative Lasso uses the n × q design matrix formed by the representatives.
The reduced-model noise variance is ξ2 = σ2 + E[(μX − μZ)2], combining observational noise with squared approximation bias.The bias arises from replacing the original linear predictor with its projection onto the span of Z.
Under a beta-min condition, the reduced-model Lasso has a variable-screening property that includes the support S(γ0) with high probability.The proposition’s probability statement is conditional on the reduced design Z.
The reduced design’s compatibility constant is typically much better behaved when q ≪ p than the corresponding constant for X.The resulting rates use a log(q) factor rather than a log(p) factor, alongside sparsity in γ0.
Dimension reduction trades improved compatibility and dimensional factors against the bias term and possible differences between detecting γ0 and detecting β0.The prediction-error decomposition separates estimation error for γ0 from squared bias.

4.3 The parameter γ0 for cluster representatives

The cluster-representative parameter γ0 is determined by covariance-weighted within-cluster coefficients. Its detection and prediction behavior improves with coherent, tight clusters but can deteriorate under coefficient cancellation.

When cluster representatives are independent, γ0 is characterized explicitly through covariance-weighted coefficients within each cluster.
Nonnegative within-cluster covariances make γ0r/|Gr| a convex combination of the coefficients in Gr.
Equal variances and equal within-cluster correlations yield uniform weights within each cluster.
Detection is easier when the covariance-weighted coefficient sum within a cluster is sufficiently strong, even if individual coefficients are small.
Near cancellation among coefficients reduces |γ0r| and can impair detection, especially when within-cluster correlations are negative.
Cluster representatives can retain favorable prediction and screening behavior under moderate between-cluster dependence or approximately correct clustering.

4.4 A comparison

The comparison distinguishes cluster representative Lasso, cluster group Lasso, and plain Lasso by group size, sparsity pattern, bias, and coefficient cancellation. Cluster methods can outperform plain Lasso, but their advantages depend on the grouping and model structure.

For large groups containing few active variables, plain Lasso can have better rates because group Lasso rates depend on group-size factors rather than only variable sparsity.
When groups contain many active variables, cluster group Lasso is beneficial mainly for detection, while exploiting group structure.
Cluster group Lasso avoids the representative method’s bias and tolerates differing coefficient signs when the group coefficient norm is sufficiently large.
Cluster representative Lasso is most favorable when bias is small, clusters are tight, and the dimension-reduced parameter γ0 is well posed.
Cluster representative Lasso and cluster group Lasso can substantially improve prediction and detection over plain Lasso with highly correlated variables.
For groups larger than sample size, cluster group Lasso is inappropriate without within-group regularization; canonical-correlation clustering improves its compatibility constant.

4.5 Estimation of the clusters

Cluster estimation relies on within-cluster tightness and between-cluster separation. Under these conditions, hierarchical clustering based on empirical correlations consistently recovers the population clusters when log(p)/n tends to zero.

The theoretical estimation results assume that the groups correspond to the correct underlying clusters.
Tightness and separation require weaker between-cluster correlations than within-cluster correlations in absolute value.
Single-linkage clustering with dissimilarity 1 −|ˆΣj,k| consistently finds the true clusters if log(p)/n →0 under the separation condition.
Higher within-cluster correlation and greater between-cluster uncorrelatedness improve estimation of the underlying grouping.

4.6 Some first illustrations

Illustrations compare cluster representative Lasso with plain Lasso under block-correlated designs, varying active-variable patterns and clustering accuracy. Predictive performance remains informative for choosing whether representative clustering is useful.

The illustrations use p = 1000 variables, n = 100 observations, q = 5 clusters, and three active groups.
Incorrect clustering was constructed by mixing halves of true clusters with randomly selected variables.
The scenarios vary from one active variable per active group to four active variables and exact coefficient cancellation.
Results were described as robust to approximate cancellation and incorrect clustering, although incorrect clustering selected the number of clusters less well.
Cross-validated predictive performance is presented as a useful indicator of whether cluster representative Lasso works.

5 Numerical results

Across simulated and pseudo-real settings, cluster Lasso methods generally improved variable screening over plain Lasso, while prediction gains were limited and method-dependent.

Variable screening: Cluster representative Lasso (CRL) and cluster group Lasso (CGL) generally outperformed plain Lasso for variable screening, especially when active variables were concentrated within correlated clusters.This advantage appeared in the block diagonal, single block, duo block, and most pseudo-real settings.
Block diagonal model: In the block diagonal model, CRL and CGL improved screening, with larger benefits when many active variables occupied the same cluster.The comparison used true-positive screening performance as a function of the selected-set size.
Single block model: For the single block model, CRL performed at least as well as Lasso for prediction and better for screening, whereas CGL was inferior for screening, especially when most active variables shared a block.CGL nevertheless gained predictive performance when coefficient signs were switched.
Duo block model: For the duo block model, all three methods had similar prediction performance, while CRL and CGL were clearly better than Lasso for variable screening.The prediction comparison showed especially little difference when σ = 12.
Pseudo-real data: In the pseudo-real riboflavin example, cluster methods generally improved screening but showed less gain than in simulations; CRL and Lasso had similar prediction performance, while CGL lagged.Incorrect correlation-based clustering performed poorly because it produced a very large cluster and an inappropriate representative.
Method behavior and clustering: CGL can lose efficiency when active groups contain many non-active variables, while sparse group Lasso is suggested as a possible repair.The novel canonical-correlation clustering algorithm differed substantially from ordinary correlation clustering in the pseudo-real example and produced better results there.

6 Conclusions

The paper combines clustering with sparse estimation for strongly correlated variables, establishing theoretical advantages and empirical improvements for screening. It emphasizes canonical-correlation clustering, cluster-representative Lasso, and cluster group Lasso as useful alternatives to plain Lasso.

Theoretical contributions: The proposed bottom-up clustering algorithm finds an optimal clustering, is statistically consistent, and includes a rule for selecting the number of clusters.The clustering step targets small canonical correlations between groups and can be replaced by another suitable clustering procedure.
Theoretical contributions: Canonical-correlation clustering supports the cluster group Lasso by improving its compatibility constant and addresses bias and detection for cluster-representative estimation.The analysis identifies favorable settings involving within-cluster correlation, cluster size, and the distribution of active variables.
Empirical findings: Cluster Lasso methods are empirically attractive for improved variable screening compared with the plain Lasso.The empirical results concern both CRL and CGL and focus on screening and dimension reduction in the original variables.
Empirical findings: Cluster Lasso methods are an attractive and often better alternative for variable screening and dimension reduction in high-dimensional data analysis.This conclusion is framed around variable screening and dimension reduction as major applications of the Lasso.

7 Proofs

The proofs establish the clustering algorithm’s separation and fineness properties, then derive statistical consistency and bounds supporting the later group- and representative-Lasso analyses.

Clustering proof: The algorithm stops only after all between-group canonical correlations are at most τ, so its output satisfies τ-separation.This follows directly from the algorithm’s merge-until-separation rule.
Clustering proof: The resulting partition is therefore the finest clustering with τ-separation, establishing the algorithm’s optimality claim.The proof combines the stopping property with preservation of fineness throughout the agglomerative sequence.
Clustering proof: The induction argument shows that every intermediate partition remains finer than any clustering with τ-separation.When two current groups have canonical correlation above τ, they must lie inside the same group of the comparison clustering.
Statistical consistency: Uniform bounds on sample-versus-population canonical correlations imply that the population finest clustering is also the sample finest clustering over the stated τ range.The argument uses simultaneous probability bounds across cluster pairs and nontrivial within-cluster partitions, followed by Theorem 2.1.
Group-Lasso analysis: The group-Lasso analysis derives lower bounds for the compatibility constant and obtains strict positivity under the stated incoherence condition.The proof uses bounds involving the grouped active set and the correlation parameter.
Representative analysis: The representative-based analysis decomposes the response into representative and within-cluster components to bound approximation error from cluster representatives.The decomposition relates the difference between representative and target coefficients to the residual terms W and η−ε.