5 First-Order Methods
The previous chapter introduced the general concept of descent direction methods.
This chapter discusses a variety of algorithms that use first-order methods toselect the appropriate descent direction. First-order methods rely on gradient
information to help direct the search for a minimum, which can be obtained using
methods outlined in chapter 2.

5.1

Gradient Descent

An intuitive choice for descent direction d is the direction of steepest descent.
Following the direction of steepest descent is guaranteed to lead to improvement,
provided that the objective function is smooth, the step size is sufficiently small,and we are not already at a point where the gradient is zero.1 The direction ofsteepest descent is the direction opposite the gradient ∇ f , hence the name gradientdescent. For convenience in this chapter, we defineg( k ) = ∇ f (x( k ) )(5.1)

where x(k) is our design point at descent iteration k.
In gradient descent, we typically normalize the direction of steepest descent(see example 5.1):g( k )d( k ) = − ( k )
(5.2)
kg k
Jagged search paths result if we choose a step size that leads to the maximal
decrease in f . In fact, the next direction will always be orthogonal to the current
direction. We can show this as follows:

A point where the gradient is zerois called a stationary point.

1

70 c ha p te r 5 . fi rst-ord e r me thod s

Suppose we have f (x) = x1 x22 . The gradient is ∇ f = [ x22 , 2x1 x2 ]. For x(k) =[1, 2] we get an unnormalized direction of steepest descent d = [−4, −4],
which is normalized to d = [− √1 , − √1 ].
2

Example 5.1. Computing the gradient descent direction.

2

If we optimize the step size at each step, we haveα(k) = arg min f (x(k) + αd(k) )
α

(5.3)

The optimization above implies that the directional derivative equals zero. Using
equation (2.9), we have∇ f (x(k) + αd(k) )⊤ d(k) = 0
We knowd( k +1) = −Hence,∇ f (x(k) + αd(k) )k∇ f (x(k) + αd(k) )kd(k+1)⊤ d(k) = 0

(5.4)

(5.5)
(5.6)

which means that d(k+1) and d(k) are orthogonal.
Narrow valleys aligned with a descent direction are not an issue. When thedescent directions cross over the valley, many steps must be taken in order tomake progress along the valley’s floor as shown in figure 5.1. An implementationof gradient descent is provided by algorithm 5.1.

5.2 Conjugate Gradient
Gradient descent can perform poorly in narrow valleys. The conjugate gradientmethod overcomes this issue by borrowing inspiration from methods for optimizing quadratic functions:minimize f (x) =x

1 ⊤x Ax + b⊤ x + c
2

(5.7)

where A is symmetric and positive definite, and thus f has a unique local minimum (section 1.6.2).
© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

5 . 2. c on j u g a te g ra d i e n t 71

x2

Figure 5.1. Gradient descent can
result in zig-zagging in narrowcanyons. Here we see the effecton the Rosenbrock function (appendix B.6).

x1

abstract type DescentMethod end
struct GradientDescent <: DescentMethod
α
end
init!(M::GradientDescent, f, ∇f, x) = M
function step!(M::GradientDescent, f, ∇f, x)
α, g = M.α, ∇f(x)return x - α*gend

Algorithm 5.1. The gradient descent method, which follows the
direction of gradient descent witha fixed learning rate. The step!
function produces the next iterate
whereas the init function doesnothing.

© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

72 c ha p te r 5 . fi rst-ord e r me thod s

The mutually conjugate vectors are the basis vectors of A. They are generally notorthogonal to one another.
The successive conjugate directions are computed using gradient informationand the previous descent direction. The algorithm starts with the direction ofsteepest descent:d(1) = − g(1)
(5.9)

x2

The conjugate gradient method can optimize n-dimensional quadratic functions in n steps as shown in figure 5.2. Its directions are mutually conjugate withrespect to A:d(i)⊤ A d( j) = 0 for all i 6= j
(5.8)

3
2
1

x1

Figure 5.2. Conjugate gradientdescent converges in n steps
when applied to an n-dimensional
quadratic function.

