1
$\begingroup$

I know that gradient descent takes steps towards a minimum, but I am having trouble coming up with intuitions about when it will converge.

For example, on any given convex function is gradient descent guaranteed to converge? I'm inclined to say no because the steps could be too big, but I'm not certain.

More specifically, with ordinary least squares is gradient descent guaranteed to converge? I'm inclined to say no for the same reason, but again I'm not sure.

Improve this question
$\endgroup$
3
  • $\begingroup$ Would you mind specifying whether you are doing gradient descent using one training point at a time (stochastic gradient descent), more than one training point at a time (mini-batch stochastic gradient descent), or the entire training set at a time (batch gradient descent)? As it will assist me in giving you more concrete results concerning convergence guarantees and rate of convergence. $\endgroup$ – microhaus Mar 16 at 20:17
  • $\begingroup$ @microhaus My main thought was do stochastic gradient descent, but I am open to other gradient descent methods if there are different guarantees about convergence. $\endgroup$ – MLNewbie Mar 16 at 20:51
  • $\begingroup$ Initial condition plays here too. For a smooth and convex surface with a single global minimum, and given gradient descent with fixed step size, there are initial conditions that guarantee exact convergence. Also, there are orderings of training data that impact path of descent as implied by the SGD comment. $\endgroup$ – EngrStudent Mar 29 at 9:34
2
$\begingroup$

Your intuition is not wrong. The convergence of gradient descent depends crucially on the step size, which in turn depends on the shape of the function. The precise mathematical statement is due to Armijo (1966), but all modern numerical optimization textbooks contain a chapter on this, for instance chapter 3 of Nocedal & Wright (2006).

Improve this answer
$\endgroup$
3
  • $\begingroup$ I assume this intuition holds in the ordinary least squares case as well? $\endgroup$ – MLNewbie Mar 16 at 20:51
  • $\begingroup$ If by "ordinary least squares" you mean a quadratic objective function ("least squares problem"), not the OLS estimator. $\endgroup$ – Durden Mar 16 at 20:53
  • $\begingroup$ Yes I do mean the OLS problem, not the estimator. $\endgroup$ – MLNewbie Mar 16 at 21:06
0
$\begingroup$

Perhaps I could answer the part about your intuition on convex functions. For a convex and differentiable function $f:\mathbb{R}^{n} \to \mathbb{R}$ which has a L-smooth gradient $||\nabla f(x) - \nabla f(y)|| \leq L||x-y||_{p}$, (standard) gradient is guaranteed to converge assuming a fixed step size $t \leq \frac{1}{K}$. In this case, the convergence rate only depends on the number of iterations and the convergence rate is $\mathcal{O}\left(\frac{i}{num\;iterations}\right)$

You can find a good proof here.

Improve this answer
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.