Stochastic Optimization
Part I: Convex analysis andonline stochastic optimization† Taiji Suzuki† Tokyo Institute of Technology
Graduate School of Information Science and Engineering
Department of Mathematical and Computing Sciences

MLSS2015@Kyoto

1 / 73

Outline
1

Introduction

2

Short course to convex analysis
Convexity and related concepts
Duality
Smoothness and strong convexity

3

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

Online stochastic optimization
Stochastic gradient descent
Stochastic regularized dual averaging

2 / 73

Lecture plan
Part I: introduction to stochastic optimization
Convex analysis
First order method“Online” stochastic optimization method: SGD, SRDA

Part II: faster stochastic gradient methods and “batch” methods
AdaGrad, acceleration of SGD“Batch” stochastic optimization method: SDCA, SVRG, SAG

Part III: stochastic ADMM and distributed optimization
Stochastic ADMM for structured sparsity
Distributed optimization (very shortly)3 / 73

Outline
1

Introduction

2

Short course to convex analysis
Convexity and related concepts
Duality
Smoothness and strong convexity

3

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

Online stochastic optimization
Stochastic gradient descent
Stochastic regularized dual averaging

4 / 73

Machine learning as optimization
Machine learning is a methodology to deal with a lot of uncertain data.

Generalization error minimization

min EZ [ℓθ (Z )]θ∈Θ1∑ℓθ (zi )θ∈Θ nn

Empirical approximation

min

i=1

Stochastic optimization is an intersection of learning and optimization.
5 / 73

Massive data
New data input....

x1x2x3x4

Recently stochastic optimization is used to treat huge data.
n1∑ℓθ (zi ) +ψ(θ)
ni=1| {z }Huge

How to optimize this in eﬃcient way?
Do we need to go through the whole data at every iteration?

6 / 73

History of stochastic optimization for ML
1951

Robbins and Monro

Stochastic approximation
for root finding problem

1957

Rosenblatt

Perceptron

1978

Nemirovskii and Yudin

Robustification via averaging
for non-smooth obj.

1988
1992

RuppertPolyak and Juditsky

Robust step size policy and averaging
for smooth obj.

1998
2004

BottouBottou and LeCun

Online stochastic optimization
for large scale ML task

20092012

Singer and Duchi; Duchi
et al.; Xiao

FOBOS, AdaGrad, RDA

20122013

Le Roux et al.
Shalev-Shwartz and Zhang
Johnson and Zhang

Linear convergence on batch data
(SAG,SDCA,SVRG)
7 / 73

Overview of stochastic optimization
min f (x)xStochastic approximation (SA)Optimization for systems with uncertainty,
e.g., machine control, traﬃc management, social science, and so on.
gt = ∇f (x (t) ) + ξt is observed where ξt is noise (typically i.i.d.).

Stochastic approximation for machine learning and statistics
Typically generalization error minimization:
min f (x) = min EZ [ℓ(Z , x)].
xx

gt = ∇ℓ(zt , x (t) ) is observed where zt ∼ P(Z ) is i.i.d. data.
ℓ(z, x) is a loss function:e.g., logistic loss ℓ((w , y ), x) = log(1 + exp(−yw ⊤ x)) forz = (w , y ) ∈ Rp × {±1}.
Used for huge dataset.
We don’t need exact optimization. Optimization with certain
precision (typically O(1/n)) is suﬃcient.
8 / 73

Two types of stochastic optimization
Online type stochastic optimization:
We observe data sequentially.
Each observation is used just once (basically).

min EZ [ℓ(Z , x)]x

Batch type stochastic optimization
The whole sample has been already observed.
We may use training data multiple times.

1∑ℓ(zi , x)
n
n

min
x

i=1

9 / 73

Summary of convergence rates
Online methods (expected risk minimization):GR√ (non-smooth, non-strongly convex)
TG2(non-smooth, strongly convex)
µT
σR
R 2L
√ + 2 (smooth, non-strongly convex)
T( √
T
)
σ2
µ
+ exp −T (smooth, strongly convex)µT
L

Batch methods (empirical risk minimization)()
exp − n+1 µ T (smooth loss, strongly convex reg)L()
1
exp − √ nµ T (smooth loss, strongly convex reg with acceleration)n+L

G : upper bound of norm of gradient, R: diameter of the domain,
L: smoothness, µ: strong convexity, σ: variance of the gradient
10 / 73

Example of empirical risk minimization:
High dimensional data analysis

Bio-informatics

Text data

Image data
11 / 73

Example of empirical risk minimization:
High dimensional data analysis

Redundant information deteriorates the estimation accuracy.

Bio-informatics

Text data

Image data
11 / 73

Sparse estimation

Cut oﬀ redundant information → sparsity
R. Tsibshirani (1996). Regression shrinkage and selection via the lasso. J. Royal.
Statist. Soc B., Vol. 58, No. 1, pages 267–288.