We then use line search to find the next design point. For quadratic functions, thestep factor α can be computed exactly (example 5.2). The update is then:x(2) = x(1) + α (1) d(1)(5.10)

Suppose we want to derive the optimal step factor for a line search on aquadratic function:
minimize f (x + αd)

Example 5.2. The optimal step factor for a line search on a quadratic
function.

α

We can compute the derivative with respect to α:∂ 1∂ f (x + αd)=(x + αd)⊤ A(x + αd) + b⊤ (x + αd) + c∂α∂α 2= d⊤ A(x + αd) + d⊤ b

= d⊤ (Ax + b) + αd⊤ Ad
Setting∂ f (x+αd)= 0 results in:∂αα=−d⊤ (Ax + b)d⊤ Ad

Subsequent iterations choose d(k+1) based on the current gradient and a contribution from the previous descent direction:d( k ) = − g( k ) + β ( k ) d( k −1)(5.11)© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

5 . 2. c on j u g a te g ra d i e n t 73

for scalar parameter β. Larger values of β indicate that the previous descentdirection contributes more strongly.
We can derive the best value for β for a known A, using the fact that d(k) is
conjugate to d(k−1) :d(k)⊤ Ad(k−1) = 0(5.12)=0(5.13)⇒ −g(k) Ad(k−1) + β(k) d(k−1)⊤ Ad(k−1) = 0(5.14)⇒ β(k) =(5.15)

⇒ (−g

(k)

+β

( k ) ( k −1) ⊤

) Ad

d

( k −1)⊤(k )⊤Ad(k−1)gd(k−1)⊤ Ad(k−1)

The conjugate gradient method can be applied to nonquadratic functions as
well. Smooth, continuous functions behave like quadratic functions close to a
local minimum, and the conjugate gradient method will converge very quickly insuch regions.
Unfortunately, we do not know the value of A that best approximates f around(k)
x . Instead, several choices for β(k) tend to work well:
Fletcher-Reeves:2g(k)⊤ g(k)β(k) = (k−1)⊤ (k−1)(5.16)
gg
Polak-Ribière:3β(k) =g(k)⊤g( k ) − g( k −1)

g(k−1)⊤ g(k−1)



E. Polak and G. Ribière, “Notesur la Convergence de MéthodesdeDirections
Conjuguées,”
Revue Française d’informatique etde Recherche Opérationnelle, Série
Rouge, vol. 3, no. 1, pp. 35–43, 1969.
3(5.17)

Convergence for the Polak-Ribière method (algorithm 5.2) can be guaranteed
if we modify it to allow for automatic resets:β ← max( β, 0)

R. Fletcher and C. M. Reeves,“Function Minimization by Conjugate Gradients,” The Computer Journal, vol. 7, no. 2, pp. 149–154, 1964.
2(5.18)

Figure 5.3 shows an example search using this method.

© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

74 c ha p te r 5 . fi rst-ord e r me thod s

x2

Figure 5.3. The conjugate gradientmethod with the Polak-Ribière update. Gradient descent is shown in
gray.

x1

mutable struct ConjugateGradientDescent <: DescentMethoddgend
function init!(M::ConjugateGradientDescent, f, ∇f, x)
M.g = ∇f(x)M.d = -M.g
return M
endfunction step!(M::ConjugateGradientDescent, f, ∇f, x)
d, g = M.d, M.gg′ = ∇f(x)β = max(0, dot(g′, g′-g)/(g⋅g))d′ = -g′ + β*dx′ = line_search(f, x, d′)M.d, M.g = d′, g′return x′
end

Algorithm 5.2. The conjugate gradient method with the Polak-Ribière
update, where d is the previous
search direction and g is the previous gradient.

© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

5 . 3. mome n tu m 75

Gradient descent will take a long time to traverse a nearly flat surface as shownin figure 5.4. Allowing momentum to accumulate is one way to speed progress.
We can modify gradient descent to incorporate momentum.
The momentum update equations are:(k)

(5.19)x( k +1) = x( k ) + v( k +1)(5.20)v( k +1)

= βv

(k)

− αg

