For given units of a measure of model complexity, how many examples do we need to train a network to get the model right and generalize?

Question

Please name one such measure of model complexity, so we can elaborate from there. — lpounng, Jun 16 '23 at 02:10

score 0 · Answer 1 · answered Jun 19 '23 at 04:36

In general, we won't know: it is an undecidable problem.

For reference, Bashir et al. and Sehra et al. proved that for a given dataset, (even if given unlimited training time) it is undecidable whether an encodable learning algorithm will always overfit or underfit respectively. So we can never know if we have got the 'right' model (in terms of generalization error).

FYI, This problem is related to the halting problem and minimum description length (MDL).

For given units of a measure of model complexity, how many examples do we need to train a network to get the model right and generalize?

1 Answers1