We review the proof by Robbins and Munro for finding fixed points. Stochastic gradient descent, Q-learning and a bunch of other stochastic algorithms can be seen as variants of this basic algorithm. We review the basic ingredients of the original proof.
Often it is important to find a solution to the equation
by evaluating at a sequence of points. For instance Newton’s method would perform the updates . However, Robbins and Munro consider the setting where we cannot directly observe but we might observe some random variable whose mean is . Thus we observe
and hope solve for . Notice in this setting, even if we can find , Newton’s method may not converge. The key idea of Robbins and Munro is to use a schema
where we chose the sequence so that
Before proceeding here are a few different use cases:
- Quartiles. We want to find such that for some fixed . But we can only sample the random variable .
- Regression. We preform regression , but rather than estimate we want to know where .
- Optimization. We want to optimize a convex function whose gradient is . Assume that for some large . To find the optimum at we randomly sample (uniformly) whose gradient, , is an bias estimate of .
Robbins-Munro Proof.
We now go through the main steps of Robbins and Munro’s proof. This proof is intentionally not the most general but instead gives the key ideas.
We assume that is an increasing, smooth, real-valued function from to and that there is a unique point such that . Further assume and that samples belong to the interval and .
In the steps below we prove the following:
Thrm [Robbins-Munro] If we chose acording to the Robbin-Munro step rule then we have that
where here satisfies .
Ex 1. Let . Show that for Robbins-Munro
for terms
Ans 1.
as required.
Ex 2. Argue that for some constant .
Ans 2. Since is increasing, smooth and it must be that
Thus
Ex 3. Argue that if then and exists.
Ans 3. Summing the expression for [[RM:1]] over gives
Since is bounded and is finite it must be that and exists.
Ex 4. Finally argue that if then
Ans 4. We know from [3] and [3] that
Since we choose so that . It must be that . Further since we know the limit exists it must be that , as required.