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 RobbinsMonro 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:Is there already a type of algorithm similar to the RobbinsMonroalgorithm? 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 algorithmin the resources that I can access.If such an algorithm in 1 can work, what is itsrationale/intuition/motivation of $x_{n+1}=x_n-a_n M(x_n)$? Byrationale/intuition/motivation, I mean, for example, tangent lineapproximation in Newton's method for solving equation, and steepestdescent 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!
What is the deterministic counterpart of Robbins-Monro algorithm?
optimization;stochastic
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.