Grid Search

Grid Search for Calibrating and Tuning Health Economic Models

Grid search fixes a short list of candidate values for each unknown parameter, runs the model once for every combination of those values and keeps the combination with the best score. In health economics the method is used in calibrating disease models, where natural history parameters that cannot be observed directly are chosen so that modelled incidence or mortality matches registry or trial data. Its appeal is transparency, since every run is recorded and the fit across the searched region can be inspected. Its weakness is cost, because the number of runs is the product of the number of values tried for each parameter. Grid search is a form of numerical optimisation that uses no gradients and learns nothing from earlier runs, which makes it a simple reference point for judging directed methods.

Building the grid and the score it minimises

Each parameter is given a plausible range and a number of candidate values inside it, usually evenly spaced. Kong and colleagues, writing about disease simulation models, describe grid search as dividing each parameter between its minimum and maximum values into regular grids and comparing the results of all possible combinations with the calibration targets.

$$v_{i,j} = a_i + (j-1)\,h_i, \qquad h_i = \frac{b_i - a_i}{m_i - 1}, \qquad j = 1, \dots, m_i$$

where $a_i$ and $b_i$ are the lower and upper bounds for parameter $i$, $m_i$ is its number of candidate values, $h_i$ is the step between neighbouring values and $v_{i,j}$ is the $j$th candidate value.

The grid is the set of every combination of candidate values, and the search returns the point with the lowest score. A score that should be maximised, such as a likelihood, is handled by minimising its negative.

$$\hat{\theta} = \arg\min_{\theta \in G} J(\theta), \qquad G = V_1 \times V_2 \times \cdots \times V_k, \qquad N = \prod_{i=1}^{k} m_i$$

where $\theta$ holds one value for each of the $k$ parameters, $V_i$ is the set of candidate values for parameter $i$, $G$ is the grid, $J(\theta)$ is the score of the run at $\theta$, $\hat{\theta}$ is the best grid point and $N$ is the number of runs the full grid needs. Bergstra and Bengio note that this product makes grid search suffer from the curse of dimensionality, because the number of joint values grows exponentially with the number of parameters.

In calibration the score is a goodness-of-fit measure. Stout and colleagues describe likelihood measures and distances between model output and target such as the sum of squared errors, and note that an overall measure may be a raw sum or a weighted average across targets.

$$J(\theta) = \sum_{t=1}^{T} w_t \left[ g_t(\theta) - y_t \right]^2$$

where $T$ is the number of calibration targets, $y_t$ is the observed value of target $t$, $g_t(\theta)$ is the model's prediction of that target and $w_t$ is its weight.

Where grid search is used in health economic work

Grids appear in health economic analysis in three ways. Calibration and model tuning treat the grid as a search for one best point, while sensitivity and threshold analyses keep the whole grid as a map of results.

Calibrating disease natural history

In their review of calibration in cancer simulation models, Stout and colleagues found search algorithms generally not well described. Where they were specified, the formal ones included grid search and random sampling alongside directed methods. In a 2024 study of Bayesian optimisation for cost-effectiveness models, Gómez-Guillén and colleagues list grid search among general-purpose methods in current use, adequate for models of low to moderate complexity but not for more complex ones. Grid search is one way to carry out the search step of the wider calibration process.

Grids also turn up inside larger calibrations for small auxiliary fits. In a Bayesian calibration of a colorectal cancer microsimulation model, Rutter and colleagues used a grid search to choose the mean and standard deviation of a truncated Normal age distribution that came closest to the reported values for each study population.

Tuning prediction models

Prediction models used in health economics, such as models of high-cost patients, have settings that are chosen rather than estimated. In machine learning, Bergstra and Bengio report that grid search and manual search are the most widely used strategies for choosing these hyperparameters, with each candidate scored on held-out data by cross-validation. Varma and Simon, for instance, scored a support vector machine on a grid in which the trade-off parameter took values between $C = 2^{-5}$ and $C = 2^{15}$. They showed that the lowest cross-validated error found in such a search is a biased estimate of the true error, and that a nested procedure, with tuning repeated inside each outer fold, gives an almost unbiased estimate.

