Forward Selection, Forward Stagewise and LARS are all used to solve the regression problem: $$y = \beta^Tx.$$ I understand how they work, but don't know the motivation of those algorithms. Since we already have the gradient descent or SVD to solve the least square estimation.

Are they just used to simplify the complexity? Since at most $n = dimension$ iterations is needed compared with gradient descent. Here we ignore the modified LARS for solving LASSO.


1 Answer 1


Those algorithms provide different ways to add predictors sequentially to a regression model, rather than solving the model all at once with standard least-squares fitting. They are used when the standard least-squares solution doesn't exist or you perform automated variable selection.

If the number of predictors in the model exceeds the number of observations, then there is no unique least-squares solution. These algorithms can select a subset of predictors to generate a solution.

Even when there is a unique least-squares solution, these algorithms can be used with a stopping rule to select a subset of predictors. Such an automated approach is often not wise. For example, you will typically find that the specific predictors returned by these algorithms differ among re-samples of the data. Thus any decision based on such results about which are the "most important" predictors is usually on shaky grounds.

With care, these approaches can sometimes be used for prediction and inference. The Statistical Learning with Sparsity book by Hastie et al goes into detail about their proper use.

  • $\begingroup$ can I understand when there is a unique least-squares solution as that these algorithms are not good compared with Least square solution? Thus they are only used for the degenerate case of linear regression? By the way, when the matrix is degenerate, I think the gradient descent of Least square will also converge to one of the solution, right? $\endgroup$ Apr 14, 2021 at 17:33
  • $\begingroup$ @user6703592 the algorithms are unnecessary if you want a solution that involves all of the predictors and you have more cases than predictors. "Not good" is perhaps more a matter of taste. If these stepwise approaches are taken out to include all predictors, I understand that they will still end up with the least-squares solution. In a degenerate case I'm not sure which "solution" will end up being the result once you have overfit the model to include as many predictors as possible. Usually these algorithms are stopped well before that situation, returning many fewer predictors than cases. $\endgroup$
    – EdM
    Apr 14, 2021 at 18:00
  • $\begingroup$ so I understand as these algorithms are mostly used in the degenerate case (sample > features) to make the iteration stopping at a short number rather than the least square having many iterations to obtain an exact solution (has a risk to overfit). Therefore, these algorithms offer the sparsity of features to avoid overfitting. Am I right? $\endgroup$ Apr 15, 2021 at 6:05
  • 1
    $\begingroup$ @user6703592 even if number of features is less than the degrees of freedom for the solution, the algorithms can still be useful due to the bias and variance tradeoff. $\endgroup$
    – runr
    Apr 15, 2021 at 8:57
  • $\begingroup$ @user6703592 I agree completely with the comment from runr. The situation doesn't have to be degenerate for (at least some of) these algorithms to be useful, particularly for a predictive model. With repeated cross-validation to choose the number of retained predictors based on mean-square error, they might return a number of predictors on the order of 1/10 the number of observations. That said, I would tend to prefer LASSO for that type of predictor selection, as it has penalization built in. See the freely available Statistical Learning with Sparisty book linked in my answer. $\endgroup$
    – EdM
    Apr 15, 2021 at 15:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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