Skip to content
Search

Gradient descent

lastmod 2022-11-25created 2015-12-2231 edits

Gradient descent is a first-order optimization algorithm for finding approximations. The basic idea is to compute the slope (gradient) of a function and keep moving toward the lower slope, repeating until an extremum is reached.

In short, it means finding the local optimum (Maxima and minima) of a given Cost function.

Description

For a function \(f(\mathbf{x})\) to be optimized, first choose a starting point \(\mathbf{x}_0\). Given the current \(\mathbf{x}_i\), the next point to move to, \(\mathbf{x}_{i+1}\), is computed as follows.

\[ \mathbf{x}_{i+1} = \mathbf{x}_i - \gamma_i \nabla f(\mathbf{x}_i) \]

Here \(\gamma_i\) is a parameter that controls the distance to move (the convergence speed of the algorithm), and is called the Step size or Learning rate.

(For reference, \(\gamma\) is the Greek letter 'gamma')

Whether this algorithm converges depends on the properties of \(f\) and the choice of \(\gamma_i\). Also, this algorithm converges to a local optimum (Maxima and minima). Therefore, the value found is not guaranteed to be the global optimum, and it depends on the choice of the starting point \(\mathbf{x}_0\). Accordingly, gradient descent may be applied several times from various starting points and the best result among them chosen.

In the Machine learning

Gradient Descent is the process of finding a function's Local minimum through Gradient computation. If you keep following the direction in which the function decreases fastest, you reach the lowest point, and that is exactly the Local minimum. It is simple to think of it as going down a mountain by following the direction that descends fastest from the top.

600px-Extrema_example_original.svg.png

There is one problem, though: even when coming down the mountain, we are finding the fastest way down from the current position, not descending to the lowest point overall, so it does not always converge to the lowest value of the whole function. For this reason, the starting point of the descent greatly affects the result. It is a concept used very often in machine learning, and this Local minimum problem often remains a critical drawback for performance to the very end.

from the Loss function

Let me start with the Loss function. You just need to choose the Hypothesis for which the Loss function has the smallest value. Then how do you find that value? There are various methods, but generally a method called Gradient desent is used. Gradient descent can be thought of simply as a way to go down a mountain when you are lost.

  1. To get down the mountain fastest, you would probably head toward the steepest point from where you are currently standing,
  2. and from the position you moved to, head once again toward the steepest point,

and by repeating this process, you will eventually be able to reach the lowest point.

Fff.png

As the figure above shows, if you keep walking down along the steepest point, you will be able to reach the lowest point. But one problem arises here. What if the Initial Condition were not the small peak but the high peak on the opposite side? Then we would probably end up not at the Global minimum, the lowest point overall, but at a Local minimum, the lowest point in the vicinity. There is clearly a big difference between choosing the smallest value overall and the smallest value in its vicinity. Despite this drawback, however, gradient descent is one of the most widely used methods, for the following reasons.

  • It is easy to implement.
  • It can be extended to any dimension and space.

With gradient descent, you can also control the speed. The convergence speed changes drastically depending on how far you move before changing direction when going down the mountain. If the step is too small, it takes too long; if the step is too large, in the worst case it may fail to converge to a single point. Not only that, in some cases gradient descent may never end. However, these drawbacks can be compensated for in various ways, and above all, as the code below shows, it is so simple to implement that it is a very widely used method.

Linear regression example

A simple Linear regression produces a graph like the one below, a contour graph that appears when there are two independent variables.

Machine_learning_-_Comparison_of_a_few_optimization_methods.gif

As an easier-to-understand image, assume you are looking at the graph below from above (the z-axis). (Think of it as the Cost graph of a and b in y = ax + b)

Linear_Regression_-Gradient_descent-_3d_graph.jpg

Sample code 

# From calculation, we expect that the local minimum occurs at x=9/4

x_old = 0
x_new = 6 # The algorithm starts at x=6
gamma = 0.01 # step size
precision = 0.00001

def f_derivative(x):
    return 4 * x**3 - 9 * x**2

while abs(x_new - x_old) > precision:
    x_old = x_new
    x_new = x_old - gamma * f_derivative(x_old)

print("Local minimum occurs at", x_new)

Sample code 2

See GradientDescent:Example.

See also

Favorite site

References

  1. Visualizing_the_gradient_descent_method.pdf ↩

author Zer0 sitemap