2 ms·
This one's tough to answer, actually. The truly optimal learner would have to use an incomputable procedure; even time-and-space bounded versions of this proce
by eli_gottlieb 12y ago
This one's tough to answer, actually. The truly optimal learner would have to use an incomputable procedure; even time-and-space bounded versions of this procedure have additive constants larger than the Solar System.
However, it's more-or-less a matter of compression, which, by some of the basics of Kolmogorov Complexity, tells us we face a nasty question: it's undecidable/incomputable/unprovable whether a given compression algorithm is the best compressor for the data you're giving it. So it's incomputable in general whether or not you've got the best learning algorithm for your sense-data: whether it compresses your observations optimally. You really won't know you could self-improve with a better compressor until you actually find the better compressor, if you ever do at all.
An agent bounded in terms of both compute-time and sample complexity (the amount of sense-data it can learn from before being required to make a prediction) will probably face something like a sigmoid curve, where the initial self-improvements are much easier and more useful while the later ones have diminishing marginal return in terms of how much they can reduce their prediction error versus how much CPU time they have to invest to both find and run the improved algorithm.