# Given an output space for a Neural Net, what is the minimum input space for training and prediction?

As far as I can tell, a neural net computes an arbitrary function from an input set $X$ to an output set $Y$ through the magic of back propagation (i.e. it computes $f: X \rightarrow Y$).

Suppose we have a known task, with a given input space and output space. Also, we have successfully trained a neural net to predict the function with 99% accuracy. Take a subset of the input space $Z \subset X$. What is the minimum size of $Z$ such that the neural net, when given $Z$ as an input space, correctly predicts the restricted function $f_Z : Z \rightarrow Y$? We assume that $|Y| < |Z| < |X|$.

There is another similar problem which is that we want to predict the same restricted function, but we train on the smaller set $Z$. Put simply, again suppose we have a trained a neural net on a large input set $X$, that successfully computes $f$ with 99% accuracy. I now want to collect less data as the input and train the neural net on a smaller subset of information, $Z \subset X$. I want the NN to compute the restricted function $f_Z$, ie the same function as $f$, with the same codomain, but a restricted domain $Z$.

What is the smallest input subset I can use for these two problems? Is it a function of the size of $Y$ or $X$? Is there, perhaps, a metric of the complexity of $f$, call it $Comp(f)$. Could $Z$ be bounded by a function of $Comp(f)$?

• "Is it a function of the size of Y and/or X?" -- Yes, but almost certainly not a practically computable function. Is this a theoretical question or are you coming from an actual application? – kbrose Jun 5 '18 at 20:36
• It's not really clear what you're asking for, as what you've described is effectively asking for generalization error. – Alex R. Jun 5 '18 at 21:58
• It seems impossible to say anything in general. You could have a binary classification task with a single relevant, but arbitrarily high-quality feature. Or you could have no relevant features. Or all features could be relevant. Or you could know that the problem is structured in a particular way, in which case you can get by using a smaller, specialized network (compare a CNN and FFN on MNIST to see what I mean). – Sycorax Jun 6 '18 at 15:36