It's well known that in most (if not all?) computations you can trade time and space resources. An extreme example might be creating an infinitely large lookup table of all composites produced from the multiplication of two primes. Using this table, you could simply lookup the primes for a composite in constant time rather than factoring the composite, which would require superpolynomial time (this of course ignores the initial computation of the lookup table).
But, can all computational resources be traded for time? And, more specifically, can we trade the number of samples required to learn a function for time? Any resources providing a discussion of this (or just a great explanation) would be fantastic. See the background to this question for some more (and important!) context.
In a recent discussion I held that sample complexity (i.e. the data resource) is different from communication, circuit, space, or other time reducible complexity resources. In particular, if some superpolynomial quantum advantage in sample complexity exists for some learning problem (e.g. see this classic paper or this more recent one), then it may imply that there is a difference in the ability of the classical and quantum learners to "see" the information contained in the sample distribution being used to learn some target function. In such a situation, the term "quantum speedup" may not be appropriate – from the classical perspective, more time cannot make up for the lack of data, implying that sample complexity is (or can be) time irreducible.
More recently, I think I've begun to see how the term "quantum speedup" may still be appropriate in describing advantages in sample complexity. As mentioned, my past view was that the data resource is not time reducible, however, I suspect that this may not be correct. In particular, given superpolynomial time resources, a target function may be classically learnable with a polynomial number of samples by their repeated analysis – assuming the polynomial number of samples contains the necessary information for some learner to learn the target function (e.g. a quantum learner, which in this case could be used to prove that the polynomial samples contain sufficient information by some interactive proof with the classical verifier). Were this to be the case, then it is clear that the information to learn the target function does exist in the polynomial number of samples and that the classical learner simply requires (say) superpolynomial time to learn the target function from the polynomial number of samples. This would imply that sample complexity is (at least for some learning problems) time reducible.
Thus the question: Can the classical learner take that polynomial number of samples and, with superpolynomial time, learn the target function at all? That is to say, is it the case that the information is simply not accessible to a classical learner, irrespective of how long you let it compute on those polynomial number of samples (i.e. is the data resource in this context time irreducible)?
I think my initial intuition around the time irreducibility of sample complexity can be summed up by this crude analogy: Where someone with 20/20 vision looking into the distance may see mountains and certain fine details (houses, trees, a radio antenna), someone with 20/80 vision may be unable to see those fine details and only make out the shapes of the mountains – no matter how long they stare at them; they need more data, which in this scenario would mean getting a closer look by physically moving closer (more data) or interrogating their friend with 20/20 vision (interactive proof).
All said, my intuition tells me that the reducibility of sample complexity to time varies by some inherent structure of the learning problem and its interaction with the properties of the type of information one is working with (e.g. classical, quantum), though this is very much a half-baked intuition. Is there a paper where this question has already been answered?