Analysis of Distributed Stochastic Dual Coordinate Ascent

By Tianbao Yang, Shenghuo Zhu, Rong Jin, Yuanqing Lin. 2013

19 citations recorded by the source corpus.

In \citep{Yangnips13}, the author presented distributed stochastic dual coordinate ascent (DisDCA) algorithms for solving large-scale regularized loss minimization. Extraordinary performances have been observed and reported for the well-motivated updates, as referred to the practical updates, compared to the naive updates. However, no serious analysis has been provided to understand the updates and therefore the convergence rates. In the paper, we bridge the gap by providing a theoretical analysis of the convergence rates of the practical DisDCA algorithm. Our analysis helped by empirical studies has shown that it could yield an exponential speed-up in the convergence by increasing the number of dual updates at each iteration. This result justifies the superior performances of the practical DisDCA as compared to the naive variant. As a byproduct, our analysis also reveals the convergence behavior of the one-communication DisDCA.

Subfields: Artificial Intelligence, Computational Mechanics

How researchers see this paper

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

In Artificial Intelligence

In Computational Mechanics

Citations in the corpus

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.”
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 first to allow the use of any…”
Adding vs. Averaging in Distributed Primal-Dual Optimization (2015, methodology): “By making use of the primal-dual structure in the line of work of (Yu et al., 2012; Shalev-Shwartz & Zhang, 2013c; Yang, 2013; Yang et al., 2013; Jaggi et al., 2014), the C O C O A framework as well as the extension here allow to have more control over the meaningful aggregation of updates between…”
Distributed optimization with arbitrary local solvers (2015, background): “The work of [71] has provided the ﬁrst theoretical convergence analysis for an ideal case, when the distributed data parts are all orthogonal to each other — an unrealistic setting in practice.”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, methodology): “The work of [189] has provided the first theoretical convergence analysis for an ideal case, when the distributed data parts are all orthogonal to each other, which is an unrealistic setting in practice.”
An efficient distributed learning algorithm based on effective local functional approximations (2013, methodology): “, 2014) represents the class of distributed dual methods (Pechyony et al., 2011; Yang, 2013; Yang et al., 2013; Jaggi et al., 2014) that, in each outer iteration, solve (in parallel) several local dual optimization problems.”
Quartz: Randomized Dual Coordinate Ascent with Arbitrary Sampling (2015, background): “1 Quartz vs DiSDCA A distributed variant of SDCA, named DisDCA, has been proposed in [34] and analyzed in [35].”
Partitioning Data on Features or Samples in Communication-Efficient Distributed Optimization? (2015, methodology): “The original DiSCO algorithm [Communication-Efficient Distributed Optimization of SelfConcordant Empirical Loss, Yuchen Zhang and Lin Xiao, 2015]partitions the input data based on samples.”
A General Distributed Dual Coordinate Optimization Framework for Regularized Loss Minimization (2016, background): “In this section, we first present proofs about several previous propositions to establish our framework solidly.”