Grids that map a decision rather than optimise

A two-way sensitivity analysis runs the model over a lattice of values for two parameters, and a threshold analysis looks for the values at which the preferred option changes. The arithmetic is that of a grid search, but the output kept is the whole surface rather than one best point. Latin hypercube sampling instead draws a stratified random sample across the ranges.

Resolution, range and the cost of each added parameter

A grid can locate the optimum no more finely than its step. Along each axis every value in the range lies within half a step of a candidate, but when parameters interact the best grid point need not be the candidate nearest the true optimum. A best point on the edge of the grid suggests that the range was too narrow. Rates, small probabilities and many hyperparameters act on a multiplicative scale, so their candidates are often spaced evenly on a log scale.

The run count is the main constraint. Kong and colleagues give the example of a model with 20 unobservable parameters, where testing only 10 values of each would need $N = 10^{20}$ parameter sets, and they judged simulated annealing and a genetic algorithm faster than grid search because grid search time multiplies with every added parameter. Their lung cancer model needed 24 minutes to simulate 500,000 life histories, so a grid of 10 values on each of three parameters would take 1,000 runs, or 24,000 minutes (400 hours) on one such computer.

When only a few parameters affect the score, a grid wastes runs. In the nine-trial illustration of Bergstra and Bengio, a 3 by 3 grid tests the important parameter in only three distinct places, while nine random trials test nine. They still credit grids with simple implementation and trivial parallelism, and call grid search reliable in one or two dimensions.

In a stochastic microsimulation each score carries Monte Carlo error, so neighbouring grid points can swap rank by chance. Using common random numbers across grid points makes the comparison less noisy.

Worked example calibrating a two-parameter cohort model

All numbers in this example are illustrative. A cohort model of an untreated chronic disease has two parameters that no study measures directly, the annual probability $p$ of disease onset and the probability $f$ that a person with the disease dies of it within the 10-year horizon. Registry data give two targets, a 10-year cumulative incidence of 25.0 per 100 people and 5.0 disease deaths per 100 people.

The model's cumulative incidence per 100 people is $I(p) = 100\,[1 - (1 - p)^{10}]$ and its disease deaths per 100 people are $D = I(p) \times f$. The score is the unweighted sum of squared deviations.

$$J(p, f) = \left[ I(p) - 25 \right]^2 + \left[ D(p, f) - 5 \right]^2$$

where $I(p)$ is modelled cumulative incidence, $D(p, f)$ is modelled disease deaths, and 25 and 5 are the registry targets, each per 100 people.

1. Set the first grid. The candidates are $p$ in {0.02, 0.03, 0.04} and $f$ in {0.15, 0.20, 0.25}, so the grid needs 3 × 3 = 9 runs.

2. Run the model at each point. When $p$ is 0.03 the term $(1 - p)^{10}$ is 0.7374, so incidence is 100 × (1 − 0.7374) = 26.26 per 100. With $f$ set at 0.20, disease deaths are 26.26 × 0.20 = 5.25 per 100.

3. Score every point. For (0.03, 0.20) the deviations are 1.26 and 0.25, so the score is 1.5876 + 0.0625 = 1.65, using the rounded outputs shown.

4. Read the result. The best grid point is $p$ = 0.03 and $f$ = 0.20. The point (0.04, 0.15) matches the death target almost exactly but overshoots incidence by 8.52 and scores 72.59. The exact solution sets $(1 - p)^{10}$ to 0.75, so $p = 1 - 0.75^{0.1}$, which is 0.0284, and $f$ = 5 / 25 = 0.20, so the true $p$ lies between the first grid's candidates.

5. Refine around the best point. A second grid with $p$ in {0.026, 0.028, 0.030, 0.032} and $f$ in {0.19, 0.20, 0.21} needs 4 × 3 = 12 runs. Its best point is (0.028, 0.20), where incidence is 24.72 and deaths are 4.94, so the score is 0.0784 + 0.0036 = 0.08. The runner-up, (0.028, 0.21), scores 0.11, so the targets separate these candidates only weakly.

