VIEW THIS AS

Auto mode follows the Route Engine until you choose a viewpoint.

YOU ARE HERE

ROUTE CHECK

CONNECTED TO

WHAT NEXT

Use the canonical route for this room, or HELP if you are unsure.

The Gold Standard of Stochastic Approximation

Three secondary students review open books and notes together in a classroom.

Stochastic approximation is a family of iterative methods for finding a target when the information used to move toward it is noisy. Instead of requiring an exact function value or gradient at every step, the method makes a measured correction from a random observation and adjusts the size of future corrections. Its gold standard is a stable update whose target, noise assumptions, step sizes and final checks are explicit.

The central difficulty is balancing movement with averaging. Large updates respond quickly but can amplify noise or overshoot. Small updates reduce fluctuations but can move too slowly, freeze before reaching the target or fail to follow a target that changes. A smooth-looking trajectory is therefore not enough: it may indicate successful learning, excessive damping or convergence toward the wrong answer.

This guide develops the mechanism through original calculations: a noisy root at three, the running sample mean, a constant-step noise floor, instability from a steep response, biased feedback, quantile estimation and tracking. It also explains how the subject connects to stochastic gradient descent without treating every noisy update as an optimization algorithm with the same guarantees.

The Gold Standard master provides the wider collection. The Education parent asks whether understanding transfers when assumptions change, while the How X Works hub supplies supporting mechanisms. For the broader decision setting, read Simulation Optimization. Here the focus is how repeated noisy corrections can approach a mathematical target and how to recognize when they cannot.

CHAPTER 1 OF 14 · Define the target and update

1. Identify the equation behind the update

Back to contents

Start with a root-finding problem: find x* such that h(x*) = 0. You cannot evaluate h(x) exactly, but at a chosen x you can obtain an observation H(x,ξ), where ξ represents randomness. In the simplest setting, the conditional mean of the observation equals h(x). The algorithm uses that observation to decide its next move.

A common scalar update is x_next = x − aH(x,ξ), where a is a positive step size, also called a gain. The minus sign is appropriate when h increases through zero: above the root, h is positive and the update should reduce x; below the root, h is negative and the update should increase x.

The sign is part of the model

If h decreases through zero, the same minus sign can push the estimate away from the root. There is no universal rule that subtracting a noisy number produces improvement. First determine how the expected observation changes with the decision variable.

Also distinguish finding a root from minimizing a function. If h is the derivative of an objective, solving h(x) = 0 may locate a stationary point. Whether that point is a minimum depends on the objective’s structure. A root-finding method can be perfectly implemented while targeting a maximum or a point unrelated to the intended decision.

Write down the observation units as well. If x is measured in minutes and H in units of throughput error, the gain must convert between those units. Copying a numerical learning rate from another problem without considering scale can change the effective feedback strength dramatically.

Before running an algorithm, answer four questions: what is the target equation, what does one observation measure, why does the update move in a correcting direction on average, and which values of x are allowed? These questions provide a more reliable starting point than choosing a popular step-size schedule and hoping the plotted curve looks plausible.

Contents · Next chapter

CHAPTER 2 OF 14 · Define the target and update

2. Work a noisy root example by hand

Back to contents

Let h(x) = x − 3. Its unique root is x* = 3. Suppose the observation is H(x,ξ) = x − 3 + ε, where the noise ε has conditional mean zero. For a teaching path, use the particular noise values +1, −1 and 0, starting at x₀ = 0 with constant gain a = 0.5.

At the first step, the observation is 0 − 3 + 1 = −2. The new estimate is x₁ = 0 − 0.5(−2) = 1. At the second step, the observation is 1 − 3 − 1 = −3, so x₂ = 1 − 0.5(−3) = 2.5. At the third, the observation is 2.5 − 3 + 0 = −0.5, giving x₃ = 2.75.

One path illustrates arithmetic, not a theorem

This sequence moves closer to three, but a different noise sequence could temporarily move away. An update is not required to reduce the true error at every step. Its value comes from the combined behaviour of drift, noise and gain across repeated observations.

Without noise, the error e = x − 3 obeys e_next = (1 − a)e. At a = 0.5, each noiseless update halves the error. With noise, the recursion becomes e_next = (1 − a)e − aε. The first term contracts existing error; the second introduces a fresh disturbance.

