Yes, they use what's called the VC-dimension. Chapter 20 of the book Understanding Machine Learning (available for free online http://www.cs.huji.ac.il/~shais/

Yes, they use what's called the VC-dimension. Chapter 20 of the book Understanding Machine Learning (available for free online http://www.cs.huji.ac.il/~shais/UnderstandingMachineLearning/ http://www.cs.huji.ac.il/~shais/UnderstandingMachineLearning...) has a good introduction to the basics of this theory. The short story is that VC dimension describes "worst case" behavior of a learning algorithm. This is a good predictor of performance on really hard problems, but lots of modern problems turn out to be theoretically easy. For example, neural networks trained on images work much better than we would guess based on the VC dimension of neural networks. This is because the distribution of images is closer to a best case scenario than a worst case scenario. Lots of research is being done to determine when we are in a best case scenario. The "simplest" is called the Rademacher complexity. (See Chapter 26 of the UML book.) Simplest is in quotes because most phd-level students in machine learning that I've met don't even understand what a rademacher complexity is unless they are specializing in theory. And the rademacher complexity doesn't really even come close to capturing why neural networks work well on images either.