BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1088
DTSTAMP:20230914T125950Z
SUMMARY:Convex Set Disjointness\, Distributed Learning of Halfspaces\, and
Linear Programming
DESCRIPTION:Speaker: Shay Moran (Technion)\n\nAbstract: \nDistributed learn
ing protocols are designed to train on distributed data without gathering
it all on a single centralized machine\, thus contributing to the efficien
cy of the system and enhancing its privacy.\nWe study a central problem in
distributed learning\, called Distributed Learning of Halfspaces:\nlet U
\\subset R^d be a known domain of size n and let h:R^d —> R be an unknow
n target affine function. A set of examples {(u\,b)} is distributed betwee
n several parties\, where u \\in U is a point and b = sign(h(u)) \\in {-1\
, +1} is its label.\nThe parties' goal is to agree\, using minimum communi
cation\, on a classifier f: U—>{-1\,+1} such that f(u)=b for every input
example (u\,b). (In practice\, the finite domain U is defined implicitly
by the representation of d-dimensional vectors which is used in the protoc
ol.)\nWe establish a (nearly) tight bound of ~θ(d*log n) on the communica
tion complexity of the problem of distributed learning of halfspaces in th
e two-party setting.\nSince this problem is closely related to the Convex
Set Disjointness problem in communication complexity and the problem of Di
stributed Linear Programming in distributed optimization\, we are able to
derive upper and lower bounds of ~O(d^2\\log n) and ~Ω(d\\log n) for both
of these basic problems as well.\nOur main technical contribution lies in
the design and analysis of the protocols which imply the upper bounds.\nT
o this end\, we introduce a technique called Halfspace Containers\, allowi
ng for a compressed approximate representation of every halfspace.\nHalfsp
ace containers may be of independent interest and are closely related to b
racketing numbers in statistics and to hyperplane cuttings in discrete geo
metry.\n
URL:https://www.tcs.tifr.res.in/web/events/1088
DTSTART;TZID=Asia/Kolkata:20201006T160000
DTEND;TZID=Asia/Kolkata:20201006T170000
END:VEVENT
END:VCALENDAR