In neural networks, "weight regularization" is often used as a so called "complexity penalty" in order to make sure that the network generalizes better from training data.
Similarly, in "program induction", the kolmogorov-complexity is used as a complexity penalty (e.g. see Solomonoff induction): If we have a training problem consisting of input output pairs $(1,2), (456,457), (23,24)$, then the simplest program that computes this is simply
program1(x) return x + 1;
Just as in the neural net case, by applying a complexity penalty in program induction, we expect the resulting program to better generalize than a more complex program that also satisfied the training data, like:
program2(x) if x != 784 AND x != 3 AND x != 78893 then return x + 1; else x = x + 833; return x^945 + Sqrt(x + Log x );
The k-complexity penalty in program induction and the weight-regularization penalty in neural networks seem to perform the same function for generalization from training data.
However, this somewhat surprises me as they seem to be very different types. So I am wondering: Is there an analysis of the similarities and differences between these (and possibly other) complexity penalties in the context of learning from training data?