6
$\begingroup$

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!

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks! (1) I wonder why "if the amount of noise is large then convergence is dictated by the law of large numbers"? (2) Also what is the 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. $\endgroup$ – Tim May 9 '12 at 1:33
  • $\begingroup$ @Tim: (1) To get accurate results you need to average over the noise, and the accuracy of the avarage is governed by the law of large numbers and restricts convergence speed to $O(N^{-1/2})$. - (ii) If you have a linear system of equations, this is a crude form of a Kryl;ov subspace iteration. Taking the analogy further would give more sphisticated schemes with an additional forcing term proportional to $M(x_{n-1})$. $\endgroup$ – Arnold Neumaier May 9 '12 at 10:23
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.