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

Subgradients
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 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
I Can be slow to converge
1
Outline
Today:
I Subgradients
I Examples
I Properties
I Optimality characterizations
2
Basic inequality
Recall that for convex and differentiable f ,
f (y) ≥ f (x) +∇f (x)T (y − x), ∀x , y ∈ dom(f ).
Basic inequality
recall the basic inequality for differentiable convex functions:
f(y) ≥ f(x) +∇f(x)T (y − x) ∀y ∈ dom f
(x, f(x)) [ ∇f(x)
−1
]
• the first-order approximation of f at x is a global lower bound
• ∇f(x) defines a non-vertical supporting hyperplane to epi f at (x, f(x)):[ ∇f(x)
−1
]T ([
y
t
]
−
[
x
f(x)
])
≤ 0 ∀(y, t) ∈ epi f
Subgradients 4-2
I The first-order approximation of f at x is a global lower
bound.
I ∇f defines a non-vertical supporting hyperplane to epi(f ) at
(x , f (x))(
∇f −1
)((y
t
)
−
(
x
f (x)
))
≤ 0, ∀(y , t) ∈ epi(f ).
3
Subgradients
A subgradient of a convex function f at x is any g ∈ Rn such that
f (y) ≥ f (x) + gT (y − x), ∀y ∈ dom(f ).
I Always exists (on the relative interior of dom(f ))
I If f differentiable at x , then g = ∇f (x) uniquely
I Same definition works for nonconvex f (however, subgradients
need not exist).
Subgradient
g is a subgradient of a convex function f at x ∈ dom f if
f(y) ≥ f(x) + gT (y − x) ∀y ∈ dom f
x1 x2
f(y)
f(x1) + g
T
1 (y − x1)
f(x1) + g
T
2 (y − x1)
f(x2) + g
T
3 (y − x2)
g1, g2 are subgradients at x1; g3 is a subgradient at x2
Subgradients 4-3
g1 and g2 are subgradients at x1, g3 is subgradient at x2.
4
Subgradients
A subgradient of a convex function f at x is any g ∈ Rn such that
f (y) ≥ f (x) + gT (y − x), ∀y ∈ dom(f ).
I Always exists (on the relative interior of dom(f ))
I If f differentiable at x , then g = ∇f (x) uniquely
I Same definition works for nonconvex f (however, subgradients
need not exist).
Subgradient
g is a subgradient of a convex function f at x ∈ dom f if
f(y) ≥ f(x) + gT (y − x) ∀y ∈ dom f
x1 x2
f(y)
f(x1) + g
T
1 (y − x1)
f(x1) + g
T
2 (y − x1)
f(x2) + g
T
3 (y − x2)
g1, g2 are subgradients at x1; g3 is a subgradient at x2
Subgradients 4-3
g1 and g2 are subgradients at x1, g3 is subgradient at x2. 4
Examples of subgradients
Consider f : R→ R, f (x) = |x |
Examples of subgradients
Consider f : R R,
−2 −1 0 1 2
−
0.
5
0.
0
0.
5
1.
0
1.
5
2.
0
x
f(x
)
• For x 6= 0, unique subgradient g = sign(x)
• For x = 0, subgradient g is any element of [−1, 1]
5
I For x 6= 0, unique subgradient g = sign(x)
I For x = 0, subgradient g is any element of [−1, 1].
5
Examples of subgradients
Consider f : Rn → R, f (x) = ‖x‖2Consider f : Rn → R, f(x) = ‖x‖2
x1
x2
f(x)
• For x 6= 0, unique subgradient g = x/‖x‖2
• For x = 0, subgradient g is any element of {z : ‖z‖2 ≤ 1}
6
I For x 6= 0, unique subgradient g = x‖x‖2
I For x = 0, subgradient g is any lement of {z : ‖z‖2 ≤ 1}. 6
Examples of subgradients
Consider f : Rn → R, f (x) = ‖x‖1Consider f : Rn → R, f(x) = ‖x‖1
x1
x2
f(x)
• For xi 6= 0, unique ith component gi = sign(xi)
• For xi = 0, ith component gi is any element of [−1, 1]
7
I For xi 6= 0, unique ith component gi = sign(xi )
I For xi = 0, ith component gi is any element of [−1, 1].
7
Examples of subgradients
Consider f (x) = max{f1(x), f2(x)}, for f1, f2 : Rn → R convex,
differentiable
Consider f(x) = max{f1( ), 2( ) , f r 1, f2 : Rn → R convex,
differentiable
−2 −1 0 1 2
0
5
10
15
x
f(x
)
• For f1(x) > f2(x), unique subgradient g = ∇f1(x)
• For f2(x) > f1(x), unique subgradient g = ∇f2(x)
• For f1(x) = f2(x), subgradient g is any point on line segment
between ∇f1(x) and ∇f2(x)
8
I For f1(x) > f2( ), i e s r ie t f1( )
I For f2(x) > f1(x), unique subgradient g f2(x)
I For f1(x) = f2(x), subgradient g is any point on line segment
betw en ∇f1(x) and ∇f2( ). 8
Subdifferential
Set of all subgradients of convex f is called the subdifferential:
∂f (x) = {g ∈ Rn : g is a subgradient of f at x}.
Properties:
I Nonempty for convex f at x ∈ int(domf )
I ∂f (x) is closed and convex (even for nonconvex f )
I If f is differentiable at x , then ∂f (x) = {∇f (x)}
I If ∂f (x) = {g}, then f is differentiable at x and ∇f (x) = g .
Proof: See 
lectures/subgradients.pdf
9
Subdifferential
Set of all subgradients of convex f is called the subdifferential:
∂f (x) = {g ∈ Rn : g is a subgradient of f at x}.
Properties:
I Nonempty for convex f at x ∈ int(domf )
I ∂f (x) is closed and convex (even for nonconvex f )
I If f is differentiable at x , then ∂f (x) = {∇f (x)}
I If ∂f (x) = {g}, then f is differentiable at x and ∇f (x) = g .
Proof: See 
lectures/subgradients.pdf
9
Monotonicity
Theorem
The subdifferential of a convex function f is a monotone operator
(u − v)T (x − y) ≥ 0, ∀u ∈ ∂f (x), v ∈ ∂f (y).
Chứng minh.
By definition we have
f (y) ≥ f (x) + uT (y − x) and f (x) ≥ f (y) + vT (x − y).
Combining them get shows monotonicity.
Question: Monotonicity for differentiable convex function?
(∇f (x)−∇f (y))T (x − y) ≥ 0,
which follows directly from the first order characterization of
convex functions.
10
Monotonicity
Theorem
The subdifferential of a convex function f is a monotone operator
(u − v)T (x − y) ≥ 0, ∀u ∈ ∂f (x), v ∈ ∂f (y).
Chứng minh.
By definition we have
f (y) ≥ f (x) + uT (y − x) and f (x) ≥ f (y) + vT (x − y).
Combining them get shows monotonicity.
Question: Monotonicity for differentiable convex function?
(∇f (x)−∇f (y))T (x − y) ≥ 0,
which follows directly from the first order characterization of
convex functions.
10
Monotonicity
Theorem
The subdifferential of a convex function f is a monotone operator
(u − v)T (x − y) ≥ 0, ∀u ∈ ∂f (x), v ∈ ∂f (y).
Chứng minh.
By definition we have
f (y) ≥ f (x) + uT (y − x) and f (x) ≥ f (y) + vT (x − y).
Combining them get shows monotonicity.
Question: Monotonicity for differentiable convex function?
(∇f (x)−∇f (y))T (x − y) ≥ 0,
which follows directly from the first order characterization of
convex functions.
10
Examples of non-subdifferentiable functions
The following functions are not subdifferentiable at x = 0
I f : R→ R, dom(f ) = R+
f (x) =
{
1 if x = 0
0 if x > 0.
I f : R→ R, dom(f ) = R+
f (x) = −√x .
The only supporting hyperplane to epi(f ) at (0, f (0)) is vertical.
11
Connection to convex geometry
Convex set C ⊆ Rn, consider indicator function IC : Rn → R,
IC (x) = I{x ∈ C} =
0 if x ∈ C∞ if x 6∈ C .
For x ∈ C , ∂IC (x) = NC (x), the normal cone of C at x is, recall
NC = {g ∈ Rn : gT x ≥ gT y for any y ∈ C}.
Why? By definition of subgradient g ,
IC (y) ≥ IC (x) + gT (y − x) for all y .
I For y 6∈ C , IC (y) =∞
I For y ∈ C , this means 0 ≥ gT (y − x).
12
ll
l
l
1113
Subgradient calculus
Basic rules for convex functions:
I Scaling: ∂(af ) = a · ∂f provided a > 0.
I Addition: ∂(f1 + f2) = ∂f1 + ∂f2.
I Affine composition: if g(x) = f (Ax + b), then
∂g(x) = AT∂f (Ax + b).
I Finite pointwise maximum: if f (x) = maxi=1,...m fi (x), then
∂f (x) = conv
( ⋃
i :fi (x)=f (x)
∂fi (x)
)
convex hull of union of subdifferentials of active functions at
x .
14
Subgradient calculus
I General pointwise maximum: if f (x) = maxs∈S fs(x), then
∂f (x) ⊇ cl
conv
( ⋃
s:fs(x)=f (x)
∂fs(x)
) .
Under some regularity conditions (on S , fs), we get equality.
I Norms: important special case, f (x) = ‖x‖p. Let q be such
that 1/p + 1/q = 1, then
‖x‖p = max‖z‖q≤1
zT x .
And
∂f (x) = argmax‖z‖q≤1 z
T x .
15
Why subgradients?
Subgradients are important for two reasons:
I Convex analysis: optimality characterization via subgradients,
monotonicity, relationship to duality.
I Convex optimization: if you can compute subgradients, then
you can minimize any convex function.
16
Optimality condition
Subgradient optimality condition: For any f (convex or not),
f (x∗) = min
x
f (x)⇐⇒ 0 ∈ ∂f (x∗),
i.e., x∗ is a minimizer if and only if 0 is a subgradient of f at x∗.
Why? Easy: g = 0 being a subgradient means that for all y
f (y) ≥ f (x∗) + 0T (y − x∗) = f (x∗).
Note the implication for a convex and differentiable function f
with ∂f (x) = {∇f (x)}.
17
Optimality condition
Subgradient optimality condition: For any f (convex or not),
f (x∗) = min
x
f (x)⇐⇒ 0 ∈ ∂f (x∗),
i.e., x∗ is a minimizer if and only if 0 is a subgradient of f at x∗.
Why? Easy: g = 0 being a subgradient means that for all y
f (y) ≥ f (x∗) + 0T (y − x∗) = f (x∗).
Note the implication for a convex and differentiable function f
with ∂f (x) = {∇f (x)}.
17
Derivation of first-order optimality
Example of the power of subgradients: we can use what we have
learned so far to derive the first-order optimality condition.
Theorem
For f convex and differentiable and C convex
min
x
f (x) subject to x ∈ C
is solved at x if and only if
∇f (x)T (y − x) ≥ 0 for all y ∈ C .a
aDirect proof see, e.g., 
Teaching/ORF523/S16/ORF523_S16_Lec7_gh.pdf. Proof using subgradient
next slide.
Intuitively: says that gradient increases as we move away from x .
Note that for C = Rn (unconstrained case) it reduces to ∇f = 0. 18
Derivation of first-order optimality
Chứng minh.
First recast problem as
min
x
f (x) + IC (x).
Now apply subgradient optimality: 0 ∈ ∂(f (x) + IC (x)).
Observe
0 ∈ ∂(f (x) + IC (x))⇔ 0 ∈ {∇f (x)}+NC (x)
⇔ −∇f (x) ∈ NC (x)
⇔ −∇f (x)T x ≥ −∇f (x)T y for all y ∈ C
⇔ ∇f (x)T (y − x) ≥ 0 for all y ∈ C
as desired.
Note: the condition 0 ∈ ∂f (x) +NC (x) is a fully general condition
for optimality in convex problems. But it’s not always easy to work
with (KKT conditions, later, are easier). 19
Example: lasso optimality conditions
Given y ∈ Rn,X ∈ Rn×p, lasso problem can be parametrized as
min
β
1
2
‖y − Xβ‖22 + λ ‖β‖1
where λ ≥ 0.
Subgradient optimality
0 ∈ ∂
(
1
2
‖y − Xβ‖22 + λ ‖β‖1
)
⇔ 0 ∈ −XT (y − Xβ) + λ∂ ‖β‖1
⇔ XT (y − Xβ) = λv
for some v ∈ ∂ ‖β‖1, i.e.,
vi ∈

{1} if βi > 0
{−1} if βi < 0, i = 1, . . . , p.
[−1, 1] if βi = 0
20
Example: lasso optimality conditions
Given y ∈ Rn,X ∈ Rn×p, lasso problem can be parametrized as
min
β
1
2
‖y − Xβ‖22 + λ ‖β‖1
where λ ≥ 0. Subgradient optimality
0 ∈ ∂
(
1
2
‖y − Xβ‖22 + λ ‖β‖1
)
⇔ 0 ∈ −XT (y − Xβ) + λ∂ ‖β‖1
⇔ XT (y − Xβ) = λv
for some v ∈ ∂ ‖β‖1, i.e.,
vi ∈

{1} if βi > 0
{−1} if βi < 0, i = 1, . . . , p.
[−1, 1] if βi = 0
20
Example: lasso optimality conditions
Write X1, . . . ,Xp for columns of X . Then our condition readsXTi (y − Xβ) = λ · sign(βi ) if βi 6= 0|XTi (y − Xβ)| ≤ λ if βi = 0.
Note: subgradient optimality conditions don’t lead to closed-form
expression for a lasso solution. However they do provide a way to
check lasso optimality.
They are also helpful in understanding the lasso estimator; e.g., if
|XTi (y − Xβ)| < λ, then βi = 0 (used by screening rules, later?).
21
Example: lasso optimality conditions
Write X1, . . . ,Xp for columns of X . Then our condition readsXTi (y − Xβ) = λ · sign(βi ) if βi 6= 0|XTi (y − Xβ)| ≤ λ if βi = 0.
Note: subgradient optimality conditions don’t lead to closed-form
expression for a lasso solution. However they do provide a way to
check lasso optimality.
They are also helpful in understanding the lasso estimator; e.g., if
|XTi (y − Xβ)| < λ, then βi = 0 (used by screening rules, later?).
21
Example: soft-thresholding
Simplfied lasso problem with X = I :
min
β
1
2
‖y − β‖22 + λ ‖β‖1 .
This we can solve directly using subgradient optimality. Solution is
β = Sλ(y), where Sλ is the soft-thresholding operator
[Sλ(y)]i =

yi − λ if yi > λ
0 if − λ ≤ yi ≤ λ, i = 1, . . . , n.
yi + λ if yi < −λ
Check: from last slide, subgradient optimality conditions areyi − βi = λ · sign(βi ) if βi 6= 0|yi − βi | ≤ λ if βi = 0.
22
Example: soft-thresholding
Now plug in β = Sλ(y) and check these are satisfied:
I When yi > λ, βi = yi − λ > 0, so yi − βi = λ = λ · 1.
I When yi < −λ, argument is similar.
I When |yi | ≤ λ, βi = 0, and |yi − βi | = |yi | ≤ λ.
Soft-thresholding in
one variable
Now plug in β = Sλ(y) and check these are satisfied:
• When yi > λ, βi = yi − λ > 0, so yi − βi = λ = λ · 1
• When yi < −λ, argument is similar
• When |yi| ≤ λ, βi = 0, and |yi − βi| = |yi| ≤ λ
Soft-thresholding in
one variable:
−1.0 −0.5 0.0 0.5 1.0
−
1.
0
−
0.
5
0.
0
0.
5
1.
0
21
23
Example: distance to a convex set
Recall the distance function to a closed, convex set C
dist(x ,C ) = min
y∈C
‖y − x‖2 .
This is a convex function. What are its subgradients?
Write dist(x ,C ) = ‖x − PC (x)‖2, where PC (x) is the projection of
x onto C . It turns out that when dist(x ,C ) > 0,
∂ dist(x ,C ) =
{
x − PC (x)
‖x − PC (x)‖2
}
only has one element, so in fact dist(x ,C ) is differentiable and this
is its gradient.
24
Example: distance to a convex set
Recall the distance function to a closed, convex set C
dist(x ,C ) = min
y∈C
‖y − x‖2 .
This is a convex function. What are its subgradients?
Write dist(x ,C ) = ‖x − PC (x)‖2, where PC (x) is the projection of
x onto C . It turns out that when dist(x ,C ) > 0,
∂ dist(x ,C ) =
{
x − PC (x)
‖x − PC (x)‖2
}
only has one element, so in fact dist(x ,C ) is differentiable and this
is its gradient.
24
Example: distance to a convex set
We will only show one direction, i.e., that
x − PC (x)
‖x − PC (x)‖2
∈ ∂ dist(x ,C ).
Write u = PC (x). Then by first-order optimality conditions for a
projection,
(x − u)T (y − u) ≤ 0 for all y ∈ C .
Hence
C ⊆ H = {y : (x − u)T (y − u) ≤ 0}.
Claim
dist(y ,C ) ≥ (x − u)
T (y − u)
‖x − u‖2
for all y .
Check: first, for y ∈ H, the right-hand side is ≤ 0.
25
Example: distance to a convex set
Now for y 6∈ H, we have
(x − u)T (y − u) = ‖x − u‖2 ‖y − u‖2 cos θ where θ is the angle
between x − u and y − u. Thus
(x − u)T (y − u)
‖x − u‖2
= ‖y − u‖2 cos θ = dist(y ,H) ≤ dist(y ,C )
as desired.
Using the claim, we have for any y
dist(y ,C ) ≥ (x − u)
T (y − x + x − u)
‖x − u‖2
= ‖x − u‖2 +
(
x − u
‖x − u‖2
)T
(y − x)
Hence g = (x − u)/ ‖x − u‖2 is a subgradient of dist(x ,C ) at x .
26
References and further reading
S. Boyd, Lecture notes for EE 264B, Stanford University,
Spring 2010-2011
R. T. Rockafellar (1970), Convex analysis, Chapters 23–25
L. Vandenberghe, Lecture notes for EE 236C, UCLA, Spring
2011-2012
27