For β = 0, we recover gradient descent. Momentum can be interpreted as a ballrolling down a nearly horizontal incline. The ball naturally gathers momentum
as gravity causes it to accelerate, just as the gradient causes momentum to accumulate in this descent method. An implementation is provided in algorithm 5.3.
Momentum descent is compared to gradient descent in figure 5.5.
mutable struct Momentum <: DescentMethod
α # learning rate
β # momentum decayv # momentum
end
function init!(M::Momentum, f, ∇f, x)
M.v = zeros(length(x))
return M
endfunction step!(M::Momentum, f, ∇f, x)α, β, v, g = M.α, M.β, M.v, ∇f(x)v[:] = β*v - α*greturn x + v
end− exp(− x2 )5.3 Momentum
0

−0.5
−1
−4 −2

0
x

2

4

Figure 5.4. Regions that are nearlyflat have gradients with small magnitudes and can thus require many
iterations of gradient descent to traverse.

Algorithm 5.3. The momentum
method for accelerated descent.
The first line in step! makes
copies of the scalars α and β,
but creates a reference to the vector v. Thus, the following linev[:] = β*v - α*g modifies theoriginal momentum vector in the
struct M.

© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

76 c ha p te r 5 . fi rst-ord e r me thod s

gradient descent
momentumx2

Figure 5.5. Gradient descent andthe momentum method comparedon the Rosenbrock function withb = 100; see appendix B.6.

x1

5.4 Nesterov Momentum
One issue of momentum is that the steps do not slow down enough at the bottomof a valley and tend to overshoot the valley floor. Nesterov momentum4 modifies
the momentum algorithm to use the gradient at the projected future position:v(k+1) = βv(k) − α∇ f (x(k) + βv(k) )x( k +1) = x( k ) + v( k +1)(5.21)(5.22)

Y. Nesterov, “A Method of Solving
a Convex Programming Problem
with Convergence Rate O(1/k2 ),”Soviet Mathematics Doklady, vol. 27,
no. 2, pp. 543–547, 1983.
4

An implementation is provided by algorithm 5.4. The Nesterov momentum andmomentum descent methods are compared in figure 5.6.
mutable struct NesterovMomentum <: DescentMethod
α # learning rate
β # momentum decayv # momentum
end
function init!(M::NesterovMomentum, f, ∇f, x)
M.v = zeros(length(x))
return M
endfunction step!(M::NesterovMomentum, f, ∇f, x)α, β, v = M.α, M.β, M.v
v[:] = β*v - α*∇f(x + β*v)
return x + v
end

Algorithm 5.4. Nesterov’s momentum method of accelerated descent.

© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

5 . 5 . a d a g ra d 77

momentum
Nesterov momentum

x2

Figure 5.6. The momentum and
Nesterov momentum methods
compared on the Rosenbrockfunction with b = 100; seeappendix B.6.

x1

5.5 Adagrad
Momentum and Nesterov momentum update all components of x with the samelearning rate. The adaptive subgradient method, or Adagrad,5 adapts a learning
rate for each component of x. Adagrad dulls the influence of parameters withconsistently high gradients, thereby increasing the influence of parameters with
infrequent updates.6
The Adagrad update step is:( k +1)

xi

(k)

= xi

−

ǫ+

α
q

(k)
g
(k) i
si

(5.23)

where s(k) is a vector whose ith entry is the sum of the squares of the partials,
with respect to xi , up to time step k,
(k)

si


k 
( j) 2= ∑ gi(5.24)

5
J. Duchi, E. Hazan, and Y. Singer,“Adaptive Subgradient Methods
for Online Learning and Stochastic
Optimization,” Journal of Machine
Learning Research, vol. 12, pp. 2121–
2159, 2011.
6
Adagrad excels when the gradient is sparse. The original paper
was motivated by stochastic gradient descent, which picks a random
batch of training data for each iteration from which to compute a gradient. Many deep learning datasetsfor real-world problems produce
sparse gradients where some features occur far less frequently thanothers.

j =1

