Poster
Most Neural Networks Are Almost Learnable
Amit Daniely · Nati Srebro · Gal Vardi
Abstract:
We present a PTAS for learning random constant-depth networks. We show that for any fixed and depth , there is a poly-time algorithm that for any distribution on learns random Xavier networks of depth , up to an additive error of . The algorithm runs in time and sample complexity of , where is the size of the network. For some cases of sigmoid and ReLU-like activations the bound can be improved to , resulting in a quasi-poly-time algorithm for learning constant depth random networks.
Chat is not available.