  Gradient descent is an important class of iterative algorithms for minimizing
convex functions. Classically, gradient descent has been a sequential and
synchronous process. Distributed and asynchronous variants of gradient descent
have been studied since the 1980s, and they have been experiencing a resurgence
due to demand from large-scale machine learning problems running on multi-core
processors.
  We provide a version of asynchronous gradient descent (AGD) in which
communication between cores is minimal and for which there is little
synchronization overhead. We also propose a new timing model for its analysis.
With this model, we give the first amortized analysis of AGD on convex
functions. The amortization allows for bad updates (updates that increase the
value of the convex function); in contrast, most prior work makes the strong
assumption that every update must be significantly improving.
  Typically, the step sizes used in AGD are smaller than those used in its
synchronous counterpart. We provide a method to determine the step sizes in AGD
based on the Hessian entries for the convex function. In certain circumstances,
the resulting step sizes are a constant fraction of those used in the
corresponding synchronous algorithm, enabling the overall performance of AGD to
improve linearly with the number of cores.
  We give two applications of our amortized analysis.
