Every year, thousands of school and college teams across India spend thirty-six sleepless hours at the Smart India Hackathon building working prototypes. Imagine one such team is building an app that predicts monsoon rainfall risk for a district, using a k-Nearest Neighbours (k-NN) classifier trained on years of India Meteorological Department (IMD) rainfall records. The model itself is simple. The hard part is a single number they must choose before training even begins: k, the number of nearest neighbours the model consults when it makes a prediction. Pick k too small and the model gets rattled by one freak rainy year in the training data. Pick k too large and it blurs together districts and decades that do not actually behave alike. Somewhere in between is a value of k that generalises best — and the only way to find out how well a given k actually performs is to retrain the whole model with that k and check its accuracy on data it has not seen. With a multi-decade district-level dataset, one such training-and-validation run takes real minutes, not milliseconds. The team has a demo in a few hours and a dozen other features left to build. They cannot afford to try every candidate value of k. This chapter is about the algorithm that lets them spend their limited trials wisely: Bayesian optimization.
Parameters, hyperparameters, and the cost of a trial
Before going further, it helps to be precise about two words that are easy to confuse. A parameter is a value a model learns automatically from data during training — the weights in a linear regression line, for instance. A hyperparameter is a value you, the programmer, must fix before training starts, because the training process itself does not learn it. In k-NN, k is a hyperparameter: nothing about "gradient descent" or "loss minimisation" can discover it, because k-NN does not even have a training phase in the usual sense — it just stores the data and consults it at prediction time. The only way to find out whether k = 7 or k = 11 generalises better is to actually set k to that value, run the model against a held-out validation set (data withheld from training so it fairly tests generalisation), and record the accuracy.
Call one such "set a hyperparameter value, retrain, validate, record the score" cycle a trial. For a tiny model and a tiny dataset, a trial might take a fraction of a second, and you could simply try everything. For the hackathon team's dataset, a trial realistically costs several minutes of laptop time. Multiply that by every hyperparameter combination you would like to test, and "just try everything" stops being a plan and starts being the reason your team misses the judging slot.
Grid search, and why it does not scale
The most direct hyperparameter search strategy is grid search: list every candidate value for each hyperparameter, and try every combination. Suppose the team also wants to tune the distance metric and the neighbour-weighting scheme for their k-NN model, alongside k:
k: 4 candidate values, say 3, 5, 7, 9metric: 3 candidate values — euclidean, manhattan, minkowskiweights: 2 candidate values — uniform, distance
Grid search tries every combination: 4 × 3 × 2 = 24 trials. That number is not additive, it is multiplicative — adding one more hyperparameter does not add a few trials, it multiplies the existing count by however many options that new hyperparameter has. This is often called the combinatorial explosion of grid search. It is exhaustive and guaranteed to find the best combination among the candidates you listed, but the cost grows brutally fast, and every one of those 24 trials costs the same several minutes as before — potentially two hours just to tune three hyperparameters.
A cheaper alternative is random search: instead of trying every combination, randomly sample a fixed number of them, say 8 out of the 24. This is often a genuinely good strategy, because in practice a few hyperparameters usually matter far more than the rest, and random sampling tends to cover the important ones reasonably well without wasting trials on combinations that were never going to matter. But random search still treats every past trial as throwaway information — it never uses what trial 3 revealed to make a smarter choice for trial 4. Bayesian optimization exists to fix exactly that.
The core idea: let each trial teach you where to look next
Here is the intuition, in the simplest form it can take. Suppose a friend hides a coin under one of ten tiles in a row, and tells you only "warmer" or "colder" after each guess. You would not guess tile 1, then tile 2, then tile 3 in order — you would use the warmer/colder feedback from your earlier guesses to decide where to try next, focusing on the region that seems promising while still occasionally checking an unexplored tile in case the "warm" region you found is only a local, not the true, hotspot. Bayesian optimization formalises exactly this behaviour for hyperparameter tuning. After every trial, it updates a running belief about how accuracy varies across the untested hyperparameter values, then uses that belief to pick the single most promising untested value to try next. The name "Bayesian" refers to this update-your-belief-after-new-evidence pattern, which is the same spirit as Bayesian probability — though, as we will see later, the actual arithmetic used here does not involve applying Bayes' theorem's conditional-probability formula directly.
Two ingredients make this work. First, a surrogate model: a cheap, fast stand-in that estimates what accuracy a hyperparameter value would probably produce, built purely from the trials run so far. Second, an acquisition function: a rule that scores every untried candidate using the surrogate's estimate, and picks the candidate with the highest score to try next. Real trials are expensive; evaluating the surrogate and the acquisition function is essentially free, since it is just arithmetic on numbers you already have — no retraining required.
Building a surrogate: the simplest belief that could possibly work
Real Bayesian optimization tools typically use a statistical model called a Gaussian Process as the surrogate, which is well beyond Class 9 mathematics. To learn the underlying logic without that machinery, we will build the simplest surrogate imaginable — one that, fittingly, borrows the very idea we are trying to tune: nearest-neighbour reasoning.
The rule: to estimate the accuracy of an untried candidate value, look at whichever already-tried value is closest to it, and use that tried value's actual measured accuracy as your estimate. If a candidate is exactly midway between two tried values, be optimistic and use the higher of the two accuracies — a small rule we will need later, and one that keeps the search leaning toward promising regions rather than being pessimistic about ties.
This estimate alone is not enough, though. A candidate right next to a tried point should be judged confidently — we have real evidence nearby. A candidate far from every tried point is much more uncertain — our nearest-neighbour guess there could easily be wrong. So the acquisition function adds a bonus for distance from what has been tried, called the uncertainty term, since being far from evidence genuinely does mean we are more uncertain what will happen there.
The acquisition function: Upper Confidence Bound
Put the two pieces together and you get one of the simplest and most widely used acquisition functions, the Upper Confidence Bound, or UCB:
UCB(candidate) = estimated_accuracy(candidate) + beta × distance_to_nearest_tried(candidate)beta (the Greek letter used for the exploration weight) is a small constant we choose ourselves. A larger beta makes the search more adventurous, favouring unexplored regions even when the nearby evidence looks mediocre. A smaller beta makes it greedier, favouring whatever is already known to work well. In the worked example below we use beta = 0.01. Every distance in that example is 2, 4 or 6, so the bonus adds 0.02 to 0.06, and two candidates' bonuses never differ by more than 0.04: enough to break a tie or a near-tie between estimates, never enough to overturn an estimate that is ahead by more than 0.04.
Worked example: tuning k for the monsoon-risk classifier
The hackathon team narrows candidate values of k to eight odd numbers, spaced two apart so no candidate ties with another for a neighbour vote: k ∈ {1, 3, 5, 7, 9, 11, 13, 15}. Grid search over just this one hyperparameter would cost 8 trials. Because each trial eats several minutes, the team sets a firm budget of 5 trials and lets Bayesian optimization choose which five.
To trace this by hand, we need to know what accuracy each k would actually produce if tried — information that exists in reality (you would learn it by really training and validating), but that the algorithm does not get to see in advance. It only learns one entry at a time, exactly when it "spends" a trial on that value. For this worked example, here is that hidden truth, matching a very ordinary k-NN bias–variance pattern — low accuracy at very small k because the model overreacts to noisy individual points, rising accuracy as k grows enough to average out that noise, then falling again once k grows so large the model blurs together districts that do not really behave alike:
k 1 3 5 7 9 11 13 15
accuracy 0.70 0.80 0.85 0.88 0.89 0.87 0.83 0.78Keep in mind: this table exists so we can check the algorithm's work. The algorithm sees none of it until it spends a trial.
Trials 1 and 2 — seeding the search. With zero trials run, there is no "nearest tried point" to measure distance from, so the surrogate has nothing to work with. Bayesian optimization implementations conventionally start with a small number of seed trials at fixed or randomly chosen points before the surrogate takes over. Here we seed at both edges of the range, k = 1 and k = 15, which gives the surrogate at least some information across the whole span.
- Trial 1: try
k = 1→ measured accuracy 0.70. - Trial 2: try
k = 15→ measured accuracy 0.78.
Trial 3 — the surrogate takes over. Tried so far: {1: 0.70, 15: 0.78}. For every untried candidate, find the nearest tried point, take its accuracy as the estimate, and add 0.01 × distance:
k=3: nearest=1 (dist 2) 0.70 + 0.01(2) = 0.72
k=5: nearest=1 (dist 4) 0.70 + 0.01(4) = 0.74
k=7: nearest=1 (dist 6) 0.70 + 0.01(6) = 0.76
k=9: nearest=15 (dist 6) 0.78 + 0.01(6) = 0.84 <- highest
k=11: nearest=15 (dist 4) 0.78 + 0.01(4) = 0.82
k=13: nearest=15 (dist 2) 0.78 + 0.01(2) = 0.80k = 9 wins, not because either seed's accuracy was outstanding, but because it sits roughly in the middle, far from both seeds, so its uncertainty bonus is large enough to edge out the safer, nearer candidates. Trial 3: try k = 9 → measured accuracy 0.89, the best score seen so far by a wide margin.
Trial 4. Tried now: {1: 0.70, 9: 0.89, 15: 0.78}.
k=3: nearest=1 (dist 2) 0.70 + 0.02 = 0.72
k=5: tie: 1 & 9 (dist 4 each) -> optimistic, use 9's 0.89
0.89 + 0.04 = 0.93 <- highest
k=7: nearest=9 (dist 2) 0.89 + 0.02 = 0.91
k=11: nearest=9 (dist 2) 0.89 + 0.02 = 0.91
k=13: nearest=15 (dist 2) 0.78 + 0.02 = 0.80k = 5 wins outright at 0.93 — it happens to sit exactly as far from the strong new point (k=9) as from the weak seed (k=1), and our optimistic tie-break rule credits it with the stronger neighbour's accuracy plus a healthy distance bonus. Trial 4: try k = 5 → measured accuracy 0.85.
Trial 5, the last trial in the budget. Tried now: {1: 0.70, 5: 0.85, 9: 0.89, 15: 0.78}.
k=3: tie: 1 & 5 (dist 2 each) -> use 5's 0.85
0.85 + 0.02 = 0.87
k=7: tie: 5 & 9 (dist 2 each) -> use 9's 0.89
0.89 + 0.02 = 0.91 <- highest so far
k=11: nearest=9 (dist 2) 0.89 + 0.02 = 0.91 (tie with k=7)
k=13: nearest=15 (dist 2) 0.78 + 0.02 = 0.80k = 7 and k = 11 land on the exact same score, 0.91. When the acquisition scores themselves tie, we need one more rule: scan candidates in ascending order and keep whichever was found first unless a later one is strictly greater. Since 0.91 is not strictly greater than 0.91, k = 7 keeps its lead. Trial 5: try k = 7 → measured accuracy 0.88.
The budget of 5 trials is now spent. Across all five, the best measured accuracy was 0.89 at k = 9 — which, checking the hidden table, is in fact the true best value among all eight candidates. Bayesian optimization found the global optimum after trying only 5 of the 8 candidates, skipping k = 3, k = 11, and k = 13 entirely.
Seeing the search unfold
The diagram below plots the hidden true accuracy curve (dashed — shown here only for teaching; the algorithm never sees it), the five points actually tried (solid blue), and the three candidates left untouched (hollow). The gold ring marks the best point the search found.
Simulating the search in Python
The simulation below uses only lists, loops, conditionals, and functions — no dictionaries, no comprehensions, no keyword-argument defaults. A few things worth pointing out before you read it: list.append(x) adds x to the end of a list; the check if k not in tried_k tests whether k is missing from that list; and round(x, 2) just rounds a decimal to 2 places so the printed output is tidy. candidates.index(k) finds the position of k inside the candidates list, which we then use to look up the matching accuracy.
candidates = [1, 3, 5, 7, 9, 11, 13, 15]
# true_accuracy[i] is what we would ONLY learn by actually training
# and validating a k-NN model with k = candidates[i]. In a real
# project we do not know this list in advance -- here we reveal one
# entry at a time, only when a trial is actually "run".
true_accuracy = [0.70, 0.80, 0.85, 0.88, 0.89, 0.87, 0.83, 0.78]
tried_k = [] # k values actually tried so far
tried_acc = [] # the accuracy measured for each, same order
def run_trial(k):
i = candidates.index(k)
acc = true_accuracy[i]
tried_k.append(k)
tried_acc.append(acc)
return acc
def ucb_score(k):
# Find the nearest already-tried k. If two tried points are
# equally near, stay optimistic: use the higher accuracy.
best_dist = 999
best_acc = 0
for i in range(len(tried_k)):
dist = abs(k - tried_k[i])
if dist < best_dist:
best_dist = dist
best_acc = tried_acc[i]
elif dist == best_dist and tried_acc[i] > best_acc:
best_acc = tried_acc[i]
beta = 0.01
return best_acc + beta * best_dist
# Trials 1-2: seed the search at both edges of the range.
run_trial(1)
run_trial(15)
# Trials 3-5: let the surrogate + UCB rule choose each time.
for trial_number in range(3, 6):
best_k = -1
best_score = -1
for k in candidates:
if k not in tried_k:
score = ucb_score(k)
if score > best_score:
best_score = score
best_k = k
acc = run_trial(best_k)
print("Trial", trial_number, ": chose k =", best_k,
" UCB score =", round(best_score, 2),
" measured accuracy =", acc)
best_index = 0
for i in range(1, len(tried_acc)):
if tried_acc[i] > tried_acc[best_index]:
best_index = i
print("Best k found:", tried_k[best_index],
"with accuracy", tried_acc[best_index])
Tracing it by hand confirms the output: Trial 3 prints k = 9, score 0.84, accuracy 0.89; Trial 4 prints k = 5, score 0.93, accuracy 0.85; Trial 5 prints k = 7, score 0.91, accuracy 0.88; and the final line reports Best k found: 9 with accuracy 0.89 — exactly matching the walkthrough above, because the code's candidate loop runs in the same ascending order we used for the tie-break by hand.
What Bayesian optimization does and does not promise
Common misconception: "Bayesian optimization is guaranteed to find the best hyperparameter value." This is false, and worth correcting directly. It is a search strategy that uses past trials to make each new choice more informed than a blind guess — nothing more. In our worked example it happened to land on the true best candidate, k = 9, using only 5 of 8 trials. That was a genuine result of the method being smarter than blind search, not a guarantee baked into the algorithm. Three candidates, k = 3, k = 11, and k = 13, were never tried at all within the 5-trial budget; nothing in the algorithm proves in advance that none of them could have beaten 0.89 (in this constructed example, checking the hidden table shows the best of the three, k = 11 at 0.87, in fact would not have beaten 0.89 — but the algorithm has no way to know that without spending a trial to check). If the accuracy landscape had a second, taller peak hiding far from both seed points, a small trial budget could easily miss it. More trials generally shrink this risk, since more of the candidate space gets examined, but "generally shrinks the risk" is very different from "guarantees the optimum" — the second claim is simply not true of this or any fixed-budget search method.
Common misconception: "Bayesian optimization tunes the model, the way training tunes the weights." Also false, and worth separating clearly. Training a k-NN, or any model, only stores or learns its parameters for one fixed hyperparameter setting. Bayesian optimization operates one level above that: it is the outer loop deciding which hyperparameter setting to hand to training next, and it only ever learns from the final validation score of each completed trial — it has no visibility into what happens inside a single training run.
Beyond the toy version: what real tools do differently
Our nearest-tried-neighbour surrogate was chosen deliberately to be hand-traceable with Class 9 arithmetic. Production tools go further in two ways. First, the surrogate is usually a Gaussian Process regression model, which produces a smooth estimate and a genuine statistical uncertainty band across the entire candidate space at once, rather than a blunt "copy the nearest tried point" rule. Second, real tools often use an acquisition function called Expected Improvement (EI) instead of, or alongside, UCB — EI directly estimates how much better than the current best a candidate is likely to be, weighted by the probability of that happening. Libraries such as scikit-optimize and Optuna implement these ideas in ready-to-use Python code, and Google has published details of an internal service called Vizier that runs Bayesian optimization at large scale for tuning its own machine learning systems. The reasoning your hand-traced walkthrough just went through — estimate, add an uncertainty bonus, pick the best score, learn from the result — is the same reasoning running underneath all of them, just with sharper statistical tools doing the estimating.
Summary: the method in five sentences
Bayesian optimization tunes a hyperparameter when every trial is expensive, by letting each finished trial decide where to look next. It keeps a surrogate model: a cheap estimate of how well each untried value would do, built only from the trials run so far. An acquisition function such as the Upper Confidence Bound scores every candidate as its estimated accuracy plus beta times its distance from the nearest tried value, which balances exploiting values that already look good against exploring values the estimate knows least about. The highest-scoring candidate is tried next, its real result updates the surrogate, and the loop repeats until the trial budget runs out. None of this guarantees the best possible value: it is a disciplined way to spend a limited number of trials, and a poor surrogate or a badly chosen beta can still point the search the wrong way.
Check your understanding
- A teammate says, "k in k-NN gets learned automatically while the model trains, just like the weights in linear regression." Explain what is wrong with this statement, using the vocabulary of parameters versus hyperparameters.
- Suppose only two trials have been run so far:
k = 3with measured accuracy 0.82, andk = 13with measured accuracy 0.79. Using the same rule as the worked example (nearest-tried-point estimate + 0.01 × distance, optimistic tie-break), compute the UCB score for candidatesk = 5,k = 7,k = 9, andk = 11, and state which one would be chosen next.
Answer: k=5 -> nearest is 3 (dist 2): 0.82+0.02=0.84. k=7 -> nearest is 3 (dist 4): 0.82+0.04=0.86. k=9 -> nearest is 13 (dist 4): 0.79+0.04=0.83. k=11 -> nearest is 13 (dist 2): 0.79+0.02=0.81. Highest score is k=7 at 0.86, so k=7 is chosen next. - The chapter's grid search example tunes
k(4 options),metric(3 options), andweights(2 options), giving 24 trials. If a teammate now also wants to try both values of the power parameterp(1 and 2) for the minkowski metric, how many total grid search trials are needed?
Answer: 24 × 2 = 48 trials. - Grid search with a small number of cheap trials is often perfectly fine, but grid search over expensive trials is not. Explain, in your own words, exactly what "expensive" means here and why it changes the calculation.
- True or false, with a one-line justification: "Because Bayesian optimization found the true best k in the worked example using only 5 of 8 trials, we have proven it will always find the best hyperparameter value within any 5-trial budget."
Answer: False. That single example demonstrates the method can work well; it is not a proof about every possible accuracy landscape or every budget, since an untried region could always hide a better value that the budget ran out before reaching.