The Robbins/Monro Algorithm is a type of stochastic optimization algorithm of the following form: (as mentioned in wikipedia)

$$x_{n+1} - x_n = a_n(\alpha - N(x_n))$$

where $M(x) = \alpha$ is a nondecreasing function whose root is at $x=\theta$, $N$ is a random variable where $E(N) = M(x)$. (E is the expectation). Furthermore, $a_n$ is a sequence of positive terms.

A paper entitled 'Bayesian Learning via Stochastic Gradient Langevin Dynamics' written by Max Welling and Yee Whye Teh wrote the same Robbins/Monro Algorithm but in a different shape and form I was not able to recognize:

$$\Delta\theta_t = \dfrac{\epsilon_t}{2}\left ( \nabla \log p(\theta_t) + \dfrac{N}{n} \sum_{i=1}^n \nabla\log p(x_{ti}|\theta_t) \right)$$

The left hand might be similar to a change in $x$ as shown above. $\epsilon$ is a sequence, which corresponds to the term $a_n$ above. What I do not recognize are the $\nabla \log$ terms. $p$ are probabilities, so maybe they are trying to apply this to bayesian statistics as is implied in the title. I am so lost here. Is someone familiar with this?

  • $\begingroup$ It's impossible to say without looking at the context in detail, but I know this notation for finite differences which are sometimes useful for simplifying formulae. $\endgroup$ – Raphael Apr 1 '15 at 11:53
  • 1
    $\begingroup$ I believe this is gradient of the log of a probability function. In Bayesian Statistics, $\theta$ is a parameter treated as a random variable. So $p(\theta)$ is called the prior distribution. On the other hand, $p(x_{ti}|\theta_t)$ is the posterior distribution. I can identify the components piece by piece, but when they are all put together, I do not understand how this resembles the algorithm. They look quite different. $\endgroup$ – cgo Apr 1 '15 at 13:00

Your Answer

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

Browse other questions tagged or ask your own question.