Why the Compute Budget Changes the Search Choice
Subset selection can require fitting many candidate regression models. When the number of eligible predictors is small, comparing every subset may be practical. As the predictor count grows, the number of possible models grows rapidly, while forward and backward search examine only a sequence of candidates along a nested path. The decision is therefore a tradeoff: how much of the candidate set can the available computation cover?
A fit budget is useful for making that tradeoff concrete, but it does not decide which model is best. The candidate models must still be compared using a consistent selection criterion and analysis sample. Here the focus is the number of fits required and whether a search can start from the model it requires.
Counting Candidate Fits
For exhaustive search with \(p\) eligible predictors and no restrictions, each predictor is either included or excluded. There are therefore two choices for each of \(p\) predictors, giving \(2^p\) subsets. This count includes the null model, which has no predictors, and the full model, which has all \(p\).
A complete forward search evaluates the null starting model, then considers every one-predictor addition, every possible two-predictor addition along its chosen path, and continues until it reaches the full model. At a step where the current model contains \(j\) predictors, there are \(p-j\) possible additions. Across a complete path, the candidate evaluations total \(p+(p-1)+\cdots+1\), in addition to the null starting fit. Backward search has the same total: it starts at the full model and considers \(p+(p-1)+\cdots+1\) possible removals before reaching the null model.
These are counts of distinct subset models along a complete greedy path, assuming a model is not refitted unnecessarily. They do not mean forward and backward search examine the same models: they generally follow different paths. Neither path covers all \(2^p\) subsets.
A search that stops at a target size uses fewer fits. If forward search starts at the null model and adds predictors until it reaches size \(q\), it considers \(p+(p-1)+\cdots+(p-q+1)\) candidates, plus the null model. If backward search starts with all \(p\) predictors and removes predictors until it reaches size \(q\), the candidate counts are \(p+(p-1)+\cdots+(q+1)\), plus the full starting model.
The sums count candidate models at each step, not just the number of steps. For example, one step can require evaluating several alternatives before deciding which single change to make.
Worked Example: A Budget for Ten Predictors
A hypothetical pricing analysis has \(p=10\) eligible predictors. The analyst has a budget of 60 model fits and wants to search all the way from the null model to the full model if necessary. Which search methods fit within the budget, and which gives the broadest coverage?
Method: count the candidate models under each search. Exhaustive search requires \(2^{10}=1,024\) fits, since each of the ten predictors is either included or excluded. This exceeds the budget by \(1,024-60=964\) fits.
A complete forward search requires one null-model fit plus \(10+9+8+7+6+5+4+3+2+1=55\) candidate addition fits. Its total is \(1+55=56\), which is within the budget.
A complete backward search also requires 56 fits: one full-model fit plus 55 candidate deletion fits. It is within budget if the full model can be estimated.
Decision. Either complete greedy search meets the stated fit budget; exhaustive search does not. Exhaustive search would examine all 1,024 subsets if computation were available, whereas either greedy method examines only 56 models on its path. The choice between forward and backward must also respect their starting-model requirements. A common mistake is to call the 55 addition or deletion candidates the total: that omits the starting fit, so the correct total is 56.
Starting-Model Constraints Matter
A search method is useful only if its required starting model is allowed and can be fitted. Forward search needs a starting model, often a null model or a model containing mandatory predictors. Backward search needs an estimable starting model that includes all predictors eligible for removal. If the full model cannot be fitted, backward search cannot begin as specified.
Restrictions also change the size of the search space. Suppose \(m\) predictors are mandatory and \(r\) predictors are optional. If mandatory predictors must be present and no other restrictions apply, the allowed subsets correspond to the choices of which optional predictors to include. There are \(2^r\) such models, rather than \(2^{m+r}\). The mandatory predictors are included in every candidate; they are not part of the include-or-exclude choices.
A target-size rule also affects the comparison. Forward search can stop once it reaches a specified size; backward search can stop when it has removed enough predictors to reach that size. If a budget does not allow a complete search, a defined stopping rule is essential: the analyst should say what part of the search is being performed, rather than treating a partial path as a complete search.
Worked Example: Mandatory Predictors and a Target Size
A hypothetical claim-cost model must include two predictors required by the analysis plan. Four additional predictors are optional. The analyst can afford at most ten fits and wants to compare all allowed models or, if that is not affordable, search from the mandatory-predictor model to a total of four predictors. Determine the counts.
Exhaustive search. The two required predictors appear in every model. Only the four optional predictors vary, so the number of allowed subsets is \(2^4=16\). This exceeds the ten-fit budget.
Forward search to size four. The starting model contains the two mandatory predictors, so it has size two. Count that starting fit once. To reach size four, the first addition step considers each of the four optional predictors; the next considers each of the three that remain. The total is \(1+4+3=8\) fits.
Backward search to size four. The full allowed model contains six predictors: two mandatory and four optional. Count the full starting model once. The first deletion step has four eligible optional predictors; after one is removed, the next step has three. The total is \(1+4+3=8\) fits.
Decision. Exhaustive search is outside the budget, while either restricted greedy search can reach size four within it. Mandatory predictors cannot be deleted in backward search. Counting deletion of all six predictors as possible would be a mistake: only the four optional predictors may be removed, and the requested stopping size requires removing only two.
Feasibility Can Rule Out a Method
A fit budget is not the only constraint. A regression model must be estimable from the available data. For example, a model with too many linearly independent coefficients relative to the number of observations cannot have a unique ordinary least squares estimate. Collinearity can also make a model unestimable even when the predictor count alone appears acceptable.
Exhaustive search may still be feasible in principle if some subsets are excluded because they cannot be fitted, but then the candidate space and fit count must be adjusted to the actual restrictions. Forward search may be able to build an estimable model incrementally. Backward search cannot repair an unestimable full starting model through removals because it cannot take its first step.
Worked Example: When the Full Starting Model Cannot Be Fitted
A hypothetical study has six observations and seven eligible predictors, plus an intercept. Assume the design is such that every subset with at most five predictors is estimable, but models with six or seven predictors are not. The fit budget is 20. Compare exhaustive search with forward search through models of size three, and assess backward search.
Backward search. It requires the seven-predictor full model as its starting fit. That model is not estimable under the stated conditions, so backward search cannot start.
Exhaustive search over estimable subsets. A subset with \(k\) predictors has \(\binom{7}{k}\) possible choices. Only sizes zero through five are estimable, so the number of candidates is \(\binom{7}{0}+\binom{7}{1}+\binom{7}{2}+\binom{7}{3}+\binom{7}{4}+\binom{7}{5}\). The individual terms are \(1,7,21,35,35,21\), giving \(1+7+21+35+35+21=120\) fits. This exceeds the budget.
Forward search through size three. Count the null starting model once. The steps then evaluate 7 single-predictor models, 6 additions from the selected one-predictor model, and 5 additions from the selected two-predictor model. The total is \(1+7+6+5=19\) fits, within budget.
Decision. Forward search can reach size three within the budget; exhaustive search over all estimable subsets cannot, and backward search is infeasible because its required starting model cannot be fitted. This count assumes the search evaluates the stated candidates and does not refit the same subset unnecessarily. The example also shows why “fewer than \(2^p\)” is not, by itself, enough to make backward search possible.
Using Fit Counts Responsibly
Fit counts are a planning tool, not a perfect measure of elapsed computation. A model with more predictors can take longer to fit than a smaller model, and data preparation or other computational work may add substantial cost. If one fitting operation has a predictable cost, multiplying that cost by the count gives a rough budget estimate; if costs differ, use a more appropriate estimate.
Before choosing a method, check the constraints in this order:
List eligible, mandatory, and prohibited predictors, and note any model-size limits. These determine which subsets are actually allowed.
Confirm that the null or mandatory-predictor model is available for forward search and that the full allowed model is estimable for backward search.
Use the exhaustive subset count or the step-by-step path count, including the starting fit. Stop the count at the requested target size if the search stops early.
Choose a feasible search and state what it does and does not cover. A greedy path saves computation but does not examine every eligible subset.
A frequent exam trap is to compare \(2^p\) with \(p\), as though a greedy search fits only one model per predictor. At each step, it evaluates several possible additions or removals before choosing a step. The correct complete-path count is \(1+p(p+1)/2\), not \(p+1\). Another trap is to assume backward search is always available because a full model can be written down; it must also be estimable.
Check Your Understanding
Use the fit-count convention in this tutorial: include one fit for the starting model, and count each candidate model evaluated at a step.
- A complete forward search has nine eligible predictors. How many fits does it require, and would a budget of 50 fit the complete path? (Answer: \(1+9(10)/2=46\) fits; yes.)
- A forward search with eight eligible predictors starts at the null model and stops at size four. How many fits are evaluated? (Answer: \(1+8+7+6+5=27\) fits.)
- A backward search starts with ten predictors and stops at size six. How many fits are evaluated, including the full starting model? (Answer: \(1+10+9+8+7=35\) fits.)
- A model must contain three mandatory predictors, and five other predictors are optional. How many allowed models are in the exhaustive search space? How many fits does forward search use to add two optional predictors from the mandatory-predictor starting model? (Answer: \(2^5=32\) exhaustive models; \(1+5+4=10\) forward-search fits.)
- There are six eligible predictors and a budget of 25 fits. The full model is estimable. Can exhaustive search fit within budget? Can a complete forward path fit within budget? (Answer: exhaustive search requires \(2^6=64\) fits and cannot; a complete forward path requires \(1+6(7)/2=22\) fits and can.)