Optimization Online


Distributed Stochastic Variance Reduced Gradient Methods and a Lower Bound for Communication Complexity

Jason Lee(jasondlee***at***berkeley.edu)
Qihang Lin(qihang-lin***at***uiowa.edu)
Tengyu Ma(tengyu***at***cs.princeton.edu)
Tianbao Yang(tianbao-yang***at***uiowa.edu)

Abstract: We study distributed optimization algorithms for minimizing the average of convex functions. The applications include empirical risk minimization problems in statistical machine learning where the datasets are large and have to be stored on different machines. We design a distributed stochastic variance reduced gradient algorithm that, under certain conditions on the condition number, simultaneously achieves the optimal parallel runtime, amount of communication and rounds of communication among all distributed first-order methods up to constant factors. Our method and its accelerated extension also outperform existing distributed algorithms in terms of the rounds of communication as long as the condition number is not too large compared to the size of data in each machine. We also prove a lower bound for the number of rounds of communication for a broad class of distributed first-order methods including the proposed algorithms in this paper. We show that our accelerated distributed stochastic variance reduced gradient algorithm achieves this lower bound so that it uses the fewest rounds of communication among all distributed first-order algorithms.

Keywords: Distributed Optimization; Communication Complexity; Machine Learning; First-Order Method

Category 1: Convex and Nonsmooth Optimization

Category 2: Nonlinear Optimization

Citation: Technical Report. Dec, 2015.

Download: [PDF]

Entry Submitted: 12/27/2015
Entry Accepted: 12/27/2015
Entry Last Modified: 12/27/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society