# Minimal Communication-Cost Statistical Learning

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 34 references that are in the map.
- First posted on arXiv 12 Jun 2024.

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

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [signSGD: Compressed Optimisation for Non-Convex Problems](https://mlsanity.com/paper/1802.04434/) (2018)
- [Sparsified SGD with Memory](https://mlsanity.com/paper/1809.07599/) (2018)
- [Stronger generalization bounds for deep nets via a compression approach](https://mlsanity.com/paper/1802.05296/) (2018)
- [Distributed learning of deep neural network over multiple agents](https://mlsanity.com/paper/1810.06060/) (2018)
- [Sparse Communication for Distributed Gradient Descent](https://mlsanity.com/paper/1704.05021/) (2017)
- [The Convergence of Sparsified Gradient Methods](https://mlsanity.com/paper/1809.10505/) (2018)
- [Qsparse-local-SGD: Distributed SGD with Quantization, Sparsification, and Local Computations](https://mlsanity.com/paper/1906.02367/) (2019)
- [Error Compensated Quantized SGD and its Applications to Large-scale Distributed Optimization](https://mlsanity.com/paper/1806.08054/) (2018)
- [Catastrophic Fisher Explosion: Early Phase Fisher Matrix Impacts Generalization](https://mlsanity.com/paper/2012.14193/) (2020)
- [Minimal Random Code Learning: Getting Bits Back from Compressed Model Parameters](https://mlsanity.com/paper/1810.00440/) (2018)
- [8-Bit Approximations for Parallelism in Deep Learning](https://mlsanity.com/paper/1511.04561/) (2015)
- [Algorithms for the Communication of Samples](https://mlsanity.com/paper/2110.12805/) (2021)
- [Distributed Variational Representation Learning](https://mlsanity.com/paper/1807.04193/) (2018)
- [Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja's Algorithm](https://mlsanity.com/paper/1602.06929/) (2016)
- [Rate-Distortion Theoretic Generalization Bounds for Stochastic Learning Algorithms](https://mlsanity.com/paper/2203.02474/) (2022)
- [Data-dependent Generalization Bounds via Variable-Size Compressibility](https://mlsanity.com/paper/2303.05369/) (2023)
- [Exploring Fast and Communication-Efficient Algorithms in Large-scale Distributed Networks](https://mlsanity.com/paper/1901.08924/) (2019)
- [In-Network Learning: Distributed Training and Inference in Networks](https://mlsanity.com/paper/2107.03433/) (2021)
- [Semantic Communication of Learnable Concepts](https://mlsanity.com/paper/2305.08126/) (2023)

## Abstract (arXiv)

A client device which has access to n training data samples needs to obtain a statistical hypothesis or model W and then to send it to a remote server. The client and the server devices share some common randomness sequence as well as a prior on the hypothesis space. In this problem a suitable hypothesis or model W should meet two distinct design criteria simultaneously: (i) small (population) risk during the inference phase and (ii) small 'complexity' for it to be conveyed to the server with minimum communication cost. In this paper, we propose a joint training and source coding scheme with provable in-expectation guarantees, where the expectation is over the encoder's output message. Specifically, we show that by imposing a constraint on a suitable Kullback-Leibler divergence between the conditional distribution induced by a compressed learning model widehatW given W and the prior, one guarantees simultaneously small average empirical risk (aka training loss), small average generalization error and small average communication cost. We also consider a one-shot scenario in which the guarantees on the empirical risk and generalization error are obtained for every encoder's output message.