On the Cryptographic Hardness of Learning Single Periodic Neurons
  We show a simple reduction which demonstrates the cryptographic hardness of
learning a single periodic neuron over isotropic Gaussian distributions in the
presence of noise. More precisely, our reduction shows that any polynomial-time
algorithm (not necessarily gradient-based) for learning such functions under
small noise implies a polynomial-time quantum algorithm for solving worst-case
lattice problems, whose hardness form the foundation of lattice-based
cryptography. Our core hard family of functions, which are well-approximated by
one-layer neural networks, take the general form of a univariate periodic
function applied to an affine projection of the data. These functions have
appeared in previous seminal works which demonstrate their hardness against
gradient-based (Shamir'18), and Statistical Query (SQ) algorithms (Song et
al.'17). We show that if (polynomially) small noise is added to the labels, the
intractability of learning these functions applies to all polynomial-time
algorithms, beyond gradient-based and SQ algorithms, under the aforementioned
cryptographic assumptions. Moreover, we demonstrate the necessity of noise in
the hardness result by designing a polynomial-time algorithm for learning
certain families of such functions under exponentially small adversarial noise.
Our proposed algorithm is not a gradient-based or an SQ algorithm, but is
rather based on the celebrated Lenstra-Lenstra-Lov\'asz (LLL) lattice basis
reduction algorithm. Furthermore, in the absence of noise, this algorithm can
be directly applied to solve CLWE detection (Bruna et al.'21) and phase
retrieval with an optimal sample complexity of $d+1$ samples. In the former
case, this improves upon the quadratic-in-$d$ sample complexity required in
(Bruna et al.'21).
