# On Communication Complexity of Classification Problems

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Nov 2017.

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

- [Memory Bounds for Continual Learning](https://mlsanity.com/paper/2204.10830/) (2022)
- [Online Learning with Simple Predictors and a Combinatorial Characterization of Minimax in 0/1 Games](https://mlsanity.com/paper/2102.01646/) (2021)
- [On Optimal Learning Under Targeted Data Poisoning](https://mlsanity.com/paper/2210.02713/) (2022)
- [Metalearning with Very Few Samples Per Task](https://mlsanity.com/paper/2312.13978/) (2023)
- [Online Learning with Set-Valued Feedback](https://mlsanity.com/paper/2306.06247/) (2023)
- [The I/O Complexity of Attention, or How Optimal is Flash Attention?](https://mlsanity.com/paper/2402.07443/) (2024)
- [Distributional PAC-Learning from Nisan's Natural Proofs](https://mlsanity.com/paper/2310.03641/) (2023)
- [Active Learning with Simple Questions](https://mlsanity.com/paper/2405.07937/) (2024)
- [A Resilient Distributed Boosting Algorithm](https://mlsanity.com/paper/2206.04713/) (2022)
- [Sorting from Counterexamples](https://mlsanity.com/paper/2608.21579/) (2026)
- [Uniform Brackets, Containers, and Combinatorial Macbeath Regions](https://mlsanity.com/paper/2111.10048/) (2021)

## Abstract (arXiv)

This work studies distributed learning in the spirit of Yao's model of communication complexity: consider a two-party setting, where each of the players gets a list of labelled examples and they communicate in order to jointly perform some learning task. To naturally fit into the framework of learning theory, the players can send each other examples (as well as bits) where each example/bit costs one unit of communication. This enables a uniform treatment of infinite classes such as half-spaces in ℝd, which are ubiquitous in machine learning. We study several fundamental questions in this model. For example, we provide combinatorial characterizations of the classes that can be learned with efficient communication in the proper-case as well as in the improper-case. These findings imply unconditional separations between various learning contexts, e.g. realizable versus agnostic learning, proper versus improper learning, etc. The derivation of these results hinges on a type of decision problems we term "it realizability problems" where the goal is deciding whether a distributed input sample is consistent with an hypothesis from a pre-specified class. From a technical perspective, the protocols we use are based on ideas from machine learning theory and the impossibility results are based on ideas from communication complexity theory.