On Communication Complexity of Classification Problems

Daniel Kane, Roi Livni, Shay Moran, Amir Yehudayoff
Proceedings of the Thirty-Second Conference on Learning Theory, PMLR 99:1903-1943, 2019.

Abstract

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 $\R^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 in this context between various learning tasks, e.g. realizable versus agnostic learning, proper versus improper learning, etcetera. %They also imply lower bounds that match the performance %of algorithm from previous works. 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 devise (i.e. the upper bounds) are based on ideas from machine learning and the impossibility results (i.e. the lower bounds) are based on ideas from communication complexity.

Cite this Paper

BibTeX
@InProceedings{pmlr-v99-kane19a, title = {On Communication Complexity of Classification Problems}, author = {Kane, Daniel and Livni, Roi and Moran, Shay and Yehudayoff, Amir}, booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory}, pages = {1903--1943}, year = {2019}, editor = {Beygelzimer, Alina and Hsu, Daniel}, volume = {99}, series = {Proceedings of Machine Learning Research}, month = {25--28 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v99/kane19a/kane19a.pdf}, url = {https://proceedings.mlr.press/v99/kane19a.html}, abstract = {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 $\R^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 in this context between various learning tasks, e.g. realizable versus agnostic learning, proper versus improper learning, etcetera. %They also imply lower bounds that match the performance %of algorithm from previous works. 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 devise (i.e. the upper bounds) are based on ideas from machine learning and the impossibility results (i.e. the lower bounds) are based on ideas from communication complexity.} }
Endnote
%0 Conference Paper %T On Communication Complexity of Classification Problems %A Daniel Kane %A Roi Livni %A Shay Moran %A Amir Yehudayoff %B Proceedings of the Thirty-Second Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2019 %E Alina Beygelzimer %E Daniel Hsu %F pmlr-v99-kane19a %I PMLR %P 1903--1943 %U https://proceedings.mlr.press/v99/kane19a.html %V 99 %X 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 $\R^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 in this context between various learning tasks, e.g. realizable versus agnostic learning, proper versus improper learning, etcetera. %They also imply lower bounds that match the performance %of algorithm from previous works. 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 devise (i.e. the upper bounds) are based on ideas from machine learning and the impossibility results (i.e. the lower bounds) are based on ideas from communication complexity.
APA
Kane, D., Livni, R., Moran, S. & Yehudayoff, A.. (2019). On Communication Complexity of Classification Problems. Proceedings of the Thirty-Second Conference on Learning Theory, in Proceedings of Machine Learning Research 99:1903-1943 Available from https://proceedings.mlr.press/v99/kane19a.html.

Related Material