COLA: Decentralized Linear Learning

Introduction

With the immense growth of data, decentralized machine learning has become not only attractive but a necessity. Personal data from, for example, smart phones, wearables and many other mobile devices is sensitive and exposed to a great risk of data breaches and abuse when collected by a centralized authority or enterprise. Nevertheless, many users have gotten accustomed to giving up control over their data in return for useful machine learning predictions (e.g. recommendations), which benefits from joint training on the data of all users combined in a centralized fashion.

In contrast, decentralized learning aims at learning this same global machine learning model, without any central server. Instead, we only rely on distributed computations of the devices themselves, with each user’s data never leaving its device of origin. While increasing research progress has been made towards this goal, major challenges in terms of the privacy aspects as well as algorithmic efficiency, robustness and scalability remain to be addressed. Motivated by aforementioned challenges, we make progress in this work addressing the important problem of training generalized linear models in a fully decentralized environment.

In this paper, our main contribution is to propose CoLa, a new decentralized framework for training generalized linear models with convergence guarantees. Our scheme resolves both described issues in existing approaches, using techniques from primal-dual optimization, and can be seen as a generalization of CoCoA (Smith et al., 2018) to the decentralized setting. More specifically, the proposed algorithm offers

Convergence Guarantees: Linear and sublinear convergence rates are guaranteed for strongly convex and general convex objectives respectively. Our results are free of the restrictive assumptions made by stochastic methods (Zhang et al., 2015; Wang et al., 2017), which requires i.i.d. data distribution over all devices.

Communication Efficiency and Usability: Employing a data-local subproblem between each communication round, CoLa not only achieves communication efficiency but also allows the re-use of existing efficient single-machine solvers for on-device learning. We provide practical decentralized primal-dual certificates to diagnose the learning progress.

Elasticity and Fault Tolerance: Unlike sum-structured approaches such as SGD, CoLa is provably resilient to changes in the data, in the network topology, and participating devices disappearing, straggling or re-appearing in the network.

Our implementation is publicly available under github.com/epfml/cola .

1 Problem statement

Setup. Many machine learning and signal processing models are formulated as a composite convex optimization problem of the form

where $l$ is a convex loss function of a linear predictor over data and $r$ is a convex regularizer. Some cornerstone applications include e.g. logistic regression, SVMs, Lasso, generalized linear models, each combined with or without L1, L2 or elastic-net regularization. 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

The spectral properties of $\mathcal{W}$ used in this paper are that the eigenvalues of $\mathcal{W}$ are real, and $1=\lambda_{1}(\mathcal{W})\geq\cdots\geq\lambda_{n}(\mathcal{W})\geq-1$. Let the second largest magnitude of the eigenvalues of $\mathcal{W}$ be $\beta:=\max\{|\lambda_{2}(\mathcal{W})|,|\lambda_{n}(\mathcal{W})|\}$. $1-\beta$ is called the spectral gap, a quantity well-studied in graph theory and network analysis. The spectral gap measures the level of connectivity among nodes. In the extreme case when $\mathcal{W}$ is diagonal, and thus an identity matrix, the spectral gap is 0 and there is no communication among nodes. To ensure convergence of decentralized algorithms, we impose the standard assumption of positive spectral gap of the network which includes all connected graphs, such as e.g. a ring or 2-D grid topology, see also Appendix B for details.

2 Related work

Research in decentralized optimization dates back to the 1980s with the seminal work of Bertsekas and Tsitsiklis, cf. (Tsitsiklis et al., 1986). Their framework focuses on the minimization of a (smooth) function by distributing the components of the parameter vector ${\bf x}$ among agents. In contrast, a second more recent line of work (Nedic and Ozdaglar, 2009; Duchi et al., 2012; Shi et al., 2015; Mokhtari and Ribeiro, 2016; Nedic et al., 2017; Scaman et al., 2017, 2018) considers minimization of a sum of individual local cost-functions $F({\bf x})=\sum_{i}F_{i}({\bf x})$, which are potentially non-smooth. Our work here can be seen as bridging the two scenarios to the primal-dual setting (A) and (B).

While decentralized optimization is a relatively mature area in the operations research and automatic control communities, it has recently received a surge of attention for machine learning applications, see e.g. (Cevher et al., 2014). Decentralized gradient descent (DGD) with diminishing stepsizes was proposed by (Nedic and Ozdaglar, 2009; Jakovetic et al., 2012), showing convergence to the optimal solution at a sublinear rate. (Yuan et al., 2016) further prove that DGD will converge to the neighborhood of a global optimum at a linear rate when used with a constant stepsize for strongly convex objectives. (Shi et al., 2015) present EXTRA, which offers a significant performance boost compared to DGD by using a gradient tracking technique. (Nedic et al., 2017) propose the DIGing algorithm to handle a time-varying network topology. For a static and symmetric $\mathcal{W}$, DIGing recovers EXTRA by redefining the two mixing matrices in EXTRA. The dual averaging method (Duchi et al., 2012) converges at a sublinear rate with a dynamic stepsize. Under a strong convexity assumption, decomposition techniques such as decentralized ADMM (DADMM, also known as consensus ADMM) have linear convergence for time-invariant undirected graphs, if subproblems are solved exactly (Shi et al., 2014; Wei and Ozdaglar, 2013). DADMM+ (Bianchi et al., 2016) is a different primal-dual approach with more efficient closed-form updates in each step (as compared to ADMM), and is proven to converge but without a rate. Compared to CoLa, neither of DADMM and DADMM+ can be flexibly adapted to the communication-computation tradeoff due to their fixed update definition, and both require additional hyperparameters to tune in each use-case (including the $\rho$ from ADMM). Notably CoLa shows superior performance compared to DIGing and decentralized ADMM in our experiments. (Scaman et al., 2017, 2018) present lower complexity bounds and optimal algorithms for objectives in the form $F({\bf x})=\sum_{i}F_{i}({\bf x})$. Specifically, (Scaman et al., 2017) assumes each $F_{i}({\bf x})$ is smooth and strongly convex, and (Scaman et al., 2018) assumes each $F_{i}({\bf x})$ is Lipschitz continuous and convex. Additionally (Scaman et al., 2018) needs a boundedness constraint for the input problem. In contrast, CoLa can handle non-smooth and non-strongly convex objectives (A) and (B), suited to the mentioned applications in machine learning and signal processing. For smooth nonconvex models, (Lian et al., 2017) demonstrate that a variant of decentralized parallel SGD can outperform the centralized variant when the network latency is high. They further extend it to the asynchronous setting (Lian et al., 2018) and to deal with large data variance among nodes (Tang et al., 2018a) or with unreliable network links (Tang et al., 2018b). For the decentralized, asynchronous consensus optimization, (Wu et al., 2018) extends the existing PG-EXTRA and proves convergence of the algorithm. (Sirb and Ye, 2018) proves a $O(K/\epsilon^{2})$ rate for stale and stochastic gradients. (Lian et al., 2018) achieves $O(1/\epsilon)$ rate and has linear speedup with respect to number of workers.

