Mathematical proof for why gradient descent algorithm always converges

I am currently learning machine learning and I stumbled across gradient descent. I understand why the algorithm always converges to the global/local minimum when the learning rate is small enough in my head, but is there a mathematical proof?

Thank you!

It looks like you put some emphasis on mathematical rigor. It just happens my motto is currently "from math and larger than math".

Yes, there are many mathematical proofs for conclusions along the line that gradient descent method converges to local minimum when the steps are small enough. We will need some precise statement on the condition of $f$ and the steps taken. Let me quote from Wikipedia,

With certain assumptions on the function $F$ (for example, $F$ convex and $\nabla F$ Lipschitz) and particular choices of $\gamma$ (e.g., chosen either via a line search that satisfies the Wolfe conditions or the Barzilai-Borwein method shown as following), $$\gamma_n=\frac{(x_n-x_{n-1})^T[\nabla F(x_n) - \nabla F(x_{n-1})]} {||\nabla F(x_n) - \nabla F(x_{n-1})||^2}$$ convergence to a local minimum can be guaranteed. When the function $F$ is convex, all local minima are also global minima, so in this case gradient descent can converge to the global solution.

For some actual statements and proofs in their full clear detail, you can read a course note by Ryan Tibshirani at CMU. Unfortunately, because of the required mathematical rigor, they are too long to be included here.

• Just in case that course note might be gone, it has been recorded in the internet archive Jan 24 '20 at 20:15

$$let,\ x_{(n)} \ be\ a\ point\ on\ x-axis\ where\ f'( x) \ =\ 0\ ,\ and\ x_{(n\ +\ h)} \ is\ any\ other\ arbitary\ point \\ \therefore \ \ \frac{f'( x_{(n\ +\ h)})}{|\ f'( x_{(n\ +\ h)}) \ |} =\begin{cases} 1 & \mathrm{if,} \ h\ \ >0\\ 0 & \mathrm{if,} \ h\ =\ 0\\ -1 & \mathrm{if,} \ h\ < \ 0 \end{cases}\\similarly,\ \ \frac{x_{(n)} \ -\ x_{(n\ +\ h)} \ }{|\ x_{(n)} \ -\ x_{(n\ +\ h)} \ |} \ =\ \begin{cases} 1 & \mathrm{if,} \ h\ \ < 0\\ 0 & \mathrm{if,} \ h\ =\ 0\\ -1 & \mathrm{if,} \ h\ >\ 0 \end{cases}\\or,\ \frac{x_{(n)} \ -\ x_{(n\ +\ h)} \ }{|\ x_{(n)} \ -\ x_{(n\ +\ h)} \ |} \ =\ -\ \ \ \frac{f'( x_{(n\ +\ h)})}{|\ f'( x_{(n\ +\ h)}) \ |}\\ \therefore \ x_{(n)} \ =x_{(n\ +\ h)} \ -\ \eta \times f'( x_{(n\ +\ h)}) \ \ \ \ \ \ \left[ where\ \eta \ =\frac{|\ x_{(n)} \ -\ x_{(n\ +\ h)} \ |}{|f'( x_{(n\ +\ h)}) \ |} \ \right]$$

• Can you provide more context on your answer Jan 24 '20 at 19:31
• provided a more detailed explanation Jan 25 '20 at 5:19
• I think I follow the logic here, but not how this shows the convergence of gradient descent. Can you explain that part? May 9 '21 at 16:42
• @JacKeown if 𝑥(𝑛) 𝑏𝑒 𝑎 𝑝𝑜𝑖𝑛𝑡 𝑜𝑛 𝑥−𝑎𝑥𝑖𝑠 𝑤ℎ𝑒𝑟𝑒 𝑓′(𝑥) = 0 , and 𝑎𝑛𝑑 𝑥(𝑛 + ℎ) 𝑖𝑠 𝑎𝑛𝑦 𝑜𝑡ℎ𝑒𝑟 𝑎𝑟𝑏𝑖𝑡𝑎𝑟𝑦 𝑝𝑜𝑖𝑛𝑡, then deducting 𝜂×𝑓′(𝑥(𝑛 + ℎ)) from 𝑥(𝑛 + ℎ) will always lead to 𝑥(𝑛) which is the lowest point for the y-axis as 𝑓′(𝑥) = 0. Hence, convergence May 10 '21 at 17:52