Bài giảng Tối ưu hóa nâng cao - Bài 10: Newton’s Method - Hoàng Nam Dũng

Newton’s Method
Hoàng Nam Dũng
Khoa Toán - Cơ - Tin học, Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội
Newton-Raphson method
scribes/lec9.pdf
Newton’sMethodProof.html
newton-type-methods.pdf
Annimation:
Animations/RootFinding/NewtonMethod/NewtonMethod.html
1
Newton’s method
Given unconstrained, smooth convex optimization
min
x
f (x),
where f is convex, twice differentable, and dom(f ) = Rn. Recall
that gradient descent chooses initial x (0) ∈ Rn, and repeats
x (k) = x (k−1) − tk · ∇f (x (k−1)), k = 1, 2, 3, . . .
In comparison, Newton’s method repeats
x (k) = x (k−1) −
(
∇2f (x (k−1))
)−1∇f (x (k−1)), k = 1, 2, 3, . . .
Here ∇2f (x (k−1)) is the Hessian matrix of f at x (k−1).
2
Newton’s method interpretation
Recall the motivation for gradient descent step at x : we minimize
the quadratic approximation
f (y) ≈ f (x) +∇f (x)T (y − x) + 1
2t
‖y − x‖22,
over y , and this yields the update x+ = x − t∇f (x).
Newton’s method uses in a sense a better quadratic approximation
f (y) ≈ f (x) +∇f (x)T (y − x) + 1
2
(y − x)T∇2f (x)(y − x),
and minimizes over y to yield x+ = x − (∇2f (x))−1∇f (x).
3
Newton’s method
Consider minimizing f (x) = (10x21 + x
2
2 )/2+ 5 log(1+ e
−x1−x2)
We compare gradient de-
scent (black) to Newton’s
method (blue), where
both take steps of roughly
same length
Consider minimizing f(x) = (10x21 + x
2
2)/2 + 5 log(1 + e
−x1−x2)
(this must be a nonquadratic ... why?)
We compare gradient de-
scent (black) to Newton’s
method (blue), where both
take steps of roughly same
length
−20 −10 0 10 20
−
20
−
10
0
10
20 llllllllllllllllllllllllllllll
l
l
l
lll
5
4
Linearized optimality condition
Aternative interpretation of Newton step at x : we seek a direction
v so that ∇f (x + v) = 0. Let F (x) = ∇f (x). Consider linearizing
F around x , via approximation F (y) ≈ F (x) + DF (x)(y − x), i.e.,
0 = ∇f (x + v) ≈ ∇f (x) +∇2f (x)v .
Solving for v yields v = −(∇2f (x))−1∇f (x).
Linearized optimality condition
Aternative interpretation of Newton step at x: we seek a direction
v so that ∇f(x+ v) = 0. Let F (x) = ∇f(x). Consider linearizing
F around x, via approximation F (y) ≈ F (x) +DF (x)(y − x), i.e.,
0 = ∇f(x+ v) ≈ ∇f(x) +∇2f(x)v
l i f r i l )) 1 (x)
486 9 Unconstrained minimization
f ′
f̂ ′
(x, f ′(x))
(x+∆xnt, f
′(x+∆xnt))
Figure 9.18 The solid curve is the derivative f ′ of the function f shown in
figure 9.16. f̂ ′ is the linear approximation of f ′ at x. The Newton step ∆xnt
is the difference between the root of f̂ ′ and the point x.
the zero-crossing of the derivative f ′, which is monotonically increasing since f is
convex. Given our current approximation x of the solution, we form a first-order
Taylor approximation of f ′ at x. The zero-crossing of this affine approximation is
then x+∆xnt. This interpretation is illustrated in figure 9.18.
Affine invariance of the Newton step
An important feature of the Newton step is that it is independent of linear (or
affine) changes of coordinates. Suppose T ∈ Rn×n is nonsingular, and define
f¯(y) = f(Ty). Then we have
∇f¯(y) = TT∇f(x), ∇2f¯(y) = TT∇2f(x)T,
where x = Ty. The Newton step for f¯ at y is therefore
∆ynt = −
(
TT∇2f(x)T )−1 (TT∇f(x))
= −T−1∇2f(x)−1∇f(x)
= T−1∆xnt,
where ∆xnt is the Newton step for f at x. Hence the Newton steps of f and f¯ are
related by the same linear transformation, and
x+∆xnt = T (y +∆ynt).
The Newton decrement
The quantity
λ(x) =
(∇f(x)T∇2f(x)−1∇f(x))1/2
is called the Newton decrement at x. We will see that the Newton decrement
plays an important role in the analysis of Newton’s method, and is also useful
(From B & V page 486)
History: work of Newton (1685)
and Raphson (1690) originally fo-
cused on finding roots of poly-
nomials. Simpson (1740) ap-
plied this idea to general nonlin-
ear equations, and minimization
by setting the gradient to zero
7
From B & V page 486
History: work of Newton (1685)
and Raphson (1690) originally
focused on finding roots of
polynomials. Simpson (1740)
applied this idea to general
nonlinear equations, and
minimization by setting the
gradient to zero.
5
Affine invariance of Newton’s method
Important property Newton’s method: affine invariance. Given f ,
nonsingular A ∈ Rn×n. Let x = Ay , and g(y) = f (Ay). Newton
steps on g are
y+ = y − (∇2g(y))−1∇g(y)
= y − (AT∇2f (Ay)A)−1AT∇f (Ay)
= y − A−1(∇2f (Ay))−1∇f (Ay)
Hence
Ay+ = Ay − (∇2f (Ay))−1∇f (Ay),
i.e.,
x+ = x − (∇2f (x))−1f (x).
So progress is independent of problem scaling; recall that this is
not true of gradient descent.
6
Newton decrement
At a point x , we define the Newton decrement as
λ(x) =
(
∇f (x)T (∇2f (x))−1∇f (x)
)1/2
.
This relates to the difference between f (x) and the minimum of its
quadratic approximation:
f (x)−min
y
(
f (x) +∇f (x)T (y − x) + 1
2
(y − x)T∇2f (x)(y − x)
)
= f (x)−
(
f (x)− 1
2
∇f (x)T (∇2f (x))−1∇f (x)
)
=
1
2
λ(x)2.
Therefore can think of λ2(x)/2 as an approximate upper bound on
the suboptimality gap f (x)− f ∗.
7
Newton decrement
Another interpretation of Newton decrement: if Newton direction
is v = −(∇2f (x))−1∇f (x), then
λ(x) = (vT∇2f (x)v)1/2 = ‖v‖∇2f (x),
i.e., λ(x) is the length of the Newton step in the norm defined by
the Hessian ∇2f (x).
Note that the Newton decrement, like the Newton steps, are affine
invariant; i.e., if we defined g(y) = f (Ay) for nonsingular A, then
λg (y) would match λf (x) at x = Ay .
8
Backtracking line search
So far what we’ve seen is called pure Newton’s method. This need
not converge. In practice, we use damped Newton’s method (i.e.,
Newton’s method), which repeats
x+ = x − t(∇2f (x))−1∇f (x).
Note that the pure method uses t = 1.
Step sizes here typically are chosen by backtracking search, with
parameters 0 ≤ α ≤ 1/2, 0 < β < 1. At each iteration, we start
with t = 1 and while
f (x + tv) > f (x) + αt∇f (x)T v ,
we shrink t = βt, else we perform the Newton update. Note that
here v = −(∇2f (x))−1∇f (x), so ∇f (x)T v = −λ2(x).
9
Example: logistic regression
Logistic regression example, with n = 500, p = 100: we compare
gradient descent and Newton’s method, both with backtracking
Example: logistic regression
Logistic regression example, with n = 500, p = 100: we compare
gradient descent and Newton’s method, both with backtracking
0 10 20 30 40 50 60 70
1e
−1
3
1e
−0
9
1e
−0
5
1e
−0
1
1e
+0
3
k
f−
fs
ta
r
Gradient descent
Newton's method
Newton’s method: in a totally different regime of convergence...!
12
Newton’s method: in a totall ifferent regime of converg nce...!
10
Convergence analysis
Assume that f convex, twice differentiable, having dom(f ) = Rn,
and additionally
I ∇f is Lipschitz with parameter L.
I f is strongly convex with parameter m.
I ∇2f is Lipschitz with parameter M.
Theorem
Newton’s method with backtracking line search satisfies the
following two-stage convergence bounds
f (x (k))− f ∗ ≤
(f (x (0))− f ∗)− γk if k ≤ k02m3
M2
(
1
2
)2k−k0+1
if k > k0.
Here γ = αβ2η2m/L2, η = min{1, 3(1− 2α)}m2/M, and k0 is the
number of steps until ‖∇f (x (k0+1))‖2 < η. 11
Convergence analysis
In more detail, convergence analysis reveals γ > 0, 0 < η ≤ m2/M
such that convergence follows two stages
I Damped phase: ‖∇f (x (k))‖2 ≥ η, and
f (x (k+1))− f (x (k)) ≤ −γ.
I Pure phase: ‖∇f (x (k))‖ < η, backtracking selects t = 1, and
M
2m2
‖∇f (x (k+1))‖2 ≤
(
M
2m2
‖∇f (x (k))‖2
)2
.
Note that once we enter pure phase, we won’t leave, because
2m2
M
(
M
2m2
η
)2
≤ η
when η ≤ m2/M.
12
Convergence analysis
Unraveling this result, what does it say? To get f (x (k))− f ∗ ≤ ε,
we need at most
f (x (0))− f ∗
γ
+ log log(ε0/ε, )
iterations, where ε0 = 2m
3/M2.
I This is called quadratic convergence. Compare this to linear
convergence (which, recall, is what gradient descent achieves
under strong convexity).
I The above result is a local convergence rate, i.e., we are only
guaranteed quadratic convergence after some number of steps
k0, where k0 ≤ f (x
(0))−f ∗
γ .
I Somewhat bothersome may be the fact that the above bound
depends on L,m,M, and yet the algorithm itself does not ...
13
Self-concordance
A scale-free analysis is possible for self-concordant functions: on R,
a convex function f is called self-concordant if
|f ′′′(x)| ≤ 2f ′′(x)3/2 for all x ,
and on Rn is called self-concordant if its projection onto every line
segment is so.
Theorem (Nesterov and Nemirovskii)
Newton’s method with backtracking line search requires at most
C (α, β)(f (x (0))− f ∗) + log log(1/ε),
iterations to reach f (x (k))− f ∗, where C (α, β) is a constant that
only depends on α, β.
14
Self-concordance
What kind of functions are self-concordant?
I f (x) = −∑ni=1 log(xi ) on Rn++.
I f (X ) = − log(det(X )) on Sn++.
I If g is self-concordant, then so is f (x) = g(Ax + b).
I In the definition of self-concordance, we can replace factor of
2 by a general κ > 0.
I If g is κ-self-concordant, then we can rescale: f (x) = κ4g(x) is
self-concordant (2-self-concordant).
15
Comparison to first-order methods
At a high-level:
I Memory: each iteration of Newton’s method requires O(n2)
storage (n × n Hessian); each gradient iteration requires O(n)
storage (n-dimensional gradient).
I Computation: each Newton iteration requires O(n3) flops
(solving a dense n × n linear system); each gradient iteration
requires O(n) flops (scaling/adding n-dimensional vectors).
I Backtracking: backtracking line search has roughly the same
cost, both use O(n) flops per inner backtracking step.
I Conditioning: Newton’s method is not affected by a problem’s
conditioning, but gradient descent can seriously degrade.
I Fragility: Newton’s method may be empirically more sensitive
to bugs/numerical errors, gradient descent is more robust.
16
Newton method vs. gradient descent
Back to logistic regression example: now x-axis is parametrized in
terms of time taken per iteration
Back to logistic regression example: now x-axis is parametrized in
ter s of ti e taken per iteration
0.00 0.05 0.10 0.15 0.20 0.25
1e
−1
3
1e
−0
9
1e
−0
5
1e
−0
1
1e
+0
3
Time
f−
fs
ta
r
Gradient descent
Newton's method
Each gradient descent step is O(p), but each Newton step is O(p3)
19
Each gradient descent step is O(p), but each Newton step is
O(p3).
17
Sparse, structured problems
When the inner linear systems (in Hessian) can be solved efficiently
and reliably, Newton’s method can strive.
E.g., if ∇2f (x) is sparse and structured for all x, say banded, then
both memory and computation are O(n) with Newton iterations.
What functions admit a structured Hessian? Two examples:
I If g(β) = f (Xβ), then ∇2g(β) = XT∇2f (Xβ)X . Hence if X
is a structured predictor matrix and ∇2f is diagonal, then
∇2g is structured.
I If we seek to minimize f (β) + g(Dβ), where ∇2f is diagonal,
g is not smooth, and D is a structured penalty matrix, then
the Lagrange dual function is −f ∗(−DTu)− g∗(−u). Often
−D∇2f ∗(−DTu)DT can be structured.
18
Quasi-Newton methods
If the Hessian is too expensive (or singular), then a quasi-Newton
method can be used to approximate ∇2f (x) with H  0, and we
update according to
x+ = x − tH−1∇f (x).
I Approximate Hessian H is recomputed at each step. Goal is to
make H−1 cheap to apply (possibly, cheap storage too).
I Convergence is fast: superlinear, but not the same as Newton.
Roughly n steps of quasi-Newton make same progress as one
Newton step.
I Very wide variety of quasi-Newton methods; common theme is
to “propogate” computation of H across iterations.
19
Quasi-Newton methods
Davidon-Fletcher-Powell or DFP:
I Update H,H−1 via rank 2 updates from previous iterations;
cost is O(n2) for these updates.
I Since it is being stored, applying H−1 is simply O(n2) flops.
I Can be motivated by Taylor series expansion.
Broyden-Fletcher-Goldfarb-Shanno or BFGS:
I Came after DFP, but BFGS is now much more widely used.
I Again, updates H,H−1 via rank 2 updates, but does so in a
“dual” fashion to DFP; cost is still O(n2).
I Also has a limited-memory version, L-BFGS: instead of letting
updates propogate over all iterations, only keeps updates from
last m iterations; storage is now O(mn) instead of O(n2).
20
References and further reading
S. Boyd and L. Vandenberghe (2004), Convex optimization,
Chapters 9 and 10
Y. Nesterov (1998), Introductory lectures on convex
optimization: a basic course, Chapter 2
Y. Nesterov and A. Nemirovskii (1994), Interior-point
polynomial methods in convex programming, Chapter 2
J. Nocedal and S. Wright (2006), Numerical optimization,
Chapters 6 and 7
L. Vandenberghe, Lecture notes for EE 236C, UCLA, Spring
2011-2012
21