Gradient descent

Gradient descent is a method for unconstrained mathematical optimization. It is a first-order iterative algorithm for minimizing a differentiable multivariate function.

The idea is to take repeated steps in the opposite direction of the gradient (or approximate gradient) of the function at the current point, because this is the direction of steepest descent. Conversely, stepping in the direction of the gradient will lead to a trajectory that maximizes that function; the procedure is then known as gradient ascent. Gradient descent should not be confused with local search algorithms, although both are iterative methods for optimization. Gradient descent is particularly useful in machine learning and artificial intelligence for minimizing the cost or loss function. Gradient descent is generally attributed to Augustin-Louis Cauchy, who first suggested it in 1847. Jacques Hadamard independently proposed a similar method in 1907. Its convergence properties for non-linear optimization problems were first studied by Haskell Curry in 1944, with the method becoming increasingly well-studied and used in the following decades. A simple extension of gradient descent, stochastic gradient descent, serves as the most basic algorithm used for training most deep networks today.

Description

Gradient descent is based on the observation that if the multi-variable function f ( x ) {\displaystyle f(\mathbf {x} )} is defined and differentiable in a neighborhood of a point a {\displaystyle \mathbf {a} } , then f ( x ) {\displaystyle f(\mathbf {x} )} decreases fastest if one goes from a {\displaystyle \mathbf {a} } in the direction of the negative gradient of f {\displaystyle f} at a , i . e . , − ∇ f ( a ) {\displaystyle \mathbf {a} ,i.e.,-\nabla f(\mathbf {a} )} . It follows that, if

a n + 1 = a n − η ∇ f ( a n ) {\displaystyle \mathbf {a} _{n+1}=\mathbf {a} _{n}-\eta \nabla f(\mathbf {a} _{n})}

for a small enough step size or learning rate η ∈ R + {\displaystyle \eta \in \mathbb {R} _{+}} , then f ( a n ) ≥ f ( a n + 1 ) {\displaystyle f(\mathbf {a_{n}} )\geq f(\mathbf {a_{n+1}} )} . In other words, the term η ∇ f ( a ) {\displaystyle \eta \nabla f(\mathbf {a} )} is subtracted from a {\displaystyle \mathbf {a} } because we want to move against the gradient, toward the local minimum. With this observation in mind, one starts with a guess x 0 {\displaystyle \mathbf {x} _{0}} for a local minimum of f {\displaystyle f} , and considers the sequence x 0 , x 1 , x 2 , … {\displaystyle \mathbf {x} _{0},\mathbf {x} _{1},\mathbf {x} _{2},\ldots } such that

x n + 1 = x n − η n ∇ f ( x n ) , n ≥ 0. {\displaystyle \mathbf {x} _{n+1}=\mathbf {x} _{n}-\eta _{n}\nabla f(\mathbf {x} _{n}),\ n\geq 0.}

We have a monotonic sequence

f ( x 0 ) ≥ f ( x 1 ) ≥ f ( x 2 ) ≥ ⋯ , {\displaystyle f(\mathbf {x} _{0})\geq f(\mathbf {x} _{1})\geq f(\mathbf {x} _{2})\geq \cdots ,}

… excerpt ends here. Continue reading the full article.