@inproceedings{b30c82cde31f45bfab0be16ac1a59870,
title = "Embedding hard learning problems into gaussian space",
abstract = "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 theoretical computer science and show that any algorithm for agnostically learning halfspaces requires nΩ(log (1/ε)) time under the assumption that κ-sparse LPN requires nΩ(κ) 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. [1] who show that sparse polynomials are learnable under 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.",
keywords = "Agnostic learning, Distribution-specific hardness of learning, Gaussian space, Halfspacelearning",
author = "Adam Klivans and Pravesh Kothari",
note = "Publisher Copyright: {\textcopyright} Adam Klivans and Pravesh Kothari.; 17th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2014 and the 18th International Workshop on Randomization and Computation, RANDOM 2014 ; Conference date: 04-09-2014 Through 06-09-2014",
year = "2014",
month = sep,
day = "1",
doi = "10.4230/LIPIcs.APPROX-RANDOM.2014.793",
language = "English (US)",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
pages = "793--809",
editor = "Klaus Jansen and Rolim, {Jose D. P.} and Devanur, {Nikhil R.} and Cristopher Moore",
booktitle = "Leibniz International Proceedings in Informatics, LIPIcs",
address = "Germany",
}