The elastic net [3] provides a regularized objective function that meets a compromise between the two extremes of Lasso [2] and ridge regression. It takes into account both the Bayesian properties of ridge regression and also the need for sparse parameters via the $\ell_1$ penalty from Lasso.

Let $\{(x_i,y_i):~i=1,\ldots,N\}$ be our observed data set where the responses $y_i\in\mathbb{R}$ and the predictors $x_i\in\mathbb{R}^p$. Simply put, elastic net regularization is defined by solving

where the penalty function is defined as

This was applied to generalized linear models (GLMs) by Tibshirani, and also encoded as an R package for optimized calculations [1]. In particular, one can take advantage of the many sparse entries underlying the computation, as the dimension of the corresponding matrices written in sparse column format is effectively smaller; this leads to reduced runtimes of $O(pm)$ as the inner product operations sum only over the nonzero terms ($m$ being the number of nonzero terms, $p$ the dimension of the predictors).

In one example, Friedman et. al [1] effectively show that this method to compute elastic nets is more efficient and more accurate than LARS, another regression algorithm meant for high-dimensional problems. Statisticians tend to keep to their own methods for computation, so let’s try something different; let’s see what happens when under the same example, we run standard stochastic gradient descent (SGD) and its implicit variant as a comparison.

We simulate data according to the example offered in the paper by Friedman et. al [1]: generate $N$ Gaussian observations with $p$ predictors, where each predictor pair $(X_j,~X_{j'})$ has the same population correlation $\rho$. Range $\rho$ from $0$ to $0.95$, and generate outcomes

where $\beta_j=(-1)^j\exp(-2(j-1)/20)$, $Z\sim N(0,1)$, and $k$ is chosen so that the signal-to-noise ratio is $3.0$.

We use the R package glmnet in order to emulate the times displayed on Table 1 of the paper, with both the “naive” and “covariance” variants of the algorithm. As for SGD and implicit SGD, let $b^2=\rho/(1-\rho)$, so then the covariance matrix can be rewritten as $\mathbb{E}[xx^T] = b^2U+I.$ Then for computing standard SGD, we shall use the learning rate

where $\gamma_0=1/\mathrm{trace}(A) = 1/((1+b^2)p)$ and $\alpha$ is the minimal eigenvalue $\lambda_0=1$. (The latter is true because all eigenvalues are 1 excluding one which is $\lambda=1+pb^2$. One can prove this easily by $(b^2U+I)x=\lambda x$ iff $(1-\lambda)x = -b^2 S\cdot 1$, where $S=\sum x_i$.) As for implicit SGD, we’ll just use $\alpha_n=\alpha/n$.

The following is run on a 2.6 Ghz i5 core processor.

Runtime (s)

Mean Squared Error

Stochastic gradient descent is obviously faster for large $p$. In particular, it achieves much faster performance after the $p\geq 1000$ cases, and with competitive mean squared error if $N$ or $P$ is large ($N$ or $p\geq 1000$). Empirically speaking, it’s quite safe to conclude that stochastic gradient descent is the better scalable algorithm. Moreover, SGD’s error is independent of the correlation, so while elastic net is faster for small $N$ or $p$, we still recommend using SGD in the case of highly correlated variables and small $N$ or $p$. The better estimate provided by SGD may be worth more than the slightly slower runtime.

We can also run the same simulation varying $N$ and $p$ with averaged SGD (ASGD), which takes roughly the same time as standard SGD but with an improved estimate. The results would essentially be the same, only that the cutoff for a better estimate for ASGD over elastic net would be at a smaller $N$ than standard SGD’s.

The takeaway message? SGD is awesome.

[1] J. Friedman, T. Hastie, and R. Tibshirani. Regularization paths for generalized linear models via coordinate descent. Journal of statistical software, 33(1):1, 2010.

[2] R. Tibshirani. Regression Shrinkage and Selection via the Lasso. Journal of the Royal Statistical Society B, 58:267–288, 1996.

[3] H. Zou H, T. Hastie. Regularization and Variable Selection via the Elastic Net. Journal of the Royal Statistical Society B, 67(2):301–320, 2005.