12 / 73

Lasso estimator
Lasso [L1 regularization]β̂Lasso = argmin ∥Y − X β∥2 + λ∥β∥1β∈Rpwhere ∥β∥1 =∑p

j=1 |βj |.

Convex optimization
L1 norm is the convex hull of L0 normon [−1, 1]p (the largest convex function
which supports from below).
L1 norm is the Lovász extension of the
cardinality function.

13 / 73

Lasso estimator
Lasso [L1 regularization]β̂Lasso = argmin ∥Y − X β∥2 + λ∥β∥1β∈Rpwhere ∥β∥1 =∑p

j=1 |βj |.

Convex optimization
L1 norm is the convex hull of L0 normon [−1, 1]p (the largest convex function
which supports from below).
L1 norm is the Lovász extension of the
cardinality function.
More generally for a loss function ℓ (logistic loss, hinge loss, ...)
{ n
}
∑
min
ℓ(zi , x) + λ∥x∥1xi=113 / 73

Outline
1

Introduction

2

Short course to convex analysis
Convexity and related concepts
Duality
Smoothness and strong convexity

3

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

Online stochastic optimization
Stochastic gradient descent
Stochastic regularized dual averaging

14 / 73

Regularized empirical risk minimization
Basically, we want to solve
Empirical risk minimization:
1∑ℓ(zi , x).
n
n

minp

x∈R

i=1

Regularized empirical risk minimization:
1∑ℓ(zi , x) + ψ(x).
n
n

min

x∈Rp

i=1

In this lecture, we assume ℓ and ψ are convex.
→ convex analysis to exploit the properties of convex functions.

15 / 73

Outline
1

Introduction

2

Short course to convex analysis
Convexity and related concepts
Duality
Smoothness and strong convexity

3

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

Online stochastic optimization
Stochastic gradient descent
Stochastic regularized dual averaging

16 / 73

Convex set
Definition (Convex set)
A convex set is a set that contains the segment connecting two points inthe set:x1 , x2 ∈ C

Convex set=⇒

θx1 + (1 − θ2 )x2 ∈ C (θ ∈ [0, 1]).

Non-convex set

Non-convex set

17 / 73

Epigraph and domain
Let R̄ := R ∪ {∞}.

Definition (Epigraph and domain)
The epigraph of a function f : Rp → R̄ is given by
epi(f ) := {(x, µ) ∈ Rp+1 : f (x) ≤ µ}.
The domain of a function f : Rp → R̄ is given bydom(f ) := {x ∈ Rp : f (x) < ∞}.
epigraph(domain]18 / 73

Convex function
Let R̄ := R ∪ {∞}.

Definition (Convex function)
A function f : Rp → R̄ is a convex function if f satisfiesθf (x) + (1 − θ)f (y ) ≥ f (θx + (1 − θ)y )(∀x, y ∈ Rp , θ ∈ [0, 1]),

where ∞ + ∞ = ∞, ∞ ≤ ∞.

Convex

Non-convex

f is convex ⇔ epi(f ) is a convex set.
19 / 73Proper and closed convex function
If the domain of a function f is not empty (dom(f ) ̸= ∅), f is called
proper.
If the epigraph of a convex function f is a closed set, then f is called
closed.
(We are interested in only a proper closed function in this lecture.)

Even if f is closed, it’s domain is not necessarily closed (even for 1D).
“f is closed” does not imply“f is continuous.”
Closed convex function is continuous on a segment in its domain.
Closed function is “lower semicontinuity.”

20 / 73

Convex loss functions (regression)
All well used loss functions are (closed) convex. The followings are convex
w.r.t. u with a fixed label y ∈ R.
Squared loss:ℓ(y , u) = 12 (y − u)2 .
τ -quantile loss:ℓ(y , u) = (1 − τ ) max{u − y , 0} + τ max{y − u, 0}.
for some τ ∈ (0, 1). Used for quantile regression.
ϵ-sensitive loss: ℓ(y , u) = max{|y − u| − ϵ, 0} for some ϵ > 0. Usedfor support vector regression.
Squaredτ-quantile

3

Huber

-sensitive

2

1

0
-3

-2

-1

0
f-y

1

2

3

21 / 73

Convex surrogate loss (classification)y ∈ {±1}
Logistic loss:ℓ(y , u) = log((1 + exp(−yu))/2).
Hinge loss:ℓ(y , u) = max{1 − yu, 0}.
Exponential loss: ℓ(y , u) = exp(−yu).
Smoothed hinge loss:(yu ≥ 1),0,1ℓ(y , u) = 2 − yu,(yu < 0),
1
2
2 (1 − yu) , (otherwise).
0-1

4

Logistic

Hinge
exp

3

Smoothed-hinge

2

1

0
-3

-2

-1

0
yf

1

2

3

22 / 73

Convex regularization functions
Ridge regularization:
L1 regularization:

R(x) = ∥x∥22 :=∑p

2
j=1 xj .
∑R(x) = ∥x∥1 := pj=1 |xj |.
∑min{q,r }R(X ) = ∥X ∥tr = k=1
σj (X )

Trace norm regularization:
where σj (X ) ≥ 0 is the j-th singular value.
1

0.8

0.6

0.4

0.2

0

-0.2

Bridge (=0.5)

-0.4

L1

-0.6

Ridge
Elasticnet

-0.8

-1

-1

-0.8

-0.6

-0.4

-0.2

0

0.2

0.4

0.6

0.8

1

1 ∑n
⊤ 2
n ∑i=1 (yi − zi x) + λ∥x∥1 : Lasson1⊤
i=1 log(1 + exp(−yi zi x)) + λ∥X ∥tr : Low rank matrix recoveryn23 / 73

Other definitions of sets
Convex hull: conv(C ) is the smallest convex set that contains a set
C ⊆ Rp .
Aﬃne set: A set A is an aﬃne set if and only if ∀x, y ∈ A, the line thatintersects x and y lies in A: λx + (1 − λ)y ∀λ ∈ R.
Aﬃne hull: The smallest aﬃne set that contains a set C ⊆ Rp .
Relative interior: ri(C ). Let A be the aﬃne hull of a convex set C ⊆ Rp .
ri(C ) is a set of internal points with respect to the relative
topology induced by the aﬃne hull A.
Convex hullAﬃne hull

Relative interior

24 / 73

Continuity of a closed convex function
Theorem
For a (possibly non-convex) function f : Rp → R̄, the following three
conditions are equivalent to each other.
1
2

3

f is lower semi-continuous.
p
For any converging sequence {xn }∞n=1 ⊆ R s.t. x∞ = limn xn ,lim inf n f (xn ) ≥ f (x∞ ).

f is closed.

Remark: Any convex function f is continuous in ri(dom(f )). The continuity
could be broken on the boundary of the domain.

25 / 73

Outline
1

Introduction

2

Short course to convex analysis
Convexity and related concepts
Duality
Smoothness and strong convexity

3

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

Online stochastic optimization
Stochastic gradient descent
Stochastic regularized dual averaging

26 / 73Subgradient
We want to deal with non-diﬀerentiable function such as L1 regularization.
To do so, we need to define something like gradient.

Definition (Subdiﬀerential, subgradient)
For a proper convex function f : Rp → R̄, the subdiﬀerential of f at
x ∈ dom(f ) is defined by∂f (x) := {g ∈ Rp | ⟨x ′ − x, g ⟩ + f (x) ≤ f (x ′ ) (∀x ′ ∈ Rp )}.
An element of the subdiﬀerential is called subgradient.
f(x)Subgradient

27 / 73Properties of subgradient
Subgradient does not necessarily exist (∂f (x) could be empty).
f (x) = x log(x) (x ≥ 0) is proper convex but not subdiﬀerentiable at x = 0.

Subgradient always exists on ri(dom(f )).

28 / 73Properties of subgradient
Subgradient does not necessarily exist (∂f (x) could be empty).
f (x) = x log(x) (x ≥ 0) is proper convex but not subdiﬀerentiable at x = 0.

Subgradient always exists on ri(dom(f )).
If f is diﬀerentiable at x, its gradient is the unique element of subdiﬀ.
∂f (x) = {∇f (x)}.

28 / 73Properties of subgradient
Subgradient does not necessarily exist (∂f (x) could be empty).
f (x) = x log(x) (x ≥ 0) is proper convex but not subdiﬀerentiable at x = 0.

Subgradient always exists on ri(dom(f )).
If f is diﬀerentiable at x, its gradient is the unique element of subdiﬀ.
∂f (x) = {∇f (x)}.
If ri(dom(f )) ∩ ri(dom(h)) ̸= ∅, then∂(f + h)(x) = ∂f (x) + ∂h(x)= {g + g ′ | g ∈ ∂f (x), g ′ ∈ ∂h(x)}(∀x ∈ dom(f ) ∩ dom(h)).

28 / 73Properties of subgradient
Subgradient does not necessarily exist (∂f (x) could be empty).
f (x) = x log(x) (x ≥ 0) is proper convex but not subdiﬀerentiable at x = 0.

Subgradient always exists on ri(dom(f )).
If f is diﬀerentiable at x, its gradient is the unique element of subdiﬀ.
∂f (x) = {∇f (x)}.
If ri(dom(f )) ∩ ri(dom(h)) ̸= ∅, then∂(f + h)(x) = ∂f (x) + ∂h(x)= {g + g ′ | g ∈ ∂f (x), g ′ ∈ ∂h(x)}(∀x ∈ dom(f ) ∩ dom(h)).
For all g ∈ ∂f (x) and all g ′ ∈ ∂f (x ′ ) (x, x ′ ∈ dom(f )),⟨g − g ′ , x − x ′ ⟩ ≥ 0.
28 / 73

Legendre transform
Defines the other representation on the dual space (the space of gradients).

Definition (Legendre transform)
Let f be a (possibly non-convex) function f : Rp → R̄ s.t. dom(f ) ̸= ∅.
Its convex conjugate is given byf ∗ (y ) := sup {⟨x, y ⟩ − f (x)}.
x∈Rp

The map from f to f ∗ is called Legendre transform.
f(x)line with gradient y
f(x*)

0
x*

x

f*(y)
29 / 73

Examples
Squared loss

f (x)
1 2
x
2

Hinge loss

max{1 − x, 0}

Logistic loss

log(1 + exp(−x))

L1 regularization
Lp regularization{{(−y ) log(−y ) + (1 + y ) log(1 + y )∞j=1 |xj |(−1 ≤ y ≤ 0),(otherwise).
{0(maxj |yj | ≤ 1),∞ (otherwise).
p∑d p−1
p |yj | p−1
j=1

∥x∥1
∑d

y
∞

f ∗ (y )1 2
y2(−1 ≤ y ≤ 0),(otherwise).

p

p p−1

(p > 1)0

1

L1 -norm

0logistic

dual of logistic

dual
30 / 73Properties of Legendre transformf ∗ is a convex function even if f is not.
f ∗∗ is the closure of the convex hull of f :f ∗∗ = cl(conv(f )).

Corollary
Legendre transform is a bijection from the set of proper closed convex
functions onto that defined on the dual space.
f (proper closed convex)⇔

f ∗ (proper closed convex)

6f(x)cl.conv.

4
2
0
-2
-4
-6
0

1

2

3

4

31 / 73

Connection to subgradientLemmay ∈ ∂f (x) ⇔ f (x) + f ∗ (y ) = ⟨x, y ⟩ ⇔ x ∈ ∂f ∗ (y ).
∵y ∈ ∂f (x) ⇒ x = argmax{⟨x ′ , y ⟩ − f (x ′ )}x ′ ∈Rp(take the “derivative” of ⟨x ′ , y ⟩ − f (x ′ ))⇒ f ∗ (y ) = ⟨x, y ⟩ − f (x).

Remark: By definition, we always havef (x) + f ∗ (y ) ≥ ⟨x, y ⟩.
→ Young-Fenchel’s inequality.
32 / 73⋆ Fenchel’s duality theorem
Theorem (Fenchel’s duality theorem)
Let f : Rp → R̄, g : Rq → R̄ be proper closed convex, and A ∈ Rq×p .
Suppose that either of condition (a) or (b) is satisfied, then it holds thatinf {f (x) + g (Ax)} = sup {−f ∗ (A⊤ y ) − g ∗ (−y )}.

x∈Rp

y ∈Rq





(a) ∃x ∈ Rp s.t. x ∈ ri(dom(f )) and Ax ∈ ri(dom(g )).
(b) ∃y ∈ Rq s.t. A⊤ y ∈ ri(dom(f ∗ )) and −y ∈ ri(dom(g ∗ )).



If (a) is satisfied, there exists y ∗ ∈ Rq that attains sup of the RHS.
If (b) is satisfied, there exists x ∗ ∈ Rp that attains inf of the LHS.
Under (a) and (b), x ∗ , y ∗ are the optimal solutions of the each side iﬀ

A⊤ y ∗ ∈ ∂f (x ∗ ), Ax ∗ ∈ ∂g ∗ (−y ∗ ).
→ Karush-Kuhn-Tucker condition.

33 / 73Equivalence to the separation theorem
ConvexConcave

34 / 73

Applying Fenchel’s duality theorem to RERM

RERM (Regularized Empirical Risk Minimizatino):
Let ℓi (zi⊤ x) = ℓ(yi , zi⊤ x) where (zi , yi ) is the input-output pair of the i-th
observation.


{ n
}
∑
ℓi (zi⊤ x) + ψ(x)(Primal)inf px∈R|i=1 {z}f (Zx)


[Fenchel’s duality theorem]
inf {f (Zx) + ψ(x)} = − inf n {f ∗ (y ) + ψ ∗ (−Z ⊤ y )}
y ∈R

x∈Rp



(Dual)

sup

y ∈Rn

{ n
∑

}



ℓ∗i (yi ) + ψ ∗ (−Z ⊤ y )i=1This fact will be used to derive dual coordinate descent alg.


35 / 73

Outline
1

Introduction

2

Short course to convex analysis
Convexity and related concepts
Duality
Smoothness and strong convexity

3

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

Online stochastic optimization
Stochastic gradient descent
Stochastic regularized dual averaging

36 / 73

Smoothness and strong convexity
Definition
Smoothness: the gradient is Lipschitz continuous:∥∇f (x) − ∇f (x ′ )∥ ≤ L∥x − x ′ ∥.
Strong convexity: ∀θ ∈ (0, 1), ∀x, y ∈ dom(f ),µθ(1 − θ)∥x − y ∥2 + f (θx + (1 − θ)y ) ≤ θf (x) + (1 − θ)f (y ).
20Smooth but
not strongly convex

0

Smooth andStrongly convex

0

Strongly convex but
not smooth 37 / 73

Duality between smoothness and strong convexity
Smoothness and strong convexity is in a relation of duality.

Theorem
Let f : Rp → R̄ be proper closed convex.
f is L-smooth ⇐⇒ f ∗ is 1/L-strongly convex.
logistic loss

its dual function

0

1

0

Smooth but
not strongly convex

Strongly convex but
not smooth(gradient → ∞)38 / 73

Outline
1

Introduction

2

Short course to convex analysis
Convexity and related concepts
Duality
Smoothness and strong convexity

3

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

Online stochastic optimization
Stochastic gradient descent
Stochastic regularized dual averaging

39 / 73

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

minp

x∈R

i=1

∥x∥1
|{z}

.

regularization

40 / 73

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

minp

x∈R

i=1

∥x∥1
|{z}

.

regularization

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

min

x∈Rp

i=1

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

40 / 73

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.
41 / 73

Outline
1

Introduction

2

Short course to convex analysis
Convexity and related concepts
Duality
Smoothness and strong convexity

3

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

Online stochastic optimization
Stochastic gradient descent
Stochastic regularized dual averaging

42 / 73

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 ).

43 / 73

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 .

43 / 73

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

min f (x).
xSubgradient method (equivalent formula)
Subdiﬀerentiable f (x):{}12xt = argmin ⟨x, gt ⟩ +∥x − xt−1 ∥ ,2ηtx
where gt ∈ ∂f (xt−1 ).
Proximal point algorithm:{}
1
xt = argmin f (x) +∥x − xt−1 ∥2 .
2ηtx

f (xt ) → optimum for any convex f and ηt = η > 0 (Güler, 1991).
(
)t−1
1
1
∥x0 − x ∗ ∥2 .
If f (x) is strongly convex: f (xt ) − f (x ∗ ) ≤ 2η1+ση43 / 73Proximal gradient descent
Let f (x) =∑ni=1 ℓ(zi , x).

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

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

44 / 73

ExampleL1 regularization: ψ(x) = C ∥x∥1 .
xt,j = STC ηt (xt−1,j − ηt gt,j )(j-th component)

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

For many practically used regularizations, analytic form is obtained.
45 / 73

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 )46 / 73

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.
47 / 73

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’s
acceleration.
→ Optimal rate

47 / 73

Outline
1

Introduction

2

Short course to convex analysis
Convexity and related concepts
Duality
Smoothness and strong convexity

3

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

Online stochastic optimization
Stochastic gradient descent
Stochastic regularized dual averaging

48 / 73

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, . . .
1

2

3

Let 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 ∗ ∥.
t2This is also called Fast Iterative Shrinkage Thresholding Algorithm (FISTA)(Beck and Teboulle, 2009).
The step size η = 1/γ can be adaptively determined: back-tracking
technique.
49 / 73

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, . . .
1
2

3

Let 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 .
µ50 / 7351 / 73

104

NormalNesterov
2

Relative objective (f(xt ) - f * )

10

100

10-2

-4

10

10-6

-8

10

0

20

40

60

80

100

120

Iteration

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

52 / 73

Outline
1

Introduction

2

Short course to convex analysis
Convexity and related concepts
Duality
Smoothness and strong convexity

3

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

Online stochastic optimization
Stochastic gradient descent
Stochastic regularized dual averaging

53 / 73

Two types of stochastic optimization
Online type stochastic optimization:
We observe data sequentially.
We don’t need to wait until the whole sample is obtained.
Each observation is obtained just once (basically).

min EZ [ℓ(Z , x)]x

Batch type stochastic optimization
The whole sample has been already observed.
We can make use of the (finite and fixed) sample size.
We may use sample multiple times.

1∑ℓ(zi , x)
n
n

min
x

i=1

54 / 73

Online method
You don’t need to wait until the whole sample arrives.
Update the parameter at each data observation.
storage

New data input

P(z)
zt-1

xt

zt

xt+1

Observe

UpdateObserve

Update1 ∑ℓ(zt , x) + ψ(x)T
T

min E[ℓ(Z , x)] + ψ(x) ≃ min
x

x

t=1

55 / 73

The objective of online stochastic optimization
Let ℓ(z, x) be a loss of x for an observation z.
(Expected loss)

L(x) = EZ [ℓ(Z , x)]or(EL with regularization)Lψ (x) = EZ [ℓ(Z , x)] + ψ(x)The distribution of Z could be
the true population→ L(x) is the generalization error.
an empirical distribution of stored data in a storage→ L (or Lψ ) is the (regularized) empirical risk.
Online stochastic optimization itself is learning!
56 / 73

Outline
1

Introduction

2

Short course to convex analysis
Convexity and related concepts
Duality
Smoothness and strong convexity

3

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

Online stochastic optimization
Stochastic gradient descent
Stochastic regularized dual averaging

57 / 73Three steps tostochastic gradient descent∫
E[ℓ(Z , x)] =ℓ(Z , x)dP(Z )≃ ℓ(zt , xt−1 )(sampling)≃ ⟨∇x ℓ(zt , xt−1 ), x⟩(linearlization)

(1)
(2)

The approximation is correct just around xt−1 .
{}1
2
min E[ℓ(Z , x)] ≃ min ⟨∇x ℓ(zt , xt−1 ), x⟩ +∥x − xt−1 ∥(proximation)
x
2ηt
(3) x

xt-1
58 / 73

Stochastic gradient descent (SGD)
SGD (without regularization)
Observe zt ∼ P(Z ), and let ℓt (x) := ℓ(zt , x).
Calculate subgradient:gt ∈ ∂x ℓt (xt−1 ).
Update x as
xt = xt−1 − ηt gt .
We just need to observe one training data zt at each iteration.
→ O(1) computation per iteration (O(n) for batch gradient descent).
We do not need to go through the whole sample {zi }ni=1{}
Reminder: prox(q|ψ) := argminx ψ(x) + 12 ∥x − q∥2 .
59 / 73

Stochastic gradient descent (SGD)
SGD (with regularization)
Observe zt ∼ P(Z ), and let ℓt (x) := ℓ(zt , x).
Calculate subgradient:gt ∈ ∂x ℓt (xt−1 ).
Update x as
xt = prox(xt−1 − ηt gt |ηt ψ).
We just need to observe one training data zt at each iteration.
→ O(1) computation per iteration (O(n) for batch gradient descent).
We do not need to go through the whole sample {zi }ni=1{}
Reminder: prox(q|ψ) := argminx ψ(x) + 12 ∥x − q∥2 .
59 / 73

Convergence analysis of SGD
Assumption(A1) E[∥gt ∥2 ] ≤ G 2 .
(A2) E[∥xt − x ∗ ∥2 ] ≤ D 2 .

TheoremLet x̄T = T 1+1∑T

t=0 xt . For ηt =

η0√, it holdstEz1:T [Lψ (x̄T ) − Lψ (x ∗ )] ≤For η0 = D
G , we have

η0 G 2 + D 2 /η0
√
.
T

2GD
√ .
T

This is minimax optimal (up to constant).
G is independent of ψ thanks to the proximal mapping. Note that√∥∂ψ(x)∥ ≤ C p for L1 -reg.
60 / 73

Convergence analysis of SGD (strongly convex)
Assumption(A1) E[∥gt ∥2 ] ≤ G 2 .
(A3) Lψ is µ-strongly convex.

TheoremLet x̄T = T 1+1∑T1
t=0 xt . For ηt = µt , it holds

Ez1:T [Lψ (x̄T ) − Lψ (x ∗ )] ≤G 2 log(T ).
TµBetter than non-strongly convex situation.
But, this is not minimax optimal.
The bound is tight (Rakhlin et al., 2012).

61 / 73

Polynomial averaging for strongly convex risk
Assumption(A1) E[∥gt ∥2 ] ≤ G 2 .
(A3) Lψ is µ-strongly convex.
Modify the update rule as(
xt = prox xt−1 − ηt)t
gt |ηt ψ ,
t +1

∑
2
and take the weighted average x̄T =(t + 1)xt .
(T + 1)(T + 2)T

t=0

Theorem2, it holds
For ηt = µt

Ez1:T [Lψ (x̄T ) − Lψ (x ∗ )] ≤

2G 2
.
Tµ

log(T ) is removed.
This is minimax optimal (explained later).
62 / 73

Remark on polynomial averaging∑
2(t + 1)xt(T + 1)(T + 2)
T

x̄T =

t=0

O(T ) computation? No.
x̄T can be eﬃciently updated:
x̄t =

t
2
x̄t−1 +
xt .
t +2
t +2

63 / 73

General step size and weighting policy∑ +1
Let st (t = 1, 2, . . . , T + 1) be a positive sequence such that T
t=1 st = 1.
()
st
xt = prox xt−1 − ηtgt |ηt ψ(t = 1, . . . , T )
st+1
x̄T =

T
∑

st+1 xt .

t=0Assumption: (A1) E[∥gt ∥2 ] ≤ G 2 , (A2) E[∥xt − x ∗ ∥2 ] ≤ D 2 , (A3) Lψ isµ-strongly convex.

Theorem
Ez1:T [Lψ (x̄T ) − Lψ (x ∗ )]≤T∑
st+1 ηt+1
t=1

2

G2 +

1
2
T
−1 max{ st+2 − s∑
t+1 ( ηt + µ), 0}D
ηt+1
t=0

2

As for t = 0, we set 1/η0 = 0 .
64 / 73

Special case
Let the weight proportion to the step size (step size could be seen as
importance):ηt
st = ∑T +1 .
τ =1 ητIn this setting, the previous theorem gives∗∑T

Ez1:T [Lψ (x̄T ) − Lψ (x )] ≤


∞
∑
t=1
∞
∑

2 2
2
t=1 ηt G + D∑T
2 t=1 ηtηt = ∞
ηt2 < ∞

t=1

ensures the convergence.

65 / 73

Outline
1

Introduction

2

Short course to convex analysis
Convexity and related concepts
Duality
Smoothness and strong convexity

3

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

Online stochastic optimization
Stochastic gradient descent
Stochastic regularized dual averaging

66 / 73

Stochastic regularized dual averaging (SRDA)
The second assumption E[∥xt − x ∗ ∥2 ] ≤ D 2 can be removed by using dual
averaging (Nesterov, 2009, Xiao, 2009).

SRDA
Observe zt ∼ P(Z ), and let ℓt (x) := ℓ(zt , x).
Calculate gradient: gt ∈ ∂x ℓt (xt−1 ).
Take the average of the gradients:
1∑
ḡt =
gτ .
t
τ =1
{
}
1
∥x∥2
xt = argmin ⟨ḡt , x⟩ + ψ(x) +
2ηt
x∈Rp
t

Update as= prox(−ηt ḡt |ηt ψ).
The information of old observations is maintained by taking average of
gradients.
67 / 73

Convergence analysis of SRDA
Assumption(A1) E[∥gt ∥2 ] ≤ G 2 .
(A2) E[∥xt − x ∗ ∥2 ] ≤ D 2 .

TheoremLet x̄T = T 1+1∑T

t=0 xt . For ηt = η0√t, it holds

Ez1:T [Lψ (x̄T ) − Lψ (x ∗ )] ≤

η0 G 2 + ∥x ∗ − x0 ∥2 /η0√.
T

If ∥x ∗ − x0 ∥ ≤ R, then for η0 = GR , we have
2RG
√ .
T
This is minimax optimal (up to constant).
The norm of intermediate solution xt is well controlled. Thus (A2) is
not required.
68 / 73

Convergence analysis of SRDA (strongly convex)
Assumption(A1) E[∥gt ∥2 ] ≤ G 2 .
(A2) E[∥xt − x ∗ ∥2 ] ≤ D 2 .
(A3) ψ is µ-strongly convex.
Modify the update rule as∑2
τ gτ ,(t + 1)(t + 2)
t

ḡt =

(
)
xt = prox − ηt ḡt |ηt ψ ,τ =12
and take the weighted average x̄T = (T +1)(T+2)∑T

t=0 (t + 1)xt .

TheoremFor ηt = (t + 1)(t + 2)/ξ, it holds
Ez1:T [Lψ (x̄T ) − Lψ (x ∗ )] ≤ξ∥x ∗ − x0 ∥2 2G 2
+
.
T2
Tµ

2

ξ → 0 yields 2G
T µ : minimax optimal.
69 / 73

General convergence analysis
Let the weight st > 0 (t = 1, . . . ) is any positive sequence. We generalize
the update rule as∑tsτ gτ
ḡt = ∑τ =1
,
t+1
s
τ
τ =1
xt = prox(−ηt ḡt |ηt ψ)(t = 1, . . . , T ).

Let the weighted average of (xt )t be x̄T =∑Tτ =0 sτ +1 xτ
∑.
Tτ =0 sτ +1

Assumption: (A1) E[∥gt ∥2 ] ≤ G 2 , (A3) Lψ is µ-strongly convex (µ can be 0).

Theorem∑
Suppse that ηt /( t+1τ =1 sτ ) is non-decreasing, thenEz1:T [Lψ (x̄T ) − Lψ (x ∗ )]
(T +1
)
∑T +2
∑
s
st2
1
t
≤ ∑T +1
G 2 + t=1 ∥x ∗ − x0 ∥2 .
∑t
2ηT +1
2[(
s
)(µ
+
1/η
)]
s
τ
t−1
τ =1
t=1 t
t=1
70 / 73

Computational cost and generalization error
The optimal learning rate for a strongly convex expected risk
(generalization error) is O(1/n) (n is the sample size).
To achieve O(1/n) generalization error, we need to decrease thetraining error to O(1/n).

Time per iteration
Number of iterations until ϵ error
Time until ϵ error
Time until 1/n error

Normal gradient des.
nlog(1/ϵ)n log(1/ϵ)
n log(n)

SGD
1
1/ϵ
1/ϵ
n

(Bottou, 2010)

SGD is O(log(n)) faster with respect to the generalization error.

71 / 73

Typical behavior
Trainig error

0.5

SGD
Batch

0.4
0.3
0.2
0.1
0
0

0.5

1

1.5

2

2.5

3

3.5

2.5

3

3.5

Generalization error

Elaplsed time (s)
0.5
0.4
0.3
0.2
0.1
0
0

0.5

1

1.5

2

Elaplsed time (s)Normal gradient descent v.s. SGD
Logistic regression with L1 -regularization: n = 10, 000, p = 2.

SGD decreases the objective rapidly, and after a while, the batch gradientmethod catches up and slightly surpasses.
72 / 73

Summary of part I
Overview of stochastic optimization
Convex analysis
First order method
Proximal gradient descent

Online stochastic optimization
Stochastic gradient descent (SGD)
Stochastic regularized dual averaging (SRDA)
RG√
convergence in generalT
G2µT

convergence for strongly convex risk

Next part: faster algorithm of online stochastic optimization, and batch
stochastic optimization method

73 / 73

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.
L. Bottou. Online algorithms and stochastic approximations. 1998. URL
http://leon.bottou.org/papers/bottou-98x. revised, oct 2012.
L. Bottou. Large-scale machine learning with stochastic gradient descent.
In Proceedings of COMPSTAT’2010, pages 177–186. Springer, 2010.
L. Bottou and Y. LeCun. Large scale online learning. In S. Thrun, L. Saul,
and B. Schölkopf, editors, Advances in Neural Information Processing
Systems 16. MIT Press, Cambridge, MA, 2004. URL
http://leon.bottou.org/papers/bottou-lecun-2004.
J. Duchi, E. Hazan, and Y. Singer. Adaptive subgradient methods foronline learning and stochastic optimization. Journal of Machine
Learning Research, 12:2121–2159, 2011.
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.
R. Johnson and T. Zhang. Accelerating stochastic gradient descent using
predictive variance reduction. In C. Burges, L. Bottou, M. Welling,
73 / 73

Z. Ghahramani, and K. Weinberger, editors, Advances in Neural
Information Processing Systems 26, pages 315–323. Curran Associates,
Inc., 2013. URL http://papers.nips.cc/paper/
4937-accelerating-stochastic-gradient-descent-using-predicti
pdf.

N. Le Roux, M. Schmidt, and F. R. Bach. A stochastic gradient methodwith an exponential convergence rate for finite training sets. In
F. Pereira, C. Burges, L. Bottou, and K. Weinberger, editors, Advancesin Neural Information Processing Systems 25, pages 2663–2671. Curran
Associates, Inc., 2012. URL http://papers.nips.cc/paper/
4633-a-stochastic-gradient-method-with-an-exponential-conve
rate-for-finite-training-sets.pdf.
A. Nemirovskii and D. Yudin. On cezari s convergence of the steepest
descent method for approximating saddle points of convex-concave
functions. Soviet Mathematics Doklady, 19(2):576–601, 1978.
Y. Nesterov. Primal-dual subgradient methods for convex problems.
Mathematical Programming, 120(1):221–259, 2009.
B. T. Polyak and A. B. Juditsky. Acceleration of stochastic approximation
73 / 73

by averaging. SIAM Journal on Control and Optimization, 30(4):838–855, 1992.
A. Rakhlin, O. Shamir, and K. Sridharan. Making gradient descentoptimal for strongly convex stochastic optimization. In J. Langford and
J. Pineau, editors, Proceedings of the 29th International Conference on
Machine Learning, pages 449–456. Omnipress, 2012. ISBN
978-1-4503-1285-1.
H. Robbins and S. Monro. A stochastic approximation method. The
Annals of Mathematical Statistics, 22(3):400–407, 1951.
F. Rosenblatt. The perceptron: A perceiving and recognizing automaton.
Technical Report Technical Report 85-460-1, Project PARA, Cornell
Aeronautical Lab., 1957.
D. Ruppert. Eﬃcient estimations from a slowly convergent robbins-monroprocess. Technical report, Cornell University Operations Research andIndustrial Engineering, 1988.
S. Shalev-Shwartz and T. Zhang. Stochastic dual coordinate ascentmethods for regularized loss minimization. Journal of Machine Learning
Research, 14:567–599, 2013.
73 / 73

Y. Singer and J. C. Duchi. Eﬃcient learning using forward-backward
splitting. In Advances in Neural Information Processing Systems, pages
495–503, 2009.
L. Xiao. Dual averaging methods for regularized stochastic learning andonline optimization. In Advances in Neural Information Processing
Systems 23. 2009.

73 / 73