How can I randomly sample the space of consistent neural networks for given data?
I am trying to formalize your question before discussing it.
If I understand correctly, you ask for the following:
For $X \subset \mathbb{R}^{n}$ and $Y \subset \mathbb{R}^m$, let $f:X \rightarrow Y$ be a map.
Let $w \in \mathbb{R}^q$ be weights. We consider a neural network $g: \mathbb{R}^{n}\times \mathbb{R}^q \rightarrow \mathbb{R}^m$, and let $g^{(w)}: \mathbb{R}^{n} \rightarrow \mathbb{R}^{m}, x \mapsto g(x,w)$ be the neural network parametrized by $w$.
Now you want to sample from the set $\underline{W}(f,g,X):= \{w \in \mathbb{R}^{q} \mid f = (g^{(w)})_{\mid X} \}$.
However, I think constructing $\underline{W}(f,g,X)$ is very difficult in general.
The following question arises:
Do you already have some $w \in \underline{W}(f,g,X)$ ?
If not, note that $\underline{W}(f,g,X) = \emptyset$ is possible! (its easy to construct an example for that)
Note also that all known universal approximation theorems have some requirements on $f$, and only state that $f$ can be approximated by some neural network. However, for fixed architecture, it might be that there is no $w \in \mathbb{R}^q$ with $f = (g^{(w)})_{\mid X}$ nor that $f$ can be approximated by $(g^{(w)})_{\mid X}$ (e.g. in terms of the uniform-norm).
If you have some $w \in \underline{W}(f,g,X)$, there are certains trivial permutations (e.g. permuting the nodes of a fully-connected layer, or some channels). Apart from that, I am not aware of a full description of $\underline{W}(f,g,X)$. And without further details or constraints, I think its there is no general answer at the moment.
I hope this helps!