On the Cryptographic Hardness of Learning One-Hidden Layer Neural Networks
summary
Claim: learning one-hidden-layer ReLU networks with Gaussian inputs and polynomial width is provably hard to do better than chance in polynomial time once each label gets an inverse-polynomial adversarial noise term (β = 1/poly(d)). Proof gives a reduction from continuous learning with errors to a cosine neuron instance, then approximates that cosine by a polynomial-width ReLU net to within 1/poly(d) error. Combining Bruna–Regev–Song–Tang (CLWE → worst-case gap SVP) yields that a polytime learner would imply a polytime algorithm for worst-case gap SVP, contradicting lattice-cryptography assumptions; no empirical build or runtime attack is presented.
AI-written summary · about
chapters (8)
- 0:00Intro
- 1:04Learn 1. Hidden Layer Relu NN
- 3:08Main Result: Cryptographic Hardness
- 6:46The cosine neuron: a generalized linear model
- 8:39Connection with 1-hidden layer NN
- 10:59Continuous Learning with Errors (CLWE)
- 13:19The cosine neuron: Worst case hardness (theorem)
- 14:48The cosine neuron: Worst case hardness (a proof idea) Cosine Neuron
related talks
30mComputational Barriers For Learning Some Generalized Linear Models
56mContinuous LWE is as Hard as LWE
59mTutorial: Statistical Learning Theory and Neural Networks I
01h 04mRandomized Embeddings and Neural Networks
01h 03mUnderstanding ReLU Networks Through Graph Problems and Polyhedra
01h 28mThe Learning With Errors Problem and Cryptographic Applications
50mLearning and Generalization in Over-parametrized Neural Networks, Going Beyond Kernels
32mTight Hardness Results for Training Depth-2 ReLU Networks