---
# System prepended metadata

title: Decentralized FL

---

# Decentralized FL

## Notes

* There have been many recent works that propose bypassing a central orchestrator for training (PyGrid in our case). One of the techniques to achieve this is via gossip protocol where workers communicate among themselves to converge to a particular model.

# Papers

## Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication

* Consider decentralized stochastic optimization with the objective function being distributed over n machines that can only communicate to their neighbors on a fixed communication graph
* No multiple local updates on each node, but perform shared/collaborative model updates
* To overcome communication bottlenecks, nodes compress (e.g. quantize or sparsify) their model updates
    * cover both unbiased and biased compression operators
    * quality $\delta \le 1$ (1 => no compression)

### Contributions
1. CHOCO-SGD: a novel gossip-based stochastic gradient descent algorithm
    * Can reduce communication by at least two orders of magnitudes

2. CHOCO-GOSSIP: a novel gossip algorithm for the distributed average consensus problem
    * 1st linearly-converging gossip algorithm with communication compression
    * 1st gossip algorithm that supports arbitrary compressed messages for $\delta > 0$ and still exhibits linear convergence

### Introduction

* **Decentralized Communication**
    * network topology as a graph where edges represent the communication links along which messages (e.g. model updates) can be exchanged.
    * Such topologies avoid these bottlenecks and thereby offer hugely improved potential in scalability
        * maximal degree of the network is often constant (e.g. ring or torus) or a slowly growing function in n (e.g. scale-free networks).
* **Decentralied Optimization** (**or Gossip Algorithms*)
    * SGD is an inherently serial algorithm that does not take the distributed setting into account
    * Mini-batch SGD is the natural parallelization of SGD
    * Popular gossip algos:
        * Subgradient descent
        * ADMM: alternating direction method of multipliers
        * Dual Avg
    * Network topology only affects higher-order terms of the convergence rate of decentralized optimization algorithms on convex problems (see convergence rate formula)
    * CHOCO-SGD is as efficient in terms of iterations as centralized mini-batch SGD but avoids the communication bottleneck that centralized algorithms suffer from
    * CHOCO-SGD is free of i.i.d assumptions
* **Communication Compression**
    *  Propose the first method that supports arbitrary low accuracy and even biased compression operators
    *  A compressed vector $Q(g)$ can be more efficiently represented, for instance by using limited bit representation (quantization) or enforcing sparsity (both referred as compression operators in this paper)
        *  quantization operators are based on random dithering
        *  Much sparser vectors can be obtained by random sparsification techniques
    *  Techniques that do not directly quantize gradients, but instead maintain additional states are known to perform better in theory and practice
*  **Distributed Average Consensus**
    *  Consists in finding the average vector $\vec{x}$ of n local vectors
        *  Important sub-routine of many decentralized algorithms
    *  For consensus algorithms with compressed communication it has been remarked that the standard gossip algorithm does not converge to the correct solution
        *  sometimes do only converge to a neighborhood
    *  The method presented here converges linearly, even for arbitrary compressed communication, without requiring adaptive accuracy.

### Average Consensus with Communication Compression
* See Algorithm 1
* The proposed algorithm will later serve as a crucial primitive in the optimization algorithm for the general optimization problem
*  The convergence rate of scheme (Formula 3) crucially depends on the connectivity matrix $W \in R^{n×n}$ of the network defined as $(W )_{ij} = w{ij}$ also called the interaction or gossip matrix
*  CHOCO- GOSSIP that supports a much larger class of compression operators
*  Proposed scheme (see formula CHOCO-G)
    * $\hat{x}(t) ∈ R^d$ denote additional variables that are stored by all neighbors j of node i, ${i, j} \in E$, as well as on node i itself
    * This seems to require each machine to store deg(i) + 2 vectors
    * Could be re-written in a way that every node stores only three vectors: $x$, $\hat{x}$ and $\sum_{j:\{i,j\} \in E}{w_{ij}\hat{x}_j}$
        * See Apendix E
    * Preserves the average of iterates
    * the noise introduced by the compression operator vanishes as t → ∞

### Decentralized Stochastic Optimization
* Leverage Algorithm 1 to build a Communication-Compressed Decentralized SGD -> Algorithm 2 consisting o 4 parts
    * Stochastic gradient step
    * Iterate update
    * Application of Compression Operator
    * CHOCO-G local communication
* Its proven that this setting obtains a n×speed up compared to the serial implementation of SGD on only one worker.
* CHOCO-SGD converges under arbitrary high compression
    * **It tries to carefully compensate quantization errors instead of ignoring them**
        * What happen in other approaches
            * the local variable on each worker is updated using only copies on the neighbors which do not carry information about the true uncompressed values
            * Errors made previously are lost and cannot be corrected in later iterations
        * In CHOCO-SGD the sharedcopy $\hat{x}_i$ is in general different from the private copy $x_i$, allowing to carry on the true values to the next iterations

### Experiments
* Compression operators
    * $rand_k$ (sparsification), $top_k$ (sparsification) and $qsgd_s$ (quantization) compression operators
        * k -> 1% of all coordinates
        * $s \in \{2^4, 2^8\}$
* CHOCO-GOSSIP vs Baselines
    * (qsgd256) converges with the same rate as (E-G) that uses exact communications but requires much less data
    * (rand1%) sparsification as the most data-efficient method in the experiments
* CHOCO-SGD vs SoA Decentralized Stochastic Optimization schemes
    * Impact on Topology
        * Ring topology as the more affected by increasing the No of workers
            * CHOCO-SGD consistently outperforms DCD-SGD in all settings
            * CHOCO-SGD reaches almost the same performance as exact communication, while significantly reducing communication cost.
                * performs almost as good as the exact Alg. 3, but uses 100× less communication with (rand1%) sparsification
                    * (top1%) variant performs slightly better than (rand1%)
                * approximately 13× less communication for (qsgd16) quantization
* Future work
    * Analysis of CHOCO-SGD on non-convex functions

### Implementation in PyTorch
* https://github.com/epfml/ChocoSGD
* Community impl
    * https://github.com/Adirlou/OptML_Project
    * https://github.com/JYWa/MATCHA
    

