# Distributed Perceptron under Bounded Staleness, Partial Participation, and Noisy Communication

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 21 references that are in the map.
- First posted on arXiv 15 Jan 2026.

## Builds on (most cited first, 11 of 11)

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Local SGD Converges Fast and Communicates Little](https://mlsanity.com/paper/1805.09767/) (2018)
- [Asynchronous Federated Optimization](https://mlsanity.com/paper/1903.03934/) (2019)
- [Federated Learning via Over-the-Air Computation](https://mlsanity.com/paper/1812.11750/) (2018)
- [Federated Learning with Buffered Asynchronous Aggregation](https://mlsanity.com/paper/2106.06639/) (2021)
- [Federated Learning over Wireless Fading Channels](https://mlsanity.com/paper/1907.09769/) (2019)
- [Online Learning under Delayed Feedback](https://mlsanity.com/paper/1306.0686/) (2013)
- [Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning](https://mlsanity.com/paper/2206.08307/) (2022)
- [Asynchronous SGD Beats Minibatch SGD Under Arbitrary Delays](https://mlsanity.com/paper/2206.07638/) (2022)
- [Design and Analysis of Uplink and Downlink Communications for Federated Learning](https://mlsanity.com/paper/2012.04057/) (2020)
- [ARock: an Algorithmic Framework for Asynchronous Parallel Coordinate Updates](https://mlsanity.com/paper/1506.02396/) (2015)

## Abstract (arXiv)

We study a semi-asynchronous client-server perceptron trained via iterative parameter mixing (IPM-style averaging): clients run local perceptron updates and a server forms a global model by aggregating the updates that arrive in each communication round. The setting captures three system effects in federated and distributed deployments: (i) stale updates due to delayed model delivery and delayed application of client computations (two-sided version lag), (ii) partial participation (intermittent client availability), and (iii) imperfect communication on both downlink and uplink, modeled as effective zero-mean additive noise with bounded second moment. We introduce a server-side aggregation rule called staleness-bucket aggregation with padding that deterministically enforces a prescribed staleness profile over update ages without assuming any stochastic model for delays or participation. Under margin separability and bounded data radius, we prove a finite-horizon expected bound on the cumulative weighted number of perceptron mistakes over a given number of server rounds: the impact of delay appears only through the mean enforced staleness, whereas communication noise contributes an additional term that grows on the order of the square root of the horizon with the total noise energy. In the noiseless case, we show how a finite expected mistake budget yields an explicit finite-round stabilization bound under a mild fresh-participation condition.