The curve that matters cannot be evaluated

Suppose an operating level x controls a random outcome Y. Repeating the experiment at that level would reveal a distribution H(y|x), and its mean would be M(x). The decision problem is to find the level θ at which M is largest. The difficulty is not merely that the maximum is unknown. The entire mean curve is unavailable. At any chosen x the investigator receives only a random response, not M(x), not its derivative and not a global fitted model.

Kiefer and Wolfowitz begin where Robbins and Monro had stopped. Robbins–Monro used a noisy response to solve the equation M(x)=α. The 1952 paper asks for the maximum of M itself. If the derivative were observable, the task could again be written as a root problem: seek M′(θ)=0. But the authors explicitly avoid assuming that a derivative exists. Their construction manufactures a direction from values observed on the two sides of a current guess.

The response curve is assumed to rise before θ and fall after θ. This single-peaked orientation is the source of identification. A higher mean response on the right means the centre should move right; a higher mean response on the left means it should move left. Individual response pairs may reverse that comparison. The guarantee comes from their conditional expectation and from schedules that prevent those random reversals from dominating forever.

The statistical formulation matters. Calling M a “regression function” does not mean the authors first fit a contemporary regression model. It means that M(x) is the conditional mean of the response distribution at level x. The design is sequential: today’s pair of experimental levels depends on yesterday’s observations. The resulting data are therefore products of an adaptive policy, not a fixed grid sampled in advance.

The primary also imposes a uniform bound S on the conditional response variance. This is not an incidental convenience. Dividing a response difference by a small cₙ amplifies noise. A variance bound allows the proof to show that the squared random contribution is controlled by the summable series ∑aₙ²/cₙ². Later work replaces or refines such assumptions, but the 1952 claim rests on its own stated restrictions.

A left experiment and a right experiment make a surrogate slope

At iteration n, the procedure holds a current centre zₙ and a positive probing distance cₙ. It conducts one experiment at zₙ−cₙ and another at zₙ+cₙ. Let y₂ₙ₋₁ denote the response on the left and y₂ₙ the response on the right. Their difference says which side looked better on this pair. Dividing by cₙ scales the comparison by the distance used to produce it.

The original denominator is cₙ, not 2cₙ. A modern centred finite-difference formula usually divides by 2cₙ. That factor of two can be absorbed into aₙ, so it does not change the conceptual method, but historical fidelity requires reproducing the article’s recursion as printed. Quietly rewriting the formula would make later numerical comparisons harder to audit.

Conditional on zₙ, the expected numerator is M(zₙ+cₙ)−M(zₙ−cₙ). If zₙ is well to the left of θ and both probes remain on the increasing side, the expected difference is positive. The update then moves right. If zₙ is to the right, the expected difference is negative and the update moves left. When the probes straddle θ, the signal becomes small, as it should near a maximum.

This expected finite difference is a direction, not a derivative claim. The paper says that M can be discontinuous. Its regularity assumptions are written directly in terms of function differences. A derivative provides intuition, but the theorem is deliberately constructed without making differentiability the gatekeeper.

Paired placement is the intellectual move. With only a response at zₙ, a high value does not say whether moving left or right would improve the mean. The neighbouring pair creates a local comparison. This is an early, exceptionally clear example of experimental design and optimisation being the same operation: the data are collected in the shape required by the update.

The probe must shrink while movement remains possible

Kiefer–Wolfowitz has two schedules because it faces two approximations. The gain aₙ determines how much the estimated direction changes zₙ. The probe cₙ determines the scale at which left and right are compared. Taking cₙ small makes the expected finite difference more local. Yet division by cₙ magnifies the response noise. The method must reduce both without letting one defeat the other.

The first requirement, cₙ→0, says that comparisons become local. A fixed probe would keep asking about a wide chord around zₙ. Even if zₙ approached θ, the update would still be influenced by values a fixed distance away. The vanishing probe removes that persistent smoothing scale.

The second requirement, ∑aₙ=∞, preserves reach. If total movement were finite, an unfortunate starting point could remain beyond the distance the algorithm can ever cover. Shrinking gains alone are not enough; their accumulated capacity must remain unbounded.

The third requirement, ∑aₙcₙ<∞, controls the finite-difference approximation error under the article’s regularity structure. It prevents small directional distortions associated with the probe width from accumulating without limit. The fourth, ∑aₙ²/cₙ²<∞, controls amplified response noise in the squared-error calculation.

The paper’s example is aₙ=n⁻¹ and cₙ=n⁻¹ᐟ³. Then aₙcₙ=n⁻⁴ᐟ³, whose series converges. Also aₙ²/cₙ²=n⁻⁴ᐟ³, so the squared noise series converges. Meanwhile the harmonic series ∑aₙ diverges and cₙ vanishes. One exponent choice satisfies all four duties.

These asymptotic conditions do not pick the best constants for one hundred experiments. Multiplying aₙ by a large constant preserves all four series properties but can make early steps violent. Multiplying it by a tiny constant may leave severe finite-run bias. Likewise, a large coefficient on cₙ gives a stable but nonlocal chord; a small one produces a volatile difference. The theorem classifies infinite sequences, not project deadlines.

