On the Hardness of Learning One Hidden Layer Neural Networks
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866929527947526144 |
|---|---|
| author | Li, Shuchen Zadik, Ilias Zampetakis, Manolis |
| author_facet | Li, Shuchen Zadik, Ilias Zampetakis, Manolis |
| contents | In this work, we consider the problem of learning one hidden layer ReLU neural networks with inputs from $\mathbb{R}^d$. We show that this learning problem is hard under standard cryptographic assumptions even when: (1) the size of the neural network is polynomial in $d$, (2) its input distribution is a standard Gaussian, and (3) the noise is Gaussian and polynomially small in $d$. Our hardness result is based on the hardness of the Continuous Learning with Errors (CLWE) problem, and in particular, is based on the largely believed worst-case hardness of approximately solving the shortest vector problem up to a multiplicative polynomial factor. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_03477 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the Hardness of Learning One Hidden Layer Neural Networks Li, Shuchen Zadik, Ilias Zampetakis, Manolis Machine Learning Computational Complexity Statistics Theory In this work, we consider the problem of learning one hidden layer ReLU neural networks with inputs from $\mathbb{R}^d$. We show that this learning problem is hard under standard cryptographic assumptions even when: (1) the size of the neural network is polynomial in $d$, (2) its input distribution is a standard Gaussian, and (3) the noise is Gaussian and polynomially small in $d$. Our hardness result is based on the hardness of the Continuous Learning with Errors (CLWE) problem, and in particular, is based on the largely believed worst-case hardness of approximately solving the shortest vector problem up to a multiplicative polynomial factor. |
| title | On the Hardness of Learning One Hidden Layer Neural Networks |
| topic | Machine Learning Computational Complexity Statistics Theory |
| url | https://arxiv.org/abs/2410.03477 |