  This paper presents fault-tolerant asynchronous Stochastic Gradient Descent
(SGD) algorithms. SGD is widely used for approximating the minimum of a cost
function $Q$, as a core part of optimization and learning algorithms. Our
algorithms are designed for the cluster-based model, which combines
message-passing and shared-memory communication layers. Processes may fail by
crashing, and the algorithm inside each cluster is wait-free, using only reads
and writes.
  For a strongly convex function $Q$, our algorithm tolerates any number of
failures, and provides convergence rate that yields the maximal distributed
acceleration over the optimal convergence rate of sequential SGD.
  For arbitrary functions, the convergence rate has an additional term that
depends on the maximal difference between the parameters at the same iteration.
(This holds under standard assumptions on $Q$.) In this case, the algorithm
obtains the same convergence rate as sequential SGD, up to a logarithmic
factor. This is achieved by using, at each iteration, a multidimensional
approximate agreement algorithm, tailored for the cluster-based model.
  The algorithm for arbitrary functions requires that at least a majority of
the clusters contain at least one nonfaulty process. We prove that this
condition is necessary when optimizing some non-convex functions.
