# Distributed Optimization over Block-Cyclic Data

arXiv: https://arxiv.org/abs/2002.07454 · HTML: https://mlsanity.com/paper/2002.07454/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Feb 2020.

## Built on by (most cited first, 6 of 6)

- [A Unified Analysis of Federated Learning with Arbitrary Client Participation](https://mlsanity.com/paper/2205.13648/) (2022)
- [Federated Learning under Heterogeneous and Correlated Client Availability](https://mlsanity.com/paper/2301.04632/) (2023)
- [Federated Learning for Data Streams](https://mlsanity.com/paper/2301.01542/) (2023)
- [Performative Federated Learning: A Solution to Model-Dependent and Heterogeneous Distribution Shifts](https://mlsanity.com/paper/2305.05090/) (2023)
- [A Lightweight Method for Tackling Unknown Participation Statistics in Federated Averaging](https://mlsanity.com/paper/2306.03401/) (2023)
- [Introducing Federated Learning into Internet of Things ecosystems -- preliminary considerations](https://mlsanity.com/paper/2207.07700/) (2022)

## Abstract (arXiv)

We consider practical data characteristics underlying federated learning, where unbalanced and non-i.i.d. data from clients have a block-cyclic structure: each cycle contains several blocks, and each client's training data follow block-specific and non-i.i.d. distributions. Such a data structure would introduce client and block biases during the collaborative training: the single global model would be biased towards the client or block specific data. To overcome the biases, we propose two new distributed optimization algorithms called multi-model parallel SGD (MM-PSGD) and multi-chain parallel SGD (MC-PSGD) with a convergence rate of O(1/√NT), achieving a linear speedup with respect to the total number of clients. In particular, MM-PSGD adopts the block-mixed training strategy, while MC-PSGD further adds the block-separate training strategy. Both algorithms create a specific predictor for each block by averaging and comparing the historical global models generated in this block from different cycles. We extensively evaluate our algorithms over the CIFAR-10 dataset. Evaluation results demonstrate that our algorithms significantly outperform the conventional federated averaging algorithm in terms of test accuracy, and also preserve robustness for the variance of critical parameters.