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.

• 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. – microhaus Mar 16 at 20:17
• @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. – MLNewbie Mar 16 at 20:51
• 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. – EngrStudent Mar 29 at 9:34

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