What are the differences between the different gradient-based numerical optimization methods?

Question

I am interested in the specific differences of the following methods:

1. The conjugate gradient method (CGM) is an algorithm for the numerical solution of particular systems of linear equations.
2. The nonlinear conjugate gradient method (NLCGM) generalizes the conjugate gradient method to nonlinear optimization.
3. The gradient descent/steepest descent algorithm (GDA) is a first-order iterative optimization algorithm.
4. The stochastic gradient descent (SGD) is a stochastic approximation of the gradient descent optimization method for minimizing an objective function that is written as a sum of differentiable functions.

Why do some publications introduce the CGM as a method for the solution of systems of equations, when it would be much more intuitive to introduce it as a linear optimization algorithm, for which one can define the residual of the system as the objective function, to then portrait the solution of a linear system, reformulated as a quadratic minimization problem?

I know that the GDA can also be used to solve linear system of equations but it is rarely used, since the conjugate gradient method is one of the most popular alternatives. However, gradient descent can also be used to solve a system of nonlinear equations. But, besides conjugacy, convergence and benefits from preconditioning, are there any other differences worth mentioning?

To add some context to this question: I am trying to better understand the different first order optimization algorithms, in order to make a more efficient use of them in inversion problems/deep learning problems.

Answer 1

First, you should forget about solving linear equations for the moment -- that's a different context from optimization, and trying to consider both on equal footing will only lead to confusion. Why some people want to motivate an optimization algorithm by mentioning a linear solver is a question only they can answer, but I would just ignore that and focus on the method itself.

So we'll assume that you're trying to minimize some function $F:\mathbb{R}^n\to \mathbb{R}$, which we'll assume to be differentiable but not necessarily convex. Most methods (including first-order methods) compute a sequence $\{x^k\}_{k\in\mathbb{N}}$ hopefully converging to a minimizer (but in general only to a stationary point) by choosing $x^0$ and then

1. picking a search direction $d^k\in\mathbb{R}^n$,
2. picking a step size $\tau_k\in\mathbb{R}$,
3. setting $x^{k+1} = x^k + \tau_k d^k$,
4. and repeating until bored.

In first-order methods, only the function values $F(x^j)$ and gradients $\nabla F(x^j)$ for $j\leq k$ are used in the choice of $d^k$ (and $\tau_k$, which I'll not address here). This includes the methods you list:

• Steepest descent consists in the choice $d^k = -\nabla F(x^k)$. It's slow -- the asymptotic complexity is $F(x^k)-\min_x F(x) = \mathcal{O}(1/k)$.

• (Nonlinear) conjugate gradients choose $d^k$ as suitable linear combination of $\nabla F(x^k)$ and $\nabla F(x^{k-1})$, where the linear combination is determined by the specific choice of $\beta^k$ -- there exist several different variants in the literature (Fletcher--Reeves, Hestenes--Stiefel, Polak--Ribière, Hager--Zhang,...) with slightly different properties; see Hager, William W.; Zhang, Hongchao, A survey of nonlinear conjugate gradient methods, Pac. J. Optim. 2, No. 1, 35-58 (2006). ZBL1117.90048. (The $\alpha^k$ in NCG plays the role of the $\tau_k$.)

• In the special case that $F$ is quadratic, i.e., $F(x) = \frac12x^TAx + b^Tx + c$, it is possible to derive an optimal choice of $\beta^k$, which leads to the (classical) conjugate gradient method. Even more, one can show that this leads to the optimal method among all first-order methods (for quadratic functions), with complexity $F(x^k)-\min_x F(x) = \mathcal{O}(1/k^2)$ (see, e.g., Nesterov's book).

  (Of course, if $A$ is symmetric, minimizing $F$ is equivalent to solving $Ax=b$, so you can use CG as a linear solver as well. The same is not true for NCG, since, e.g., $F(x) = \|f(x)\|^2$ for $f$ nonlinear can have local minimizers that don't correspond to roots of $f$. Root finding and minimization are in general two completely different problems.)

  So there's indeed little reason to choose steepest descent over NCG, since the additional work is negligible (a few inner products and AXPYs) and you potentially get much better performance.

• Stochastic gradient descent for $F(x) = \sum_{i=1}^n F_i(x_i)$ consists in the choice $d^k = -\nabla F_i(x_i^k)$ for some randomly chosen $i$. Since $\nabla F(x^k) = \sum_{i=1}^k \nabla F_i(x_i^k)$, under some conditions on the step size and the random choice, after enough iterations you can consider $n$ steps as a single "averaged" steepest descent iteration. So you'd expect about the same convergence speed asymptotically as steepest descent, but the single iterations are much cheaper, and you might get where you want faster (in wall clock time).

  I've also seen (nonlinear) conjugate gradient versions of it in the literature, but I'm not sure how much you can prove about them.