0
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Please name one such measure of model complexity, so we can elaborate from there. $\endgroup$
    – lpounng
    Jun 16, 2023 at 2:10
  • $\begingroup$ Let us use VC complexity. $\endgroup$ Jun 16, 2023 at 9:28

1 Answer 1

0
$\begingroup$

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).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .