0
$\begingroup$

As a beginner in ML, I find it hard to understand how Conjugate Gradient Optimization methods work. The sources I've looked up online have a very complicated explanation.

Can someone explain in a simple way the gist of Conjugate Gradient methods? In short, I want to know how these methods iterate & improve upon the parameter values. I understand the working of Gradient Descent very well & it would be helpful if the logic behind CG is explained in comparison to GD.

Thank You.

$\endgroup$

1 Answer 1

2
$\begingroup$

The important thing to understand is the fact that given an equation to solve $Ax=b$ and using the fact that $A$ is positive-definite and symmetric one can derive an inner product space from $A$ (one can generalize for other matrices).

That is, $\left<u,v\right>_A = u^TAv$. Then if this inner product is zero for certain vectors $u,v$ then we can say these are orthogonal (with respect to the inner product derived from $A$).

Orthogonality is an important property to have, since then the orthogonal vectors can be used to span the set of solutions and thus a solution $x_*$ of $Ax_*=b$ can be expanded in terms of these vectors which then become easy to compute (directly or iteratively).

That is:

Assume we have a set of orthogonal (conjugate) vectors $p_k$ which span the set of solutions, ie $\{p_0,p_1,..,p_{n-1}\}$, where $\left<p_i,p_j\right>_A=0$ for $i \ne j$.

$$x_*=\sum _{i}\alpha _{i}p_i \Rightarrow A x_*=\sum _{i}\alpha_i A p_i$$

Left-multiplying by $p_k^T$ yields

$$p_k^T b =p_k^T A x_*=\sum _{i} \alpha_i p_k^T A p_i=\sum _{i} \alpha_i \left\langle p_k,p_i\right\rangle_{A}=\alpha_k\left\langle p_k, p_k\right\rangle_{A}$$

and so

$$\alpha_k={\frac {\langle p_k,b \rangle }{\langle p_k,p_k\rangle_{A}}}$$

and we have our solution in terms of this expansion.

The above can also be approximated iteratively as:

  1. Choose initial guess $x_0$ (without loss of generality $x_0=0$), compute first vector $p_0=b-Ax_0$, the other conjugate vectors must necessarily be orthogonal to this one (eg use orthogonalization algorithm).
  2. Let $r_k = b-Ax_k$ be the residual at the kth step. Then using orthogonalization we can compute the kth vector at the kth step as $p_k=r_k-\sum_{i<k}{\frac {p_i^T A r_k}{p_i^T A p_i}} p_i$. Update $x_{k+1}=x_{k}+\alpha_k p_k$, $\alpha_k=\frac{\left<p_k,r_k\right>}{\left<p_k,p_k\right>_A}$
  3. Finally after $n$ (size of $A$) steps we have $x_*=\sum _{i}\alpha _{i}p_i$ for $p_i$ and $\alpha_i$ as above.

The trick here is that we can, by definition, use the orthogonalization algorithm to derive the vectors one by one at a certain iteration step.

One advantage of this method is its fast convergence relative to gradient descent for example (theoretically it can converge in at most $n$ steps, where $n$ is the size of $A$).

On the other hand, a gradient descent method for solving $Ax=b$ would proceed as follows:

  1. Choose initial guess $x_0$ (without loss of generality $x_0=0$).
  2. At kth step update $x_k = x_{k-1} + \lambda \Delta_k$ (where $\Delta_k=b-Ax_{k-1}$ is the estimation of the gradient at kth step)
  3. Repeat until convergence.

References:

  1. Conjugate gradient method
  2. Gradient Descent
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.