What “Best” Means in Best-Subset Search
For a specified number of predictors, exhaustive best-subset search fits every candidate subset of that size and selects the one with the lowest value of a chosen score. The word best therefore has a precise meaning only after the score is named. When the score is training residual sum of squares, the search has a direct guarantee: it finds the minimum training RSS among the candidate models of that size. That guarantee is about the search and the score, not about whether the selected model is true or will predict best on new data.
To state the result, suppose there are \(p\) eligible predictors and a common response vector \(y\) for \(n\) observations. A candidate subset \(S\) contains \(k\) predictors. Each candidate model includes an intercept, and its coefficients are estimated by ordinary least squares (OLS). We compare only subsets of the same size \(k\), fit to the same response observations. The result concerns the finite set of candidate subsets being searched.
The guarantee requires a consistent comparison: the same response observations and response values, the same definition of RSS, and the same fitting procedure for every candidate. If some models use different observations, or if candidates are evaluated with a different score, the conclusion does not follow as stated. OLS coefficients need not be unique when predictors are linearly dependent, but the fitted values and RSS are still well-defined: they are determined by projection onto the model’s column space.
Why the RSS Winner Is the Global Winner at That Size
For each subset \(S\), OLS chooses the fitted vector that is closest to \(y\) in squared Euclidean distance among all fitted vectors the model can produce. In geometric terms, the fitted vector is the projection of \(y\) onto the column space spanned by the intercept and the predictors in \(S\). Once each model has been fitted this way, exhaustive search compares the resulting distances over every candidate subset.
The inner minimum is the OLS fit for a particular subset. The outer minimum compares those fitted models. Exhaustive search evaluates every eligible \(S\), so it must encounter a subset attaining the smallest value in this finite collection. This is a global statement within the specified candidate set; it does not say that any unsearched model, a model of another size, or a model assessed on new observations has a larger score.
A short least-squares justification makes the role of the fitting method clear. Write \(Z_S\) for the design matrix containing the intercept column and the predictors in \(S\). If \(Z_S\) has full column rank, the OLS estimate is \(\widehat{\beta}_S=(Z_S^{\mathsf T}Z_S)^{-1}Z_S^{\mathsf T}y\). It satisfies the normal equations \(Z_S^{\mathsf T}(y-Z_S\widehat{\beta}_S)=0\): the residual is orthogonal to every column of the design matrix. For any other coefficient vector \(\beta_S\), expand the squared error around the OLS estimate:
The cross-product term is zero by the normal equations, and the remaining added squared norm cannot be negative. Thus OLS attains the smallest RSS within each model’s column space. Exhaustive search then takes the smallest of those within-model minima. If the design is rank-deficient, the inverse formula is unavailable, but projection onto the column space gives the same least-squares conclusion.
Worked Example: Selecting One Predictor by RSS
A hypothetical insurer models annual claim cost from four observations using an intercept and one predictor at a time. The centered response is \(y-10=(4,-1,-3,0)\), and the three centered candidate predictors are \(u=(1,1,-1,-1)\), \(v=(1,-1,1,-1)\), and \(w=(1,-1,-1,1)\). Each predictor is orthogonal to the intercept and to the other two, and each has squared length 4. Use exhaustive search to select the one-predictor model with the smallest RSS.
Method. In this orthogonal design, the OLS slope for a centered predictor \(z\) is \(z^{\mathsf T}(y-10)/(z^{\mathsf T}z)\). Calculate the slope and residuals for each candidate, then compare the residual sums of squares.
For \(u\), the slope is \((4-1+3+0)/4=6/4=1.5\). Its fitted centered values are \(1.5u=(1.5,1.5,-1.5,-1.5)\), giving residuals \((2.5,-2.5,-1.5,1.5)\). Therefore \(\operatorname{RSS}(u)=2.5^2+(-2.5)^2+(-1.5)^2+1.5^2=6.25+6.25+2.25+2.25=17\).
For \(v\), the slope is \((4+1-3+0)/4=2/4=0.5\). Its fitted centered values are \((0.5,-0.5,0.5,-0.5)\), so the residuals are \((3.5,-0.5,-3.5,0.5)\). Thus \(\operatorname{RSS}(v)=12.25+0.25+12.25+0.25=25\).
For \(w\), the slope is \((4+1+3+0)/4=8/4=2\). Its fitted centered values are \((2,-2,-2,2)\), so the residuals are \((2,1,-1,-2)\). Thus \(\operatorname{RSS}(w)=4+1+1+4=10\). The three RSS values are 17, 25, and 10, so the exhaustive one-predictor search selects \(w\).
Check. The total centered response sum of squares is \(4^2+(-1)^2+(-3)^2+0^2=26\). The fitted sums of squares for \(u,v,w\) are \(1.5^2(4)=9\), \(0.5^2(4)=1\), and \(2^2(4)=16\). Subtracting these from 26 gives RSS values 17, 25, and 10, respectively. The check agrees. The mistake this calculation avoids is choosing the predictor with the largest absolute response association without comparing the actual residual sums of squares.
A Fixed-Size Search Can Be Checked Directly
Orthogonal predictors provide a transparent way to see why the size restriction matters. When centered predictors are mutually orthogonal, the squared fitted contribution from each predictor can be calculated separately. With \(k\) predictors in the model, the RSS is the total centered response sum of squares minus the contributions of the \(k\) selected predictors. In this special case, the smallest RSS is obtained by including the \(k\) largest contributions. In a general, nonorthogonal design, contributions do not separate this way, so each subset must be fitted and its RSS compared.
Worked Example: Comparing Every Two-Predictor Subset
A hypothetical portfolio model has five observations, an intercept, and four centered mutually orthogonal predictors. Their squared fitted contributions to the response are 8, 6, 3, and 5, respectively. The total centered response sum of squares is 22. An analyst searches all subsets containing exactly two predictors. Find the RSS for each candidate and identify the winner.
Method. For any subset, subtract the contributions of its included predictors from the total centered sum of squares, 22. There are \(\binom{4}{2}=6\) two-predictor subsets.
The subset containing predictors 1 and 2 has \(\operatorname{RSS}=22-8-6=8\). The subset containing 1 and 3 has \(\operatorname{RSS}=22-8-3=11\). The subset containing 1 and 4 has \(\operatorname{RSS}=22-8-5=9\).
The subset containing 2 and 3 has \(\operatorname{RSS}=22-6-3=13\). The subset containing 2 and 4 has \(\operatorname{RSS}=22-6-5=11\). The subset containing 3 and 4 has \(\operatorname{RSS}=22-3-5=14\). The smallest of the six values is 8, so the exhaustive search selects predictors 1 and 2.
Check. The largest two contributions are 8 and 6; including them leaves \(22-(8+6)=8\), as calculated. The comparison avoids a common shortcut error: choosing a subset because its predictors look individually useful without evaluating the combined model’s RSS. The shortcut is valid in this particular orthogonal example only because the contributions separate.
The Guarantee Belongs to the Score
Exhaustive search guarantees a minimum only for the score it actually evaluates. If the score is training RSS, the winner has the lowest training RSS among the searched subsets. If the score is a strictly increasing function of RSS alone, the ranking is unchanged: for example, comparing \(\log(\operatorname{RSS})\) gives the same winner as comparing RSS, provided all candidate RSS values are positive. A nondecreasing transformation preserves the ranking but can turn distinct values into ties.
A score that includes other information can rank candidates differently. For instance, a validation score measures error on observations not used to estimate the coefficients. A penalty or a different predictive criterion may also change which subset is preferred. In those situations, an exhaustive search can still find the best candidate under that stated score if every candidate is evaluated consistently, but the training-RSS guarantee does not determine the answer.
Worked Example: The Winner Changes With the Score
A hypothetical insurer fits two candidate models, each with exactly two predictors, on the same training observations. Model A has training RSS 12, and model B has training RSS 14. On a separate validation set of two observations, model A has residuals \((3,-3)\) and model B has residuals \((2,-2)\). Compare the training-RSS and validation-MSE winners.
Training-RSS comparison. Since \(12<14\), model A has the lower training RSS and is the exhaustive-search winner if training RSS is the chosen score.
Validation comparison. Model A’s validation sum of squared errors is \(3^2+(-3)^2=18\), so its validation MSE is \(18/2=9\). Model B’s validation sum of squared errors is \(2^2+(-2)^2=8\), so its validation MSE is \(8/2=4\). Since \(4<9\), model B is the validation-MSE winner.
Conclusion and check. The two models have the same predictor count, but model A wins on training RSS and model B wins on validation MSE. The arithmetic confirms both rankings. The common mistake is to claim that the smallest training RSS must also mean the smallest validation error; these are different scores evaluated on different data.
What the Result Does Not Establish
The guarantee is deliberately limited. It does not say that the winning subset is the true mechanism generating the response, that its coefficients have small uncertainty, or that it will predict best outside the training data. A lowest-RSS result is also conditional on the candidate predictors and model form supplied to the search. If a relevant predictor is unavailable or the specified relationship is unsuitable, exhaustive search cannot correct that limitation merely by comparing every subset.
Ties are possible. If two or more candidate subsets have the same minimum RSS, each is an RSS winner; the guarantee does not choose uniquely among them. Nor does “best at size \(k\)” compare that winner with models of other sizes. The fixed-size condition is part of the claim, not an incidental detail: this result alone provides no rule for selecting how many predictors to use.
Check Your Understanding
For each problem, identify the score being optimized and apply the fixed-size guarantee only where it fits.
- A three-predictor search produces training RSS values of 19, 15, 17, and 15 for four candidate subsets. Which subset or subsets are RSS winners, and what is the minimum RSS? (Answer: The second and fourth subsets tie; the minimum RSS is 15.)
- Four mutually orthogonal centered predictors contribute 12, 9, 7, and 2 to a response with total centered sum of squares 40. A search requires exactly two predictors. Find the winning subset and its RSS. (Answer: Select predictors 1 and 2; RSS \(=40-12-9=19\).)
- Two same-size candidate models have RSS values 6 and 10. The stated score is \(2\log(\operatorname{RSS})+4\). Which model has the lower score? (Answer: The model with RSS 6, because \(2\log(6)+4<2\log(10)+4\).)
- Two same-size models have training RSS values 21 and 24. Their validation residual vectors are \((1,-3)\) and \((2,-1)\), respectively. Which model wins on training RSS, and which wins on validation MSE? (Answer: The first model wins on training RSS; validation MSEs are \(10/2=5\) and \(5/2=2.5\), so the second wins on validation MSE.)
- Candidate A has RSS 11 from 40 observations, while candidate B has RSS 9 from 30 observations because some records were missing for B. Can the fixed-size RSS guarantee alone justify selecting B as the winner? (Answer: No. The models were not fitted to the same response observations, so their RSS values are not the consistent fixed-data comparison required by the guarantee.)