braverman21a@v134@PMLR

Total: 1

#1 Near Optimal Distributed Learning of Halfspaces with Two Parties [PDF] [Copy] [Kimi] [REL]

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

<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 URd be a known domain of size n and let h:RdR 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~uU 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.

Subject: COLT.2021 - Accept