Part of Advances in Neural Information Processing Systems 36 (NeurIPS 2023) Main Conference Track
Amit Daniely, Nati Srebro, Gal Vardi
We present a PTAS for learning random constant-depth networks. We show that for any fixed ϵ>0 and depth i, there is a poly-time algorithm that for any distribution on √d⋅Sd−1 learns random Xavier networks of depth i, up to an additive error of ϵ. The algorithm runs in time and sample complexity of (ˉd)poly(ϵ−1), where ˉd is the size of the network. For some cases of sigmoid and ReLU-like activations the bound can be improved to (ˉd)polylog(ϵ−1), resulting in a quasi-poly-time algorithm for learning constant depth random networks.