| |
|
| |
|
Adam Klivans
University of Texas at Austin
Lower Bounds on the Statistical-Query Dimension of Intersections of Halfspaces
June 12, 2006 3:00pm
Abstract:
I proves new lower bounds for learning intersections of halfspaces, one of the most important concept classes in computational learning theory.
Our main result is that any statistical-query algorithm for learning the intersection of $\sqrt{n}$ halfspaces in $n$ dimensions must make $2^{\Omega(\sqrt{n})}$ queries. This is the first non-trivial lower bound on the statistical-query dimension for this concept class (the previous best lower bound was $n^{\Omega(\log n)}$). Our hardness result holds even for intersections of majorities (low-weight halfspaces).
We also show that the intersection of two majorities (low-weight
halfspaces) cannot be computed by a polynomial threshold function (PTF) with fewer than $n^{\Omega((\log n)/\log\log n)}$ monomials. This is the first super-polynomial lower bound on the PTF length of this concept class, and is nearly optimal. As a consequence, intersections of halfspaces do not belong to the class TOP (polynomial size threshold of parities), the most expressive concept class known to be learnable via Jackson's Harmonic Sieve algorithm.
The above results are joint work with Alexander Sherstov. If time permits we will discuss a new connection between learning Boolean circuits and proving circuit lower bounds (joint work with Lance Fortnow).
If you have questions, or would like to meet the speaker, please contact Ponda at 4-1994 or pondabarnes@tti-c.org. For information on future TTI-C talks or events, please go to the TTI-C Events page.