Counting Fits And Comparing Search Costs

Why Count the Fits?

Subset searches differ not only in the models they can reach, but also in how many candidate regressions they evaluate to get there. Counting those fits gives a useful first comparison of computational burden. In particular, exhaustive search considers every subset, while forward and backward procedures follow a sequence of greedy steps.

The counts below concern candidate regression fits, not the time required to fit each regression. A regression with more predictors can take more computation than one with fewer predictors, and software may reuse intermediate calculations. Even so, the number of candidate fits reveals an important difference in how the procedures scale.

Exhaustive Search: Count Every Subset

For each of the \(p\) predictors, an exhaustive search either includes it or excludes it. Each predictor therefore has two possibilities, and the choices are independent across predictors. The total number of subsets, including the empty subset, is

The empty subset corresponds to the intercept-only model under the counting convention above. If the question asks only for nonempty subsets, the count is \(2^p-1\). For a search restricted to models of exactly size \(k\), there are \({p \choose k}\) candidates. If it considers all sizes from zero through \(q\), the count is \(\sum_{k=0}^{q}{p \choose k}\).

These distinctions matter: a search over every subset is not the same as a search over every subset up to a specified size. State which collection is being counted before calculating.

Forward Selection: Add One Predictor at a Time

Forward selection begins with the intercept-only model and evaluates possible one-predictor additions. After selecting a predictor, it evaluates additions to the resulting model, continuing until it reaches the chosen target size \(q\). At a step where the current model has \(j\) predictors, there are \(p-j\) predictors remaining as possible additions.

Thus, the number of candidate regressions evaluated to reach size \(q\), not counting the initial intercept-only reference fit, is

The count falls from step to step because a predictor chosen at an earlier step is no longer a candidate addition. If forward selection runs all the way to size \(p\), the candidate-fit count is \(p+(p-1)+\cdots+1=p(p+1)/2\). Include one more fit if the starting intercept-only regression is also counted.

Backward Elimination: Remove One Predictor at a Time

Backward elimination starts from the full model containing all \(p\) predictors. If the target is a model of size \(q\), the procedure evaluates possible removals from sizes \(p,p-1,\ldots,q+1\). From a model of size \(k\), there are \(k\) possible single-predictor removals. Therefore, the number of candidate regressions, excluding the initial full-model fit, is

The last candidate set is evaluated when the current model has \(q+1\) predictors: removing one produces a candidate model of size \(q\). If the initial full model is included in the count, add one. Continuing all the way to size zero requires \(p(p+1)/2\) candidate fits, plus the initial full-model fit if it is counted.

The forward and backward counts need not be equal when both procedures stop at the same size. Forward selection tests additions from the smaller models; backward elimination tests removals from the larger models. Their candidate sets are generated at different stages.

Comparing Fit Counts and Their Growth

For a complete forward path or a complete backward path, the number of candidate fits is \(p(p+1)/2\), which grows quadratically in \(p\). Exhaustive search instead evaluates \(2^p\) subsets, which grows exponentially. For small \(p\), the difference may be modest; for larger \(p\), exhaustive search can require vastly more regressions.

What the Counts Do and Do Not Say

These formulas count candidate subsets evaluated under a particular search procedure. They do not say that every subset of a given size is evaluated by a greedy search. For example, a forward procedure reaching size four evaluates four successive candidate layers along its selected path; it does not evaluate every four-predictor subset. Exhaustive search does evaluate all such subsets if it includes all model sizes.

Fit counts are also not identical to total computing time. A fit with \(k\) predictors may take more work than a fit with one predictor, and implementation choices can reduce repeated calculation. For a rough comparison, however, the exponential versus quadratic growth in the number of candidates is a central distinction. The counts also do not establish which procedure is preferable for a particular analysis; they describe search burden, not model quality.

Common Counting Traps

• Multiplying by the initial number of predictors at every forward step. The available set shrinks after each selected addition. Use \(p+(p-1)+\cdots\), not \(q p\).
• Omitting the last step. To reach size \(q\), forward selection evaluates additions that produce size \(q\); backward elimination evaluates removals that produce size \(q\).
• Mixing candidate fits with starting fits. The formulas exclude the intercept-only starting regression for forward selection and the full-model starting regression for backward elimination. Add one when the question asks for every fit including the start.
• Confusing all subsets with subsets of a specified size. Use \(2^p\) for all subsets, \({p\choose k}\) for exactly size \(k\), and a sum of binomial coefficients for a range of sizes.
• Equating a selected path with all models at that size. A greedy procedure evaluates candidates at each step, not every possible model of the final size.