[section] [section]

[section] [section] [section]

Fix \(\Gamma\) a pair of growth spaces of rank 2. The first parameter serves to define asymptotic behavior and can be roughly thought of as determining the size of the input. The second parameter serves to control the resources available to the predictor. To illustrate the significance of the second parameter using the informal¹ example from Section 1, the question “what is the probability 7614829 is prime?” depends on the amount of available resources. For example, we can use additional resources to test for divisibility by additional smaller primes (or in some more clever way) until eventually we are able to test primality and assign a probability in \(\{0,1\}\).

Given a distributional estimation problem \((\mu,f)\) and \(Q: {{\{ 0, 1 \}^*}}\xrightarrow{\Gamma} {\mathbb{Q}}\), we can consider the estimation error \(\operatorname{E}_{(x,y) \sim \mu^k \times U^{\operatorname{r}_Q(k,j)}}[(Q^{kj}(x,y) - f(x))^2]\). It makes little sense to require this error to be minimal for every \((k,j) \in {\mathbb{N}}^2\), since we can always hard-code a finite number of answers into \(Q\) without violating the resource restrictions. Instead we require minimization up to an asymptotically small error. Since it makes sense to consider different kind of asymptotic requirements, we introduce an abstraction that corresponds to this choice.

Given \(n \in {\mathbb{N}}\), an error space of rank \(n\) is a set \(\mathcal{E}\) of bounded functions \(\varepsilon: {\mathbb{N}}^n \rightarrow {\mathbb{R}}^{\geq 0}\) s.t.

1. If \(\varepsilon_1, \varepsilon_2 \in \mathcal{E}\) then \(\varepsilon_1 + \varepsilon_2 \in \mathcal{E}\).

2. If \(\varepsilon_1 \in \mathcal{E}\), \(\varepsilon_2: {\mathbb{N}}^n \rightarrow {\mathbb{R}}^{\geq 0}\) and \(\forall K \in {\mathbb{N}}^n: \varepsilon_2(K) \leq \varepsilon_1(K)\) then \(\varepsilon_2 \in \mathcal{E}\).

3. There is a polynomial \(h: {\mathbb{N}}^n \rightarrow {\mathbb{N}}\) s.t. \(2^{-h} \in \mathcal{E}\).