This decomposition is the core mechanism. It separates two reasons an estimate can change: correction toward the root and response to random variation. A large movement is not automatically strong learning, and a small movement is not automatically accuracy.

For software testing, preserve this three-step example as an exact check. Verify the sign, the ordering of the observations and whether the gain is applied once. If a program returns 2.25 instead of 2.5 at the second step, investigate the implementation before studying convergence plots. Simple exact cases often expose errors that large noisy experiments conceal.

Previous chapter · Contents · Next chapter

CHAPTER 3 OF 14 · Define the target and update

3. Recognize the running average as stochastic approximation

Back to contents

Suppose Y₁, Y₂ and later observations have a common mean θ. The recursion m_n = m_(n−1) + (Y_n − m_(n−1))/n is the ordinary running sample mean when it begins with n = 1. It stores only the previous estimate and the new observation, yet after n observations it equals their arithmetic average.

The equation being solved is h(m) = m − θ = 0. A noisy observation of h(m) is m − Y_n. Subtracting that observation with gain 1/n produces exactly the running-average update.

Check the identity on concrete data

Take observations 4, 2 and 3. The first update gives m₁ = 4, regardless of the initial value because the first gain is one. The second gives m₂ = 4 + (2 − 4)/2 = 3. The third gives m₃ = 3 + (3 − 3)/3 = 3. These equal the successive sample averages 4, 3 and 3.

For independent observations with variance σ², the variance of m_n is σ²/n. This statement comes from the special averaging structure and the stated independence assumption. It does not mean that every stochastic-approximation estimate has variance σ²/n or that successive iterates are independent observations of the target.

The example also explains the role of a decreasing gain. Early observations can move the average substantially; later observations receive weight 1/n. No individual late observation can replace the entire accumulated history. If the target is truly constant, this helps average away noise.

If the target changes, however, the old history remains influential. After ten thousand observations, the next observation receives weight only one ten-thousand-and-first. That may be appropriate for estimating a stable population mean and unsuitable for quickly tracking a newly changed process. The same recursion can be excellent or poor depending on the target being estimated.

Previous chapter · Contents · Next chapter

CHAPTER 4 OF 14 · Choose gains and check stability

4. Understand what step-size conditions do and do not promise

Back to contents

Classical decreasing-gain analyses often use positive gains whose sum diverges while the sum of their squares converges. Informally, the updates retain enough total capacity to move, while their cumulative squared exposure to noise is controlled. These conditions are part of a convergence argument, not a complete convergence theorem by themselves.

For a_n = 1/n, the harmonic sum diverges and the sum of squares converges. More generally, a_n = c/n^γ with c > 0 has both properties when 1/2 < γ ≤ 1. At γ = 1/2 the squared gains behave like 1/n and their sum diverges. At γ > 1 the gains themselves have a finite sum.

A schedule cannot repair an unstable mean field

Consider a root problem with the wrong update sign. Even gains satisfying the two summability conditions can move the process in the wrong direction. Likewise, biased observations can target a shifted equation, and unbounded iterates can leave the region where the local model is useful.

The founding Robbins–Monro paper treats sequential experiments for locating a root of an unknown mean response under stated restrictions. Its importance is the formulation of learning from noisy observations, not a licence to attach a convergence claim to any decreasing learning rate.

In practice, record the actual schedule, including offsets and restarts. A rule c/(n+b) may reduce aggressive early updates, but c and b affect finite-run behaviour. If the observation counter resets unexpectedly, the gain can jump back to a large value. If the counter increments per batch in one implementation and per individual sample in another, equal-looking formulas may deliver very different updates.

A useful diagnostic is to plot gains alongside estimates and residual observations. A flat estimate accompanied by a nearly zero gain is weak evidence of success: the algorithm may simply have stopped responding. The question is whether the residual has become small in an independently meaningful sense, not whether the update has become visually imperceptible.

Previous chapter · Contents · Next chapter

CHAPTER 5 OF 14 · Choose gains and check stability

5. Derive the noise floor for a constant gain

Back to contents

