Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR14-063 | 23rd April 2014 02:46

Embedding Hard Learning Problems into Gaussian Space

RSS-Feed




TR14-063
Authors: Adam Klivans, Pravesh Kothari
Publication: 23rd April 2014 20:12
Downloads: 4123
Keywords: 


Abstract:

We give the first representation-independent hardness result for agnostically learning halfspaces with respect to the Gaussian distribution. We reduce from the problem of learning sparse parities with noise with respect to the uniform distribution on the hypercube (sparse LPN), a notoriously hard problem in computer science and show that any algorithm for agnostically learning halfspaces requires $n^{\Omega(\log{(1/\epsilon)})}$ time, ruling out a polynomial time algorithm for the problem. As far as we are aware, this is the first representation-independent hardness result for supervised learning when the underlying distribution is restricted to be a Gaussian.

We also show that the problem of agnostically learning sparse polynomials with respect to the Gaussian distribution in polynomial time is as hard as PAC learning DNFs on the uniform distribution in polynomial time. This complements the surprising result of Andoni et. al (2014} who show that sparse polynomials are learnable under {\em random} Gaussian noise in polynomial time.

Taken together, these results show the inherent difficulty of designing supervised learning algorithms in Euclidean space even in the presence of strong distributional assumptions. Our results use a novel embedding of random labeled examples from the uniform distribution on the Boolean hypercube into random labeled examples from the Gaussian distribution that allows us to relate the hardness of learning problems on two different domains and distributions.



ISSN 1433-8092 | Imprint