Notes on Gradient Decent

Intro:

Gradient descent is a first order optimisation algorithem used for finding for the local minimum of a real-valued function $\underset{x}{min}f(x)$ with respect to the variable $x$.

Usually the functions $f$ are multivariate i.e. functions that take multiple input variables and produce a single output, and have the form:

$$f:{\mathbb{R}}^n\to \mathbb{R}$$

where ${\mathbb{R}}^n$ denotes the $n$-dimensional real space, and the function $f$ maps an $n$-dimensional vector of real numbers to a single real number.

Examples of Multivariate Functions

1. Two Variables: $f(x,y)=x^2+y^2$ This function takes two input variables, $x$ and $y$, and produces a single output which is the sum of the squares of the inputs.

2. Three Variables: $g(x,y,z)=x\cdot y+y\cdot z+z\cdot x$ This function takes three input variables, $x$, $y$, and $z$, and produces a single output which is the sum of the products of the pairs of inputs.

The gradient at a point, points in the direction of steepest ascent ¹.

Gradient decent relies on that $f(x_0)$ decreases fasterst if we move from $x_0$ in the direction of the negative gradient $-((\mathrm{\nabla }f)(x_0){)}^{\mathrm{\top }}$. Note, we uise the transpose for the gradient, otherwise vector dimensions will not work out.

Detailed Explanation

• $\mathrm{\nabla }f$: This symbol represents the gradient of the function $f$. The gradient is a vector of partial derivatives of $f$ with respect to its input variables. If $f$ is a function of $n$ variables, $\mathrm{\nabla }f$ is a vector with $n$ components.

• $(\mathrm{\nabla }f)(x_0)$: This means that the gradient $\mathrm{\nabla }f$ is evaluated at the specific point $x_0$. The point $x_0$ is in the domain of $f$.

• $(\mathrm{\nabla }f)(x_0{)}^{\mathrm{\top }}$: The $\mathrm{\top }$ symbol denotes the transpose of the gradient vector. If the gradient $(\mathrm{\nabla }f)(x_0)$ is originally a column vector, its transpose will be a row vector, and vice versa.

• $-(\mathrm{\nabla }f)(x_0{)}^{\mathrm{\top }}$: The minus sign indicates that we are considering the negative of the transposed gradient vector evaluated at $x_0$.

Example

Consider a function $f(x,y)=x^2+y^2$.

1. Gradient Calculation: $\mathrm{\nabla }f=(\frac{\partial f}{\partial x},\frac{\partial f}{\partial y})=(2x,2y)$

2. Evaluating at $x_0=(1,1)$: $(\mathrm{\nabla }f)(1,1)=(2\cdot 1,2\cdot 1)=(2,2)$

3. Transposing the Gradient: If $(2,2)$ is a row vector, its transpose is still $(2,2)$ but often, it is considered a column vector transposed to a row vector.

4. Negative Transposed Gradient: $-(\mathrm{\nabla }f)(1,1{)}^{\mathrm{\top }}=-(2,2)$

This negative gradient is used to update the current point $x_0$ in the gradient descent method to find the function’s minimum.

If for a small step-size $\mathrm{\nabla }\ge 0$

1. Mathematics for Machine Learning, Section 5.1, https://yung-web.github.io/home/courses/mathml.html ↩