A unified implicit moment tensor estimation framework yields poly(d,k)-time learners for mixtures of linear regressions, spherical Gaussians, and positive sums of ReLU activations, with one unproven step in the regression application.
On the Hardness of Learning One Hidden Layer Neural Networks
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
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.
fields
cs.DS 1years
2024 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models
A unified implicit moment tensor estimation framework yields poly(d,k)-time learners for mixtures of linear regressions, spherical Gaussians, and positive sums of ReLU activations, with one unproven step in the regression application.