In the distributed setting with a central server, algorithms of the CoCoA 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). For convex models, CoCoA has shown to significantly outperform competing methods including e.g., ADMM, distributed SGD etc. Other centralized algorithm representatives are parallel SGD variants such as (Agarwal and Duchi, 2011; Zinkevich et al., 2010) and more recent distributed second-order methods (Zhang and Lin, 2015; Reddi et al., 2016; Gargiani, 2017; Lee and Chang, 2017; Dünner et al., 2018; Lee et al., 2018).

In this paper we extend CoCoA to the challenging decentralized environment—with no central coordinator—while maintaining all of its nice properties. We are not aware of any existing primal-dual methods in the decentralized setting, except the recent work of (Smith et al., 2017) on federated learning for the special case of multi-task learning problems. Federated learning was first described by (Konecnỳ et al., 2015, 2016; McMahan et al., 2017) as decentralized learning for on-device learning applications, combining a global shared model with local personalized models. Current federated optimization algorithms (like FedAvg in (McMahan et al., 2017)) are still close to the centralized setting. In contrast, our work provides a fully decentralized alternative algorithm for federated learning with generalized linear models.

The decentralized algorithm: CoLa

The CoLa framework is summarized in Algorithm 1. For a given input problem we map it to either of the (A) or (B) formulation, and define the locally stored dataset $\mathbf{A}_{[k]}$ and local part of the weight vector $\mathbf{x}_{[k]}$ in node $k$ accordingly. While ${\bf v}=\mathbf{A}\mathbf{x}$ is the shared state being communicated in CoCoA, this is generally unknown to a node in the fully decentralized setting. Instead, we maintain ${\bf v}_{k}$, a local estimate of ${\bf v}$ in node $k$, and use it as a surrogate in the algorithm.

New data-local quadratic subproblems. During a computation step, node $k$ locally solves the following minimization problem

Algorithm description. At time $t$ on node $k$, ${\bf v}^{(t+\frac{1}{2})}_{k}$ is a local estimate of the shared variable after a communication step (i.e. gossip mixing). The local subproblem (1) based on this estimate is solved and yields $\Delta{\bf x}_{[k]}$. Then we calculate $\Delta{\bf v}_{k}:=\mathbf{A}_{[k]}\Delta{\bf x}_{[k]}$, and update the local shared vector ${\bf v}^{(t+1)}_{k}$. We allow the local subproblem to be solved approximately:

Let $\Theta\in$ be the relative accuracy of the local solver (potentially randomized), in the sense of returning an approximate solution $\Delta{\bf x}_{[k]}$ at each step $t$, s.t.

Real-world communication networks are not homogeneous and static, but greatly vary in availability, computation, communication and storage capacity. Also, the training data is subject to changes. While these issues impose significant challenges for most existing distributed training algorithms, we hereby show that CoLa offers adaptivity to such dynamic and heterogenous scenarios.

Scalability and elasticity in terms of availability and computational capacity can be modelled by a node-specific local accuracy parameter $\Theta_{k}$ in Assumption 1, as proposed by (Smith et al., 2017). The more resources node $k$ has, the more accurate (smaller) $\Theta_{k}$ we can use. The same mechanism also allows dealing with fault tolerance and stragglers, which is crucial e.g. on a network of personal devices. More specifically, when a new node $k$ joins the network, its ${\bf x}_{[k]}$ variables are initialized to ${\bf 0}$; when node $k$ leaves, its ${\bf x}_{[k]}$ is frozen, and its subproblem is not touched anymore (i.e. $\Theta_{k}=1$). Using the same approach, we can adapt to dynamic changes in the dataset—such as additions and removal of local data columns—by adjusting the size of the local weight vector accordingly. Unlike gradient-based methods and ADMM, CoLa does not require parameter tuning to converge, increasing resilience to drastic changes.

Extension to improved second-order subproblems. In the centralized setting, it has recently been shown that the Hessian information of $f$ can be properly utilized to define improved local subproblems (Lee and Chang, 2017; Dünner et al., 2018). Similar techniques can be applied to CoLa as well, details on which are left in Appendix E.

Extension to time-varying graphs. Similar to scalability and elasticity, it is also straightforward to extend CoLa to a time varying graph under proper assumptions. If we use the time-varying model in (Nedic et al., 2017, Assumption 1), where an undirected graph is connected with $B$ gossip steps, then changing CoLa to perform $B$ communication steps and one computation step per round still guarantees convergence. Details of this setup are provided in Appendix E.

On the convergence of CoLa

