Total: 1
<i>Distributed learning</i> 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 {\it 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.\footnote{In practice, the domain U is defined implicitly by the representation of d-dimensional vectors which is used in the protocol.} A set of <i>examples</i> {(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 ˜O(dlogn) bits. To this end, we introduce a new tool called <i>halfspace containers</i>, that is closely related to <i>bracketing numbers</i> in statistics and to <i>hyperplane cuttings</i> in discrete geometry, and allows for a compressed approximate representation of every halfspace. We complement our upper bound result by an almost matching ˜Ω(dlogn) lower bound on the communication complexity of any such protocol Since the distributed halfspace learning problem is closely related to the <i>convex set disjointness</i> problem in communication complexity and the problem of <i>distributed linear programming</i> in distributed optimization, we also derive upper and lower bounds of ˜O(d2logn) and~˜Ω(dlogn) on the communication complexity of both of these basic problems.