How does neural net complexity relate to other complexity measures?

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?

• It's not clear to me what you are asking, or what kind of analysis you're looking for. Of course, they're both instances of regularization; they both are applying Occam's razor. Perhaps your surprise is primarily due to the fact that this is the first time you're seeing it. I'm not sure what else there would be to say, so unless you can articulate a more specific question, it's hard for me to tell what an answer to this question would look like. – D.W. Feb 10 at 20:18