In this section we present a convergence analysis of the proposed decentralized algorithm CoLa for both general convex and strongly convex objectives. In order to capture the evolution of CoLa, we reformulate the original problem (A) by incorporating both $\mathbf{x}$ and local estimates $\{{\bf v}_{k}\}_{k=1}^{K}$

While the consensus is not always satisfied during Algorithm 1, the following relations between the decentralized objective and the original one (A) always hold. All proofs are deferred to Appendix C.

Let $\{\mathbf{v}_{k}\}$ and $\mathbf{x}$ be the iterates generated during the execution of Algorithm 1. At any timestep, it holds that

The dual problem and duality gap of the decentralized objective (DA) are given in Lemma 2.

The Lagrangian dual of the decentralized formation (DA) is

Given primal variables $\{\mathbf{x},\{\mathbf{v}_{k}\}_{k=1}^{K}\}$ and dual variables $\{\mathbf{w}_{k}\}_{k=1}^{K}$, the duality gap is:

If the dual variables are fixed to the optimality condition $\mathbf{w}_{k}=\nabla f(\mathbf{v}_{k})$, then the dual variables can be omitted in the argument list of duality gap, namely $G_{\mathcal{H}}(\mathbf{x},\{\mathbf{v}_{k}\}_{k=1}^{K})$. Note that the decentralized duality gap generalizes the duality gap of CoCoA: when consensus is ensured, i.e., $\mathbf{v}_{k}\equiv\mathbf{A}\mathbf{x}$ and $\mathbf{w}_{k}\equiv\nabla f(\mathbf{A}\mathbf{x})$, the decentralized duality gap recovers that of CoCoA.

We use the following data-dependent quantities in our main theorems

If $\{g_{i}\}$ are strongly convex, CoLa achieves the following linear rate of convergence.

Consider Algorithm 1 with $\gamma:=1$ and let $\Theta$ be the quality of the local solver in Assumption 1. Let $g_{i}$ be $\mu_{g}$-strongly convex for all $i\in[n]$ and let $f$ be $1/\tau$-smooth. Let $\bar{\sigma}^{\prime}:=(1+\beta)\sigma^{\prime}$, $\alpha:=(1+\frac{(1-\beta)^{2}}{36(1+\Theta)\beta})^{-1}$ and $\eta:=\gamma(1-\Theta)(1-\alpha)$

Then after $T$ iterations of Algorithm 1 with$\varepsilon^{(0)}_{\mathcal{H}}:=\mathcal{H}_{A}(\mathbf{x}^{(0)},\{\mathbf{v}_{k}^{(0)}\}_{k=1}^{K})-\mathcal{H}_{A}(\mathbf{x}^{\star},\{{\mathbf{v}_{k}^{\star}}\}_{k=1}^{K})$ is the initial suboptimality.

2 Sublinear rate for general convex objectives

Models such as sparse logistic regression, Lasso, group Lasso are non-strongly convex. For such models, we show that CoLa enjoys a $\mathcal{O}(1/T)$ sublinear rate of convergence for all network topologies with a positive spectral gap.

Consider Algorithm 1, using a local solver of quality $\Theta$. Let $g_{i}(\cdot)$ have $L$-bounded support, and let $f$ be $(1/\tau)$-smooth. Let $\varepsilon_{G_{\mathcal{H}}}>0$ be the desired duality gap. Then after $T$ iterations where

and $\bar{\sigma}^{\prime}:=(1+\beta)\sigma^{\prime}$, $\alpha:=(1+\frac{(1-\beta)^{2}}{36(1+\Theta)\beta})^{-1}$ and $\eta:=\gamma(1-\Theta)(1-\alpha)$. We have that the expected duality gap satisfies

at the averaged iterate $\bar{\mathbf{x}}:=\frac{1}{T-T_{0}}\sum_{t=T_{0}+1}^{T-1}\mathbf{x}^{(t)}$, and $\mathbf{v}_{k}^{\prime}:=\sum_{l=1}^{K}\mathcal{W}_{kl}\mathbf{v}_{l}$ and $\bar{\mathbf{v}}_{k}:=\frac{1}{T-T_{0}}\sum_{t=T_{0}+1}^{T-1}(\mathbf{v}_{k}^{\prime})^{(t)}$ and $\bar{\mathbf{w}}_{k}:=\frac{1}{T-T_{0}}\sum_{t=T_{0}+1}^{T-1}\nabla f((\mathbf{v}_{k}^{\prime})^{(t)})$.

Note that the assumption of bounded support for the $g_{i}$ functions is not restrictive in the general convex case, as discussed e.g. in (Dünner et al., 2016).

3 Local certificates for global accuracy

Accuracy certificates for the training error are very useful for practitioners to diagnose the learning progress. In the centralized setting, the duality gap serves as such a certificate, and is available as a stopping criterion on the master node. In the decentralized setting of our interest, this is more challenging as consensus is not guaranteed. Nevertheless, we show in the following Proposition 1 that certificates for the decentralized objective (DA) can be computed from local quantities:

Assume $g_{i}$ has $L$-bounded support, and let $\mathcal{N}_{k}:=\{j:\mathcal{W}_{jk}>0\}$ be the set of nodes accessible to node $k$. Then for any given $\varepsilon>0$, we have

if for all $k=1,\ldots,K$ the following two local conditions are satisfied:

The local conditions (9) and (10) have a clear interpretation. The first one ensures the duality gap of the local subproblem given by $\mathbf{v}_{k}$ as on the left hand side of (9) is small. The second condition (10) guarantees that consensus violation is bounded, by ensuring that the gradient of each node is similar to its neighborhood nodes.

