//img.uscri.be/pth/6541483f2aa6f2f7d36a2001b1b6b4dfe1c6d59a
Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

Exact vs Inexact Gradient Methods Examples of Inexact Methods

De
81 pages
Exact vs. Inexact Gradient Methods Examples of Inexact Methods Convergence Rate Analysis Numerical Experiments Inexact Gradient and Proximal-Gradient Methods Mark Schmidt1 Joint work with Nicolas Le Roux1, Francis Bach1, and Michael Friedlander2 1CNRS/INRIA/ENS 2University of British Columbia November 2011 Mark Schmidt Inexact Gradient and Proximal-Gradient Methods

  • british columbia

  • inexact gradient

  • convergence rate

  • experiments

  • analysis numerical

  • proximal-gradient methods


Voir plus Voir moins

November2011

1
CNRS/INRIA/ENS
2
UniversityofBritishColumbia

MarkSchmidt
1

JointworkwithNicolasLeRoux
1
,FrancisBach
1
,andMichaelFriedlander
2

InexactGradientandProximal-GradientMethods

sdohteMtneidarG-lamixorPdnatneidarGtcaxenItdimhcSkraMstnemirepxElaciremuNsisylanAetaRecnegrevnoCsdohteMtcaxenIfoselpmaxEsdohteMtneidarGtcaxenI.svtcaxE
ExamplesofInexactMethods

v2

n1

oExactvs.InexactGradientMethods

COutline

sdohteMtcaxenIfoselpmaxEsdohteMtneidarGtcaxenI.svtcaxEsdohteMtneidarG-lamixorPdnatneidarGtcaxenItdimhcSkraMstnemirepxElaciremuNsisylanAetaRecnNumericalExperiments

e4

gConvergenceRateAnalysis

r3

e
Shouldweuse
AlgorithmS
or

AlgorithmD
?

AlgorithmSvs.AlgorithmD:

Errorvs.Iteration

AlgorithmSvs.AlgorithmD
HybridMethods
ConvergenceRatesofFirst-OrderMethods

stnemirepxElaciremuNsisylanAetaRecnegrevnoCsdohteMtcaxenIfoselpmaxEsdohteMtneidarGtcaxenI.svtcaxEsdohteMtneidarG-lamixorPdnatneidarGtcaxenItdimhcSkraM.k2/1fororrenasahDmhtiroglA,knoitaretinO.k/1fororrenasahSmhtiroglA,knoitaretinO
Shouldweuse
AlgorithmS
or
AlgorithmD
?

Oniteration
k
,
AlgorithmS
hasanerrorof1
/
k
.
Oniteration
k
,
AlgorithmD
hasanerrorof1
/
2
k
.

AlgorithmSvs.AlgorithmD:Errorvs.Iteration

sdohteMtneidarG-lamixorPdnatneidarGtcaxenItdimhcSkraMsdohteMredrO-tsriFfosetaRecnegrevnoCsdohteMdirbyHDmhtiroglA.svSmhtiroglAstnemirepxElaciremuNsisylanAetaRecnegrevnoCsdohteMtcaxenIfoselpmaxEsdohteMtneidarGtcaxenI.svtcaxE
sdohteMredrO-tsShouldweuse
AlgorithmS
or
AlgorithmD
?

rOniteration
k
,
AlgorithmS
hasanerrorof1
/
k
.
Oniteration
k
,
AlgorithmD
hasanerrorof1
/
2
k
.

iAlgorithmSvs.AlgorithmD:Errorvs.Iteration

FfosetaRecnegrevnoCsdohteMdirbyHDmhtiroglA.svSmhtiroglAstnemirepxElaciremuNsisylanAetaRecnegrevnoCsdohteMtcaxenIfoselpmaxEsdohteMtneidarGtcaxenI.svtcaxEsdohteMtneidarG-lamixorPdnatneidarGtcaxenItdimhcSkraM
But,theerrorisnotthewholestory:

AlgorithmSvs.AlgorithmD:Error

.sv

emiT

sdohteMtneidarG-lamixorPdnatneidarGtcaxenItdimhcSkraM.evisnepxeeraDmhtiroglAfosnoitaretI.paehceraSmhtiroglAfosnoitaretIsdohteMredrO-tsriFfosetaRecnegrevnoCsdohteMdirbyHDmhtiroglA.svSmhtiroglAstnemirepxElaciremuNsisylanAetaRecnegrevnoCsdohteMtcaxenIfoselpmaxEsdohteMtneidarGtcaxenI.svtcaxE
But,theerrorisnotthewholestory:

Iterationsof
AlgorithmD
are
expensive
.

Iterationsof
AlgorithmS
are
cheap
.

AlgorithmSvs.AlgorithmD:Errorvs.Time

sdohteMredrO-tsriFfosetaRecnegrevnoCsdohteMdirbyHDmhtiroglA.svSmhtiroglAstnemirepxElaciremuNsisylanAetaRecnegrevnoCsdohteMtcaxenIfoselpmaxEsdohteMtneidarGtcaxenI.svtcaxEsdohteMtneidarG-lamixorPdnatneidarGtcaxenItdimhcSkraM
But,theerrorisnotthewholestory:

Iterationsof
AlgorithmD
are
expensive
.

Iterationsof
AlgorithmS
are
cheap
.

AlgorithmSvs.AlgorithmD:Errorvs.Time

sdohteMtneidarG-lamixorPdnatneidarGtcaxenItdimhcSkraMsdohteMredrO-tsriFfosetaRecnegrevnoCsdohteMdirbyHDmhtiroglA.svSmhtiroglAstnemirepxElaciremuNsisylanAetaRecnegrevnoCsdohteMtcaxenIfoselpmaxEsdohteMtneidarGtcaxenI.svtcaxE
Determinstic
makessteadyprogress,butisexpensive.

Stochastic
makesgreatprogressinitially,butslowsdown.

Stochasticvs.Deterministic:

MotivationforHybridMethods

sdohteMredrO-tsriFfosetaRecnegrevnoCsdohteMdirbyHDmhtiroglA.svSmhtiroglAstnemirepxElaciremuNsisylanAetaRecnegrevnoCsdohteMtcaxenIfoselpmaxEsdohteMtneidarGtcaxenI.svtcaxEsdohteMtneidarG-lamixorPdnatneidarGtcaxenItdimhcSkraM?sdlrowhtobfotsebehttegdohtemdirbyhanaC
Cana
hybrid
methodgetthebestofbothworlds?

Determinstic
makessteadyprogress,butisexpensive.

Stochastic
makesgreatprogressinitially,butslowsdown.

Stochasticvs.Deterministic:

MotivationforHybridMethods

sdohteMtneidarG-lamixorPdnatneidarGtcaxenItdimhcSkraMsdohteMredrO-tsriFfosetaRecnegrevnoCsdohteMdirbyHDmhtiroglA.svSmhtiroglAstnemirepxElaciremuNsisylanAetaRecnegrevnoCsdohteMtcaxenIfoselpmaxEsdohteMtneidarGtcaxenI.svtcaxE