Source-linked AI summary
Trace Lasso: a trace norm regularization for correlated designs
Edouard Grave, Guillaume Obozinski, Francis Bach
TL;DR
The paper addresses instability caused by using the ℓ1-norm when estimating linear-model parameters with highly correlated covariates. It introduces the trace Lasso, a correlation-aware trace-norm penalty, and analyzes its properties and optimization. Synthetic experiments show better estimation performance in strong-correlation regimes than existing norms.
Problem
Lasso estimation can be unstable with strongly correlated covariates, motivating a regularizer that accounts for the design's correlation structure.
Method
The trace Lasso uses the trace norm of selected covariates as a convex complexity measure and adapts between ℓ1- and ℓ2-like behavior according to correlations.
Results
Synthetic experiments show that the trace Lasso outperforms existing norms in strong-correlation regimes.
Takeaways & Limitations
The trace Lasso adds strong convexity in directions of highly correlated covariates and has a unique minimum, supporting more stable estimation.
Takeaways & Limitations
The dual norm lacks a closed-form expression in general, although bounds are available and exact in some special cases.
Abstract
from arXiv · showhide
Using the $\ell_1$-norm to regularize the estimation of the parameter vector of a linear model leads to an unstable estimator when covariates are highly correlated. In this paper, we introduce a new penalty function which takes into account the correlation of the design matrix to stabilize the estimation. This norm, called the trace Lasso, uses the trace norm, which is a convex surrogate of the rank, of the selected covariates as the criterion of model complexity. We analyze the properties of our norm, describe an optimization algorithm based on reweighted least-squares, and illustrate the behavior of this norm on synthetic data, showing that it is more adapted to strong correlations than competing methods such as the elastic net.
1 Introduction
The paper addresses instability in sparse estimation under strong covariate correlations by proposing a design-adaptive norm. The trace Lasso interpolates between ℓ1 and ℓ2 behavior according to correlations and is analyzed theoretically and computationally.
- Motivation: Strongly correlated predictors can make Lasso selection unstable, with correlated variables selected inconsistently despite acceptable predictive performance.The Lasso is most effective in low-correlation settings but may select only one of two correlated variables at random.
- Motivation: An ideal regularizer should adapt to the design, add strong convexity only where needed, and avoid manual grouping or indiscriminate ℓ2 regularization.This motivates a new norm intended to combine design adaptivity with stable estimation.
- Contributions: The trace Lasso is a trace-norm-based penalty that interpolates between the ℓ1-norm and ℓ2-norm depending on covariate correlations.It uses the trace norm as a convex surrogate for the rank of selected covariates.
- Contributions: The paper establishes that penalization with the trace Lasso has a unique minimum and provides optimization algorithms based on reweighted least-squares.The uniqueness result is presented in Section 2.2, while the algorithms are described in Section 3.
- Contributions: The paper studies the trace Lasso's second-order expansion around independence and relates it to existing approaches for incorporating correlations.This analysis examines behavior near the Lasso case.
- Experiments: Synthetic experiments show that the trace Lasso outperforms existing norms in strong-correlation regimes.The experiments are reported in Section 5.
2 Definition and properties of the trace Lasso
The trace Lasso applies the trace norm to the design matrix weighted by coefficients, using the span of selected predictors as an adaptive complexity measure. It interpolates between Lasso-like behavior for weak correlations and Tikhonov-like behavior for strong correlations, while yielding a unique minimizer under strongly convex loss.
- Trace Lasso definition: The trace Lasso penalizes the trace norm of X Diag(w), a convex surrogate for the rank of the selected predictors.The rank measures the dimension of the subspace spanned by selected predictors, rather than merely their count.
- Limiting cases: For orthogonal predictors, the trace Lasso equals the ℓ1-norm.This recovers Lasso behavior when predictors are uncorrelated.
- Adaptive behavior: For strongly correlated predictors, the trace Lasso equals the Tikhonov penalty and behaves like the ℓ2-norm; for nearly uncorrelated predictors, it behaves like the ℓ1-norm.Thus the penalty adapts to correlation rather than applying strong convexity uniformly.
- Uniqueness and stability: If the loss is strongly convex in its prediction argument, empirical risk minimization penalized by the trace Lasso has a unique solution.The proof establishes strong convexity of the trace Lasso in directions where the loss is flat.
- Design dependence: The trace Lasso depends on P only through P⊤P, so with P = X it depends on the covariate correlation matrix X⊤X.This makes the penalty design-adaptive without requiring a manually specified variable partition.
- Comparison with existing penalties: Unlike the elastic net, this family interpolates between ℓ1 and ℓ2 behavior adaptively while requiring a single regularization parameter.For the trace Lasso, strong correlations produce ℓ2-like behavior and weak correlations produce ℓ1-like behavior.
3 Optimization algorithm
The trace Lasso optimization uses an iteratively reweighted least-squares formulation, alternating updates over the parameter vector and an auxiliary matrix. For square loss, each parameter update is a reweighted least-squares problem that can be solved efficiently with conjugate gradients.
- The square-loss objective combines 1/2∥y − Xw∥2^2 with λ∥X Diag(w)∥∗.The trace Lasso is used as the penalty in the penalized least-squares problem.
- The algorithm uses an iteratively reweighted least-squares method instead of subgradient descent because trace-norm subgradients are expensive and converge slowly.
- The reformulated objective is jointly convex in w and S, enabling alternating minimization over these variables.A regularization term involving tr(S^-1) is added to avoid a noninvertible minimizing S and nonconvergence.
- Optimizing over w yields a least-squares problem penalized by a reweighted ℓ2-norm w⊤Dw.
- Conjugate gradients solve each linear system with complexity O(knp), where k ≤ p is the number of iterations needed to converge.Warm restarts can reduce k because successive systems change only slightly.
- The regularization path starts at λ = Ω∗(X⊤y), where the zero vector is the solution, and then decreases λ.
4 Approximation around the Lasso
Around the independence case, the trace Lasso admits a second-order approximation whose correlation-dependent term shrinks coefficients of correlated covariates toward each other. This term resembles pairwise elastic net penalties.
- The approximation perturbs P = I by a small symmetric matrix ∆, where the trace Lasso equals the ℓ1-norm at independence.
- For correlated covariates, the second-order term shrinks their corresponding coefficients toward each other.
- The correlation-dependent term is similar to pairwise elastic net penalties of the form |w|⊤P|w|.
5 Experiments
Synthetic experiments compare the trace Lasso with classical penalties under uncorrelated, clustered, and Toeplitz covariance structures. It is strongest in the correlated designs, while the Lasso is slightly better in the uncorrelated experiment.
- The experiments use p = 1024 covariates, n = 256 observations, and identity, block-diagonal, or Toeplitz covariance matrices.The block-diagonal design contains clusters of eight variables, while the Toeplitz design has Σij = 0.95|i−j|.
- In uncorrelated designs, the trace Lasso slightly underperforms the Lasso because empirical correlations induce weak coupling between variable selections.
- In block-diagonal and Toeplitz designs, the trace Lasso outperforms other methods, including the pairwise elastic net.The reported advantage occurs when variables that should be selected together are correlated.
- Figure 2 compares elastic net, pairwise elastic net, and trace Lasso in the experiment with uncorrelated variables.
6 Conclusion
The paper concludes that the trace Lasso uses covariate correlations to add strong convexity selectively and achieves better estimation performance on synthetic data. Future work targets theoretical guarantees and applications to correlated inverse problems.
- The trace Lasso adds strong convexity in directions of highly correlated covariates rather than uniformly applying a squared ℓ2-norm.
- Synthetic experiments show that this adaptive behavior leads to better estimation performance.
- Future work will study group-Lasso-like behavior, theoretical guarantees for adaptivity, and applications such as deblurring.
A Perturbation of the trace norm
The section follows a technique from prior work to approximate the trace norm.
- The trace norm is approximated using a technique from prior work.
A.1 Jordan-Wielandt matrices
The Jordan-Wielandt matrix connects the singular values of M to the eigenvalues of a symmetric block construction, including positive, negative, and zero eigenvalues.
- For rank-r matrix M, the construction is based on its strictly positive singular values and associated singular vectors.
- Each positive singular value s_i of M corresponds to eigenvalues s_i and −s_i of the Jordan-Wielandt matrix.
- The remaining eigenvalues of the Jordan-Wielandt matrix are zero, with eigenvectors associated with the zero eigenspace.
- A closed contour is chosen without passing through the matrix's eigenvalues for subsequent spectral analysis.
A.3 Perturbation analysis
The perturbation analysis studies how singular values change under a matrix perturbation by tracking eigenvalue projectors through contour integrals.
- A perturbation Δ with ∥Δ∥op < s_r/4 allows analysis around the r largest eigenvalues of the Jordan-Wielandt matrices.
- Resolvent identities expand the perturbed spectral projector into terms whose contour integrals determine singular-value changes.
- The first-order integral vanishes when the associated singular values lie on the same side of the contour.
- A contour around zero separately captures perturbations of the zero singular values.
- The resulting proposition gives a perturbation formula for the singular values of M under Δ.
B Proof of proposition 1
The proof establishes uniqueness of the penalized empirical-risk minimizer by showing that any alternative optimum would contradict the trace-Lasso penalty structure across correlated predictor groups.
- Strong convexity of the loss outside the nullspace of X forces the difference between two optimal solutions into that nullspace.
- The proof analyzes the objective locally through the singular-value decomposition of X Diag(w).
- Optimality implies that the relevant covariance and diagonal perturbation matrices commute and are simultaneously diagonalizable.
- Predictors are partitioned into connected groups according to nonzero covariance links, making the coefficient γ constant within each group.
- Any nonzero nullspace component would leave data fit unchanged but strictly reduce the penalty, contradicting optimality and proving uniqueness.
C Proof of proposition 3
The proof establishes two inequalities, using the duality between the trace and operator norms and a bound on column ℓ2 norms.
- The proof addresses the first inequality.
- The proof addresses the second inequality.
- The first equality follows because the dual norm of the trace norm is the operator norm.
- The second inequality uses that operator-norm-bounded matrices have columns with ℓ2 norm smaller than one.