The resulting certificate from Proposition 1 is local, in the sense that no global vector aggregations are needed to compute it. For a certificate on the global objective, the boolean flag of each local condition (9) and (10) being satisfied or not needs to be shared with all nodes, but this requires extremely little communication. Exact values of the parameters $\beta$ and $\sum_{k=1}^{K}n_{k}^{2}\sigma_{k}$ are not required to be known, and any valid upper bound can be used instead. We can use the local certificates to avoid unnecessary work on local problems which are already optimized, as well as to continuously quantify how newly arriving local data has to be re-optimized in the case of online training. The local certificates can also be used to quantify the contribution of newly joining or departing nodes, which is particularly useful in the elastic scenario described above.

Experimental results

Here we illustrate the advantages of CoLa in three respects: firstly we investigate the application in different network topologies and with varying subproblem quality $\Theta$; secondly, we compare CoLa with state-of-the-art decentralized baselines: \footnotesize1⃝, DIGing (Nedic et al., 2017), which generalizes the gradient-tracking technique of the EXTRA algorithm (Shi et al., 2015), and \footnotesize2⃝, Decentralized ADMM (aka. consensus ADMM), which extends the classical ADMM (Alternating Direction Method of Multipliers) method (Boyd et al., 2011) to the decentralized setting (Shi et al., 2014; Wei and Ozdaglar, 2013); Finally, we show that CoLa works in the challenging unreliable network environment where each node has a certain chance to drop out of the network.

We implement all algorithms in PyTorch with MPI backend. The decentralized network topology is simulated by running one thread per graph node, on a $2<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mo>×</mo></mrow><annotation encoding="application/x-tex">\times</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6667em;vertical-align:-0.0833em;"></span><span class="mord">×</span></span></span></span></span>12$ core Intel Xeon CPU E5-2680 v3 server with 256 GB RAM. Table 1 describes the datasetshttps://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/ used in the experiments. For Lasso, the columns of $\mathbf{A}$ are features. For ridge regression, the columns are features and samples for CoLa primal and CoLa dual, respectively. The order of columns is shuffled once before being distributed across the nodes. Due to space limit, details on the experimental configurations are included in Appendix D.

Effect of approximation quality $\Theta$. We study the convergence behavior in terms of the approximation quality $\Theta$. Here, $\Theta$ is controlled by the number of data passes $\kappa$ on subproblem (1) per node. Figure 1 shows that increasing $\kappa$ always results in less number of iterations (less communication rounds) for CoLa. However, given a fixed network bandwidth, it leads to a clear trade-off for the overall wall-clock time, showing the cost of both communication and computation. Larger $\kappa$ leads to less communication rounds, however, it also takes more time to solve subproblems. The observations suggest that one can adjust $\Theta$ for each node to handle system heterogeneity, as what we have discussed at the end of LABEL:{sec:cola}.

Effect of graph topology. Fixing $K$=$16$, we test the performance of CoLa on 5 different topologies: ring, 2-connected cycle, 3-connected cycle, 2D grid and complete graph. The mixing matrix $\mathcal{W}$ is given by Metropolis weights for all test cases (details in Appendix B). Convergence curves are plotted in Figure 4. One can observe that for all topologies, CoLa converges monotonically and especailly when all nodes in the network are equal, smaller $\beta$ leads to a faster convergence rate. This is consistent with the intuition that $1-\beta$ measures the connectivity level of the topology.

Superior performance compared to baselines. We compare CoLa with DIGing and D-ADMM for strongly and general convex problems. For general convex objectives, we use Lasso regression with $\lambda=10^{-4}$ on the webspam dataset; for the strongly convex objective, we use Ridge regression with $\lambda=10^{-5}$ on the URL reputation dataset. For Ridge regression, we can map CoLa to both primal and dual problems. Figure 2 traces the results on log-suboptimality. One can observe that for both generally and strongly convex objectives, CoLa significantly outperforms DIGing and decentralized ADMM in terms of number of communication rounds and computation time. While DIGing and D-ADMM need parameter tuning to ensure convergence and efficiency, CoLa is much easier to deploy as it is parameter free. Additionally, convergence guarantees of ADMM relies on exact subproblem solvers, whereas inexact solver is allowed for CoLa.

Fault tolerance to unreliable nodes. Assume each node of a network only has a chance of $p$ to participate in each round. If a new node $k$ joins the network, then local variables are initialized as $\mathbf{x}_{[k]}=0$; if node $k$ leaves the network, then $\mathbf{x}_{[k]}$ will be frozen with $\Theta_{k}=1$. All remaining nodes dynamically adjust their weights to maintain the doubly stochastic property of $\mathcal{W}$. We run CoLa on such unreliable networks of different $p$s and show the results in Figure 4. First, one can observe that for all $p>0$ the suboptimality decreases monotonically as CoLa progresses. It is also clear from the result that a smaller dropout rate (a larger $p$) leads to a faster convergence of CoLa.

Discussion and conclusions

In this work we have studied training generalized linear models in the fully decentralized setting. We proposed a communication-efficient decentralized framework, termed CoLa, which is free of parameter tuning. We proved that it has a sublinear rate of convergence for general convex problems, allowing e.g. L1 regularizers, and has a linear rate of convergence for strongly convex objectives. Our scheme offers primal-dual certificates which are useful in the decentralized setting. We demonstrated that CoLa offers full adaptivity to heterogenous distributed systems on arbitrary network topologies, and is adaptive to changes in network size and data, and offers fault tolerance and elasticity. Future research directions include improving subproblems, as well as extension to the network topology with directed graphs, as well as recent communication compression schemes (Stich et al., 2018).

Acknowledgments. We thank Prof. Bharat K. Bhargava for fruitful discussions. We acknowledge funding from SNSF grant 200021_175796, Microsoft Research JRC project ‘Coltrain’, as well as a Google Focused Research Award.

References

Appendix A Definitions

A generalization of (Rockafellar, 2015, Corollary 13.3.3). Given a proper convex function $g$ it holds that $g$ has $L$-bounded support w.r.t. the norm $\left\lVert{.}\right\rVert$ if and only if $g^{*}$ is $L$-Lipschitz w.r.t. the dual norm $\left\lVert{.}\right\rVert_{*}$.

