Good characterization. It's worth noting that learning theory never gives any kind of guarantee that you will actually find a function that provides a good fit to the training data, it just tells you that if you do, and the function comes from a low-complexity set, it will probably give good generalization.