Stochastic Optimization:
First order method† ‡ Taiji Suzuki† Tokyo Institute of Technology
Graduate School of Information Science and Engineering
Department of Mathematical and Computing Sciences‡ JST, PRESTO

Intensive course @ Nagoya University

1 / 16

Outline

1First order method
Proximal gradient descent
Nesterov’s acceleration and optimal convergence

2 / 16

Outline

1

First order method
Proximal gradient descent
Nesterov’s acceleration and optimal convergence3 / 16

Regularized learning problem
Lasso:
1∑(yi − zi⊤ x)2 +nnminpx∈Ri=1∥x∥1|{z}.

regularization

4 / 16

Regularized learning problem
Lasso:
1∑(yi − zi⊤ x)2 +nn

minpx∈Ri=1∥x∥1|{z}.

regularization

General regularized learning problem:
1∑ℓ(zi , x) + ψ(x).
nnminx∈Rp

i=1Diﬃculty: Sparsity inducing regularization is usually non-smooth.

4 / 16

First order optimization

xt+1 xt

xt-1

Optimization methods that use only the function value f (x) and thefirst order gradient g ∈ ∂f (x).
Computation per iteration is light, and suited for high dimensional
problems.
Newton method is a second order method.
5 / 16

Outline

1First order method
Proximal gradient descent
Nesterov’s acceleration and optimal convergence

6 / 16

Gradient descent
Let f (x) =∑ni=1 ℓ(zi , x).

min f (x).
xSubgradient method
Diﬀerentiable f (x):xt = xt−1 − ηt ∇f (xt−1 ).

7 / 16

Gradient descent
Let f (x) =∑ni=1 ℓ(zi , x).

min f (x).
xSubgradient method
Subdiﬀerentiable f (x):gt ∈ ∂f (xt−1 ),xt = xt−1 − ηt gt .

7 / 16

Gradient descent
Let f (x) =∑ni=1 ℓ(zi , x).

min f (x).
xSubgradient method (equivalent formula)
Subdiﬀerentiable f (x):{}12
xt = argmin ⟨x, gt ⟩ +∥x − xt−1 ∥ ,2ηtx
where gt ∈ ∂f (xt−1 ).
Proximal point algorithm:{}
1xt = argmin f (x) +∥x − xt−1 ∥2 .
2ηtxf (xt ) → optimum for any convex f and ηt = η > 0 (?).
()t−1
11∥x0 − x ∗ ∥2 .
If f (x) is strongly convex: f (xt ) − f (x ∗ ) ≤ 2η1+ση
7 / 16

Proximal gradient descent
Let f (x) =∑ni=1 ℓ(zi , x).

min f (x) + ψ(x).
x

Proximal gradient descent{}
12xt = argmin ⟨x, gt ⟩ + ψ(x) +∥x − xt−1 ∥2ηtx{}
1= argmin ηt ψ(x) + ∥x − (xt−1 − ηt gt )∥22x

where gt ∈ ∂f (xt−1 ).
The update rule is given by proximal mapping:{}
12prox(q|ψ̃) = argmin ψ̃(x) + ∥x − q∥2x
→ By using the proximal mapping, we can avoid bad properties (e.g.,non-smoothness) of ψ.

8 / 16Example
L1 regularization: ψ(x) = C ∥x∥1 .
xt,j = STC ηt (xt−1,j − ηt gt,j )(j-th component)

whereSTC (q) = sign(q) max{|q| − C , 0}.
→ Unimportant elements are forced to be 0.

For many practically used regularizations, analytic form is obtained.
9 / 16

Example of proximal mapping (cont.)∑Trace norm: ψ(X ) = C ∥X ∥tr = C j σj (X ) (sum of singular values).
Let
Xt−1 − ηt Gt = U diag(σ1 , . . . , σd )V ,thenXt = U 

STC ηt (σ1 )..

.


V.
STC η (σd )10 / 16

