Richard P. Stanley Seminar in Combinatorics: Learning Functions of Halfspaces

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 roughly log(n) halfspaces (joint work with Josh Alman and Rocco Servedio).

For information about the Richard P. Stanley Seminar in Combinatorics, visit… https://math.mit.edu/combin/