When designing a machine-learning system, there are various parameters that have to be determined. I am interested in the following general question: is it possible to construct a dataset on which the system will have good performance with some specific set of parameters, but not with other paramteres?

To be more concrete, let's focus on neural networks. Suppose we have a simple neural network: a multilayer perceptron with a single hidden layer. The size of the input is fixed, the activation function is fixed (e.g. tanh), and the output is binary. The only parameter that has to be determined is the size of the hidden layer.

My question is: given a number $n$, is it possible to construct a dataset $D_n$ such that:

• The MLP with $n$ hidden nodes has good performance on $D_n$ (e.g. in 10-fold cross validation);
• The MLP with $n-1$ hidden nodes has bad performance on $D_n$

?

_{Note: I asked in CS theory but got no reply.}