Return to h(x) = x − 3 and independent zero-mean noise with variance σ². With constant gain a, the error obeys e_next = (1 − a)e − aε. Assume the new noise is independent of the current error. The mean error contracts by the factor 1 − a, while its variance follows V_next = (1 − a)²V + a²σ².

For 0 < a < 2, the magnitude of 1 − a is less than one. The limiting variance, if the recursion is run under these assumptions, solves V = (1 − a)²V + a²σ². Rearranging gives V = aσ²/(2 − a).

Quantify the speed–noise tradeoff

With σ² = 1 and a = 0.5, the limiting variance is 1/3 and the limiting standard deviation is approximately 0.577. With a = 0.1, the variance is 1/19, approximately 0.0526, and the standard deviation is approximately 0.229. The smaller gain reduces persistent fluctuations but contracts the initial mean error more slowly.

At a = 1, the new estimate is 3 − ε: it replaces the old state using the latest observation. It forgets initial error immediately but retains the full noise variance. This is responsive, not precise. At a = 2, the noiseless error alternates without contraction, and the stable-variance formula no longer applies.

The distinction between mean convergence and concentration around a point matters. The expected estimate can approach three while individual trajectories continue fluctuating. A graph averaged over many runs can therefore look smooth even though any single deployed run remains noisy.

Constant gains are not automatically a mistake. They can be useful when continued adaptation matters. But reporting a constant-gain noisy trajectory as exact convergence to a fixed root overstates what this elementary calculation supports. State whether the aim is asymptotic precision, a useful neighbourhood or responsiveness to change.

Previous chapter · Contents · Next chapter

CHAPTER 6 OF 14 · Choose gains and check stability

6. Check slope and scale before increasing the gain

Back to contents

Now change the mean response to h(x) = 4(x − 3). The root is still three, but the response is four times as steep. Without noise, the error recursion is e_next = (1 − 4a)e. Stability requires |1 − 4a| < 1, which means 0 < a < 0.5.

At a = 0.25, the noiseless error vanishes in one update because 1 − 4a = 0. At a = 0.4, the factor is −0.6: the estimate alternates around the root while shrinking its error. At a = 0.6, the factor is −1.4: the oscillations grow.

Reproduce an unstable trajectory

Starting at zero with gain 0.6 and no noise, h(0) = −12, so x₁ = 7.2. Then h(7.2) = 16.8, giving x₂ = −2.88. The next update gives x₃ = 11.232. The root has not changed; the gain is simply too large for the slope.

This example warns against diagnosing every oscillation as random noise. Deterministic overshoot can produce alternating behaviour even with exact observations. Conversely, modest fluctuations can be entirely compatible with a stable constant-gain noisy process. Inspect the expected dynamics before prescribing more averaging.

Changing measurement units can create the same practical issue. If a residual previously reported in metres is reported in centimetres, its numerical magnitude increases one hundredfold. Unless the gain is adjusted consistently, the update becomes one hundred times stronger in the decision variable’s units.

For several variables, different directions can have very different scales and sensitivities. A single gain may be gentle in one direction and unstable in another. Scaling, preconditioning and coordinate-specific methods address aspects of this problem, but they require a clear account of what information the update uses. The first repair is often a unit and sensitivity check, not a more elaborate optimizer.

Previous chapter · Contents · Next chapter

CHAPTER 7 OF 14 · Inspect gradients, bias and averaging

7. Connect stochastic approximation to stochastic gradients

Back to contents

Suppose the objective is F(x) = E[ℓ(x,Z)], and an available random vector g(x,Z) is an appropriate unbiased estimate of its gradient. The update x_next = x − a g(x,Z) is stochastic gradient descent. It is a stochastic-approximation method applied to a gradient field, with additional structure from the optimization problem.

For a scalar example, let ℓ(x,Z) = (x − Z)²/2, with E[Z] = 3 and finite variance. The gradient for one observation is x − Z. Its expectation is x − 3, so the mean objective is minimized at three. Using gain 1/n recovers the running-average mechanism from Chapter 3.

An observed loss can rise during useful learning

At a particular observation, moving toward that observation can worsen performance on another. A stochastic update does not generally decrease every sample loss or even the true expected objective at every step. Claims about expected decrease or convergence require specific assumptions and gain choices.

