Expressivity of neural networks, how much information can be stored

I want to know whether a given neural network (with a finite number of nodes) is able to store all injective maps f: D -> C, where D has cardinality k and C has cardinality N (so the number of maps is N! over (N-k)! ). For example is a network with 1000 nodes able to store 60 injective maps from {1,2,3} to {1,2,3,4,5}?

(By storing information I mean something like: when classifying information the network can access and use the information)

In particular I was curious if the above question can be translated to a question about the VC-dimension of a neural network. Can a question about storing injective maps in a neural network be translated to a question about the VC-dimension of a neural network?

EDIT: I’m interested in something like the following result

There are 60 functions, note that we can represent this with 6 bits The codomain consists of 5 elements, which can be encoded by 3 bits (since 5 < 2^3) We need to map 3 elements of the domain to an element of the co-domain, so we need 3 times 3 bits for each function So to encode 60 functions we need 60 * 3 * 3 bits

In general we need (N! / (N-k)! ) * k * log_2(N) bits Note that (N-k+1)^k < N! / (N-k)! < N^k and even (N-k)^k < (N! / (N-k)! ) * k * log_2(N) < N^k

One weight in a neural network is 32 bits If we have X weights, then we have X*32 bits

So if X*32 is smaller than log_2(N-k) * k, then it’s not possible to express all the functions in the network [I’m actually more interested in negative results like the one I gave, sorry if that’s confusing. Positive results are welcome as well.]

• I'm not sure what your question is. It sounds like you've already got an answer, so I'm not sure what you need us for.
– D.W.
Oct 3 '20 at 21:36

However, if you're willing to accept empirical evidence rather than theorems and proofs, research has demonstrated empirically that if you choose a deep neural network architecture with sufficient capacity and you train for long enough, neural nets can memorize the training set and achieve 100% accuracy on the training set, at least for a randomly chosen function $$f$$ . This may not tell you exactly what size neural network you need to ensure that it can express all such functions, and it's not a proof or a guarantee.