OctoInformBeta

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

Proposition 4.1 [Tree data]: Normalized minimal data yield ordered child averages, ancestor bounds, and dyadic budgets totaling at most 1/2561/256

An adaptive tree retains fixed separating functionals.

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

An adaptive choice of nonexpansive maps joins two requirements: averages of their values return near a common anchor, and each new value is separated from the predictions determined by earlier choices.

Let XX be a real Banach space. Minimal invariant data consist of a nonempty, norm-closed, bounded, convex, norm-separable, weakly compact set K⊂XK\subset X and a fixed-point-free nonexpansive map T:K→KT:K\to K. An invariant subset C⊂KC\subset K satisfies T(C)⊂CT(C)\subset C✦; minimality means that every nonempty norm-closed convex invariant subset of KK equals KK.✦ Normalized minimal data additionally specify diam⁡K=1\operatorname{diam}K=1, a norm-dense sequence (zi)i≥0(z_i)_{i\ge0} in KK, metrizability of KK with its weak topology, and weak compactness of BYB_Y, where Y=span⁡(K−K)¯,BY={u∈Y:∥u∥≤1}⊂X.Y=\overline{\operatorname{span}(K-K)},\qquad B_Y=\{u\in Y:\|u\|\le1\}\subset X.(1)✦ The closure and norm in (1) are those of XX. Write KwK_w for the separate weakly topologized copy of KK and ι:K→Kw\iota:K\to K_w for the canonical bijection; the underlying norm point of ι(u)\iota(u) is uu.

For a∈Ka\in K and 0≤t≤10\le t\le1, the anchored averaging map St,a:K→KS_{t,a}:K\to K sends uu to ta+(1−t)T(u)ta+(1-t)T(u). For an anchor a∈Ka\in K and 0<t≤10<t\le1, the weighted resolvent Rt(a)R_t(a) is the unique fixed point in KK of the anchored averaging map St,aS_{t,a}.✦ Write RnR_n for R1/nR_{1/n} when n≥1n\ge1.✦ The generated family 𝒢\mathcal G is the least family of selfmaps of KK containing the identity and these discrete resolvents and closed under composition and convex mixing: the mixture of f,gf,g with nonnegative coefficients a,ba,b summing to one is the map u↦af(u)+bg(u)u\mapsto af(u)+bg(u).✦ For a point x∈Kx\in K, the tail families of 𝒢\mathcal G and the terminal sequence are ℋm={Rn∘g:n≥1,n≥m,g∈𝒢},bj=Rj+1(x)(j≥0).\mathcal H_m=\{R_n\circ g:n\ge1,\ n\ge m,\ g\in\mathcal G\},\qquad b_j=R_{j+1}(x)\quad(j\ge0).(2) An anchor for the families in (2) is a point x∈Kx\in K whose tail-limit set DxD_x is nonempty, weakly compact, contained in KK, and satisfies Dx=ι−1(⋂n≥0{ι(h(x)):h∈ℋn+1}¯Kw),x∈conv¯Dx.D_x=\iota^{-1}\!\left(\bigcap_{n\ge0} \overline{\{\iota(h(x)):h\in\mathcal H_{n+1}\}}^{\,K_w}\right), \qquad x\in\overline{\operatorname{conv}}D_x.(3)✦ The convex closure in (3) is a norm closure.

Frontiers and Predictions