Appendix B Graph topology

Let $\mathcal{E}$ be the set of edges of a graph. For time-invariant undirected graph the mixing matrix should satisfy the following properties:

(Double stochasticity) $\mathcal{W}\mathbf{1}=\mathbf{1}$, $\mathbf{1}^{\top}\mathcal{W}=\mathbf{1}^{\top}$;

(Symmetrization) For all $i,j$, $\mathcal{W}_{ij}=\mathcal{W}_{ji}$;

(Edge utilization) If $(i,j)\in\mathcal{E}$, then $\mathcal{W}_{ij}>0$; otherwise $\mathcal{W}_{ij}=0$.

A desired mixing matrix can be constructed using Metropolis-Hastings weights (Hastings, 1970):

where $d_{i}=|\mathcal{N}_{i}|$ is the degree of node $i$.

Appendix C Proofs

This section consists of three parts. Tools and observations are provided in Section C.1; The main lemmas for the convergence analysis are proved in Section C.2 ; The main theorems and implications are proved in Section C.3.

In some circumstances, it is convenient to use notations of array of stack column vectors. For example, one can stack local estimates $\mathbf{v}_{k}$ to matrix $\mathbf{V}:=[\mathbf{v}_{1};\cdots;\mathbf{v}_{K}]$, $\Delta\mathbf{V}=[\Delta\mathbf{v}_{1};\cdots;\Delta\mathbf{v}_{K}]$. The consensus vector $\mathbf{v}_{c}$ is repeated $K$ times which will be stacked similarly: $\mathbf{V}_{c}:=\mathbf{A}\mathbf{x}\mathbf{1}_{K}^{\top}=\mathbf{V}\mathbf{E}$ where $\mathbf{E}=\frac{1}{K}\mathbf{1}_{K}\mathbf{1}_{K}^{\top}$. The consensus violation under the two notations is written as

Besides, we also adopt following notations in the proof when there is no ambiguity: $\mathbf{v}_{k}^{\prime}:=\sum_{l=1}^{K}\mathcal{W}_{kl}\mathbf{v}_{l}$, $\mathbf{g}_{k}:=\nabla f(\mathbf{v}_{k})$, $\mathbf{g}_{k}^{\prime}:=\nabla f(\mathbf{v}_{k}^{\prime})$ and $\bar{\mathbf{g}}:=\frac{1}{K}\sum_{k=1}^{K}\mathbf{g}_{k}$. For the decentralized duality gap $G_{\mathcal{H}}(\mathbf{x},\{\mathbf{v}_{k}\}_{k=1}^{K},\{\mathbf{w}_{k}\}_{k=1}^{K})$, when $\mathbf{w}_{k}=\nabla f(\mathbf{v}_{k})$, we simplify $G_{\mathcal{H}}(\mathbf{x},\{\mathbf{v}_{k}\}_{k=1}^{K},\{\mathbf{w}_{k}\}_{k=1}^{K})$ to be $G_{\mathcal{H}}(\mathbf{x},\{\mathbf{v}_{k}\}_{k=1}^{K})$ in the sequel.

However, the specific analysis of the new fully decentralized algorithm CoLa poses many new challenges, and we propose significantly new proof techniques in the analysis. Specifically, i) we introduce the decentralized duality gap, which is suited for the decentralized algorithm CoLa; ii) consensus violation is the usually challenging part in analyzing decentralized algorithms. Unlike using uniform bounds for consensus violations, e.g., (Yuan et al., 2016), we properly combine the consensus violation term and the objective decrease term (c.f. Lemmas 6 and 8), thus reaching arguably tight convergence bounds for both the consensus violation term and the objective.

In this subsection we introduce basic lemmas. Lemma 1 establishes the relation between $\{{\bf v}_{k}\}_{k=1}^{K}$ and ${\mathbf{v}_{c}}$ and bounds $F_{A}({\bf x})$ using $\mathcal{H}_{A}({\bf x})$ and the consensus violation.

Let ${\widetilde{{\bf v}}}:=\frac{1}{K}\sum_{k=1}^{K}\mathbf{v}_{k}$. Using the doubly stochastic property of the matrix $\mathcal{W}$

On the other hand, ${\bf v}_{c}^{(t)}:=\mathbf{A}\mathbf{x}^{(t)}$ is updated based on all changes of local variables $\{{\bf x}_{[k]}\}_{k=1}^{K}$

Since $\widetilde{{\bf v}}^{(0)}={\bf v}_{c}^{(0)}$, we can conclude that $\widetilde{{\bf v}}^{(t)}={\bf v}_{c}^{(t)}$ $\forall~{}t$. From convexity of $f$ we know

The following lemma introduces the dual problem and the duality gap of (DA). See 2

Let $\bm{\lambda}_{k}$ be the Lagrangian multiplier for the constraint ${\bf v}_{k}=\mathbf{A}\mathbf{x}$, the Lagrangian function is

The dual problem of (DA) follows by taking the infimum with respect to both $\mathbf{x}$ and $\{\mathbf{v}_{k}\}_{k=1}^{K}$:

Let us change variables from $\bm{\lambda}_{k}$ to $\mathbf{w}_{k}$ by setting $\mathbf{w}_{k}:=K\bm{\lambda}_{k}$. If written in terms of minimization, the Lagrangian dual of $\mathcal{H}_{A}$ is

The optimality condition is that $\mathbf{w}_{k}=\nabla f(\mathbf{v}_{k})$. Now we can see the duality gap is

The following lemma correlates the consensus violation with the magnitude of the $\mathbf{v}$ parameter updates $\left\lVert{\Delta\mathbf{v}_{k}}\right\rVert_{2}^{2}$.

The consensus violation during the execution of Algorithm 1 can be bound by

