Trading Computation for Communication: Distributed Stochastic Dual Coordinate Ascent

By Tianbao Yang. 2013

163 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Optimization & Training

Citations in the corpus

Federated Optimization: Distributed Optimization Beyond the Datacenter (2015, background): “Such algorithms perform a large amount of computation locally, before each round of communication, ideally balancing the cost of computation and communication[10, 11, 4, 7, 14].”
Central Server Free Federated Learning over Single-sided Trust Social Networks (2019, background): “…a multi-task learning framework for federated learning and its related optimization algorithm, which extends early works SDCA (Shalev-Shwartz and Zhang, 2013; Yang, 2013; Yang et al., 2013) and CO-COA (Jaggi et al., 2014; Ma et al., 2015; Smith et al., 2016) to the federated learning setting.”
COLA: Decentralized Linear Learning (2018, methodology): “In the distributed setting with a central server, algorithms of the C O C O A family [Yang, 2013, Jaggi et al., 2014, Ma et al., 2015, Dünner et al., 2018]—see [Smith et al., 2018] for a recent overview— are targeted for problems of the forms (A) and (B).”
Communication-Efficient Learning of Deep Networks from Decentralized Data (2016, background): “In the convex setting, the problem of distributed optimization and estimation has received significant attention [4, 15, 33], and some algorithms do focus specifically on communication efficiency [45, 34, 40, 27, 43].”
Federated Learning: Challenges, Methods, and Future Directions (2019, background): “the amount of computation versus communication substantially more ﬂexible. For convex objectives, distributed local-updating primal-dual methods have emerged as a popular way to tackle such a problem [54, 62, 72, 107, 128]. These approaches leverage duality structure to effectively decompose the glo”
CoCoA: A General Framework for Communication-Efficient Distributed Optimization (2016, methodology): “By making use of the primal-dual structure in the line of work of Yu et al. (2012); Pechyony et al. (2011); Yang (2013); Yang et al. (2013) and Lee and Roth (2015), the CoCoA -v1 and CoCoA frameworks (which are special cases of the presented framework, CoCoA ) are the ﬁrst to allow the use of any…”
AIDE: Fast and Communication Efficient Distributed Optimization (2016, methodology): “These methods are DANE [20], DISCO [23] and COCOA+ [11, 5, 12, 21].”
Communication-Efficient Distributed Optimization using an Approximate Newton-type Method (2013, methodology): “A similar dependence occurs with other recently-proposed algorithms for distributed optimization (e.g. Yang, 2013; Mahajan et al., 2013; Dekel et al., 2012; Cotter et al., 2011; Duchi et al., 2012).”
Bayesian Nonparametric Federated Learning of Neural Networks (2019, background): “Yet others explore distributed optimization with a specific emphasis on communication efficiency (Zhang et al., 2013; Shamir et al., 2014; Yang, 2013; Ma et al., 2015; Zhang & Lin, 2015).”
Federated Optimization: Distributed Machine Learning for On-Device Intelligence (2016, methodology): “The first version of the algorithm was proposed as DisDCA in [101], without convergence guarantees.”
Adding vs. Averaging in Distributed Primal-Dual Optimization (2015, methodology): “However, mini-batch versions of both SGD and coordinate descent (CD) (Richtárik & Takáč, 2013; Shalev-Shwartz & Zhang, 2013b; Yang, 2013; Qu & Richtárik, 2014; Qu et al., 2014) suffer from their convergence rate degrading towards the rate of batch gradient descent as the size of the mini-batch is in”
Communication Complexity of Distributed Convex Learning and Optimization (2015, background): “…multiple cores on a single CPU to large-scale and geographically distributed computing grids), distributed learning and optimization methods have been the focus of much research in recent years, with just a few examples including [23, 4, 2, 25, 1, 5, 12, 22, 15, 16, 8, 7, 9, 11, 19, 18, 3, 24].”
Communication-Efficient Distributed Dual Coordinate Ascent (2014, methodology): “We generalize the algorithm of [2, 3] by allowing the use of arbitrary (dual) optimization methods as the local subroutine within our framework.”
Distributed optimization with arbitrary local solvers (2015, background): “The framework therefore completely decouples the local solvers from the distributed communication.”
An asynchronous parallel stochastic coordinate descent algorithm (2013, background): “Then for ǫ > 0 and η ∈ (0 , 1) , we have that provided that one of the following conditions holds: In the essentially strongly convex case (3) with l > 0 , we require (cid:12)(cid:12)(cid:12)(cid:12) while in the general convex case, it suﬃces that”
GIANT: Globally Improved Approximate Newton Method for Distributed Optimization (2017, methodology): “…2016, Liu et al., 2015, Necoara and Clipici, 2016, Richt´arik and Tak´a v c, 2016) and dual coordinate ascent algorithms (Richt´arik and Tak´ac, 2016, Yang, 2013, Zheng et al., 2016) are two other classes of ﬁrst-order algorithms that are suitable for distributed settings but have high…”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, methodology): “However, mini-batch versions of both SGD and coordinate descent (CD) [151, 149, 164, 111, 188, 176, 150, 140, 141, 143, 38, 40] suffer from their convergence rate degrading towards the rate of batch gradient descent as the size of the mini-batch is increased.”
Partitioning Data on Features or Samples in Communication-Efficient Distributed Optimization? (2015, methodology): “Existing mehods o ften require a large amount of communication between computing nodes [17, 7, 9, 18], which is typically several ma gnitudes slower than reading data from their own memory [10].”
Distributed Mini-Batch SDCA (2015, methodology): “In this Section we will make use of the Expected Separable Overapproximation (ESO) theory introduced in [20] and further extended e.g. in [16, 19, 18].”