Theoretical proof of convergence of sequential weight update procedure (Neural Networks and Machine Learning)

Question

My question is at the bottom. (Most of the descriptive words come from Chris. Bishop's Neural Networks for Pattern Recognition)

let $w$ be the weight vector of the neural network and $E$ the error function.

According to the Robbins-Monro algorithm, this $$w_{kj}^{(r+1)}=w_{kj}^{(r)}-\eta\left.\frac{\partial E}{\partial w_{kj}}\right|_{w^{(r)}}$$ will converge to where $$\frac{\partial E}{\partial w_{kj}}=0$$

In general the error function is given by a sum of terms each of which is calculated using one of the patterns from the training set, so that $$E=\sum_nE^n(w)$$ And in applications we just update the weight vector using one pattern at a time $$w_{kj}^{(r+1)}=w_{kj}^{(r)}-\eta\frac{\partial E^n}{\partial w_{kj}}$$

My question is: Why the algorithm will converge using the last formula? Once we use it to update the $w$, the value of $w$ is changed, I can't prove the convergence using $$\frac{\partial E}{\partial w_{kj}}=\sum_n \frac{\partial E^n}{\partial w_{kj}}$$

Answer 1

As pointed out by Rong, for gradient descent to converge the learning rate $\eta$ has to be chosen appropriately. It has to be large enough that every update determines a big enough change in the weights, but it has to be small enough not to overshoot the local minimum of the cost function. You may want to take a look at this paper that analyzes some sufficient conditions for gradient descent to work

• Armijo, Larry (1966). "Minimization of functions having Lipschitz continuous first partial derivatives". Pacific J. Math. 16 (1): 1–3.