[Theory] Fwd: [TTIC Talks] REMINDER: 10/25 Machine Learning Seminar Series: Shay Moran, Technion

[Madhur Tulsiani]

Shay Moran is speaking at the ML Seminar Series at 10:30 am. The talk might
also be of interest if you like halfspaces, communication complexity or
optimization. Please see the email below for details.

Best,
Madhur

---------- Forwarded message ---------
From: Alicia McClarin <amcclarin at ttic.edu>
Date: Thu, Oct 24, 2019 at 12:05 PM
Subject: [TTIC Talks] REMINDER: 10/25 Machine Learning Seminar Series: Shay
Moran, Technion
To: <ml-announce at lists.uchicago.edu>, Jonathan Rodriguez <
jgrodriguez at galton.uchicago.edu>, TTIC Talks <talks at ttic.edu>


*When: *    Friday, October 25th at 10:30am

*Where: *   TTIC, 6045 S Kenwood Avenue, 5th Floor, Room 526
<https://www.google.com/maps/search/6045+S+Kenwood+Avenue,+5th+Floor,+Room+526?entry=gmail&source=g>

*Who: *       Shay Moran, Technion

*Title:*        Convex Set Disjointness, Distributed Learning of
Halfspaces, and LP Feasibility

*Abstract: *We study the {\em Convex Set Disjointness} (CSD) problem, where
two players have input sets taken from an arbitrary fixed domain U\subset
R^d of size | U| = n. Their mutual goal is to decide using minimum
communication whether the convex hulls of their sets intersect
(equivalently, whether their sets can be separated by a hyperplane).
Different forms of this problem naturally arise in distributed learning and
optimization:it is equivalent to Distributed Linear Program (LP)
Feasibility -- a basic task in distributed optimization, and it is tightly
linked to Distributed Learning of Halfspaces in R^d. In communication
complexity theory, CSD can be viewed as a geometric interpolation between
the classical problems of Set Disjointness (when d>= n-1) and Greater-Than
(when d=1).

We establish a nearly tight bound of ~Theta(d log n) on the communication
complexity of learning halfspaces in R^d. For Convex Set Disjointness (and
the equivalent task of distributed LP feasibility)we derive upper and lower
bounds of tilde O(d^2\log n) and~Omega(d\log n). These results improve upon
several previous works in distributed learning and optimization.

Unlike typical works in communication complexity, the main technical
contribution of this work lies in the upper bounds. In particular, our
protocols are based on a Container Lemma for Halfspaces and on two variants
of {\it Carath\'eodory's Theorem}, which may be of independent interest.
These geometric statements are used by our protocols to provide a
compressed summary of the players' input.



Joint work with Mark Braverman, Gillat Kol, and Raghuvansh R. Saxena
(Princeton University).
Link to paper:
https://arxiv.org/abs/1909.03547

*University of Chicago  <https://www.uchicago.edu/>and** Toyota
Technological Institute at Chicago <http://www.ttic.edu/>*
Machine Learning Seminar Series
<https://voices.uchicago.edu/machinelearning/events/>Sign up for
announcement email list at
https://lists.uchicago.edu/web/subscribe/ml-announce.

-- 
*Alicia McClarin*
*Toyota Technological Institute at Chicago*
*6045 S. Kenwood Ave.,
<https://www.google.com/maps/search/6045+S.+Kenwood+Ave.,%C2%A0+Office+518+Chicago,+IL+60637?entry=gmail&source=g>**Office
518
<https://www.google.com/maps/search/6045+S.+Kenwood+Ave.,%C2%A0+Office+518+Chicago,+IL+60637?entry=gmail&source=g>*
*Chicago, IL 60637
<https://www.google.com/maps/search/6045+S.+Kenwood+Ave.,%C2%A0+Office+518+Chicago,+IL+60637?entry=gmail&source=g>*
*773-834-3321*
*www.ttic.edu* <http://www.ttic.edu/>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20191024/d33db143/attachment.html>