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]$?

  • 1
    $\begingroup$ 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? $\endgroup$ – Michael Oct 10 '16 at 21:08
  • $\begingroup$ @Michael you're right using characteristic polynomial isn't it? $\endgroup$ – Javier Oct 10 '16 at 21:10
  • $\begingroup$ 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). $\endgroup$ – Michael Oct 10 '16 at 21:11
  • $\begingroup$ up to now my conclusion is that it only converges if $ 0 < \gamma \le 2$ $\endgroup$ – Javier Oct 10 '16 at 21:43
  • $\begingroup$ For $\gamma=2$ it does not necessarily converge. $\endgroup$ – Michael Oct 11 '16 at 0:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.