Avoiding Communication in Proximal Methods for Convex Optimization
  Problems
  The fast iterative soft thresholding algorithm (FISTA) is used to solve
convex regularized optimization problems in machine learning. Distributed
implementations of the algorithm have become popular since they enable the
analysis of large datasets. However, existing formulations of FISTA communicate
data at every iteration which reduces its performance on modern distributed
architectures. The communication costs of FISTA, including bandwidth and
latency costs, is closely tied to the mathematical formulation of the
algorithm. This work reformulates FISTA to communicate data at every k
iterations and reduce data communication when operating on large data sets. We
formulate the algorithm for two different optimization methods on the Lasso
problem and show that the latency cost is reduced by a factor of k while
bandwidth and floating-point operation costs remain the same. The convergence
rates and stability properties of the reformulated algorithms are similar to
the standard formulations. The performance of communication-avoiding FISTA and
Proximal Newton methods is evaluated on 1 to 1024 nodes for multiple benchmarks
and demonstrate average speedups of 3-10x with scaling properties that
outperform the classical algorithms.
