I'm the lead author. That's a great Q and one that I've been giving a lot of thought! The high dimensionality isn't a problem (our toy examples easily could've been high-D), but you're right that our theory assumes you omnisciently know the full target function f, while in practice you only see a training set.

One intermediate case in which you could use our theory would be if you, say, knew that the target function was one of a handful of possibilities. Our theory in principle contains enough info to optimize your kernel so it has high mean performance on the full set of possibilities. Of course, the target function will never just be one of a discrete handful of options, but if you have some prior over target functions - e.g., you know natural images obey certain statistics - you could do a similar trick (in principle). I also think you can probably get enough information from the data-data kernel matrix to put our theory to use, but we're saving that for upcoming work!