Graph-based regularization for regression problems with alignment and highly-correlated designs

Abstract

Sparse models for high-dimensional linear regression and machine learning have received substantial attention over the past two decades. Model selection, or determining which features or covariates are the best explanatory variables, is critical to the interpretability of a learned model. Much of the current literature assumes that covariates are only mildly correlated. However, in many modern applications covariates are highly correlated and do not exhibit key properties (such as the restricted eigenvalue condition, restricted isometry property, or other related assumptions). This work considers a high-dimensional regression setting in which a graph governs both correlations among the covariates and the similarity among regression coefficients -- meaning there is \emph{alignment} between the covariates and regression coefficients. Using side information about the strength of correlations among features, we form a graph with edge weights corresponding to pairwise covariances. This graph is used to define a graph total variation regularizer that promotes similar weights for correlated features. This work shows how the proposed graph-based regularization yields mean-squared error guarantees for a broad range of covariance graph structures. These guarantees are optimal for many specific covariance graphs, including block and lattice graphs. Our proposed approach outperforms other methods for highly-correlated design in a variety of experiments on synthetic data and real biochemistry data.

References in corpus (7)

• The composite absolute penalties family for grouped and hierarchical variable selection
• Network Lasso: Clustering and Optimization in Large Graphs
• Total variation regularization for fMRI-based prediction of behaviour
• Statistical estimation and testing via the sorted L1 norm
• Optimal rates for total variation denoising
• Total Variation Classes Beyond 1d: Minimax Rates, and the Limitations of Linear Smoothers
• Dictionary LASSO: Guaranteed Sparse Recovery under Linear Transformation

Cited by in corpus (3)

• The Mismatch Principle: The Generalized Lasso Under Large Model Uncertainties
• New Computational and Statistical Aspects of Regularized Regression with Application to Rare Feature Selection and Aggregation
• Error Analysis on Graph Laplacian Regularized Estimator