Exact vs Inexact Gradient Methods Examples of Inexact Methods

-

English
81 pages
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

Description

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


Sujets

Informations

Publié par
Nombre de lectures 32
Langue English
Poids de l'ouvrage 1 Mo
Signaler un problème

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