The paper avoids derivatives but still requires usable geometry

The authors discuss the “spirit” of their conditions in unusually practical terms. If a differentiable M had a derivative, they would not want that derivative too large near θ, too small away from θ, or prone to extremely steep regions that could throw the process far from the maximum. They then encode those concerns without requiring differentiability.

Condition 1 gives local Lipschitz control near θ: sufficiently close points around the maximum cannot have mean responses differing faster than a constant times their separation. This bounds the local finite-difference term and prevents pathological steepness near the target.

Condition 2 says that sufficiently nearby experimental levels have a bounded mean-response difference. It is a broader increment bound. The paper explicitly notes that M may be discontinuous, so this condition is not a disguised assertion of global smoothness.

Condition 3 supplies separation away from θ. For every positive distance δ, centres at least δ away must have a two-sided mean difference, over sufficiently small probes, whose magnitude per unit probe is bounded below by a positive π(δ). This prevents the curve from becoming arbitrarily flat far from the maximum. Without it, the expected direction might be correctly signed yet too weak to overcome shrinking gains.

The distinction between derivative-free and assumption-free is essential. An algorithm can avoid measuring derivatives while its proof relies on regularity that derivative language would make intuitive. “Black box” describes the observation interface, not the absence of structure in the mean response.

The paper also anticipates bounded experimental domains. In practice one may know an interval [C₁,C₂] containing θ. If a proposed probe zₙ±cₙ falls outside the interval, the authors describe moving zₙ so that the offending probe lies at the relevant boundary and then proceeding. They state that it is sufficient for their conditions to hold on the known interval. This is a specific boundary device in the source, not a licence to assume every modern projection rule inherits the same proof.

Squared distance becomes a ledger for drift and noise

The proof sets bₙ=E(zₙ−θ)². Squaring the recursion produces three kinds of term: the previous squared error, a cross term involving the signed response difference, and a squared response-difference term multiplied by aₙ²/cₙ². Conditional expectations separate what the mean curve contributes from what random response noise contributes.

The authors decompose the conditional cross term into positive and negative parts. Because M rises before θ and falls after θ, the expected finite-difference direction has the restoring sign. Away from θ, Condition 3 supplies a positive lower bound on directional strength. Near θ, Condition 1 bounds the contribution so it cannot create uncontrolled growth.

The squared response difference is bounded using the response-variance assumption and a bound on nearby mean differences. Its cumulative effect is then controlled by ∑aₙ²/cₙ². The local approximation contribution is linked to ∑aₙcₙ. These are not arbitrary technical decorations: they are precisely the budgets that make the second-moment ledger finite.

A central intermediate result is that a weighted series of directional contributions converges even though ∑aₙ diverges. Therefore the direction multiplied by distance cannot stay bounded away from zero forever. The proof selects a subsequence on which an expected finite-difference strength times |zₙ−θ| tends to zero, then uses the separation condition to show that this subsequence converges in probability to θ.

The final step turns subsequence control into full-sequence control. Starting sufficiently late and sufficiently close, the remaining positive series budgets are made small. Chebyshev’s inequality bounds the chance that later iterates escape a chosen neighbourhood. Combined with the probability that the selected late iterate is already close, this proves zₙ→θ in probability.

“Converges stochastically” is the paper’s phrase for convergence in probability. It does not assert that almost every infinite sample path converges, and it does not present an asymptotic distribution or a convergence rate. Those stronger or more detailed results were developed in subsequent stochastic-approximation theory.

Every iteration is a small trial design

The method consumes two response observations per update. A budget of N responses therefore permits about N/2 centre moves before replication. This denominator matters when comparing Kiefer–Wolfowitz with a method that uses one response per update or with a batch design that estimates a fuller response curve. Counting iterations alone gives a misleading efficiency comparison.

The two responses should be paired in time and context wherever the scientific setting permits. If the left experiment is run in the morning and the right experiment after a regime change, their difference mixes the local mean contrast with temporal drift. Randomising left/right order, blocking on shared conditions or using common random numbers in simulation can reduce confounding, but those design choices require their own analysis. They are not stated features of the original theorem.

Independence and response distributions need explicit operational definitions. The article assigns the two observations their respective conditional distributions at zₙ−cₙ and zₙ+cₙ. A live system may produce autocorrelation, carry-over or interference between probes. The finite-difference numerator then has a different variance: and potentially a different expectation: from the idealised paired experiment.

Units again provide a useful audit. The response difference has outcome units; division by cₙ gives outcome per level; multiplication by aₙ must return level units. A gain coefficient therefore embodies an inverse-curvature scale. Rescaling the outcome or x-axis without updating both schedules changes the effective algorithm even when the displayed exponents remain the same.

Stopping is one of the further problems named by Kiefer and Wolfowitz themselves. A small movement |zₙ₊₁−zₙ| is not a reliable stopping certificate because a small aₙ forces small movements everywhere. A practical stopping rule should combine the estimated location, recent paired contrasts, their uncertainty, remaining gain, sensitivity to cₙ and the cost of an incorrect operating point.

