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