The Generalized Elastic Net for Least Squares Regression With Network-Aligned Signal and Correlated Design

We propose a novel <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\ell _{1}+\ell _{2}$</tex-math></inline-formula>-penalty, which we refer to as the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Generalized Elastic Net</i>, for regression problems where the feature vectors are indexed by vertices of a known graph and the true signal is believed to be smooth or piecewise constant with respect to this graph. Under the assumption of correlated Gaussian design, we derive upper bounds for the prediction and estimation errors, which are graph-dependent and consist of a parametric rate for the unpenalized portion of the regression vector and another term that depends on our network alignment assumption. We also provide a coordinate descent procedure based on the Lagrange dual objective to compute this estimator for large-scale problems. Finally, we compare our proposed estimator to existing regularized estimators on a number of real and synthetic datasets, demonstrating its ability to leverage the network structure to improve the RMSE, even under strong feature correlations.