All-Subsets Search And Computational Limits

What an All-Subsets Search Does

Stepwise selection moves through a limited sequence of models. An all-subsets search instead considers every model in a specified finite family, fits each one, and compares them using a criterion chosen in advance. Its appeal is direct: if every admissible candidate is evaluated successfully, the procedure can identify the candidate with the best value of that criterion. Its limitation is equally direct: the number of candidates can grow too quickly for every fit to be practical.

The search is defined by its candidate predictors and its admissibility rules, not by a vague instruction to “try everything.” For example, the analyst might allow every subset of five named predictors while requiring an intercept. Or the candidate family might impose hierarchy constraints on interactions. The criterion also must be specified: AIC, BIC, or a predictive score can lead to different choices.

Definition: Let \(x_1,\ldots,x_p\) be a prespecified collection of candidate terms. For an admissible subset \(S\subseteq\{1,\ldots,p\}\), let \(M_S\) be the GLM containing the terms indexed by \(S\), together with any terms required in every candidate, such as an intercept. An all-subsets search evaluates a prespecified criterion \(C(M_S)\) for every admissible \(S\), then selects a model attaining the smallest criterion when smaller values are preferred. If larger values are preferred, the maximizing convention is used instead.

A criterion may be an information criterion or a predictive score. For example, for maximized log-likelihood \(\ell(\hat{\theta}_{M})\), AIC is \( -2\ell(\hat{\theta}_{M})+2k_M\), and BIC is \( -2\ell(\hat{\theta}_{M})+k_M\log n\), where \(k_M\) is the number of estimated parameters and \(n\) is the sample size. A cross-validation loss can also be minimized. The criterion and its fitting conventions should be fixed before comparing candidates.

Comparisons require a coherent candidate set. In particular, likelihood-based criteria must be calculated from comparable likelihoods on the same observations and response representation. Predictive scores should likewise use a common scoring definition and validation plan. Otherwise, a numerical ranking can reflect differences in how the scores were calculated rather than differences among the models.

Counting the Candidate Models

If each of \(p\) candidate terms can either be included or excluded independently, there are two choices for each term. The intercept, if required, is common to all candidates and does not double the count. Thus the number of subsets is \(2^p\).

Result: With \(p\) independently selectable terms and no restrictions on their combinations, an all-subsets search has \(2^p\) candidate models, including the model with none of the candidate terms. If exactly \(r\) terms must be included, there are \(\binom{p}{r}\) candidates.

To verify the unrestricted count, group the subsets by their size. There are \(\binom{p}{r}\) subsets of size \(r\), so the total is the sum of those counts:

\sum_{r=0}^{p}\binom{p}{r}=(1+1)^p=2^p.

The equality follows from the binomial theorem. It also makes clear why reporting only the number of predictors can be misleading: increasing \(p\) by one doubles the number of models.

Worked Example: Three Predictors and an AIC Comparison

Suppose a binary response is modeled by logistic regression using three candidate predictors \(A,B,C\), with an intercept in every model. All \(2^3=8\) subsets are admissible. Assume every fit converged, and that the following maximized log-likelihoods were obtained on the same 200 observations. The parameter count \(k\) includes the intercept. Calculate AIC for each model and identify the all-subsets choice.

Terms included	\(k\)	\(\ell(\hat{\theta}_M)\)	AIC calculation	AIC
None	1	-60	\(120+2\)	122
A	2	-53	\(106+4\)	110
B	2	-56	\(112+4\)	116
C	2	-59	\(118+4\)	122
A, B	3	-49	\(98+6\)	104
A, C	3	-52	\(104+6\)	110
B, C	3	-55	\(110+6\)	116
A, B, C	4	-48.5	\(97+8\)	105

For example, the A, B model has AIC \( -2(-49)+2(3)=98+6=104\). The model with all three predictors has AIC \( -2(-48.5)+2(4)=97+8=105\). Although that larger model has the highest log-likelihood in the table, its AIC is one point higher than the A, B model's. The minimum over all eight values is 104, so the all-subsets AIC choice is the model containing A and B. This conclusion is specifically about the stated candidate family and AIC criterion.

Constraints Change the Count

The \(2^p\) formula applies when terms can be selected independently. Model-building rules may make some combinations inadmissible. In particular, the earlier material on interactions with hierarchy motivates rules such as requiring both corresponding main effects whenever a two-way interaction is included. The search must count and evaluate only models that satisfy the rule.

Worked Example: Counting Models Under Strong Hierarchy

Consider three main effects \(A,B,C\) and their three pairwise interactions \(AB,AC,BC\). Suppose the strong-hierarchy rule requires both main effects whenever an interaction is present. Count the admissible models, with an intercept common to all.

First choose the set of included main effects. If it contains \(k\) main effects, only interactions between pairs in that set can be considered. There are \(\binom{k}{2}\) such interactions, each of which can be included or excluded. The number of admissible interaction choices for that main-effect set is therefore \(2^{\binom{k}{2}}\).

There is one main-effect set of size zero, three of size one, three of size two, and one of size three. Summing the allowable interaction choices gives

\binom{3}{0}2^{\binom{0}{2}} +\binom{3}{1}2^{\binom{1}{2}} +\binom{3}{2}2^{\binom{2}{2}} +\binom{3}{3}2^{\binom{3}{2}} =1+3+6+8=18.

Here \(\binom{0}{2}=\binom{1}{2}=0\), so the first two terms count one interaction configuration for each such main-effect set. The unrestricted six-term search would have \(2^6=64\) models, but 46 violate strong hierarchy. The count of 18 includes the intercept-only model.

