ECCC-Report TR13-008https://eccc.weizmann.ac.il/report/2013/008Comments and Revisions published for TR13-008en-usTue, 08 Jan 2013 22:04:52 +0200
Paper TR13-008
| Moment-Matching Polynomials |
Adam Klivans,
Raghu Meka
https://eccc.weizmann.ac.il/report/2013/008We give a new framework for proving the existence of low-degree, polynomial approximators for Boolean functions with respect to broad classes of non-product distributions. Our proofs use techniques related to the classical moment problem and deviate significantly from known Fourier-based methods, which require the underlying distribution to have some product structure.
Our main application is the first polynomial-time algorithm for agnostically learning any function of a constant number of halfspaces with respect to any log-concave distribution (for any constant accuracy parameter). This result was not known even for the case of learning the intersection of two halfspaces without noise. Additionally, we show that in the "smoothed-analysis" setting, the above results hold with respect to distributions that have sub-exponential tails, a property satisfied by many natural and well-studied distributions in machine learning.
Given that our algorithms can be implemented using Support Vector Machines (SVMs) with a polynomial kernel, these results give a rigorous theoretical explanation as to why many kernel methods work so well in practice.Tue, 08 Jan 2013 22:04:52 +0200https://eccc.weizmann.ac.il/report/2013/008