18851

Video URL

https://simons.berkeley.edu/talks/cryptographic-hardness-learning-one-hidden-layer-neural-networks

On the Cryptographic Hardness of Learning One-Hidden Layer Neural Networks

(2021). On the Cryptographic Hardness of Learning One-Hidden Layer Neural Networks. The Simons Institute for the Theory of Computing. https://simons.berkeley.edu/talks/cryptographic-hardness-learning-one-hidden-layer-neural-networks

On the Cryptographic Hardness of Learning One-Hidden Layer Neural Networks. The Simons Institute for the Theory of Computing, Dec. 07, 2021, https://simons.berkeley.edu/talks/cryptographic-hardness-learning-one-hidden-layer-neural-networks 

          @misc{ scivideos_18851,
            doi = {},
            url = {https://simons.berkeley.edu/talks/cryptographic-hardness-learning-one-hidden-layer-neural-networks},
            author = {},
            keywords = {},
            language = {en},
            title = {On the Cryptographic Hardness of Learning One-Hidden Layer Neural Networks},
            publisher = {The Simons Institute for the Theory of Computing},
            year = {2021},
            month = {dec},
            note = {18851 see, \url{https://scivideos.org/Simons-Institute/18851}}
          }
Ilias Zadik (MIT)
Talk number18851
Source RepositorySimons Institute
Subject

Abstract

In this short talk, I will share some recent progress on the hardness of learning shallow RELU neural networks (Relu-NN) and polynomially small adversarial noise. We will present a result that efficiently learning an 1-hidden layer Relu-NN under Gaussian input and adversarial noise is "cryptographically hard", in the sense that it implies a polynomial-time quantum algorithm for the worst-case shortest vector problem.