Date & Time:
October 25, 2019 10:30 am – 11:30 am
TTIC 526, 6045 S. Kenwood Ave., Chicago, IL,
10/25/2019 10:30 AM 10/25/2019 11:30 AM America/Chicago Shay Moran (Technion) – Convex Set Disjointness, Distributed Learning of Halfspaces & LP Feasibility TTIC 526, 6045 S. Kenwood Ave., Chicago, IL,

Convex Set Disjointness, Distributed Learning of Halfspaces, and LP Feasibility

We study the Convex Set Disjointness (CSD) problem, where two players have input sets taken from an arbitrary fixed domain Usubset 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 Halfdpaces 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^2log n) and ~Omega(dlog 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).

Host: Machine Learning Seminar Series

Shay Moran

Department of Mathematics, Technion

Research interests: Mathematical problems that arise in computer science with a focus on combinatorial and geometric problems related to machine learning.

Related News & Events


“Machine Learning Foundations Accelerate Innovation and Promote Trustworthiness” by Rebecca Willett

Jan 26, 2024

Nightshade: Data Poisoning to Fight Generative AI with Ben Zhao

Jan 23, 2024
In the News

In The News: U.N. Officials Urge Regulation of Artificial Intelligence

"Security Council members said they feared that a new technology might prove a major threat to world peace."
Jul 27, 2023
UChicago CS News

UChicago Computer Scientists Bring in Generative Neural Networks to Stop Real-Time Video From Lagging

Jun 29, 2023
UChicago CS News

Computer Science Displays Catch Attention at MSI’s Annual Robot Block Party

Apr 07, 2023
UChicago CS News

UChicago, Stanford Researchers Explore How Robots and Computers Can Help Strangers Have Meaningful In-Person Conversations

Mar 29, 2023
Students posing at competition
UChicago CS News

UChicago Undergrad Team Places Second Overall In Regionals For World’s Largest Programming Competition

Mar 17, 2023
UChicago CS News

Postdoc Alum John Paparrizos Named ICDE Rising Star

Mar 15, 2023
UChicago CS News

New EAGER Grant to Asst. Prof. Eric Jonas Will Explore ML for Quantum Spectrometry

Mar 03, 2023
UChicago CS News

Assistant Professor Chenhao Tan Receives Sloan Research Fellowship

Feb 15, 2023
UChicago CS News

UChicago Scientists Develop New Tool to Protect Artists from AI Mimicry

Feb 13, 2023
In the News

Professors Rebecca Willett and Ben Zhao Discuss the Future of AI on Public Radio

Jan 26, 2023
arrow-down-largearrow-left-largearrow-right-large-greyarrow-right-large-yellowarrow-right-largearrow-right-smallbutton-arrowclosedocumentfacebookfacet-arrow-down-whitefacet-arrow-downPage 1CheckedCheckedicon-apple-t5backgroundLayer 1icon-google-t5icon-office365-t5icon-outlook-t5backgroundLayer 1icon-outlookcom-t5backgroundLayer 1icon-yahoo-t5backgroundLayer 1internal-yellowinternalintranetlinkedinlinkoutpauseplaypresentationsearch-bluesearchshareslider-arrow-nextslider-arrow-prevtwittervideoyoutube