this is for holding javascript data
Vadim Kosoy added Fix_a_growth_space_Gamma__.tex
about 8 years ago
Commit id: 686745cf886b4ac22809035d419c6eaa1db2e992
deletions | additions
diff --git a/Fix_a_growth_space_Gamma__.tex b/Fix_a_growth_space_Gamma__.tex
new file mode 100644
index 0000000..1bb2436
--- /dev/null
+++ b/Fix_a_growth_space_Gamma__.tex
...
Fix a growth space $\Gamma$ of type $(2,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\footnote{This example cannot be formalized in the framework as presented here since the set of prime numbers is in $\textsc{P}$. We can probably tackle it by introducing restrictions on spatial resources, but this out of the current scope.} 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: \Words \xrightarrow{\Gamma} \Rats$, we can consider the estimation error $\E_{(x,y) \sim \mu^k \times U^{\R_Q(K)}}[(Q^{kj}(x,y) - f(x))^2]$. It makes little sense to require this error to be minimal for every $(k,j) \in \Nats^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.
\begin{definition}
TBD
\end{definition}
