2 papers
cs.LG2020
Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descent
Surbhi Goel, Aravind Gollakota, Zhihan Jin +2
We prove the first superpolynomial lower bounds for learning one-layer neural networks with respect to the Gaussian distribution using gradient descent. We show that any classifier…
cs.DS2019
Approximating Permanent of Random Matrices with Vanishing Mean: Made Better and Simpler
Zhengfeng Ji, Zhihan Jin, Pinyan Lu
The algorithm and complexity of approximating the permanent of a matrix is an extensively studied topic. Recently, its connection with quantum supremacy and more specifically Boson…