7
$\begingroup$

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.

$\endgroup$
13
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ For a fair number of numerical methods for PDEs textbooks the motivation question is clearly close to the inverse of the point you make. They already have an invertible, symmetric positive definite linear system to solve, and don't want to get too distracted talking about optimisation. A classic example would be Numerical Recipes by Press et al., where the chapter ordering puts linear systems first. $\endgroup$ – origimbo May 24 '17 at 10:20
  • $\begingroup$ Of course, but there the context is explicitly about solving linear systems, not optimization as in this question. That was exactly my point: horses for courses. $\endgroup$ – Christian Clason May 24 '17 at 10:24
  • $\begingroup$ So you don't consider trust region versions to be among "most methods"? $\endgroup$ – Mark L. Stone May 25 '17 at 1:15
  • 1
    $\begingroup$ @MarkL.Stone Well, straining things a bit you could argue that they do: if you consider the trust region step as a combined choice of $\tau_k d^k$ -- notice that I didn't treat the choice of $\tau_k$ at all. (I personally think that trust region methods are a much better choice than the usual line searches.) But that's beside the point here -- I only wanted to give a framework that covers the methods the OP listed, not argue that it is the (only or best) framework for optimization. Even in that framework, the list can certainly be extended. I've edited the answer to make that clear(er). $\endgroup$ – Christian Clason May 25 '17 at 8:19
  • 1
    $\begingroup$ Steepest descent can be line search or trust region (or no search). $\endgroup$ – Mark L. Stone May 25 '17 at 13:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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