6
$\begingroup$

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!

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Just in case that course note might be gone, it has been recorded in the internet archive $\endgroup$
    – John L.
    Jan 24 '20 at 20:15
0
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Can you provide more context on your answer $\endgroup$ Jan 24 '20 at 19:31
  • 1
    $\begingroup$ provided a more detailed explanation $\endgroup$
    – isnvi23h4
    Jan 25 '20 at 5:19
  • $\begingroup$ I think I follow the logic here, but not how this shows the convergence of gradient descent. Can you explain that part? $\endgroup$
    – JacKeown
    May 9 '21 at 16:42
  • $\begingroup$ @JacKeown if π‘₯(𝑛) 𝑏𝑒 π‘Ž π‘π‘œπ‘–π‘›π‘‘ π‘œπ‘› π‘₯βˆ’π‘Žπ‘₯𝑖𝑠 π‘€β„Žπ‘’π‘Ÿπ‘’ 𝑓′(π‘₯) = 0 , and π‘Žπ‘›π‘‘ π‘₯(𝑛 + β„Ž) 𝑖𝑠 π‘Žπ‘›π‘¦ π‘œπ‘‘β„Žπ‘’π‘Ÿ π‘Žπ‘Ÿπ‘π‘–π‘‘π‘Žπ‘Ÿπ‘¦ π‘π‘œπ‘–π‘›π‘‘, then deducting πœ‚×𝑓′(π‘₯(𝑛 + β„Ž)) from π‘₯(𝑛 + β„Ž) will always lead to π‘₯(𝑛) which is the lowest point for the y-axis as 𝑓′(π‘₯) = 0. Hence, convergence $\endgroup$
    – isnvi23h4
    May 10 '21 at 17:52

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.