COLA: Decentralized Linear Learning

1.2 Related work

• Prior decentralized optimization either splits parameter coordinates or sums local costs; the latter often lacks consensus when data are non-IID.In the sum-structured approach, local-cost minimizers may differ across devices.Source: §1 · p. 1

1 Introduction

• COLA generalizes COCOA to decentralized generalized-linear-model training, using primal-dual optimization to address limitations of existing approaches.The framework is designed for training without a central coordinator.Source: §1 · p. 2, §1.2 · p. 3
• Linear and sublinear convergence rates are guaranteed for strongly convex and general convex objectives, respectively, without the cited stochastic methods’ IID-data assumption.The cited stochastic methods require IID data distribution over devices [Zhang et al., 2015, Wang et al., 2017].Source: §1 · p. 2
• COLA achieves communication efficiency and allows reuse of efficient single-machine solvers for on-device learning.Source: §1 · p. 2
• COLA is described as provably resilient to changes in data and network topology, and to devices disappearing, straggling, or reappearing.Source: §1 · p. 2

• Each node maintains a local estimate vk of the shared state v = Ax, which is unavailable to a node in the fully decentralized setting.The local estimate serves as the algorithm’s surrogate for the shared state.Source: §2 · p. 4
• Each node’s subproblem depends on its local data and neighboring nodes’ estimates; γ defaults to 1, with σ′ = γK given as a safe choice.The subproblem can be solved approximately.Source: §2 · pp. 4–5

Elasticity to network size, compute resources and changing data—and fault tolerance

• New nodes initialize local variables to zero, departing nodes freeze them, and local accuracy parameters accommodate differing resources and stragglers.The same approach accommodates additions or removals of local data columns, and COLA does not require parameter tuning to converge.Source: §2 · p. 5

Extension to improved second-order subproblems

• Hessian information can be used to define improved local subproblems for COLA, with details provided in Appendix E.The passage relates this extension to techniques previously shown in the centralized setting [Lee and Chang, 2017, Dünner et al., 2018].Source: §2 · p. 5

Extension to time-varying graphs

• For a time-varying graph connected within B gossip steps, COLA can use B communication steps and one computation step per round while retaining convergence guarantees.The extension is stated under the time-varying model in [Nedic et al., 2017, Assumption 1].Source: §2 · p. 5

3 On the convergence of COLA

• Even without consensus, relations connect the decentralized objective to the original; under consensus, the decentralized duality gap recovers COCOA’s.The decentralized duality gap generalizes COCOA’s.Source: §3 · pp. 5–6

3.1 Linear rate for strongly convex objectives

• With strongly convex gi and 1/τ-smooth f, COLA guarantees linear convergence for local solvers of quality Θ.The theorem sets γ := 1.Source: §3.1 · p. 6

3.2 Sublinear rate for general convex objectives

• For general convex objectives, COLA achieves O(1/T) convergence on networks with positive spectral gap, assuming bounded-support gi and smooth f.The theorem states the result for a local solver of quality Θ.Source: §3.2 · p. 6

3.3 Local certificates for global accuracy

• Local subproblem-gap and neighborhood-gradient conditions yield certificates without global vector aggregation, supporting online reoptimization and join-or-departure impact tracking.Nodes share only the Boolean status of the local conditions to obtain a global-objective certificate.Source: §3.3 · p. 7

Experimental setup

• The evaluation compares COLA with DIGing and decentralized ADMM, tests topology and subproblem quality, and includes networks with node dropouts.The experiments are implemented in PyTorch with an MPI backend on a simulated network.Source: §4 · pp. 7–8

Effect of approximation quality Θ

• Increasing κ reduces communication rounds but can increase wall-clock time because solving local subproblems takes longer.The authors suggest adjusting each node's Θ to handle system heterogeneity.Source: Figure 1 · p. 7, §4 · p. 8

Effect of graph topology

• Across five 16-node topologies, COLA converges monotonically, with smaller β associated with faster convergence.The tested topologies are a ring, 2-connected cycle, 3-connected cycle, 2D grid, and complete graph.Source: §4 · p. 8, Figure 3 · p. 9

Superior performance compared to baselines

• COLA significantly outperforms DIGing and decentralized ADMM in communication rounds and computation time on the reported Lasso and ridge-regression tasks.The comparison also reports that COLA is parameter free and permits inexact subproblem solvers, unlike the stated tuning and exact-solver requirements of the baselines.Source: §4 · p. 8, Figure 2 · p. 8

Fault tolerance to unreliable nodes

• For every tested participation probability p > 0, suboptimality decreases monotonically; larger p leads to faster convergence.Joining nodes initialize x[k] to zero, departing nodes' x[k] is frozen, and remaining nodes adjust weights to preserve doubly stochastic W.Source: §4 · p. 9, Figure 4 · p. 9

5 Discussion and conclusions

• COLA has sublinear convergence for general convex problems and linear convergence for strongly convex objectives; the authors identify subproblem improvements, directed graphs, and communication compression as future work.The paper also reports primal-dual certificates, adaptability to network and data changes, fault tolerance, and elasticity.Source: §5 · p. 9

A Definitions

• The appendix defines Lipschitz continuity, smoothness, bounded support, and strong convexity, and states a duality between bounded support and Lipschitz continuity of the conjugate.These definitions specify objective properties used in the paper's analysis.Source: A Definitions · p. 12

B Graph topology

• For time-invariant undirected graphs, the appendix specifies mixing-matrix properties and gives Metropolis-Hastings weights based on node degrees.An edge receives positive weight, while non-edges receive zero weight; the construction is attributed to Hastings (1970).Source: B Graph topology · p. 12

C Proofs

