By using an informal term such as "generalize", I am aware I am getting close to philosophical territory, and that my question could be seen as unsuitable for CV.
I will do my best to be specific enough in phrasing it, to allow for meaningful answers by the standards of this community.
I am trying to gain some broad overview of the methods with which ML researchers and practitioners, statisticians and mathematicians, tackle the question whether a model successfully learned to generalize -- or whether it failed to do so.
Or maybe better, to avoid framing the question categorically: to which degree a model learned to generalize?
In other words, I am asking which formally specified (and to remain practical: computable and computationally tractable) methods exist that can be seen as addressing the informal question posed in the title, that of a model's or method's ability to 'generalize'.
Does that question make any sense up to this point? And is it possible to answer it in the context of CV?
Some additional remarks, trying to clarify the question further:
What I'm asking about is maybe a taxonomy of sorts (happily accepting your personal taxonomy, in case no canonical one exists) of such methods, of both 'hard' formal results, and methods relying on empirical evaluation.
Closely related to 'generalization', and, I'm afraid, equally underspecified: the notion of systematicity. A model's ability to generalize often seems to be mentioned alongside the question whether the model found a systematical solution for a task it was trained on. Does that help in any way? (Probably not.)
Maybe the following distinction needs to be made: mentioning "models" above, I somewhat conflate the general learning algorithm or method, and particular instances of these methods, i.e. models that are constructed by the algorithm from training data.
My question then contains at least two sub-questions: ways to speak about the 'generalization' ability of the algorithm itself, and which to evaluate the same for a trained model?
At least in the context of neural networks (the family of models I'm most familiar with), it seems to me that the 'generalization' question is answered mostly empirically, and mostly by one particular method only (perhaps the only one available, in reality?): by separating the data into distinct sets (standard being 2 for train/test, or 3 for train/test/evaluation), keeping data used for training and performance evaluation separate.
As a consequence, we can then consider overfitting of a model (as measured by the model's performance on the withheld data), and find ways to combat it (regularization).
Which brings me to consider another distinction: (i) 'generalization' as performance over unseen data that we (plausibly) know was generated by the same function that also generated the training data, in contrast to: (ii) generalization to (unseen) data that we might only hypothesize or believe to be produced by the same underlying, general function.
By my own (still very incomplete) understanding, it appears then that we are usually only concerned with evaluating 'generalization' of the first type (i.e. by measuring and comparing performance over unseen data generated with some certainty by the same function as the training data -- I say "with some certainty", because we either chose the function generating the data ourselves, or following from the relatively natural assumption that the same function generated the particular data set we used, say, a set of 1 million 400 by 600 px pictures of dancing cats), while generalization of the second type is not usually measured or considered (i.e. performance over unseen examples that are in a sense truly new and different from the ones encountered during training, but that we might believe are the product of the same function that generated the training data).
Here's another strong possibility: I am completely wrong with that characterization (not really surprising, considering how confused I still am about all things ML). If that's the case, my apologies for misrepresenting (and misunderstanding) the current approaches.