Why Random Search for Boosting?
A boosted-tree model can change substantially when its learning rate, tree depth, row subsampling fraction, or number of boosting iterations changes. A grid search evaluates combinations selected in advance, with specified levels for each control. Random search instead draws a fixed number of combinations from specified parameter ranges or distributions.
The distinction is about selecting hyperparameter combinations, not randomly selecting observations for model fitting. Row subsampling is itself one of the boosting controls: at each iteration, a specified fraction of training rows may be used to fit the next tree. That model-fitting step is separate from randomly drawing candidate values for a tuning experiment.
A random search is not automatically more effective than a grid. Its advantage is most plausible when some controls matter much more than others, or when the useful region occupies a small part of a large parameter space. A grid with many levels in every dimension can spend much of its budget varying relatively unimportant controls in lockstep. Random search can produce more distinct values for a high-impact control within the same number of fitted candidates.
Define the Search Before Drawing Candidates
Specify the ranges, allowable values, and sampling distributions before fitting models. For a regression-boosting task, one possible search space is:
| Control | Example search space | Sampling choice |
|---|---|---|
| Learning rate \(\eta\) | 0.01 to 0.20 | Log-uniform |
| Tree depth \(D\) | Integers 1 through 5 | Discrete uniform |
| Row subsampling fraction \(s\) | 0.50 to 0.90 | Uniform |
| Number of iterations \(M\) | 200, 300, ..., 1,000 | Discrete uniform |
A log-uniform learning-rate distribution gives equal probability to equal-width intervals on the logarithmic scale. It does not concentrate most candidates near the upper end of the numeric range. This can be useful when plausible learning rates differ by multiplicative factors. A uniform distribution on the ordinary scale would put equal probability on intervals such as 0.01 to 0.02 and 0.19 to 0.20; a log-uniform distribution instead gives equal probability to intervals with the same ratio of endpoints.
Tree depth and iteration count are discrete controls, so candidates must be valid integers or belong to the stated set. The chosen ranges should reflect the modeling problem and available computing budget. A random search cannot find a useful configuration outside the region it samples, and an unnecessarily wide range can devote many fits to implausible settings.
Hold the evaluation protocol constant across candidates. For example, use the same training and validation data, preprocessing, response definition, and metric for every fit. If the selection criterion is validation RMSE, select the candidate with the smallest validation RMSE; if it is a loss to minimize, lower is better. The final test set should not be used repeatedly to choose hyperparameters, because that turns it into part of the tuning process.
Drawing and Evaluating Candidates
One convenient way to generate a candidate is to draw independent uniform random numbers \(U_1,U_2,U_3,U_4\) on the interval from 0 inclusive to 1 exclusive, then transform them to the desired parameter scales. Independence here describes the candidate-generation procedure; it does not mean the controls have independent effects on model performance.
Here \(\lfloor x\rfloor\) is the greatest integer less than or equal to \(x\). Since \(U_2\) and \(U_4\) are below 1, these transformations produce depths from 1 to 5 and iteration counts from 200 to 1,000 in increments of 100. The subsampling fraction lies from 0.50 up to, but not including, 0.90. If the intended space includes the upper endpoint, define a discrete set of allowable values or handle the endpoint explicitly.
Worked Example: Transforming Random Draws Into One Candidate
A hypothetical search uses the four transformations above. One candidate has random draws \(U_1=0.25\), \(U_2=0.62\), \(U_3=0.75\), and \(U_4=0.44\). Determine its four hyperparameter values. Method: transform each draw using the rule for its parameter. This avoids treating a log-uniform learning rate as if it were uniform on the ordinary scale.
Learning rate. The log-uniform transformation gives \(\eta=\exp(\log(0.01)+0.25\{\log(0.20)-\log(0.01)\})\). Since \(0.20/0.01=20\), this is \(0.01\times20^{0.25}\). The fourth root of 20 is approximately 2.1147, so \(\eta\approx0.02115\).
Depth. \(D=1+\lfloor5(0.62)\rfloor=1+\lfloor3.10\rfloor=4\).
Subsampling. \(s=0.50+0.40(0.75)=0.50+0.30=0.80\).
Iterations. \(M=200+100\lfloor9(0.44)\rfloor=200+100\lfloor3.96\rfloor=500\).
The candidate is therefore \((\eta,D,s,M)\approx(0.02115,4,0.80,500)\). It satisfies all four stated ranges, including the integer requirements for depth and iteration count.
After candidates are drawn, fit each model under the same evaluation protocol and record the chosen validation metric. The sampling process does not determine which candidate is best; only the measured criterion does. Keep a table of candidate values and results so that selection is traceable.
Worked Selection and Search Efficiency
Worked Example: Selecting From a Four-Candidate Search
A hypothetical insurer models a continuous claim-cost outcome using a training sample and a fixed validation sample. Four random-search candidates produce the following validation RMSE values, in thousands of dollars. Select the candidate with the lowest validation RMSE and compare it with a reference model whose validation RMSE is 4.50. Method: rank candidates by the prespecified metric, then calculate the relative improvement over the reference. This avoids choosing a candidate because its training fit alone looks best.
| Candidate | \(\eta\) | \(D\) | \(s\) | \(M\) | Validation RMSE |
|---|---|---|---|---|---|
| A | 0.020 | 2 | 0.70 | 600 | 4.28 |
| B | 0.080 | 3 | 0.80 | 400 | 4.17 |
| C | 0.035 | 4 | 0.60 | 700 | 4.12 |
| D | 0.120 | 1 | 0.90 | 300 | 4.35 |
The four validation RMSE values are 4.28, 4.17, 4.12, and 4.35. Their minimum is 4.12, so candidate C is selected under the stated rule. The absolute reduction from the reference is \(4.50-4.12=0.38\) thousand dollars.
The relative reduction is \(0.38/4.50=0.08444\ldots\), or approximately 8.44% when rounded to two decimal places. Thus candidate C has the lowest validation RMSE among these four fits, with an 8.44% reduction from the reference metric. This comparison does not establish that the reduction will recur on new data; it is a validation result, not a guarantee.
Common mistake avoided: selecting candidate D because its learning rate is largest, or selecting any candidate from its training score alone. Neither rule matches the prespecified objective of minimizing validation RMSE.
Why a Fixed Budget Can Favor Random Search
Suppose the parameter space is sampled independently on each trial, and a fraction \(q\) of that space is considered promising. If each random draw has probability \(q\) of landing in that region, then the probability of missing it on one draw is \(1-q\). For \(B\) independent draws, the probability of missing it every time is \((1-q)^B\). Therefore the probability of at least one hit is:
This result assumes that the draws follow the stated sampling distribution and that the promising region has probability mass \(q\) under that distribution. The calculation concerns reaching the region at least once; it does not guarantee that the resulting model will be best or that the region has been identified precisely.
A grid with \(k\) levels for each of \(p\) controls evaluates \(k^p\) combinations if it uses the full Cartesian product. At a fixed budget, adding grid levels to every control can make the total number of fits grow rapidly. If only a few controls strongly affect performance, a random search can give those controls a range of values without requiring a dense grid along every other dimension.
Worked Example: Comparing Search Coverage Under a Fit Budget
A team can fit 40 candidate models. Under its chosen sampling distributions, assume that a promising region occupies 10% of the probability mass. Compare the random search’s chance of sampling that region with a grid containing five levels for each of four controls. Method: use the hit-probability formula for random search and count the full grid combinations. This avoids confusing “40 candidates total” with 40 levels per control.
Here \(q=0.10\) and \(B=40\). The probability of at least one hit is \(1-(1-0.10)^{40}=1-0.9^{40}\). Since \(0.9^{40}\approx0.01478\), the probability is approximately \(0.98522\), or 98.52% rounded to two decimal places.
The grid has \(5^4=625\) combinations: five learning-rate levels times five depths times five subsampling levels times five iteration levels. It therefore exceeds the 40-fit budget. A 40-fit random search is feasible within that budget, while this full grid is not.
The result is not proof that random search always wins. If the grid were deliberately designed around a known promising region, or the parameter space were small and all controls mattered similarly, a grid might be preferable. The calculation shows why random search can be an efficient broad exploration when the grid’s Cartesian product is too large for the available budget.
A Practical Random-Search Workflow
Choose the validation metric to minimize or maximize before comparing candidates. Record its scale and direction clearly.
Set ranges or allowable values for learning rate, depth, row subsampling, and iteration count. Choose distributions that reflect plausible values and the intended coverage.
Decide how many complete configurations can be fitted. Each configuration is one candidate, even though it contains several parameter values.
Apply the same training and validation protocol to each candidate. Keep a record of the parameter values and validation result.
Choose by the prespecified validation criterion, state the selected values and metric, and preserve the test set for final evaluation rather than repeated tuning.
The random-search budget should be large enough to explore the space meaningfully but not so large that the search becomes an unplanned collection of repeated validation comparisons. A random seed can make the generated candidate list reproducible, but reproducibility does not correct a poorly chosen search space or evaluation protocol.
Common Exam Traps
- Counting levels instead of candidate combinations. Forty candidates means 40 complete configurations. Forty levels for each of four controls would imply \(40^4=2{,}560{,}000\) combinations in a full grid.
- Using the wrong distribution. Sampling the learning rate uniformly from 0.01 to 0.20 is not the same as sampling it log-uniformly. State which scale is uniform before interpreting coverage.
- Confusing two kinds of randomness. Randomly selecting a candidate configuration is different from using row subsampling within a boosted model.
- Changing the evaluation rule across candidates. Candidate rankings are not comparable if different data partitions or metrics are used without a justified, consistent design.
- Claiming random search guarantees a good result. It samples according to its specified distributions. It can miss a promising region, especially with a small budget or an unsuitable search space.
Check Your Understanding
For each problem, identify the relevant search design or calculate the requested quantity.
- A search draws \(U=0.50\) to generate a log-uniform learning rate between 0.01 and 0.16. Using \(\eta=\exp(\log(0.01)+U\{\log(0.16)-\log(0.01)\})\), calculate the learning rate. (Answer: 0.0400)
- A depth draw uses \(D=1+\lfloor6U\rfloor\), where \(U=0.83\). What depth is selected? (Answer: 5)
- A team tests 30 independent random candidates. If 5% of the search distribution is promising, what is the probability of at least one hit? Give the probability to four decimals. (Answer: \(1-0.95^{30}=0.7854\))
- A full grid uses 4 learning-rate values, 3 depths, 5 subsampling fractions, and 6 iteration counts. How many candidate fits does it require, and does it fit a budget of 350? (Answer: \(4\times3\times5\times6=360\) fits; no, it exceeds the budget by 10.)
- A 25-candidate random search uses validation MAE, with lower values preferred. The best candidate has validation MAE 2.40 and a reference model has validation MAE 2.75. What is the absolute and relative reduction from the reference? (Answer: absolute reduction \(=0.35\); relative reduction \(=0.35/2.75=0.1273\), or 12.73%.)