viewof gdEta = Inputs.range([0, 2], {value: 0.2, step: 0.05, label: "Learning rate η"})
viewof gdIters = Inputs.range([1, 100], {value: 20, step: 1, label: "Iterations"})
viewof gdStart0 = Inputs.range([-6, 6], {value: -5.5, step: 0.1, label: "Start x₀"})
viewof gdStart1 = Inputs.range([-6, 6], {value: 2, step: 0.1, label: "Start x₁"})Basics of Optimization
Taylor Series, Gradient, and Hessian
Let us consider a local extremum (minimum or maximum) of a function \(f: \mathbb{R}^2 \to \mathbb{R}\), \(\bm{w} = (w_1, w_2) \mapsto f(\bm{w}) = f(w_1, w_2)\). We perform a power series (Taylor) expansion around \(\bm{w} = \bm{w}^{(0)}\) and just keep the first three terms to obtain
\[ f(\bm{w}) \approx f\left(\bm{w}^{(0)}\right) + \nabla_wf\left(\bm{w}^{(0)}\right)^\top \delta \bm{w} + \frac{1}{2} \delta \bm{w}^\top \bm{H}_f(\bm{w}) \delta \bm{w}, \tag{1}\]
where the gradient of \(f\) is defined by \(\nabla_w f(\bm{w}) = \bmat{\pd{f}{w_1}(\bm{w}) & \pd{f}{w_2}(\bm{w})}^\top\), \(\delta \bm{w} = \bm{w} - \bm{w}^{(0)}\), and \(\bm{H}_f(\bm{w})\) is the Hessian matrix of second derivatives:
\[ \bm{H}_f(\bm{w}) = \bmat{ \pdd{f}{w_1}(\bm{w}) & \frac{\partial^2 f}{\partial w_1 \partial w_2}(\bm{w}) \\ \frac{\partial^2 f}{\partial w_2 \partial w_1}(\bm{w}) & \pdd{f}{w_2}(\bm{w}) }(\bm{w}). \]
If \(\bm{w}^{(0)}\) is an extremum, then \(\nabla_w f\left(\bm{w}^{(0)}\right) = \bm{0}\), so at such a point, the linear term in Equation 1 vanishes. Therefore \(\bm{w}^{(0)}\) is a local minimum if and only if the Hessian is positive definite. By the same token, it is a local maximum if and only if the Hessian is negative definite.
Gradient Descent/Ascent
For complicated functions, such as neural nets, it is difficult to solve \(\nabla_w f\left(\bm{w}^{(0)}\right) = \bm{0}\) for \(\bm{w}^{(0)}\). Instead, we start at a random point \(\bm{w}^{(1)}\) and search for where \(\nabla f = \bm{0}\). To do this, we use the first-order approximation
\[ f\left( \bm{w}^{n+1} \right) \approx f\left( \bm{w}^{n} \right) + \nabla_w f\left(\bm{w}^{(n)}\right)^\top \delta \bm{w}^{(n)}, \]
where \(\delta \bm{w}^{(n)} = \bm{w}^{(n+1)} - \bm{w}^{(n)}\). Then with \(\eta > 0\), we set \(\bm{w}^{(n+1)}\) according to
\[ \bm{w}^{(n+1)} := \bm{w}^{(n)} \mp \eta \nabla_w f\left( \bm{w}^{(n)}\right). \]
Depending on the sign on the right-hand side of this equation, this forces \(f\) to decrease or increase, respectively. Indeed, computing the change in \(f\) after one iteration, we obtain
\[ \begin{equation} \begin{split} \Delta f \triangleq f\left(\bm{w}^{(n+1)}\right) - f\left(\bm{w}^{(n)}\right) &= \nabla_w f\left( \bm{w}^{(n)} \right) \delta \bm{w}^{(n)} \\ &= \mp \eta \nabla_w f\left( \bm{w}^{(n)} \right)^\top \nabla_w f\left( \bm{w}^{(n)} \right) \\ &= \mp \eta \norm{\nabla_w f\left( \bm{w}^{(n)} \right)}{}^2 \lessgtr 0 \end{split} \end{equation} \]
Symmetric and Positive Definite Matrices
Definition 1 (Symmetric Matrix) A matrix \(\bm{Q} \in \R^{n\times n}\) is symmetric if
\[ \bm{Q}^\top = \bm{Q}. \]
The symbol for symmetric matrices of dimension \(n\) is \(\S_n\).
Definition 2 (Positive Semidefinite Matrix) A matrix \(\bm{Q} \in \S_n\) is positive semidefinite if for all \(\bm{x} \in \R^n\),
\[ \bm{x}^\top \bm{Q x} \geq 0. \]
Definition 3 (Positive Definite Matrix) A matrix \(\bm{Q} \in \S_n\) is positive definite if for all \(\bm{x} \in \R^n\) such that \(\bm{x} \neq \bm{0}\),
\[ \bm{x}^\top \bm{Q x} > 0. \]
Definition 4 (Negative (Semi)Definite Matrix) A matrix \(\bm{Q} \in \S_n\) is negative (semi)definite if its additive inverse, \(-\bm{Q}\), is positive (semi)definite.
Least Squares Identification
Given \(y(x) = \sin{x}\), \(-\pi \leq x \leq \pi\), find the parameters \(a\), \(b\), \(c\), \(d\), such that
\[ y_P(x) = a + bx + cx^s + dx^3 \]
is a “good” approximation to \(y(x) = \sin{x}\). Let
\[ \bm{x} = \bmat{x_1 = -\pi & x_2 & \cdots & x_{n-1} & x_n = \pi} \]
and
\[ \bm{y} = \sin{\bm{x}} = \bmat{\sin{x_1} = 0 & \sin{x_2} & \cdots & \sin{x_{n-1}} & \sin{x_n} = 0}. \]
Then, we want to find \(a\), \(b\), \(c\), \(d\) such that
\[ \underbrace{ \bmat{ y_1 \\ y_2 \\ \vdots \\ y_n }}_{\bm{Y}\in \R^n} = \bmat{ \sin{x_1} \\ \sin{x_2} \\ \vdots \\ \sin{x_n} } = \underbrace{\bmat{ 1 & x_1 & x_1^2 & x_1^3 \\ 1 & x_2 & x_2^2 & x_2^3 \\ \vdots & \vdots & \vdots & \vdots \\ 1 & x_n & x_n^2 & x_n^3 }}_{\bm{W} \in \R^{n \times 4}} \underbrace{\bmat{ a \\ b \\ c \\ d }}_{\bm{P} \in \R^4} \]
Let us define the error vector \(\bm{E} := \bm{Y} - \bm{WP}\) and the total error \(e: \R^n \to \R\)
\[ e(\bm{Y}) := \norm{\bm{E}}{}^2 = \bm{E}^\top \bm{E} = \bm{Y}^\top \bm{Y} - 2 \bm{P}^\top \bm{W}^\top \bm{Y} + \bm{P}^\top \bm{W}^\top\bm{W} \bm{P}. \]
The gradient of the error function is given by
\[ \nabla e(\bm{Y}) = -2 \bm{W}^\top \bm{Y} + 2 \bm{W}^\top\bm{WP} = -2\bm{W}^\top (\bm{Y} - \bm{WP}) = -2\bm{W}^\top\bm{E}. \]
Setting this equal to zero, we obtain a linear equation in \(\bm{P}\), whose solution is given by
\[ \bm{P}^* = \left( \bm{W}^\top \bm{W} \right)^{-1} \bm{W}^\top \bm{Y}. \]
Note that \(\bm{W}^\top \bm{W} \in \S_4\) is invertible if and only if \(\bm{W}\) has full rank if and only if there are at least \(4\) distinct data points in the data set \(\bm{x}\). The iterative solution to this problem is found by picking a guess at a solution, say \(\bm{P}^{(0)} = \bm{0}\), and then update it until convergence according to the first-order difference equation
\[ \begin{split} \bm{P}^{(n+1)} = \bm{P}^{(n)} - \eta \nabla e(\bm{Y}) &= \bm{P}^{(n)} + 2\eta\bm{W}^\top\left(\bm{Y} - \bm{W}\bm{P}^{(n)}\right) \\ &= \left(\bm{I} - 2\eta\bm{W}^\top \bm{W}\right)\bm{P}^{(n)} + 2\eta \bm{W}^\top\bm{Y}. \end{split} \tag{2}\]
Note\(\bm{W}^\top \bm{W}\) is positive definite if \(\bm{W}\) has full rank.
\(\bm{W}^\top \bm{W}\) is obviously symmetric. Taking an arbitrary \(\bm{x} \in \R^4\), and letting \(\bm{v} = \bm{Wx}\) we see that \[ \bm{x}^\top \left(\bm{W}^\top \bm{W}\right) \bm{x} = \bm{v}^\top \bm{v} = \norm{\bm{v}}{}^2 \geq 0. \] Finally, observe that \(\bm{v} = \bm{0}\) if and only if \(\bm{x} = \bm{0}\) since \(\bm{W}\) has full rank. \(\square\)
NoteContinuous Analogue of the Gradient Descent
This difference Equation 2 has an associated differential equation, namely
\[ \dot{\bm{P}} = -\alpha\bm{W}^\top\bm{WP} + \alpha\bm{W}^\top \bm{Y} \] with \(\alpha > 0\). Since \(\bm{W}^\top \bm{W} \succeq 0\), this is a stable linear time-invariant ordinary differential equation. Hence, its final value can be found by invoking the Final Value Theorem (FVT) from control theory. To apply that, take the Laplace transform of the ODE (with zero initial conditions) to get
\[ s \bm{P}(s) = -\alpha \bm{W}^\top \bm{W} \bm{P}(s) + \frac{\alpha \bm{W}^\top\bm{Y}}{s} \]
After some rearrangement, the FVT yields \[ \lim_{t \to \infty} \bm{P}(t) = \lim_{s \to 0} s \bm{P}(s) = \lim_{s \to 0} s \left(s\bm{I} + \alpha \bm{W}^\top \bm{W}\right)^{-1}\frac{\alpha \bm{W}^\top \bm{Y}}{s} = \left(\bm{W}^\top\bm{W}\right)^{-1}\bm{W}^\top\bm{Y}. \]
Infinitely-Many Extrema
The cost \(C(\bm{x}) = \tfrac{1}{2}\left(\cos^2 x_0 + \sin^2 x_1\right)\) has infinitely many minima. Move the sliders to see where gradient descent ends up from different starting points and learning rates. Everything runs in your browser.
NoteThe same computation in NumPy
import numpy as np
def C(x):
return 0.5 * (np.cos(x[0])**2 + np.sin(x[1])**2)
def grad_C(x):
# analytical gradient of C
return np.array([-np.cos(x[0]) * np.sin(x[0]),
np.sin(x[1]) * np.cos(x[1])])
def run_gradient_descent(x0, eta, n_iter=50):
x = np.array(x0, dtype=np.float64)
path = [x.copy()]
for _ in range(n_iter):
x = x - eta * grad_C(x)
path.append(x.copy())
return np.array(path)
path = run_gradient_descent([-5.5, 2.0], eta=0.2, n_iter=20)Least Squares: Closed-Form vs. Gradient Descent
This interactive application demonstrates Least Squares Identification as described in the provided notes. We aim to approximate \(y = \sin(x)\) using a 3rd-degree polynomial:
\[ y_P(x) = a + bx + cx^2 + dx^3 \]
We compare two methods:
- Closed Form: The analytical solution \(\bm{P}^* = \left(\bm{W}^\top \bm{W}\right)^{-1} \bm{W}^\top \bm{Y}\).
- Gradient Descent: Iteratively minimizing the squared error \(e\).
TipTaylor Series Check
The Taylor series for \(\sin(x)\) is \(x - \frac{x^3}{6} + \dots\). Therefore, we expect our coefficients to converge near: \(a=0, b=1, c=0, d=-\nicefrac{1}{6}\).
NoteThe same computation in NumPy
import numpy as np
n = 100
x_data = np.linspace(-np.pi, np.pi, n)
y_data = np.sin(x_data)
W = np.column_stack([np.ones_like(x_data), x_data, x_data**2, x_data**3])
# Closed form: P* = (W^T W)^{-1} W^T Y
P_closed = np.linalg.solve(W.T @ W, W.T @ y_data)
# Gradient descent: dE/dP = -2 W^T (Y - W P)
def run_gd_linear_regression(W, Y, learning_rate, epochs):
P = np.zeros(4)
errors = []
for _ in range(epochs):
error = Y - W @ P
P = P - learning_rate * (-2 * W.T @ error)
errors.append(np.sum(error**2))
return P, errors
P_gd, errors = run_gd_linear_regression(W, y_data, 1e-5, 100)Embedding these Jupyter Notebooks makes the website sluggish, so please download them and open locally.
