Richard P. Stanley Seminar in Combinatorics

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).