GRAPH-BASED REGULARIZATION FOR REGRESSION PROBLEMS WITH HIGHLY-CORRELATED DESIGNS

Sparse models for high-dimensional linear regression and machine learning have received substantial attention over the past two decades. Much of the current literature assumes that covariates are only mildly correlated, however, in modern applications ranging from functional MRI to genome-wide association studies, covariates are highly correlated. We consider a high-dimensional regression setting in which a graph governs both correlations among the covariates and the similarity among regression coefficients. This graph is used to define a graph total variation regularizer that promotes similar weights for highly correlated features. Our proposed graph-based regularization yields mean-squared error guarantees for a broad range of covariance graph structures by imposing additional structure on the parameter which encourages alignment with the covariance graph.