OctoInformBeta

OpenAI preprint, September 2026 · §4. A tree of maps and separating functionals

§4.1 (setting): ordered weighted trees and nonlinear root evaluation: Positive child weights bound the sensitivity of root evaluation to terminal data

Weighted trees evaluate nonlinear maps at the root.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

Terminal values in a convex set can be propagated towards a tree’s root by averaging over children and applying nonexpansive maps. The order of these operations matters when the maps are nonlinear. Path weights measure the contribution of each terminal value to changes in the root output.

Let XX be a real normed space and let K⊆XK\subseteq X. All norms below are the norm of XX.

The Claim

Definition 1. An ordered rooted tree TT is a sequence of nonempty finite ordered levels VkV_k, indexed by k≥0k\geq 0, together with order-preserving surjections pk:Vk+1→Vkp_k:V_{k+1}\to V_k, called parent maps.✦ For positive integers mkm_k, the levels have the form (1), and the root rr is the unique node of V0V_0. Vk={0,…,mk−1},mk≥1,m0=1.V_k=\{0,\ldots,m_k-1\},\qquad m_k\geq 1,\qquad m_0=1.(1) For i≤ji\leq j, the ancestor map aij:Vj→Via_i^j:V_j\to V_i follows the parent maps down to level ii.✦ The descendants Dij(v)D_i^j(v) of v∈Viv\in V_i at level jj are the nodes at level jj whose ancestor at level ii is vv, as in (2). aii=id⁡Vi,aij+1=aij∘pj,Dij(v)={u∈Vj:aij(u)=v}.a_i^i=\operatorname{id}_{V_i},\qquad a_i^{j+1}=a_i^j\circ p_j,\qquad D_i^j(v)=\{u\in V_j:a_i^j(u)=v\}.(2)

A weighted rooted tree WW on TT is an assignment of a positive real weight wk(c)w_k(c) to each child c∈Vk+1c\in V_{k+1}, normalized separately over the children of each parent by (3). wk(c)>0,∑c∈Vk+1pk(c)=vwk(c)=1(v∈Vk).w_k(c)>0,\qquad \sum_{\substack{c\in V_{k+1}\\p_k(c)=v}}w_k(c)=1 \quad(v\in V_k).(3)✦ The root path weight πk(v)\pi_k(v) of v∈Vkv\in V_k is the product of the child weights along its path from the root, defined by (4). π0(r)=1,πk+1(c)=πk(pk(c))wk(c).\pi_0(r)=1,\qquad \pi_{k+1}(c)=\pi_k\bigl(p_k(c)\bigr)w_k(c).(4)✦

A nonexpansive tree evaluation EE on WW and a convex subset KK of XX is a family of selfmaps Fk,v:K→KF_{k,v}:K\to K, one for each v∈Vkv\in V_k, satisfying the nonexpansiveness condition (5). ∥Fk,v(x)−Fk,v(y)∥≤∥x−y∥(x,y∈K).\|F_{k,v}(x)-F_{k,v}(y)\|\leq\|x-y\| \qquad(x,y\in K).(5) For terminal values H:Vk+1→KH:V_{k+1}\to K, the weighted child average AkH:Vk→KA_kH:V_k\to K is the map given by (6). (AkH)(v)=∑c∈Vk+1pk(c)=vwk(c)H(c).(A_kH)(v)= \sum_{\substack{c\in V_{k+1}\\p_k(c)=v}}w_k(c)H(c).(6)✦ The root evaluation Ek(H)∈KE_k(H)\in K of terminal values H:Vk→KH:V_k\to K is the point specified recursively by (7), with node maps applied only at levels strictly less than the terminal level. E0(H)=H(r),Ek+1(H)=Ek(v↦Fk,v((AkH)(v))).E_0(H)=H(r),\qquad E_{k+1}(H)=E_k\bigl(v\mapsto F_{k,v}((A_kH)(v))\bigr).(7)✦

Theorem 1. Let WW be a weighted rooted tree on an ordered rooted tree TT. Its path weights satisfy (8) for every k≥0k\geq 0 and (9) whenever i≤ji\leq j and v∈Viv\in V_i. ∑v∈Vkπk(v)=1.\sum_{v\in V_k}\pi_k(v)=1.(8)✦ ∑u∈Dij(v)πj(u)=πi(v).\sum_{u\in D_i^j(v)}\pi_j(u)=\pi_i(v).(9)✦ Let EE be a nonexpansive tree evaluation on WW and a convex set K⊆XK\subseteq X. For terminal values H,H′:Vk→KH,H':V_k\to K, its sensitivity is bounded by (10). ∥Ek(H)−Ek(H′)∥≤∑v∈Vkπk(v)∥H(v)−H′(v)∥.\|E_k(H)-E_k(H')\| \leq\sum_{v\in V_k}\pi_k(v)\|H(v)-H'(v)\|.(10)✦

What Is Checked

The statements concern ordered trees with nonempty finite levels and surjective order-preserving parent maps, positive child weights normalized at each parent, and nonexpansive selfmaps of a convex subset of a real normed space. Weighted child averages and root evaluations of terminal values in KK also belong to KK.