A finite evaluated frontier F=(P,(Gp)p∈P,Φ)F=(P,(G_p)_{p\in P},\Phi) consists of a nonempty finite ordered set PP, nonexpansive maps Gp:K→KG_p:K\to K, and an evaluation Φ:KP→K\Phi:K^P\to K satisfying ∥Φ(H)−Φ(H′)∥≤maxp∈P∥Hp−Hp′∥.\|\Phi(H)-\Phi(H')\|\le\max_{p\in P}\|H_p-H'_p\|.(4)✦ The initial frontier has one node, its map is the identity, and its evaluation returns the sole input.✦ A weighted frontier extension gives each parent a nonempty ordered list of children, positive child weights summing to one, and nonexpansive child maps.✦ Children are concatenated in parent order. Write π(c)\pi(c) for the parent of a child cc and αc\alpha_c for its weight; the child average and collapse send child inputs HH to A(H)p=∑π(c)=pαcHc,C(H)p=Gp(A(H)p),Φnext(H)=Φ(C(H)).A(H)_p=\sum_{\pi(c)=p}\alpha_cH_c,\qquad C(H)_p=G_p(A(H)_p),\qquad \Phi_{\mathrm{next}}(H)=\Phi(C(H)).(5) A coherent frontier tower (Fk)k≥0(F_k)_{k\ge0} is a sequence of frontiers that starts at the initial frontier and takes each next frontier from such an extension as in (5).

An ordered rooted tree 𝒯\mathcal T has nonempty finite ordered levels LkL_k, a single root r∈L0r\in L_0, and increasing surjective parent maps π:Lk+1→Lk\pi:L_{k+1}\to L_k.✦ A weighted tree is an ordered rooted tree 𝒯\mathcal T equipped with positive weights αv\alpha_v with ∑π(v)=pαv=1\sum_{\pi(v)=p}\alpha_v=1.✦ A tree of maps assigns a nonexpansive selfmap GvG_v of KK to every node.✦ The cutoff evaluation ℰk:KLk→K\mathcal E_k:K^{L_k}\to K of a tree of maps on 𝒯\mathcal T is the iteration of (5), with ℰ0(H)=Hr\mathcal E_0(H)=H_r.✦ For v∈Lkv\in L_k and points b,y∈Kb,y\in K, the ideal switched cutoff and ancestor displacement are Ik,v(x,b)u={Gu(x),u<v,b,u≥v,Δv(y)=∑p≺v∥Gp(y)−y∥,I_{k,v}(x,b)_u= \begin{cases}G_u(x),&u<v,\\ b,&u\ge v,\end{cases} \qquad \Delta_v(y)=\sum_{p\prec v}\|G_p(y)-y\|,(6) where p≺vp\prec v means that pp is a proper ancestor of vv.

For a finite family (yi)i∈I(y_i)_{i\in I} in KK with assigned parents ρ:I→P\rho:I\to P, admissible coefficients and residual parent inputs are Θρ={θ∈[0,∞)I:sp(θ):=∑ρ(i)=pθi≤1for every p},rp(b,θ)=b+∑ρ(i)=pθi(yi−b).\Theta_\rho=\left\{\theta\in[0,\infty)^I: s_p(\theta):=\sum_{\rho(i)=p}\theta_i\le1\ \text{for every }p\right\}, \qquad r_p(b,\theta)=b+\sum_{\rho(i)=p}\theta_i(y_i-b).(7) The parent-restricted coefficient is θi\theta_i when ρ(i)=p\rho(i)=p and zero otherwise✦. For a sequence b•b_\bullet in KK and an ultrafilter UU on the naturals, choose weak limits of the evaluated predictions and define the detector at depth dd by QF,θ(b)=Φ((Gp(rp(b,θ)))p∈P),qF,θ=weak lim⁡j→UQF,θ(bj),Ed(F,ρ,y,b•,U)={zi:i<d}∪{qF,θ:θ∈Θρ}.Q_{F,\theta}(b)=\Phi\bigl((G_p(r_p(b,\theta)))_{p\in P}\bigr),\qquad q_{F,\theta}=\mathop{\mathrm{weak\,lim}}_{j\to U}Q_{F,\theta}(b_j),\qquad E_d(F,\rho,y,b_\bullet,U)=\{z_i:i<d\}\cup \{q_{F,\theta}:\theta\in\Theta_\rho\}.(8) For a tree frontier, Φ=ℰk\Phi=\mathcal E_k and P=LkP=L_k give the tree predictions by the same formula.

Candidate Histories and Budgets

A candidate context consists of a generated frontier, an anchor, a terminal sequence, an ultrafilter, a depth dd, a base ordinal BB, and a list of generated ancestor maps for each parent.✦ In an anchored context the anchor is the specified point xx.✦ A candidate record a=(p,g,f)a=(p,g,f) consists of its parent pp, a generated map gg, and a continuous linear functional f∈X*f\in X^*.✦ A history h=(a0,…,aN−1)h=(a_0,\ldots,a_{N-1}) is a finite list of candidate records, with parent indices ρ(i)=pi\rho(i)=p_i and anchor outputs yi=gi(x)y_i=g_i(x). The detector E(h)E(h) of a candidate history hh is the set in (8) formed from the history’s parent indices and anchor outputs and the context’s terminal sequence, ultrafilter, and depth.✦

The next candidate has ordinal B+NB+N, counting discarded candidates✦, and budget ε(B+N)\varepsilon(B+N), where ε(n)=2−(n+9),δrun=2−dε(B).\varepsilon(n)=2^{-(n+9)},\qquad \delta_{\mathrm{run}}=2^{-d}\varepsilon(B).(9) Let 𝒜p\mathcal A_p be the context’s ancestor list for pp with the frontier map GpG_p appended.✦ A record a=(p,g,f)a=(p,g,f) is legal after hh precisely when ∥f∥≤1,f(g(x)−z)≥1−ε(B+N)(z∈E(h)),∑G∈𝒜p∥G(g(x))−g(x)∥≤ε(B+N).\|f\|\le1,\qquad f(g(x)-z)\ge1-\varepsilon(B+N)\quad(z\in E(h)),\qquad \sum_{G\in\mathcal A_p}\|G(g(x))-g(x)\|\le\varepsilon(B+N).(10)✦ A valid chronological history hh is a finite list of candidate records in which each record satisfies (10) after its preceding records. A legal append transition adds one such record with its prescribed parent and map.✦ The selected tail threshold is a function of the parent and the current history.

For a map a:M→Ka:M\to K, families ℱm⊂M\mathcal F_m\subset M, a threshold function m(i,s)m(i,s) depending on the selection index ii and state ss, a prescribed state transition, and an initial state s0s_0, an adaptive parent return with tolerance δ>0\delta>0 is a nonempty finite sequence of selections uiu_i, successive states sis_i beginning at the prescribed initial state, and coefficients βi≥0\beta_i\ge0 satisfying ui∈ℱm(i,si),si→si+1under ui,∑iβi=1,∥∑iβia(ui)−x∥<δ.u_i\in\mathcal F_{m(i,s_i)},\qquad s_i\longrightarrow s_{i+1}\ \text{under }u_i,\qquad \sum_i\beta_i=1,\qquad \left\|\sum_i\beta_i a(u_i)-x\right\|<\delta.(11)✦ The retained subsequence of an adaptive parent return is the subsequence consisting exactly of its positive coefficients, in their original order, and has the sum and average of the parent return. Contextual parent returns use a(g)=g(x)a(g)=g(x), the families ℋm\mathcal H_m, and legal append transitions.✦ At tolerance (9), parents are processed in their order, beginning with the empty history and starting each later parent with the preceding parent’s completed history. The retained child extension of a context takes the nonexpansive retained maps from each selected parent return as its child maps and their strictly positive coefficients as its weights, preserving the original order of parents and retained children. The selected stage extension of a candidate context is its retained child extension at the selection return tolerance in (9).

A complete candidate list for a level records every candidate in parent order; its retained nodes form an increasing subsequence respecting the parent map.✦ The earlier candidates of a retained node vv are all entries strictly before its position in this full list.✦ Final coefficients give a retained entry its child weight and a discarded entry zero.✦ The actual admissible parameter θv\theta^v of a retained node vv is the coefficient family in (7) obtained by restricting the final coefficients to the candidates earlier than vv. At level kk, let BkB_k be the base ordinal and FkF_k the parent frontier; candidate positions start at zero. A retained candidate vv carries the functional of its original record ava_v and the global ordinal ℓ(v)=Bk+position⁡(v),ev=ε(ℓ(v)),yv=Gv(x),qv=qFk,θv.\ell(v)=B_k+\operatorname{position}(v),\qquad e_v=\varepsilon(\ell(v)),\qquad y_v=G_v(x),\qquad q_v=q_{F_k,\theta^v}.(12) The prefix hvh_v consists of the records before vv, including those later discarded.✦

For nonroot budgets ee on an ordered rooted tree, the cumulative minimum mm is the sequence starting at m0=1m_0=1 and satisfying mk+1=min⁡{mk,min⁡v∈Lk+1ev}m_{k+1}=\min\{m_k,\min_{v\in L_{k+1}}e_v\}.✦

Definition 1. The retained dyadic tolerance τ\tau of a tree with budgets ee is the sequence τk=2−(k+1)mk(k≥0).\tau_k=2^{-(k+1)}m_k\qquad(k\ge0).(13)✦

A switching tree datum for normalized minimal data is a weighted ordered tree with generated nonexpansive maps, root map Gr=idG_r=\operatorname{id}, an anchor x∈Kx\in K, an injective ordinal assignment ℓ\ell, functionals fv∈X*f_v\in X^* of norm at most one, an ultrafilter UU refining the tail filter on the naturals, and points qv∈Kq_v\in K satisfying ∥∑π(v)=pαvyv−x∥≤τk(p∈Lk),Δv(yv)≤ev(v∈Lk+1),ℰk+1(Ik+1,v(x,bj))⇀qv(j→U),fv(yv−z)≥1−ev(z∈{qv}∪{zi:i<k+1}).\begin{aligned} \left\|\sum_{\pi(v)=p}\alpha_vy_v-x\right\|&\le\tau_k &&(p\in L_k),\\ \Delta_v(y_v)&\le e_v &&(v\in L_{k+1}),\\ \mathcal E_{k+1}\bigl(I_{k+1,v}(x,b_j)\bigr)&\rightharpoonup q_v &&(j\to U),\\ f_v(y_v-z)&\ge1-e_v &&\bigl(z\in\{q_v\}\cup\{z_i:i<k+1\}\bigr). \end{aligned}(14)✦ In (14), yvy_v and eve_v have the meanings in (12), the sequence bjb_j is (2), and τk\tau_k is (13). Denote the collection of these data by 𝔖(D)\mathfrak S(D), where DD denotes the normalized minimal data.

The Claim

Theorem 1. Let DD be normalized minimal data. Switching tree data exist: 𝔖(D)≠⌀.\mathfrak S(D)\ne\varnothing.(15)✦ For a specified anchor AA with anchor point xAx_A and an ultrafilter UU refining the tail filter, the successive anchored candidate contexts determine a frontier tower and a selected datum 𝒮(D,A,U)\mathscr S(D,A,U) with that anchor and ultrafilter: 𝒮(D,A,U)∈𝔖(D),x𝒮(D,A,U)=xA,U𝒮(D,A,U)=U.\mathscr S(D,A,U)\in\mathfrak S(D),\qquad x_{\mathscr S(D,A,U)}=x_A,\qquad U_{\mathscr S(D,A,U)}=U.(16)✦ The tower’s frontiers supply its levels and maps, and its extensions supply its parent maps and weights. Its retained prefixes are legal in their stage contexts: av is legal after hv.a_v\text{ is legal after }h_v.(17)✦ For every nonroot retained node, its original functional separates the whole prefix detector: fv(yv−z)≥1−ev(z∈E(hv)).f_v(y_v-z)\ge1-e_v\qquad(z\in E(h_v)).(18)✦ The actual retained-weight prediction belongs to that detector: qv∈E(hv).q_v\in E(h_v).(19)✦ The prefix detector and candidate functional are fixed before the remaining and future weights are chosen. Every injective ordinal assignment on a tree has ∑v≠rev≤1256.\sum_{v\ne r}e_v\le\frac1{256}.(20)✦ For any nonroot budgets bounded above by one and every k≥0k\ge0, the cumulative minimum at level k+1k+1 is attained: mk+1=evfor some v∈Li with 1≤i≤k+1.m_{k+1}=e_v\quad\text{for some }v\in L_i \text{ with }1\le i\le k+1.(21)✦

More generally, fix any finite evaluated frontier FF, a finite parent assignment ρ:I→P\rho:I\to P, points yi∈Ky_i\in K, a sequence b•b_\bullet in KK, an ultrafilter UU, a depth dd, a finite family (Ha)a∈J(H_a)_{a\in J} of generated maps, and e>0e>0. With E=Ed(F,ρ,y,b•,U)E=E_d(F,\rho,y,b_\bullet,U), there is a prepared tail threshold satisfying m≥1,g∈𝒢(g∈ℋm),for every g∈ℋm and u∈K, there is f∈X* with ∥f∥≤1,f(g(u)−z)≥1−e(z∈E),∑a∈J∥Ha(g(u))−g(u)∥≤e.\begin{gathered} m\ge1,\qquad g\in\mathcal G\quad(g\in\mathcal H_m),\\ \text{for every }g\in\mathcal H_m\text{ and }u\in K, \text{ there is }f\in X^*\text{ with }\|f\|\le1,\\ f(g(u)-z)\ge1-e\quad(z\in E),\qquad \sum_{a\in J}\|H_a(g(u))-g(u)\|\le e. \end{gathered}(22)✦

In the paper, the result reads: with the anchor xx and terminal sequence fixed, there is an infinite ordered tree with generated maps GvG_v, points yvy_v, and positive child weights αv\alpha_v summing to one at each parent, every nonroot node has ev>0e_v>0, a functional fv∈X*f_v\in X^* with ∥fv∥≤1\|f_v\|\le1, and its earlier-candidate prediction set EvE_v, the budgets satisfy ∑v≠rev≤1/128\sum_{v\ne r}e_v\le1/128, the tolerances are τ0=1/2\tau_0=1/2 and τk=2−k−1min⁡{eu:u∈Li,1≤i≤k}\tau_k=2^{-k-1}\min\{e_u:u\in L_i,\ 1\le i\le k\} for k≥1k\ge1, each p∈Lkp\in L_k satisfies ∥∑π(v)=pαvyv−x∥≤τk\|\sum_{\pi(v)=p}\alpha_vy_v-x\|\le\tau_k, and every nonroot vv satisfies ∑p≺v∥Gp(yv)−yv∥≤ev\sum_{p\prec v}\|G_p(y_v)-y_v\|\le e_v and fv(yv−z)≥1−evf_v(y_v-z)\ge1-e_v for all z∈Evz\in E_v, including ziz_i with i≤depth⁡(v)i\le\operatorname{depth}(v), while budgets, functionals, and prediction sets stay fixed as the remaining and future weights are chosen.

What Is Checked

The tree existence statement (15) is over normalized minimal data; the anchored selection (16) additionally specifies an anchor and an ultrafilter on the naturals refining the tail filter, while the prepared threshold (22) allows arbitrary finite frontier prediction data and any ultrafilter on the naturals. The budget sum bound is stated for any ordered rooted tree with an injective assignment of candidate ordinals to its nonroot nodes. The attainment statement is stated for any ordered rooted tree with nonroot budgets at most one. All nonexpansiveness and displacement bounds use the ambient norm; weak convergence takes place in the weakly topologized ambient space.

The anchored averaging map St,aS_{t,a} has contraction factor 1−t1-t for 0<t≤10<t\le1✦, and every positive integer nn has 0<1/n≤10<1/n\le1. Weak compactness of KK gives a weak ultrafilter limit in KK for every KK-valued family, including the predictions in (8).✦ The contextual thresholds are at least one✦; every map in the selected tail admits a legal append transition.✦ The return tolerance in (9) is positive✦.

Suppose that KwK_w is metrizable, x∈conv¯D0x\in\overline{\operatorname{conv}}D_0 for a set D0⊂KD_0\subset K, every point of D0D_0 lies in the weak closure of a(ℱm)a(\mathcal F_m) for each m≥1m\ge1, all thresholds are positive integers, and every admissible selection admits a successor state. Then adaptive returns as in (11) exist. The construction selects such returns from any prescribed initial state.✦