<p>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</p>

<ul>
<li>Armijo, Larry (1966). <a href="http://projecteuclid.org/euclid.pjm/1102995080" rel="nofollow">"Minimization of functions having Lipschitz continuous first partial derivatives"</a>. Pacific J. Math. 16 (1): 1–3.</li>
</ul>

CC BY-SA 3.0
2012-06-28T16:23:37.723Z
2012-06-28T16:23:37.723Z
mrig
<p>My question is at the bottom.
(Most of the descriptive words come from Chris. Bishop's <em>Neural Networks for Pattern Recognition</em>)</p>

<p>let $w$ be the weight vector of the neural network and $E$ the error function. </p>

<p>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$$</p>

<p>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}}$$</p>

<p>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}}$$</p>

CC BY-SA 3.0
2012-04-10T17:41:59.547Z
The $\eta$ in the latter formula can be chosen to be much smaller, then change in $w$ will be small and there is hope to show similar convergence as the first formula. Full proof will be more technically involved and may require some properties of the error function.
Rong Ge
<machine-learning><ai.artificial-intel><network-modeling>
Theoretical proof of convergence of sequential weight update procedure (Neural Networks and Machine Learning)
Chen
# Theoretical proof of convergence of sequential weight update procedure (Neural Networks and Machine Learning)

(Asked by: username_0 on 2012-04-08)

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}}$$

**Tags:** machine-learning, ai.artificial-intel, network-modeling
> **Comments:**
> **username_1**: The $\eta$ in the latter formula can be chosen to be much smaller, then change in $w$ will be small and there is hope to show similar convergence as the first formula. Full proof will be more technically involved and may require some properties of the error function.  

---

## 1 answers

### Answer by username_2 on 2012-06-28. Score: 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"](http://projecteuclid.org/euclid.pjm/1102995080). Pacific J. Math. 16 (1): 1–3.


---

