000253553 001__ 253553
000253553 005__ 20180712173137.0
000253553 037__ $$aSTUDENT
000253553 245__ $$aAsynchronous updates for stochastic gradient descent
000253553 260__ $$c2017-06-09
000253553 269__ $$a2017-06-09
000253553 336__ $$aStudent Projects
000253553 520__ $$aFinding convergence rates for numerical optimization algorithms is an important task, because it gives a justification to their use in solving practical problems, while also providing a way to compare their efficiency. This is especially useful in an asynchronous environment, because the algorithms are often proven to be more efficient than their synchronous counterparts by experience, but they lack the theory that justifies this property. Furthermore, analyzing the various issues that can arise when inconsistency is taken into consideration, it is possible to obtain a clearer picture of the downsides of inexact implementations one should be aware of. This work tries to address the problem of finding an expected convergence rate for the asynchronous version of the widely popular stochastic gradient descent algorithm, applied to the common class of problems that present a cost function with a sum structure. It follows a similar approach to the one suggested by R. Leblond, F. Pedregosa and S. Lacoste-Julien in "ASAGA: Asynchronous Parallel SAGA" (2016) [RLLJ16], also borrowing their formalization of asynchronicity. The main achievement of this work is a bound on the constant step size that guarantees convergence in expectation of the algorithm. The relative convergence rate is also obtained. The result is also partially validated by sequential models of an asynchronous environment. We hope that this can be a basis for future applications of the same approach to more specific algorithms and that numerical experiments on real multiprocessor architecture can be performed in the future to further validate the convergence rates.
000253553 700__ $$aChiappa, Alberto Silvio
000253553 720_2 $$0250586$$aStich, Sebastian Urban
000253553 720_2 $$0250160$$aJaggi, Martin
000253553 8560_ $$fsebastian.stich@epfl.ch
000253553 8564_ $$s784139$$uhttps://infoscience.epfl.ch/record/253553/files/report_pdf.pdf
000253553 8564_ $$s1690865$$uhttps://infoscience.epfl.ch/record/253553/files/report_pdfa.pdf
000253553 909C0 $$0252581$$mjennifer.bachmann-ona@epfl.ch$$pMLO$$xU13319
000253553 909CO $$ooai:infoscience.epfl.ch:253553$$pIC
000253553 960__ $$asebastian.stich@epfl.ch
000253553 961__ $$alaurence.gauvin@epfl.ch
000253553 980__ $$aSTUDENT
000253553 980__ $$bSemester assignment
000253553 981__ $$aoverwrite