The specialist article on stochastic gradient descent, noisy gradients and learning rates develops this optimization setting. The broader subject also includes noisy root problems where no objective function is supplied. Keeping that distinction prevents useful gradient intuition from becoming an unsupported assumption.

The research review by Bottou, Curtis and Nocedal provides a route into large-scale machine-learning optimization and methods for handling stochastic directions. An algorithm’s practical success in that setting does not establish a universal guarantee for arbitrary noisy feedback.

Even the identity E[g(x,Z)] = ∇F(x) needs justification in a concrete model. It can depend on sampling and on conditions allowing differentiation and expectation to be interchanged. If observations are selected preferentially, or if a derivative estimator is systematically biased, the update may follow a different mean field from the one the analyst intended.

Previous chapter · Contents · Next chapter

CHAPTER 8 OF 14 · Inspect gradients, bias and averaging

8. Separate bias from random variation

Back to contents

Replace the observation in the root example by H(x,ξ) = x − 3 + b + ε, where b is a constant measurement bias and ε has conditional mean zero. The expected observation is now x − 3 + b. Its root is 3 − b.

If b = 0.4, the observed system points toward 2.6. More observations can make the algorithm increasingly consistent about that wrong target. Reducing the gain smooths the trajectory but does not remove the bias. Increasing the batch size averages ε more effectively while leaving b intact.

Identify which mean is being approximated

A positive bias might arise from a sensor offset, a truncated simulation, a systematically selected sample or an approximation inside the observation calculation. The numerical recursion cannot tell these apart. It sees only the response supplied to it.

Conditional unbiasedness is often the relevant requirement. The new error should have mean zero given the information used to choose the current iterate, under the model supporting the analysis. An error with unconditional mean zero across a dataset may still be predictably associated with the current state or sampling rule.

The guide to how martingales work explains why the information available at each stage matters. In stochastic approximation, a martingale-difference noise assumption describes the absence of a predictable residual drift relative to that history. It does not mean that all observations are independent or that every form of dependence is harmless.

For diagnosis, test the observation mechanism at fixed known inputs. Compare repeated measurements with an independently known answer, as in the root-at-three example. If the average observed residual is about 0.4 at the true root, the algorithm has a measurement problem before it has a gain problem. Repairing the update schedule alone cannot restore the intended equation.

Previous chapter · Contents · Next chapter

CHAPTER 9 OF 14 · Inspect gradients, bias and averaging

9. Use batches and averaging with clear accounting

Back to contents

Suppose one residual observation has conditional noise variance σ², and a batch contains b conditionally independent observations at the same iterate. Averaging those observations reduces the conditional noise variance to σ²/b. This calculation depends on independence or appropriate covariance handling; copying one observation b times does not create b units of information.

For the constant-gain linear example with a = 0.5 and σ² = 1, batches of four independent observations reduce the effective variance to 0.25. The limiting iterate variance becomes 0.5 × 0.25/(2 − 0.5) = 1/12, approximately 0.0833, rather than 1/3.

Compare cost as well as smoothness

Each batch update now costs four observations. Comparing one hundred single-observation updates with one hundred four-observation updates gives the second procedure four times as much data. A fair computational comparison should specify whether the budget is observations, simulator calls, elapsed time or another resource.

Batching and averaging iterates are different operations. Batching averages observations before an update. Iterate averaging combines points produced by the algorithm afterward. The iterates are generally dependent because each inherits information from earlier ones. Their average’s uncertainty cannot be calculated by treating them as independent raw measurements.

Averaging can also retain early bias. If an algorithm starts far from the target, averaging its entire trajectory includes those early poor estimates. Whether to average from the beginning or after a specified initial phase is part of the method and should be recorded. Selecting the averaging window after inspecting many alternatives can introduce further selection effects.

The best use of a batch is not necessarily the largest possible batch. More precise observations at each point can mean fewer opportunities to move within a fixed budget. If the current point is far from the target, many observations there may be less useful than a sequence of reasonably informative corrections. The tradeoff depends on noise, response geometry and the cost of each observation.

Previous chapter · Contents · Next chapter

CHAPTER 10 OF 14 · Constrain, estimate and track

10. Respect constraints and the meaning of projection

Back to contents

