## 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.

Original language | English (US) |
---|---|

Title of host publication | Leibniz International Proceedings in Informatics, LIPIcs |

Editors | Klaus Jansen, Cristopher Moore, Nikhil R. Devanur, Jose D. P. Rolim |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

Pages | 793-809 |

Number of pages | 17 |

ISBN (Electronic) | 9783939897743 |

DOIs | |

State | Published - Sep 1 2014 |

Externally published | Yes |

Event | 17th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2014 and the 18th International Workshop on Randomization and Computation, RANDOM 2014 - Barcelona, Spain Duration: Sep 4 2014 → Sep 6 2014 |

### Publication series

Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Volume | 28 |

ISSN (Print) | 1868-8969 |

### Other

Other | 17th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2014 and the 18th International Workshop on Randomization and Computation, RANDOM 2014 |
---|---|

Country | Spain |

City | Barcelona |

Period | 9/4/14 → 9/6/14 |

## All Science Journal Classification (ASJC) codes

- Software