# Convergence of gradient descent method with one parameter

We want to minimize the mean square error in a regression model that uses just one paremeter $w_0$. For convinience we take the mean square error to be $MSE(w_0) = \frac{1}{2N} \sum_{i=1}^{N} (y_n - w_0)^2$ so that gradient descent method takes the form $w^{t+1} = (1-\gamma) w^{t} + \frac{\gamma}{N} \sum_{n = 1}^{N} y_n$.

In the case $\gamma \in ]0,1]$ this sequence clearly converges using the fact that it is a convex combination of points and that therefore we get a monotone and bounded sequence.

What happens if $\gamma \ni ]0,1]$?

• If you define $c=\frac{\gamma}{N}\sum_{n=1}^Ny_n$ then your recursion is $w[t+1] = (1-\gamma)w[t] + c$ and this is a linear recurrence relation over $t \in \{0, 1, 2, ...\}$ that can be solved for any $\gamma \in \mathbb{R}$. Do you know how to solve those? For example, find a particular solutoin, and a class of homogeneous solutions? – Michael Oct 10 '16 at 21:08
• @Michael you're right using characteristic polynomial isn't it? – Javier Oct 10 '16 at 21:10
• I suppose so. You can look for homogeneous solutions of the type $w[t] = x^t$. And particular solutions of the type $w[t]=b$ (constant). – Michael Oct 10 '16 at 21:11
• up to now my conclusion is that it only converges if $0 < \gamma \le 2$ – Javier Oct 10 '16 at 21:43
• For $\gamma=2$ it does not necessarily converge. – Michael Oct 11 '16 at 0:57