Suppose x must remain in an interval [0,5]. A projected update first proposes x − aH and then clips the result into that interval. This can prevent impossible actions and keep a numerical process within a specified domain. It also changes the update rule.

If the unconstrained root is three, projection may help maintain feasible iterates without excluding the desired target. If the unconstrained root is seven, however, projection cannot make seven feasible. The process may settle at the boundary five while the residual remains nonzero.

A boundary point needs the right interpretation

For the objective F(x) = (x − 7)²/2 constrained to [0,5], the constrained minimum is five. Its derivative is −2, not zero. The boundary solution is valid for constrained minimization even though it is not a root of the unconstrained gradient. A root-finding report that says the residual has vanished would be false.

With a = 1 and current x = 4, the unprojected gradient step proposes seven; projection returns five. A second identical step again returns five. The update is zero after projection, yet the unconstrained gradient is still −2. This gives another concrete reason that a small iterate change is not, by itself, a universal convergence certificate.

Clipping noisy residuals is a different modification from projecting the iterate. It can limit extreme updates but may change the conditional mean of the observation, especially with asymmetric noise. That modification needs analysis rather than an assumption that robustness is free.

For an implementation, log proposed and projected values separately, along with the frequency of boundary contact. Frequent clipping may indicate a genuine constrained solution, an excessively aggressive gain, an infeasible target or a unit error. Those possibilities call for different repairs. A projection operation keeps numbers inside a box; it does not explain why they belong near its edge.

Previous chapter · Contents · Next chapter

CHAPTER 11 OF 14 · Constrain, estimate and track

11. Estimate a quantile through noisy signs

Back to contents

Stochastic approximation is not limited to estimating means or gradients. Suppose Y has a continuous distribution with cumulative distribution function F, and the goal is a quantile x* satisfying F(x*) = q. At a proposed x, the indicator I(Y ≤ x) has expectation F(x).

The update x_next = x + a[q − I(Y ≤ x)] therefore moves upward when an observation exceeds x and downward when an observation is at or below it. Its expected increment is a[q − F(x)], which points toward the quantile when F increases through q.

Check a numerical update and its units

Let q = 0.8, x = 4 and a = 0.5 in the units of Y. If Y = 6, the indicator is zero and the next estimate is 4 + 0.5 × 0.8 = 4.4. If the next observation is Y = 3, the indicator at x = 4.4 is one and the update gives 4.4 + 0.5 × (−0.2) = 4.3.

The unequal upward and downward increments reflect the chosen quantile. An upper quantile should sit above most observations; downward updates occur more often near equilibrium but are smaller. For the median q = 0.5, the two increment magnitudes are equal.

This mechanism assumes a suitable target and response structure. A discrete distribution can have jumps, so the equation F(x) = q may have no exact solution or more than one relevant quantile convention may be needed. Flat regions can also make location identification difficult. State the quantile definition before claiming convergence to a unique number.

Quantile estimation illustrates a valuable design pattern: construct an observable quantity whose expectation reveals which side of the target the current estimate occupies. Then verify the sign, scale, noise and regularity assumptions. The attractive simplicity of a one-line update does not remove the need to define what answer it is supposed to approximate.

Previous chapter · Contents · Next chapter

CHAPTER 12 OF 14 · Constrain, estimate and track

12. Distinguish convergence from tracking a moving target

Back to contents

A decreasing gain is designed in many classical settings to settle toward a fixed target. A moving target creates a different task. If the underlying mean changes while gains become extremely small, the algorithm may retain old information too strongly to adapt in useful time.

For a simple mean tracker, m_next = (1 − a)m + aY_next with constant a. After the true mean jumps from three to five, and assuming zero-mean observation noise, the expected tracking error relative to five is multiplied by 1 − a at each update. If the estimate starts at three and a = 0.2, the expected estimate after k updates is 5 − 2(0.8)^k.

Quantify lag instead of calling it failure

After five updates, the expected estimate is 4.34464. After ten it is approximately 4.78525. The tracker is adapting, but it lags. A larger gain would reduce this expected lag while increasing sensitivity to observation noise.

For a target increasing by a constant amount v each step, the same tracker has a steady expected error of −(1 − a)v/a relative to the current target under this timing convention. With a = 0.2 and v = 0.1, the expected lag is −0.4. The formula assumes a continuing linear trend and the stated observation timing, not arbitrary change.

