Question

When applying the Robbins-Monro algorithm for stochastic approximation, what is the necessary condition for the sequence of step sizes to ensure the algorithm converges to the root?

Accepted Answer

The Robbins-Monro algorithm is a method used to find the root of a function when you can only observe the function through noisy measurements. To guarantee that the sequence of estimates converges to the true root, the sequence of step sizes, often denoted as alpha sub n, must satisfy two specific conditions. First, the sum of all step sizes must be infinite, which is expressed as the sum of alpha sub n from n equals one to infinity equals infinity. This condition is necessary because the algorithm needs the step sizes to be large enough to travel from any initial starting point to the target root regardless of how far away it is. Second, the sum of the squares of the step sizes must be finite, expressed as the sum of the square of alpha sub n from n equals one to infinity is less than infinity. This condition is necessary to ensure that the step sizes shrink quickly enough to eventually suppress the random noise inherent in the measurements, allowing the algorithm to settle precisely at the root rather than oscillating around it. A classic example of a sequence that satisfies both conditions is alpha sub n equals one divided by n.

Home → All Courses → Science and Mathematics Courses → Computational Statistics → Flashcard

When applying the Robbins-Monro algorithm for stochastic approximation, what is the necessary condition for the sequence of step sizes to ensure the algorithm converges to the root?