This calculation also illustrates a general principle: constraints can reduce a search substantially, but the count depends on the precise constraints. A rule that allows an interaction when at least one main effect is present is not the same rule, and would produce a different candidate family.

Why Exhaustive Search Has Computational Limits

A finite search is not automatically a feasible search. The number of fits doubles whenever one independently selectable term is added. If fitting each model takes roughly \(t\) seconds, then a first approximation to the total fitting time is \(2^p t\). This ignores data preparation, failed fits, validation folds, and the cost of calculating or storing results, so it can understate the actual burden.

Worked Example: Estimating the Search Time

Suppose there are 30 independently selectable predictors and each model fit takes an average of 0.02 seconds. Ignoring overhead, how long would an exhaustive search take on one processor?

The candidate count is

2^{30}=1,073,741,824.

Multiplying by the assumed time per fit gives \(1,073,741,824(0.02)=21,474,836.48\) seconds. Converting to days,

\frac{21,474,836.48}{86,400}\approx 248.55\text{ days}.

Thus even a very fast individual fit can lead to a search lasting about 249 days on one processor, before accounting for overhead or repeated validation fits. Parallel computation can reduce elapsed time, but it does not remove the number of model evaluations; moreover, perfect speed-up is rarely achieved.

What Exhaustiveness Guarantees

The main guarantee is deliberately narrow: an exhaustive search finds the best criterion value among the candidates it actually evaluates, provided all fits and scores are well-defined and the search is completed. It does not establish that the candidate family contains the scientifically correct model, that the criterion is the right objective, or that the selected model will perform best on new data.

Result: Let \(\mathcal{M}\) be a nonempty finite candidate family. Suppose \(C(M)\) is a finite, well-defined score for every \(M\in\mathcal{M}\), and smaller values are preferred. If every member is evaluated, selecting a model with minimum score returns a global minimizer of \(C\) over \(\mathcal{M}\).

To prove the result, list the finite family as \(M_1,\ldots,M_q\). The evaluated scores \(C(M_1),\ldots,C(M_q)\) form a finite nonempty set of real numbers, so the set has a minimum. Let \(j\) be an index attaining that minimum. By definition, \(C(M_j)\leq C(M_i)\) for every \(i=1,\ldots,q\). Hence \(M_j\) is a global minimizer over the specified family. If several models tie, each tied model is a global minimizer; a prespecified tie-breaking rule can make the reported choice reproducible. \(\square\)

In practice, some candidate fits may fail to converge, or may not yield a finite criterion. The stated guarantee then applies only if the family and treatment of such failures have been defined so that every candidate receives a valid, comparable score. Silently dropping difficult models changes what was searched.

Exhaustive and Heuristic Approaches

A heuristic explores only part of the possible model space or avoids fitting every candidate. Stepwise selection is one example: it follows a sequence of additions or deletions determined by local comparisons. It can be much cheaper, but it does not generally guarantee the smallest criterion among all admissible subsets. A good model can be missed if reaching it would require passing through an intermediate model that the procedure rejects.

Other strategies include prescreening predictors, imposing scientifically justified restrictions, and using algorithms that prune parts of a search when they can certify that those parts cannot improve the current best score. Such pruning may preserve an exact global solution if its bounds are valid; a heuristic restriction or early stopping rule generally does not. The distinction is whether the method has a proof that excluded candidates cannot win, not whether the method sounds systematic.

Define the candidate family.
Specify terms, required components, interaction rules, and any other restrictions before fitting candidates.

Choose one comparison criterion.
State the score, which direction is preferred, and how all candidates will be fit and scored comparably.

Estimate feasibility.
Count admissible candidates and account for fitting time, validation repetitions, and possible convergence problems.

Search and report the scope.
If exhaustive, report the best score within the complete stated family. If not, identify the search as restricted or heuristic rather than claiming a global optimum.

Common Pitfalls

Calling a partial search exhaustive. Evaluating many subsets is not the same as evaluating every admissible subset. State which models were actually considered.
Changing the criterion during the search. Choosing whichever score favors a preferred model makes the optimization target unclear. Prespecify the criterion and apply it consistently.
Counting terms as parameters. A factor with several levels or a spline can require multiple coefficients. Information criteria use the fitted parameter count \(k_M\), not necessarily the number of named predictors.
Ignoring fit failures. A nonconverged or undefined fit has not supplied an ordinary comparable score. Define how such candidates are handled and report any exclusions.
Overstating the conclusion. Exhaustive optimization establishes the best score only within the specified family and for the specified criterion. It does not prove that the selected model is uniquely true or universally best.

Key takeaway: All-subsets search is a transparent finite optimization, but its guarantee is conditional on a clearly defined candidate family, a consistent criterion, and successful evaluation of every admissible model. Its cost grows exponentially with the number of independently selectable terms.

Check Your Understanding

Use these questions to check both the counting argument and the scope of the search guarantee.

How many models are in an unrestricted all-subsets search with 12 independently selectable predictors, including the predictor-free model?
If exactly four of 10 candidate terms must be selected, how many subsets are considered?
Why can a hierarchy constraint make the candidate count smaller than \(2^p\)? Give one example of a combination it excludes.
What does an exhaustive search guarantee when all candidate scores are valid and the criterion is minimized?
Why should a stepwise search not be described as finding the globally best subset unless an additional guarantee is available?