We discuss two related asynchronous parallel stochastic methods. The
first (AsyRK) is based on a randomized Kaczmarz scheme for solving a
linear system Ax=b, which is identical to a standard stochastic
gradient process applied to the least-squares formulation min
||Ax-b||^2. The second (AsySPCD) is based on a randomized coordinate
descent method for composite convex optimization, which can also be
viewed as a type of stochastic gradient method, though this fact is
not used in the analysis. We analyze the expected convergence behavior
of both algorithms, showing that a threshold number of processors can
be identified below which near-linear speedup can be expected in the
parallel implementation. The analysis of AsySPCD pays particular
attention to the issue of "inconsistent reads," in which the partial
gradient may be evaluated at an iterate which never actually exists at
any point in time.
This talk represents joint work with Ji Liu and other colleagues at
UW-Madison.
Copyright. All Rights Reserved.