Bài giảng Tối ưu hóa nâng cao - Bài 7: Subgradient Method - Hoàng Nam Dũng

Subgradient 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
Last last time: gradient descent
Consider the problem
min
x
f (x)
for f convex and differentiable, dom(f ) = Rn.
Gradient descent: choose initial x (0) ∈ Rn, repeat:
x (k) = x (k−1) − tk · ∇f (x (k−1)), k = 1, 2, 3, . . .
Step sizes tk chosen to be fixed and small, or by backtracking line
search.
If ∇f Lipschitz, gradient descent has convergence rate O(1/ε).
Downsides:
I Requires f differentiable — addressed this lecture.
I Can be slow to converge — addressed next lecture.
1
Subgradient method
Now consider f convex, having dom(f ) = Rn, but not necessarily
differentiable.
Subgradient method: like gradient descent, but replacing gradients
with subgradients, i.e., initialize x (0), repeat:
x (k) = x (k−1) − tk · g (k−1), k = 1, 2, 3, . . .
where g (k−1) ∈ ∂f (x (k−1)) any subgradient of f at x (k−1).
Subgradient method is not necessarily a descent method, so we
keep track of best iterate x
(k)
best among x
(0), ...x (k) so far, i.e.,
f (x
(k)
best) = mini=0,...,k
f (x (i)).
2
Subgradient method
Now consider f convex, having dom(f ) = Rn, but not necessarily
differentiable.
Subgradient method: like gradient descent, but replacing gradients
with subgradients, i.e., initialize x (0), repeat:
x (k) = x (k−1) − tk · g (k−1), k = 1, 2, 3, . . .
where g (k−1) ∈ ∂f (x (k−1)) any subgradient of f at x (k−1).
Subgradient method is not necessarily a descent method, so we
keep track of best iterate x
(k)
best among x
(0), ...x (k) so far, i.e.,
f (x
(k)
best) = mini=0,...,k
f (x (i)).
2
Outline
Today:
I How to choose step sizes
I Convergence analysis
I Intersection of sets
I Projected subgradient method
3
Step size choices
I Fixed step sizes: tk = t all k = 1, 2, 3, . . .
I Fixed step length, i.e., tk = s/‖g (k−1)‖2, and hence
‖tkg (k−1)‖2 = s.
I Diminishing step sizes: choose to meet conditions
∞∑
k=1
t2k <∞,
∞∑
k=1
tk =∞,
i.e., square summable but not summable. Important here that
step sizes go to zero, but not too fast.
There are several other options too, but key difference to gradient
descent: step sizes are pre-specified, not adaptively computed.
4
Convergence analysis
Assume that f convex, dom(f ) = Rn, and also that f is Lipschitz
continuous with constant L > 0, i.e.,
|f (x)− f (y)| ≤ L ‖x − y‖2 for all x , y .
Theorem
For a fixed step size t, subgradient method satisfies
f (x
(k)
best)− f ∗ ≤
‖x (0) − x∗‖22
2kt
+
L2t
2
.
For fixed step length, i.e., tk = s/‖g (k−1)‖2, we have
f (x
(k)
best)− f ∗ ≤
L‖x (0) − x∗‖22
2ks
+
Ls
2
.
For diminishing step sizes, subgradient method satisfies
f (x
(k)
best)− f ∗ ≤
‖x (0) − x∗‖22 + L2
∑k
i=1 t
2
i
2
∑k
i=1 ti
,
i.e., lim
k→∞
f (x
(k)
best) = f
∗. 5
Lipschitz continuity
Before the proof let consider the Lipschitz continuity assumption.
Lemma
f is Lipschitz continuous with constant L > 0, i.e.,
|f (x)− f (y)| ≤ L ‖x − y‖2 for all x , y ,
is equivalent to
‖g‖2 ≤ L for all x and g ∈ ∂f (x).
Chứng minh.
⇐=: Choose subgradients gx and gy at x and y . We have
gTx (x − y) ≥ f (x)− f (y) ≥ gTy (x − y).
Apply Cauchy-Schwarz inequality get
L‖x − y‖2 ≥ f (x)− f (y) ≥ −L‖x − y‖2.
6
Lipschitz continuity
Before the proof let consider the Lipschitz continuity assumption.
Lemma
f is Lipschitz continuous with constant L > 0, i.e.,
|f (x)− f (y)| ≤ L ‖x − y‖2 for all x , y ,
is equivalent to
‖g‖2 ≤ L for all x and g ∈ ∂f (x).
Chứng minh.
=⇒: Assume ‖g‖2 > L for some g ∈ ∂f (x). Take y = x + g/‖g‖2
we have ‖y − x‖2 = 1 and
f (y) ≥ f (x) + gT (y − x) = f (x) + ‖g‖2 > f (x) + L,
contradiction.
7
Convergence analysis - Proof
Can prove both results from same basic inequality. Key steps:
I Using definition of subgradient
‖x (k) − x∗‖22 = ‖x (k−1) − tkg (k−1) − x∗‖22
= ‖x (k−1) − x∗‖22 − 2tkg (k−1)(x (k−1) − x∗) + t2k‖g (k−1)‖22
≤ ‖x (k−1) − x∗‖22 − 2tk(f (x (k−1))− f (x∗)) + t2k‖g (k−1)‖22.
I Iterating last inequality
‖x (k) − x∗‖22
≤ ‖x (0) − x∗‖22 − 2
k∑
i=1
ti (f (x
(i−1))− f (x∗)) +
k∑
i=1
t2i ‖g (i−1)‖22.
8
Convergence analysis - Proof
Can prove both results from same basic inequality. Key steps:
I Using definition of subgradient
‖x (k) − x∗‖22 = ‖x (k−1) − tkg (k−1) − x∗‖22
= ‖x (k−1) − x∗‖22 − 2tkg (k−1)(x (k−1) − x∗) + t2k‖g (k−1)‖22
≤ ‖x (k−1) − x∗‖22 − 2tk(f (x (k−1))− f (x∗)) + t2k‖g (k−1)‖22.
I Iterating last inequality
‖x (k) − x∗‖22
≤ ‖x (0) − x∗‖22 − 2
k∑
i=1
ti (f (x
(i−1))− f (x∗)) +
k∑
i=1
t2i ‖g (i−1)‖22.
8
Convergence analysis - Proof
I Using ‖x (k) − x∗‖2 ≥ 0 and letting R = ‖x (0) − x∗‖2, we have
0 ≤ R2 − 2
k∑
i=1
ti (f (x
(i−1))− f (x∗)) +
k∑
i=1
t2i ‖g (i−1)‖22.
I Introducing f (x (k)best) = mini=0,...k f (x
(i)) and rearranging, we
have the basic inequality
f (x
(k)
best)− f (x∗) ≤
R2 +
∑k
i=1 t
2
i ‖g (i−1)‖22
2
∑k
i=1 ti
.
For different step sizes choices, convergence results can be directly
obtained from this bound. E.g., theorems for fixed and diminishing
step sizes follow.
9
Convergence analysis - Proof
I Using ‖x (k) − x∗‖2 ≥ 0 and letting R = ‖x (0) − x∗‖2, we have
0 ≤ R2 − 2
k∑
i=1
ti (f (x
(i−1))− f (x∗)) +
k∑
i=1
t2i ‖g (i−1)‖22.
I Introducing f (x (k)best) = mini=0,...k f (x
(i)) and rearranging, we
have the basic inequality
f (x
(k)
best)− f (x∗) ≤
R2 +
∑k
i=1 t
2
i ‖g (i−1)‖22
2
∑k
i=1 ti
.
For different step sizes choices, convergence results can be directly
obtained from this bound. E.g., theorems for fixed and diminishing
step sizes follow.
9
Convergence analysis - Proof
I Using ‖x (k) − x∗‖2 ≥ 0 and letting R = ‖x (0) − x∗‖2, we have
0 ≤ R2 − 2
k∑
i=1
ti (f (x
(i−1))− f (x∗)) +
k∑
i=1
t2i ‖g (i−1)‖22.
I Introducing f (x (k)best) = mini=0,...k f (x
(i)) and rearranging, we
have the basic inequality
f (x
(k)
best)− f (x∗) ≤
R2 +
∑k
i=1 t
2
i ‖g (i−1)‖22
2
∑k
i=1 ti
.
For different step sizes choices, convergence results can be directly
obtained from this bound. E.g., theorems for fixed and diminishing
step sizes follow.
9
Convergence analysis - Proof
The basic inequality tells us that after k steps, we have
f (x
(k)
best)− f (x∗) ≤
R2 +
∑k
i=1 t
2
i ‖g (i−1)‖22
2
∑k
i=1 ti
.
With fixed step size t, this and the Lipschitz continuity assumption
give
f (x
(k)
best)− f ∗ ≤
R2
2kt
+
L2t
2
.
I Does not guarantee convergence (as k →∞).
I For large k , f (x (k)best) is approximately
L2t
2 -suboptimal.
I To make the gap ≤ ε, let’s make each term ≤ ε/2. So we can
choose t = ε/L2, and k = R2/t · 1/ε = R2L2/ε2.
I.e., subgradient method guarantees the gap ε in k = O(1/ε2)
iterations ... compare this to O(1/ε) rate of gradient descent.
10
Convergence analysis - Proof
The basic inequality tells us that after k steps, we have
f (x
(k)
best)− f (x∗) ≤
R2 +
∑k
i=1 t
2
i ‖g (i−1)‖22
2
∑k
i=1 ti
.
With fixed step size t, this and the Lipschitz continuity assumption
give
f (x
(k)
best)− f ∗ ≤
R2
2kt
+
L2t
2
.
I Does not guarantee convergence (as k →∞).
I For large k , f (x (k)best) is approximately
L2t
2 -suboptimal.
I To make the gap ≤ ε, let’s make each term ≤ ε/2. So we can
choose t = ε/L2, and k = R2/t · 1/ε = R2L2/ε2.
I.e., subgradient method guarantees the gap ε in k = O(1/ε2)
iterations ... compare this to O(1/ε) rate of gradient descent.
10
Convergence analysis - Proof
The basic inequality tells us that after k steps, we have
f (x
(k)
best)− f (x∗) ≤
R2 +
∑k
i=1 t
2
i ‖g (i−1)‖22
2
∑k
i=1 ti
.
With fixed step size t, this and the Lipschitz continuity assumption
give
f (x
(k)
best)− f ∗ ≤
R2
2kt
+
L2t
2
.
I Does not guarantee convergence (as k →∞).
I For large k , f (x (k)best) is approximately
L2t
2 -suboptimal.
I To make the gap ≤ ε, let’s make each term ≤ ε/2. So we can
choose t = ε/L2, and k = R2/t · 1/ε = R2L2/ε2.
I.e., subgradient method guarantees the gap ε in k = O(1/ε2)
iterations ... compare this to O(1/ε) rate of gradient descent. 10
Convergence analysis - Proof
The basic inequality tells us that after k steps, we have
f (x
(k)
best)− f (x∗) ≤
R2 +
∑k
i=1 t
2
i ‖g (i−1)‖22
2
∑k
i=1 ti
.
With fixed step length, i.e., ti = s/‖g (i−1)‖2, we have
f (x
(k)
best)−f (x∗) ≤
R2 + ks2
2s
∑k
i=1 ‖g (i−1)‖−12
≤ R
2 + ks2
2s
∑k
i=1 L
−1 =
LR2
2ks
+
Ls
2
.
I Does not guarantee convergence (as k →∞).
I For large k , f (x (k)best) is approximately
Ls
2 -suboptimal.
I To make the gap ≤ ε, let’s make each term ≤ ε/2. So we can
choose s = ε/L, and k = LR2/s · 1/ε = R2L2/ε2.
11
Convergence analysis - Proof
The basic inequality tells us that after k steps, we have
f (x
(k)
best)− f (x∗) ≤
R2 +
∑k
i=1 t
2
i ‖g (i−1)‖22
2
∑k
i=1 ti
.
With fixed step length, i.e., ti = s/‖g (i−1)‖2, we have
f (x
(k)
best)−f (x∗) ≤
R2 + ks2
2s
∑k
i=1 ‖g (i−1)‖−12
≤ R
2 + ks2
2s
∑k
i=1 L
−1 =
LR2
2ks
+
Ls
2
.
I Does not guarantee convergence (as k →∞).
I For large k , f (x (k)best) is approximately
Ls
2 -suboptimal.
I To make the gap ≤ ε, let’s make each term ≤ ε/2. So we can
choose s = ε/L, and k = LR2/s · 1/ε = R2L2/ε2.
11
Convergence analysis - Proof
The basic inequality tells us that after k steps, we have
f (x
(k)
best)− f (x∗) ≤
R2 +
∑k
i=1 t
2
i ‖g (i−1)‖22
2
∑k
i=1 ti
.
From this and the Lipschitz continuity, we have
f (x
(k)
best)− f (x∗) ≤
R2 + L2
∑k
i=1 t
2
i
2
∑k
i=1 ti
.
With diminishing step size,
∑∞
i=1 ti =∞ and
∑∞
i=1 t
2
i <∞, there
holds
lim
k→∞
f (x
(k)
best) = f
∗.
12
Example: 1-norm minimization
minimize ‖Ax− b‖1
• subgradient is given by AT sign(Ax− b)
• example with A ∈ R500×100, b ∈ R500
Fixed steplength tk = s/‖g(k−1)‖2 for s = 0.1, 0.01, 0.001
0 20 40 60 80 100
10−3
10−2
10−1
100
k
(f(x(k))− f?)/f?
0.1
0.01
0.001
0 1000 2000 3000
10−4
10−3
10−2
10−1
100
k
(fbest(x
(k))− f?)/f?
0.1
0.01
0.001
Subgradient method 5-8
Diminishing step size: tk = 0.01/
√
k and tk = 0.01/k
0 1000 2000 3000 4000 5000
10−5
10−4
10−3
10−2
10−1
100
k
(fbest(x
(k))− f?)/f?
0.01/
√
k
0.01/k
Subgradient method 5-9
Example: regularized logistic regression
Given (xi , yi ) ∈ Rp × {0, 1} for i = 1, ...n, the logistic regression
loss is
f (β) =
n∑
i=1
(
−yixTi β + log(1+ exp(xTi β))
)
.
This is a smooth and convex with
∇f (β) =
n∑
i=1
(yi − pi (β))xi ,
where pi (β) = exp(x
T
i β)/(1+ exp(x
T
i β)), i = 1, . . . , n.
Consider the regularized problem
min
β
f (β) + λ · P(β),
where P(β) = ‖β‖22 ridge penalty; or P(β) = ‖β‖1 lasso penalty.
13
Example: regularized logistic regression
Ridge: use gradients; lasso: use subgradients. Example here has
n = 1000, p = 20.
Ridge: use gradients; lasso: use subgradients. Example here has
n = 1000, p = 20:
0 50 100 150 200
1e
−1
3
1e
−1
0
1e
−0
7
1e
−0
4
1e
−0
1
Gradient descent
k
f−
fs
ta
r
t=0.001
0 50 100 150 200
0.
02
0.
05
0.
20
0.
50
2.
00
Subgradient method
k
f−
fs
ta
r
t=0.001
t=0.001/k
Step sizes hand-tuned to be favorable for each method (of course
comparison is imperfect, but it reveals the convergence behaviors)
11
Step sizes hand-tuned to be favorable for each method (of course
i i i f , i l i . 14
Polyak step sizes
Polyak step sizes: when the optimal value f ∗ is known, take
tk =
f (x (k−1))− f ∗
‖g (k−1)‖22
, k = 1, 2, 3, . . .
Can be motivated from first step in subgradient proof:
‖x (k)−x∗‖22 ≤ ‖x (k−1)−x∗‖22−2tk(f (x (k−1))−f (x∗))+t2k‖g (k−1)‖22.
Polyak step size minimizes the right-hand side.
With Polyak step sizes, can show subgradient method converges to
optimal value. Convergence rate is still O(1/ε2)
f (x
(k)
best)− f (x∗) ≤
LR√
k
.
(Proof: see slide 11, 
236C/lectures/sgmethod.pdf).
15
Example: intersection of sets
Suppose we want to find x∗ ∈ C1 ∩ · · · ∩ Cm, i.e., find a point in
intersection of closed, convex sets C1, ...,Cm.
First define
fi (x) = dist(x ,Ci ), i = 1, . . . ,m
f (x) = max
i=1,...,m
fi (x)
and now solve
min
x
f (x).
Check: is this convex?
Note that f ∗ = 0⇐⇒ x∗ ∈ C1 ∩ · · · ∩ Cm.
16
Example: intersection of sets
Recall the distance function dist(x ,C ) = miny∈C ‖y − x‖2. Last
time we computed its gradient
∇ dist(x ,C ) = x − PC (x)‖x − PC (x)‖2
where PC (x) is the projection of x onto C .
Also recall subgradient rule: if f (x) = maxi=1,...m fi (x), then
∂f (x) = conv
 ⋃
i :fi (x)=f (x)
∂fi (x)
 .
So if fi (x) = f (x) and gi ∈ ∂fi (x), then gi ∈ ∂f (x).
17
Example: intersection of sets
Put these two facts together for intersection of sets problem, with
fi (x) = dist(x ,Ci ): if Ci is farthest set from x (so fi (x) = f (x)),
and
gi = ∇fi (x) = x − PCi (x)‖x − PCi (x)‖2
then gi ∈ ∂f (x).
Now apply subgradient method, with Polyak size tk = f (x
(k−1)).
At iteration k , with Ci farthest from x
(k−1), we perform update
x (k) = x (k−1) − f (x (k−1)) x
(k−1) − PCi (x (k−1))
‖x (k−1) − PCi (x (k−1))‖
= PCi (x
(k−1)),
since
f (x (k−1)) = dist(x (k−1),Ci ) = ‖x (k−1) − PCi (x (k−1))‖.
18
Example: intersection of sets
For two sets, this is the famous alternating projections1 algorithm,
i.e., just keep projecting back and forth.
For two sets, this is the famous alternating projections algorithm1,
i.e., just keep projecting back and forth
(From Boyd’s lecture notes)
1von Neumann (1950), “Functional operators, volume II: The geometry of
orthogonal spaces”
16
1von Neumann (1950), “Functional operators, volum II: The geometry of
orthogonal spaces”
19
Projected subgradient method
To optimize a convex function f over a convex set C ,
min
x
f (x) subject to x ∈ C
we can use the projected subgradient method.
Just like the usual subgradient method, except we project onto C
at each iteration:
x (k) = PC (x
(k−1) − tk · g (k−1)), k = 1, 2, 3, . . .
Assuming we can do this projection, we get the same convergence
guarantees as the usual subgradient method, with the same step
size choices.
20
Projected subgradient method
What sets C are easy to project onto? Lots, e.g.,
I Affine images: {Ax + b : x ∈ Rn}
I Solution set of linear system: {x : Ax = b}
I Nonnegative orthant: Rn+ = {x : x ≥ 0}
I Some norm balls: {x : ‖x‖p ≤ 1} for p = 1, 2,∞
I Some simple polyhedra and simple cones.
Warning: it is easy to write down seemingly simple set C , and PC
can turn out to be very hard! E.g., generally hard to project onto
arbitrary polyhedron C = {x : Ax ≤ b}.
Note: projected gradient descent works too, more next time ...
21
Can we do better?
Upside of the subgradient method: broad applicability.
Downside: O(1/ε2) convergence rate over problem class of convex,
Lipschitz functions is really slow.
Nonsmooth first-order methods: iterative methods updating x (k) in
x (0) + span{g (0), g (1), . . . , g (k−1)}
where subgradients g (0), g (1), . . . , g (k−1) come from weak oracle.
Theorem (Nesterov)
For any k ≤ n− 1 and starting point x (0), there is a function in the
problem class such that any nonsmooth first-order method satisfies
f (x (k))− f ∗ ≥ RG
2(1+
√
k + 1)
.
22
Improving on the subgradient method
In words, we cannot do better than the O(1/ε2) rate of subgradient
method (unless we go beyond nonsmooth first-order methods).
So instead of trying to improve across the board, we will focus on
minimizing composite functions of the form
f (x) = g(x) + h(x)
where g is convex and differentiable, h is convex and nonsmooth
but “simple”.
For a lot of problems (i.e., functions h), we can recover the O(1/ε)
rate of gradient descent with a simple algorithm, having important
practical consequences.
23
References and further reading
S. Boyd, Lecture notes for EE 264B, Stanford University,
Spring 2010-2011
Y. Nesterov (1998), Introductory lectures on convex
optimization: a basic course, Chapter 3
B. Polyak (1987), Introduction to optimization, Chapter 5
L. Vandenberghe, Lecture notes for EE 236C, UCLA, Spring
2011-2012
24