where $c_{1}(\beta,\gamma,K):=\gamma^{2}K^{2}/(1-\beta)^{2}$.

Consider the norm of consensus violation at time $t+1$ and apply Algo. Step 1

Further, use $\mathcal{W}(\mathbf{I}-\mathbf{E})=(\mathbf{I}-\mathbf{E})(\mathcal{W}-\mathbf{E})$, $\left\lVert{\mathbf{I}-\mathbf{E}}\right\rVert_{\infty}=1$, and Young’s inequality with $\varepsilon_{\mathbf{v}}$

Use the spectral property of $\mathcal{W}$ we therefore have:

Recursively apply (15) for $i=0,\ldots,t-1$ gives

Consider $\left\lVert{\Delta\mathbf{V}^{(t)}}\right\rVert_{F}^{2}$ generated at time $t$, it will be used in (16) from time $t+1,t+2,\ldots,$ with coefficients $1,(1+\varepsilon_{\mathbf{v}})\beta^{2},((1+\varepsilon_{\mathbf{v}})\beta^{2})^{2},\ldots$. Sum of such coefficients are finite

where we need $(1+\varepsilon_{\mathbf{v}})\beta^{2}<1$. To minimize $c_{1}(\beta,\gamma,K)$ we can choose $\varepsilon_{\mathbf{v}}=1/\beta-1$

Let $\Delta{{\bf x}^{\star}_{[k]}}$ and $\Delta{{\bf x}_{[k]}}$ be the exact and $\Theta$-inexact solution of subproblem $\mathscr{G}^{\sigma^{\prime}}_{k}({}\cdot{};\mathbf{v}_{k},{\bf x}_{[k]})$. The change of iterates satisfies the following inequality

First use the Taylor expansion of $\mathscr{G}^{\sigma^{\prime}}_{k}({}\cdot{};\mathbf{v}_{k},{\bf x}_{[k]})$ and the defnition of $\Delta{{\bf x}^{\star}_{[k]}}$ we have

Similarly, apply (20) for $\Delta\mathbf{z}_{[k]}=\Delta\mathbf{x}_{[k]}$ for all $k$ and sum them up gives

By Assumption 1 the previous inequality becomes

The following inequality is straightforward

Multiply (24) with $\sigma^{\prime}/(2\tau)$ and use (21) and (23)

C.2 Main lemmas

We first present two main lemmas for the per-iteration improvement.

Let $g_{i}$ be strongly convex with convexity parameter $\mu_{g}\geq 0$ with respect to the norm $\left\lVert{\cdot}\right\rVert,\forall~{}i\in[n]$. Then for all iterations $t$ of outer loop, and any $s\in$, it holds that

where $\alpha\in$ is a constant and $\eta:=\gamma(1-\Theta)(1-\alpha)$ and $\sigma_{1}^{\prime}:=\frac{(1-\Theta)}{2(1+\Theta)}\sigma^{\prime}$ and $\bar{\sigma}^{\prime}:=(1+\beta)\sigma^{\prime}$ and $\mathbf{v}_{k}^{\prime}:=\sum_{l=1}^{K}\mathcal{W}_{kl}\mathbf{v}_{l}$.

For simplicity, we write $\mathcal{H}_{A}^{(t)}$ instead of $\mathcal{H}_{A}(\mathbf{x}^{(t)};\{\mathbf{v}_{k}^{(t)}\}_{k=1}^{K})$ and $\mathbf{v}_{k}^{\prime}:=\sum_{i=1}^{K}\mathcal{W}_{ik}\mathbf{v}_{i}$.

By the convexity of $f$, $D_{1}\geq 0$. Using the convexity of $f$ and $g$ in $D_{2}$ we have

Let $\alpha\in$ and apply Lemma 5, the previous inequality becomes

where $\sigma_{1}^{\prime}:=\frac{(1-\Theta)}{2(1+\Theta)}\sigma^{\prime}$. From the definition of $u_{i}$ we know

Replacing $\Delta{\bf x}_{i}=s(u_{i}-x_{i})$ in $C$ gives

We can bound the last term of the previous equation as $D_{3}$

Bound the gradient terms with consensus violation. First bound $\sum_{k=1}^{K}\left\lVert{\mathbf{g}_{k}^{\prime}-\bar{\mathbf{g}}^{\prime}}\right\rVert_{2}^{2}$, define $\mathbf{g}_{c}:=\nabla f(\mathbf{A}\mathbf{x})$

Apply the $1/\tau$-smoothness of $f$ we have

Then let $\bar{\sigma}^{\prime}:=(1+\beta)\sigma^{\prime}$ and $\eta:=\gamma(1-\Theta)(1-\alpha)$ we have

The following lemma correlates the consensus violation with the size of updates

Let $c>0$ be any constant value. Define $\delta^{(0)}:={\bf 0}$ and

Then the consensus violation has an upper bound.

First $t=0$, $b_{0}=\delta^{(0)}=0$. If the claim holds for time $t-1$, then $b_{t-1}\leq e_{1}\delta^{(t-1)}$. At time $t$, we have

Let $g_{i}$ be strongly convex with convexity parameter $\mu_{g}\geq 0$ with respect to the norm $\left\lVert{\cdot}\right\rVert,\forall~{}i\in[n]$. Then for all iterations $t$ of outer loop, and $s\in$, it holds that

where $\alpha:=(1+\frac{(1-\beta)^{2}}{36(1+\Theta)\beta})^{-1}\in$, $\eta:=\gamma(1-\Theta)(1-\alpha)$, $\bar{\sigma}^{\prime}:=(1+\beta)\sigma^{\prime}$ and

where $\delta^{(t)}$ is defined in Lemma 7.

In this proof we use $\mathbf{v}_{k}^{\prime}:=\sum_{i}\mathcal{W}_{ki}\mathbf{v}_{i}$. From Lemma 6 we know that

Use the following notations to simplify the calculation

