Are all computational resources reducible to the time resource?

Question

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.

---

Background

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?

Answer 1

can we trade the number of samples required to learn a function for time

In general, the answer to this question will be no, because there are two different scaling behaviors being conflated:

a. Sample complexity: The number of samples sufficient to accurately learn a dataset, from any randomly sampled training set.$^1$

b. Algorithmic complexity: Some measure of runtime of an algorithm with respect to an input size.

To be more formal lets consider a learning problem as follows: There is some domain of patterns $\mathcal{X}$ that can be stored and processed classically, and a label function $f: \mathcal{X} \rightarrow \{0,1\}$, and the goal of the learner is to learn some function $h(x)$ that assigns each $x\in \mathcal{X}$ a label $y \in \{0,1\}$. The patterns are accessible by drawing from a probability distribution $\mathcal{D}$ defined over $\mathcal{X}$, and we construct a "training set" $S = \{(x_1, f(x_1)), \dots, (x_m, f(x_m))\}$ for the learner by drawing $m$ samples according to $\mathcal{D}$ and providing their true labels. To incorporate prior knowledge (which we should do, as the No Free Lunch theorem demonstrates) we require our function is taken from some hypothesis class: $h\in \mathcal{H}$. Then the sample complexity (a) is the smallest number $m$ for which we are guaranteed to, with high probability, be able to learn some $h$ that approximates $f$ with small error.

However for algorithmic complexity, all we can really say is there is some parameter $n$ for which a classical learner will require runtime scaling as $C(n)$ to implement any given $h$ on some pattern in $S$ while a quantum learner will require runtime scaling as $Q(n)$.

There are a few comments that I think demonstrate why these should not be thought of as interchangeable:

1. Fix $S$. Given any algorithm employing a quantum computer (giving rise to a hypothesis class $\mathcal{H}_Q$) to learn $f$ with high accuracy over $S$, you immediately have a purely classical algorithm that performs with equal accuracy on $S$. That classical algorithm learns a function in $\mathcal{H}_C=\mathcal{H}_Q$ by the following procedure: Simulate the quantum learning algorithm on a classical computer.

2. The opposite of (1) is also true: any classical learner successfully employing $\mathcal{H}_C$ to learn $f$ on $S$ can be reproduced by employing a quantum computer, since quantum computation is universal.

3. Fix $\mathcal{H}$. The sample complexity for learning $f$ by employing $\mathcal{H}$ may or may not have a clear relationship with $C(n)$ or $Q(n)$. For instance say we are promised that $f$ is a hyperplane in $\mathbb{C}^d$. We fix $\mathcal{H}_Q=\mathcal{H}_C$ to be the set of functions of the form $\langle w, x\rangle$ with $x \in \mathcal{X} \subseteq \mathbb{C}^d$ and $w \in \mathbb{C}^d$. Hyperplane classifiers on $\mathbb{C}^d$ tend to be cheap to implement so $C(n)$ is small, but implementing any specific hyperplane classifier using a quantum computer with $n=\log d$ qubits could require a very deep circuit. But both of these hypothesis classes have equivalent VC dimension and so at least under the PAC learning framework you end up with the same sample complexity.

Also note that in the second reference you mentioned, the authors are very explicit that they wish to compare the quantum learning algorithm to an efficient classical learner for which $C(n) = \text{poly}(n)$, and then describe how no such learner exists for the learning problem they've constructed. If they tried to compare to a classical learner with no restrictions on $C(n)$, then by comment 1 above such a learner is trivial to find. I don't recall seeing arguments related to a sampling complexity improvement for the quantum algorithm, so I would be interested to understand how that figures into the speedup described by the paper.

---

$^1$ I believe this definition is more common than using the minimum number of samples required to learn a function. I think it is also more useful: If there truly is some minimum sample size necessary to learn $f$, I don't have any guarantee that I draw the corresponding sample from $\mathcal{D}^m$. So at least to me it makes more sense to start with the assumption that you must draw samples uniformly at random from $\mathcal{D}^m$, and then figure out how big $m$ has to be before you can confidently learn $f$.

Answer 2

Time irreducible & Inaccessibility (philosophical + analytically):

Interesting question! Let me start antichronological with your lovely example. Neal has 20/20 and Peter 20/80. You are saying that Peter needs to get closer to see the mountains and it's infrastructure clearly. So you are changing the equal base condition both had at the beginning. That's okey but how does Peter know there is more to see out there!?

This is a good analogy to our "Problem" related to time. The computational complexity theory is saying that any problem has it's amount of resources needed [such as time and storage] to be solved computational by algorithms. Whether it's worth it is of course another question. The problems get their own classifications etc.. But what really interesting is, is their bounds. For that we are going back to Neal and Peter. Neal is seeing the "whole" location of the landscape, Peter not. Thus Peter can only guess that there is more to see. But will never proof it. Hence, it is only a result of speculation that Peter changed the distance to get within range [of the problem].

The same applies to problems outside the bounds. If one is not within reach of the solution, the existence or the observation of the problem, then one cannot prove it, only guess it. The range is the mentioned "resource" and in our specific question "time". My theory is that problems outside of this bounds can only be discovered by chance (e.g. speculation), can only be solved in a certain time value if one is within reach. In other words, there is a phase of indefinable time to "approach" the problem, but if you are within reach, then the time can be determined and thus solved by algorithms.

Conclusion:

There is a period of time when the information is inaccessible to the learner (Until Peter realizes that he has to move or Neal points it out to him.). After that, however, everything will be a matter of polynomial time and the problem will be solved.

Time irreducible (mathematically):

Upper bound: To show an upper bound T(n) on the time complexity of a problem, one needs to show only that there is a particular algorithm with running time at most T(n)

Lower bound: To show a lower bound of T(n) for a problem requires showing that no algorithm can have time complexity lower than T(n).