A General Distributed Dual Coordinate Optimization Framework for Regularized Loss Minimization

By Shun Zheng, Jialei Wang, Fen Xia, Wei Xu, Tong Zhang. 2016

22 citations recorded by the source corpus.

In modern large-scale machine learning applications, the training data are often partitioned and stored on multiple machines. It is customary to employ the "data parallelism" approach, where the aggregated training loss is minimized without moving data across machines. In this paper, we introduce a novel distributed dual formulation for regularized loss minimization problems that can directly handle data parallelism in the distributed setting. This formulation allows us to systematically derive dual coordinate optimization procedures, which we refer to as Distributed Alternating Dual Maximization (DADM). The framework extends earlier studies described in (Boyd et al., 2011; Ma et al., 2015a; Jaggi et al., 2014; Yang, 2013) and has rigorous theoretical analyses. Moreover with the help of the new formulation, we develop the accelerated version of DADM (Acc-DADM) by generalizing the acceleration technique from (Shalev-Shwartz and Zhang, 2014) to the distributed setting. We also provide theoretical results for the proposed accelerated version and the new result improves previous ones (Yang, 2013; Ma et al., 2015a) whose runtimes grow linearly on the condition number. Our empirical studies validate our theory and show that our accelerated approach significantly improves the previous state-of-the-art distributed dual coordinate optimization algorithms.

How researchers see this paper

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

Citations in the corpus

On the Convergence of FedAvg on Non-IID Data (2019, background): “Traditional distributed machine learning employs a centralized approach which ﬁrst aggregates the training data on a single machine or in a data center and then performs model updates [7, 23, 36, 19, 20, 26, 40, 25].”
GIANT: Globally Improved Approximate Newton Method for Distributed Optimization (2017, methodology): “…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 communication costs.”
Distributed block-diagonal approximation methods for regularized empirical risk minimization (2017, methodology): “Recently, Zheng et al. (2017) adopted for DisDCA an acceleration technique in Lin et al. (2015); Shalev-Shwartz and Zhang (2016), resulting in a theoretically faster algorithm.”
L1-Regularized Distributed Optimization: A Communication-Efficient Primal-Dual Framework (2015, background): “However, by solving the problem in the dual, COCOA+ (like SDCA, prox-SDCA, and numerous other primal-dual methods [26, 27, 30, 35, 36]) is only equipped to handle strongly convex regularizers, which prevents it from being directly applied to L1-regularized objectives.”
A Distributed Second-Order Algorithm You Can Trust (2018, background): “Approaches such as (Yang, 2013; Jaggi et al., 2014; Zhang & Lin, 2015; Zheng et al., 2017; Wang et al., 2017) are restricted to strongly-convex regularizers, and typically work on the dual formulation of the objective.”