The paper also names optimal choices of {aₙ} and {cₙ} as an open problem. That sentence is an important guard against retrospective inflation. The authors prove consistency for a class of schedules and give one example. They do not claim their example is universally efficient. Modern tuning rules answer a different, later question about finite-sample or asymptotic loss.

Zeroth-order optimisation is a descendant, not a synonym

Modern literature often calls this a zeroth-order method because it uses function values rather than derivatives. The label is useful, but it covers a much wider family: deterministic direct search, random-direction estimators, bandit feedback, smoothing-based gradients and high-dimensional nonconvex algorithms. Kiefer–Wolfowitz is a specific stochastic, paired, one-dimensional ancestor within that landscape.

Blum extended stochastic approximation to multiple dimensions in 1954. Coordinatewise finite differences in d dimensions may require two responses per coordinate. Spall’s simultaneous perturbation method later formed a multivariate direction from two globally perturbed evaluations, reducing the number of measurements per iteration. Those developments address dimensional cost that the 1952 five-page article does not analyse.

Rate theory and iterate averaging likewise belong to the later lineage. Consistency says the estimation error vanishes in a probability sense; it does not price how many experiments are needed to reach a tolerance. Bias, response variance, local curvature, dimension and schedule constants determine that price. A companion should celebrate the architecture without presenting every later guarantee as if it appeared at birth.

The durable idea is the conversion of values into a direction. When derivatives are unavailable but controlled experiments are possible, place observations around the current point, compare them, move in the expected better direction and narrow both movement and spatial resolution according to compatible schedules. That design pattern now appears in simulation optimisation, adaptive control, experiment-driven calibration and black-box machine learning.

A good endpoint can hide a bad experimental mechanism

A finite run should be audited at the level of its generated evidence, not only by its last centre. A transcription error that divides by 2cₙ instead of cₙ may still reach the peak after the gain constant compensates. A left/right label swap may accidentally look successful on a symmetric test function when the starting point or seed is favourable. Exact replay therefore checks each row: the stored centre, probe, responses, direction, gain and next centre must satisfy the declared historical recursion.

Several deliberately different objectives are needed before treating implementation behaviour as understood. A symmetric parabola checks arithmetic and orientation. An asymmetric single peak reveals whether wide probes introduce systematic finite-horizon displacement. A flat-topped response exposes weak identification near the optimum. A steep boundary maximum tests feasibility logic. None replaces the theorem assumptions, but each is a diagnostic instrument aimed at a distinct engineering failure.

Repeated-path summaries should be reported against response cost. For each schedule, simulate or repeat the experiment over many independent seeds, then show the distribution of final location error, the frequency of boundary interventions and the worst transient excursion. Compare designs after equal numbers of responses, not equal numbers of updates, because replication changes the cost of a step. Predeclare the seeds or randomness protocol when the evidence supports a consequential decision.

Stability across neighbouring schedule constants is more informative than one tuned demonstration. If a small change in A or C reverses performance, the operating point is not robustly established. A sensitivity grid can separate three phenomena: failure to travel far enough, excessive response-noise amplification and persistent finite-difference bias. Those categories correspond directly to reach, variance and probe-width mechanisms in the proof.

The maximiser’s practical value also needs its own loss scale. Being 0.1 units from θ may be negligible on a broad response curve and costly on a sharp one. Conversely, a location estimate can wander while M(zₙ) remains nearly optimal on a plateau. The original theorem targets location convergence. An applied report should state whether the business or scientific loss depends on location error, response regret, safety excursions or experimental cost, then evaluate the procedure on that declared quantity.

Place in the canon: from noisy equations to noisy optimisation

Paper 0031 introduced Robbins and Monro’s method for locating the root of an unknown mean response. Paper 0032 performs the decisive transformation from root-finding to optimisation when the derivative is unavailable. Two function-value observations synthesize the missing directional signal. The pair makes an implicit equation observable without ever fitting the full curve.

This is the canon’s first direct bridge from statistical experimentation to black-box optimisation. Earlier papers asked how to update belief, choose under risk or propagate probability. Kiefer–Wolfowitz asks how an agent can change the world twice, compare the consequences and use the comparison to select its next experiment. Agency appears not as an abstract policy but as a sequence of controlled interventions whose geometry creates information.

The next layers of the canon will enlarge this idea: multidimensional approximation, generalisation, optimisation and learning systems. The historical boundary remains useful throughout. A modern algorithm may inherit paired perturbations and shrinking gains while adding projections, vector geometry, adaptive moments or neural objectives. Naming those additions preserves both the originality of 1952 and the labour of later theory.

Executable paired-probe laboratory

The laboratory maximises M(x)=10−(x−2.2)² using the historical scaling of the Kiefer–Wolfowitz update. A seeded generator adds bounded zero-mean response noise. Four profiles vary noise, probe width and replication. The exact audit checks every recorded recursion, deterministic replay and the exponent conditions for aₙ=A/(n+8) and cₙ=C/(n+8)¹ᐟ³. The displayed endpoint is a finite-path observation, never a proof of the theorem.

Memory studio