# Why does forward selection only take $O(p^2)$ calls to the learning algorithm?

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.

• +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/….
– Dave
Jul 23, 2020 at 21:38
• @Dave Wait, is forward selection a subset of stepwise regression? Jul 23, 2020 at 23:14
• 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)?
– Dave
Jul 24, 2020 at 0:08
• @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. Jul 24, 2020 at 2:11
• 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. Jul 24, 2020 at 5:55

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]$$.
• 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? Jul 23, 2020 at 23:17