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 be a real Banach space. Minimal invariant data consist of a nonempty, norm-closed, bounded, convex, norm-separable, weakly compact set and a fixed-point-free nonexpansive map . An invariant subset satisfies ✦; minimality means that every nonempty norm-closed convex invariant subset of equals .✦ Normalized minimal data additionally specify , a norm-dense sequence in , metrizability of with its weak topology, and weak compactness of , where (1)✦ The closure and norm in (1) are those of . Write for the separate weakly topologized copy of and for the canonical bijection; the underlying norm point of is .
For and , the anchored averaging map sends to . For an anchor and , the weighted resolvent is the unique fixed point in of the anchored averaging map .✦ Write for when .✦ The generated family is the least family of selfmaps of containing the identity and these discrete resolvents and closed under composition and convex mixing: the mixture of with nonnegative coefficients summing to one is the map .✦ For a point , the tail families of and the terminal sequence are (2) An anchor for the families in (2) is a point whose tail-limit set is nonempty, weakly compact, contained in , and satisfies (3)✦ The convex closure in (3) is a norm closure.
Frontiers and Predictions
A finite evaluated frontier consists of a nonempty finite ordered set , nonexpansive maps , and an evaluation satisfying (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 for the parent of a child and for its weight; the child average and collapse send child inputs to (5) A coherent frontier tower 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 has nonempty finite ordered levels , a single root , and increasing surjective parent maps .✦ A weighted tree is an ordered rooted tree equipped with positive weights with .✦ A tree of maps assigns a nonexpansive selfmap of to every node.✦ The cutoff evaluation of a tree of maps on is the iteration of (5), with .✦ For and points , the ideal switched cutoff and ancestor displacement are (6) where means that is a proper ancestor of .
For a finite family in with assigned parents , admissible coefficients and residual parent inputs are (7) The parent-restricted coefficient is when and zero otherwise✦. For a sequence in and an ultrafilter on the naturals, choose weak limits of the evaluated predictions and define the detector at depth by (8) For a tree frontier, and 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 , a base ordinal , and a list of generated ancestor maps for each parent.✦ In an anchored context the anchor is the specified point .✦ A candidate record consists of its parent , a generated map , and a continuous linear functional .✦ A history is a finite list of candidate records, with parent indices and anchor outputs . The detector of a candidate history 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 , counting discarded candidates✦, and budget , where (9) Let be the context’s ancestor list for with the frontier map appended.✦ A record is legal after precisely when (10)✦ A valid chronological history 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 , families , a threshold function depending on the selection index and state , a prescribed state transition, and an initial state , an adaptive parent return with tolerance is a nonempty finite sequence of selections , successive states beginning at the prescribed initial state, and coefficients satisfying (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 , the families , 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 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 of a retained node is the coefficient family in (7) obtained by restricting the final coefficients to the candidates earlier than . At level , let be the base ordinal and the parent frontier; candidate positions start at zero. A retained candidate carries the functional of its original record and the global ordinal (12) The prefix consists of the records before , including those later discarded.✦
For nonroot budgets on an ordered rooted tree, the cumulative minimum is the sequence starting at and satisfying .✦
Definition 1. The retained dyadic tolerance of a tree with budgets is the sequence (13)✦
A switching tree datum for normalized minimal data is a weighted ordered tree with generated nonexpansive maps, root map , an anchor , an injective ordinal assignment , functionals of norm at most one, an ultrafilter refining the tail filter on the naturals, and points satisfying (14)✦ In (14), and have the meanings in (12), the sequence is (2), and is (13). Denote the collection of these data by , where denotes the normalized minimal data.
The Claim
Theorem 1. Let be normalized minimal data. Switching tree data exist: (15)✦ For a specified anchor with anchor point and an ultrafilter refining the tail filter, the successive anchored candidate contexts determine a frontier tower and a selected datum with that anchor and ultrafilter: (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: (17)✦ For every nonroot retained node, its original functional separates the whole prefix detector: (18)✦ The actual retained-weight prediction belongs to that detector: (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 (20)✦ For any nonroot budgets bounded above by one and every , the cumulative minimum at level is attained: (21)✦
More generally, fix any finite evaluated frontier , a finite parent assignment , points , a sequence in , an ultrafilter , a depth , a finite family of generated maps, and . With , there is a prepared tail threshold satisfying (22)✦
In the paper, the result reads: with the anchor and terminal sequence fixed, there is an infinite ordered tree with generated maps , points , and positive child weights summing to one at each parent, every nonroot node has , a functional with , and its earlier-candidate prediction set , the budgets satisfy , the tolerances are and for , each satisfies , and every nonroot satisfies and for all , including with , 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 has contraction factor for ✦, and every positive integer has . Weak compactness of gives a weak ultrafilter limit in for every -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 is metrizable, for a set , every point of lies in the weak closure of for each , 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.✦