PaperlayerView exact revision on arXiv

Source-linked AI summary

Collaborative Deep Learning in Fixed Topology Networks

Zhanhong Jiang, Aditya Balu, Chinmay Hegde, Soumik Sarkar

arXiv:1706.07880v1stat.MLcs.LG

TL;DR

The paper addresses the limited combination of data parallelization and decentralized computation for deep learning over communication-constrained networks. It introduces consensus-based distributed SGD methods for fixed-topology networks, analyzes their convergence, and reports higher accuracy than FedAvg despite being slightly slower under the stated conditions.

  • Problem

    Existing distributed deep-learning approaches insufficiently address data parallelization together with decentralized computation, especially when agents have local data and fixed neighbor communication.

  • Method

    The paper proposes CDSGD and CDMSGD for collaborative learning over fixed-topology networks and analyzes them using Lyapunov function construction.

  • Results

    The proposed methods support consensus and convergence analysis across generic, strongly convex, and nonconvex objectives, while experiments show higher accuracy than FedAvg under stated conditions.

  • Takeaways & Limitations

    The framework combines data parallelism, decentralized computation, and constrained fixed-topology communication for collaborative learning with local or private data.

  • Takeaways & Limitations

    The convergence bounds depend on graph topology, and increasing certain eigenvalues can worsen connectivity and adversely affect consensus.

Abstract

from arXiv · show

There is significant recent interest to parallelize deep learning algorithms in order to handle the enormous growth in data and model sizes. While most advances focus on model parallelization and engaging multiple computing agents via using a central parameter server, aspect of data parallelization along with decentralized computation has not been explored sufficiently. In this context, this paper presents a new consensus-based distributed SGD (CDSGD) (and its momentum variant, CDMSGD) algorithm for collaborative deep learning over fixed topology networks that enables data parallelization as well as decentralized computation. Such a framework can be extremely useful for learning agents with access to only local/private data in a communication constrained environment. We analyze the convergence properties of the proposed algorithm with strongly convex and nonconvex objective functions with fixed and diminishing step sizes using concepts of Lyapunov function construction. We demonstrate the efficacy of our algorithms in comparison with the baseline centralized SGD and the recently proposed federated averaging algorithm (that also enables data parallelism) based on benchmark datasets such as MNIST, CIFAR-10 and CIFAR-100.

1 Introduction

The paper targets collaborative deep learning that combines data parallelization, decentralized computation, and communication over fixed-topology networks. It proposes CDSGD and CDMSGD with convergence analysis and benchmark comparisons against centralized SGD and FedAvg.

  • 1 Introduction: Existing distributed approaches emphasize model parallelization or central parameter-server aggregation, while data parallelization remains insufficiently addressed.Data parallelization matters for scenarios where agents retain local or private data.
  • 1 Introduction: Fixed-topology communication is motivated by sensor and robotic networks where agents can communicate only with designated neighbors.Arbitrary on-demand communication between agent pairs may be infeasible in these settings.
  • 1 Introduction: CDSGD and CDMSGD jointly support data parallelization, decentralized computation, and constrained communication over fixed-topology networks.The paper presents rigorous convergence analysis for convex and nonconvex objectives with fixed and diminishing step sizes.
  • 1 Introduction: The experiments compare the proposed methods with centralized SGD and FedAvg on MNIST, CIFAR-10, and CIFAR-100.Under the stated agent and hyperparameter conditions, the method is slightly slower but achieves higher accuracy than FedAvg.
  • 1 Introduction: The paper distinguishes its work from prior distributed methods through collaborative data parallelism and analysis extending to stochastic and nonconvex settings.Earlier cited works considered convex or nonconvex optimization in deterministic settings.

2 Formulation

The formulation distributes empirical risk minimization across agents with local datasets connected by a static, connected undirected graph. It specifies smoothness, convexity, coercivity, Lipschitz, and interaction-matrix assumptions for the analysis.

  • 2 Formulation: The learning problem is formulated as standard unconstrained empirical risk minimization over data points and a parameter vector.The global objective is represented through local agent-specific objectives.
  • 2 Formulation: Each agent accesses only its own training subset, while agents communicate over a static connected undirected graph.The neighborhood of an agent contains its graph neighbors and the agent itself.
  • 2 Formulation: The distributed objective is decomposed as f(x) = Σ_j f_j(x), with each f_j representing the objective associated with Agent j.The formulation assumes every agent has the same local objective function, unlike general distributed optimization problems.
  • 2 Formulation: The analysis assumes local objectives are smooth, proper, coercive, and Lipschitz continuous, with strong-convexity and smoothness conditions also characterized.The supplied formulation defines strong convexity, smoothness, Lipschitz continuity, and coercivity.
  • 2 Formulation: The interaction matrix encodes communication weights and is constrained by graph sparsity, double stochasticity, a one-dimensional consensus nullspace, and positive definiteness.Its eigenvalues satisfy λ1(Π) = 1 > λ2(Π) ≥ ··· ≥ λN(Π) > 0.

3 Proposed Algorithm