This clarifies why a positive noise floor may be acceptable in a tracking problem but undesirable in a fixed-parameter estimation problem. The correct comparison concerns responsiveness and error under the actual target dynamics. A method optimized for one objective can perform poorly at the other.

Before changing the gain in response to a drifting graph, check whether the system changed, the measurement changed or the algorithm became unstable. These explanations can produce similar pictures. Preserve timestamps and model versions so that adaptation is evaluated against the target that existed when each observation was collected.

Previous chapter · Contents · Next chapter

CHAPTER 13 OF 14 · Transfer and continue learning

13. Diagnose apparent convergence and test transfer

Back to contents

First exercise: an estimate barely moves after many iterations, but fresh residual observations have average 0.8. Is the root established? No. A tiny gain can produce tiny updates even when the expected residual is substantial. Check the gain scale, available movement and whether the observation model is biased.

Second exercise: the response changes from h(x) = x − 3 to h(x) = 4(x − 3), while a constant gain 0.6 is retained. What happens without noise? The error multiplier changes from 0.4 to −1.4. The first system contracts; the second oscillates with growing magnitude. The target stays three, but the stable gain range changes.

Match each symptom to a mechanism

Third exercise: a sensor adds 0.4 to every residual. Will taking sixteen measurements per update remove the error? No. Independent random noise variance can fall by a factor of sixteen, but the systematic bias remains. The mean observed root is 2.6 in the linear example.

Fourth exercise: a projected optimization iterate remains at five for the objective (x − 7)²/2 on [0,5]. Must the algorithm be broken because the derivative is nonzero? No. Five is the constrained minimum. The right optimality condition accounts for the boundary rather than demanding an unconstrained root.

Fifth exercise: replace an independent batch of four measurements with four copies of one measurement. Does the variance divide by four? No. Perfectly duplicated measurements have the same average as the single observation. Counting rows is not the same as adding information.

For practical validation, freeze a proposed solution and collect fresh observations suited to the intended claim. Examine residual behaviour, objective performance or feasibility as appropriate. If the evaluation itself uses repeated inspection and data-dependent stopping, consult Sequential Analysis rather than automatically attaching fixed-sample uncertainty statements. Learning a candidate and establishing what can be said about it are related but separate tasks.

Previous chapter · Contents · Next chapter

CHAPTER 14 OF 14 · Transfer and continue learning

14. Learning routes, common questions and primary reading

Back to contents

What should a beginner implement first?

Implement the running mean, the noisy root at three and the steep noiseless response. Keep the noise sequence fixed while changing the gain so that differences in trajectories can be attributed to the update choice. Then repeat whole experiments with independent noise streams to study variability. Save both single trajectories and summaries across runs; they answer different questions.

Does every stochastic-approximation method minimize a loss?

No. The mean response may define a root problem without being the gradient of an objective. Even when it is a gradient, a stationary point is not automatically a global minimum. The problem structure determines what a successful root or stationary-point calculation means.

Does a decreasing gain guarantee convergence?

No. The gain conditions must be combined with assumptions about the mean response, noise and stability. Wrong signs, biased feedback, excluded targets or changing data-generating mechanisms can invalidate the intended conclusion. A schedule is one ingredient of a method.

What must a reproducible result record?

Record the target equation or objective, observation mechanism, initialization, gain schedule, counters, units, constraints, random-stream handling, batch sizes and stopping rule. Preserve any projection, clipping, restart or averaging choices. Report what independent checks were performed and whether the final claim concerns a root, constrained optimum, neighbourhood or tracking error.

Where should a practitioner read next?

Read Robbins and Monro’s original paper for the foundational noisy-root formulation. Use Bottou, Curtis and Nocedal’s research review for the connection with stochastic optimization in machine learning. The calculations here are original teaching derivations with deliberately simple assumptions, not performance claims for a particular software package or real system.

Continue through the site’s stochastic-gradient explanation for noisy optimization directions, martingale guide for conditional information, and Simulation Optimization root for decision validation. The transferable skill is to explain what the update learns on average, why its size is appropriate and which new evidence would show that the apparent target is wrong.

Previous chapter · Contents · Gold Standard master