Regularized Linear Regression via Covariance Fitting

Per Mattsson, Dave Zachariah, Petre StoicaIEEE TSP 2023 · OpenReview

TL;DR

This paper unifies several popular regularized linear regression techniques (Ridge, LASSO, LAD) under a single framework by showing they are "tuned" versions of a more general estimator. The key innovation is using a data-driven covariance fitting method (SPICE) to automatically determine the regularization parameters, making these estimators more practical and often achieving near-optimal performance.

What Problem Does This Paper Address?

Estimating parameters in linear models ($y = \Phi \theta_0 + \epsilon$) is a fundamental problem. While ordinary least squares (LS) is standard, it can perform poorly with noisy, heteroscedastic, or correlated errors, or when the number of samples is small relative to the number of features. Regularized methods like Ridge, LASSO, and LAD address this by adding penalty terms to the objective function, but they require careful tuning of regularization parameters. The paper's core problem is how to automatically and optimally tune these regularization parameters using only the observed data, without relying on prior knowledge of the noise or parameter distributions.

Methods

The authors introduce a general class of regularized estimators parameterized by positive semi-definite weight matrices, $C$ and $V$. This class encompasses optimal linear estimators like the best linear unbiased estimator (BLUE) and the linear minimum mean-square error estimator (LMMSE). The crucial step is proposing a data-adaptive approach to determine $C$ and $V$ by minimizing a covariance fitting criterion based on the SPICE methodology. This criterion aims to make the estimated covariance of the data match the true covariance.

By choosing different structures for these data-adaptive weight matrices ($C$ and $V$), the authors demonstrate that the resulting estimators correspond to:

  • Square-root Ridge Regression: When $V$ is uniform diagonal and $C$ is uniform diagonal.
  • $l_2$-penalized Least Absolute Deviation: When $V$ is uniform diagonal and $C$ is uniform diagonal.
  • Square-root LASSO: When $V$ is uniform diagonal and $C$ is non-uniform diagonal (standardizing regressors).
  • $l_1$-penalized Least Absolute Deviation: When $V$ is uniform diagonal and $C$ is non-uniform diagonal.

The paper shows that these "tuned" estimators, derived from data-driven $C$ and $V$, are equivalent to known regularized estimators with optimally tuned regularization parameters.

Datasets

The paper does not introduce new datasets. Instead, it uses synthetic data generated according to specific noise and parameter structures to evaluate the performance of the proposed tuned estimators. The experiments involve three scenarios:

  1. Uniform noise and a dense parameter vector.
  2. Uniform noise and a sparse parameter vector.
  3. Non-uniform noise (outliers) and a sparse parameter vector.

These scenarios are designed to test the robustness and effectiveness of the tuned estimators under different data-generating conditions.

Key Insights and Ideas

  • Unification of Regularized Estimators: The paper provides a powerful theoretical framework that unifies seemingly disparate regularized estimators (Ridge, LASSO, LAD) as special cases of a more general covariance-fitting-based approach.
  • Data-Driven Tuning: The core contribution is a method to automatically tune regularization parameters using data-adaptive weight matrices derived from a covariance fitting criterion. This removes the need for manual tuning or prior knowledge.
  • SPICE Methodology Extension: The SPICE methodology, previously used for hyperparameter-free sparse estimation, is extended to handle singular covariance matrices and applied to a broader class of regularized estimators.
  • Structure Matters: The choice of structure for the weight matrices $C$ and $V$ (e.g., uniform diagonal, non-uniform diagonal, unstructured) directly dictates which type of regularized estimator is obtained and influences its performance characteristics (e.g., robustness to outliers, handling of sparse parameters).
  • Practical Relevance: The tuned estimators are shown to perform close to an "oracle" estimator (which knows the true parameters) in numerical experiments, demonstrating their practical utility.

Key Results

  • The proposed data-adaptive covariance fitting method yields tuned versions of square-root Ridge, square-root LASSO, and regularized LAD estimators.
  • The structure of the weight matrices $C$ and $V$ determines the data-fitting term and the regularization term, respectively.
  • Numerical experiments show that the tuned estimators can significantly reduce the mean squared error compared to unregularized methods.
  • In cases where the assumed covariance structure matches the true data-generating process, the tuned estimators achieve performance close to the optimal lower bound.
  • Assuming a more general structure for $C$ and $V$ than necessary does not significantly degrade performance. The paper suggests that a non-uniform diagonal structure for both $C$ and $V$ (L1-WL1 estimator) is a sensible default when prior knowledge is limited.

Limitations and Future Work

  • Unstructured Weight Matrices: The paper notes that using unstructured positive semi-definite matrices for $C$ and $V$ in the covariance fitting criterion often leads to uninteresting or unregularized estimators, particularly when the data can be explained by ordinary least squares. This suggests that structured matrices are more practically relevant.
  • Feasibility: The existence of a solution to the minimization problem depends on the data falling within the range space of the constructed matrix $R(C, V)$. The paper addresses this by ensuring the covariance fitting criterion itself produces a valid covariance matrix.
  • Future Work: The paper implicitly suggests that exploring other covariance structures for $C$ and $V$ could lead to further insights and new estimators. The success of the SPICE methodology in unifying and tuning these estimators opens avenues for applying similar data-driven approaches to other statistical modeling problems.

Summary updated

Abstract

The linear minimum mean-square error estimator (LMMSE) can be viewed as a solution to a certain regularized least-squares problem formulated using model covariance matrices. However, the appropriate parameters of the model covariance matrices are unknown in many applications. This raises the question: how should we choose them using only the data? Using data-adaptive matrices obtained via the covariance fitting SPICE-methodology, we show that the empirical LMMSE is equivalent to tuned versions of various known regularized estimators – such as ridge regression, LASSO, and regularized least absolute deviation – depending on the chosen covariance structures. These theoretical results unify several important estimators under a common umbrella. Furthermore, through a number of numerical examples we show that the regularization parameters obtained via covariance fitting are close to optimal for a range of different signal conditions.
BibTeX
@article{mattsson2023regularized,
  author = {Per Mattsson and Dave Zachariah and Petre Stoica},
  title = {{Regularized Linear Regression via Covariance Fitting}},
  journal = {IEEE Trans. Signal Process.},
  year = {2023},
  url = {https://openreview.net/forum?id=0Eci00oEw5I},
}
Figure