Convergence of proximal gradient descent
Strong convexity and smoothness of f determines the convergence rate.
xt = prox(xt−1 − ηt gt |ηt ψ(x)).
property of f
γ-SmoothNon-smoothµ-Strongly)( convexµexp −tγ1µt

non-strongly convγt
1√t

The step size ηt should be appropriately chosen.
Setting of ηt
SmoothNon-smooth

Strongly conv

non-strongly conv

1γ
2µt

1γ
1
√t

To achieve this convergence rate, we need to take an average of {xt }tappropriately; Polyak-Ruppert averaging, polynomially decaying averaging.
11 / 16Convergence of proximal gradient descent
Strong convexity and smoothness of f determines the convergence rate.
xt = prox(xt−1 − ηt gt |ηt ψ(x)).
property of fγ-SmoothNon-smoothµ-Strongly
convex( √)µexp −tγ
1µt

non-strongly conv
γt2
1
√t

The step size ηt should be appropriately chosen.
Setting of ηt
SmoothNon-smooth

Strongly conv

non-strongly conv

1γ
2µt

1γ
1√t

To achieve this convergence rate, we need to take an average of {xt }tappropriately; Polyak-Ruppert averaging, polynomially decaying averaging.
Convergence for smooth loss can be improved by Nesterov’sacceleration.
→ Optimal rate

11 / 16

Outline

1First order method
Proximal gradient descent
Nesterov’s acceleration and optimal convergence

12 / 16

Nesterov’s acceleration (non-strongly convex)
minx {f (x) + ψ(x)}Assumption: f (x) is γ-smooth.

Nesterov’s acceleration scheme
Let s1 = 1 and η = γ1 , and iterate the following for t = 1, 2, . . .
123Let gt ∈ ∂f (yt ), and update xt = prox(yt − ηgt |ηψ).
√1+ 1+4st2
Set st+1 =.
2()−1
Update yt+1 = xt + sstt+1(xt − xt−1 ).

If f is γ-smooth, thenf (xt ) − f (x ∗ ) ≤2γ∥xt − x ∗ ∥.
t2

This is also called Fast Iterative Shrinkage Thresholding Algorithm (FISTA)(?).
The step size η = 1/γ can be adaptively determined: back-tracking.
“Momentum” method is important for deep learning (?).

13 / 16

Nesterov’s acceleration (strongly convex)
minx {f (x) + ψ(x)}Assumption: f (x) is γ-smooth and µ-strongly convex. (it must be γ > µ)

Nesterov’s acceleration scheme
Let A1 = 1, α1 = γ/µ and η = γ1 , and iterate the following fort = 1, 2, . . .
123Let gt ∈ ∂f (yt ), and update

xt = prox(yt − ηgt |ηψ).

2
Set αt+1 > 1 so that (γ − µ)αt+1− (2γ + At )αt+1 + γ = 0, and let
At+1 = At /αt+1 .
()tUpdate yt+1 = xt + (γ−µ)(αµ+A(xt − xt−1 ).
t+1 −1)(αt −1)

If f is γ-smooth and µ-strongly convex, then(√ )tγ∗f (xt ) − f (x ) ≤ γ 1 −∥x0 − x ∗ ∥2 .
µ14 / 16

15 / 16

104

NormalNesterov
2Relative objective (f(xt ) - f * )10100

10-2-41010-6-8

100

20

40

60

80

100

120

Iteration

Nesterov’s acceleration v.s. normal gradient descent
Lasso: n = 8, 000, p = 500.

16 / 16

A. Beck and M. Teboulle. A fast iterative shrinkage-thresholding algorithm
for linear inverse problems. SIAM journal on imaging sciences, 2(1):183–202, 2009.
O. Güler. On the convergence of the proximal point algorithm for convex
minimization. SIAM Journal on Control and Optimization, 29(2):403–419, 1991.
I. Sutskever, J. Martens, G. Dahl, and G. Hinton. On the importance ofinitialization and momentum in deep learning. In Proceedings of the30th international conference on machine learning (ICML-13), pages
1139–1147, 2013.

16 / 16