The proposed approach combines consensus-based SGD updates with decentralized communication over a fixed network, while its convergence analysis uses a Lyapunov function and stochastic-gradient assumptions. The section develops conditions for descent and convergence under smoothness, convexity, and variance-control assumptions.

  • Consensus Distributed SGD: CDSGD is built from SGD and consensus to solve distributed stochastic optimization across communicating agents.The method also has Polyak- and Nesterov-momentum variants, with straightforward mini-batch implementations.
  • Consensus Distributed SGD: Each agent uses its neighborhood, step size α, and a stochastic gradient of its local objective in the distributed update.The stochastic gradient is denoted g_j(x_j^k) in the supplied algorithm description.
  • Lyapunov analysis: The analysis rewrites the update as an effective gradient step combining the stochastic gradient with a consensus-correction term α^-1(I − Π)x^k.This combined quantity is called the Stochastic Lyapunov Gradient.
  • Lyapunov analysis: A Lyapunov function is constructed from the objective and a disagreement norm associated with the positive semidefinite matrix I − Π.The construction is motivated directly by the rewritten update law.
  • Assumptions and convergence: Under smoothness and strong-convexity assumptions, the aggregate objective inherits Lipschitz-gradient and strong-convexity properties and has a unique minimizer.The paper also establishes the parameter relations H_m ≤ γ_m and Ĥ ≤ ĝamma.
  • Assumptions and convergence: Convergence analysis requires controlling stochastic-gradient variance in addition to unbiasedness, using assumptions that bound variance by Q + Q_V||∇V(x^k)||^2.The stated conditions support sufficient Lyapunov descent and impose step-size requirements for the resulting bounds.

4 Main Results

The paper establishes consensus and convergence guarantees for CDSGD under fixed step sizes, covering strongly convex and nonconvex objectives. It also characterizes how step size, gradient noise, and network topology affect these guarantees.

  • CDSGD achieves consensus across agents for generic convex or nonconvex loss functions when the fixed step size is below a natural upper bound.
  • Strongly convex case: Under strongly convex objectives, CDSGD converges linearly to a neighborhood of the global optimum.The neighborhood radius depends on gradient noise, step size, and the interaction-matrix spectral gap.
  • Strongly convex case: Smaller step sizes reduce the convergence neighborhood, although excessively small values may slow the convergence rate.
  • Nonconvex case: With nonconvex objectives, CDSGD guarantees a bounded average second moment of gradients rather than convergence of the objective-value sequence.Without gradient noise, the gradient norms approach zero and estimates approach a stationary point; stochastic gradients do not support that same claim.
  • Topology effects: The nonconvex upper bound reflects a tradeoff between consensus and gradient convergence governed by the network topology.Increasing the spectral gap can tighten the bound but may worsen graph connectivity through an increase in λ2(Π).
  • Diminishing step size: Complementary convergence results for diminishing step sizes are provided in the supplementary material.

5 Experimental Results

Experiments evaluate CDSGD and CDMSGD against centralized SGD and FedAvg, then examine how network size and topology affect accuracy and consensus. The proposed methods reach competitive accuracy, while topology creates a speed–consensus trade-off.

  • Performance comparison: CDSGD eventually reaches accuracy comparable with centralized SGD, but converges significantly more slowly.CDSGD also has a significantly smaller training–validation generalization gap than centralized SGD.
  • Performance comparison: CDMSGD achieves better steady-state performance than FedAvg while reaching centralized SGD-level performance, despite being slightly slower.The comparison uses the same number of agents, with FedAvg configured using E = 1 and C = 1.
  • Network size: Increasing the network from 2 to 8 to 16 agents slows convergence, while all tested network sizes achieve similar accuracy levels.The network-size experiment uses CDMSGD and evaluates training performance as the number of agents grows.
  • Network topology: Sparser networks, identified by higher second-largest eigenvalues, converge faster in average accuracy.This trend resembles the effect of reducing FedAvg’s client fraction, which makes agent interactions sparser.
  • Network topology: Denser networks provide more stable consensus across agents, making topology density important for decentralized collaborative learning.With a central parameter server, sparse topology may instead be useful for faster convergence.

6 Conclusion and Future Work

The paper develops consensus-based distributed learning over fixed-topology networks and establishes analytical and experimental support for its convergence and accuracy. CDSGD approaches centralized accuracy, while CDMSGD can outperform FedAvg.

  • Analytical results: CDSGD supports linear convergence with sufficiently small fixed steps and sublinear convergence with diminishing steps for strongly convex, Lipschitz-differentiable objectives.For nonconvex objectives, CDSGD produces decaying gradients.
  • Experimental results: CDSGD can reach centralized SGD-level accuracy with sufficient training epochs while maintaining significantly lower generalization error.The conclusion reports this behavior on benchmark experiments.
  • Experimental results: CDMSGD can outperform FedAvg, which provides data parallelism but not decentralized computation.This positions the momentum variant as the stronger empirical comparison in the paper’s decentralized setting.

7.1 Additional analytical results and proofs