Fix constant $c$ such that $\frac{f_{1}}{cc_{1}}=1$ in (44)

Fix $(f_{2}e_{1}+\frac{f_{1}\beta}{cc_{1}})=\frac{1+\beta}{2}<1$ in (44), to determine $\alpha\in$. First consider $f_{2}e_{1}$

Finally, using all of the previous equations we know

C.3 Main theorems

Here we present the proofs of Theorem 1 and Theorem 2.

If $g_{i}^{*}$ are $L$-Lipschitz continuous for all $i\in[n]$, then

For general convex functions, the strong convexity parameter is $\mu_{g}=0$, and hence the definition (41) of the complexity constant $R^{(t)}$ becomes

Here the last inequality follows from $L$-Lipschitz property of $g^{*}$. ∎

If $g_{i}(\cdot)$ are $\mu_{g}$-strongly convex, one can use the definition of $\sigma_{k}$ and $\sigma_{\text{max}}$ to find

then $R^{(t)}\leq 0$. The duality gap has a lower bound duality gap

Therefore if we denote $\varepsilon^{(t)}_{\mathcal{H}}:=\mathcal{H}_{A}^{(t)}-\mathcal{H}_{A}^{\star}+\delta^{(t)}$ we have recursively that

The right hand side will be smaller than some $\varepsilon_{\mathcal{H}}$ if

Moreover, to bound the duality gap $G_{\mathcal{H}}^{(t)}$, we have

Hence if $\varepsilon_{\mathcal{H}}\leq\eta s_{0}\varepsilon_{G_{\mathcal{H}}}$ then $G_{\mathcal{H}}^{(t)}\leq\varepsilon_{G_{\mathcal{H}}}$. Therefore after

iterations we have obtained a duality gap less then $\varepsilon_{G_{\mathcal{H}}}$.

We write $\mathcal{H}_{A}^{(t)}$ instead of $\mathcal{H}_{A}(\mathbf{x}^{(t)};\{\mathbf{v}_{k}^{(t)}\}_{k=1}^{K})$ and $\mathcal{H}_{A}^{\star}$ instead of $\mathcal{H}_{A}({\mathbf{x}}^{\star};\{{\mathbf{v}_{k}}^{\star}\}_{k=1}^{K})$. We begin by estimating the expected change of feasibility for $\mathcal{H}_{A}$. We can bound this above by using Lemma 8 and the fact that $F_{B}(\cdot)$ is always a lower bound for $-F_{A}(\cdot)$ and then applying (51) to find

We know that $\delta^{(0)}=0$. Choose $s=1$ and

Clearly, (60) implies that (61) holds for $t=t_{0}$. Assuming that it holds for any $t\geq t_{0}$, we show that it must also hold for $t+1$. Indeed, using

by applying the bounds (57) and (61), plugging in the definition of $s$ (62), and simplifying. We upper bound the term $D$ using the fact that geometric mean is less or equal to arithmetic mean:

We can apply the results of Lemma 8 to get

If $T\geq\lceil\frac{1}{\eta}\rceil+T_{0}$ such that $T_{0}\geq t_{0}$ we have

To have right hand side of (64) smaller then $\varepsilon_{G_{\mathcal{H}}}$ it is sufficient to choose $T_{0}$ and $T$ such that

Hence if $T_{0}\geq t_{0}+\frac{2}{\eta}\left(\frac{8L^{2}\sigma\bar{\sigma}^{\prime}}{\tau\varepsilon_{G_{\mathcal{H}}}}-1\right)$ and $T\geq T_{0}+\frac{4L^{2}\sigma\bar{\sigma}^{\prime}}{\tau\varepsilon_{G_{\mathcal{H}}}\eta}$ then (65) and (66) are satisfied.

If the $\mathbf{w}_{k}$ variable in the duality gap (6) is fixed to $\mathbf{w}_{k}=\mathbf{g}_{k}:=\nabla f(\mathbf{v}_{k})$, then using the equality condition of the Fenchel-Young inequality on $f$, the duality gap can be written as follows

where $\bar{\mathbf{g}}=\frac{1}{K}\sum_{k=1}^{K}\mathbf{g}_{k}$ is the only term locally unavailable.

If both terms in (68) are less than $\varepsilon/2$, then $G_{\mathcal{H}}\leq\varepsilon$. Since the first term can be calculated locally, we only need for all $k=1,\ldots K$

Consider the second term in (68). Compute the difference between $g_{i}^{*}(-\mathbf{A}_{i}^{\top}\bar{\mathbf{g}})$ and $g_{i}^{*}(-\mathbf{A}_{i}^{\top}{\mathbf{g}}_{k})$

where we use Lemma 3 and $L$-Lipschitz continuity. Then sum up coordinates $i\in\mathcal{P}_{k}$ on node $k$

Sum up (71) for all $k=1,\ldots,K$ and apply the Cauchy-Schwarz inequality

We will upper bound $\sum_{i\in\mathcal{P}_{k}}\left\lVert{\mathbf{A}_{i}}\right\rVert_{2}$ and $\left\lVert{\bar{\mathbf{g}}-\mathbf{g}_{k}}\right\rVert_{2}$ separately. First we have

where we write $\left\lVert{.}\right\rVert_{\infty,2}$ for the largest Euclidean norm of a column of the argument matrix, and then used the definition of $\sigma_{k}$ as in (7). Let us write $\mathbf{G}:=[\mathbf{g}_{1};\cdots;\mathbf{g}_{K}]$, $\mathbf{E}:=\frac{1}{K}[\mathbf{1};\cdots;\mathbf{1}]$, then apply Young’s inequality with $\delta$

Take $\delta:=(1-\beta)/\beta$, then we have

then (72) is less than $\varepsilon/2$. Finally, (75) can be guaranteed by imposing the following restrictions for all $k=1,\ldots,K$