and ǫ is a small value, on the order of 1 × 10−8 , to prevent division by zero.
Adagrad is far less sensitive to the learning rate parameter α. The learning rate
parameter is typically set to a default value of 0.01. Adagrad’s primary weakness
is that the components of s are each strictly nondecreasing. The accumulated sum
causes the effective learning rate to decrease during training, often becoming
infinitesimally small before convergence. An implementation is provided byalgorithm 5.5.
© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

78 c ha p te r 5 . fi rst-ord e r me thod s

Algorithm 5.5. The Adagrad accelerated descent method.

mutable struct Adagrad <: DescentMethod
α # learning rateϵ # small values # sum of squared gradientendfunction init!(M::Adagrad, f, ∇f, x)
M.s = zeros(length(x))
return M
endfunction step!(M::Adagrad, f, ∇f, x)α, ϵ, s, g = M.α, M.ϵ, M.s, ∇f(x)s[:] += g.*g
return x - α*g ./ (sqrt.(s) .+ ϵ)
end

5.6

RMSProp

RMSProp7 extends Adagrad to avoid the effect of a monotonically decreasing
learning rate. RMSProp maintains a decaying average of squared gradients. Thisaverage is updated according to:8ŝ(k+1) = γŝ(k) + (1 − γ) g(k) ⊙ g(k)(5.25)

where the decay γ ∈ [0, 1] is typically close to 0.9.
The decaying average of past squared gradients can be substituted into RMSProp’s update equation:9( k +1)

xi

α
(k)
q
g
( k +1) i
ǫ + ŝiα(k)(k)= xi −gǫ + RMS( gi ) i
(k)

= xi

−

(5.26)(5.27)

RMSProp is unpublished andcomes from Lecture 6e of Geoff
Hinton’s Coursera class.
8
The operation a ⊙ b is theelement-wise product between
vectors a and b.
7

The denominator is similar to theroot mean square (RMS) of thegradient component. In this chapter we use RMS( x ) to refer to the
decaying root mean square of thetime series of x.
9

An implementation is provided by algorithm 5.6.

5.7 Adadelta
Adadelta10 is another method for overcoming Adagrad’s monotonically decreasing
learning rate. After independently deriving the RMSProp update, the authors
noticed that the units in the update equations for gradient descent, momentum,

10
M. D. Zeiler, “ADADELTA: An
Adaptive Learning Rate Method,”
ArXiv, no. 1212.5701, 2012.

© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

5.8. adam

79

Algorithm 5.6. The RMSProp accelerated descent method.

mutable struct RMSProp <: DescentMethod
α # learning rateγ # decay
ϵ # small values # sum of squared gradientendfunction init!(M::RMSProp, f, ∇f, x)
M.s = zeros(length(x))
return M
endfunction step!(M::RMSProp, f, ∇f, x)α, γ, ϵ, s, g = M.α, M.γ, M.ϵ, M.s, ∇f(x)s[:] = γ*s + (1-γ)*(g.*g)
return x - α*g ./ (sqrt.(s) .+ ϵ)
end

and Adagrad do not match. To fix this, they use an exponentially decaying averageof the square updates:( k +1)

xi

(k)

= xi

−

RMS(∆xi ) (k)gǫ + RMS( gi ) i(5.28)

which eliminates the learning rate parameter entirely. An implementation isprovided by algorithm 5.7.

5.8

Adam

The adaptive moment estimation method, or Adam,11 also adapts learning rates toeach parameter (algorithm 5.8). It stores both an exponentially decaying squared
gradient like RMSProp and Adadelta, but also an exponentially decaying gradient
like momentum.
Initializing the gradient and squared gradient to zero introduces a bias. A bias
correction step helps alleviate the issue.12 The equations applied during each

D. Kingma and J. Ba, “Adam: A
Method for Stochastic Optimization,” in International Conference
on Learning Representations (ICLR),
2015.

11

According to the original
paper, good default settings are
α = 0.001, γv = 0.9, γs = 0.999,
and ǫ = 1 × 10−8 .

12© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

80 c ha p te r 5 . fi rst-ord e r me thod s

