CoCoA: A General Framework for Communication-Efficient Distributed Optimization

By Virginia Smith, Simone Forte, Chenxin Ma, Martin Takác, Michael I. Jordan, Martin Jaggi. 2016

285 citations recorded by the source corpus.

The scale of modern datasets necessitates the development of efficient distributed optimization methods for machine learning. We present a general-purpose framework for distributed computing environments, CoCoA, that has an efficient communication scheme and is applicable to a wide variety of problems in machine learning and signal processing. We extend the framework to cover general non-strongly-convex regularizers, including L1-regularized problems like lasso, sparse logistic regression, and elastic net regularization, and show how earlier work can be derived as a special case. We provide convergence guarantees for the class of convex regularized loss minimization objectives, leveraging a novel approach in handling non-strongly-convex regularizers and non-smooth loss functions. The resulting framework has markedly improved performance over state-of-the-art methods, as we illustrate with an extensive set of experiments on real distributed datasets.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Networks and Communications, Optimization & Training, Federated & Distributed Learning

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 Theory and Mathematics

In Computer Networks and Communications

In Optimization & Training

In Federated & Distributed Learning

Citations in the corpus

Federated Optimization in Heterogeneous Networks (2018, methodology): “Large-scale machine learning, particularly in data center settings, has motivated the development of numerous distributed optimization methods in the past decade (see, e.g., Boyd et al., 2010; Dekel et al., 2012; Dean et al., 2012; Zhang et al., 2013; Li et al., 2014a; Shamir et al., 2014; Reddi et ”
Communication Efficient Decentralized Training with Multiple Local Updates (2019, background): “An orthogonal one is to pay more local computation for less communication, e.g., one-shot aggregation [53, 54, 16, 21, 46], primal-dual algorithms [37, 38, 7] and distributed Newton methods [33, 52, 29, 35, 25].”
SCAFFOLD: Stochastic Controlled Averaging for On-Device Federated Learning (2019, methodology): “For well structured convex problems, CoCoA uses the dual variable as the control variates, enabling ﬂexible distributed methods (Smith et al., 2016).”
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.”
FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization (2019, background): “…in distributed learning has recently gained considerable attention for both master-worker [Alistarh et al., 2017, Bernstein et al., 2018, Seide et al., 2014, Smith et al., 2016] and masterless topologies [Koloskova et al., 2019, Reisizadeh et al., 2019a, Wang et al., 2019, Zhang et al., 2018].”
On the Convergence of FedAvg on Non-IID Data (2019, background): “The primal-dual algorithms [6, 26, 27] are more generally applicable and more relevant to FL.”
Fair Resource Allocation in Federated Learning (2019, background): “…learning faces challenges such as expensive communication, systems heterogeneity (e.g., variability in hardware or network connection) and statistical heterogeneity (i.e., diﬀering local data distributions per device), making it distinct from classical distributed optimization [32, 35, 39].”
Communication trade-offs for synchronized distributed SGD with large step size (2019, background): “Some of them are Boyd et al. (2011) (ADMM), Shamir et al. (2014) (DANE), Zhang and Xiao (2015) (DiSCO), Reddi et al. (2016) (AIDE), Ma et al. (2017); Smith et al. (2016); Ma et al. (2015) (COCOA) and some of the references therein.”
Expanding the Reach of Federated Learning by Reducing Client Resource Requirements (2018, background): “Communication-efﬁcient distributed learning Distributed learning is known to suffer from communication over-heads associated with the frequent gradient updates exchanged among nodes [Wang et al., 2018, Dean et al., 2012, Smith et al., 2018, Reddi et al., 2016].”
Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms (2018, methodology): “A natural idea is to allow workers to perform τ local updates to the model instead of just computing gradients, and then periodically averaging the local models (Moritz et al., 2015; Zhang et al., 2016; Povey et al., 2014; Su & Chen, 2015; Chaudhari et al., 2017; Smith et al., 2018; Lin et al., 2018”
COLA: Decentralized Linear Learning (2018, methodology): “Following the setup of [Dünner et al., 2016, Smith et al., 2018], these training problems can be mapped to either of the two following formulations, which are dual to each other ⇥ P where f ⇤ , g ⇤ i are the convex conjugates of f and g i , respectively.”
Federated Multi-Task Learning (2017, background): “Compared to [49, 30] which assumes θ t = θ < 1, our assumption is significantly less restrictive and better models the federated setting, where nodes are unreliable and may periodically drop out.”
FedDANE: A Federated Newton-Type Method (2019, background): “For example, COCOA [12] is a communication-efﬁcient primal-dual framework that leverages duality to decompose the global objective into subproblems that can be solved inexactly.”
Federated Learning: Challenges, Methods, and Future Directions (2019, methodology): “For convex objectives, distributed local updating primaldual methods have emerged as a popular way to tackle such a problem [43].”
Age-Based Scheduling Policy for Federated Learning in Mobile Edge Networks (2019, background): “Due to the sheer volume of data generated by the end-user devices, as well as the increasing concerns about sharing private information, a new machine learning model, namely the federated learning (FL) [1–4], has emerged from the intersection of artiﬁcial intelligence and edge computing [5–7].”
Scheduling Policies for Federated Learning in Wireless Networks (2019, neutral): “of (64) by ε and noticing that E[D(v0)−D(v∗)] < n [37].”
GIANT: Globally Improved Approximate Newton Method for Distributed Optimization (2017, methodology): “However, in comparison, GIANT has some major advantages over the prior works DANE, AIDE, CoCoA (Smith et al., 2016), and DiSCO (Zhang and Lin, 2015).”