Near Optimal Distributed Learning of Halfspaces with Two Parties

Mark Braverman, Gillat Kol, Shay Moran, Raghuvansh R. Saxena

Research output: Contribution to journalConference articlepeer-review

3 Scopus citations


Distributed learning protocols are designed to train on distributed data without gathering it all on a single centralized machine, thus contributing to the efficiency of the system and enhancing its privacy. We study a central problem in distributed learning, called distributed learning of halfspaces: let U ⊆ Rd be a known domain of size n and let h : Rd → R be an unknown target affine function.1 A set of examples {(u, b)} is distributed between several parties, where u ∈ U is a point and b = sign(h(u)) ∈ {±1} is its label. The parties’ goal is to agree on a classifier f : U → {±1} such that f(u) = b for every input example (u, b). We design a protocol for the distributed halfspace learning problem in the two-party setting, communicating only Õ(dlog n) bits. To this end, we introduce a new tool called halfspace containers, that is closely related to bracketing numbers in statistics and to hyperplane cuttings in discrete geometry, and allows for a compressed approximate representation of every halfspace. We complement our upper bound result by an almost matching Ω̃(dlog n) lower bound on the communication complexity of any such protocol. Since the distributed halfspace learning problem is closely related to the convex set disjointness problem in communication complexity and the problem of distributed linear programming in distributed optimization, we also derive upper and lower bounds of Õ(d2 log n) and Ω̃(dlog n) on the communication complexity of both of these basic problems.

Original languageEnglish (US)
Pages (from-to)724-758
Number of pages35
JournalProceedings of Machine Learning Research
StatePublished - 2021
Event34th Conference on Learning Theory, COLT 2021 - Boulder, United States
Duration: Aug 15 2021Aug 19 2021

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence
  • Software
  • Control and Systems Engineering
  • Statistics and Probability


  • Communication Complexity
  • Distributed Learning


Dive into the research topics of 'Near Optimal Distributed Learning of Halfspaces with Two Parties'. Together they form a unique fingerprint.

Cite this