<div><div dir="auto">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.</div></div><div dir="auto"><br></div><div dir="auto">Best,</div><div dir="auto">Madhur </div><div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">---------- Forwarded message ---------<br>From: <strong class="gmail_sendername" dir="auto">Alicia McClarin</strong> <span dir="auto"><<a href="mailto:amcclarin@ttic.edu">amcclarin@ttic.edu</a>></span><br>Date: Thu, Oct 24, 2019 at 12:05 PM<br>Subject: [TTIC Talks] REMINDER: 10/25 Machine Learning Seminar Series: Shay Moran, Technion<br>To:  <<a href="mailto:ml-announce@lists.uchicago.edu">ml-announce@lists.uchicago.edu</a>>, Jonathan Rodriguez <<a href="mailto:jgrodriguez@galton.uchicago.edu">jgrodriguez@galton.uchicago.edu</a>>, TTIC Talks <<a href="mailto:talks@ttic.edu">talks@ttic.edu</a>><br></div><br><br><div dir="ltr"><div class="gmail_default"><font face="arial, helvetica, sans-serif"><b>When: </b>    Friday, October 25th at 10:30am</font></div><div class="gmail_default"><b><font face="arial, helvetica, sans-serif"><br></font></b></div><div class="gmail_default"><font face="arial, helvetica, sans-serif"><b>Where: </b>  <b> </b></font><span style="color:rgb(0,0,0);font-family:arial,helvetica,sans-serif">TTIC</span><span style="color:rgb(0,0,0);font-family:arial,helvetica,sans-serif">, <a href="https://www.google.com/maps/search/6045+S+Kenwood+Avenue,+5th+Floor,+Room+526?entry=gmail&source=g">6045 S Kenwood Avenue, 5th Floor, Room 526</a></span></div><div class="gmail_default"><br></div><div class="gmail_default"><font face="arial, helvetica, sans-serif"><b>Who: </b>       </font><span>Shay</span> Moran, Technion</div><div class="gmail_default"><br></div><div class="gmail_default"><div style="margin:0px;padding:0px 0px 20px;width:1337.3px"><div id="m_-4224846220324948656gmail-m_-3695523444922846162gmail-m_-6347408271442848163gmail-m_-7404826267275577745m_-4289695673627584033gmail-m_-5513052736425723567gmail-m_-1232615408917137598gmail-m_-8170851091567805726gmail-m_5060498845683329548gmail-m_6370517152245766134m_60372103153299925gmail-m_3939378776351258492m_-5744785253320301212gmail-m_-3431820893768067416m_-4781781202659172041gmail-m_1411384538057782154gmail-m_-2602862226548060193gmail-m_2308107385707571375gmail-m_-4294178622907846594gmail-m_-8828297477395305783gmail-m_472195179138337646gmail-m_7702150797537706748m_6360626503578278750gmail-m_4825572068462259833gmail-m_6990054991242104006gmail-m_2677612458337831619gmail-:18i" style="direction:ltr;margin:8px 0px 0px;padding:0px"><div id="m_-4224846220324948656gmail-m_-3695523444922846162gmail-m_-6347408271442848163gmail-m_-7404826267275577745m_-4289695673627584033gmail-m_-5513052736425723567gmail-m_-1232615408917137598gmail-m_-8170851091567805726gmail-m_5060498845683329548gmail-m_6370517152245766134m_60372103153299925gmail-m_3939378776351258492m_-5744785253320301212gmail-m_-3431820893768067416m_-4781781202659172041gmail-m_1411384538057782154gmail-m_-2602862226548060193gmail-m_2308107385707571375gmail-m_-4294178622907846594gmail-m_-8828297477395305783gmail-m_472195179138337646gmail-m_7702150797537706748m_6360626503578278750gmail-m_4825572068462259833gmail-m_6990054991242104006gmail-m_2677612458337831619gmail-:18h" style="overflow:hidden;font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:1.5"><div><font face="arial, helvetica, sans-serif"><b>Title:</b>        </font>Convex Set Disjointness, Distributed Learning of Halfspaces, and LP Feasibility</div><div><font face="arial, helvetica, sans-serif"><br></font></div><div><font face="arial, helvetica, sans-serif"><b>Abstract: </b></font><font face="arial, sans-serif"><span style="color:black"></span></font><span style="color:black;text-indent:0.5in"><font face="arial, sans-serif">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). </font></span></div><div><span style="color:black;text-indent:0.5in"><font face="arial, sans-serif"><br></font></span></div><div><span style="color:black;font-family:arial,sans-serif;text-indent:0.5in">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. </span></div><div><span style="color:black;font-family:arial,sans-serif;text-indent:0.5in"><br></span></div><div><span style="font-family:arial,sans-serif;color:black;text-indent:0.5in">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.</span></div><p class="MsoNormal" style="margin:0in 0in 0.0001pt;text-indent:0.5in;line-height:normal"><font face="arial, sans-serif"> </font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal"><span style="color:black"><font face="arial, sans-serif">Joint work with Mark Braverman, Gillat Kol, and Raghuvansh R. Saxena (Princeton University).</font></span><span style="font-family:"Times New Roman",serif;font-size:12pt"></span></p></div></div></div></div><div class="gmail_default"><div style="margin:0px;padding:0px 0px 20px;width:1337.3px"><div style="direction:ltr;margin:8px 0px 0px;padding:0px"><div style="overflow:hidden;font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:1.5"><div><div style="margin:0px;font-stretch:normal;line-height:normal"><div>Link to paper:</div><div><a href="https://arxiv.org/abs/1909.03547" target="_blank">https://arxiv.org/abs/1909.03547</a></div></div></div><div style="outline:none;padding:10px 0px;width:22px;margin:2px 0px 0px"><br></div></div><div id="m_-4224846220324948656gmail-m_-3695523444922846162gmail-m_-6347408271442848163gmail-m_-7404826267275577745m_-4289695673627584033gmail-m_-5513052736425723567gmail-m_-1232615408917137598gmail-m_-8170851091567805726gmail-m_5060498845683329548gmail-m_6370517152245766134m_60372103153299925gmail-m_3939378776351258492m_-5744785253320301212gmail-m_-3431820893768067416m_-4781781202659172041gmail-m_1411384538057782154gmail-m_-2602862226548060193gmail-m_2308107385707571375gmail-m_-4294178622907846594gmail-m_-8828297477395305783gmail-m_472195179138337646gmail-m_7702150797537706748m_6360626503578278750gmail-m_4825572068462259833gmail-m_6990054991242104006gmail-m_2677612458337831619gmail-:18h" style="overflow:hidden;font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:1.5"><div><h3 style="box-sizing:border-box;margin:0px;padding:0px 0px 10px;border:0px;outline:0px;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;vertical-align:baseline;line-height:1em;text-align:center"><div style="text-align:left"><font face="arial, sans-serif" size="4"><i style="color:rgb(11,83,148)"><a href="https://www.uchicago.edu/" style="font-weight:normal;box-sizing:border-box;margin:0px;padding:0px;border:0px;outline:0px;background:transparent;vertical-align:baseline;text-decoration-line:none" target="_blank"><span class="gmail_default"></span>University of Chicago </a>and</i><i style="color:rgb(11,83,148);font-weight:normal"> <a href="http://www.ttic.edu/" style="box-sizing:border-box;margin:0px;padding:0px;border:0px;outline:0px;background:transparent;vertical-align:baseline;text-decoration-line:none" target="_blank">Toyota Technological Institute at Chicago</a></i></font></div></h3><h2 style="box-sizing:border-box;margin:0px;padding:0px 0px 10px;border:0px;outline:0px;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;vertical-align:baseline;color:rgb(51,51,51);line-height:1em"><font size="2" face="verdana, sans-serif"><a href="https://voices.uchicago.edu/machinelearning/events/" target="_blank">Machine Learning Seminar Series</a></font></h2><h6 style="font-size:14px;box-sizing:border-box;margin:0px;padding:0px 0px 10px;border:0px;outline:0px;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial;vertical-align:baseline;font-weight:500;line-height:1em;font-family:Montserrat,Helvetica,Arial,Lucida,sans-serif"><font color="#333333">Sign up for announcement email list at </font><a href="https://lists.uchicago.edu/web/subscribe/ml-announce." target="_blank"><font color="#0000ff"><span style="box-sizing:border-box;border-style:initial;border-color:initial;outline-color:initial;outline-style:initial;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial">https://lists.uchicago.edu/web/subscribe/ml-announce</span></font><font color="#333333">.</font></a></h6></div></div></div></div></div></div><div dir="ltr"><div><br></div>-- <br><div dir="ltr" data-smartmail="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div dir="ltr"><div dir="ltr"><div dir="ltr"><b><font color="#0b5394">Alicia McClarin</font></b><div><div><font color="#0b5394"><i>Toyota Technological Institute at Chicago</i></font></div><div><div><font color="#0b5394"><i><a href="https://www.google.com/maps/search/6045+S.+Kenwood+Ave.,%C2%A0+Office+518+Chicago,+IL+60637?entry=gmail&source=g">6045 S. Kenwood Ave., </a></i></font><i style="color:rgb(11,83,148)"><a href="https://www.google.com/maps/search/6045+S.+Kenwood+Ave.,%C2%A0+Office+518+Chicago,+IL+60637?entry=gmail&source=g">Office 518</a></i></div><div><i style="color:rgb(11,83,148)"><a href="https://www.google.com/maps/search/6045+S.+Kenwood+Ave.,%C2%A0+Office+518+Chicago,+IL+60637?entry=gmail&source=g">Chicago, IL 60637</a></i><br></div></div><div><i style="color:rgb(11,83,148)">773-834-3321</i><i style="color:rgb(11,83,148)"><br></i></div><div><a href="http://www.ttic.edu/" target="_blank"><font color="#0b5394"><i>www.ttic.edu</i></font></a></div></div></div></div></div></div></div></div></div></div>

</div></div>