Appendix D Experiment details

In this section we provide greater details about the experimental setup and implementations. All the codes are written in PyTorch (0.4.0a0+cc9d3b2) with MPI backend (Paszke et al., 2017). In each experiment, we run centralized CoCoA for a sufficiently long time until progress stalled; then use their minimal value as the approximate optima.

DIGing is a distributed algorithm based on inexact gradient and a gradient tracking technique. (Nedic et al., 2017) proves linear convergence of DIGing when the distributed optimization objective is strongly convex over time-varying graphs with a fixed learning rate. In this experiments, we only consider the time-invariant graph. The stepsize is chosen via a grid search. (Nedic et al., 2017) mentioned that the EXTRA algorithm (Shi et al., 2015) is almost identical to that of the DIGing algorithm when the same stepsize is chosen for both algorithms, so we only present with DIGing here.

CoLa.

We implement CoLa framework with local solvers from Scikit-Learn (Pedregosa et al., 2011). Their ElasticNet solver uses coordinate descent internally. We note that since the framework and theory allow any internal solver to be used, CoLa could benefit even beyond the results shown by using existing fast solvers. We implement CoCoA as a special case of CoLa. The aggregation parameter $\gamma$ is fixed to $1$ for all experiments.

ADMM.

Alternating Direction Method of Multipliers (ADMM) (Boyd et al., 2011) is a classical approach in distributed optimization problems. Applying ADMM to decentralized settings (Shi et al., 2014) involves solving

where $z_{ij}$ is an auxiliary variable imposing the consensus constraint on neighbors $i$ and $j$. We therefore employ the coordinate descent algorithm to solve the local problem. The number of coordinates chosen in each round is the same as that of CoLa. We choose the penalty parameter from the conclusion of (Shi et al., 2014).

Additional experiments.

We provide additional experimental results here. First the consensus violation $\sum_{k=1}^{K}\left\lVert{\mathbf{v}_{k}-\mathbf{v}_{c}}\right\rVert_{2}^{2}$ curve for Figure 2 is displayed in Figure 6. As we can see, the consensus violation starts with 0 and soon becomes very large, then gradually drops down. This is because we are minimizing the sum of $\mathcal{H}_{A}^{(t)}$ and $\delta^{(t)}$, see the proof of Theorem 1. Then another model under failing nodes is tested in Figure 6 where $\mathbf{x}_{[k]}$ are initialized to 0 when node $k$ leave the network. Note that we assume the leaving node $k$ will inform its neighborhood and modify their own local estimates so that the rest nodes still satisfy $\frac{1}{\text{\#nodes}}\sum_{k}\mathbf{v}_{k}=\mathbf{v}_{c}$. This failure model, however, oscillates and does not converge fast.

Appendix E Details regarding extensions

In this section we extend framework CoLa to handle fault tolerance and time varying graphs. Here we assume when a node leave the network, their local variables $\mathbf{x}$ are frozen. We use same assumptions about the fault tolerance model in (Smith et al., 2017).

At each iteration $t$, we define the accuracy level of the solution calculated by node $k$ to its subproblem as

where ${\Delta{\bf x}}^{\star}_{k}$ is the minimizer of the subproblem $\mathscr{G}^{\sigma^{\prime}}_{k}(\cdot;{\bf x}_{[k]}^{(t)},\mathbf{v}_{k}^{(t)})$. We allow this value to vary between with $\theta_{k}^{t}:=1$ meaning that no updates to subproblem $\mathscr{G}^{\sigma^{\prime}}_{k}$ are made by node $k$ at iteration $t$.

The flexible choice of $\theta_{k}^{t}$ allows the consideration of stragglers and fault tolerance. We also need the following assumption on $\theta_{k}^{t}$.

In addition we write $\bar{\Theta}:=p_{\text{max}}+(1-p_{\text{max}})\Theta_{\text{max}}<1$. Another assumption on time varying model is necessary in order to maintain the same linear and sublinear convergence rate. It is from (Nedic et al., 2017, Assumption 1):

Assume the mixing matrix $\mathcal{W}(t)$ is a function of time $t$. There exist a positive integer $B$ such that the spectral gap satisfies the following condition

We change the Algorithm 1 such that it performs gossip step for $B$ times between solving subproblems. In this way, the convergence rate on time varying mixing matrix is similar to a static graph with mixing matrix $\prod_{i=t}^{t+B-1}\mathcal{W}(i)$. The sublinear/linear rate can be proved similarly.

E.2 Data dependent aggregation parameter

In Algorithm 1, the aggregation parameter $\gamma$ controls the level of adding $\gamma$ versus averaging $\gamma:=\frac{1}{K}$ of the partial solution from all machines. For the convergence discussed below to hold, the subproblem parameter $\sigma^{\prime}$ must be chosen not smaller than

The simple choice of $\sigma^{\prime}:=\gamma K$ is valid for (78), closer to the actual bound given in $\sigma^{\prime}_{\text{min}}$.

E.3 Hessian subproblem

If the Hessian matrix of $f$ is available, it can be used to define better local subproblems, as done in the classical distributed setting by (Gargiani, 2017; Lee and Chang, 2017; Dünner et al., 2018; Lee et al., 2018). We use same idea in the decentralized setting, defining the improved subproblem

The sum of previous subproblems satisfies the following relations

This means that the sequence \big{\{}\sum_{k=1}^{K}\mathscr{G}^{\sigma^{\prime}}_{k}({\bf 0};{\bf x}_{[k]}^{(t)},\mathbf{v}_{k}^{(t)})\big{\}}_{t=0}^{\infty} is monotonically non-increasing. Following the reasoning in this paper, we can have similar convergence guarantees for both strongly convex and general convex problems. Formalizing all detailed implications here would be out of the scope of this paper, but the main point is that the second-order techniques developed for the CoCoA framework also have their analogon in the decentralized setting.