# Understanding Conjugate Gradient Optimization methods

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.

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_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_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. Update $$x_{k+1}=x_{k}+\alpha_k p_k$$, $$\alpha_k=\frac{\left}{\left_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: