Deterministic vs Stochastic Optimization Convergence Rates of Gradient Methods

Michael Friedlander1

Description

Deterministic vs. Stochastic Optimization Convergence Rates of Gradient Methods Practical Issues and Application Other Projects and Summary Hybrid Deterministic-Stochastic Methods for Data Fitting Michael Friedlander1 Mark Schmidt2 1University of British Columbia 2INRIA/ENS July 2011 Michael Friedlander and Mark Schmdit Hybrid Deterministic-Stochastic Methods for Data Fitting

• data fitting


• british columbia


• stochastic optimization


• hybrid deterministic-stochastic

Sujets

• Friedlander
• Curve fitting
• British Columbia
• Stochastic optimization

Informations

• Publié par: pefav
• Nombre de lectures: 12
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

July2011

2
INRIA/ENS

1
UniversityofBritishColumbia

MichaelFriedlander
1
MarkSchmidt
2

HybridDeterministic-StochasticMethodsforData
Fitting

gnittiFataDrofsdohteMcitsahcotS-citsinimreteDdirbyHtidmhcSkraMdnarednaldeirFleahciMyrammuSdnastcejorPrehtOnoitacilppAdnaseussIlacitcarPsdohteMtneidarGfosetaRecnegrevnoCnoitazimitpOcitsahcotS.svcitsinimreteD
gnittiFataDrofsdohteMcitsahcotS-citsinimreteDdirbyHtidmhcSkraMdnarednaldeirFleahciMOtherProjectsandSummary

4

PracticalIssuesandApplication

y3

rConvergenceRatesofGradientMethods

a2

m1

mDeterministicvs.StochasticOptimization

uOutline

SdnastcejorPrehtOnoitacilppAdnaseussIlacitcarPsdohteMtneidarGfosetaRecnegrevnoCnoitazimitpOcitsahcotS.svcitsinimreteD
naseussIlacitcarPsdohteMtneidarGfosetaRecnegrevnoCnoitazimitpOcitsahcotS.svcitsinimreteDShouldweuse
AlgorithmS
or

AlgorithmD
?

AlgorithmSvs.AlgorithmD:

Errorvs.Iteration

H
Al
y
g
b
o
ri
ri
d
th
M
m
et
S
ho
vs
d
.
s
AlgorithmD

gnittiFataDrofsdohteMcitsahcotS-citsinimreteDdirbyHtidmhcSkraMdnarednaldeirFleahciM.k2/1fororrenasahDmhtiroglA,knoitaretinO.k/1fororrenasahSmhtiroglA,knoitaretinOyrammuSdnastcejorPrehtOnoitacilppAd
gnittiFataDrofsdohteMcitsahcotS-citsinimreteDdirbyHtidmhcSkraMdnarednaldeirFleahciMShouldweuse
AlgorithmS
or
AlgorithmD
?
Oniteration
k
,
AlgorithmS
hasanerrorof1
/
k
.
Oniteration
k
,
AlgorithmD
hasanerrorof1
/
2
k
.

sAlgorithmSvs.AlgorithmD:Errorvs.Iteration

dohteMdirbyHDmhtiroglA.svSmhtiroglAyrammuSdnastcejorPrehtOnoitacilppAdnaseussIlacitcarPsdohteMtneidarGfosetaRecnegrevnoCnoitazimitpOcitsahcotS.svcitsinimreteD
arGfosetaRecnegrevnoCnoitazimitpOcitsahcotS.svcitsinimreteDShouldweuse
AlgorithmS
or
AlgorithmD
?
Oniteration
k
,
AlgorithmS
hasanerrorof1
/
k
.
Oniteration
k
,
AlgorithmD
hasanerrorof1
/
2
k
.

AlgorithmSvs.AlgorithmD:Errorvs.Iteration

gnittiFataDrofsdohteMcitsahcotS-citsinimreteDdirbyHtidmhcSkraMdnarednaldeirFleahciMsdohteMdirbyHDmhtiroglA.svSmhtiroglAyrammuSdnastcejorPrehtOnoitacilppAdnaseussIlacitcarPsdohteMtneid
gnittiFataDrofsdohteMcitsahcotS-citsinimreteDdirbyHtidmhcSkraMdnarednaldeirFleahciM.evisnepxeeraDmhtiroglAfosnoitaretI.paehceraSmhtiroglAfosnoitaretIsdohteMdirbyHDmhtiroglA.sBut,theerrorisnotthewholestory:

vAlgorithmSvs.AlgorithmD:Errorvs.Time

SmhtiroglAyrammuSdnastcejorPrehtOnoitacilppAdnaseussIlacitcarPsdohteMtneidarGfosetaRecnegrevnoCnoitazimitpOcitsahcotS.svcitsinimreteD
aRecnegrevnoCnoitazimitpOcitsahcotS.svcitsinimreteDBut,theerrorisnotthewholestory:

Iterationsof
AlgorithmD
are
expensive
.

Iterationsof
AlgorithmS
are
cheap
.

AlgorithmSvs.AlgorithmD:Errorvs.Time

gnittiFataDrofsdohteMcitsahcotS-citsinimreteDdirbyHtidmhcSkraMdnarednaldeirFleahciMsdohteMdirbyHDmhtiroglA.svSmhtiroglAyrammuSdnastcejorPrehtOnoitacilppAdnaseussIlacitcarPsdohteMtneidarGfoset
gnittiFataDrofsdohteMcitsahcotS-citsinimreteDdirbyHtidmhcSkraMdnarednaldeirFleahciMsdohBut,theerrorisnotthewholestory:

tIterationsof
AlgorithmD
are
expensive
.

eIterationsof
AlgorithmS
are
cheap
.

MAlgorithmSvs.AlgorithmD:Errorvs.Time

dirbyHDmhtiroglA.svSmhtiroglAyrammuSdnastcejorPrehtOnoitacilppAdnaseussIlacitcarPsdohteMtneidarGfosetaRecnegrevnoCnoitazimitpOcitsahcotS.svcitsinimreteD
tneidarGfosetaRecnegrevnoCnoitazimitpOcitsahcotS.svcitsinimreteDDeterminstic
makessteadyprogress,butisexpensive.

Stochastic
makesgreatprogressinitially,butslowsdown.

Stochasticvs.Deterministic:

MotivationforHybridMethods

gnittiFataDrofsdohteMcitsahcotS-citsinimreteDdirbyHtidmhcSkraMdnarednaldeirFleahciM?sdlrowhtobfotsebehttegdohtemdirbyhanaCsdohteMdirbyHDmhtiroglA.svSmhtiroglAyrammuSdnastcejorPrehtOnoitacilppAdnaseussIlacitcarPsdohteM
sinimreteDdirbyHtidmhcSkraMdnarednaldeirFleahciMsdohteMdirbyHDmhtiroglA.svSmhtiroglAyraCana
hybrid
methodgetthebestofbothworlds?

mDeterminstic
makessteadyprogress,butisexpensive.

mStochastic
makesgreatprogressinitially,butslowsdown.

uStochasticvs.Deterministic:

SMotivationforHybridMethods

dnastcejorPrehtOnoitacilppAdnaseussIlacitcarPsdohteMtneidarGfosetaRecnegrevnoCnoitazimitpOcitsahcotS.svcitsinimreteDgnittiFataDrofsdohteMcitsahcotS-cit