12. Coordinate Descent and Conjugate Gradient — Coordinates and Conjugate Directions

// CORE 6/7 — coordinate descent, conjugate gradient, preconditioning

Not every algorithm uses the full gradient or Hessian at once. Coordinate descent moves one coordinate at a time, while conjugate gradient quickly solves linear systems along special directions.

Coordinate descent

Coordinate descent optimizes one coordinate or one coordinate block at a time:

$$x_i\leftarrow \arg\min_z f(x_1,\dots,x_{i-1},z,x_{i+1},\dots,x_n).$$

It is highly efficient when each coordinate subproblem is cheap to solve. It is useful for Lasso, matrix factorization, and some large-scale ML problems.

Coordinate-selection methods

Method	Description
Cyclic	Visit coordinates in a fixed order
Randomized	Select a random coordinate
Greedy	Choose the coordinate expected to reduce the objective most
Block	Update a group of coordinates together

It is fast when the coordinate axes align well with the problem structure, but may be slow when variables are strongly coupled.

Conjugate gradient

Conjugate gradient is an iterative method for solving a symmetric positive-definite linear system:

$$Ax=b.$$

It can simultaneously be viewed as minimizing the quadratic function

$$\min_x \frac{1}{2}x^\top Ax-b^\top x.$$

The gradient is $Ax-b$, and it is zero at the solution.

Conjugate directions

CG does not simply follow the gradient. It constructs directions that are mutually $A$-conjugate:

$$p_i^\top A p_j=0\quad (i\ne j).$$

As a result, the next direction does not undo what was already optimized in a previous direction. In exact arithmetic, an $n$-dimensional problem is solved within at most $n$ iterations. With actual floating-point arithmetic, errors make preconditioning important.

Preconditioning

Preconditioning transforms a difficult system into a better-conditioned system.

Original problem:

$$Ax=b.$$

With a preconditioner $M$, solve approximately the following form:

$$M^{-1}Ax=M^{-1}b.$$

The goal is to reduce the condition number of $M^{-1}A$. A good preconditioner satisfies two conditions:

1. It approximates $A$ well.
2. Solving $Mz=r$ is cheap.

When to use each method

Method	Good fit
Coordinate descent	Coordinatewise optimization is cheap and the structure separates
Conjugate gradient	Large SPD linear system; Hessian-vector products are available
Preconditioned CG	A large condition number makes CG slow

Newton-CG reduces cost on large-scale problems by approximating the Newton step with CG instead of solving it exactly.

Next: Expensive Optimization