Tag Info

Gradient descent is a first-order iterative optimization algorithm. To find a local minimum of a function using gradient descent, one takes steps proportional to the negative of the gradient (or of the approximate gradient) of the function at the current point. For stochastic gradient descent there is also the [sgd] tag.

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

$$\mathbf {b} =\mathbf {a} -\gamma \nabla F(\mathbf {a} )$$

for $\gamma$ small enough, then $F(\mathbf {a} )\geq F(\mathbf {b} > )$. In other words, the term $\gamma \nabla F(\mathbf > {a} )$ is subtracted from $\mathbf {a}$ because we want to move against the gradient, namely down toward the minimum. With this observation in mind, one starts with a guess $\mathbf {x} _{0}$ for a local minimum of $F$, and considers the sequence $\mathbf {x} > _{0},\mathbf {x} _{1},\mathbf {x} _{2},\dots$ such that

$$\mathbf {x} _{n+1}=\mathbf {x} _{n}-\gamma _{n}\nabla F(\mathbf {x} > _{n}),\ n\geq 0$$

We have

$$F(\mathbf {x} _{0})\geq F(\mathbf {x} _{1})\geq F(\mathbf {x} > _{2})\geq \cdots$$

so hopefully the sequence $\mathbf {x} _{n}$ converges to the desired local minimum.