Why a Locally Best Choice May Not Lead to the Best Subset
A greedy search makes its next move using the choices available at the current step. In forward selection, that means adding the predictor that gives the largest immediate decrease in residual sum of squares (RSS). The choice is locally best, but it can affect which predictors are useful later. A predictor that looks modest on its own may work especially well with another predictor that the search has not yet selected.
This distinction matters whenever the goal is to find the best model of a specified size. A search path examines only subsets reachable through its earlier decisions; exhaustive search compares every subset of that size. The two methods can therefore reach different answers, even when every step of the greedy search is carried out correctly.
The comparison must use the same response and analysis observations. At a given step, forward selection compares only additions to its current subset. Exhaustive best-subset search instead compares all possible subsets of the requested size, whether or not they contain variables selected at earlier steps.
Why the Immediate RSS Reduction Depends on the Current Model
Assume least squares with a fixed set of observations. Center the response and predictors, or equivalently account for the intercept separately. Write \(M_S\) for the space spanned by the predictors already in subset \(S\), and let \(P_S\) denote projection onto that space. The current residual vector is \(r_S=(I-P_S)y\). For a candidate predictor \(x_j\), its part not already represented by \(S\) is \(z=(I-P_S)x_j\).
This formula explains what forward selection is comparing: the squared projection of the current residual onto the part of the new predictor that the current model does not already explain. If \(z=0\), the candidate predictor adds no new direction to the model and cannot reduce RSS.
Project the candidate predictor away from \(M_S\), producing \(z=(I-P_S)x_j\). This is the candidate's new contribution beyond the predictors already selected.
The quantity \(r_S^\mathsf{T}z\) measures how much of the unexplained response aligns with that new contribution.
Projecting \(r_S\) onto the one-dimensional direction \(z\) reduces its squared length by \((r_S^\mathsf{T}z)^2/(z^\mathsf{T}z)\).
The result follows because \(z\) is orthogonal to the current model space. Adding \(x_j\) therefore expands the model by the direction \(z\), and the updated residual is \(r_S-z(r_S^\mathsf{T}z)/(z^\mathsf{T}z)\). Expanding its squared length gives the formula:
Thus the value of a predictor is conditional on the current subset. A variable's marginal fit when entered first is not enough to determine how valuable it would be in another subset.
Worked Example: A Forward Addition Misses the Best Pair
In a hypothetical regression, use an orthonormal coordinate system for centered observations. The response vector is \(y=(1,0,0)\), and three unit-length predictors are \(A=(3/5,0,4/5)\), \(B=(1/2,\sqrt{3}/2,0)\), and \(C=(1/2,-\sqrt{3}/2,0)\). Find the forward-selected pair and compare its RSS with the best pair. The intercept-only RSS is \(y^\mathsf{T}y=1\).
Step 1: Calculate the three one-predictor RSS values. Each predictor has length one, so the reduction from adding a predictor alone is its squared inner product with \(y\). For \(A\), \(y^\mathsf{T}A=3/5\), giving \(\operatorname{RSS}(\{A\})=1-(3/5)^2=16/25=0.64\). For \(B\) and \(C\), the inner product is \(1/2\), so each gives \(1-(1/2)^2=3/4=0.75\). Forward selection therefore adds \(A\) first.
Step 2: Calculate the RSS after adding \(B\) to \(A\). The plane spanned by \(A\) and \(B\) has a normal vector \(A\times B=(-2\sqrt{3}/5,\,2/5,\,3\sqrt{3}/10)\). Its squared length is \(12/25+4/25+27/100=91/100\). The squared distance from \(y\) to this plane is the squared component of \(y\) along the unit normal: \((12/25)/(91/100)=48/91\). Thus \(\operatorname{RSS}(\{A,B\})=48/91\), approximately \(0.5275\).
Step 3: Compare the other forward addition and the exhaustive pair. By symmetry, \(\operatorname{RSS}(\{A,C\})=48/91\), so either \(B\) or \(C\) is an equally good second addition after \(A\). However, \(B\) and \(C\) span the plane with third coordinate zero, which contains \(y\). Therefore \(\operatorname{RSS}(\{B,C\})=0\). The best pair is \(B,C\), not a pair containing the first forward choice \(A\).
Check. The pair RSS values are \(48/91\), \(48/91\), and \(0\), all no greater than their one-predictor subset RSS values. The forward search correctly finds the best addition after \(A\), but its pair has positive RSS while the exhaustive best pair fits this constructed response exactly. The method avoids the mistake of assuming the best single predictor must belong to the best pair.
Comparing the Search Path With All Subsets of a Fixed Size
The following hypothetical regression output illustrates the same issue without requiring predictor coordinates. Suppose a risk analyst models a continuous claim-cost adjustment using predictors \(A\), \(B\), and \(C\). Treat the table as fitted RSS values from the same observations, with an intercept in every model. The scenario and values are illustrative, not industry data.
Worked Example: Finding the Best Two-Predictor Model From RSS Output
The intercept-only model has RSS \(500\). The one-predictor RSS values are \(380\) for \(A\), \(410\) for \(B\), and \(430\) for \(C\). The two-predictor RSS values are \(320\) for \(AB\), \(350\) for \(AC\), and \(210\) for \(BC\). Find the forward-selected pair and the exhaustive best pair, then quantify the difference.
Step 1: Select the first predictor. The smallest one-predictor RSS is \(380\), so forward selection first chooses \(A\).
Step 2: Select the second predictor along the forward path. The available additions produce RSS \(320\) for \(AB\) and \(350\) for \(AC\). Forward selection adds \(B\), reaching \(AB\) with RSS \(320\).
Step 3: Search all pairs. The exhaustive comparison is \(AB:320\), \(AC:350\), and \(BC:210\). The best pair is \(BC\), with RSS \(210\). It improves on the forward pair's RSS by \(320-210=110\) units.
Check. Each two-predictor RSS is less than or equal to the RSS for either of its one-predictor subsets, as required for nested least-squares models. Forward selection chooses the best available addition at each step, yet it does not find the best pair overall. The method avoids comparing only models along the forward path when the question asks for the best model of a specified size.
Worked Example: A Four-Predictor Search at Two Model Sizes
For a hypothetical equipment-maintenance response, suppose the fitted RSS values on one common sample are as follows. The intercept-only RSS is \(200\); the one-predictor RSS values are \(A:150\), \(B:160\), \(C:170\), and \(D:180\). For pairs, the values are \(AB:120\), \(AC:140\), \(AD:145\), \(BC:80\), \(BD:100\), and \(CD:90\). For triples, they are \(ABC:70\), \(ABD:85\), \(ACD:75\), and \(BCD:60\). The full model \(ABCD\) has RSS \(45\). Trace forward selection through size three and compare it with exhaustive search at sizes two and three.
Step 1: Reach size one. Among the single predictors, \(A\) has the smallest RSS, \(150\), so it enters first.
Step 2: Reach size two. Given \(A\), the possible additions give \(AB:120\), \(AC:140\), and \(AD:145\). The search chooses \(B\), reaching \(AB\) with RSS \(120\). Across all six pairs, however, the smallest RSS is \(BC:80\). Thus the forward pair has \(120-80=40\) more residual sum of squares than the exhaustive best pair.
Step 3: Reach size three. From \(AB\), adding \(C\) gives \(ABC:70\), while adding \(D\) gives \(ABD:85\). Forward selection chooses \(ABC\). Among all four triples, the smallest RSS is \(BCD:60\), so forward selection also misses the best triple. The full-model value \(45\) is no greater than the listed triple RSS values, consistent with adding a predictor not increasing training RSS.
Check. At both sizes, the forward result is a valid model on the search path, but it is not the minimum-RSS subset of that size. The method avoids treating a good fit at a larger model size, such as the full model's RSS of \(45\), as evidence that the path found the best smaller model.
Common Exam Trap and Practical Interpretation
Wrong calculation: “\(A\) has the smallest one-predictor RSS, so the best two-predictor model must contain \(A\).” This conclusion does not follow. In the four-predictor example, \(A\) is best alone, but the best pair is \(BC\), with RSS \(80\), compared with \(120\) for the forward-selected \(AB\).
Correction: If the task asks for the best subset of size \(k\), compare all subsets of size \(k\) when exhaustive results are available. If the task asks what forward selection reaches, follow the sequential additions from the current subset. These are different questions and can have different answers.
The same issue can arise for a backward search: its local comparisons are among deletions from the current model, not among every subset of the eventual target size. Neither greedy path is a general guarantee of the best subset at every size. The examples here focus on forward search because its early choice makes the restriction especially visible: after \(A\) enters, later steps cannot reach a subset that excludes \(A\).
Check Your Understanding
For each problem, distinguish the local choice from the best subset of the requested size.
- A regression has intercept-only RSS \(100\), one-predictor RSS values \(A:60\), \(B:55\), and \(C:70\), and pair RSS values \(AB:42\), \(AC:40\), and \(BC:30\). Which predictor enters first in forward selection, which pair does it reach, and what is the exhaustive best pair? (Answer: \(B\) enters first; forward selection reaches \(BC\) with RSS \(30\); the exhaustive best pair is also \(BC\), with RSS \(30\).)
- One-predictor RSS values are \(A:80\), \(B:90\), and \(C:95\). Pair RSS values are \(AB:70\), \(AC:75\), and \(BC:40\). Which pair does forward selection reach, and which pair is best exhaustively? (Answer: Forward selection reaches \(AB\) with RSS \(70\); the exhaustive best pair is \(BC\) with RSS \(40\).)
- At a particular forward-search step, the current model has RSS \(64\). Adding predictor \(X\) gives RSS \(48\), and adding predictor \(Z\) gives RSS \(55\). Which addition is selected, and by how much does it reduce RSS? (Answer: Add \(X\); its RSS reduction is \(64-48=16\).)
- For four predictors, the one-predictor RSS values are \(A:150\), \(B:160\), \(C:170\), and \(D:180\). The pair RSS values are \(AB:120\), \(AC:140\), \(AD:145\), \(BC:80\), \(BD:100\), and \(CD:90\). What pair does forward selection reach, and what is the difference between its RSS and the exhaustive best pair's RSS? (Answer: Forward selection reaches \(AB\) with RSS \(120\); the exhaustive best pair is \(BC\) with RSS \(80\), a difference of \(40\).)
- Explain why the RSS reduction from adding a predictor cannot be judged solely by its one-predictor fit. (Answer: The reduction is based on the candidate predictor's component not already explained by the current model and its alignment with the current residual, so its conditional contribution can differ from its marginal contribution.)