What an Exhaustive Best-Subset Search Does
Suppose a regression analysis has \(p\) candidate predictors. A subset is one particular choice of which predictors to include. An exhaustive best-subset search fits a model for every allowed subset, identifies the best-fitting subset at each exact size, and then compares those size-specific winners to decide which model to use. The search is exhaustive because it considers every allowed combination, rather than adding or removing predictors along a single path.
For a standard search with an intercept and \(p\) candidate predictors, every predictor is either included or excluded. There are \(2^p\) subsets, including the empty subset, which gives an intercept-only model. Of these, \(\binom{p}{k}\) contain exactly \(k\) predictors. Thus, the search first organizes fits into exact-size groups; it does not yet answer which size should be selected.
“Best at size \(k\)” and “best overall” are different claims. The first is a comparison among models of the same size. The second requires a rule for comparing different sizes. A search can identify every size-specific winner without deciding which one should ultimately be selected.
Counting and Organizing the Fits
If all subsets are allowed, each of the \(p\) predictors has two choices, so the total number of candidate models is \(2^p\). Equivalently, counting by exact size gives the same total:
The empty subset counts as a model, and the full subset contains all \(p\) candidate predictors. If an intercept is included in every model, it is not counted as one of the optional predictors. For example, with four optional predictors the search contains \(1+4+6+4+1=16\) models: one of size zero, four of size one, six of size two, four of size three, and one of size four.
In practice, the search can be recorded in a table with one row per subset. For each row, record the included predictors, the number of predictors, and the fit measure. Then, within each exact-size group, find the smallest training RSS. Ties can occur; if so, there is more than one size-specific winner under that criterion, and any tie-breaking rule should be stated rather than assumed.
State which terms may be included and whether any combinations are prohibited or required.
For an unrestricted search, include all \(2^p\) combinations, including the empty subset.
Use the same response and training observations for the candidate fits being compared.
Within each size, select the allowed model with the smallest training RSS, or with another stated within-size criterion.
Use a stated selection criterion, such as a validation error or an information criterion, rather than treating the smallest training RSS as the complete selection rule.
Why Orthogonal Predictors Make a Useful Check
A simple derivation shows how the RSS values can be checked in a special case. Assume a least-squares regression with an intercept, centered response \(y\), and centered predictor columns that are mutually orthogonal. For predictor \(x_j\), its fitted coefficient in a model containing it is \(\hat{\beta}_j=(x_j^\mathsf{T}y)/(x_j^\mathsf{T}x_j)\). The reduction in RSS from adding this predictor is \((x_j^\mathsf{T}y)^2/(x_j^\mathsf{T}x_j)\).
To see why, the fitted component from \(x_j\) is \(\hat{\beta}_j x_j\), whose squared length is \(\hat{\beta}_j^2x_j^\mathsf{T}x_j\). Substituting the coefficient gives the stated reduction. Because the predictor columns are orthogonal, adding one does not alter the fitted component from another. Therefore, for a subset \(S\),
This shortcut depends on orthogonality and centering. With correlated predictors, the reduction associated with a predictor can depend on which other predictors are in the model; fit each subset rather than adding separate one-predictor reductions.
Worked Example: Enumerating All Subsets with Orthogonal Predictors
A hypothetical training set has centered response with \(\operatorname{TSS}=120\) and three mutually orthogonal, centered candidate predictors \(A\), \(B\), and \(C\). Their respective squared projection lengths, \((x_j^\mathsf{T}y)^2/(x_j^\mathsf{T}x_j)\), are 30, 25, and 10. Find the RSS for every subset and the best subset at each size. A separate validation sample of 10 observations gives validation SSEs of 20 for the intercept-only model, 12 for the size-one winner, 14 for the size-two winner, and 17 for the size-three model.
Method. There are \(2^3=8\) subsets. Orthogonality lets us subtract the projection contributions for included predictors from 120:
| Subset | Size | RSS calculation | Training RSS |
|---|---|---|---|
| Empty | 0 | \(120\) | 120 |
| \(A\) | 1 | \(120-30\) | 90 |
| \(B\) | 1 | \(120-25\) | 95 |
| \(C\) | 1 | \(120-10\) | 110 |
| \(A,B\) | 2 | \(120-30-25\) | 65 |
| \(A,C\) | 2 | \(120-30-10\) | 80 |
| \(B,C\) | 2 | \(120-25-10\) | 85 |
| \(A,B,C\) | 3 | \(120-30-25-10\) | 55 |
Size-specific winners. At size zero, the only model has RSS 120. At size one, \(A\) wins with RSS 90, compared with 95 and 110. At size two, \(A,B\) wins with RSS 65, compared with 80 and 85. At size three, the full model has RSS 55.
Compare model sizes. Validation MSE is validation SSE divided by 10. The four values are \(20/10=2.0\), \(12/10=1.2\), \(14/10=1.4\), and \(17/10=1.7\). The smallest is 1.2, so this stated validation rule selects the size-one model containing \(A\). The training-RSS winner across all eight fits is instead the size-three model, with RSS 55.
Check and common mistake. The table contains \(1+3+3+1=8\) fits, as required. Choosing the full model solely because its training RSS is smallest would confuse fitting the training data with selecting a model for its validation performance.
Comparing the Size-Specific Winners
Once the search has produced one or more winners at each size, a separate decision is needed. Training RSS is a fit measure on the observations used to estimate the coefficients. By itself, it does not provide a complete rule for choosing between models of different sizes. A model-selection procedure may instead use validation performance or an information criterion. The criterion must be specified, and the same comparison procedure must be applied to the candidate winners.
For example, if validation squared error is the chosen criterion, calculate the predictions on the same validation observations for every size-specific winner and compare their validation errors. If an information criterion is used, its complexity penalty is part of the comparison; do not compare only its fit component. The detailed definition and assumptions of a particular criterion matter, but the search itself is separate from that choice.
The scope of “size” also needs care. In a basic search, size is the number of included predictors. With multi-parameter factors or grouped terms, a search may count included variables or count regression coefficients; those are not necessarily the same. State the convention. Likewise, if scientific or modeling requirements prohibit some combinations, the search should enumerate the allowed subsets, not blindly report \(2^p\) fits as though all combinations were admissible.
Worked Example: Finding Winners When Predictors Are Correlated
A hypothetical regression analysis considers three candidate predictors \(A\), \(B\), and \(C\). Least-squares fitting on the same training observations gives the following RSS values. The predictors need not be orthogonal. Find the exact-size winners, then use the supplied validation SSEs to choose a model size. The validation set has 20 observations.
| Subset | Training RSS |
|---|---|
| Empty | 100 |
| \(A\) | 72 |
| \(B\) | 68 |
| \(C\) | 80 |
| \(A,B\) | 54 |
| \(A,C\) | 60 |
| \(B,C\) | 57 |
| \(A,B,C\) | 50 |
Method. First group by size. Size zero has only the empty subset, with RSS 100. The size-one comparison is \(72,68,80\), so \(B\) wins with RSS 68. The size-two comparison is \(54,60,57\), so \(A,B\) wins with RSS 54. The only size-three model is \(A,B,C\), with RSS 50. This accounts for all \(1+3+3+1=8\) subsets.
The validation SSEs for the size-zero, size-one, size-two, and size-three winners are respectively 42, 30, 28, and 34. Divide each by 20 to obtain validation MSEs: \(42/20=2.10\), \(30/20=1.50\), \(28/20=1.40\), and \(34/20=1.70\). Under this criterion, select the size-two winner, \(A,B\).
Check and common mistake. The winning subset at size one is \(B\), even though \(A\) may be associated with a strong fit in another subset. The winning subset at size two is \(A,B\). Do not rank individual predictors by their one-predictor RSS and assume that this ranking determines the best combination; with correlated predictors, subset fits must be compared directly.
Allowed Subsets and Practical Limits
An exhaustive search is exact only relative to its stated candidate set and restrictions. For example, a model with an interaction term is sometimes required to include both corresponding main effects. That rule reduces the set of admissible models. The search should still examine every admissible subset and identify the best model at each size represented among those subsets. A size can have fewer candidates than \(\binom{p}{k}\) when restrictions apply.
The number of fits grows quickly: with 10 unrestricted predictors there are \(2^{10}=1{,}024\) models, while with 20 there are \(2^{20}=1{,}048{,}576\). Exhaustive search is therefore most practical when the candidate set is modest or when specialized computation makes the fits feasible. A search that stops early or explores only a fraction of the subsets is not exhaustive, even if it finds a strong model.
- Keep the two decisions separate. First find the best subset within each size; then compare the winners across sizes.
- Use a consistent candidate set. State whether the intercept is fixed in all models and which predictors or terms are optional.
- Count what the procedure counts. Predictor count and coefficient count can differ for grouped or multi-level terms.
- Do not overinterpret exhaustive. It means all allowed candidates were considered; it does not guarantee the chosen model is scientifically appropriate or performs well on new data.
Worked Example: Exhaustive Search with an Interaction Restriction
A hypothetical analysis considers main effects \(A\), \(B\), and \(C\), plus the interaction \(A:B\). The modeling rule permits \(A:B\) only when both \(A\) and \(B\) are included. The following training RSS values are obtained for every allowed model. Find the size-specific winners and select a model using validation SSE on 10 observations.
| Allowed subset | Size | Training RSS |
|---|---|---|
| Empty | 0 | 100 |
| \(A\) | 1 | 80 |
| \(B\) | 1 | 85 |
| \(C\) | 1 | 90 |
| \(A,B\) | 2 | 60 |
| \(A,C\) | 2 | 75 |
| \(B,C\) | 2 | 78 |
| \(A,B,C\) | 3 | 55 |
| \(A,B,A:B\) | 3 | 47 |
| \(A,B,C,A:B\) | 4 | 42 |
Enumerate allowed models. Without the interaction, the three main effects give \(2^3=8\) subsets. If the interaction is included, both \(A\) and \(B\) must also be present, so the only additional allowed subsets are \(A,B,A:B\) and \(A,B,C,A:B\). There are \(8+2=10\) allowed fits, exactly the number of rows in the table.
Find winners by size. Size zero has RSS 100. At size one, \(A\) wins with RSS 80. At size two, \(A,B\) wins with RSS 60. At size three, compare \(A,B,C\) at 55 with \(A,B,A:B\) at 47; the interaction model wins. At size four, the only model has RSS 42.
Validation SSEs for the five size-specific winners, in increasing size order, are 38, 29, 21, 22, and 27. Their validation MSEs are \(38/10=3.8\), \(29/10=2.9\), \(21/10=2.1\), \(22/10=2.2\), and \(27/10=2.7\). The smallest is 2.1, so the selected model is \(A,B\). It is not the size-three training-RSS winner or the full model.
Check and common mistake. The restricted search has 10 fits, not \(2^4=16\), because six combinations containing the interaction violate the rule. Counting all four terms as independently optional would include inadmissible models and would answer a different search problem.
Check Your Understanding
For each problem, keep the within-size search separate from the comparison across sizes.
- An unrestricted search has five candidate predictors. How many models are fitted in total, including the intercept-only model, and how many models have exactly three predictors? (Answer: 32 total models; 10 models of size three.)
- For four candidate subsets of size two, the training RSS values are 41, 38, 44, and 39. Which is the size-two winner, and what is its RSS? (Answer: The subset with RSS 38; its RSS is 38.)
- Three size-specific winners have validation SSEs 24, 18, and 21 on a common validation set of 12 observations. Which winner is preferred by validation MSE, and what is that MSE? (Answer: The second winner; \(18/12=1.5\).)
- Main effects \(A,B,C\) are candidates, and interaction \(A:B\) is allowed only when both \(A\) and \(B\) are included. How many subsets are allowed, and how many allowed subsets have size three? (Answer: 10 allowed subsets; 2 of size three.)
- An unrestricted search has six candidate predictors, and each fitted model takes two seconds. How many models are fitted, how many have exactly four predictors, and how long does fitting all models take if fits are performed sequentially? (Answer: 64 models; 15 of size four; 128 seconds.)