In http://cs229.stanford.edu/notes/cs229-notes-all/cs229-notes5.pdf pg 5, it states that forward search takes $O(p^2)$ (note the notes uses $n$ instead of $p$ for the number if independent variables).

Isn't the number of calls actually $O(2^p \cdot k$)? You're consider all possible subsets of independent variables in forward search, of which there are $2^p$ of them. For each subset you perform a k-fold validation so $k$ learning calls for each subset.

How is it that it's quadratic instead of exponential?

  • $\begingroup$ +1 for the unusual question (at least on here) about time complexity, but please do note Andrew Gelman's stance on stepwise regression: statmodeling.stat.columbia.edu/2014/06/02/…. $\endgroup$
    – Dave
    Jul 23, 2020 at 21:38
  • $\begingroup$ @Dave Wait, is forward selection a subset of stepwise regression? $\endgroup$
    – David
    Jul 23, 2020 at 23:14
  • $\begingroup$ Isn’t forward selection trying out your variables, getting the best fit with one, and then adding additional variables one at a time until the increase in fit isn’t worth adding a new variable (measured by any number of methods, AIC, for example)? $\endgroup$
    – Dave
    Jul 24, 2020 at 0:08
  • $\begingroup$ @Dave Yes, when I originally posted this and replied to you, I misunderstood forward selection. I had thought it was a method that tests ALL possible subsets instead of approaching it in a greedy fashion. $\endgroup$
    – David
    Jul 24, 2020 at 2:11
  • 1
    $\begingroup$ Like so many things in statistics, stepwise model selection is wrong in many ways, but can be extremely useful. I think sometimes the strong opinions of seasoned statisticians can scare off those new to the field from developing a broad toolset while learning the limitations of different methods. $\endgroup$
    – abalter
    Jul 24, 2020 at 5:55

1 Answer 1


In the forward selection procedure described, the features are partitioned into selected vs. candidate sets. At the start, the selected set is empty, and all $p$ features are candidates. At each stage, each candidate feature is provisionally added as a(n additional) trial feature, and the best one is chosen to be kept.

So 1 new feature is removed from the candidate set after each iteration. This means the first iteration tests $p$ candidates, the second $p-1$, etc. And $p + (p-1) + \ldots + 2 + 1 = O[p^2]$.

Once a feature is added to the selected set, it is never removed in subsequent iterations. So the procedure does not explore all subsets of features. Rather it is a greedy heuristic, with no guarantees of optimality. (I believe this is why techniques like LASSO have become more popular for feature selection.)

  • $\begingroup$ Oh I think I misunderstood forward selection and the algorithm in the link I provided. Forward selection isn't the feature selection method that tests all possible subsets of the $p$ features? What is the name of the method that does? $\endgroup$
    – David
    Jul 23, 2020 at 23:17
  • $\begingroup$ @David I am not sure if there is a particular "method" for this. Some methods, like the LASSO path, allow feature selection considering all features together. This may be relevant. $\endgroup$
    – GeoMatt22
    Jul 24, 2020 at 1:48

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.