6. Carry the result into the evaluation. An illustrative treatment halves case fatality. Disease deaths averted per 1,000 people are 1,000 × ($I$ / 100) × $f$ × 0.5. The first grid's best point gives 10 × 26.26 × 0.20 × 0.5 = 26.3, the second grid's gives 10 × 24.72 × 0.20 × 0.5 = 24.7 and the exact solution gives 10 × 25.0 × 0.20 × 0.5 = 25.0. The coarse grid overstates the benefit by about 5%, an error that would carry into the QALY gain and the ICER. The two passes used 9 + 12 = 21 runs.

What the best grid point can and cannot support

Grid search returns one parameter set, the best of those tried, and says nothing on its own about how certain that set is. Rutter and colleagues point out that calibration methods based on a grid search for the best fit do not provide interval estimates, unlike the Bayesian calibration they proposed. A cost-effectiveness analysis that carries only the best grid point forward leaves calibration uncertainty out of the probabilistic sensitivity analysis.

The full score table still helps, since near ties like the 0.08 and 0.11 in the worked example warn that the targets may not pin the parameters down. Stout and colleagues proposed a calibration reporting checklist covering targets, goodness-of-fit metrics, search algorithms, acceptance criteria and stopping rules, and note that a stopping rule may rest on the extent of the parameter space searched. For a grid that means stating the ranges, the step for each parameter, the number of runs and the scores of the leading points.

Grid search beside random, directed and Bayesian search

The alternatives differ in how they choose the next run. Random search draws points independently over the same ranges, so trials can be added or dropped during a search, which Bergstra and Bengio note is not possible for a grid. Directed methods such as gradient descent and the Nelder-Mead method use earlier results to move towards better fit, and Bayesian optimisation fits a surrogate to all previous runs to choose the next one.

A coarse grid can also supply starting points for a directed method, which then refines the best few, so the grid covers the region while most runs go where fit is good.

Common misreadings of grid search results

Most errors come from treating the best grid point as more than the best of a fixed list. Three recur in calibration and tuning work.

1. Reading the best point as the optimum. Exhaustive search guarantees only the best point on the grid, and the true optimum can lie between candidates, as it did for $p$ in the worked example.
2. Reporting the minimum cross-validated error from a tuning grid as expected performance. Varma and Simon showed this is optimistic and that nested cross-validation corrects it.
3. Passing one best-fitting set to the economic model as if it were known. Near ties and calibration uncertainty belong in the sensitivity analysis.

Sources

• Bergstra J, Bengio Y. Random search for hyper-parameter optimization. Journal of Machine Learning Research. 2012;13:281-305. https://www.jmlr.org/papers/volume13/bergstra12a/bergstra12a.pdf
• Gómez-Guillén D, Díaz M, Arcos JL, Cerquides J. Bayesian optimization with additive kernels for a stepwise calibration of simulation models for cost-effectiveness analysis. International Journal of Computational Intelligence Systems. 2024;17:249. https://doi.org/10.1007/s44196-024-00646-x
• Kong CY, McMahon PM, Gazelle GS. Calibration of disease simulation model using an engineering approach. Value in Health. 2009;12(4):521-529. https://doi.org/10.1111/j.1524-4733.2008.00484.x
• Rutter CM, Miglioretti DL, Savarino JE. Bayesian calibration of microsimulation models. Journal of the American Statistical Association. 2009;104(488):1338-1350. https://doi.org/10.1198/jasa.2009.ap07466
• Stout NK, Knudsen AB, Kong CY, McMahon PM, Gazelle GS. Calibration methods used in cancer simulation models and suggested reporting guidelines. PharmacoEconomics. 2009;27(7):533-545. https://doi.org/10.2165/11314830-000000000-00000
• Varma S, Simon R. Bias in error estimation when using cross-validation for model selection. BMC Bioinformatics. 2006;7:91. https://doi.org/10.1186/1471-2105-7-91