Gradient

Definition (Gradient)

Let $f:{\mathbb{R}}^n\to \mathbb{R}$ be sufficiently differentiable. The Gradient at $x\in {\mathbb{R}}^n$ is defined as

$$\nabla f(x)={\left[\frac{\partial f}{\partial x_1},\dots ,\frac{\partial f}{\partial x_n}\right]}^T$$

for each component $x_i$ of $f$.

First-Order Taylor Expansion

Optimization algorithms use the following expansion to predict how the function value will change if we move a tiny amount in a certain direction (which is $\Delta x$).

$$f(x+\Delta x)=f(x)+\nabla f(x{)}^T\Delta (x)+O(||\Delta x|{|}_2^2)$$

which is essentially linear approximation but in ${\mathbb{R}}^n$.

Recall how we do linear approximation for some simple curve in ${\mathbb{R}}^2$:

$$f(x+\Delta x)=f(x)+\frac{d}{dx}[f(x)]\cdot \Delta x$$

The Taylor Expansion generalizes the tangent line into $n$ dimensions. The $O(||\Delta x|{|}_2^2)$ term is essentially the remainder of the rest of the terms of the Taylor Series. As $\Delta x\to 0$, then the $O\to 0$. In first-order optimization, we assume $\Delta x$ is so small, that $\Delta x^2$ is essentially negligible.

From the previous equation, by the Multivariate MVT¹ we get

$$\begin{array}{rl}f(x+\Delta x)& =f(x)+\nabla f(x{)}^T\Delta (x)+O(||\Delta x|{|}_2^2)\\ & =f(x)+\nabla f(x+t\Delta x{)}^T\Delta x\end{array}$$

for some $t\in (0,1)$. The last line needs some justification. Let

$$g(t)=f(x+t\Delta x)[0,1]\to \mathbb{R}$$

such that when $t=0,g(0)=f(x)$ and $t=1,g(1)=f(x+\Delta x)$. By applying MVT on this parameterized curve,

$$g(1)-g(0)=g^{\prime }(t)\cdot (1-0)$$

for some $t\in (0,1)$. But $g^{\prime }(t)$ is calculated via Chain Rule, it becomes the gradient of $f$ at that middle point.

$$g^{\prime }(t)=\nabla f(x+t\Delta x)\cdot \Delta x=\nabla f(x+t\Delta x{)}^T\Delta x$$

and by substitution,

$$f(x+\Delta x)-f(x)=\nabla f(x+t\Delta x{)}^T\Delta x$$

which is our desired result.

Maximizing Function Value via Level Sets

Suppose we wanted to maximize $f(x)$ via some tiny distance traveled $\Delta x$. In particular, we want to pick a direction for some magnitude $|\Delta x|$ such that

$$f(x+\Delta x)-f(x)>0$$

Visually, we can see that the space at which the $x+\Delta x$ provides any effort to this function is “half” of the directions we can go. Imagine in ${\mathbb{R}}^3$, a sphere of directions we can go from some arbitrary point on some curve. Half the sphere are directions that would advance our objective function.

More precisely, via the First-Order Taylor Expansion. we get

$$f(x+\Delta x)=f(x)+\nabla f(x{)}^T\Delta (x)+O(||\Delta x|{|}_2^2)$$

the second term is positive. Conversely, if we wanted to perform Gradient Descent, we want to minimize $f$, and our second term is negative.

Naive Algorithm for Gradient Ascent/Descent

With the same picture, if we pick any direction $\Delta x$, and by picking its inverse $-\Delta x$, we have a $100\%$ chance to maximize $f$ by picking the better option. Unfortunately, this has the same pitfalls as Gradient Descent. In particular, it has no “bigger picture” of the space it inhabits. So we can stuck at a local minima, skip the global minima via too large $\Delta x$, or etc.

Also known as the Three-Point Algorithm. This kind of optimization is called zero-order optimization. We only evaluate things via $f$. In other words, we do zero derivatives to determine a better direction to travel.

This algorithm can perform better than Gradient Descent.

1. If there are places with no gradient.
2. If there are many local minimas. Consider in ${\mathbb{R}}^2$ the curve $x+\sin (x)$. Gradient descent can get stuck in these wells.

Second-Order Taylor Expansion

We can further expand the First-Order Taylor Expansion.

$$\begin{array}{rl}f(x+\Delta x)& =f(x)+\nabla f(x{)}^T\Delta x+\frac{1}{2}\Delta x^T{\nabla }^{2}f(x+\xi \Delta x)\Delta x\\ & =f(x)+\nabla f(x{)}^T\Delta x+\frac{1}{2}\Delta x^T{\nabla }^{2}f(x)\Delta x+O(||\Delta x|{|}^3)\end{array}$$

Note that the term ${\nabla }^{2}f(x+\xi \Delta x)$ is known as the Hessian.

Footnotes

1. See these notes for more information about the Generalized Mean Value Theorem for multivariate real-valued functions. ↩