TCS+ talk: Wednesday, May 20, Shyamal Patel, Columbia University
Clement Canonne
Our next talk (and the last of the semester!) will take place this coming Wednesday, May 20th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Shyamal Patel from Columbia University will speak about "Learning Functions of Halfspaces" (abstract below).
Please sign up on the online form at https://sites.google.com/view/tcsplus/welcome/next-tcs-talk if you wish to join the talk as an individual or a group. Registration is /not/ required to attend the interactive talk, and the link will be posted on the website the day prior to the talk; however, by registering in the form, you will receive a reminder, along with the link. (The link to the recording will also be posted on our website afterwards.)
Hoping to see you all there,
The organizers
-------------------------------
Speaker: Shyamal Patel (Columbia University)
Title: Learning Functions of Halfspaces
Abstract: Learning halfspaces is one of the most basic and fundamental problems in learning theory. While we have a good understanding of the problem, simple generalizations such as learning an intersection of halfspaces appear much more challenging. While learning an intersection of halfspaces can be done efficiently if we assume our data is drawn from a uniform or log-concave distribution, there are large gaps in our understanding when we make no assumptions on the background distribution. In particular, even for learning an intersection of two halfspaces, we have no non-trivial learning algorithms and no evidence that the problem requires super-polynomial time.
In this talk, we’ll describe a sub-exponential time algorithm for learning an intersection of halfspaces and more generally for learning an arbitrary function of ~O(log(n)) halfspaces (joint work with Josh Alman and Rocco Servedio).