How big does a Neural Net need to be to learn anything
The size of the Neural Network is usually treated as a hyper-parameter. You need to estimate it from a separate cross-validation set. 

For Neural nets there are no theoretical proven bounds (there are some papers here and there, but they are not applicable in practice). 

You need to use the good old "cross-validation" method to search for the best fit value of the size of NN. 

P.S. : There is a paper from Yoshua Bengio with all trick and traits for training such machines. 

https://arxiv.org/abs/1206.5533