What is the deterministic counterpart of Robbins-Monro algorithm?

Question

From Wikipedia, assume that we have a function $M(x)$, and we want to solve the equation $M(x) = 0$. But we cannot directly observe the function $M(x)$, we can instead obtain measurements of the random variable $N(x)$ where $E[N(x)] = M(x)$. The Robbins–Monro algorithm is to solve this problem by generating iterates of the form: $$ x_{n+1}=x_n-a_n N(x_n) $$ where $a_1, a_2, \dots$ is a sequence of positive step sizes.

If considering solving the deterministic version of the equation instead, ie solving $M(x)=0$ when $M(x)$ can be observed directly, I wonder:

1. Is there already a type of algorithm similar to the Robbins–Monro algorithm? Is it $$ x_{n+1}=x_n-a_n M(x_n) $$ where $a_1, a_2, \dots$ is a sequence of positive step sizes? I couldn't find such an algorithm in the resources that I can access.
2. If such an algorithm in 1 can work, what is its rationale/intuition/motivation of $x_{n+1}=x_n-a_n M(x_n)$? By rationale/intuition/motivation, I mean, for example, tangent line approximation in Newton's method for solving equation, and steepest descent in gradient descent method for optimization.

The reason of asking this question is that I think most, if not all, stochastic approximation algorithms are inspired from some algorithms for the similar deterministic cases.

Thanks and regards!

Answer 1

In the deterministic case, you can of course run the same algorithm, but it is very inefficient compared to quasi-Newton (Broyden type) methods. There is little point to investigate the properties of so poor an algorithm.

On the other hand, broyden's method is quite sensitive to noise, hence cannot be easily adapted to the stochastic case. Moreover, if the amount of noise is large then convergence is dictated by the law of large numbers anyway, and there is little to be gained from trying to adapt algorithms with superlinear convergence.

Answer 2

The Wikipedia article on this topic is rather bad (from an educational point of view) and somewhat misleading. Do not use it. You'll find a better summary of the method here. In particular, I find it confusing to call $a_k$ a step sequence.

---

To get an intuitive understanding of the method, let's look at Newton's method for the (deterministic) function $M(x)$ first. The iteration looks like this:

$$x_{n+1} = x_{n} - \frac{1}{M'(x_n)} M(x_n)$$

Notice that if $a_n = 1/M'(x_n)$ then the Robbins-Monro iteration is just Newton's method. In fact to make the Robbins-Monro iteration work well, one needs to start with an estimate of $M'(x_n)$ (as described in the paper I linked). This is the first step towards the intuitive understanding of the method.

Now let's write $N(x) = M(x) - \eta$ where $\eta$ is a noise term with mean zero. Then the sequence of iterates will be $$x_{n+1} = x_n - a_n N(x_n) = x_n - a_n M(x_n) + a_n \eta_n.$$

As the iteration progresses, the noise terms $a_n\eta_n$ get added up. If the $a_n$ sequence is decreasing then the noise will decrease too. (This might not be entirely obvious from the formula above, but it can be shown with more rigorous calculations.)

To better understand what is happening during iteration, let us study the case when $M(x) = \alpha (x - \bar x)$, i.e. $M(x)$ is a linear function with root $\bar x$. This is usually a good approximation in a narrow enough interval around the root. Let us choose $a_n = a/M'(x_n) = a/\alpha$. In other words, the number $a$ tells us how close we are to the exact Newton iteration (sans noise). If $a=1$ then we re-gain Newton's method, plus the noise term. If $a$ is in a certain interval around 1, then the iteration will still converge to the root $\bar x$. Let's find this interval:

The sequence will be $$x_{n+1} = x_n (1-a) + a \bar x + a \eta_n/\alpha,$$ or in terms of the staring value $x_0$, $$x_n = (1 - (1-a)^n)\bar x + x_0 (1-a)^n + \text{noise}.$$

The Newton-like part of this iteration converges if $0 < a < 2$, and the convergence is fastest if $a=1$. But what about the noise term? It can be shown that the noise in $x_n$ depends monotonically on $a$ for $0<a<2$ and it gets smaller as $a$ decreases. Thus we have a tradeoff between fast convergence of the Newton-like part and effective averaging of the noise. If $a$ is small then we get good averaging of the noise but slow convergence of the deterministic part and vice versa. A decreasing $a_n$ sequence helps with faster convergence initially and more effective averaging of the noise in later steps.

I hope this helps.