Gradient Descent
Lead Author: Jordan
The method of Gradient Descent (also known as Steepest Descent) considers only the current gradient when choosing the search direction \(\mathbf{p}_k\). This method can be thought of as being memoryless as it does not utilise the history of search directions taken i.e. \(\mathbf{p}_1,...,\mathbf{p}_{k-1}\). By differentiating the quadratic loss function,
we know the minimum is achieved when \(\mathbf{A}\mathbf{x} = \mathbf{b}\). By using the negative gradient, \(\mathbf{r}(\mathbf{x}):=\mathbf{b} - \mathbf{Ax}\), we can choose a sufficiently small learning rate, \(\alpha\) for the problem to converge. By additionally defining some convergence threshold, \(\tau>0\) and the maximum number of iterations, \(K\), the gradient descent algorithm for a linear system is defined below.
\begin{algorithm}
\caption{Gradient Descent}
\begin{algorithmic}
\PROCEDURE{GradientDescent}{$\mathbf{A}, \mathbf{b}, \mathbf{x}_0, \alpha, \tau, K$}
\STATE $\mathbf{r}_0 = \mathbf{b} - \mathbf{Ax}_0$
\FOR{$k = 1$ \TO $K$}
\IF{$||\mathbf{r}_{k-1}||_2 \le \tau$}
\BREAK
\ENDIF
\STATE $\mathbf{p}_k = \mathbf{r}_{k-1}$
\STATE $\mathbf{x}_k = \mathbf{x}_{k-1} + \alpha\mathbf{p}_k$
\STATE $\mathbf{r}_k = \mathbf{b} - \mathbf{Ax}_{k}$
\ENDFOR
\RETURN $\mathbf{x}_k$
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}
An issue with the current method is that we have to choose a sufficiently small learning rate ourselves which is data dependent. Further, setting it too small results in more iterations needed before convergence and setting it too large results in our solution exploding. By the use of some Mathematics, we can determine the optimal learning rate at every iteration step.
Determining the Optimal Learning Rate
Here we determine the optimal learning rate \(\alpha_k\) by analysing the quadratic loss function:
We see that by considering the derivative, the minimisation of \(\phi\) occurs when \(\mathbf{A}\mathbf{x} = \mathbf{b}\). By considering some arbitrary \(\mathbf{y}_k\) we can write \(\phi(\mathbf{x})\) in terms of \(\mathbf{y}_k\) and a couple of other terms:
What this result shows is that regardless of the search direction \(\mathbf{p}_k\), we can choose \(\alpha_k\) to ensure the cost function \(\phi\) is being minimised by setting \(\alpha_k = \mathbf{p}_k^\text{T}\mathbf{r}_{k-1}\ /\ ||\mathbf{p}_k||_\mathbf{A}^2\). In the case of gradient descent, we set \(\mathbf{p}_k = \mathbf{r}_{k-1}\).
\begin{algorithm}
\caption{Gradient Descent with Optimal $\alpha$}
\begin{algorithmic}
\PROCEDURE{GradientDescent}{$\mathbf{A}, \mathbf{b}, \mathbf{x}_0, \tau, K$}
\STATE $\mathbf{r}_0 = \mathbf{b} - \mathbf{Ax}_0$
\FOR{$k = 1$ \TO $K$}
\IF{$||\mathbf{r}_{k-1}||_2 \le \tau$}
\BREAK
\ENDIF
\STATE $\mathbf{p}_k = \mathbf{r}_{k-1}$
\STATE $\alpha = ||\mathbf{p}_k||_2^2 / ||\mathbf{p}_k||_\mathbf{A}^2$
\STATE $\mathbf{x}_k = \mathbf{x}_{k-1} + \alpha\mathbf{p}_k$
\STATE $\mathbf{r}_k = \mathbf{b} - \mathbf{Ax}_{k}$
\ENDFOR
\RETURN $\mathbf{x}_k$
\ENDPROCEDURE
\end{algorithmic}
\end{algorithm}
Convergence
Defining the error vector as \(\mathbf{e} := \mathbf{x}^* - \mathbf{x}\), the method of gradient descent has the following convergence rate:
where \(K_2\) is the condition number in the 2-norm. This can be shown by considering \(\mathbf{x}_k(\alpha) = \mathbf{x}_{k-1} + \alpha\mathbf{r}_{k-1}\) as a function of \(\alpha\in\mathbb{R}^+\).
Expanding \(\mathbf{e}_k = \sum_{j}^M a_j\mathbf{z}_j\) w.r.t. the orthogonal basis of eigenvectors of \(\mathbf{A}\), then for some coefficients \(\{a_j\}_{j=1}^M\subset\mathbb{R}\), we obtain
where \(\lambda_j\) is the \(j\)-th eigenvalue of \(\mathbf{A}\) with \(\lambda_1 \ge \lambda_j \ge \lambda_M\).