Algorithm 5.7. The Adadelta accelerated descent method. The small
constant ϵ is added to the numerator as well to prevent progressfrom entirely decaying to zero andto start off the first iteration where∆x = 0.

mutable struct Adadelta <: DescentMethod
γs # gradient decay
γx # update decay
ϵ # small values # sum of squared gradientsu # sum of squared updates
endfunction init!(M::Adadelta, f, ∇f, x)
M.s = zeros(length(x))
M.u = zeros(length(x))
return M
endfunction step!(M::Adadelta, f, ∇f, x)
γs, γx, ϵ, s, u, g = M.γs, M.γx, M.ϵ, M.s, M.u, ∇f(x)s[:] = γs*s + (1-γs)*g.*g
Δx = - (sqrt.(u) .+ ϵ) ./ (sqrt.(s) .+ ϵ) .* gu[:] = γx*u + (1-γx)*Δx.*Δx
return x + Δx
end

iteration for Adam are:biased decaying momentum: v(k+1) = γv v(k) + (1 − γv )g(k)(5.29)
biased decaying sq. gradient: s(k+1) = γs s(k) + (1 − γs ) g(k) ⊙ g(k) (5.30)(5.31)

corrected decaying momentum: v̂(k+1) = v(k+1) /(1 − γvk )corrected decaying sq. gradient: ŝ( k +1)=s( k +1)/(1 − γsk )next iterate: x(k+1) = x(k) − αv̂(k+1) / ǫ +(5.32)pŝ(k+1)(5.33)

5.9 Hypergradient Descent
The accelerated descent methods are either extremely sensitive to the learning rateor go to great lengths to adapt the learning rate during execution. The learning
rate dictates how sensitive the method is to the gradient signal. A rate that is toohigh or too low often drastically affects performance.

© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

5 . 9. hy p e rg ra d i e n t d e sc e n t 81

mutable struct Adam <: DescentMethod
α # learning rate
γv # decay
γs # decay
ϵ # small value
k # step counterv # 1st moment estimates # 2nd moment estimate
endfunction init!(M::Adam, f, ∇f, x)
M.k = 0M.v = zeros(length(x))
M.s = zeros(length(x))
return M
endfunction step!(M::Adam, f, ∇f, x)
α, γv, γs, ϵ, k = M.α, M.γv, M.γs, M.ϵ, M.ks, v, g = M.s, M.v, ∇f(x)v[:] = γv*v + (1-γv)*gs[:] = γs*s + (1-γs)*g.*g
M.k = k += 1
v_hat = v ./ (1 - γv^k)s_hat = s ./ (1 - γs^k)
return x - α*v_hat ./ (sqrt.(s_hat) .+ ϵ)end

Algorithm 5.8. The Adam accelerated descent method.

© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

82 c ha p te r 5 . fi rst-ord e r me thod sHypergradient descent13 was developed with the understanding that the derivative of the learning rate should be useful for improving optimizer performance. A
hypergradient is a derivative taken with respect to a hyperparameter. Hypergradient algorithms reduce the sensitivity to the hyperparameter, allowing it to adapt
more quickly.
Hypergradient descent applies gradient descent to the learning rate of anunderlying descent method. The method requires the partial derivative of theobjective function with respect to the learning rate. For gradient descent, thispartial derivative is:∂ f (x( k +1) )( k +1) ⊤ ∂(k)(k) (k)
=
(
g
)
x
−
α
g
(k)
∂α(k)
∂α


= ( g( k +1) ) ⊤ − g( k )A. G. Baydin, R. Cornish, D. M.
Rubio, M. Schmidt, and F. Wood,“Online Learning Rate Adaptation
with Hypergradient Descent,” inInternational Conference on Learning
Representations (ICLR), 2018.
13(5.34)(5.35)

Computing the hypergradient thus requires keeping track of the last gradient.
The resulting update rule is:∂ f (x( k ) )∂α(k−1)( k −1)=α+ µ (g( k ) ) ⊤ g( k −1)

α ( k ) = α ( k −1) − µ(5.36)(5.37)