The supplementary analysis establishes technical inequalities and convergence results for CDSGD with fixed step sizes under strongly convex and nonconvex objectives. The proofs use assumptions, boundedness lemmas, expectations, and recursive inequalities.

  • Proof setup: The supplementary section introduces auxiliary lemmas for the CDSGD iterates before proving the main convergence statements.The proof sequence includes lemmas concerning iterate inequalities, Lyapunov lower bounds, and bounded expected gradient norms.
  • Proof setup: Coercivity of each local objective provides a lower bound for the Lyapunov function, supporting analysis when a global optimum may not be achieved.The lower bound is stated over an open set containing the CDSGD iterates.
  • Strongly convex case: Under the stated assumptions, Theorem 1 analyzes CDSGD with a fixed step size in the strongly convex case.Its proof uses the preceding lemmas, strong convexity, expectation, and recursive application of the resulting inequality.
  • Nonconvex case: Theorem 2 analyzes CDSGD with a fixed step size for nonconvex objectives using expectation, summation across iterations, and a Lyapunov-based rearrangement.The theorem’s stated conditions include the paper’s assumptions and a step-size constraint.

7.2 Proof with Diminishing Step Size

The diminishing-step-size analysis shows that CDSGD asymptotically reaches consensus and converges under strongly convex objectives, while its gradient norm decays under nonconvex objectives. The proofs establish boundedness and recursively control the Lyapunov sequence.

  • Step-size conditions: A diminishing step-size sequence satisfies α_k → 0 while supporting convergence to the optimal value under noisy gradients.The analysis motivates adaptive step sizes because noisy gradients are common in deep learning.
  • Consensus: With diminishing step size, agent disagreement converges to zero in expectation, establishing asymptotic consensus.The relevant bound controls E[∥(I − Π)x_k∥] as k increases.
  • Strongly convex case: The diminishing-step-size Lyapunov function remains strongly convex with bounded associated quantities under the stated assumptions.These properties allow the fixed-step-size assumptions to remain applicable with modified constants.
  • Strongly convex case: For strongly convex objectives, Theorem 3 bounds expected Lyapunov suboptimality by a geometrically decaying term plus a diminishing-step-size error term.The bound uses constants β < 1 and γ′Q̂ and is stated for the specified diminishing step-size conditions.
  • Nonconvex case: For nonconvex objectives, diminishing step sizes make the gradient norm decay toward zero even in the presence of noise.The proof uses a finite right-hand side bound whose limiting behavior forces ∥∇V̂(x_k)∥² toward zero.

7.3 Additional pseudo-codes of the algorithms

The paper provides pseudocode for CDSGD with Polyak and Nesterov momentum, including distributing data across agents and processing local data subsets.

  • Momentum variants: CDSGD is extended with both Polyak momentum and Nesterov momentum variants.The paper presents separate pseudocode algorithms for each momentum formulation.
  • Data distribution: Both algorithms begin by distributing the training dataset to N agents.This establishes the data-parallel setup used by the distributed procedures.
  • Local processing: Each agent processes its corresponding data subset during the distributed procedure.The pseudocode explicitly introduces an agent-specific processing loop and local data shuffling.
  • Local processing: The local data subset is randomly shuffled before subsequent algorithmic updates.Random shuffling appears in both the Polyak and Nesterov pseudocode descriptions.

7.4 Additional Experimental Results

Additional experiments compare distributed methods with centralized and federated baselines across benchmark datasets and examine step-size effects. The results show slower but ultimately stronger validation behavior for consensus methods in several comparisons, while step size affects convergence, consensus stability, and accuracy.

  • CIFAR-10 comparison: CDSGD converges more slowly than SGD but eventually achieves better validation performance and a smaller generalization gap on CIFAR-10.SGD dominates training early, whereas CDSGD shows linear convergence in log scale for both training and validation.
  • CIFAR-10 comparison: Figure 3 compares average training and validation loss for CDSGD versus SGD, and CDMSGD versus Federated Averaging.Solid lines represent training loss and dashed lines represent validation loss.
  • CIFAR-100 and MNIST results: CDMSGD is the slowest of the compared CIFAR-100 methods but eventually converges to lower loss than FedAvg.Its validation accuracy is significantly higher than FedAvg while approaching centralized SGD accuracy.
  • CIFAR-100 and MNIST results: On MNIST, the accuracy trends remain consistent with those observed on CIFAR-10 and CIFAR-100.The MNIST comparison reports loss and accuracy across SGD, CDSGD, CDMSGD, and FedAvg.
  • Step-size effects: With a decaying step size, CDMSGD performs slightly better than SGD, while centralized MSGD performs best on MNIST.The experiment compares SGD, MSGD, and CDMSGD under decaying-step-size conditions.
  • Step-size effects: Fixed step size 0.1 gives the fastest convergence but unstable consensus, whereas 0.001 yields stable consensus with moving-average variance remaining 0.The experiments vary fixed step sizes from 0.1 to 0.01 to 0.001.
Loading 1706.07880v1…