User:IssaRice/Logical inductor construction

Notes from the Logical Induction paper as I walk through the construction of LIA in section 5.

Lemma 5.1.1 (Fixed Point Lemma)

"Observe that $\mathcal{V}\text{'}$ is equal to the natural inclusion of the finite-dimensional cube $[0,1{]}^{{{\mathcal{S}}^{\prime }}^{\prime }}$ in the space of all valuations $\mathcal{V}=[0,1{]}^{\mathcal{S}}$." -- I think what this is saying is that since $\mathcal{S}\text{'}\subset \mathcal{S}$, we can think of $[0,1{]}^{{{\mathcal{S}}^{\prime }}^{\prime }}$ as being sort of a subset of $[0,1{]}^{\mathcal{S}}$. Except it's not strictly speaking a subset, since the functions in $[0,1{]}^{{{\mathcal{S}}^{\prime }}^{\prime }}$ and $[0,1{]}^{\mathcal{S}}$ have different domains. How can we make it a subset? The "natural" way to do this is to set everything outside of $\mathcal{S}\text{'}$ to zero. But that's exactly what $\mathcal{V}\text{'}=\{\mathbb{V}\in [0,1{]}^{\mathcal{S}}:\mathbb{V}(\varphi )=0\text{ whenever }\varphi \notin {{\mathcal{S}}^{\prime }}^{\prime }\}$ is. One thing I'm still not sure about is the "finite-dimensional" part; doesn't having $[0,1]$ make the cube infinite-dimensional?

Definition of fix: I found it helpful to look at the graph of $f(x)=max(0,min(1,x))$; this looks like the identity function in the interval $[0,1]$, but then becomes constant once it hits either of the endpoints. If you've already thought about the definition of continuous threshold indicator (definition 4.3.2), then you will recognize that $f(x)={\mathrm{I}\mathrm{n}\mathrm{d}}_1(x>0)$.

"the compact, convex space $\mathcal{V}\text{'}$" -- this intuitively makes sense, since $\mathcal{V}\text{'}$ basically "looks like" a cube. But I'm not sure how to verify this.

For the fixed point reasoning: we don't actually have a fixed point of $f$; instead, it's a fixed point of $g$, where $g(x)=f(x+\delta )$ and $\delta =T_n({\mathbb{P}}_{\le n-1},{\mathbb{V}}^{\text{fix}})[\varphi ]$. If $\delta >0$, then the graph of $g$ is just the graph of $f$ but shifted to the left. You will see that this intersects the graph of the identity function at $x=1$; this is the fixed point. On the other hand, if $\delta <0$, then we shift the graph of $f$ to the right, and now the fixed point is at $x=0$.

The key property of ${\mathbb{V}}^{\text{fix}}$ that we use in the proof:

• If $T_n$ buys a share of $\varphi$ on day $n$, then the price of $\varphi$ on day $n$ is 1 (the maximum possible).
• If $T_n$ sells a share of $\varphi$ on day $n$, then the price of $\varphi$ on day $n$ is 0 (the minimum possible).

One question to ask is, couldn't we just avoid using Brouwer's fixed point theorem by just setting the prices to obey the above property? There are two problems with this. One is that the definition of the $n$th day prices would depend on $T_n$'s behavior, which depends on the $n$th day prices! So the definition would be circular. The other problem is that we can't guarantee that the map would be continuous if we just magically set it to obey some property.

Something else I got confused about: I was thinking that the above key property only talks about day $n$. Couldn't the trader make a lot of money on previous days, and then just make no money on day $n$, so that it would still be making lots of money? The answer is that we are only dealing with a trading strategy in this lemma, not a full trader. Later, in lemma 5.1.3, we recursively use this idea to deal with a full trader.

The following is used in the Fixed Point Lemma (5.1.1):

Writing the $n$-strategy as

$T_n=\sum _{j=1}^k{\xi }_j{\varphi }_j-\sum _{j=1}^k{\xi }_j\underset{j}{\overset{*n}{\varphi }}$

we have

$\mathbb{V}(T_n({\mathbb{P}}_{\le n-1},\mathbb{V}))=\sum _{j=1}^k{\xi }_j({\mathbb{P}}_{\le n-1},\mathbb{V})\cdot \mathbb{V}({\varphi }_j)-\sum _{j=1}^k{\xi }_j({\mathbb{P}}_{\le n-1},\mathbb{V})\cdot \underset{j}{\overset{*n}{\varphi }}({\mathbb{P}}_{\le n-1},\mathbb{V})$

But $\underset{j}{\overset{*n}{\varphi }}({\mathbb{P}}_{\le n-1},\mathbb{V})=\mathbb{V}({\varphi }_j)$ so the two sums cancel to obtain $0$.

See also

• https://machinelearning.subwiki.org/wiki/User:IssaRice/Logical_induction_notation