where µ is the hypergradient learning rate.
This derivation can be applied to any gradient-based descent method that follows equation (4.1). Implementations are provided for the hypergradient versionsof gradient descent (algorithm 5.9) and Nesterov momentum (algorithm 5.10).
These methods are visualized in figure 5.7.

© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

5 . 9. hy p e rg ra d i e n t d e sc e n t 83

mutable struct HyperGradientDescent <: DescentMethod
α0 # initial learning rateμ # learning rate of the learning rate
α # current learning rate
g_prev # previous gradientendfunction init!(M::HyperGradientDescent, f, ∇f, x)
M.α = M.α0
M.g_prev = zeros(length(x))
return M
endfunction step!(M::HyperGradientDescent, f, ∇f, x)
α, μ, g, g_prev = M.α, M.μ, ∇f(x), M.g_prev
α = α + μ*(g⋅g_prev)
M.g_prev, M.α = g, α
return x - α*gend

Algorithm 5.9. The hypergradient
form of gradient descent.

mutable struct HyperNesterovMomentum <: DescentMethod
α0 # initial learning rateμ # learning rate of the learning rate
β # momentum decayv # momentum
α # current learning rate
h_prev # previous gradientendfunction init!(M::HyperNesterovMomentum, f, ∇f, x)
M.α = M.α0
M.v = zeros(length(x))
M.h_prev = zeros(length(x))
return M
endfunction step!(M::HyperNesterovMomentum, f, ∇f, x)α, β, μ, v = M.α, M.β, M.μ, M.v
h, h_prev = ∇f(x + β*v), M.h_prev
α = α + μ*(h⋅h_prev)v[:] = β*v - α*hM.h_prev, M.α = h, αreturn x + v
end

Algorithm 5.10. The hypergradient
form of the Nesterov momentum
descent method.

© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

84 c ha p te r 5 . fi rst-ord e r me thod s

hypergradienthyper-Nesterov

x2

Figure 5.7. Hypergradient versions of gradient descent and Nesterov momentum compared on the
Rosenbrock function with b = 100;
see appendix B.6.

x1

5.10

Summary• Gradient descent follows the direction of steepest descent.
• The conjugate gradient method can automatically adjust to local valleys.
• Descent methods with momentum build up progress in favorable directions.
• A wide variety of accelerated descent methods use special techniques to speed
up descent.
• Hypergradient descent applies gradient descent to the learning rate of anunderlying descent method.

5.11 Exercises
Exercise 5.1. Compute the gradient of x⊤ Ax + b⊤ x when A is symmetric.
Exercise 5.2. Apply gradient descent with a unit step factor to f ( x ) = x4 from astarting point of your choice. Compute two iterations.
Exercise 5.3. Apply one step of gradient descent to f ( x ) = e x + e− x from x (1) = 10with both a unit step factor and with exact line search.
Exercise 5.4. The conjugate gradient method can also be used to find a search
direction d when a local quadratic model of a function is available at the current
point. With d as search direction, let the model beq(d) = d⊤ Hd + b⊤ d + c© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

5 . 11. e x e rc i se s 85

for a symmetric matrix H. What is the Hessian in this case? What is the gradientof q when d = 0? What can go wrong if the conjugate gradient method is applied
to the quadratic model to get the search direction d?
Exercise 5.5. How is Nesterov momentum an improvement over momentum?
Exercise 5.6. In what way is the conjugate gradient method an improvement oversteepest descent?
Exercise 5.7. In conjugate gradient descent, what is the descent direction at
the first iteration for the function f ( x, y) = x2 + xy + y2 + 5 when initializedat ( x, y) = (1, 1)? What is the resulting point after two steps of the conjugate
gradient method?
Exercise 5.8. We have a polynomial function f such that f (x) > 2 for all x inthree-dimensional Euclidean space. Suppose we are using steepest descent withstep lengths optimized at each step, and we want to find a local minimum of f .
If our unnormalized descent direction is [1, 2, 3] at step k, is it possible for ourunnormalized descent direction at step k + 1 to be [0, 0, −3]? Why or why not?

© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com