• The section directs readers to Appendix C.1 for tools and observations, C.2 for convergence lemmas, and C.3 for theorems and implications.Source: C Proofs · p. 12
• Convergence rates are derived by bounding expected per-iteration reduction with the decentralized duality gap and related terms, then using properties of the objectives.Source: C Proofs · p. 13
• The analysis combines consensus violation and objective decrease rather than using uniform consensus bounds, yielding arguably tight bounds for both consensus violation and the objective.The authors introduce a decentralized duality gap suited to COLA and use it with these bounds to analyze convergence.Source: C Proofs · p. 13

C.1 Observations and properties

• The section relates local estimates and the consensus vector to objective and iterate-change inequalities used in the analysis.It presents bounds involving F, H, consensus violation, and changes to the iterates.Source: §C.1 · pp. 13, 15
• The decentralized formulation has a Lagrangian dual and an associated duality gap.The passage introduces the dual function and gap for (DA).Source: §C.1 · pp. 13–14
• A lemma bounds consensus violation during Algorithm 1 using the iterates and update-related quantities.The bound is developed from the algorithm’s Step 8 and recursive application of an inequality.Source: §C.1 · pp. 14–15
• A geometric-series condition, (1 + ε_v)β^2 < 1, makes the coefficient sum finite; ε_v = 1/β − 1 is given as the minimizing choice for c1.Source: §C.1 · p. 15

C.2 Main lemmas

• Lemma 6 bounds per-iteration improvement when the functions g_i are strongly convex with parameter μ_g ≥ 0.Its stated bound holds for every outer iteration and s ∈ [0, 1].Source: §C.2 · p. 16
• Lemma 7 bounds consensus violation through a quantity defined recursively from the updates.The lemma introduces δ(0) = 0 and establishes an upper bound on consensus violation.Source: §C.2 · p. 18
• Lemma 8 uses the consensus bound from Lemma 7 in a per-iteration improvement bound under the stated strong-convexity condition.The proof combines results from Lemmas 6 and 7 with the parameters defined for the bound.Source: §C.2 · p. 19

C.3 Main theorems

• Theorem 1 gives an expected duality-gap guarantee after T iterations when each g_i is μ_g-strongly convex and f is 1/τ-smooth.The theorem uses Algorithm 1 with γ = 1 and a local solver of quality Θ.Source: §C.3 · p. 20
• Theorem 2 gives an expected duality-gap guarantee for the non-strongly-convex case when g_i has L-bounded support and f is (1/τ)-smooth.The theorem specifies an iteration count T for a desired gap ε_GH.Source: §C.3 · p. 21
• The local-certificate proposition states that local conditions at every node suffice to guarantee a global duality gap no greater than ε.It assumes g_i has L-bounded support and defines N_k as the nodes accessible to node k.Source: §C.3 · p. 23

D Experiment details

• Centralized CoCoA runs until progress stalls, and its minimum value serves as the approximate optimum for each experiment.The code uses PyTorch 0.4.0a0+cc9d3b2 with the MPI backend.Source: D Experiment details · p. 24
• DIGing is tested on a time-invariant graph with a grid-searched stepsize; EXTRA is omitted because it is described as almost identical under the same stepsize [Shi et al., 2015].The cited work proves linear convergence for strongly convex objectives over time-varying graphs with a fixed learning rate.Source: D Experiment details · p. 24
• COLA uses Scikit-Learn local solvers, including ElasticNet coordinate descent, and fixes aggregation parameter γ to 1 in all experiments.The framework and theory allow any internal solver, so faster existing solvers could improve results beyond those shown.Source: D Experiment details · p. 24
• Figure 5's consensus violation starts at zero, soon becomes very large, then gradually drops; the node-failure model oscillates and does not converge fast.The Figure 6 setting resets x[k] after a node leaves.Source: Figure 5 · p. 25, D Experiment details · p. 25, Figure 6 · p. 25
• For ADMM, neighboring nodes' local problems use coordinate descent with the same coordinates per round as COLA, and the penalty parameter follows [Shi et al., 2014].The decentralized formulation introduces auxiliary variables imposing consensus constraints between neighboring nodes [Shi et al., 2014].Source: D Experiment details · pp. 24–25

E.1 Fault tolerance and time varying graphs

• When a node leaves, its local variables x are frozen; the extension uses the same fault-tolerance assumptions as [Smith et al., 2017].The per-node-per-iteration approximation parameter specifies the accuracy of each node's subproblem solution and can vary across iterations.Source: §E.1 · p. 25
• The fault-tolerance model includes assumptions on the per-node approximation parameter and on node behavior over the history of iterates.The supplied passages also require a time-varying mixing-matrix spectral-gap condition over a window of B iterations [Nedic et al., 2017, Assumption 1].Source: §E.1 · pp. 25–26
• Adding B gossip steps between subproblem solves gives a convergence rate on time-varying mixing matrices similar to the static-graph rate, with sublinear or linear rates proved similarly.The relevant mixing matrix is the product Qt+B−1 through t of W(i).Source: §E.1 · p. 26

E.2 Data dependent aggregation parameter

• The aggregation parameter γ controls adding versus averaging partial solutions, and σ′ = γK is a valid simple choice for the subproblem parameter.The convergence discussion requires σ′ to meet a lower bound.Source: §E.2 · p. 26

E.3 Hessian subproblem

• When the Hessian is available, it can define improved local subproblems in the decentralized setting, extending second-order techniques used in COCOA.The appendix states that similar convergence guarantees can be obtained for strongly convex and general convex problems, while detailed implications are out of scope.Source: §E.3 · p. 26
• The sum of previous subproblems satisfies stated relations, supporting the appendix's convergence discussion.The supplied passage gives no further detail about those relations.Source: §E.3 · p. 26