I am trying to compare computational complexity / estimation speed of three groups of methods for linear regression as distinguished in Hastie et al. "Elements of Statistical Learning" (2nd ed.), Chapter 3:

  1. Subset selection
  2. Shrinkage methods
  3. Methods using derived input directions (PCR, PLS)

The comparison can be very rough, just to give some idea. I gather that the answers may depend on the dimension of the problem and how that fits the computer architecture, so for a concrete example one may consider a sample size of 500 and 50 candidate regressors. I am mostly interested in motivation behind the computational complexity / estimation speed but not in how long it would take on a certain processor for the given example.

  • $\begingroup$ When using PCR or PLS, the number of components is a tuning parameter (similar to $\lambda$ in ridge regression). So these methods will also need to cross-validated to find the optimal number of components. LASSO also has one regularization parameter, but elastic net has two (elastic net = ridge + LASSO) so cross-validation is more expensive. Apart from that, LASSO is probably slower to fit than all other models, because it does not have a closed-form solution. $\endgroup$ – amoeba Oct 19 '15 at 15:00
  • $\begingroup$ Thank you! You comment would make a nice answer if you included two more details: (1) how expensive is one iteration of PCR and PLS as compared with one OLS run of the regular regression; (2) quantify the speed of LASSO more precisely to make it comparable to the speed of the regular regression (is it polynomially, exponentially, or linearly more expensive, and why). $\endgroup$ – Richard Hardy Oct 19 '15 at 15:08
  • $\begingroup$ Unfortunately, I don't have a ready answer to this, especially to (2). That's why I only left a comment. +1, by the way, and congratulations with 5k rep! $\endgroup$ – amoeba Oct 20 '15 at 20:04
  • 1
    $\begingroup$ @amoeba, thanks! I could not have expected to reach 5k when I started (very slowly) last year. But it's very exciting and rewarding to be an active member here at Cross Validated! $\endgroup$ – Richard Hardy Oct 21 '15 at 5:43
  • $\begingroup$ @amoeba, I think I got a hold of LASSO complexity if LARS algorithm is used; I updated my post accordingly. But I did not read the LARS paper carefully, so I am not completely sure it is correct... $\endgroup$ – Richard Hardy Jan 14 '16 at 12:28

Group 1:
The complexity/speed of group 1. seems not too difficult to figure out if brute force algorithms are used (although there may be more efficient alternatives such as the "leaps and bounds" algorithm). For example, full subset selection will require $2^K$ regressions to be fit given a pool of $K$ candidate features. An OLS fit of one linear regression has the complexity of $\mathcal{O}(K^2 n)$ (as per this post) where $n$ is the sample size. Hence, the total complexity of brute-force full subset selection should be $\mathcal{O}(2^K K^2 n)$.

Group 2:
The complexity/speed of group 2. is discussed in sections 3.8 and 3.9 of the book. For example, ridge regression with a given penalty $\lambda$ has the same computational complexity as a regular regression. Since $\lambda$ needs to be found using cross validation, the computational load increases linearly in the number of data splits used in cross-validation (say, $S$). If the $\lambda$ grid has $L$ points, the total complexity of ridge regression with tuning the $\lambda$ parameter will be $\mathcal{O}(LSK^2 n)$.
There is quite some talk about LASSO in the book, but I could not find quite what I need. However, I found on p. 443 of Efron et al. "Least Angle Regression" (2004) that LASSO complexity for a given $\lambda$ is the same as the complexity of an OLS fit of linear regression if LARS method is used. Then the total complexity of LASSO with tuning the $\lambda$ parameter will be $\mathcal{O}(LSK^2 n)$. (I did not read that paper carefully, so please correct me if I got this one wrong.)
Elastic net combines ridge and LASSO; the two have the same computational complexity; hence, the complexity of elastic net should be $\mathcal{O}(ALSK^2 n)$ where $A$ is the grid size of the tuning parameter $\alpha$ that balances the weights of ridge versus LASSO.

Group 3:
I still miss any note on the complexity/speed for group 3. which consists of principal components regression (PCR) and partial least squares (PLS).

| cite | improve this answer | |
  • $\begingroup$ I'm not sure this is correct. Doesn't LARS perform the entire regularization path (all the lambdas) for Lasso at the cost of a single OLS fit? Then of course there is also coordinate descent which can be much faster than LARS depending on the specifics of the problem. $\endgroup$ – OldSchool May 8 at 2:28
  • $\begingroup$ @OldSchool, you might be right. Could you give a reference I could check? $\endgroup$ – Richard Hardy May 11 at 6:23
  • $\begingroup$ Sure, here's a link to the original Standford paper. All implemented in glmnet. link $\endgroup$ – OldSchool May 11 at 17:11

It's only for one part of question 2 on group 3 above (namely PLS), but may be informative nonetheless: Srinivasan et al (2010, technical report; see https://www.umiacs.umd.edu/~balajiv/Papers/UMD_CS_TR_Pls_Gpu.pdf) did some measurements on PLS using the NIPALS algorithm - stating that time (and space) complexity of this algorithm be O(dN) - for extraction and including these in different models for a) detection of humans in images, and b) face recognition. Measurements were done using their own GPU based implementation.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.