How big does a Neural Net need to be to learn anything Is there literature on how big a net needs to be to learn an arbitrary classification problem where the input is a n-bit integer and the output is one of k categories? I'm interested in both a theoretical bound and the size needed in practice with current training and initialization techniques. 

To be specific, the neural net is allowed to see all possible inputs and their respective outputs, so I will not hide anything from the training set, as the function is not assumed to have any structure whatsoever.
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