On the Hardness of Learning One Hidden Layer Neural Networks
<|reference_start|>On the Hardness of Learning One Hidden Layer Neural Networks: 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.<|reference_end|>
@article{li2024on,
    title={On the Hardness of Learning One Hidden Layer Neural Networks},
    author={Shuchen Li, Ilias Zadik, Manolis Zampetakis},
    journal={arXiv preprint arXiv:2410.03477},
    year={2024},
    archivePrefix={arXiv},
    eprint={2410.03477},
    primaryClass={cs.LG cs.CC math.ST stat.ML stat.TH}
}