4
$\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!

| cite | improve this question | | | | |
$\endgroup$
4
$\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.

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ Just in case that course note might be gone, it has been recorded in the internet archive $\endgroup$ – John L. Jan 24 at 20:15
-1
$\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]$$

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ Can you provide more context on your answer $\endgroup$ – narek Bojikian Jan 24 at 19:31
  • 1
    $\begingroup$ provided a more detailed explanation $\endgroup$ – souparno majumder Jan 25 at 5:19

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.