Computational Limits of Exhaustive Search

Why Exhaustive Search Becomes Expensive

Best-subset selection asks which combinations of candidate predictors give the strongest models. Its appeal is straightforward: unlike a search that follows only one path through the candidates, exhaustive search can compare every allowed subset. Its cost grows rapidly, however. With \(p\) candidate predictors, each predictor is either included or excluded, creating \(2^p\) possible subsets.

The exponential count matters because each candidate model may require a regression fit and a score, such as residual sum of squares (RSS) or a model-selection criterion. A search that is practical for a handful of predictors can become infeasible as \(p\) grows. Branch-and-bound addresses this computational problem: it can skip groups of candidate models when a valid bound shows that none can improve the best model found so far.

What Is Being Counted?

The count follows because each predictor has two choices, included or excluded. Multiplying the two choices across \(p\) predictors gives \(2\times2\times\cdots\times2=2^p\). If the intercept-only model is not counted as a candidate, the number is \(2^p-1\). The intercept does not count as one of the \(p\) candidate predictors.

The first formula counts subsets of a particular size \(k\): choose \(k\) predictors from \(p\). The second adds the counts at all sizes. Exhaustive best-subset procedures commonly find the best model at each size, then use a chosen criterion to compare sizes. They need not use the same criterion for both tasks.

The Computational Growth

The count doubles whenever one additional candidate predictor is added: \(2^{p+1}=2\cdot2^p\). This is exponential growth, not a small fixed increase per predictor. The following counts include the empty subset.

For scale, if fitting and scoring each model took an idealized one millisecond, a serial search over the \(2^{30}\) subsets would take about \(1{,}073{,}742\) seconds, or 12.4 days. Real computation also has overhead, and the time per fit depends on the data and implementation. The calculation is only an illustration, but it shows why an algorithm that avoids some fits may be valuable.

Branch-and-Bound: Search With a Safe Bound

Branch-and-bound organizes candidate subsets into branches. At a branch point, some predictors have been selected, some excluded, and some left undecided. Instead of fitting every completion of that partial choice, the algorithm calculates a bound on how good any completion could possibly be. If even that bound cannot beat the current best candidate, the whole branch can be pruned.

For least-squares best subsets, a useful fact is that adding predictors cannot increase the minimum RSS when the response, observations, and fitting rules stay fixed. The larger model can always set the added coefficients to zero and reproduce the smaller model's fit. Therefore, the RSS of the model containing all selected and undecided predictors is a lower bound on the RSS of each of its smaller descendant models.

Why the Bound Is Valid

Let \(S\) be the predictors already selected at a branch, \(U\) the undecided predictors, and \(E\) the predictors excluded. Any completion of that branch uses a subset of \(S\cup U\). Denote by \(\operatorname{RSS}(A)\) the least-squares RSS for the model using predictor set \(A\), with the same intercept convention throughout.

The fitted values available to a model using a subset of \(S\cup U\) are also available to the model using all of \(S\cup U\): it can set coefficients for unused predictors to zero. Since least squares minimizes RSS over the available fitted values, the larger model's minimum RSS cannot be greater. Thus, for every completion \(C\) of the branch,

For a fixed target size \(k\), if the incumbent has RSS \(R_k\) and \(\operatorname{RSS}(S\cup U)>R_k\), then every feasible completion has RSS greater than \(R_k\). None can be the minimum-RSS size-\(k\) subset. The strict inequality avoids discarding a tied optimum; if only one optimum is required, a tie can be handled according to the algorithm's stated tie rule.

This argument is an exact justification for pruning, not a heuristic guess about which predictors are promising. It relies on a valid bound and on comparing models under the same least-squares setup. A bound that is merely plausible, rather than guaranteed, could remove the true best model.

From Best RSS at Each Size to a Selection Criterion

Many best-subset procedures first identify the lowest-RSS model at each size. They then compare those size-specific winners using a criterion such as AIC, BIC, or Mallows \(C_p\). For a fixed size and the usual least-squares versions of these criteria, the penalty for model size is constant, so lower RSS gives the preferred model at that size. Once the best model for each size is known, the selected size can be determined by the specified criterion.

Branch-and-bound can therefore preserve the exhaustive answer by finding the exact minimum-RSS subset at every required size, then applying the same criterion to those winners. It changes which models must be fitted, not the definition of the winner. This guarantee depends on using a valid pruning bound and searching all branches that could still contain an improvement.

The least-squares nesting argument is algebraic; it does not require normally distributed errors. If the goal is statistical inference rather than computational comparison, the relevant regression assumptions still matter for that inference. And if candidate models are subject to extra restrictions, such as grouped inclusion rules, the branches and bounds must respect those restrictions.

What Branch-and-Bound Can and Cannot Promise

Branch-and-bound can substantially reduce the number of fitted models when the bounds quickly become worse than an incumbent. Its savings are data- and problem-dependent, however. If bounds are weak, or many models remain potentially competitive, the search may approach the exhaustive count. In the worst case, branch-and-bound still has exponential computational cost.

The method also has costs of its own: it must organize the search, calculate bounds, and maintain the best candidates found so far. Whether it is faster depends on whether the avoided fits outweigh that overhead. Most importantly, fewer fitted models do not by themselves mean a less accurate answer. With valid bounds, the exact best-subset result is unchanged; without valid bounds, pruning can turn an exact search into an unreliable shortcut.

Common Mistake

• Wrong reasoning: “Branch-and-bound is faster because it skips models, so it must return an approximate answer.”
• Correction: It can return the exact best-subset answer if every pruned branch is ruled out by a mathematically valid bound. The number of fits may be lower, but the best model is unchanged.
• Another pitfall: “The search fits fewer models, so its runtime is guaranteed to be small.” Avoided fits do not guarantee a large saving; bounds can be weak, and worst-case growth remains exponential.