The Minimax Rate of Denoising Flows on Trees

Two classical problems anchor Gaussian denoising under geometric constraints. Isotonic regression, the estimation of a monotone sequence, obeys the cube-root phase diagram of shape-constrained estimation (Zhang, 2002; Chatterjee et al., 2015). Mean estimation over a scaled simplex, the nonnegative part of an $\ell_{1}$ ball, obeys the $\sqrt{\log}$ diagram of sparse estimation (Donoho and Johnstone, 1994; Birgé and Massart, 2001). The two diagrams, each carrying decades of theory, are unlike in kind: the monotone problem pays a power of its depth, the sparse problem a logarithm of its width. Between the sequence and the simplex lies every geometry in which depth and branching interact, and there the picture has remained incomplete.

One model generalizes both. A tree flow (Chatterjee and Lafferty, 2018) assigns to the vertices of a rooted tree nonnegative values such that each vertex passes to its children at most what it receives: a mass enters at the root, travels downward, and may leak at any vertex. A path, depth without branching, is bounded isotonic regression; a star, branching without depth, is mean estimation over the scaled simplex. The same inequalities arise wherever hierarchical totals are measured with noise. In the consistency post-processing of differentially private counts they hold with equality (Hay et al., 2010; Abowd et al., 2022); in profiling a call tree the leak carries real mass, the self time of a procedure (Graham et al., 1982). Chatterjee and Lafferty studied the least squares estimator, the projection onto the flow cone and the natural tuning-free program for the model, and discovered that it behaves unlike its isotonic counterpart: its rate of convergence is not monotone in the depth of the tree, and it can miss the minimax rate by a power of $n\text{.}$ Where the projection fell short, the minimax rate was attained only by least squares over an exponentially large net, and their closing sentence poses the challenge of “closing the gap between the LSE and the minimax lower bound” with an efficient estimator. A decade later the challenge stood, and with it three gaps: the minimax risk was uncharacterized beyond two regimes of trees, the worst case of least squares at a fixed budget was unquantified, and no efficient estimator was known to attain the minimax rate where the projection did not.

This paper closes all three. We ask: for every finite rooted tree and every budget and noise level, what is the minimax risk of denoising a tree flow, and is it attained by a computationally efficient estimator? One combinatorial functional of the tree organizes the answers, stated in Section 1.1: a rate formula; an exact and efficient estimator; adaptation to the budget and, in an explicit regime, to the noise level; and the worst-case price of least squares. In the local entropy program for convex constraints (Neykov, 2023), the flow polytopes thereby form a nonsymmetric, combinatorially explicit family.

This section records the interfaces used by the rest of the paper: the two normal forms of the flow polytope, the Euclidean realization of the tree metric, and the working properties of the ancestor profile, including the surrogate index through which the profile is computed. Proofs are collected in Section S.1.

The main theorem of the paper is the rate formula.

The formula is insensitive to the choice of $(A_{0},C_{\star})$ in Equation 1.5: any pair for which Theorem 1 holds yields a formula $\asymp R^{*}_{T}\text{.}$ The entropy reading is the following.

Section 3.1 converts the profile into a coded cover of the flow polytope, yielding the upper bounds and the certificates that the estimators of Section 4 later consume; Section 3.2 converts the same profile into legal packings and the matching lower bounds; and Section 3.3 joins the two at the crossing index, proves both statements above, and derives the benchmark corollaries. The assembly is given here; the proofs of the two halves are in Sections S.2 and S.3.

This section proves the three estimation theorems; the first is stated here, the adaptation pair in Section 4.3.

The estimator is an exponentially weighted aggregate over a class of integer states, evaluated exactly in the sense fixed by Remark 4.1. Section 4.1 constructs it and proves the risk bound, Section 4.2 gives the algorithm, and Section 4.3 removes first the budget and then the noise level.

The last theorem prices the default estimator. The body is compact and convex, so the data have a unique Euclidean projection onto it, the constrained least squares estimator

the solution of a tuning-free convex program; write

for its worst-case risk.

We prove the broom lower bound first: the broom isolates the mechanism, extreme-value forcing through a terminal star, and every numerical threshold in the forcing step is explicit (Section S.4). The universal upper bound shows the resulting separation extremal over all trees and parameters; its proof, sketched at the end of the section, runs the coded cover of Section 3.1 through a localized-width analysis.

The broom couples the two classical geometries in series, a path feeding a star. For integers $L\geq 1$ and $m\geq 1\text{,}$ the broom $T_{L}$ consists of a handle, the path $o=v_{0},v_{1},\dots,v_{L}$ of $L$ edges, and of $m$ terminal leaves $w_{1},\dots,w_{m}\text{,}$ the children of $v_{L}\text{,}$ so that $n=L+1+m$ and $h_{T_{L}}=H_{T_{L}}=L+1\text{;}$ the budget and the noise level are fixed at $V:=L^{1/4}$ and $\sigma:=1\text{.}$

Proof of Theorem 5, lower bound.

Fix $n\geq n_{0}\text{,}$ with $n_{0}$ a universal constant large enough for the estimates below. The maximality of $L$ gives $e^{20L^{5/2}}\leq\sqrt{n}<e^{20(L+1)^{5/2}}\text{;}$ for $n\geq n_{0}$ it forces $L\geq 4$ and $L+1\leq\sqrt{n}\text{,}$ whence $m=n-L-1\geq n-\sqrt{n}\geq\sqrt{n}\geq e^{20L^{5/2}}\text{.}$ The true signal is $\mu=Vp_{o}\text{:}$ all mass rests at the root, and every nonroot coordinate vanishes. We show that one extreme leaf noise forces the projection to carry more than half the budget through the entire handle, at squared loss exceeding $L^{3/2}/4\text{,}$ on an event of probability at least $3/8\text{;}$ and that the minimax risk of the broom is of order $\sqrt{L}\text{.}$

Coordinates. Write $h_{j}$ for the coordinate of a body point at $v_{j}$ and $\ell_{i}$ for its coordinate at $w_{i}\text{.}$ By Lemma 2.1, nonnegativity of the leaks identifies the body, in these coordinates, with the chain

The root coordinate equals $V$ on the whole body, and at the true signal the nonroot data are pure noise: $Y_{v_{j}}=Z_{v_{j}}$ and $Y_{w_{i}}=Z_{w_{i}}\text{.}$ Expanding $\|Y-\theta\|_{2}^{2}$ and discarding the terms that do not depend on $\theta$ shows that the nonroot coordinates of the projection maximize over Equation 5.1 the objective

The forcing inequality. Aggregate the noise into three statistics, local to this proof:

Routing the full budget to a leaf attaining $M\text{,}$ that is, taking $h_{j}=V$ for every $j\text{,}$ $\ell_{i^{\star}}=V$ at one index $i^{\star}$ with $Z_{w_{i^{\star}}}=M\text{,}$ and $\ell_{i}=0$ elsewhere, is feasible in Equation 5.1. Its objective value is $2VW+2VM-(L+1)V^{2}\text{.}$ On the other side, suppose $M>0\text{;}$ then every feasible point with $h_{L}\leq V/2$ obeys

since $2Z_{v_{j}}h_{j}-h_{j}^{2}\leq[Z_{v_{j}}]_{+}^{2}$ for every $h_{j}\geq 0\text{,}$ while discarding $-\sum_{i}\ell_{i}^{2}$ and replacing each $Z_{w_{i}}$ by $M$ bounds the leaf part by $2M\sum_{i}\ell_{i}\leq 2Mh_{L}\leq MV\text{,}$ the last two steps by Equation 5.1 and by the hypothesis $h_{L}\leq V/2$ (Section S.4). The routed candidate beats the cap Equation 5.3 exactly when

When $M>0$ and Equation 5.4 hold, no maximizer of $\Psi$ can have $h_{L}\leq V/2\text{,}$ so the coordinates $(\widehat{h},\widehat{\ell})$ of $\widehat{\mu}_{\mathrm{LSE}}$ satisfy $\widehat{h}_{L}>V/2\text{;}$ the chain Equation 5.1 propagates the bound up the handle, and since the true nonroot signal is zero,

The forcing event. Let

On $E\text{,}$ with $V=L^{1/4}\text{,}$ the right side of Equation 5.4 is less than $4L^{5/4}\leq M$ for $L\geq 4\text{,}$ so the forcing inequality holds; Markov’s inequality on the handle statistics and a Gaussian tail estimate on the leaf maximum, using $m\geq e^{20L^{5/2}}\text{,}$ give $\mathbb{P}(E)\geq\tfrac{3}{8}$ (Section S.4). Combining with Equation 5.5,

The minimax rate. The ancestor-covering numbers of the broom are explicit: $N^{\uparrow}_{T}(0)=n\text{,}$ and for integers $1\leq j\leq L\text{,}$

Both directions follow by counting along the root-to-leaf path $v_{0},\dots,v_{L},w_{1}\text{;}$ the single center $v_{L+1-j}$ covers every leaf at distance exactly $j$ (Section S.4). Thus every radius $r\geq 1$ sees a covering count independent of $m\text{:}$ the terminal star enters the profile Equation 1.4 only through radii $r<1\text{,}$ where the truncation caps its term at $k\text{.}$ What survives is path geometry: Section S.4 turns Equation 5.7 into the profile bounds

The crossing then solves at $k_{0}\asymp(V^{2}(L+2)/\sigma^{2})^{1/3}\asymp\sqrt{L}\text{,}$ with the dimension clause of Equation 1.5 silent and the diameter branch of Theorem 1 inactive, so

(Section S.4).

Conclusion. The maximality of $L$ gives $\sqrt{n}<e^{20(L+1)^{5/2}}\text{,}$ so $\log n<40(L+1)^{5/2}$ and $L\geq c(\log n)^{2/5}\text{.}$ Dividing Equation 5.6 by Equation 5.9 gives a ratio at least $cL\geq c^{\prime}(\log n)^{2/5}$ at this signal, and the worst-case risk dominates this single-signal risk. ∎

The upper half is a statement about every tree and every parameter pair at once; its proof has three blocks, completed in Section S.7.

Proof sketch of Theorem 5, upper bound.

A localized projection principle. For $\mu\in\mathcal{F}_{V}(T)$ and $t>0\text{,}$ let

be the localized Gaussian width of the body at the truth. If $t\geq\sigma$ and $\sigma\,w_{\mu}(s)\leq s^{2}/4$ for every $s\geq t\text{,}$ then $\mathbb{E}_{\mu}\|\widehat{\mu}_{\mathrm{LSE}}-\mu\|_{2}^{2}\leq 33\,t^{2}\text{.}$ On the event $\|\widehat{\mu}_{\mathrm{LSE}}-\mu\|_{2}\geq s\text{,}$ projection optimality forces the supremum defining $w_{\mu}(s)$ above twice its mean; the supremum is $s$-Lipschitz in $Z\text{,}$ so Gaussian concentration bounds its probability, and integrating the tail from $t$ gives the claim (Section S.7). Localizing least squares at a fixed point of the width is Chatterjee’s argument (Chatterjee, 2014).

The width of the body through the coded cover. Fix an integer $2\leq k\leq n/C_{\star}\text{,}$ write $\overline{\delta}:=\overline{\delta}_{k}(T)$ for the surrogate profile Equation 2.1, and let $\ell_{n}:=1+\log(en)\text{.}$ Section S.7 proves the truth-localized width bound

The first term is the width of the coded cover $\mathcal{D}_{k}$ seen from the truth: recentering at a deterministic center $\nu_{\mu}\in\mathcal{D}_{k}$ (Proposition 3.1) confines every center met by the local ball to distance $t+2CV\sqrt{\overline{\delta}}\text{,}$ and the class has logarithmic cardinality $O(k)\text{,}$ so the maximum of the recentered pairings obeys a $\sqrt{k}$ bound. The second term bounds the residual $\theta-\nu_{\theta}\text{,}$ uniformly over the body, through the three components of the construction behind Proposition 3.1: the collapse and rounding residuals, bounded by a capped order-statistics sum and a union of norm concentrations over $e^{Ck}$ subspaces at $CV\sqrt{k\overline{\delta}}$ (Section S.7); and the exit quantization. Conditionally on $(\theta,Z)\text{,}$ the pairing of $Z$ with the quantization error is centered, so on the sampling event of that construction, of probability at least $\tfrac{1}{4}\text{,}$ its conditional expectation is at most four conditional standard deviations. Some realization in the event meets this bound, and the randomized rounding becomes, for each noise outcome, a deterministic choice of a nearby center in $\mathcal{D}_{k}\text{.}$

Closure of the exponent. Let $2\leq k_{0}\leq K\text{,}$ where $R^{*}_{T}\asymp\sigma^{2}k_{0}$ (Section 3.3). The crossing Equation 1.5 and the sandwich $\overline{\delta}_{k_{0}}\leq 2\delta_{k_{0}}$ give $V\sqrt{\overline{\delta}_{k_{0}}}\leq C\sigma\sqrt{k_{0}}\text{,}$ hence also $V\sqrt{k_{0}\overline{\delta}_{k_{0}}}\leq C\sigma k_{0}\text{.}$ Inserting these into Equation 5.10 at $k=k_{0}$ and feeding the result to the localization principle at $t^{2}\asymp\sigma^{2}[\,k_{0}\log(2+\ell_{n})+\sqrt{k_{0}\,\ell_{n}}\,]$ gives

This bound deteriorates as $k_{0}$ shrinks, but a small crossing index strengthens the projection: the profile remembers the height, $\delta_{k}\geq cH_{T}/k^{2}$ for $k\leq n/C_{\star}$ (Section S.7), so the crossing forces $V^{2}H_{T}\leq C\sigma^{2}k_{0}^{3}\text{,}$ while $R^{\mathrm{worst}}_{\mathrm{LSE}}\leq V^{2}H_{T}$ holds, the truth and its projection lying in the body. Hence

The two bounds meet at $k_{0}=\ell_{n}^{1/5}\text{:}$ for $k_{0}\leq\ell_{n}^{1/5}\text{,}$ Equation 5.12 is at most $C\ell_{n}^{2/5}\text{;}$ for $k_{0}>\ell_{n}^{1/5}\text{,}$ Equation 5.11 is at most $C[\log(2+\ell_{n})+\ell_{n}^{2/5}]\leq C^{\prime}\ell_{n}^{2/5}\text{.}$ At the endpoints $k_{0}=K+1$ and $k_{0}=1$ the deterministic caps $R^{\mathrm{worst}}_{\mathrm{LSE}}\leq\min\{V^{2}H_{T},\ \sigma^{2}n\}$ close the argument against $R^{*}_{T}$ (Section S.7). ∎

The broom is where the two geometries of this paper part ways. Euclidean geometry sees $m$ orthogonal leaf directions, and the extreme noise among them pulls the projection through the handle; the ancestor geometry sees, at every radius $r\geq 1\text{,}$ one vertex that covers the entire star, and the truncation caps its cost at the information budget rather than per leaf. The truncated ancestor profile is therefore the right geometry for this body. On every finite tree it determines the minimax rate and yields an estimator evaluated exactly, one that survives the removal of the budget at an additive cost of order $\sigma^{2}\text{;}$ across all trees it prices the blindness of the default convex program at the power $2/5$ of the logarithm.

The appendices below contain the complete proofs. References of the form Lemma 2.3, (1.4), or Section 2 point to the main body above; statements and equations proved here carry the prefix S, and the notation of the main body remains in force.

This section proves the statements deferred from Section 2, Lemmas 2.1 to 2.3, and verifies two comparisons stated in Section 1.1: the center convention behind (1.6), and the capped constraint of Chatterjee and Lafferty (2018). The two normal forms and the isometry come first; the computational claims of Lemma 2.3 then rest on an exact linear-time algorithm for minimum ancestor nets.

Proof of Lemma 2.1.

Item (1) is equivalent to item (2). Definition (1.2) reads $\mu=V\sum_{u}\lambda_{u}p_{u}$ with $\lambda$ a probability vector on $\mathsf{V}\text{,}$ and the substitution $s_{u}=V\lambda_{u}$ turns this into $\mu=\sum_{u}s_{u}p_{u}$ with $s_{u}\geq 0$ and $\sum_{u}s_{u}=V\text{.}$ For uniqueness, order $\mathsf{V}$ so that every vertex precedes its descendants, for instance by nondecreasing depth, and let $P$ be the matrix with columns $(p_{u})_{u\in\mathsf{V}}$ in that order. Its entry at row $v$ and column $u$ is $\mathbf{1}\{v\preceq u\}\text{,}$ which vanishes when $v$ follows $u\text{,}$ because a strict ancestor of $u$ precedes $u\text{;}$ and $p_{u}(u)=1$ on the diagonal. So $P$ is upper triangular with unit diagonal, hence $\det P=1$ and $P$ is invertible, and the coefficient vector is determined by $\mu\text{.}$

Item (2) implies item (3) and both displayed identities. Evaluating $\mu=\sum_{u}s_{u}p_{u}$ at $v$ gives

the first identity; at $v=o$ it reads $\mu(o)=\sum_{u}s_{u}=V\text{,}$ every vertex being a descendant of the root. The strict descendants of $v$ are partitioned by the subtrees $T_{c}\text{,}$ $c\in\operatorname{ch}(v)\text{,}$ so subtracting Equation S.1.1 at the children from Equation S.1.1 at $v$ leaves the single term $u=v\text{:}$

This is the second identity; since $s\geq 0$ it gives $\mu(v)\geq\sum_{c\in\operatorname{ch}(v)}\mu(c)\text{,}$ which with $\mu(o)=V$ is item (3).

Item (3) implies item (2). Set $s_{v}:=\mu(v)-\sum_{c\in\operatorname{ch}(v)}\mu(c)\text{,}$ nonnegative by hypothesis. We prove Equation S.1.1 by induction from the leaves upward. At a leaf the sum over children is empty, so $s_{v}=\mu(v)\text{,}$ which is the claim. At an internal vertex, the same partition of the strict descendants of $v$ and the inductive hypothesis at the children give

At $v=o$ this yields $\sum_{u}s_{u}=\mu(o)=V\text{,}$ and reading Equation S.1.1 at every coordinate says exactly $\mu=\sum_{u}s_{u}p_{u}\text{.}$ ∎

Proof of Lemma 2.2.

Part (1). A vertex is a common ancestor of $u$ and $w$ precisely when it is an ancestor of their deepest common ancestor $u\wedge w\text{,}$ and a vertex $x$ has exactly $\operatorname{depth}(x)+1$ ancestors, namely the vertices of the segment from $o$ to $x\text{.}$ Hence

and in particular $\|p_{x}\|_{2}^{2}=\operatorname{depth}(x)+1\text{.}$ Expanding the square,

the last equality because the $u$-to-$w$ path is the concatenation of the segments from $u$ up to $u\wedge w$ and from $u\wedge w$ down to $w\text{.}$ The diameter of a convex hull equals that of its generating set, so $\operatorname{diam}^{2}\mathcal{F}_{V}(T)=\max_{u,w}\|Vp_{u}-Vp_{w}\|_{2}^{2}=V^{2}H_{T}$ by (1.2).

Part (2). For $a\preceq b$ every ancestor of $a$ is an ancestor of $b\text{,}$ so

that is, $p_{b}-p_{a}=\mathbf{1}_{(a,b]}\text{.}$ For general $u,w$ put $m:=u\wedge w$ and subtract the two vertical cases,

The sets $(m,u]$ and $(m,w]$ are disjoint, since a common element would be a common ancestor of $u$ and $w$ strictly below $m\text{;}$ their union is the set of lower endpoints of the edges on the $u$-to-$w$ path, by the description of that path just used.

For the last assertion, let $u$ and $w$ lie in a connected subtree $C\text{.}$ The $u$-to-$w$ path then runs inside $C\text{,}$ so the support of $p_{u}-p_{w}$ consists of lower endpoints of edges of $C\text{.}$ Distinct edges have distinct lower endpoints, an edge being determined by its lower endpoint, so differences taken within edge-disjoint connected subtrees occupy disjoint coordinate sets. ∎

Fix an integer radius $q\geq 0\text{.}$ The residual-depth greedy computes a minimum ancestor $q$-net in one postorder pass, maintaining one number per vertex. Process the vertices in postorder, with a fixed child order, and at each vertex $v$ compute, from the values $r_{c}$ already assigned at its children,

if $d_{v}=q\text{,}$ select $v$ as a center and set $r_{v}:=-\infty\text{;}$ otherwise set $r_{v}:=d_{v}\text{.}$ After the root has been processed, select it as well if $r_{o}\neq-\infty\text{.}$ The number $r_{v}$ tracks the depth below $v$ of the deepest vertex of $T_{v}$ that no selected center covers, with $-\infty$ standing for none; the proof below verifies this reading.

Proof.

We first verify feasibility, then exhibit the selected centers, in a suitable order, as a run of a conceptually simpler procedure, the deepest-uncovered greedy, and finally prove by an exchange argument that every run of that procedure is minimum.

Feasibility. Call a vertex uncovered at a given moment when no center selected so far is an ancestor of it within distance $q\text{.}$ We claim that after $v$ is processed, $r_{v}$ is exactly the maximal depth below $v$ of an uncovered vertex of $T_{v}\text{,}$ with $r_{v}=-\infty$ when none exists, and that $r_{v}<q\text{.}$ When $v$ is examined, every selected center is an already processed vertex, and no ancestor of $v$ has been processed, so $v$ is uncovered. Moreover, an ancestor of a vertex of $T_{c}\text{,}$ for a child $c$ of $v\text{,}$ lies in $T_{c}$ or strictly above $c\text{,}$ and no center selected after $c$ was processed is of either kind: the subtree $T_{c}$ is finished, and the vertices above $c$ are not yet processed. The uncovered part of $T_{c}$ is therefore still the one described by $r_{c}\text{,}$ and the uncovered vertices of $T_{v}$ are $v$ itself together with those of the children’s subtrees, one level deeper. Hence $d_{v}$ in Equation S.1.2 is exactly the maximal depth below $v$ of an uncovered vertex of $T_{v}\text{,}$ and $d_{v}\leq q$ by the inductive bound $r_{c}<q\text{.}$ If $d_{v}=q\text{,}$ selecting $v$ covers every uncovered vertex of $T_{v}\text{,}$ all being descendants of $v$ within distance $q\text{,}$ and $r_{v}=-\infty$ is correct; otherwise no center is added and $r_{v}=d_{v}<q$ is correct. When the root has been processed, either $r_{o}=-\infty$ and nothing remains uncovered, or the final selection covers the remaining uncovered vertices, which lie within $r_{o}<q$ of the root. Each vertex is examined once at cost proportional to its number of children, so the pass costs $O(n)\text{;}$ and the child order being fixed, the algorithm makes no arbitrary choices, so the output is a deterministic function of $(T,q)\text{.}$

Reduction to the deepest-uncovered greedy. The comparison procedure repeats the following step until every vertex is covered: pick an uncovered vertex $u$ of maximum depth and select its ancestor at distance exactly $\min\{q,\operatorname{depth}(u)\}\text{.}$ To exhibit the algorithm’s output as a run of this procedure, attach to every center $g$ selected through the test $d_{g}=q$ a witness $u_{g}\in T_{g}$ realizing $d_{g}\text{,}$ so that $d_{T}(g,u_{g})=q\text{;}$ if the root is selected at the end, its witness is a deepest vertex left uncovered, at distance $r_{o}<q\text{.}$ Order the selected centers by nonincreasing depth, ties broken by processing order, with the final root selection last, and let $P$ denote the set of centers preceding a given center in this order.

Fix a center $g$ with $d_{T}(g,u_{g})=q\text{.}$ First, $u_{g}$ is uncovered when only $P$ is in place: a center covering $u_{g}$ is an ancestor of $u_{g}$ of depth at least $\operatorname{depth}(u_{g})-q=\operatorname{depth}(g)\text{,}$ so it lies on the vertical segment between $g$ and $u_{g}\text{,}$ inside $T_{g}\text{,}$ and was processed, and selected, before $g\text{;}$ had it covered $u_{g}\text{,}$ then $u_{g}$ would already be covered when $g$ was examined and could not realize $d_{g}\text{.}$ Second, every vertex $w$ strictly deeper than $u_{g}$ is covered by $P\text{:}$ the complete output is feasible, so some selected center $c$ satisfies $c\preceq w$ and $d_{T}(c,w)\leq q\text{,}$ whence

and every selected center strictly deeper than $g$ precedes it. Thus at $g$’s turn the vertex $u_{g}$ is a deepest uncovered vertex, and $g$ is its ancestor at distance exactly $q=\min\{q,\operatorname{depth}(u_{g})\}\text{.}$

For the final root selection with witness $u\text{:}$ no nonroot center covers the witness, which is still uncovered after the whole tree has been processed; every $w$ strictly deeper than $u$ is covered by a nonroot center, since otherwise $w$ would be an uncovered vertex deeper than $u$ at that moment, contradicting the maximality defining $r_{o}\text{;}$ and the root is the ancestor of $u$ at distance $\operatorname{depth}(u)=\min\{q,\operatorname{depth}(u)\}\text{,}$ since $\operatorname{depth}(u)=r_{o}<q\text{.}$

Optimality by exchange. Suppose, inductively, that some minimum ancestor $q$-net $O$ contains the first $t-1$ centers of a run of the deepest-uncovered greedy; let $u$ be the uncovered vertex of maximum depth picked at step $t$ and $g$ its selected ancestor. Feasibility of $O$ provides $c\in O$ with $c\preceq u$ and $d_{T}(c,u)\leq q\text{;}$ being an ancestor of $u$ of depth at least $\operatorname{depth}(u)-q\text{,}$ the center $c$ lies on the segment between $g$ and $u\text{,}$ and $c$ is not among the first $t-1$ centers, which do not cover $u\text{.}$ Set $O^{\prime}:=(O\setminus\{c\})\cup\{g\}\text{.}$ A vertex $x$ covered by $c$ but not by $g$ is a descendant of $g\text{,}$ as $g\preceq c\preceq x\text{,}$ with $d_{T}(g,x)>q\text{,}$ so that

and $x$ is covered by the first $t-1$ centers, which lie in $O^{\prime}\text{.}$ Thus $O^{\prime}$ is feasible, contains the first $t$ centers, and $|O^{\prime}|\leq|O|\text{,}$ so $O^{\prime}$ is again a minimum net. By induction the complete run is contained in a minimum net, and being itself feasible, it is minimum. ∎

Proof of Lemma 2.3.

Throughout, write $c_{q}:=\min\{k,[\log(N^{\uparrow}_{T}(q)/k)]_{+}\}$ for the truncated factor of the profile at integer radius $q\text{,}$ the dependence on the fixed index $k$ suppressed from the notation.

Part (1). Dividing the truncated factor in (1.4) by $k$ and using $\min\{k,x\}/k=\min\{1,x/k\}$ gives

Fix $r\text{.}$ As $k$ increases, $[\log(N^{\uparrow}_{T}(r)/k)]_{+}$ is nonnegative and nonincreasing, and so is $1/k\text{;}$ a product of two nonnegative nonincreasing functions is nonincreasing, and the cap by $1$ preserves this. Every term of the supremum in Equation S.1.3 is therefore nonincreasing in $k\text{,}$ and so is $\delta_{k}\text{.}$ For the upper bound, the root is an ancestor of every vertex within distance $h_{T}\text{,}$ so $N^{\uparrow}_{T}(r)=1$ and the term vanishes for $r\geq h_{T}\text{,}$ while for $r<h_{T}$ the term is at most $r<h_{T}\text{;}$ hence $\delta_{k}\leq h_{T}\text{.}$

Part (2). Tree distances take integer values, so the covering constraint $d_{T}(a,u)\leq r$ is equivalent to $d_{T}(a,u)\leq\lfloor r\rfloor\text{,}$ and $N^{\uparrow}_{T}(r)=N^{\uparrow}_{T}(\lfloor r\rfloor)$ for every $r\geq 0\text{.}$ The supremum in (1.4) therefore splits along integer radii:

the inner supremum being approached as $r\uparrow q+1\text{.}$ Radii $q\geq h_{T}$ have $N^{\uparrow}_{T}(q)=1$ and $c_{q}=0\text{,}$ so the outer supremum is a maximum over the integers $0\leq q<h_{T}\text{,}$ an empty maximum being zero; this also covers $n=1\text{,}$ where $h_{T}=0\text{.}$

Part (3): the two-sided comparison. Write $G:=\{2^{\ell}-1:\ \ell\in\{0,1,2,\dots\},\ 2^{\ell}\leq h_{T}\}$ for the grid, so that (2.1) reads $\overline{\delta}_{k}=\tfrac{2}{k}\max_{q\in G}(q+1)c_{q}\text{.}$ The grid consists of integer radii below $h_{T}\text{,}$ so part (2) gives $\max_{q\in G}(q+1)c_{q}\leq\alpha_{k}\text{,}$ that is, $\overline{\delta}_{k}\leq 2\delta_{k}\text{.}$ Conversely, fix an integer $0\leq q<h_{T}$ and set $s:=q+1\in[1,h_{T}]\text{;}$ the largest power of two $p\leq s$ satisfies $p>s/2\text{,}$ and $q^{\prime}:=p-1$ belongs to $G$ with $q^{\prime}\leq q\text{.}$ Every ancestor $q^{\prime}$-net is an ancestor $q$-net, so $N^{\uparrow}_{T}(q^{\prime})\geq N^{\uparrow}_{T}(q)$ and $c_{q^{\prime}}\geq c_{q}\text{,}$ whence

Maximizing over $q$ gives $\max_{q\in G}(q+1)c_{q}\geq\alpha_{k}/2\text{,}$ that is, $\overline{\delta}_{k}\geq\delta_{k}\text{.}$ When $h_{T}=0$ both sides vanish by convention. Monotonicity of $k\mapsto\overline{\delta}_{k}$ follows as in part (1), applied to the finite maximum over $G\text{.}$

Part (3): the sandwich. Put $K:=\lfloor n/C_{\star}\rfloor\text{.}$ The dimension clause $k>n/C_{\star}$ first holds at $k=K+1\text{,}$ so the minima in (1.5) and (2.2) are over nonempty sets and $k_{0},k_{\mathrm{alg}}\leq K+1\text{.}$ For the lower half: if $k_{0}\leq K\text{,}$ the dimension clause fails at $k_{0}\text{,}$ so the profile clause holds there, $V^{2}\overline{\delta}_{k_{0}}\leq 2V^{2}\delta_{k_{0}}\leq 2A_{0}\sigma^{2}k_{0}\text{,}$ and $k_{\mathrm{alg}}\leq k_{0}\text{;}$ if $k_{0}=K+1\text{,}$ then $k_{\mathrm{alg}}\leq K+1=k_{0}$ directly. For the upper half: if $k_{\mathrm{alg}}=K+1\text{,}$ the lower half forces $k_{0}=K+1=k_{\mathrm{alg}}\text{.}$ Otherwise $k_{\mathrm{alg}}\leq K\text{,}$ so the dimension clause of (2.2) fails at $k_{\mathrm{alg}}\text{,}$ its profile clause holds, and $V^{2}\delta_{k_{\mathrm{alg}}}\leq V^{2}\overline{\delta}_{k_{\mathrm{alg}}}\leq 2A_{0}\sigma^{2}k_{\mathrm{alg}}\text{.}$ If $k_{0}=k_{\mathrm{alg}}$ there is nothing to prove. If $k_{0}>k_{\mathrm{alg}}\text{,}$ every integer $k$ with $k_{\mathrm{alg}}\leq k\leq k_{0}-1$ fails both clauses of (1.5) by the minimality of $k_{0}\text{;}$ in particular $V^{2}\delta_{k}>A_{0}\sigma^{2}k\text{,}$ and combining this with the monotonicity of part (1),

so $k<2k_{\mathrm{alg}}\text{.}$ At $k=k_{0}-1$ this reads $k_{0}-1<2k_{\mathrm{alg}}\text{,}$ that is, $k_{0}\leq 2k_{\mathrm{alg}}\text{.}$

Part (3): complexity. Lemma S.1.1 computes $N^{\uparrow}_{T}(q)$ exactly in $O(n)$ operations for each integer radius. The grid $G$ has $O(\log(h_{T}+1))$ elements, so storing $\{N^{\uparrow}_{T}(q)\}_{q\in G}$ costs $O(n\log(h_{T}+1))\text{,}$ after which each evaluation of $\overline{\delta}_{k}$ costs $O(\log(h_{T}+1))\text{.}$ The predicate in (2.2) is monotone in $k\text{:}$ in its profile clause the left side is nonincreasing by the monotonicity proved above and the right side is increasing, and its dimension clause is monotone; $k_{\mathrm{alg}}$ is therefore located by binary search over $\{1,\dots,K+1\}$ with $O(\log n)$ predicate evaluations. Since $h_{T}<n\text{,}$ the total is $O(n\log(n+1))\text{.}$ For $k_{0}\text{,}$ running Lemma S.1.1 at every integer radius $0\leq q<h_{T}$ costs $O(n\,h_{T})$ and stores all counts; each $\alpha_{k}$ then costs $O(h_{T})$ by (2.3), and scanning $k=1,2,\dots$ until the first index satisfying (1.5), at most $K+1\leq n$ values, costs $O(n\,h_{T})$ in total. ∎

Finally, we verify the center-convention comparison stated with (1.6). Write $H^{c,\mathrm{int}}_{T}(t)$ for the covering entropy of $\mathcal{F}_{V}(T)$ at squared radius $t$ with centers restricted to the body, and

Since every cover with centers in the body is in particular a cover with free centers, $H^{c}_{T}(t)\leq H^{c,\mathrm{int}}_{T}(t)$ for every $t>0\text{.}$ Conversely, fix $t>0$ and a cover of the body by $\exp H^{c}_{T}(t)$ balls of radius $\sqrt{t}$ with arbitrary centers, and replace the center $y$ of each ball by its Euclidean projection $\pi_{y}:=\Pi_{\mathcal{F}_{V}(T)}(y)$ onto the body. The variational inequality of the projection, $\langle y-\pi_{y},\mu-\pi_{y}\rangle\leq 0$ for every $\mu\in\mathcal{F}_{V}(T)\text{,}$ gives

so every $\mu$ within $\sqrt{t}$ of $y$ is within $\sqrt{t}$ of $\pi_{y}\text{.}$ The projected balls, of the same radius and number, cover the body with internal centers, so $H^{c,\mathrm{int}}_{T}(t)\leq H^{c}_{T}(t)\text{.}$ The two entropies coincide at every radius, and $\rho^{\mathrm{int}}_{T}=\rho_{T}\text{:}$ the center convention is immaterial.

We also verify the comparison with the capped constraint of Chatterjee and Lafferty (2018), stated in Section 1.1. Let

the infimum over the same maps as in (1.3), and assume $n\geq 2\text{.}$ Since $\mathcal{F}_{V}(T)\subseteq\mathcal{K}_{V}(T)\text{,}$ every estimator has at least as large a supremum risk on the larger set, so $R^{\mathrm{cap}}_{T}\geq R^{*}_{T}\text{.}$

For the reverse, split $\mu$ into its root value $\mu(o)$ and its remaining coordinates $\mu_{-}\text{,}$ and write $C_{a}$ for the set of $\mu_{-}$ arising from $\mu\in\mathcal{F}_{a}(T)\text{.}$ Adding $(V-a)p_{o}$ to such a $\mu$ raises its root value to $V$ and changes no other coordinate, so $C_{a}\subseteq C_{V}$ whenever $0<a\leq V\text{,}$ and $C_{0}:=\{0\}\subseteq C_{V}$ as well. On the slice the root value is known, so it is estimated at no loss, while $Y_{o}$ is independent of $Y_{-}$ with a law free of $\mu_{-}$ and therefore acts as pure randomization, which cannot lower a maximum risk under squared loss; hence $R^{*}_{T}(V,\sigma)$ is exactly the minimax risk of estimating $\mu_{-}\in C_{V}$ from $Y_{-}\text{.}$ Fix $\varepsilon>0\text{,}$ let $\widehat{\theta}$ attain that risk to within $\varepsilon\text{,}$ and on the capped body take $\widehat{\mu}_{-}:=\widehat{\theta}(Y_{-})$ together with

Every $\mu\in\mathcal{K}_{V}(T)$ has $\mu_{-}\in C_{\mu(o)}\subseteq C_{V}\text{,}$ so its nonroot risk is at most $R^{*}_{T}(V,\sigma)+\varepsilon\text{.}$ Its root risk is at most $\mu(o)^{2}\leq V^{2}$ in the first case, and at most $\mathbb{E}(Y_{o}-\mu(o))^{2}=\sigma^{2}$ in the second, projection onto an interval containing $\mu(o)$ being nonexpansive. Letting $\varepsilon\downarrow 0\text{,}$

Finally $n\geq 2$ forces $H_{T}\geq 1\text{,}$ so the two-point bound (3.8) gives

fixing the root value and capping it pose the same problem up to universal constants.

The comparison is constructive: the estimator of Theorem 2 transfers to the capped body. At budget $V$ its root coordinate is identically $V\text{,}$ and its nonroot coordinates depend on $Y$ only through $Y_{-}\text{:}$ every integer state has root coordinate $k\text{,}$ so the root factor cancels from the ratio (4.2), and the branch selection in (4.3) depends on $(T,V,\sigma)$ alone. Write $\widehat{\mu}^{V}_{-}(Y_{-})$ for this nonroot part. For $\mu\in\mathcal{K}_{V}(T)$ the raised signal $(V,\mu_{-})$ lies in $\mathcal{F}_{V}(T)\text{,}$ and $Y_{-}$ has the law of the nonroot data of the slice model there, so Theorem 2 bounds the risk of $\widehat{\mu}^{V}_{-}$ against $\mu_{-}$ by $C\,R^{*}_{T}(V,\sigma)\text{,}$ uniformly over $\mathcal{K}_{V}(T)\text{.}$ Paired with the root rule above, it yields a deterministic estimator, computed in $O(n^{2}\log(n+1))$ arithmetic operations, whose risk on the capped body is at most $C\bigl(R^{*}_{T}(V,\sigma)+\min\{V^{2},\sigma^{2}\}\bigr)\leq C^{\prime}\,R^{\mathrm{cap}}_{T}(V,\sigma)\text{.}$

This section completes the proof of Proposition 3.1. The main text gives the mechanism behind each stage. To make this section self-contained, we restate the objects below and supply the estimates and accounting: the floor on the working scale and the sizes of the nets, the structure of the cells, the disjointness and charge accounting of the heavy hierarchy, the collapse and exit estimates, the edge count of the skeleton together with the explicit constants of the error assembly, and the counting bound for the coded cover.

Throughout, $k$ is an integer with $2\leq k\leq n/C_{\star}$ and, as in Section 3.1, $\bar{\alpha}:=k\overline{\delta}_{k}(T)\text{;}$ the level weights are $m_{j}=2^{j}$ for $0\leq j\leq J\text{,}$ with $m_{J}$ the largest power of two strictly below $k\text{;}$ $S_{j}$ is the minimum ancestor $\lfloor\bar{\alpha}/m_{j}\rfloor$-net computed by the greedy of Lemma S.1.1; and $R_{j}:=S_{0}\cup\dots\cup S_{j}\text{.}$ The net hierarchy, the active support and the activation charges below therefore depend on $(T,k)$ alone, the signal entering only through the stopped refinement of the construction. The active support, the first-appearance weight, and the activation charge are

and the code length of an integer vector $z$ supported on $A_{k}$ is

the display (3.1). Throughout, $e_{v}$ denotes the coordinate vector at $v\text{.}$

The first lemma contains the size facts quoted when the nets are introduced: the working scale is never degenerate, and the profile itself caps the size of every net.

Proof.

Part (1). The surrogate dominates the profile, $\overline{\delta}_{k}\geq\delta_{k}$ by Lemma 2.3, so $\bar{\alpha}=k\overline{\delta}_{k}\geq k\delta_{k}=\alpha_{k}(T)\text{.}$ For the floor, tree distances are integers, so at radii $0<r<1$ every vertex is its own only ancestor within distance $r\text{;}$ every ancestor $r$-net then contains all of $\mathsf{V}\text{,}$ and $N^{\uparrow}_{T}(r)=n\text{.}$ Hence

using $k\geq 2$ and $n/k\geq C_{\star}=e^{2}\text{.}$

Part (2). Fix $0\leq j\leq J$ and suppose $N^{\uparrow}_{T}(\lfloor\bar{\alpha}/m_{j}\rfloor)>ke^{m_{j}}\text{.}$ The radius $r:=\bar{\alpha}/m_{j}$ is positive by part (1), and the covering constraint depends on $r$ only through $\lfloor r\rfloor\text{,}$ so $N^{\uparrow}_{T}(r)=N^{\uparrow}_{T}(\lfloor r\rfloor)>ke^{m_{j}}\text{,}$ that is, $[\log(N^{\uparrow}_{T}(r)/k)]_{+}>m_{j}\text{.}$ Since also $m_{j}\leq m_{J}<k\text{,}$ the minimum of $k$ and this positive part exceeds $m_{j}\text{,}$ and the term of (1.4) at $r$ satisfies

contradicting that $\alpha_{k}(T)$ is the supremum of these terms.

Part (3). The sets $S_{i}$ are minimum nets, so $|S_{i}|=N^{\uparrow}_{T}(\lfloor\bar{\alpha}/m_{i}\rfloor)\leq ke^{m_{i}}$ by part (2), and $|R_{j}|\leq k\sum_{i\leq j}e^{m_{i}}\text{.}$ For $j\geq 1$ the sum has $j$ terms before the last, each at most $e^{m_{j-1}}\text{,}$ and $j\leq e^{2^{j-1}}$ gives $je^{m_{j-1}}\leq e^{m_{j-1}+2^{j-1}}=e^{m_{j}}\text{,}$ so $\sum_{i\leq j}e^{m_{i}}\leq 2e^{m_{j}}\text{;}$ for $j=0$ this is immediate. ∎

The cells inherit their structure from the nesting of the nets alone. Parts (2)–(4) below are the rooted-connectedness, refinement, and radius properties quoted in the main body; part (3) also identifies the parent of each cell, the hierarchy used from here on.

Proof.

All four parts are read off the chain structure of ancestors and the nesting $R_{j}\subseteq R_{j+1}\text{.}$

Part (1). The root lies in every ancestor net, being its own only ancestor, so every vertex has an ancestor in $R_{j}\text{;}$ the ancestors of $v$ form a chain, so among them the elements of $R_{j}$ have a unique deepest member, and $a_{j}(v)$ is well defined. The fibers of $v\mapsto a_{j}(v)$ partition $\mathsf{V}\text{,}$ and $a_{j}(a)=a$ for $a\in R_{j}\text{.}$

Part (2). Every ancestor of $z$ is an ancestor of $v\text{,}$ so every $R_{j}$-ancestor of $z$ has depth at most $\operatorname{depth}(a_{j}(v))=\operatorname{depth}(a)\text{;}$ and $a$ itself is an $R_{j}$-ancestor of $z\text{,}$ since $a\preceq z\text{.}$ Hence $a_{j}(z)=a\text{.}$

Part (3). Let $s$ be an $R_{j}$-ancestor of $u\text{.}$ Then $s\in R_{j+1}\text{,}$ so $\operatorname{depth}(s)\leq\operatorname{depth}(b)\text{;}$ and $s$ and $b$ are comparable, both being ancestors of $u\text{,}$ so $s\preceq b$ and $s$ is an $R_{j}$-ancestor of $b\text{.}$ Conversely, every $R_{j}$-ancestor of $b$ is an ancestor of $u\text{,}$ since $b\preceq u\text{.}$ The $R_{j}$-ancestors of $u$ and of $b$ therefore coincide, and $a_{j}(u)=a_{j}(b)\text{.}$ In particular $B_{b,j+1}\subseteq B_{a_{j}(b),j}\text{,}$ and $a_{j}(b)\preceq b\text{.}$

Part (4). The net property supplies $s\in R_{j}$ with $s\preceq v$ and $d_{T}(s,v)\leq\lfloor\bar{\alpha}/m_{j}\rfloor\text{.}$ The deepest $R_{j}$-ancestor $a=a_{j}(v)$ has $\operatorname{depth}(a)\geq\operatorname{depth}(s)\text{,}$ so $a$ lies on the segment from $s$ to $v$ and $d_{T}(a,v)\leq d_{T}(s,v)\leq\lfloor\bar{\alpha}/m_{j}\rfloor\text{.}$ ∎

The remaining facts concern the stopped refinement that the proof of Proposition 3.1 runs for a fixed signal. Fix $f=\sum_{u}\lambda_{u}p_{u}$ with $\lambda_{u}\geq 0$ and $\sum_{u}\lambda_{u}=1\text{,}$ write $\lambda(B):=\sum_{u\in B}\lambda_{u}\text{,}$ write $m(B):=m_{j}$ for the level weight of a level-$j$ cell $B\text{,}$ and call $B$ heavy when $\lambda(B)>m(B)/k$ and light otherwise. The refinement begins at level $0\text{,}$ refines every heavy cell into its level-$(j{+}1)$ subcells, stops at every light cell, and stops everything at level $J\text{.}$ The cells at which it stops are the terminal cells. They partition $\mathsf{V}$ because the cells of one level do and each refinement step replaces a cell by a partition of it (Lemma S.2.2(1),(3)), and $\mathcal{L}$ denotes their collection. For $L\in\mathcal{L}$ we write $a_{L}$ for its root and $\lambda_{L}:=\lambda(L)\text{.}$ As in the main proof, $U$ consists of $R_{0}$ together with the roots of all heavy cells; a heavy cell is maximal when no heavy cell lies strictly below it in the hierarchy of Lemma S.2.2(3).

Proof.

Part (1) is a chain argument in the hierarchy, and part (4) follows from it; part (2) charges the skeleton to vertical segments along the nets; part (3) charges activation weights to maximal heavy cells.

Parts (1) and (4). Suppose two distinct heavy cells $(B,i)$ and $(B^{\prime},j)$ with $i\leq j$ have intersecting underlying sets. Cells at one level partition $\mathsf{V}\text{,}$ so $i<j\text{.}$ Iterating Lemma S.2.2(3), $B^{\prime}$ is contained in a unique cell of each level below $j\text{;}$ its level-$i$ cell meets $B\text{,}$ hence equals $B\text{,}$ and the chain of cells containing $B^{\prime}$ at levels $i,\dots,j$ ascends from $(B^{\prime},j)$ to $(B,i)$ in the hierarchy. Each cell of this chain, at level $\ell$ say, has mass at least $\lambda(B^{\prime})>m_{j}/k\geq m_{\ell}/k$ and is therefore heavy. In particular the chain member at level $i{+}1$ is a heavy cell strictly below $(B,i)\text{,}$ so $(B,i)$ is not maximal. Distinct maximal heavy cells therefore cannot intersect. Each carries mass exceeding $m(C)/k\text{,}$ and their supports being disjoint, their masses total at most $\lambda(\mathsf{V})=1\text{,}$ so

which is part (4); the empty family satisfies it trivially.

Part (2). The subtree $S$ lies in the union of two families of vertical segments, whose total length we bound.

First, connect $R_{0}$ to the root. For $a\in R_{0}\setminus\{o\}\text{,}$ the net property of $R_{0}$ at the parent of $a$ supplies $s\in R_{0}$ with $s\preceq\operatorname{pa}(a)$ and $d_{T}(s,\operatorname{pa}(a))\leq\lfloor\bar{\alpha}\rfloor\text{;}$ the deepest strict $R_{0}$-ancestor $\bar{a}$ of $a$ then lies on the segment from $s$ to $a\text{,}$ so

by Lemma S.2.1(1). Iterating $a\mapsto\bar{a}$ from any element of $R_{0}$ reaches the root, which belongs to every ancestor net, so the segments $[\bar{a},a]\text{,}$ $a\in R_{0}\setminus\{o\}\text{,}$ connect $R_{0}$ to $o\text{;}$ by Lemma S.2.1(2) their total length is at most $\tfrac{3}{2}\bar{\alpha}\,|R_{0}|\leq\tfrac{3}{2}e\,\bar{\alpha}k\text{.}$

Second, connect the heavy roots to $R_{0}\text{.}$ The root $b$ of a heavy cell $B$ at level $j\geq 1$ lies in its parent cell, whose root $a_{j-1}(b)$ is an ancestor of $b$ within distance $\lfloor\bar{\alpha}/m_{j-1}\rfloor\leq 2\bar{\alpha}/m_{j}$ (Lemma S.2.2(3)–(4)); and the parent cell is heavy as well, its mass being at least $\lambda(B)>m_{j}/k>m_{j-1}/k\text{.}$ Iterating these segments joins every heavy root to the root of a level-$0$ cell, which lies in $R_{0}\text{.}$ At level $j$ the heavy cells are disjoint and each has mass exceeding $m_{j}/k\text{,}$ so there are fewer than $k/m_{j}$ of them, and the segments they contribute have total length less than

Every member of $U$ is thus connected to the root inside the union of the two families, so $S$ is contained in that union and $|E(S)|\leq\tfrac{3}{2}e\,\bar{\alpha}k+\tfrac{2}{3}\,\bar{\alpha}k\leq 5\bar{\alpha}k\text{.}$

Part (3). The set $U\setminus R_{0}$ consists of roots of heavy cells at levels $j\geq 1\text{.}$ Charge each $v\in U\setminus R_{0}$ to a heavy cell rooted at $v$ of minimal level $j(v)\geq 1\text{;}$ roots of level-$j$ cells lie in $R_{j}\text{,}$ so $\widetilde{\omega}(v)=\omega(v)\leq m_{j(v)}\text{,}$ and the charging is injective into the set $\mathcal{H}$ of heavy cells. Hence

Assign every heavy cell to one maximal heavy cell weakly below it in the hierarchy, obtained by descending to heavy children while one exists. The cells assigned to a fixed maximal cell $(C,\ell)$ all lie on its ancestor chain, so their level weights total at most $m_{0}+m_{1}+\dots+m_{\ell}<2m_{\ell}\text{,}$ and

the last step by part (4), which also covers the case of an empty family. ∎

The construction of the main proof samples the light exits at random. The next lemma supplies the collapse bound quoted there, the exit estimates behind the fixed realization, and the budgets that realization carries. Its objects are the following.

Collapsing every terminal cell to its root gives $g:=\sum_{L\in\mathcal{L}}\lambda_{L}p_{a_{L}}\text{.}$ A heavy terminal cell is one the refinement did not split, so it sits at level $J$ and no heavy cell lies below it; being maximal it contributes $m_{J}\geq k/2$ to the sum in Lemma S.2.3(4), and there is therefore at most one. Each terminal cell $L$ is attached to $U$ at $h(L):=a_{L}$ when $L$ is a level-$0$ cell or the heavy terminal one, and otherwise at the root of the parent cell of $L\text{,}$ which is heavy because $L$ was reached by the refinement; either way $h(L)\in U\text{,}$ and $h(L)\preceq a_{L}$ by Lemma S.2.2(3). Put $q_{L}:=p_{a_{L}}-p_{h(L)}\text{.}$ In the first two cases $q_{L}=0\text{;}$ otherwise, $L$ sits at a level $j\geq 1\text{,}$ and its parent cell has level weight $m_{j}/2=m(L)/2$ and contains $a_{L}\text{,}$ so Lemma S.2.2(4) and Lemma 2.2(1) give

With $b_{h}:=\sum_{L:\,h(L)=h}\lambda_{L}$ this splits the collapsed signal as $g=g_{0}+\sum_{L}\lambda_{L}q_{L}\text{,}$ where $g_{0}:=\sum_{h\in U}b_{h}p_{h}$ is the skeleton and the nonzero $q_{L}$ are the light exits.

The skeleton is rounded through one scalar. List $U$ as $h_{1},\dots,h_{s}$ in a fixed depth-first preorder of $T\text{,}$ write $b_{i}:=b_{h_{i}}$ for the masses in that order, set $B_{i}:=\sum_{\ell\leq i}b_{\ell}$ with $B_{0}:=0\text{,}$ and put $Q_{i}:=\lfloor kB_{i}\rfloor-\lfloor kB_{i-1}\rfloor\in\mathbb{Z}_{\geq 0}\text{.}$ Let $Q$ be the integer vector with $Q_{h_{i}}:=Q_{i}$ and $Q_{v}:=0$ for $v\notin U\text{,}$ and set $\bar{g}_{0}:=\frac{1}{k}\sum_{h\in U}Q_{h}p_{h}\text{.}$ Over an interval of the list the $Q_{i}$ telescope, so their sum differs from $k$ times the corresponding mass by a difference of two floor errors, hence by less than $1\text{.}$ The terminal cells partition $\mathsf{V}\text{,}$ so $B_{s}=\sum_{L}\lambda_{L}=1$ and the whole list gives $\sum_{i}Q_{i}=\lfloor kB_{s}\rfloor=k\text{;}$ as the $B_{i}$ increase, $Q$ is a nonnegative integer leak vector of total mass $k$ supported on $U\text{.}$ Every subtree $T_{v}$ is a contiguous block of a depth-first preorder, so $U\cap T_{v}$ is such an interval, and coordinates are subtree sums by Lemma 2.1; therefore $g_{0}$ and $\bar{g}_{0}$ differ by less than $1/k$ at every vertex simultaneously.

Finally, write $\mathcal{L}_{\mathrm{ex}}:=\{L\in\mathcal{L}:q_{L}\neq 0\}$ for the light exits, every member of which is a light cell and therefore has $\lambda_{L}\leq m(L)/k\text{.}$ They are quantized by the independent variables $Z_{L}=\frac{m(L)}{k}\xi_{L}\text{,}$ $L\in\mathcal{L}_{\mathrm{ex}}\text{,}$ with $\xi_{L}\sim\mathrm{Bernoulli}(k\lambda_{L}/m(L))\text{,}$ which is a legitimate parameter by that bound. With the selection weight $W:=\sum_{L\in\mathcal{L}_{\mathrm{ex}}}m(L)\mathbf{1}\{Z_{L}\neq 0\}\text{,}$ the integer vector is

and the flow states of an integer vector $z$ are the subtree sums $x_{v}:=\sum_{u\succeq v}z_{u}\text{,}$ that is, the coordinates of $\sum_{u}z_{u}p_{u}\text{.}$

Proof.

Part (1). The blocks $e_{L}=\sum_{u\in L}\lambda_{u}(p_{u}-p_{a_{L}})$ have pairwise disjoint supports, as recorded in the main proof, so $\|f-g\|_{2}^{2}=\sum_{L\in\mathcal{L}}\|e_{L}\|_{2}^{2}\text{.}$ Every $u\in L$ has $d_{T}(a_{L},u)\leq\bar{\alpha}/m(L)$ by Lemma S.2.2(4), so the triangle inequality and Lemma 2.2(1) give $\|e_{L}\|_{2}\leq\sum_{u\in L}\lambda_{u}\sqrt{d_{T}(a_{L},u)}\leq\lambda_{L}\sqrt{\bar{\alpha}/m(L)}\text{.}$ A light terminal cell has $\lambda_{L}\leq m(L)/k\text{,}$ whence $\|e_{L}\|_{2}^{2}\leq\lambda_{L}^{2}\bar{\alpha}/m(L)\leq\lambda_{L}\bar{\alpha}/k\text{,}$ and summing over the light cells with $\sum_{L}\lambda_{L}\leq 1$ bounds their total contribution by $\bar{\alpha}/k\text{.}$ At most one terminal cell is heavy; it sits at level $J\text{,}$ where $m_{J}\geq k/2\text{,}$ and contributes $\|e_{L}\|_{2}^{2}\leq\lambda_{L}^{2}\bar{\alpha}/m_{J}\leq 2\bar{\alpha}/k\text{.}$ Adding the two bounds proves (1).

Part (2). Each $Z_{L}$ has mean $\lambda_{L}$ and

while $\|q_{L}\|_{2}^{2}\leq 2\bar{\alpha}/m(L)$ by Equation S.2.1. The $Z_{L}$ are independent, so the cross terms vanish in expectation. With every sum below running over $L\in\mathcal{L}_{\mathrm{ex}}\text{,}$

Also $\mathbb{E}W=\sum_{L}m(L)\,k\lambda_{L}/m(L)=k\sum_{L}\lambda_{L}\leq k\text{.}$ By Markov’s inequality $\mathbb{P}(W>2k)\leq\tfrac{1}{2}\text{,}$ and the squared norm exceeds $8\bar{\alpha}/k$ with probability at most $\tfrac{1}{4}\text{,}$ so both bounds hold with probability at least $\tfrac{1}{4}\text{.}$

Part (3). The skeleton $Q$ is supported on $U\subseteq A_{k}$ and each selected transfer on $\{a_{L},h(L)\}\text{;}$ the root of a level-$j$ cell lies in $R_{j}\subseteq A_{k}\text{,}$ so $\operatorname{supp}(z)\subseteq A_{k}\text{.}$ Since $Q$ is nonnegative with total mass $k$ and each selected transfer adds $2m(L)$ to the $\ell_{1}$ norm, $\|z\|_{1}\leq k+2W\leq 5k\text{.}$ The selected exit roots are distinct, being roots of distinct terminal cells, and $\widetilde{\omega}(a_{L})\leq\omega(a_{L})\leq m(L)$ because $a_{L}\in R_{j}$ with $m_{j}=m(L)\text{;}$ their charges therefore total at most $\sum_{L:\,Z_{L}\neq 0}m(L)=W\text{.}$ ∎

Two explicit constants follow. The subtree $S$ has at most $5\bar{\alpha}k+1\leq 6\bar{\alpha}k$ vertices, by Lemma S.2.3(2) and $\bar{\alpha}\geq 2\text{;}$ since $g_{0}$ and $\bar{g}_{0}$ differ by less than $1/k$ at every vertex and vanish outside $S\text{,}$ $\|g_{0}-\bar{g}_{0}\|_{2}^{2}<6\bar{\alpha}k/k^{2}=6\bar{\alpha}/k\text{:}$ the display (3.5) holds with $C=6\text{.}$ Together with the collapse and exit bounds of Lemma S.2.4, the error assembly of the main proof reads

the last step by Lemma 2.3, so part (1) of Proposition 3.1 holds with $C_{0}=102\text{.}$

It remains to prove the counting bound.

Proof.

We bound the larger class defined by the support and code-length constraints alone. Each member $z$ determines its support, split into the free part $\operatorname{supp}(z)\cap R_{0}$ and the charged part $\operatorname{supp}(z)\setminus R_{0}\text{,}$ and its coefficient vector; we count the three in turn and multiply.

Free parts. Any subset of $R_{0}$ can occur, and $|R_{0}|\leq ke^{m_{0}}=ek$ by Lemma S.2.1(2), so the free parts number at most $2^{ek}\leq e^{ek}\text{.}$

Charged parts. Group the charged vertices by first appearance: $G_{j}:=\{v\in A_{k}\setminus R_{0}:\ \omega(v)=m_{j}\}$ satisfies $G_{j}\subseteq R_{j}\text{,}$ hence $|G_{j}|\leq 2ke^{m_{j}}$ by Lemma S.2.1(3), for $1\leq j\leq J\text{.}$ The groups partition $A_{k}\setminus R_{0}\text{,}$ so a charged part is the disjoint union of its intersections with them, and one with $q_{j}$ elements of $G_{j}$ carries activation charge $\sum_{j}m_{j}q_{j}\leq\Gamma(z)\leq 9k\text{.}$ Inserting the factor $e^{2(9k-\sum_{j}m_{j}q_{j})}\geq 1$ and then dropping the charge constraint,

using $\log(1+x)\leq x\text{,}$ $|G_{j}|e^{-2m_{j}}\leq 2ke^{-m_{j}}\text{,}$ and $\sum_{j\geq 1}e^{-2^{j}}<\tfrac{1}{6}\text{.}$

Coefficients. Every charged support vertex carries charge at least $1\text{,}$ so a support has at most $ek+9k\leq 12k$ vertices. On a fixed support of size $d\text{,}$ the map $z\mapsto(z^{+},z^{-})$ is injective into the nonnegative integer vectors on $2d$ coordinates with total at most $9k\text{,}$ since $\|z\|_{1}\leq\Gamma(z)\leq 9k\text{;}$ these number $\binom{9k+2d}{2d}\leq 2^{9k+2d}\leq 2^{33k}\leq e^{23k}\text{.}$

Multiplying the three counts bounds the class by $e^{(e+19+23)k}\leq e^{45k}\text{.}$ ∎

The facts quoted in the main proof are now all in place, and Proposition 3.1 is proved.

This section completes the lower-bound half of Section 3.2. Lemmas 3.2 and 3.3, whose proofs were sketched there, are proved in full first, with the constants of the latter fixed. Two self-contained lemmas follow: the additivity of Bayes risks across coordinate-disjoint blocks, and the edge-disjoint grouping of a separated vertex set. The section then completes the proofs of Propositions 3.4 and 3.5, and finally the deferred cases of Theorem 1 and Proposition 1.

Proof of Lemma 3.2.

Write $\mathcal{P}:=\{p_{u}:u\in\mathsf{V}\}$ and $\varepsilon:=\sqrt{r}/3\text{,}$ and fix a maximal $\varepsilon$-separated subset of $\mathcal{P}\text{;}$ by maximality, every point of $\mathcal{P}$ lies within Euclidean distance $\varepsilon$ of the subset. By Lemma 2.2(1), the vertices indexing the subset have pairwise tree distances at least $\varepsilon^{2}=r/9\text{,}$ so it suffices to bound their number below by $N^{\uparrow}_{T}(r)\text{.}$

Consider the ball of radius $\varepsilon$ around one point of the subset, let $C$ be the set of vertices whose indicators it contains, and let $a$ be the deepest common ancestor of $C\text{.}$ Fix $u\in C$ with $u\neq a$ and let $c$ be the child of $a$ on the path toward $u\text{.}$ Not all of $C$ lies in the subtree $T_{c}\text{,}$ since $c$ would then be a common ancestor of $C$ deeper than $a\text{;}$ fix $v\in C\setminus T_{c}\text{.}$ The meet $u\wedge v$ is at least as deep as $a\text{,}$ the latter being a common ancestor of $u$ and $v\text{;}$ and it is not deeper, since an ancestor of $u$ strictly below $a$ lies in $T_{c}\text{,}$ and $u\wedge v\in T_{c}$ would force $v\in T_{c}\text{.}$ Hence $u\wedge v=a\text{,}$ so the path from $u$ to $v$ passes through $a\text{,}$ and by Lemma 2.2(1),

the indicators $p_{u}$ and $p_{v}$ lying in one ball of radius $\varepsilon\text{.}$ The bound holds trivially at $u=a\text{,}$ so $a$ ancestor-covers every vertex of $C$ within distance $r\text{.}$ Every vertex of $T$ lies in the captured set of some ball, so collecting one such ancestor per ball yields an ancestor $r$-net, of size at most the number of balls; the number of balls is the size of the separated subset, and every ancestor $r$-net has at least $N^{\uparrow}_{T}(r)$ elements, which proves the bound. ∎

Two facts about Gaussian shifts are used without further comment (Tsybakov, 2009). The Kullback–Leibler divergence between $N(\theta,\sigma^{2}I_{N})$ and $N(\theta^{\prime},\sigma^{2}I_{N})$ is $\|\theta-\theta^{\prime}\|_{2}^{2}/(2\sigma^{2})\text{.}$ Fano’s inequality in its pairwise form states that if a label is uniform on $M\geq 2$ hypotheses whose data laws satisfy $\max_{i,j}\operatorname{KL}(P_{i},P_{j})\leq\kappa\text{,}$ then every decoder based on the data errs with probability at least $1-(\kappa+\log 2)/\log M\text{.}$

Proof of Lemma 3.3.

Fix $\eta:=\tfrac{1}{10}\text{,}$ the constant of the main-text sketch, and shrink each block into its information budget:

so that $\tau_{j}\in[0,1]$ and, by hypothesis (1), the shrunken family lies in $K\text{.}$ Place the uniform product prior on $\mathbf{a}\text{.}$ Since the family lies in $K\text{,}$ the minimax risk over $K$ dominates the Bayes risk of this prior, and it suffices to bound the latter for an arbitrary estimator $\widehat{\mu}=\widehat{\mu}(Y)\text{.}$

Separation. Let $\widehat{\mathbf{a}}$ index a member of the shrunken family nearest to $\widehat{\mu}\text{,}$ ties broken by a fixed order, so that $\|\widehat{\mu}-\widetilde{\mu}_{\mathbf{a}}\|_{2}\geq\tfrac{1}{2}\|\widetilde{\mu}_{\widehat{\mathbf{a}}}-\widetilde{\mu}_{\mathbf{a}}\|_{2}$ by the triangle inequality, and write $\Delta_{j}:=g_{j}(\widehat{a}_{j})-g_{j}(a_{j})\text{,}$ blocks with $\Delta_{j}=0$ dropped. With $\rho_{ij}:=|\langle\Delta_{i},\Delta_{j}\rangle|/(\|\Delta_{i}\|_{2}\|\Delta_{j}\|_{2})\text{,}$ hypothesis (3) gives $\sum_{j\neq i}\rho_{ij}\leq\gamma$ for every $i\text{,}$ and

the last step by $xy\leq\tfrac{1}{2}(x^{2}+y^{2})$ and the row sums. Since $\|\Delta_{j}\|_{2}\geq d_{j}$ whenever $\widehat{a}_{j}\neq a_{j}\text{,}$ pathwise

Per-block error. Fix $j$ and condition on the other labels $\mathbf{a}_{-j}\text{.}$ Under the product prior, $a_{j}$ remains uniform on $\mathcal{A}_{j}\text{,}$ and subtracting the known vector $\mu_{0}+\sum_{i\neq j}\tau_{i}g_{i}(a_{i})$ from $Y$ reduces the conditional problem to testing the finite Gaussian family $\{\tau_{j}g_{j}(a):a\in\mathcal{A}_{j}\}\text{,}$ whose pairwise Kullback–Leibler divergences are at most $\tau_{j}^{2}D_{j}^{2}/(2\sigma^{2})\leq\eta h_{j}/2\text{.}$ If $|\mathcal{A}_{j}|\geq 3\text{,}$ Fano’s inequality gives every decoder error probability at least $1-\eta/2-\log 2/\log|\mathcal{A}_{j}|\geq 1-\tfrac{1}{20}-\log 2/\log 3>\tfrac{1}{4}\text{.}$ If $|\mathcal{A}_{j}|=2\text{,}$ then $D_{j}=d_{j}$ and the two means are at distance $\tau_{j}D_{j}\leq\sigma\sqrt{\eta\log 2}\text{;}$ the likelihood-ratio test is optimal and projects the data onto the difference of the means; its two conditional errors are equal, and the Bayes error is

where $\Phi_{\mathcal{N}}$ is the standard normal distribution function, whose density is at most $1/\sqrt{2\pi}\text{.}$ In either case, every decoder of $a_{j}$ that is measurable in $Y$ is, conditionally on $\mathbf{a}_{-j}\text{,}$ a decoder of the reduced problem, so $\mathbb{P}(\widehat{a}_{j}\neq a_{j})\geq\tfrac{1}{4}\text{.}$

Assembly. Taking expectations in the separation bound,

and by the definition of $\tau_{j}$ and hypothesis (2),

so the Bayes risk of the prior is at least $c_{A}(1-\gamma)\sum_{j}\min\{d_{j}^{2},\sigma^{2}h_{j}\}$ with $c_{A}:=\eta/(16A)=1/(160A)\text{.}$

The restricted loss. When every contrast is supported in the coordinate set $S\text{,}$ choose $\widehat{\mathbf{a}}$ nearest to $\widehat{\mu}$ in the norm restricted to $S\text{.}$ The differences $(\widetilde{\mu}_{\widehat{\mathbf{a}}}-\widetilde{\mu}_{\mathbf{a}})|_{S}=\sum_{j}\tau_{j}\Delta_{j}$ are unchanged, since the contrasts live in $S\text{,}$ so the separation bound holds for $\|(\widehat{\mu}-\widetilde{\mu}_{\mathbf{a}})|_{S}\|_{2}^{2}\text{;}$ and the per-block bound applies to any decoder measurable in the full data $Y\text{,}$ in particular to this one. The assembly is identical. ∎

The assembly across groups in Proposition 3.4 rests on the fact that coordinate-disjoint blocks contribute additively to the Bayes risk.

Proof.

The squared loss dominates the sum of its restrictions to the disjoint sets: $\|\widehat{\mu}-\mu_{\boldsymbol{\theta}}\|_{2}^{2}\geq\sum_{i}\|(\widehat{\mu}-\mu_{\boldsymbol{\theta}})|_{S_{i}}\|_{2}^{2}\text{.}$ Fix $i\text{.}$ For $\ell\neq i$ the restriction $h_{\ell}(\theta_{\ell})|_{S_{i}}$ does not depend on $\theta_{\ell}\text{:}$ two values of $\theta_{\ell}$ differ on $S_{i}$ by a contrast of block $\ell$ restricted to $S_{i}\text{,}$ which vanishes because those contrasts are supported in $S_{\ell}\text{,}$ disjoint from $S_{i}\text{.}$ Hence $\mu_{\boldsymbol{\theta}}|_{S_{i}}=c_{i}+h_{i}(\theta_{i})|_{S_{i}}$ for a fixed vector $c_{i}\text{,}$ and $Y_{S_{i}}$ is distributed as in the isolated problem. Moreover $Y_{S_{i}^{c}}$ is a function of $(\boldsymbol{\theta}_{-i},Z_{S_{i}^{c}})\text{,}$ which is independent of $(\theta_{i},Z_{S_{i}})$ under the product prior, so $Y_{S_{i}^{c}}$ is independent of the pair $(\theta_{i},Y_{S_{i}})$ and the conditional law of $\mu_{\boldsymbol{\theta}}|_{S_{i}}$ given $Y$ equals its conditional law given $Y_{S_{i}}\text{.}$ The Bayes-optimal estimate of $\mu_{\boldsymbol{\theta}}|_{S_{i}}\text{,}$ its posterior mean, is therefore a function of $Y_{S_{i}}$ alone, and $\mathbb{E}\|(\widehat{\mu}-\mu_{\boldsymbol{\theta}})|_{S_{i}}\|_{2}^{2}$ is at least the isolated Bayes risk for every estimator $\widehat{\mu}\text{.}$ Summing over $i$ completes the proof. ∎

The next lemma produces the edge-disjoint groups of the main-text sketch, with explicit comparison constants.

Proof.

Call the members of $U$ marks. Work in the minimal subtree of $T$ spanning $U\text{,}$ rooted by the orientation inherited from $T\text{,}$ and set $L:=\max\{2,\lfloor M/(4q)\rfloor\}\text{.}$

The procedure. Process the vertices in postorder, distinguishing each mark’s token, which will be assigned to at most one group, from the vertices and edges that only provide connectivity. Each vertex $v$ receives a collection of items, each a connected subgraph containing $v$ together with the unassigned tokens it carries: for every child $c$ of $v\text{,}$ the residual passed up from $c\text{,}$ extended by the edge $(v,c)\text{;}$ and, if $v$ is a mark, the one-point item $\{v\}$ carrying the token of $v\text{.}$ Insert the items into an open bin one at a time; whenever the bin first carries at least $L$ tokens, seal it: its subgraphs unite into a component, connected through $v\text{,}$ and its tokens, now permanently assigned, form the component’s mark set. After the last item, pass the union of the open bin and the bare vertex $\{v\}\text{,}$ carrying the bin’s tokens, upward as the residual of $v\text{.}$ At the root, discard the final residual.

The invariant. Sealed components and residuals are connected, being unions of items that share the vertex at which they formed. A residual carries fewer than $L$ tokens, its bin having never reached $L\text{;}$ consequently every item carries fewer than $L$ tokens, the one-point items because $L\geq 2\text{,}$ and a component seals with at least $L$ but fewer than $2L$ tokens. Each token is assigned at most once, so the mark sets $U_{i}$ are pairwise disjoint; and a token’s vertex belongs to every subgraph that carries it, so $U_{i}\subseteq U\cap\mathcal{C}_{i}\text{.}$ Finally, each edge of the spanning subtree enters the process in exactly one item and thereafter stays inside whichever bin, component, or residual that item joined; the components are therefore pairwise edge-disjoint.

Counting. Let $q^{\prime}$ be the number of sealed components; by the invariant, $|U_{i}|\in[L,2L)$ for each. Every token is either assigned at some sealing or sits in the final, discarded residual, which carries fewer than $L\text{;}$ hence

If $M\geq 12q\text{,}$ then $L=\lfloor M/(4q)\rfloor\geq 3$ and $M/(6q)\leq L\leq M/(4q)\text{,}$ since $\lfloor x\rfloor\geq x-1\geq\tfrac{2}{3}x$ for $x\geq 3\text{;}$ hence $q^{\prime}\leq M/L\leq 6q$ and $q^{\prime}>M/(2L)-\tfrac{1}{2}\geq 2q-\tfrac{1}{2}\text{,}$ so $q^{\prime}\geq 2q\geq q\text{,}$ while $|U_{i}|\in[L,2L)\subseteq[M/(6q),\,M/(2q)]\text{.}$ If $M<12q\text{,}$ then $L=2\text{:}$ every item then carries at most one token, so components seal with exactly two, and $|U_{i}|=2$ lies in $[M/(6q),M/q]$ because $2q\leq M<12q\text{.}$ For $M\geq 4$ the count gives $q^{\prime}\leq M/2\leq 6q$ and $q^{\prime}>(M-2)/4\geq M/8\geq q/4\text{;}$ for $M\in\{2,3\}\text{,}$ necessarily $q=1\text{,}$ and the procedure seals exactly one component: fewer than $4$ tokens admit at most one, and at least one seals because all unassigned tokens funnel into the bins at the root. ∎

Completion of the proof of Proposition 3.4.

Lemma S.3.2, applied with the parameter $q$ of the proposition, supplies the groups of the main-text sketch, with $q/4\leq q^{\prime}\leq 6q$ and $M/(6q)\leq M_{i}\leq M/q\text{;}$ every group receives the budget $a=V/q^{\prime}\text{.}$ Fix a group, with marked set $U_{i}$ of size $M_{i}\geq 2\text{,}$ and adopt the objects of the sketch: the radii $r_{\ell}=16^{\ell}r\text{,}$ the nested maximal separated subsets $N_{\ell}\text{,}$ the descent chain with its node weights and child counts $m_{\ell}\text{,}$ the retained levels $I\text{,}$ the alphabets $\mathcal{A}_{\ell}\text{,}$ and the masses $a_{\ell}$ with their normalizer $S\text{.}$ We verify the claims quoted there and assemble.

The hierarchy and its entropy. Maximality of $N_{\ell}$ inside $N_{\ell-1}$ means that every point of $N_{\ell-1}$ lies within $r_{\ell}$ of a point of $N_{\ell}\text{,}$ so parents can be assigned, each point of $N_{\ell}$ to itself; and once $r_{\ell}$ exceeds the diameter of $U_{i}$ an $r_{\ell}$-separated subset is a single point: the hierarchy has a top. The weight of a node is at most its number of children times the largest weight of a child, so descending along children of maximal weight from the top, whose weight is $M_{i}\text{,}$ to a leaf, whose weight is one, gives $M_{i}\leq\prod_{\ell}m_{\ell}\text{,}$ that is, $\sum_{\ell}\log m_{\ell}\geq\log M_{i}\text{.}$ Levels with $m_{\ell}=1$ contribute zero to this sum, and among the four residue classes modulo four of the remaining levels one carries at least a quarter of it; the retained class $I$ therefore has $H=\sum_{\ell\in I}h_{\ell}\geq\tfrac{1}{4}\log M_{i}\text{.}$

Separations and aspect. Distinct children $u\neq v$ of the chain node at level $\ell$ lie in $N_{\ell-1}\text{,}$ so $d_{T}(u,v)\geq r_{\ell-1}\text{;}$ both lie within $r_{\ell}$ of their parent, so $d_{T}(u,v)\leq 2r_{\ell}=32\,r_{\ell-1}\text{.}$ By Lemma 2.2(1), the contrasts $\Delta=a_{\ell}(p_{u}-p_{v})$ then satisfy $a_{\ell}^{2}r_{\ell-1}\leq\|\Delta\|_{2}^{2}\leq 32\,a_{\ell}^{2}r_{\ell-1}\text{,}$ so $d_{\ell}^{2}\geq a_{\ell}^{2}r_{\ell-1}$ and $D_{\ell}^{2}\leq 32\,a_{\ell}^{2}r_{\ell-1}\leq 32\,d_{\ell}^{2}\text{:}$ hypothesis (2) of Lemma 3.3 holds with $A=32\text{.}$

Overlap. For $\ell<\ell^{\prime}$ in $I\text{,}$ a contrast $\Delta_{\ell}$ has entries in $[-a_{\ell},a_{\ell}]$ and support of size $d_{T}(u,v)\leq 32\,r_{\ell-1}\text{,}$ by Lemma 2.2(2), so $|\langle\Delta_{\ell},\Delta_{\ell^{\prime}}\rangle|\leq 32\,r_{\ell-1}a_{\ell}a_{\ell^{\prime}}\text{,}$ and with the norm lower bounds just proved the normalized entry is at most $32\sqrt{r_{\ell-1}/r_{\ell^{\prime}-1}}=32\cdot 4^{-(\ell^{\prime}-\ell)}\text{.}$ Retained levels differ by at least four, so every row of the normalized Gram matrix sums to at most

hypothesis (3) of Lemma 3.3 holds with this $\gamma\text{.}$

Legality and scalability. With the reference points $u_{\ell}^{0}\in\mathcal{A}_{\ell}$ and $\mu_{0}:=\sum_{\ell\in I}a_{\ell}p_{u_{\ell}^{0}}\text{,}$ a blockwise-scaled member of the group family is

a leak combination with nonnegative coefficients of total mass $\sum_{\ell\in I}a_{\ell}=a\text{;}$ hypothesis (1) of Lemma 3.3 holds with $K$ the convex set of all such mass-$a$ combinations.

The allocation. Since $a_{\ell}^{2}r_{\ell-1}=a^{2}h_{\ell}/S^{2}\text{,}$

By the Cauchy–Schwarz inequality, $S^{2}\leq H\sum_{\ell\in I}r_{\ell-1}^{-1}\text{,}$ and the radii grow geometrically, so $\sum_{\ell\in I}r_{\ell-1}^{-1}\leq r^{-1}\sum_{i\geq 0}16^{-i}=16/(15r)\leq 2/r\text{;}$ hence $a^{2}/S^{2}\geq a^{2}r/(2H)$ and

using $H\geq\tfrac{1}{4}\log M_{i}\text{.}$

Assembly. The contrasts of the group join members of $U_{i}\subseteq\mathcal{C}_{i}\text{,}$ and the connecting paths run inside the connected subtree $\mathcal{C}_{i}\text{,}$ so all group contrasts are supported in the set $S_{i}$ of lower endpoints of the edges of $\mathcal{C}_{i}$ (Lemma 2.2(2)). Lemma 3.3, in its restricted-loss form with $A=32$ and $\gamma=64/255\text{,}$ therefore bounds the Bayes risk of the shrunken group family, for every estimator measurable in the full data, below by

by the aspect and allocation bounds above. Sums of one shrunken member per group are legal points of $\mathcal{F}_{V}(T)\text{,}$ as verified in the main body; the sets $S_{i}$ are pairwise disjoint, the $E(\mathcal{C}_{i})$ being disjoint and distinct edges having distinct lower endpoints; and the prior is a product across groups. Lemma S.3.1 therefore bounds the joint Bayes risk below by the sum of the isolated group risks, and each isolated problem is, after subtracting its fixed vector, the group problem observed through $Y_{S_{i}}$ alone, so its Bayes risk also dominates the displayed bound. Hence

Finally, $a=V/q^{\prime}\geq V/(6q)\text{,}$ and $\log M_{i}\geq\tfrac{1}{7}\log(eM/q)\text{:}$ if $M/q\geq 36\text{,}$ then with $x:=\log(M/q)\text{,}$ $\log M_{i}\geq\log(M/(6q))=x-\log 6$ and $5(x-\log 6)-(1+x)=4x-5\log 6-1\geq 4\log 36-5\log 6-1=3\log 6-1>0\text{,}$ so the ratio to $\log(eM/q)=1+x$ is at least $\tfrac{1}{5}\text{;}$ if $M/q<36\text{,}$ then $\log M_{i}\geq\log 2$ and $\log(eM/q)<1+\log 36\text{,}$ and $7\log 2>4.8>1+\log 36\text{.}$ Therefore

which is the claim. ∎

The reduction of Proposition 3.5 rests on a scalar matching of the free parameter $q$ to the profile; the constant $8$ below is the one priced into $A_{0}=18\cdot 8=144\text{.}$

Proof.

Write $B:=1+L$ and note $M\geq 2\text{.}$ There are three cases.

Case $L\geq k\text{.}$ Take $q:=1\text{,}$ which equals $\max\{1,k/B\}$ since $k/B<1\text{.}$ The hypothesis reads $V^{2}r\geq 8\sigma^{2}k\text{,}$ and $\sigma^{2}\log(eM)=\sigma^{2}(1+\log M)\geq\sigma^{2}(1+L)\geq\sigma^{2}k\text{,}$ so both branches are at least $\sigma^{2}k\text{.}$

Case $L<k$ and $M\geq 8k/B\text{.}$ Take $q:=\max\{1,\lfloor k/B\rfloor\}\text{.}$ Then $k/(2B)\leq q\leq 2k/B\text{:}$ if $k\geq B$ this is $\lfloor x\rfloor\in[x/2,x]$ at $x=k/B\geq 1\text{;}$ if $k<B\text{,}$ then $q=1\text{,}$ and $k/(2B)<\tfrac{1}{2}<1\leq 2k/B$ because $B=1+L<1+k\leq 2k\text{.}$ Also $q\leq 2k/B\leq M/4<M/2$ by the case hypothesis. The hypothesis of the lemma reads $V^{2}rL/k\geq 8\sigma^{2}k\text{,}$ so

For the entropy branch, $M=ke^{L}$ and $q\leq 2k/B$ give $eM/q\geq\tfrac{e}{2}\,Be^{L}\text{,}$ so

since $0.7(1+L)+\log(1+L)\geq 0.7>\log 2\text{;}$ hence $\sigma^{2}q\log(eM/q)\geq\sigma^{2}\,\tfrac{k}{2B}\cdot 0.3B=0.15\,\sigma^{2}k\text{.}$

Case $L<k$ and $M<8k/B\text{.}$ Take $q:=\lfloor M/2\rfloor\text{,}$ so $M/3\leq q\leq M/2\text{;}$ and $q$ is comparable to $\max\{1,k/B\}\text{,}$ since $k<M<8k/B$ forces $B<8\text{,}$ whence $q\geq(M-1)/2\geq k/2$ and $q<4k/B\leq 4k\text{.}$ The entropy branch has $\log(eM/q)\geq\log(2e)>1\text{,}$ so $\sigma^{2}q\log(eM/q)\geq\sigma^{2}M/3>\sigma^{2}k/3\text{;}$ and the mass branch, using $k/M>B/8$ and $B>L\text{,}$

In every case the minimum is at least $0.15\,\sigma^{2}k\geq\sigma^{2}k/7\text{.}$ ∎

Completion of the proof of Proposition 3.5.

The main text reduces the proposition to the following situation: an integer $k\geq 1\text{,}$ and $M\geq N^{\uparrow}_{T}(r)>k$ vertices with pairwise tree distances at least $r^{\prime}:=r/9\text{,}$ where

the term at $(r^{\prime},M)$ is at least one ninth of the term at $(r,N^{\uparrow}_{T}(r))\text{,}$ since $r^{\prime}=r/9$ and enlarging the count only increases the positive part. With $L:=\log(M/k)>0$ this is the hypothesis of Lemma S.3.3. Its conclusion returns an integer $1\leq q\leq M/2\text{,}$ comparable to $\max\{1,k/(1+\log(M/k))\}$ as asserted in the main body, with $\min\{V^{2}r^{\prime}/q,\ \sigma^{2}q\log(eM/q)\}\geq\sigma^{2}k/7\text{.}$ Proposition 3.4, applied to the $M$ separated vertices with this $q\text{,}$ gives $R^{*}_{T}(V,\sigma)\geq(c/7)\,\sigma^{2}k$ with $c$ the constant of that proposition, which proves Proposition 3.5. ∎

Section 3.3 assembles the two halves. We next record its two-point bound, the deferred comparisons from three of the four cases, and the fixed-point conclusion. First, the generic bound (3.6) rests on the oracle inequality for least squares over a finite set of candidates. The inequality is classical, and belongs to the Gaussian model selection theory of Birgé and Massart (2001) and Massart (2007); we give the short proof so that its constants are explicit.

Proof.

Let $f^{\star}$ attain the minimum and $a:=\|f^{\star}-\mu\|_{2}\text{.}$ If $|\mathcal{N}|=1$ then $\widehat{f}=f^{\star}$ and the claim is immediate, so assume $N:=|\mathcal{N}|\geq 2\text{.}$ Optimality of $\widehat{f}$ and $Y-f=(\mu-f)+\sigma Z$ give

that is, $\|\mu-\widehat{f}\|_{2}^{2}\leq a^{2}+2\sigma\langle Z,\widehat{f}-f^{\star}\rangle\text{.}$ Writing $u_{f}:=(f-f^{\star})/\|f-f^{\star}\|_{2}$ for $f\neq f^{\star}$ and $G:=\bigl[\max_{f\neq f^{\star}}\langle Z,u_{f}\rangle\bigr]_{+}\text{,}$ we get $\langle Z,\widehat{f}-f^{\star}\rangle\leq\|\widehat{f}-f^{\star}\|_{2}\,G\text{,}$ whence, with $x:=\|\widehat{f}-\mu\|_{2}$ and the triangle inequality $\|\widehat{f}-f^{\star}\|_{2}\leq x+a\text{,}$

so $x^{2}\leq 4a^{2}+6\sigma^{2}G^{2}\text{.}$ Each $\langle Z,u_{f}\rangle$ is standard normal, so $\mathbb{P}(G>s)\leq\min\{1,Ne^{-s^{2}/2}\}$ and, splitting the integral $\mathbb{E}G^{2}=\int_{0}^{\infty}2s\,\mathbb{P}(G>s)\,ds$ at $s_{0}:=\sqrt{2\log N}\text{,}$

Combining the two displays proves the lemma. ∎

Completion of Theorem 1 and Proposition 1.

For the two-point bound, pick $u,w$ at tree distance $H_{T}\text{.}$ The segment from $Vp_{u}$ to $Vp_{w}$ lies in $\mathcal{F}_{V}(T)$ and has length $V\sqrt{H_{T}}$ by Lemma 2.2(1), so it contains two points at distance

Testing one against the other is a one-dimensional Gaussian shift of size $\varrho/\sigma\leq 1\text{,}$ so under the uniform prior on the pair every test errs with probability at least a universal constant. For any estimator, decoding the nearer of the two points errs only when the squared loss is at least $\varrho^{2}/4\text{;}$ hence the maximum of the two risks is at least $c\varrho^{2}\text{,}$ which is the display (3.8).

Case $n<C_{\star}\text{.}$ By (3.8) and $\sigma^{2}\geq\sigma^{2}n/C_{\star}\text{,}$

which is (I) and the lower half of (II); the upper half follows from (3.6), since $\rho_{T}\wedge V^{2}H_{T}\wedge\sigma^{2}n\leq C_{\star}\min\{V^{2}H_{T},\sigma^{2}\}\text{.}$

Case $k_{0}=1$ with $n\geq C_{\star}\text{.}$ The main text bounds $\rho_{T}\leq(A_{0}/\log 2)\,\sigma^{2}$ there, so

using $\rho_{T}\leq V^{2}h_{T}\leq V^{2}H_{T}$ for the second branch; with (3.8) this gives (I). For (II), $\min\{V^{2}H_{T},\sigma^{2}k_{0}\}=\min\{V^{2}H_{T},\sigma^{2}\}\text{,}$ whose lower half is (3.8) and whose upper half is $R^{*}_{T}\leq C\rho_{T}\wedge CV^{2}H_{T}\leq C^{\prime}\min\{\sigma^{2},V^{2}H_{T}\}$ by (3.6).

Case $k_{0}=K+1$ with $n\geq C_{\star}\text{.}$ Here $K=\lfloor n/C_{\star}\rfloor\geq n/(2C_{\star})\text{,}$ so $\sigma^{2}k_{0}=\sigma^{2}(K+1)$ lies between $\sigma^{2}n/(2C_{\star})$ and $2\sigma^{2}n/C_{\star}\text{,}$ while $V^{2}H_{T}\geq V^{2}\delta_{K}>A_{0}\sigma^{2}K\geq\sigma^{2}k_{0}/2\text{.}$ Hence $\min\{V^{2}H_{T},\sigma^{2}k_{0}\}\asymp\sigma^{2}n\text{,}$ bounded below by the profile-to-risk lower bound proved in the main body and above by (3.6) through the branch $\sigma^{2}n\text{.}$

The fixed point. In the interior case $2\leq k_{0}\leq K\text{,}$ the bound (3.6) gives $\rho_{T}\geq\rho_{T}\wedge V^{2}H_{T}\wedge\sigma^{2}n\geq R^{*}_{T}/C\text{,}$ so (3.9) and (3.10) pin the fixed point itself: $c\,\sigma^{2}k_{0}\leq\rho_{T}\leq C\,\sigma^{2}k_{0}\text{.}$ ∎

This section proves Corollaries 1, 2, and 3, together with the broom profile bounds (5.8) and the remaining computations deferred from the broom lower bound of Section 5: the objective cap, the probability of the forcing event, the broom’s covering counts, and the crossing that pins its minimax rate. By Theorem 1 the minimax risk is $\min\{V^{2}H_{T},\sigma^{2}k_{0}\}$ up to universal constants, so each corollary reduces to pinning the covering counts and the profile with explicit constants, localizing $k_{0}\text{,}$ and identifying the active branch in every parameter regime. Throughout, $K:=\lfloor n/C_{\star}\rfloor$ with $C_{\star}=e^{2}\text{;}$ the dimension clause of (1.5) holds at $K+1\text{,}$ so $1\leq k_{0}\leq K+1$ on every tree. In the corollary proofs, $W:=V/\sigma\text{.}$

On the path, ancestor covering is interval covering, and the exact counts it yields reduce the profile to one scalar optimization.

Proof.

Index the vertices by depth $0,\dots,L\text{.}$ The ancestors of $u$ are $0,\dots,u\text{,}$ so a center $a$ covers exactly the vertices $a,\dots,\min\{a+q,L\}\text{:}$ ancestor $q$-nets are coverings of $L+1$ points by blocks of $q+1$ consecutive integers anchored at their left endpoints. The centers $j(q+1)\text{,}$ $0\leq j\leq\lfloor L/(q+1)\rfloor\text{,}$ form such a covering, and there are $\lfloor L/(q+1)\rfloor+1=\lceil(L+1)/(q+1)\rceil$ of them; no net is smaller, because each center covers at most $q+1$ of the $L+1$ vertices and net sizes are integers.

Upper bound. Consider a radius $q$ whose term in the discrete formula (2.3) is nonzero, so that $N^{\uparrow}_{T}(q)>k\geq 1\text{;}$ then $\lceil(L+1)/(q+1)\rceil\geq 2$ forces $(L+1)/(q+1)>1\text{,}$ whence $N^{\uparrow}_{T}(q)<(L+1)/(q+1)+1<2(L+1)/(q+1)\text{.}$ With $y:=q+1$ and $A:=2(L+1)/k\text{,}$ the term is therefore at most

the supremum being attained at $y=A/e\text{.}$

Lower bound. Set $x:=(L+1)/(ek)$ and $y:=\lfloor x\rfloor\text{.}$ The hypothesis $k\leq(L+1)/e^{2}$ gives $x\geq e>2\text{,}$ so $y\geq x-1\geq x/2\text{;}$ and $y\leq x\leq(L+1)/e\leq L\text{,}$ so $q:=y-1$ is an admissible radius. Then $N^{\uparrow}_{T}(q)=\lceil(L+1)/y\rceil\geq(L+1)/y\geq ek\text{,}$ so $[\log(N^{\uparrow}_{T}(q)/k)]_{+}\geq 1$ and the term at $q$ is at least $y\min\{k,1\}=y\geq(L+1)/(2ek)\text{.}$ ∎

Proof of Corollary 1.

By Theorem 1 and $H_{P_{L}}=L\text{,}$ $R^{*}_{P_{L}}(V,\sigma)\asymp\min\{V^{2}L,\sigma^{2}k_{0}\}\text{;}$ write

for the right side of Corollary 1. Since its middle branch is the geometric interpolation $(V^{2}L)^{1/3}(\sigma^{2})^{2/3}\text{,}$ every branch of $F\text{,}$ and hence $F$ itself, dominates $\min\{V^{2}L,\sigma^{2}\}\text{.}$ Here $K=\lfloor(L+1)/e^{2}\rfloor\text{,}$ and there are three cases.

Case $k_{0}=1\text{.}$ Here $\min\{V^{2}L,\sigma^{2}k_{0}\}=\min\{V^{2}L,\sigma^{2}\}\text{,}$ which $F$ dominates; and since $F\leq V^{2}L\text{,}$ the matching upper bound needs an argument only when $\sigma^{2}<V^{2}L\text{.}$ By (1.5), $k_{0}=1$ means $L+1<e^{2}$ or $V^{2}\delta_{1}\leq A_{0}\sigma^{2}\text{.}$ In the first case $F\leq\sigma^{2}(L+1)<e^{2}\sigma^{2}\text{.}$ Otherwise $L+1\geq e^{2}\text{,}$ so Lemma S.4.1 applies at $k=1$ and gives $\delta_{1}=\alpha_{1}\geq(L+1)/(2e)\text{,}$ whence $F\leq V^{2}L\leq 2e\,V^{2}\delta_{1}\leq 2eA_{0}\sigma^{2}\text{.}$

Case $2\leq k_{0}\leq K\text{.}$ By minimality no clause of (1.5) holds below $k_{0}\text{,}$ while at $k_{0}$ the crossing clause holds, the dimension clause being silent there. Lemma S.4.1 is available on all of $[1,K]\text{,}$ since $K\leq(L+1)/e^{2}\text{,}$ and with

the crossing inequalities at $k_{0}$ and $k_{0}-1$ read

that is, $k_{0}^{3}\geq\kappa^{3}/2$ and $(k_{0}-1)^{3}<2\kappa^{3}\text{;}$ since $k_{0}\geq 2$ gives $k_{0}\leq 2(k_{0}-1)\text{,}$

Hence $\sigma^{2}k_{0}\asymp\sigma^{2}\kappa\asymp V^{2/3}\sigma^{4/3}L^{1/3}\text{,}$ the middle branch of $F\text{,}$ using $L\leq L+1\leq 2L\text{.}$ That branch is the least of the three up to constants: failure of the crossing clause at $k=1$ gives $A_{0}\sigma^{2}<V^{2}\delta_{1}\leq 4V^{2}L/e\text{,}$ so $\sigma^{2}\leq CV^{2}L$ and the middle branch is at most $(V^{2}L)^{1/3}(CV^{2}L)^{2/3}=C^{2/3}V^{2}L\text{;}$ and it is $\asymp\sigma^{2}k_{0}\leq\sigma^{2}K\leq\sigma^{2}(L+1)\text{.}$ Therefore $F\asymp\sigma^{2}k_{0}\text{,}$ and the same middle-branch bound gives $\sigma^{2}k_{0}\leq CV^{2}L\text{,}$ so $\min\{V^{2}L,\sigma^{2}k_{0}\}\asymp\sigma^{2}k_{0}$ as well.

Case $k_{0}=K+1\geq 2\text{.}$ Then $K\geq 1\text{,}$ so $L+1\geq e^{2}\text{,}$ and no clause fired on $[1,K]\text{;}$ at $k=K\text{,}$

using $K\geq(L+1)/(2e^{2})\text{,}$ which holds because $\lfloor x\rfloor\geq x/2$ for $x\geq 1\text{.}$ Hence $V^{2}\geq c\,\sigma^{2}(L+1)^{2}$ with $c:=A_{0}/(16e^{5})\text{,}$ and both remaining branches of $F$ dominate the third: $V^{2}L\geq\tfrac{1}{2}V^{2}(L+1)\geq\tfrac{c}{2}\,\sigma^{2}(L+1)^{3}\geq\tfrac{c}{2}\,\sigma^{2}(L+1)\text{,}$ and $(V^{2}L)^{1/3}\sigma^{4/3}\geq(\tfrac{c}{2})^{1/3}\sigma^{2}(L+1)\text{.}$ Therefore $F\asymp\sigma^{2}(L+1)\text{.}$ On the other side, $(L+1)/e^{2}<K+1\leq 2(L+1)/e^{2}$ gives $\sigma^{2}k_{0}\asymp\sigma^{2}(L+1)\text{,}$ and $\min\{V^{2}L,\sigma^{2}k_{0}\}\asymp\sigma^{2}(L+1)$ as well, by $V^{2}L\geq\tfrac{c}{2}\,\sigma^{2}(L+1)\text{.}$ The three cases are exhaustive. ∎

On the star, $h_{S_{m}}=1\text{,}$ so only the count $N^{\uparrow}_{T}(0)=m+1$ remains; the profile is exact by Remark 2.1, splitting into a capped and a logarithmic phase, and the case analysis tracks which phase meets the crossing.

Proof of Corollary 2.

By Theorem 1 and $H_{S_{m}}=2\text{,}$ $R^{*}_{S_{m}}(V,\sigma)\asymp\min\{V^{2},\sigma^{2}k_{0}\}$ after absorbing the factor two; here $n=m+1\text{.}$ By Remark 2.1,

and since $k$ grows while $\ell(k)$ does not, the set $\{k\geq 1:k\leq\ell(k)\}$ is an initial segment of the integers; it contains $1\text{,}$ because $\ell(1)=\log(m+1)>1\text{,}$ and is finite, because $\ell$ vanishes beyond $m+1\text{.}$ With $\bar{k}$ its largest element, the profile has two phases:

Write

so that $F$ is the right side of Corollary 2.

Bounded stars. For any universal $m_{0}$ the corollary holds for $m\leq m_{0}$ with constants depending only on $m_{0}\text{:}$ from $1\leq k_{0}\leq K+1\leq m_{0}\text{,}$ $\min\{V^{2},\sigma^{2}k_{0}\}\asymp\min\{V^{2},\sigma^{2}\}\text{,}$ while $F\leq\min\{V^{2},\sigma^{2}m\}\leq m_{0}\min\{V^{2},\sigma^{2}\}$ and every branch of $F$ dominates $\min\{V^{2},\sigma^{2}\}\text{,}$ the middle one because $\sigma^{2}W\sqrt{\Lambda}\geq\sigma V\geq\min\{V^{2},\sigma^{2}\}\text{.}$ Now fix a universal $m_{0}$ with the following four properties for every $m\geq m_{0}$ (one may take $m_{0}=\lceil e^{10}\rceil$): (a) $\bar{k}\geq\tfrac{1}{2}\log(m+1)\text{;}$ (b) $\bar{k}+1\leq K\text{;}$ (c) $\log(m/w)\geq\tfrac{1}{2}(1+\log m)$ whenever $1\leq w\leq\sqrt{A_{0}\log(m+1)}\text{;}$ (d) $m\geq 4e^{4}(1+\log m)\text{.}$ Property (a) holds because $k^{\prime}:=\lceil\tfrac{1}{2}\log(m+1)\rceil$ satisfies $k^{\prime}+\log k^{\prime}\leq\log(m+1)$ once $m$ is large, so that $k^{\prime}\leq\ell(k^{\prime})\text{;}$ (b) and (d) compare linear with logarithmic growth; (c) is worst at $w=\sqrt{A_{0}\log(m+1)}\text{,}$ where it reads $\tfrac{1}{2}\log m\geq\tfrac{1}{2}+\tfrac{1}{2}\log(A_{0}\log(m+1))\text{.}$ We also use, unconditionally, $\bar{k}\leq\ell(\bar{k})\leq\log(m+1)\text{.}$ Assume $m\geq m_{0}\text{;}$ there are four cases in $W\text{.}$

Case $W^{2}\leq A_{0}\text{.}$ Since $\bar{k}\geq 1\text{,}$ the capped phase gives $V^{2}\delta_{1}=\sigma^{2}W^{2}\leq A_{0}\sigma^{2}\text{:}$ the crossing clause fires at once and $k_{0}=1\text{.}$ Then $\min\{V^{2},\sigma^{2}k_{0}\}\in[V^{2}/A_{0},\,V^{2}]\text{.}$ And $F\asymp V^{2}\text{:}$ it is at most $V^{2}\text{,}$ while $\sigma^{2}W\sqrt{\Lambda}\geq\sigma^{2}W\geq V^{2}/\sqrt{A_{0}}$ and $\sigma^{2}m\geq 2\sigma^{2}\geq 2V^{2}/A_{0}\text{.}$

Case $A_{0}<W^{2}\leq A_{0}\bar{k}\text{.}$ Every integer $k<W^{2}/A_{0}$ has $k<\bar{k}\text{,}$ so the capped phase gives $V^{2}\delta_{k}=\sigma^{2}W^{2}>A_{0}\sigma^{2}k\text{,}$ and $k<\bar{k}\leq K$ keeps the dimension clause silent: no clause fires below $W^{2}/A_{0}\text{.}$ At $k_{1}:=\lceil W^{2}/A_{0}\rceil\text{,}$ which is at most $\bar{k}\leq K$ because $W^{2}/A_{0}\leq\bar{k}$ and $\bar{k}$ is an integer, the bound $\delta_{k_{1}}\leq 1$ gives $V^{2}\delta_{k_{1}}\leq\sigma^{2}W^{2}\leq A_{0}\sigma^{2}k_{1}\text{.}$ Hence

so $\min\{V^{2},\sigma^{2}k_{0}\}\asymp V^{2}\text{.}$ For $F\asymp V^{2}\text{:}$ the case hypothesis and $\bar{k}\leq\log(m+1)$ give $W\leq\sqrt{A_{0}\log(m+1)}\text{,}$ so property (c) yields $\Lambda\geq\tfrac{1}{2}(1+\log m)$ and

the denominator by $\log(m+1)\leq 1+\log m\text{.}$ Also $\sigma^{2}m\geq\sigma^{2}W^{2}=V^{2}\text{,}$ since property (d) gives $m\geq A_{0}\log(m+1)\geq W^{2}\text{.}$

Case $W^{2}>A_{0}\bar{k}$ and $W<m\text{.}$ Now $W>\sqrt{A_{0}}$ and $\log(m/W)>0\text{,}$ so $\Lambda=1+\log(m/W)\text{.}$ Set

No crossing below $c_{1}\kappa\text{:}$ fix an integer $k\leq\min\{c_{1}\kappa,K\}\text{,}$ so that the dimension clause is silent at $k\text{.}$ If $k\leq\bar{k}\text{,}$ the capped phase and the case hypothesis give $V^{2}\delta_{k}=\sigma^{2}W^{2}>A_{0}\sigma^{2}\bar{k}\geq A_{0}\sigma^{2}k\text{.}$ If $\bar{k}<k\leq c_{1}\kappa\text{,}$ monotonicity of $\ell$ gives

the last step because $\log(2\sqrt{A_{0}})=\log 24>3$ and $\tfrac{3}{4}\Lambda+1\geq\tfrac{1}{2}\log\Lambda$ for every $\Lambda\geq 1\text{;}$ hence, using $A_{0}c_{1}^{2}=\tfrac{1}{4}\text{,}$

So no clause fires at $k\text{,}$ and $k_{0}>\min\{c_{1}\kappa,K\}\text{.}$ Crossing by $\lceil\kappa\rceil\text{:}$ if $\lceil\kappa\rceil\leq K\text{,}$ then $k_{1}:=\lceil\kappa\rceil$ has

so the crossing clause fires by $k_{1}$ and $k_{0}\leq\lceil\kappa\rceil\text{.}$

If $\kappa\leq K\text{:}$ then $c_{1}\kappa<k_{0}\leq\lceil\kappa\rceil\leq 2\kappa\text{,}$ using $\kappa\geq W>1\text{,}$ so $\sigma^{2}k_{0}\asymp\sigma^{2}\kappa=\sigma^{2}W\sqrt{\Lambda}\text{,}$ the middle branch of $F\text{.}$ Moreover, by property (a) and the case hypothesis,

hence $\min\{V^{2},\sigma^{2}k_{0}\}\asymp\sigma^{2}\kappa\text{,}$ and $F\asymp\sigma^{2}\kappa$ as well: the first branch is at least $6\sigma^{2}\kappa\text{,}$ and the third is at least the second because $\kappa\leq K\leq m\text{.}$ If $\kappa>K\text{:}$ then $k_{0}>\min\{c_{1}\kappa,K\}\geq c_{1}K$ and $k_{0}\leq K+1\leq 2K\text{,}$ so $\sigma^{2}k_{0}\asymp\sigma^{2}K\asymp\sigma^{2}m\text{,}$ using $K\geq(m+1)/(2e^{2})\text{.}$ Also $V^{2}>\sigma^{2}m\text{:}$ squaring $W\sqrt{\Lambda}=\kappa>K\geq m/(2e^{2})$ gives

by property (d) and $\Lambda\leq 1+\log m\text{.}$ Hence $\min\{V^{2},\sigma^{2}k_{0}\}\asymp\sigma^{2}m\text{,}$ and $F\asymp\sigma^{2}m\text{:}$ its first branch exceeds $\sigma^{2}m\text{,}$ and its second is $\sigma^{2}\kappa>\sigma^{2}K\geq\sigma^{2}m/(2e^{2})\text{.}$

Case $W\geq m\text{.}$ Then $\Lambda=1$ and $F=\sigma^{2}\min\{W^{2},W,m\}=\sigma^{2}m\text{.}$ For every integer $k\leq K\text{,}$

so $\min\{k,\ell(k)\}\geq 1$ and $V^{2}\delta_{k}\geq\sigma^{2}W^{2}/k>A_{0}\sigma^{2}k$ whenever $k<W/\sqrt{A_{0}}\text{:}$ no clause fires below $\min\{W/\sqrt{A_{0}},\,K+1\}\geq m/12\text{,}$ the first entry because $W\geq m$ and $\sqrt{A_{0}}=12\text{,}$ the second because $K+1>(m+1)/e^{2}$ and $e^{2}<12\text{.}$ Hence $m/12\leq k_{0}\leq K+1\leq m$ and $\sigma^{2}k_{0}\asymp\sigma^{2}m\text{.}$ Since $V^{2}=\sigma^{2}W^{2}\geq\sigma^{2}m^{2}\geq\sigma^{2}m\text{,}$ also $\min\{V^{2},\sigma^{2}k_{0}\}\asymp\sigma^{2}m\asymp F\text{.}$

The four cases cover $m\geq m_{0}\text{:}$ if $W\geq m$ the fourth applies, and otherwise $W^{2}\leq A_{0}\text{,}$ $A_{0}<W^{2}\leq A_{0}\bar{k}\text{,}$ and $W^{2}>A_{0}\bar{k}$ partition the range. ∎

On the complete binary tree the covering counts decay exponentially in the radius. Radius therefore trades against entropy linearly, and the profile is governed by $\log(n/k)\text{:}$ quadratic in that logarithm when the budget exceeds it, and truncated at the budget otherwise.

Proof.

Covering counts. An ancestor of a depth-$h$ leaf within distance $q$ has depth at least $h-q\text{,}$ and a vertex at depth $d\geq h-q$ has $2^{h-d}\leq 2^{q}$ leaf descendants; covering all $2^{h}$ leaves therefore needs at least $2^{h-q}$ centers. Conversely, let $R$ consist of the root together with every vertex whose depth is of the form $D_{j}:=h-q-j(q+1)\geq 0\text{,}$ $j\geq 0\text{.}$ A selected vertex covers exactly the depths $D_{j},\dots,D_{j}+q$ of its subtree; consecutive selected depths differ by $q+1\text{,}$ so the covered bands tile $\{D_{j^{*}},\dots,h\}\text{,}$ where $D_{j^{*}}$ is the smallest selected depth, and $D_{j^{*}}\leq q\text{,}$ since otherwise $D_{j^{*}}-(q+1)\geq 0$ would be selected as well; the root covers the depths below $D_{j^{*}}\text{.}$ Hence $R$ is an ancestor $q$-net, of size

Profile, upper bound. Since $2^{h+1}=n+1$ and $\log(n+1)\leq\log n+\tfrac{1}{3}$ for $n\geq 3\text{,}$ every integer $0\leq q<h$ has, with $y:=q+1\text{,}$

and $\beta+\tfrac{3}{2}\leq\tfrac{7}{4}\beta$ because $\beta\geq 2\text{.}$ Substituting $u:=y\log 2$ in the discrete formula (2.3) and writing $B:=\tfrac{7}{4}\beta\text{,}$

if $k\geq B/4$ the supremum is at most $\sup_{u}u(B-u)_{+}=B^{2}/4\text{,}$ while if $k<B/4$ the product is at most $uk\leq(B-k)k$ for $u\leq B-k\text{,}$ and at most $u(B-u)_{+}\leq(B-k)k$ beyond, since $u(B-u)_{+}$ is nonincreasing past $B/2<B-k\text{.}$

Profile, lower bound. Set $y:=\lfloor\beta/(2\log 2)\rfloor\text{.}$ From $\beta\geq 2\text{:}$ $\beta/(2\log 2)\geq 1/\log 2>1\text{,}$ so $y\geq 1$ and, halving, $y\geq\beta/(4\log 2)\text{;}$ and $y\leq\beta/(2\log 2)\leq\log n/(2\log 2)\leq(h+1)/2\leq h\text{,}$ so $q:=y-1$ is an admissible radius. At this radius,

so, using $\min\{k,\beta/2\}\geq\tfrac{1}{2}\min\{k,\beta\}\text{,}$ the term at $q$ is at least

Proof of Corollary 3.

By Theorem 1 and $H_{B_{h}}=2h\text{,}$ $R^{*}_{B_{h}}(V,\sigma)\asymp\min\{V^{2}h,\sigma^{2}k_{0}\}$ after absorbing the factor two. Write $\beta(k):=\log(n/k)\text{,}$ as in Lemma S.4.2, and

the right side of Corollary 3.

Bounded trees. For any universal $n_{0}$ the corollary holds for $n\leq n_{0}$ with constants depending only on $n_{0}\text{:}$ from $1\leq k_{0}\leq K+1\leq n_{0}\text{,}$ $\min\{V^{2}h,\sigma^{2}k_{0}\}\asymp\min\{V^{2}h,\sigma^{2}\}\text{,}$ while $F\leq\min\{V^{2}h,\sigma^{2}n\}\leq n_{0}\min\{V^{2}h,\sigma^{2}\}$ and every branch of $F$ dominates $\min\{V^{2}h,\sigma^{2}\}\text{;}$ for the middle branch, when $W\leq 1$ this is $\sigma^{2}W\Lambda\geq\log 2\cdot\sigma^{2}W^{2}h\text{,}$ using $W\geq W^{2}$ and $\Lambda\geq 1+\log n\geq h\log 2\text{,}$ and when $W>1$ it is $\sigma^{2}W\Lambda\geq\sigma^{2}\text{.}$ Now fix a universal $n_{0}$ (one may take $n_{0}=2^{7}$) such that for every $n\geq n_{0}\text{:}$ $h\leq K\text{,}$ $n\leq 2e^{2}K\text{,}$ and $\log h\leq\tfrac{\log 2}{2}\,h\text{.}$ Assume $n\geq n_{0}\text{.}$

The diameter regime $W\leq 1\text{.}$ We claim $k_{0}\geq c\,W^{2}h$ with $c:=c_{B}\log 2/(4A_{0})\text{.}$ This is trivial when $cW^{2}h<1\text{;}$ otherwise fix an integer $k\leq cW^{2}h\leq ch\text{.}$ Then

the last step because $c\leq\log 2/2\text{;}$ so Lemma S.4.2 gives

and the dimension clause is silent at $k\leq h\leq K\text{:}$ no clause fires at any $k\leq cW^{2}h\text{,}$ proving the claim. In either case $\sigma^{2}k_{0}\geq c\,V^{2}h\text{,}$ so

And $F\asymp V^{2}h\text{:}$ its first branch is $V^{2}h\text{;}$ its middle branch dominates $\log 2\cdot V^{2}h$ as above; and $\sigma^{2}n\geq\sigma^{2}h\geq V^{2}h\text{.}$ This proves the corollary for $W\leq 1\text{.}$

The entropy and dimension regimes $W>1\text{.}$ Put $\kappa:=W\Lambda\geq 1\text{.}$ First, if $\lceil\kappa\rceil\leq K\text{,}$ the crossing clause fires by $k_{1}:=\lceil\kappa\rceil\text{:}$ there $W\leq k_{1}\leq K\leq n\text{,}$ so $\beta(k_{1})\leq\log(n/W)\leq\Lambda\text{,}$ and Lemma S.4.2 gives

hence $k_{0}\leq\lceil\kappa\rceil$ whenever $\lceil\kappa\rceil\leq K\text{.}$ Second, with $c:=c_{B}/(8A_{0})\text{,}$ no clause fires at any integer $k\leq\min\{c\kappa,K\}\text{.}$ The dimension clause is silent since $k\leq K\text{.}$ For the crossing clause, note first that $\beta(k)\geq\Lambda/4\text{:}$ if $W\geq n$ this reads $\beta(k)\geq 2>\tfrac{1}{4}=\Lambda/4\text{,}$ and if $W<n\text{,}$ then $k\leq cW\Lambda$ with $c\leq 1$ gives

the first branch because $\tfrac{3}{4}\Lambda\geq 1+\log\Lambda$ for $\Lambda\geq 3\text{.}$ Now split on $\min\{k,\beta(k)\}\text{.}$ If $k\leq\beta(k)\text{,}$ then, using $k\leq cW\Lambda\leq cW^{2}\Lambda$ and $A_{0}c=c_{B}/8\text{,}$

If $k>\beta(k)\text{,}$ then

the last step because $k\leq c\kappa$ and $c=c_{B}/(8A_{0})<\sqrt{c_{B}}/(4\sqrt{A_{0}})\text{,}$ so that $k^{2}\leq c^{2}\kappa^{2}<\tfrac{c_{B}}{16A_{0}}\kappa^{2}\text{.}$ Hence $k_{0}>\min\{c\kappa,K\}\text{.}$

Combining the two tests: if $\kappa\leq K\text{,}$ then $c\kappa<k_{0}\leq\lceil\kappa\rceil\leq 2\kappa\text{,}$ so $\sigma^{2}k_{0}\asymp\sigma^{2}\kappa=\sigma^{2}\min\{W\Lambda,n\}\text{,}$ using $\kappa\leq K\leq n\text{;}$ if $\kappa>K\text{,}$ then $k_{0}>\min\{c\kappa,K\}\geq cK$ and $k_{0}\leq K+1\leq 2K\text{,}$ so $\sigma^{2}k_{0}\asymp\sigma^{2}K\asymp\sigma^{2}n\asymp\sigma^{2}\min\{W\Lambda,n\}\text{,}$ using $n\leq 2e^{2}K\text{.}$ In both regimes

which proves the corollary for $W>1\text{.}$ ∎

It remains to prove the profile bounds (5.8) for the broom $T_{L}$ of Section 5, the handle $o=v_{0},\dots,v_{L}$ with $m$ leaf children at $v_{L}\text{,}$ so that $h_{T_{L}}=L+1\text{.}$ Its ancestor-covering numbers were computed in (5.7) there: $N^{\uparrow}_{T}(0)=n\text{,}$ and $N^{\uparrow}_{T}(q)=\lceil(L+2)/(q+1)\rceil$ for integers $1\leq q\leq L\text{.}$

Proof.

By the discrete formula (2.3), with $h_{T_{L}}=L+1\text{,}$

Upper bound. The term at $q=0$ is at most $k$ and contributes at most $1$ to $\delta_{k}=\alpha_{k}/k\text{.}$ Consider $1\leq q\leq L$ with a nonvanishing term and put $y:=q+1\text{.}$ Then $\lceil(L+2)/y\rceil>k\text{,}$ hence $(L+2)/y>k\text{,}$ since a real number at most the integer $k$ has ceiling at most $k\text{;}$ consequently

and the term is at most

the supremum attained at $u=A/e\text{.}$ Hence $\alpha_{k}\leq\max\{k,\ 2(L+2)/(ek)\}\text{,}$ and dividing by $k$ proves the upper bound.

Lower bound. Set $x:=(L+2)/(ek)\text{,}$ at least $2$ in the stated range, and $y:=\lfloor x\rfloor\text{,}$ so that $y\geq 2$ and $y>x-1\geq x/2\text{.}$ The radius $q:=y-1$ lies in $[1,L]\text{:}$ $q\geq 1$ since $y\geq 2\text{,}$ and $q\leq L$ since $y\leq x\leq(L+2)/e<L+1$ for every $L\geq 1\text{.}$ Then

so $[\log(N^{\uparrow}_{T}(q)/k)]_{+}\geq 1\text{,}$ and the term at $q$ is at least $y\cdot\min\{k,1\}=y\geq x/2\text{.}$ Hence $\alpha_{k}\geq(L+2)/(2ek)\text{,}$ and dividing by $k$ proves the lower bound. ∎

Four computations from the lower-bound proof of Theorem 5 remain, in the notation fixed there: $V=L^{1/4}\text{,}$ $\sigma=1\text{,}$ $m\geq e^{20L^{5/2}}\text{,}$ and the statistics $W=\sum_{j=1}^{L}Z_{v_{j}}\text{,}$ $Q=\sum_{j=1}^{L}[Z_{v_{j}}]_{+}^{2}\text{,}$ $M=\max_{1\leq i\leq m}Z_{w_{i}}\text{.}$

The covering counts (5.7). For the lower bound, the root-to-leaf path $v_{0},\dots,v_{L},w_{1}$ has $L+2$ vertices; an ancestor center on it covers at most $j+1$ consecutive ones, and a center at any other leaf covers none of them, so $N^{\uparrow}_{T}(j)\geq\lceil(L+2)/(j+1)\rceil\text{.}$ For the upper bound, the single center $v_{L+1-j}$ covers $v_{L+1-j},\dots,v_{L}$ together with every leaf, each at distance exactly $j\text{,}$ and $\lceil(L-j+1)/(j+1)\rceil$ further centers along the prefix $v_{0},\dots,v_{L-j}$ complete an ancestor $j$-net; the total is $1+\lceil(L-j+1)/(j+1)\rceil=\lceil(L+2)/(j+1)\rceil\text{.}$

The cap (5.3). For $h_{j}\geq 0$ the handle term obeys $2Z_{v_{j}}h_{j}-h_{j}^{2}\leq[Z_{v_{j}}]_{+}^{2}\text{:}$ the left side is nonpositive when $Z_{v_{j}}\leq 0\text{,}$ and equals $Z_{v_{j}}^{2}-(h_{j}-Z_{v_{j}})^{2}$ otherwise. The leaf part is at most $2M\sum_{i}\ell_{i}\leq 2Mh_{L}\leq MV$ by (5.1), the last step because the case under consideration has $h_{L}\leq V/2\text{.}$

The forcing event $E=\{W\geq-2\sqrt{L}\}\cap\{Q\leq 2L\}\cap\{M\geq 4L^{5/4}\}$ has probability at least $\tfrac{3}{8}\text{.}$ On $E\text{,}$

the middle inequality being equivalent to $L^{-1}+4L^{-3/4}+2L^{-1/2}<3\text{,}$ whose left side is decreasing in $L$ and below $3$ at $L=4\text{;}$ so the forcing inequality (5.4) holds on $E\text{.}$ Since $W\sim N(0,L)\text{,}$ Markov’s inequality applied to $W^{2}$ gives $\mathbb{P}(W<-2\sqrt{L})\leq\tfrac{1}{4}\text{;}$ since $\mathbb{E}Q=L/2\text{,}$ by $\mathbb{E}[Z_{v_{j}}]_{+}^{2}=\tfrac{1}{2}\text{,}$ the same inequality gives $\mathbb{P}(Q>2L)\leq\tfrac{1}{4}\text{;}$ hence $\mathbb{P}\{W\geq-2\sqrt{L},\ Q\leq 2L\}\geq\tfrac{1}{2}\text{.}$ For the leaves, set $t:=4L^{5/4}$ and integrate the standard normal density, decreasing on $[t,t+t^{-1}]\text{,}$ over that interval:

the exponent being $\tfrac{1}{2}t^{2}+1+\tfrac{1}{2}t^{-2}\leq 8L^{5/2}+\tfrac{33}{32}$ by $t^{2}=16L^{5/2}\geq 16\text{.}$ Multiplying by $m\geq e^{20L^{5/2}}\text{,}$

the middle expression being increasing in $L$ and, at $L=1\text{,}$ equal to $c_{G}e^{12}\geq e^{12-33/32-3}\geq e^{7}\text{,}$ using $4\sqrt{2\pi}\leq e^{3}\text{.}$ The leaves are independent of one another, so $\mathbb{P}(M<t)=(1-\mathbb{P}(Z_{w_{1}}\geq t))^{m}\leq e^{-m\mathbb{P}(Z_{w_{1}}\geq t)}\leq\tfrac{1}{4}\text{,}$ and independent of the handle, whence $\mathbb{P}(E)\geq\tfrac{1}{2}\cdot\tfrac{3}{4}=\tfrac{3}{8}\text{.}$

The crossing index satisfies $k_{0}\asymp\sqrt{L}\text{.}$ Set $\kappa:=(V^{2}(L+2)/(2eA_{0}))^{1/3}\text{,}$ which is $\asymp\sqrt{L}$ since $V^{2}=\sqrt{L}\text{.}$ Every integer $k<\kappa$ lies in the lower-bound range of Lemma S.4.3: $(2e)^{2}\sqrt{L}\leq A_{0}(L+2)^{2}$ gives $\kappa\leq(L+2)/(2e)\text{,}$ and there $V^{2}\delta_{k}\geq V^{2}(L+2)/(2ek^{2})>A_{0}k\text{,}$ the strict inequality being $k^{3}<\kappa^{3}$ rearranged, while $n\geq e^{20L^{5/2}}$ keeps the dimension clause of (1.5) silent; hence $k_{0}\geq\kappa\text{.}$ At $k_{+}:=\lceil 4^{1/3}\kappa\rceil$ the upper bound of Lemma S.4.3 gives $V^{2}\delta_{k_{+}}\leq\max\{V^{2},2V^{2}(L+2)/(ek_{+}^{2})\}\leq A_{0}k_{+}\text{,}$ the first branch since $A_{0}k_{+}\geq A_{0}^{2/3}(2/e)^{1/3}\sqrt{L}\geq V^{2}$ and the second since $k_{+}^{3}\geq 4\kappa^{3}\text{;}$ so the crossing fires by $k_{+}$ and $\kappa\leq k_{0}\leq\lceil 4^{1/3}\kappa\rceil\text{,}$ whence $k_{0}\asymp\sqrt{L}\text{.}$ Finally $\kappa\leq(L+2)/(2e)$ gives $k_{0}\leq\lceil 4^{1/3}\kappa\rceil\leq L+3\leq\sqrt{L}\,(L+1)=V^{2}H_{T_{L}}\text{,}$ so the minimum in Theorem 1 is the information branch and $R^{*}_{T_{L}}(L^{1/4},1)\asymp k_{0}\asymp\sqrt{L}\text{.}$

This section proves the statements deferred from Sections 4.1 and 4.2: the bound on the normalizing sum of the prior, the completion of the proof of Lemma 4.1, the risk of the three elementary branches of (4.3), the correctness and cost of the exact evaluation of the aggregate (4.2), and the batched evaluation behind the instance sentence of Section 4.2, including the softly linear evaluation on stars.

Throughout, $K:=\lfloor n/C_{\star}\rfloor\text{;}$ except in the treatment of the elementary branches, $k$ is an integer with $2\leq k\leq K\text{.}$ The active support $A_{k}\text{,}$ the charges $\widetilde{\omega}\text{,}$ the code length $\Gamma\text{,}$ and the level weights $m_{j}=2^{j}$ for $0\leq j\leq J$ are those of Section 3.1; $\mathcal{X}_{k}$ is the class (4.1) of integer states of Section 4.1; and, as in Section 4.2 there, $\varphi_{v}(x)=e^{-(Y_{v}-bx)^{2}/(4\sigma^{2})}$ with the shorthand $b:=V/k\text{.}$

Proof.

The map $x\mapsto z$ is injective on state vectors, since the subtree sums $x_{v}=\sum_{u\succeq v}z_{u}$ recover $x\text{,}$ and $\Gamma(x)$ depends only on $z\text{.}$ Dropping the constraints $x_{o}=k$ and $0\leq x_{v}\leq 3k$ therefore bounds the sum by a product over the support:

the factor at $v$ being $1+e^{-2\widetilde{\omega}(v)}\cdot 2\sum_{t\geq 1}e^{-2t}\text{,}$ with $2\sum_{t\geq 1}e^{-2t}=\tfrac{2}{e^{2}-1}\text{.}$ The free level $R_{0}\text{,}$ where $\widetilde{\omega}=0\text{,}$ has $|R_{0}|\leq ke^{m_{0}}=ek$ vertices by Lemma S.2.1(2), and $\log(1+\tfrac{2}{e^{2}-1})\leq\tfrac{3}{10}\text{,}$ so it contributes at most $\tfrac{3}{10}ek<0.82\,k$ to the logarithm. The charged vertices split into the groups $G_{j}:=\{v\in A_{k}\setminus R_{0}:\ \omega(v)=m_{j}\}\subseteq R_{j}\text{,}$ $1\leq j\leq J\text{,}$ with $|G_{j}|\leq 2ke^{m_{j}}$ by Lemma S.2.1(3); since $\log(1+y)\leq y\text{,}$ their contribution is at most

using $\sum_{j\geq 1}e^{-2^{j}}<e^{-2}+e^{-4}+2e^{-8}<0.16\text{.}$ The logarithm of the product is below $0.93\,k\text{.}$ ∎

In the setting of Lemma 4.1, write

for the normalizing sum of the weights, positive and smooth on $\mathbb{R}^{N}\text{.}$

Completion of the proof of Lemma 4.1.

The Jacobian. The logarithm of a weight is $\log\pi_{f}-\|y-f\|_{2}^{2}/(4\sigma^{2})-\log\mathcal{Z}(y)\text{;}$ differentiating it in $y_{i}$ gives

that is, $\partial\widehat{\pi}_{f}/\partial y_{i}=\widehat{\pi}_{f}\,(f_{i}-\widehat{f}_{i})/(2\sigma^{2})\text{.}$ Multiplying by $f_{j}$ and summing over $f\text{,}$

the Jacobian identity of the main-text sketch; taking $i=j$ and summing,

The domain of Stein’s identity. The aggregate takes values in the convex hull of the finite set $F\text{,}$ so it is bounded; its partial derivatives are posterior covariances of coordinates of $F\text{,}$ bounded uniformly in $y\text{;}$ and both are smooth, since $\mathcal{Z}>0$ everywhere. For such a map, Stein’s identity (Stein, 1981) gives

The cancellation. At fixed $y\text{,}$ expanding $\|y-f\|_{2}^{2}$ around $\widehat{f}_{\pi}(y)$ and averaging under $\widehat{\pi}(y)$ kills the cross term, since $\sum_{f}\widehat{\pi}_{f}\,(f-\widehat{f}_{\pi})=0\text{:}$

The last sum is $2\sigma^{2}\operatorname{div}\widehat{f}_{\pi}(y)$ by Equation S.5.1, so substituting the expansion into Stein’s identity cancels the divergence terms and leaves the risk identity of the main-text sketch.

The variational bound. The relative entropy of probability vectors on $F$ is $\operatorname{KL}(\rho\,\|\,\pi):=\sum_{f}\rho_{f}\log(\rho_{f}/\pi_{f})\text{,}$ with $0\log 0:=0\text{.}$ For any such $\rho\text{,}$ inserting the definition of $\widehat{\pi}(y)$ gives the identity

so the left side is minimized exactly at $\rho=\widehat{\pi}(y)\text{.}$ Comparing the minimizer with the point mass at $f_{0}\text{,}$ and dropping the nonnegative divergence $\operatorname{KL}(\widehat{\pi}(y)\,\|\,\pi)$ from the minimum,

the pathwise bound of the main body, whose expectation completes the proof there. ∎

The elementary branches of (4.3) are next. Their analysis rests on two facts: the root-corrected observation matches $\mu(o)=V$ exactly, and $Vp_{o}$ is within $V\sqrt{h_{T}}$ of every body point.

Proof.

For every $\mu=\sum_{u}\lambda_{u}\,Vp_{u}\in\mathcal{F}_{V}(T)\text{,}$ convexity of the norm and Lemma 2.2 give $\|\mu-Vp_{o}\|_{2}\leq\max_{u}\|Vp_{u}-Vp_{o}\|_{2}=V\sqrt{h_{T}}\text{.}$

Diameter branch ($V^{2}H_{T}\leq\sigma^{2}k$). The estimator is the constant $Vp_{o}\text{,}$ so its risk is at most $V^{2}h_{T}\leq V^{2}H_{T}\text{,}$ which is the minimum under the branch condition.

Dimension branch ($V^{2}H_{T}>\sigma^{2}k$ and $k>K$). Since $k\leq K+1$ always, $k=K+1\text{,}$ and $K=\lfloor n/C_{\star}\rfloor$ gives $n<C_{\star}(K+1)=C_{\star}k\text{.}$ The root coordinate of $\widetilde{Y}$ is exact, so

and the minimum is $\sigma^{2}k$ under the branch condition.

First-budget branch ($V^{2}H_{T}>\sigma^{2}k$ and $k=1\leq K$). Here $n\geq C_{\star}\text{,}$ so $n\geq 2\text{,}$ and, as in Section 3.3, every ancestor $r$-net with $r<h_{T}$ has at least two elements: the root lies in every net and covers no deepest vertex. Hence $N^{\uparrow}_{T}(r)\geq 2$ for all $r<h_{T}\text{,}$ and letting $r\uparrow h_{T}$ in (1.4) gives $\alpha_{1}\geq h_{T}\log 2\text{.}$ The dimension clause of (2.2) is silent at $k=1\text{,}$ since $1\leq K\text{,}$ so the surrogate crossing clause fired there, $V^{2}\overline{\delta}_{1}\leq 2A_{0}\sigma^{2}\text{,}$ and with Lemma 2.3,

the minimum is $\sigma^{2}$ under the branch condition. ∎

The rest of the section evaluates the interior branch. Fix $2\leq k\leq K$ and collect the prior into local kernels: for $z\in\mathbb{Z}$ put

For a state vector $x\in\{0,\dots,3k\}^{\mathsf{V}}$ with leaks $z_{v}=x_{v}-\sum_{c\in\operatorname{ch}(v)}x_{c}\text{,}$ the product $\prod_{v}\kappa_{v}(z_{v})$ equals $e^{-2\Gamma(x)}$ when the leaks vanish off $A_{k}$ and is zero otherwise. The denominator of (4.2) is therefore the total weight $\prod_{v}\kappa_{v}(z_{v})\,\varphi_{v}(x_{v})$ of all state vectors with $x_{o}=k\text{,}$ and it is positive: the vector with $x_{o}=k$ and all other states zero has its one leak at the root, where $\widetilde{\omega}(o)=0$ because $o\in R_{0}\text{,}$ so its weight is $e^{-2k}\varphi_{o}(k)\prod_{v\neq o}\varphi_{v}(0)>0\text{.}$ In the same terms, the coefficients of the message (4.5) are

the leaks computed within $T_{v}\text{.}$

Messages are polynomials of degree at most $3k\text{,}$ but the product of many children’s messages is not, and its degree must not be allowed to grow with their number. The device is a pair representation: a polynomial $F(\zeta)=\sum_{i\geq 0}F[i]\zeta^{i}$ with nonnegative coefficients is carried as its truncation $F_{0}(\zeta):=\sum_{i\leq 3k}F[i]\zeta^{i}$ together with its tail

the evaluation of the high part at $e^{-2}\text{,}$ shifted to the cap. Messages have zero tail; tails arise along partial products of messages and stay scalars.

Proof.

For $q\leq 3k\text{,}$ $[\zeta^{q}](FG)=\sum_{i+j=q}F[i]G[j]$ involves only indices $i,j\leq 3k\text{,}$ which gives the truncation claim. In $\tau_{FG}=\sum_{i+j>3k}F[i]G[j]e^{-2(i+j-3k)}\text{,}$ partition the index pairs according to whether $i\leq 3k$ and whether $j\leq 3k\text{.}$ The low–low pairs give the first term of Equation S.5.4. The low–high pairs factor as $\sum_{i\leq 3k}F[i]e^{-2i}\cdot\sum_{j>3k}G[j]e^{-2(j-3k)}=F_{0}(e^{-2})\tau_{G}\text{,}$ the high–low pairs symmetrically, and the high–high pairs as $e^{-6k}\tau_{F}\tau_{G}\text{,}$ since $e^{-2(i+j-3k)}=e^{-2(i-3k)}e^{-2(j-3k)}e^{-6k}\text{.}$ For the cost: the single multiplication $F_{0}G_{0}$ yields all coefficients through degree $6k\text{,}$ and every remaining ingredient of Equation S.5.4, including the evaluations $F_{0}(e^{-2})$ and $G_{0}(e^{-2})\text{,}$ is $O(k)$ arithmetic on them. ∎

The recursion of Section 4.2 now takes its precise form. At each vertex the children’s messages are merged pairwise in the pair representation, and one local pass applies the observation weight and the prior kernel.

Proof.

Assignments on the subtrees of distinct children are independent, and weights multiply, so $Q_{v}[s]$ is the total weight of the assignments on the child subtrees whose states at the children sum to $s\text{;}$ here $s$ ranges over all of $\{0,1,\dots\}\text{,}$ and the pair of $Q_{v}$ is assembled by Lemma S.5.3. A state $x$ at $v$ completes such a family to an assignment on $T_{v}$ with local weight $\varphi_{v}(x)\kappa_{v}(x-s)\text{,}$ so by Equation S.5.3

If $v\notin A_{k}\text{,}$ the kernel forces $s=x\leq 3k\text{,}$ which is Equation S.5.5; child sums beyond $3k$ contribute nothing. If $v\in A_{k}\text{,}$ the kernel splits the sum at $s=x$ into $Q_{v}[x]+e^{-2\widetilde{\omega}(v)}(\psi^{-}_{x}+\psi^{+}_{x})$ with

the high child sums entering exactly through the tail. The recurrences Equation S.5.6 are immediate from the definitions; the seed $\psi^{+}_{3k}=\tau_{v}$ is the identity just displayed at $x=3k\text{.}$ Both passes cost $O(k)\text{,}$ as does applying Equation S.5.5, and the leaf base case ($Q_{v}\equiv 1$) is contained in the general one. At the root, Equation S.5.3 with $x=k$ sums the weights of all state vectors with $x_{o}=k\text{,}$ which is the denominator of (4.2). ∎

The pruning and the chain compression described in Section 4.2 modify this recursion; neither changes the posterior.

Proof.

For (1): on $T_{w}$ all kernels force $z\equiv 0\text{,}$ so leaf-up induction gives $x\equiv 0$ on $T_{w}$ for every assignment of nonzero weight; the surviving factor is $\prod_{u\in T_{w}}\kappa_{u}(0)\varphi_{u}(0)$ as claimed. A factor common to every assignment multiplies numerator and denominator of each posterior expectation alike. Since $x_{u}=0$ with posterior probability one, $\widehat{\mu}_{k}(u)=b\,\mathbb{E}_{Y}[x_{u}]=0\text{.}$

For (2): a vertex $w\in\mathcal{C}$ has $z_{w}=0$ and all of its child subtrees off the chain disjoint from $A_{k}\text{,}$ hence carrying state zero, so $x_{w}$ equals the state of its unique child toward $A_{k}\text{;}$ iterating down the chain, all these states equal $x_{c_{\mathcal{C}}}=:x\text{.}$ The chain’s likelihood factor is $\prod_{w\in\mathcal{C}}\varphi_{w}(x)\text{,}$ and expanding the exponent,

which is Equation S.5.7 after the constant is dropped. Pathwise equality of the states gives $\mathbb{E}_{Y}[x_{w}]=\mathbb{E}_{Y}[x_{c_{\mathcal{C}}}]\text{,}$ hence the coordinate claim. ∎

The forward computation of $P_{o}[k]$ is a straight-line program in the $n(3k+1)$ inputs $\varphi_{v}(x)$ whose gates are polynomial multiplications with their tail formulas Equation S.5.4, the linear recurrences Equation S.5.6, and the coordinatewise products Equation S.5.5. The reverse sweep differentiates it.

Proof.

By Equation S.5.3 at the root, $P_{o}[k]$ is a sum of monomials, one per state vector $x^{\prime}$ with $x^{\prime}_{o}=k\text{,}$ each containing the input $\varphi_{v}(x^{\prime}_{v})$ exactly once and otherwise only kernel constants and inputs at other vertices. Hence $\varphi_{v}(x)\,\partial P_{o}[k]/\partial\varphi_{v}(x)$ is the total weight of the state vectors with $x^{\prime}_{v}=x\text{,}$ so the ratio in Equation S.5.8 is the posterior probability of $\{x_{v}=x\}$ and the sum is $b\,\mathbb{E}_{Y}[x_{v}]=\widehat{\mu}_{k}(v)\text{.}$

For the cost, propagate the derivatives of $P_{o}[k]$ with respect to every intermediate quantity backward through the program, from the output to the inputs. By the chain rule, the derivative with respect to a quantity is assembled from the derivatives with respect to the quantities that consume it, so one backward pass over the acyclic program suffices; each gate is handled by the transpose of its linearization, at the cost of the gate itself. For a product of pairs, the derivative with respect to a coefficient of one factor is a correlation with the other,

one multiplication of polynomials of degree at most $6k$ after reversing the coefficient order, plus the $O(k)$ coordinatewise contributions of Equation S.5.4 through its low coefficients, its evaluations, and its tails. The transposed recurrences Equation S.5.6 run in the opposite direction in $O(k)\text{,}$ and the coordinatewise products Equation S.5.5 are differentiated in $O(k)\text{.}$ Every gate’s transpose therefore costs the order of the gate, and the sweep visits each gate once. ∎

The operation count of Theorem 2. Computing $k_{\mathrm{alg}}$ costs $O(n\log(n+1))$ operations by Lemma 2.3; the nets $S_{j}$ at the $J+1=O(\log(k+1))$ dyadic radii cost $O(n)$ each by Lemma S.1.1, and the charges $\widetilde{\omega}$ one further pass. In the interior branch, the forward computation performs, over the whole tree, fewer than $n$ products of pairs, each $O(k\log(k+1))$ by Lemma S.5.3 and the multiplication model of Section 2.1, and $O(k)$ local work at each vertex (Lemma S.5.4); the reverse sweep matches this cost (Lemma S.5.6); and assembling Equation S.5.8 at every vertex costs $O(nk)\text{.}$ Pruning and compression (Lemma S.5.5) only remove work. The elementary branches cost $O(n)$ beyond the preprocessing. Every tie break (child orders, the greedy of Lemma S.1.1, the merge order) is fixed, so the whole map $(T,V,\sigma,Y)\mapsto\widehat{\mu}$ is deterministic, and the total is

operations, since $k\leq K+1\leq n\text{:}$ the count claimed in Theorem 2, whose proof is now complete.

The remaining two lemmas support the instance sentence of Section 4.2. Sibling messages that are dilations of a common polynomial multiply in batch: the mechanism is that logarithms turn the product into power sums of the dilation parameters. Two standard consequences of fast multiplication are used (von zur Gathen and Gerhard, 2013): Newton iteration computes truncated inverses and logarithms of power series with constant term $1\text{,}$ and exponentials of those with constant term $0\text{,}$ at the cost of $O(1)$ multiplications of the same degree; and a degree-$D$ polynomial is evaluated at $d$ points in $O((D+d)\log^{2}(D+d))$ operations by a product tree.

Proof.

Write $g(\zeta):=\log F(\zeta)=\sum_{m=1}^{3k}g_{m}\zeta^{m}$ modulo $\zeta^{3k+1}\text{,}$ computable by Newton iteration since $F[0]=1\text{,}$ and let $t_{m}:=\sum_{i\leq d}\xi_{i}^{m}$ be the power sums. Then, modulo $\zeta^{3k+1}\text{,}$

because $\log F(\xi_{i}\zeta)=\sum_{m}g_{m}\xi_{i}^{m}\zeta^{m}$ and the logarithms add. The power sums come from the auxiliary polynomial $N(\zeta):=\prod_{i\leq d}(1-\xi_{i}\zeta)\text{,}$ built by a product tree, through the logarithmic-derivative identity $-\zeta N^{\prime}(\zeta)/N(\zeta)=\sum_{m\geq 1}t_{m}\zeta^{m}\text{,}$ one derivative, one truncated inversion, and one multiplication; the exponential in Equation S.5.10 is one more Newton iteration. This proves (1), and (2) is multipoint evaluation of $F$ and $F^{\prime}$ at the points $e^{-2}\xi_{i}\text{.}$ For (3), write $P:=\exp(H)$ with $H:=\sum_{m}g_{m}t_{m}\zeta^{m}\text{;}$ then $dP=P\,dH\text{,}$ so the displayed quantity, as a function of the $t_{m}\text{,}$ has

one correlation as in Equation S.5.9; and since $\xi_{i}\,\partial t_{m}/\partial\xi_{i}=m\,\xi_{i}^{m}\text{,}$ the value carried by the dilation parameter $\xi_{i}$ is the evaluation at $\xi_{i}$ of the polynomial $\sum_{m=1}^{3k}m\,g_{m}\bigl(\sum_{s\geq m}y_{s}[\zeta^{s-m}]P\bigr)\,\zeta^{m}\text{,}$ a second multipoint evaluation. Every step is a product tree, a truncated inversion, a logarithm or exponential, a correlation, or a multipoint evaluation at degree $O(k+d)\text{,}$ each within the stated bound. ∎

On the star, either the active support collapses to the root or every leaf message is a dilation of one template; in both cases the evaluation is softly linear.

Proof.

The preprocessing and the elementary branches cost $O(n\log(n+1))\text{,}$ so let the interior branch be selected, with budget $2\leq k\leq K$ and working scale $\bar{\alpha}=k\overline{\delta}_{k}\geq 2$ (Lemma S.2.1(1)). On the star, the minimum ancestor $r$-net with $r\geq 1$ is $\{o\}\text{,}$ a leaf being an ancestor only of itself, while at $r=0$ every vertex needs itself; so with $j_{0}:=\min\{j:\lfloor\bar{\alpha}/m_{j}\rfloor=0\}\text{,}$ understood as $j_{0}=J+1$ if no radius vanishes, the nets are $S_{j}=\{o\}$ for $j<j_{0}$ and $S_{j}=\mathsf{V}$ for $j\geq j_{0}\text{,}$ and $j_{0}\geq 1$ because $\lfloor\bar{\alpha}\rfloor\geq 2\text{.}$

If $j_{0}=J+1\text{,}$ then $A_{k}=\{o\}\text{:}$ the only state vector with nonzero weight has $x_{o}=k$ and all leaf states zero, the posterior is a point mass, and $\widehat{\mu}_{k}=\tfrac{V}{k}\,x=Vp_{o}$ is written in $O(n)\text{.}$

If $j_{0}\leq J\text{,}$ then $A_{k}=\mathsf{V}$ and every leaf carries the same charge $\widetilde{\omega}=m_{j_{0}}\text{.}$ Factor the local weight of leaf $v$ at state $x$ as $\varphi_{v}(x)=e^{-Y_{v}^{2}/(4\sigma^{2})}\,e^{-b^{2}x^{2}/(4\sigma^{2})}\,\xi_{v}^{x}$ with $\xi_{v}:=e^{bY_{v}/(2\sigma^{2})}\text{;}$ the first factor is common to every assignment and is dropped. By Lemma S.5.4, the message of leaf $v$ is then $F(\xi_{v}\zeta)$ for the common template

and the child product of the root is $Q_{o}(\zeta)=\prod_{v}F(\xi_{v}\zeta)\text{.}$ Lemma S.5.7(1) gives its truncation, Lemma S.5.7(2) gives $Q_{o}(e^{-2})=\prod_{v}F(e^{-2}\xi_{v})\text{,}$ and the tail follows as

exactly, from the definition of the tail. The root pass of Lemma S.5.4 then yields $P_{o}[k]$ in $O(k)$ operations.

For the marginals, $P_{o}[k]$ is a linear function of $(Q_{o}[0],\dots,Q_{o}[3k],\tau_{o})$ by Equation S.5.5 and Equation S.5.6, with coefficients computable in $O(k)\text{;}$ and every assignment’s weight carries the factor $\xi_{v}^{x_{v}}\text{,}$ so Euler differentiation gives

The derivative splits along the linear form: the low coefficients contribute one instance of Lemma S.5.7(3), with weights that combine the direct coefficients of the linear form and the term $-e^{6k-2s}$ that $Q_{o}[s]$ inherits from $\tau_{o}\text{,}$ while $Q_{o}(e^{-2})$ contributes

an $O(1)$ combination of the values from Lemma S.5.7(2), whose denominators are positive because $F$ has positive constant term and nonnegative coefficients. Then $\widehat{\mu}_{k}(v)=b\,\mathbb{E}_{Y}[x_{v}]$ at every leaf and $\widehat{\mu}_{k}(o)=V\text{.}$ All steps beyond the preprocessing cost $O((k+m)\log^{2}(k+m))\text{,}$ and $k\leq K<n$ makes this $O(n\log^{2}n)\text{.}$ ∎

Together, Lemmas S.5.7 and S.5.8 verify the instance sentence of Section 4.2: a group of sibling messages agreeing up to a dilation of the variable multiplies in batch, and on stars the entire evaluation is softly linear in $n\text{.}$

This section proves the statements deferred from Section 4.3: the selection oracle (4.8), in the weighted and random-penalty form stated there; the scale calculus for the minimax risk; the subspace approximation (4.7); the enumeration of admissible supports; the assembly of the sufficiency half of Theorem 3, including its running time; the difference statistics of Theorem 4 with their contamination bound, the concentration of the noise estimate, and the moment bookkeeping; and the noise-estimation ceiling stated at the end of Section 4.3. Throughout, $K:=\lfloor n/C_{\star}\rfloor$ and dyadic integers are powers of two; the selection constant of (4.8) is instantiated as $C_{2}:=128\text{.}$ The standard Gaussian tail bound $\mathbb{P}\bigl(N(0,\tau^{2})\geq t\bigr)\leq e^{-t^{2}/(2\tau^{2})}\text{,}$ valid for $t\geq 0\text{,}$ is used without further comment.

The selection engine comes first. The lemma below is the oracle promised with (4.8): the noise may have unequal, even zero, coordinate variances, which is how conditioning on the root observation will enter, and the penalties may be random as long as they are bracketed on an event, which is how the estimated noise scale will enter.

Proof.

The selected model is compared with one fixed model through the basic inequality of penalized least squares; a single Kraft-weighted deviation variable controls the Gaussian fluctuations over the whole collection, and the full model is handled by its own comparison.

A projection bound. Let $U\subseteq\mathbb{R}^{N}$ be a fixed subspace of dimension $d$ and $P_{U}$ the orthogonal projection onto it. For an orthonormal basis $u_{1},\dots,u_{d}$ of $U\text{,}$ the vector $(\langle Z,u_{i}\rangle)_{i\leq d}$ is centered Gaussian with covariance $\Sigma\preceq\sigma^{2}I_{d}\text{:}$ its quadratic form at $a\in\mathbb{R}^{d}$ is $\operatorname{Var}\langle Z,\sum_{i}a_{i}u_{i}\rangle\leq\sigma^{2}\|\sum_{i}a_{i}u_{i}\|_{2}^{2}=\sigma^{2}\|a\|_{2}^{2}\text{.}$ For a centered Gaussian $g$ of variance $\tau^{2}\leq\sigma^{2}\text{,}$ direct integration gives $\mathbb{E}e^{g^{2}/(4\sigma^{2})}=(1-\tau^{2}/(2\sigma^{2}))^{-1/2}\leq\sqrt{2}\text{,}$ the case $\tau^{2}=0$ included; diagonalizing $\Sigma$ and multiplying over the independent coordinates,

hence, by Markov’s inequality and $2^{1/2}\leq e\text{,}$ for every $t\geq 0\text{,}$

The deviation variable. Fix a comparison model $m_{0}\in\mathcal{M}$ and let $f_{0}\in m_{0}$ attain $a:=\operatorname{dist}(\theta,m_{0})\text{,}$ the metric projection of $\theta$ onto the closed affine set $m_{0}\text{.}$ For $m\in\mathcal{M}$ put

so that every $\nu=c_{m}+w\in m$ has $\nu-f_{0}=(c_{m}-f_{0})+w\in U_{m}\text{,}$ and define

By the projection bound and a union bound, $\mathbb{P}(Z^{*}>t)\leq\sum_{m}e^{-\Delta_{m}-t}\leq e^{-t}\text{,}$ so $\mathbb{E}Z^{*}=\int_{0}^{\infty}\mathbb{P}(Z^{*}>t)\,dt\leq 1\text{;}$ and by its definition, $\|P_{U_{m}}Z\|_{2}^{2}\leq 4\sigma^{2}(d_{m}+\Delta_{m}+Z^{*})$ for every $m$ simultaneously.

A model is selected. Suppose the minimum is attained at some $\widehat{m}\in\mathcal{M}$ with fit $\widehat{\theta}\in\widehat{m}\text{,}$ and write $d:=\widehat{\theta}-\theta\text{.}$ Expanding the basic inequality against $(m_{0},f_{0})\text{,}$ $\|Y-\widehat{\theta}\|_{2}^{2}+\operatorname{pen}(\widehat{m})\leq\|Y-f_{0}\|_{2}^{2}+\operatorname{pen}(m_{0})\text{,}$ at $Y=\theta+Z$ and combining the two cross terms into $2\langle Z,\widehat{\theta}-f_{0}\rangle$ gives

Since $\widehat{\theta}-f_{0}\in U_{\widehat{m}}\text{,}$ the inequality $2xy\leq\tfrac{1}{4}x^{2}+4y^{2}$ and the deviation variable give

By $d_{\widehat{m}}\leq D_{\widehat{m}}+D_{m_{0}}+1\text{,}$ the last term splits into $16\sigma^{2}(D_{\widehat{m}}+\Delta_{\widehat{m}})+16\sigma^{2}(D_{m_{0}}+1)+16\sigma^{2}Z^{*}\text{,}$ and on $E$ the penalty dominates its first piece: $\operatorname{pen}(\widehat{m})\geq 32\sigma^{2}(D_{\widehat{m}}+\Delta_{\widehat{m}})\text{.}$ Together with $\tfrac{1}{4}(\|d\|_{2}+a)^{2}\leq\tfrac{1}{2}\|d\|_{2}^{2}+\tfrac{1}{2}a^{2}\text{,}$ the expansion rearranges to

The full model is selected. Then $\widehat{\theta}=Y$ and $\|d\|_{2}^{2}=\|Z\|_{2}^{2}\text{,}$ while the full model’s own residual vanishes, so the basic inequality against $(m_{0},f_{0})$ reads $\operatorname{pen}(\mathrm{full})\leq\|Y-f_{0}\|_{2}^{2}+\operatorname{pen}(m_{0})\leq 2a^{2}+2\|Z\|_{2}^{2}+\operatorname{pen}(m_{0})\text{;}$ on $E$ this gives $32\sigma^{2}N\leq 2a^{2}+2\|Z\|_{2}^{2}+\operatorname{pen}(m_{0})\text{.}$ On the event $\{\|Z\|_{2}^{2}\leq 2\sigma^{2}N\}\text{,}$ where $2\|Z\|_{2}^{2}\leq 4\sigma^{2}N\text{,}$ the preceding two inequalities force $28\sigma^{2}N\leq 2a^{2}+\operatorname{pen}(m_{0})\text{,}$ hence $\|Z\|_{2}^{2}\leq 2\sigma^{2}N\leq\tfrac{1}{14}\bigl(2a^{2}+\operatorname{pen}(m_{0})\bigr)\text{.}$ On the complement, the projection bound at $U=\mathbb{R}^{N}$ gives $\mathbb{P}(\|Z\|_{2}^{2}>2\sigma^{2}N)\leq 2^{N/2}e^{-N/2}\leq e^{-N/8}\text{;}$ moreover $\mathbb{E}\|Z\|_{2}^{4}=\sum_{i}\mathbb{E}Z_{i}^{4}+\sum_{i\neq j}\mathbb{E}Z_{i}^{2}\,\mathbb{E}Z_{j}^{2}\leq 3\sigma^{4}N+\sigma^{4}N(N-1)\leq 3\sigma^{4}N^{2}\text{,}$ the coordinates being independent with fourth moments at most $3\sigma^{4}\text{,}$ so the Cauchy–Schwarz inequality gives

the map $N\mapsto Ne^{-N/16}$ being bounded.

Assembly. Combining Equation S.6.1 with the two estimates of the full-model case and using $\mathbb{E}Z^{*}\leq 1$ and the bracketing of $\operatorname{pen}(m_{0})$ on $E\text{,}$

and taking the infimum over $m_{0}$ gives the first branch of the minimum. For the second branch, compare with the full model instead: if the full model is selected, then $\mathbb{E}[\|d\|_{2}^{2}\,\mathbf{1}_{E}]\leq\mathbb{E}\|Z\|_{2}^{2}\leq\sigma^{2}N\text{;}$ if some $\widehat{m}$ is selected, the basic inequality against the full model gives $\|Y-\widehat{\theta}\|_{2}^{2}\leq\operatorname{pen}(\mathrm{full})\leq\bar{\kappa}\sigma^{2}N$ on $E\text{,}$ so $\|d\|_{2}^{2}\leq 2\|Y-\widehat{\theta}\|_{2}^{2}+2\|Z\|_{2}^{2}$ has expectation at most $(2\bar{\kappa}+2)\sigma^{2}N$ there. Taking the minimum of the two comparisons completes the proof. ∎

Three features are used below. The penalties may be random, only their bracketing on $E$ entering the argument. The coordinate variances may differ and may vanish. And a point $\nu$ is the affine model $\{\nu\}$ with $D_{m}=0\text{,}$ whose oracle value reads $\|\theta-\nu\|_{2}^{2}+\sigma^{2}(\Delta_{\{\nu\}}+1)\text{;}$ we write $w(\nu)$ for the weight of a point model. The display (4.8) is the deterministic special case: penalties $C_{2}\sigma^{2}(\dim m+\Delta_{m})$ and $C_{2}\sigma^{2}N$ satisfy the bracketing with $E$ the whole probability space and $\bar{\kappa}=C_{2}\text{.}$

The coverage argument will replace the unknown amplitude by a grid value and the unknown noise level by a rounded estimate. The next lemma prices both substitutions.

Proof.

Monotonicity in $V\text{.}$ Let $V\leq V^{\prime}\text{.}$ The translation $\iota(\mu):=\mu+(V^{\prime}-V)p_{o}$ adds $V^{\prime}-V$ to the leak at the root and changes no other leak, so it maps $\mathcal{F}_{V}(T)$ into $\mathcal{F}_{V^{\prime}}(T)$ by Lemma 2.1. Given any estimator $\widehat{\mu}^{\prime}\text{,}$ define $\widehat{\mu}(Y):=\widehat{\mu}^{\prime}\bigl(Y+(V^{\prime}-V)p_{o}\bigr)-(V^{\prime}-V)p_{o}\text{.}$ Under $\mu\in\mathcal{F}_{V}(T)\text{,}$ the shifted data $Y+(V^{\prime}-V)p_{o}$ are distributed as an observation of $\iota(\mu)\text{,}$ and $\|\widehat{\mu}-\mu\|_{2}=\|\widehat{\mu}^{\prime}(Y+(V^{\prime}-V)p_{o})-\iota(\mu)\|_{2}\text{,}$ so the risk of $\widehat{\mu}$ at $\mu$ equals the risk of $\widehat{\mu}^{\prime}$ at $\iota(\mu)\in\mathcal{F}_{V^{\prime}}(T)\text{.}$ Taking the supremum over $\mu$ and then the infimum over $\widehat{\mu}^{\prime}$ gives $R^{*}_{T}(V,\sigma)\leq R^{*}_{T}(V^{\prime},\sigma)\text{.}$

Monotonicity in $\sigma\text{.}$ Let $\sigma\leq\sigma^{\prime}$ and let $W\sim N(0,(\sigma^{\prime 2}-\sigma^{2})I_{n})$ be independent of the data. For any estimator $\widehat{\mu}^{\prime}\text{,}$ the randomized procedure $\widehat{\mu}^{\prime}(Y+W)$ has, at every $\mu\text{,}$ the risk of $\widehat{\mu}^{\prime}$ under noise level $\sigma^{\prime}\text{;}$ replacing it by its average $\widehat{\mu}(Y):=\mathbb{E}_{W}\widehat{\mu}^{\prime}(Y+W)$ only lowers the squared-error risk, by Jensen’s inequality conditionally on $Y\text{,}$ and produces a deterministic estimator. Hence $R^{*}_{T}(V,\sigma)\leq R^{*}_{T}(V,\sigma^{\prime})\text{.}$

The quadratic bounds. Scaling the observation, the parameter, and the estimator by $a>0$ turns the experiment at $(V,\sigma)$ into the experiment at $(aV,a\sigma)\text{,}$ since $\mathcal{F}_{aV}(T)=a\,\mathcal{F}_{V}(T)\text{;}$ the squared error scales by $a^{2}\text{,}$ so

For $c\geq 1\text{,}$ combining this exact identity with the monotonicity just proved gives

using $\sigma/c\leq\sigma$ and $V/c\leq V\text{.}$ ∎

Two consequences are used repeatedly. First, for every amplitude $v>0$ and every working scale $s\in[\sigma/2,4\sigma]\text{,}$ monotonicity and the quadratic bound at $c=4$ give

Second, $k_{\mathrm{alg}}(T,v,s)\leq k_{0}(T,v,s)$ by Lemma 2.3(3), and the middle term below is at most $CR^{*}_{T}(v,s)$ by Theorem 1 at $(v,s)\text{,}$ so Equation S.6.2 gives

valid for all $v>0$ and $s\in[\sigma/2,4\sigma]\text{.}$

The amplitude-free half of the candidate system rests on the subspace approximation (4.7), verified next with an explicit constant.

Proof.

Run the proof of Proposition 3.1 on the normalized signal $f:=\mu/V\text{,}$ retaining its objects: the terminal cells $L$ with masses $\lambda_{L}$ and exits $q_{L}\text{;}$ the collapse $g$ with $\|f-g\|_{2}^{2}\leq 3\bar{\alpha}/k$ by (3.4); the skeleton $g_{0}=\sum_{h\in U}b_{h}\,p_{h}\text{,}$ supported on the set $U$ consisting of $R_{0}$ and the heavy roots, with $g=g_{0}+\sum_{L}\lambda_{L}q_{L}\text{;}$ and the exit sampling, fixed at a realization with $W\leq 2k$ and $\|\sum_{L}(Z_{L}-\lambda_{L})q_{L}\|_{2}^{2}\leq 8\bar{\alpha}/k\text{.}$ Keep the skeleton unrounded and set

a real linear combination of $\{p_{v}:\ v\in U\cup\{a_{L}:Z_{L}\neq 0\}\}\text{.}$ The set $S:=\bigl(U\cup\{a_{L}:Z_{L}\neq 0\}\bigr)\setminus R_{0}$ is admissible: the heavy roots carry total activation charge below $2k$ by Lemma S.2.3(3); the selected exit roots are pairwise distinct with $\widetilde{\omega}(a_{L})\leq m(L)\text{,}$ so their charges total at most $W\leq 2k\text{;}$ and a union is charged at most the sum of its parts. Hence $\sum_{v\in S}\widetilde{\omega}(v)\leq 4k\text{.}$ Since $\nu\in\mathcal{V}_{k,S}$ and $f-\nu=(f-g)+\sum_{L}(\lambda_{L}-Z_{L})q_{L}\text{,}$

Restoring the amplitude multiplies the squared distance by $V^{2}\text{.}$ ∎

Selecting over the capped subspaces requires listing them; this is the enumeration claim of Section 4.3.

Proof.

An admissible support is a subset of $A_{k}\setminus R_{0}$ of total activation charge at most $4k\leq 9k\text{,}$ hence one of the charged parts counted in the proof of Lemma S.2.5, where the generating-function estimate bounds their number by $e^{19k}\leq e^{C_{1}k}\text{.}$ To enumerate, fix a linear order on $A_{k}\setminus R_{0}$ and run a depth-first search over subsets that appends only higher-indexed vertices and recurses only while the accumulated charge remains at most $4k\text{.}$ Every node visited by the search is an admissible support, every admissible support is visited exactly once, along the insertion order of its elements, and testing all extensions of a visited support costs $O(|A_{k}|)$ operations. ∎

The candidate system. The estimator of Theorem 3 is the penalized selection of Lemma S.6.1 over the candidates described in Section 4.3, which we now fix precisely. The system is parameterized by a working scale $s\text{,}$ equal to $\sigma$ in Theorem 3 and to the rounded noise estimate in Theorem 4. Fix a universal threshold $n_{\star}$ such that

For $n<n_{\star}$ the estimator returns $Y\text{,}$ whose risk $n\sigma^{2}\leq n_{\star}\sigma^{2}$ is absorbed by the additive $\sigma^{2}$ after enlarging the universal constant; assume $n\geq n_{\star}$ from here on, and set $k^{\star}:=\lfloor\log n/(2C_{1})\rfloor\text{,}$ so that $2\leq k^{\star}\leq K\text{.}$ Write

with $J^{+}=J^{-}:=\lceil\log_{2}(n+1)\rceil+2\text{,}$ for the root-anchored and the low-amplitude grids. Throughout, $\mathcal{X}_{k}$ is the class (4.1) of integer states of Section 4.1. The candidates are:

• •

  the subspaces $\mathcal{V}_{k,S}$ for dyadic $2\leq k\leq k^{\star}$ and admissible $S\text{,}$ with weights $\Delta_{k,S}:=(C_{1}+1)k\text{,}$ together with $\operatorname{span}(p_{o})$ at weight $1\text{;}$

• •

  the point models $\nu_{i,k,x}:=(v_{i}/k)\,x$ for $x\in\mathcal{X}_{k}$ and dyadic $2\leq k\leq K\text{,}$ at weights $w(\nu_{i,k,x}):=2\Gamma(x)+k+i+\log_{2}k+4\text{,}$ and the root points $\nu^{0}_{i}:=v_{i}\,p_{o}$ at weights $i+4\text{;}$ their low-amplitude counterparts $\nu^{-}_{j,k,x}:=(v^{-}_{j}/k)\,x$ at weights $2\Gamma(x)+k+2\log(1+j)+\log_{2}k+4\text{,}$ and $\nu^{0-}_{j}:=v^{-}_{j}\,p_{o}$ at weights $2\log(1+j)+4\text{;}$

• •

  the full model.

The penalties are $\operatorname{pen}(m):=C_{2}s^{2}(D_{m}+\Delta_{m})$ for the affine and point models, with $\Delta_{m}$ the weight just listed, and $\operatorname{pen}(\mathrm{full}):=C_{2}s^{2}n\text{.}$ The supports $A_{k}\text{,}$ the charges $\widetilde{\omega}\text{,}$ and hence $\Gamma$ and $\mathcal{X}_{k}$ depend only on $(T,k)$ (Proposition 3.1); a grid index enters only through its amplitude and its weight, and all tie breaks are fixed, so the system and its penalties are deterministic given $(Y_{o},s)\text{.}$

The weights are Kraft-summable with room to spare. For the subspaces, Lemma S.6.4 gives

For the grid family, Lemma S.5.1 gives $\sum_{x\in\mathcal{X}_{k}}e^{-2\Gamma(x)-k}\leq 1$ for every dyadic $k=2^{\ell}\text{,}$ so, once the price of the grid index is factored out, each amplitude contributes at most $1$ from its root candidate and $\sum_{\ell\geq 1}e^{-\ell}$ from its flow candidates, and

The total is below $1\text{,}$ as Lemma S.6.1 requires.

The root-anchored grid is finite, and the truth can exceed its top value only after a downward root-noise fluctuation of order $n\text{.}$ The next lemma quantifies both halves of this statement; its event $\mathcal{E}_{+}$ is the one announced in Section 4.3.

Proof.

Part (1). Since $Y_{o}=V+\sigma Z_{o}$ and $(Y_{o})_{+}\geq Y_{o}\text{,}$

If $\sigma|Z_{o}|\leq s\text{,}$ then $v_{0}=(Y_{o})_{+}+s\geq V-\sigma|Z_{o}|+s\geq V\text{,}$ so $i^{*}=0$ and $2^{i^{*}}s=s\text{.}$ If $\sigma|Z_{o}|>s$ and $i^{*}\geq 1\text{,}$ minimality gives $v_{i^{*}-1}<V\text{,}$ that is, $2^{i^{*}-1}s<V-(Y_{o})_{+}\leq\sigma|Z_{o}|\text{,}$ so $2^{i^{*}}s<2\sigma|Z_{o}|\text{;}$ and if $\sigma|Z_{o}|>s$ and $i^{*}=0\text{,}$ then $2^{i^{*}}s=s<2\sigma|Z_{o}|\text{.}$ In every case $2^{i^{*}}s\leq 2s+2\sigma|Z_{o}|\text{,}$ and $i^{*}$ is finite, the grid values increasing to infinity. Dividing by $s\geq\sigma/2$ gives $2^{i^{*}}\leq 2+4|Z_{o}|=2(1+2|Z_{o}|)\text{,}$ which is the bound on $i^{*}\text{.}$ Next, $(Y_{o})_{+}\leq V+\sigma|Z_{o}|\text{,}$ since $Y_{o}\leq V+\sigma|Z_{o}|$ and $0\leq V\text{,}$ so $v_{i^{*}}=(Y_{o})_{+}+2^{i^{*}}s\leq V+\sigma|Z_{o}|+2s+2\sigma|Z_{o}|\text{.}$ For the last pointwise claim, $v_{i^{*}}\geq Y_{o}$ because $(Y_{o})_{+}\geq Y_{o}\text{,}$ and

since $-Y_{o}=-V-\sigma Z_{o}\leq\sigma|Z_{o}|\text{.}$ In expectation, $\mathbb{E}\,i^{*}\leq 1+\log_{2}(1+2\,\mathbb{E}|Z_{o}|)\leq 3$ by concavity of $t\mapsto\log_{2}(1+2t)$ and $\mathbb{E}|Z_{o}|\leq 1\text{,}$ while $\mathbb{E}(Y_{o}-v_{i^{*}})^{2}\leq 2(2s)^{2}+18\sigma^{2}\mathbb{E}Z_{o}^{2}\leq 146\sigma^{2}\text{,}$ using $s\leq 4\sigma\text{.}$

Part (2). On $\mathcal{E}_{+}^{\,c}\text{,}$ $i^{*}>J^{+}\text{,}$ so $v_{J^{+}}<V$ and

using $2^{J^{+}}\geq 2^{\log_{2}(n+1)+2}=4(n+1)$ and $s\geq\sigma/2\text{;}$ the positive part is positive here, so it equals $-\sigma Z_{o}\text{,}$ and $Z_{o}<-2(n+1)\text{.}$

Part (3). The selected criterion value is at most the full model’s, whose fit is $Y$ itself, so $\|Y-\widehat{\mu}\|_{2}^{2}\leq\|Y-\widehat{\mu}\|_{2}^{2}+\operatorname{pen}(\widehat{m})\leq\operatorname{pen}(\mathrm{full})=C_{2}s^{2}n\text{,}$ and $\|\widehat{\mu}-\mu\|_{2}^{2}\leq 2\|\widehat{\mu}-Y\|_{2}^{2}+2\|Y-\mu\|_{2}^{2}\leq 2C_{2}s^{2}n+2\sigma^{2}\|Z\|_{2}^{2}\text{.}$ Put $a:=2(n+1)\text{.}$ By part (2) and the independence of $Z_{o}$ from the nonroot coordinates,

where $\phi_{\mathcal{N}}$ is the standard normal density, the middle step by the Gaussian tail bound and one integration by parts. With $s^{2}\leq 16\sigma^{2}$ and $n\,e^{-a^{2}/2}\leq C\text{,}$ the pathwise bound integrates to $\mathbb{E}[\|\widehat{\mu}-\mu\|_{2}^{2}\mathbf{1}_{\mathcal{E}_{+}^{c}}]\leq C\sigma^{2}\text{.}$ ∎

With the anchor in place, some grid candidate always sits close to the truth at a price the selection can afford. The lemma is stated conditionally on the root observation, matching the conditional analysis of the selection to come.

Proof.

Every candidate of anchored index $i^{*}$ has root coordinate exactly $v\text{:}$ the flow candidates because their root state is $k\text{,}$ so $\nu_{i^{*},k,x}(o)=(v/k)\,k=v\text{,}$ and the root candidates trivially. Since $v\geq V\text{,}$ the translate $\mu^{\prime}:=\mu+(v-V)p_{o}$ lies in $\mathcal{F}_{v}(T)$ by Lemma 2.1 and agrees with $\mu$ off the root, with $\mu^{\prime}(o)=v\text{;}$ hence, for every such candidate $\nu\text{,}$

Let $k_{\max}$ be the largest dyadic integer at most $K\text{,}$ defined when $K\geq 2\text{,}$ so that $2k_{\max}>K\text{.}$ There are three exhaustive cases.

Case (a): $s^{2}k^{\prime}\leq v^{2}H_{T}\text{,}$ $K\geq 2\text{,}$ and $k^{\prime}\leq k_{\max}\text{.}$ Choose the smallest dyadic $k\geq\max\{k^{\prime},2\}\text{;}$ then $k\leq 2k^{\prime}$ and $k\leq k_{\max}\leq K\text{,}$ since $k_{\max}$ is itself a dyadic integer at least $\max\{k^{\prime},2\}\text{.}$ Proposition 3.1(1), applied to $\mu^{\prime}\in\mathcal{F}_{v}(T)$ at budget $k$ and taken with the explicit constant of its error assembly in Section S.2, supplies $x^{\star}\in\mathcal{X}_{k}$ with $\Gamma(x^{\star})\leq 9k$ and

the second step by the monotonicity of $\overline{\delta}$ (Lemma 2.3(3)) and $k\geq k^{\prime}\text{,}$ the third because the dimension clause of (2.2) is silent at $k^{\prime}\leq K\text{,}$ so its surrogate crossing clause fired there: $v^{2}\overline{\delta}_{k^{\prime}}\leq 2A_{0}s^{2}k^{\prime}\text{.}$ The weight obeys

By the case hypothesis and Equation S.6.3, $s^{2}k^{\prime}=\min\{v^{2}H_{T},s^{2}k^{\prime}\}\leq CR^{*}_{T}(v,\sigma)\text{,}$ and $\sigma^{2}k^{\prime}\leq 4s^{2}k^{\prime}\text{;}$ with Equation S.6.7, the candidate’s oracle value is therefore at most $(y_{0}-v)^{2}+CR^{*}_{T}(v,\sigma)+C\sigma^{2}(1+i^{*})\text{,}$ which is Equation S.6.5.

Case (b): $v^{2}H_{T}<s^{2}k^{\prime}\text{.}$ Take the root candidate $\nu^{0}_{i^{*}}\text{,}$ whose nonroot coordinates vanish. By Equation S.6.7 and the convexity bound $\|\mu-Vp_{o}\|_{2}\leq V\sqrt{h_{T}}$ established in the proof of Lemma S.5.2,

and $V^{2}h_{T}\leq v^{2}H_{T}=\min\{v^{2}H_{T},s^{2}k^{\prime}\}\leq CR^{*}_{T}(v,\sigma)$ by Equation S.6.3. The weight is $i^{*}+4\text{,}$ so the oracle value is at most $(y_{0}-v)^{2}+CR^{*}_{T}(v,\sigma)+\sigma^{2}(i^{*}+5)\text{.}$

Case (c): $s^{2}k^{\prime}\leq v^{2}H_{T}\text{,}$ and $K\leq 1$ or $k^{\prime}>k_{\max}\text{.}$ If $K\geq 2$ and $k^{\prime}>k_{\max}\text{,}$ then $K<2k_{\max}<2k^{\prime}$ and $n<C_{\star}(K+1)\leq 2C_{\star}K<4C_{\star}k^{\prime}\text{,}$ so

by the case hypothesis and Equation S.6.3: the full-model branch of $\mathfrak{O}$ qualifies. If $K\leq 1\text{,}$ then $n<2C_{\star}\text{,}$ and $\sigma^{2}n\leq 2C_{\star}\sigma^{2}$ is absorbed by the term $\sigma^{2}(1+i^{*})$ of Equation S.6.5.

The low-amplitude bound. Let $V<s/2$ and $j^{*}\leq J^{-}\text{.}$ From $2^{j^{*}}\leq s/V<2^{j^{*}+1}\text{,}$ the amplitude $v^{-}_{j^{*}}=2^{-j^{*}}s$ lies in $[V,2V)\text{,}$ the translate $\mu+(v^{-}_{j^{*}}-V)p_{o}$ lies in $\mathcal{F}_{v^{-}_{j^{*}}}(T)$ and agrees with $\mu$ off the root, and every candidate of low-amplitude index $j^{*}$ has root coordinate exactly $v^{-}_{j^{*}}\text{,}$ so Equation S.6.7 holds with $v^{-}_{j^{*}}$ in place of $v\text{.}$ The three cases above run verbatim at the amplitude $v^{-}_{j^{*}}$ and its crossing index $k_{\mathrm{alg}}(T,v^{-}_{j^{*}},s)\text{,}$ the weight contributions $i^{*}+\log_{2}k+4$ and $i^{*}+4$ replaced by $2\log(1+j^{*})+\log_{2}k+4$ and $2\log(1+j^{*})+4\text{;}$ they yield Equation S.6.6. ∎

One computational ingredient remains before the assembly: the inner minimization of the selection criterion over an integer-state class. It is the min-plus analogue of the evaluation of Lemma S.5.4, on the same one-dimensional state and with its own overflow scalar.

Proof.

Write $b:=v/k$ and $D:=3k\text{.}$ The class is nonempty: the state vector with $x_{o}=k$ and all other states zero belongs to $\mathcal{X}_{k}\text{,}$ its one leak sitting at the root. Losses and charges are vertex-additive, and the admissible completions on the subtrees of distinct children are independent given the state at their parent, so the minimum is computed by a postorder dynamic program over one state per vertex.

As in Lemma S.5.5, every $x\in\mathcal{X}_{k}$ vanishes on a subtree disjoint from $A_{k}\text{,}$ so such a subtree contributes one state-independent constant, the sum of $Y_{w}^{2}$ over its vertices, to every candidate; and a maximal chain of vertices off $A_{k}$ with a single child subtree meeting $A_{k}$ carries one common state. Call the tree obtained by pruning the zero subtrees and contracting these chains the reduced tree. The cost of such a chain is the explicit quadratic $x\mapsto\sum_{u}(Y_{u}-bx)^{2}$ in the state $x$ at the reduced-tree vertex below it, generated in $O(k)$ operations from the chain’s length, sum, and sum of squares. Unlike its sum-product counterpart, the min-plus recursion retains these additive constants: the values $m_{v,k}$ of different candidates are later compared, so nothing may be dropped. The reduction partitions the vertices: each vertex $u$ of the reduced tree owns itself, the suppressed chain entering it, and the zero subtrees pruned at $u$ or along that chain. Write $\widehat{T}_{u}$ for the union of the blocks owned by $u$ and by its descendants in the reduced tree, so that $\widehat{T}_{o}=\mathsf{V}\text{,}$ and define at each such $u$ the table

the minimum over the state vectors $x^{\prime}\in\{0,\dots,D\}^{\widehat{T}_{u}}$ with $x^{\prime}_{u}=x$ whose leaks $z^{\prime}$ vanish off $A_{k}\text{.}$

Overflow. Child states are individually at most $D\text{,}$ but their sum is not. A partial min-plus product of child tables, with conceptual value $A(t)$ at child sum $t\geq 0\text{,}$ is carried as its truncation $A(0),\dots,A(D)$ together with the overflow scalar

the minimum of an empty set being $+\infty\text{.}$ For the min-plus convolution of two partial products, $H(q)=\min_{i+j=q}\{A(i)+B(j)\}\text{,}$ the values $H(0),\dots,H(D)$ cost $O(D^{2})$ directly, and partitioning the pairs $(i,j)$ with $i+j>D$ according to whether each index exceeds $D$ gives the exact overflow

since $A(i)+c(i-D)$ ranges over the overflowed side: for instance, $i>D$ and $j\leq D$ give $A(i)+B(j)+c(i+j-D)=[A(i)+c(i-D)]+[B(j)+cj]\text{,}$ minimized by the second block. Each merge therefore costs $O(D^{2})=O(k^{2})\text{,}$ and there are fewer than $n$ merges in the whole tree.

The local step. Let $(Q(0),\dots,Q(D),\tau_{Q})$ be the assembled child-sum table at $u\text{,}$ an empty product having $Q(0)=0\text{,}$ $Q(t)=+\infty$ for $t\geq 1\text{,}$ and $\tau_{Q}=+\infty\text{,}$ and let $\chi_{u}(x)$ be the cost of the rest of $u$’s own block: the quadratic cost of the suppressed chain entering $u\text{,}$ all of whose vertices carry the state $x\text{,}$ plus the constants of the block’s pruned subtrees, zero if the block is the singleton $\{u\}\text{.}$ If $u\notin A_{k}\text{,}$ conservation forces the child sum to equal $x\leq D\text{,}$ the overflow is irrelevant, and $m_{u}(x)=(Y_{u}-bx)^{2}+\chi_{u}(x)+Q(x)\text{.}$ If $u\in A_{k}\text{,}$ splitting on $z_{u}=0$ against $z_{u}\neq 0$ gives

including $t=x$ in the charged branch only adds the option $Q(x)+c\widetilde{\omega}(u)\text{,}$ dominated by the first branch, so the split is exact. The inner minimum is a one-dimensional distance transform, the min-plus mirror of the recurrences in Lemma S.5.4: with

one has $F(x)=\min_{t\leq x}\{Q(t)+c(x-t)\}$ and $B(x)=\min_{t\geq x}\{Q(t)+c(t-x)\}\text{,}$ the seed at $D$ covering the overflowed sums because $\min_{t>D}\{Q(t)+c(t-x)\}=\tau_{Q}+c(D-x)$ for $x\leq D\text{;}$ hence $\min_{t\geq 0}\{Q(t)+c|x-t|\}=\min\{F(x),B(x)\}\text{,}$ at cost $O(k)$ for the two passes. At the root, $x_{o}=k$ is pinned and $\widetilde{\omega}(o)=0\text{,}$ so $m_{v,k}$ is the local step evaluated at $x=k\text{.}$ Storing, at every minimum, an attaining index, an attaining block of Equation S.6.8, and an attaining overflow sum, and backtracking from the root, recovers a minimizer $x\in\mathcal{X}_{k}\text{.}$ The total is $O(k^{2})$ per merge and $O(k)$ per vertex, hence $O(nk^{2})$ operations. ∎

Completion of the proof of Theorem 3, sufficiency.

The estimator is the penalized selection of Lemma S.6.1 over the candidate system at working scale $s=\sigma\text{,}$ with penalties $C_{2}\sigma^{2}(D_{m}+\Delta_{m})$ and $C_{2}\sigma^{2}n\text{;}$ for $n<n_{\star}$ it returns $Y\text{,}$ a case already absorbed. Condition on $Y_{o}=y_{0}\text{:}$ the candidate system is deterministic, the data decompose as $Y=\widetilde{\theta}+(0,\sigma Z_{-o})$ with $\widetilde{\theta}=(y_{0},\mu_{-o})\text{,}$ the noise being centered Gaussian with independent coordinates of variances at most $\sigma^{2}\text{,}$ the root variance zero, and the penalties are deterministic, so Lemma S.6.1 applies conditionally with $E$ the whole space, $\bar{\kappa}=C_{2}\text{,}$ and $N=n\text{.}$ Since $\widetilde{\theta}-\mu=(Y_{o}-V)p_{o}\text{,}$ the pathwise root replacement

converts conditional bounds on $\|\widehat{\mu}-\widetilde{\theta}\|_{2}^{2}$ into risk bounds. Write $k_{a}:=k_{\mathrm{alg}}(T,V,\sigma)$ and $r:=\min\{V^{2}H_{T},\sigma^{2}k_{a}\}\text{;}$ by Theorem 1 and the sandwich $k_{a}\leq k_{0}\leq 2k_{a}$ of Lemma 2.3(3), $r\asymp R^{*}_{T}(V,\sigma)\text{.}$ The anchor event $\mathcal{E}_{+}$ is determined by $Y_{o}\text{.}$ Its complement contributes at most $C\sigma^{2}$ to the risk, by Lemma S.6.5(3); on $\mathcal{E}_{+}\text{,}$ taking conditional expectations in Equation S.6.9 and applying Lemma S.6.1 conditionally bounds the contribution by $C\,\mathbb{E}[\mathfrak{O}^{\prime}\,\mathbf{1}_{\mathcal{E}_{+}}]+C\sigma^{2}\text{,}$ where $\mathfrak{O}^{\prime}$ is the conditional oracle value of Lemma S.6.1, the minimum over all candidates including the subspaces. It therefore suffices to prove

There are three exhaustive regimes; in the first two the bound is pointwise.

Diameter regime: $V^{2}H_{T}\leq\sigma^{2}k_{a}\text{.}$ The model $\operatorname{span}(p_{o})$ contains $y_{0}p_{o}\text{,}$ and $\widetilde{\theta}-y_{0}p_{o}$ vanishes at the root and equals $\mu$ off it, so

by convexity as in Lemma S.5.2. Dimension and weight are one each, so $\mathfrak{O}^{\prime}\leq r+3\sigma^{2}\text{.}$

Entropy regime with small crossing: $\sigma^{2}k_{a}<V^{2}H_{T}$ and $k_{a}\leq k^{\star}/2\text{.}$ Choose the smallest dyadic $k\geq\max\{k_{a},2\}\text{,}$ so that $k\leq\max\{2k_{a},2\}\leq k^{\star}$ and $k\leq 4k_{a}\text{.}$ Since $k_{a}\leq k^{\star}/2\leq K/2\text{,}$ the dimension clause of (2.2) is silent at $k_{a}\text{,}$ so its surrogate crossing clause fired there: $V^{2}\overline{\delta}_{k_{a}}\leq 2A_{0}\sigma^{2}k_{a}\text{.}$ Lemma S.6.3 at budget $k$ and the monotonicity of $\overline{\delta}$ (Lemma 2.3(3)) give an admissible $S$ with

The root indicator $p_{o}$ lies in every profile subspace, $o$ being in $R_{0}\text{,}$ so translating an approximant of $\mu$ by $(y_{0}-V)p_{o}$ shows $\operatorname{dist}(\widetilde{\theta},\mathcal{V}_{k,S})\leq\operatorname{dist}(\mu,\mathcal{V}_{k,S})\text{.}$ With $\dim\mathcal{V}_{k,S}\leq|R_{0}|+|S|\leq(e+4)k$ and $\Delta_{k,S}=(C_{1}+1)k\text{,}$ the oracle value of this subspace is at most $44A_{0}\sigma^{2}k_{a}+C\sigma^{2}k\leq C\sigma^{2}k_{a}=Cr\text{.}$

Entropy regime with large crossing: $\sigma^{2}k_{a}<V^{2}H_{T}$ and $k_{a}>k^{\star}/2\text{.}$ Suppose first $V\geq\sigma/2\text{.}$ On $\mathcal{E}_{+}\text{,}$ Lemma S.6.5(1) with $s=\sigma$ and $\sigma/V\leq 2$ gives, pointwise,

so Lemma S.6.2, at the factor $c=v_{i^{*}}/V\geq 1\text{,}$ gives $R^{*}_{T}(v_{i^{*}},\sigma)\leq(5+6|Z_{o}|)^{2}R^{*}_{T}(V,\sigma)$ pointwise, of expectation at most $CR^{*}_{T}(V,\sigma)\text{.}$ Since $\mathfrak{O}^{\prime}\leq\mathfrak{O}\text{,}$ the infimum running over more candidates, Equation S.6.5 and Lemma S.6.5(1) together prove Equation S.6.10 in this regime. Suppose now $V<\sigma/2\text{.}$ The regime inequality and $H_{T}<n$ give $\sigma^{2}k_{a}<V^{2}H_{T}\leq V^{2}n\text{,}$ so $\sigma/V<\sqrt{n/k_{a}}\leq\sqrt{n}$ and $j^{*}=\lfloor\log_{2}(\sigma/V)\rfloor$ satisfies $1\leq j^{*}\leq\tfrac{1}{2}\log_{2}n\leq J^{-}\text{.}$ The low-amplitude bound Equation S.6.6 applies, and its three terms are handled in turn: $v^{-}_{j^{*}}\in[V,2V]$ and Lemma S.6.2 give $R^{*}_{T}(v^{-}_{j^{*}},\sigma)\leq 4R^{*}_{T}(V,\sigma)\text{;}$ the amplitude $v^{-}_{j^{*}}=2^{-j^{*}}\sigma$ is deterministic, so

using $|V-v^{-}_{j^{*}}|\leq V<\sigma/2\text{;}$ and, since $\log(1+t)\leq t$ and $k_{a}>k^{\star}/2\geq\log n/(8C_{1})$ for $n\geq n_{\star}\text{,}$

This proves Equation S.6.10 in every regime, hence the risk bound of Theorem 3.

Running time. The dyadic budgets $k\leq k^{\star}$ carry $\sum_{k}e^{C_{1}k}\leq 2e^{C_{1}k^{\star}}\leq 2\sqrt{n}$ admissible supports in total, the terms of the sum growing at least geometrically; by Lemma S.6.4 they are listed in $O(n\sqrt{n})$ operations. One $O(n\log n)$ preprocessing pass stores every vertex’s $2^{j}$-th ancestor for $j\leq\lceil\log_{2}n\rceil$ and every root-path sum of $Y\text{;}$ lifting the deeper endpoint and then both endpoints finds the deepest common ancestor of any pair in $O(\log n)$ operations, and, by the ancestor count recorded with Lemma 2.2, $\langle p_{u},p_{w}\rangle=\operatorname{depth}(u\wedge w)+1\text{,}$ while $\langle Y,p_{u}\rangle$ is the stored root-path sum at $u\text{.}$ Forming and solving the normal equations of one subspace, of dimension $O(\log n)\text{,}$ therefore costs $O(\log^{3}n)$ operations after the preprocessing, and the subspace half costs $O(n^{3/2})$ in total, up to logarithmic factors. The grid half has $O(\log n)$ amplitudes, $O(\log n)$ budgets, and, for each pair, one run of Lemma S.6.7 with $c=2C_{2}\sigma^{2}\text{:}$ the remaining weight $C_{2}\sigma^{2}(k+i+\log_{2}k+4)$ of a flow candidate is constant across $x\in\mathcal{X}_{k}\text{,}$ so the penalized criterion is minimized by the returned minimizer. With $k\leq n\text{,}$ the grid half costs $O(n^{3}\log^{2}n)$ operations, a conservative bound, and the final comparison across all candidates is dominated by it. All tie breaks are fixed, so the estimator is a deterministic function of $(T,\sigma,Y)\text{,}$ computable in polynomial time. ∎

It remains to remove the noise level; the difference statistics and their contamination bound come first. Write $\operatorname{hc}(u)$ for the size-heavy child of an internal vertex $u\text{,}$ fixed in Section 4.3, pair the children of each branching vertex by a fixed rule, one child left unpaired when their number is odd, and take

at least $(n-1)/2$ statistics in all, each a Gaussian of variance $2\sigma^{2}$ around a signal difference. For every $\varepsilon>0\text{,}$ the contamination bound announced in the main body reads

Proof of (S.6.12).

Fix $\varepsilon>0\text{.}$ Both counts rest on the identity, valid for every vertex set $B$ by the subtree sums of Lemma 2.1,

when every root path meets $B$ in at most $w$ vertices, the count on the right is at most $w\text{,}$ and the leaks total $V\text{,}$ so $\sum_{a\in B}\mu(a)\leq Vw\text{.}$

Heavy differences. Every internal vertex carries exactly one heavy edge, and every vertex is the size-heavy child of at most one vertex, its parent, so the heavy edges partition $\mathsf{V}$ into vertex-disjoint paths; the top of such a path is the root or the lower endpoint of a light edge. The flow form of Lemma 2.1 makes every mean $\mathbb{E}X_{u}=\mu(u)-\mu(\operatorname{hc}(u))$ nonnegative, and along one heavy path the means telescope to $\mu(\mathrm{top})-\mu(\mathrm{bottom})\leq\mu(\mathrm{top})\text{.}$ A root path contains at most $w_{\mathrm{lt}}$ tops, one for the root and one per light edge it crosses, so Equation S.6.13, applied to the set of tops, gives

Sibling pairs. The coordinates $\mu(c)$ of the children of a branching vertex $u$ are nonnegative, so a pair with $|\mathbb{E}X_{c,c^{\prime}}|=|\mu(c)-\mu(c^{\prime})|\geq\varepsilon\sigma$ contains a child whose coordinate is at least $\varepsilon\sigma\text{;}$ such children number at most $\mu(u)/(\varepsilon\sigma)\text{,}$ since $\sum_{c\in\operatorname{ch}(u)}\mu(c)\leq\mu(u)\text{,}$ and distinct pairs contain distinct children. Summing over the branching vertices, of which a root path contains at most $w_{\mathrm{br}}\text{,}$ and applying Equation S.6.13 to their set,

Adding the two displays gives Equation S.6.12, the width being $w_{T}=w_{\mathrm{lt}}+w_{\mathrm{br}}\text{.}$ ∎

The statistic family Equation S.6.11 has at least $(n-1)/2$ members: an internal vertex with $g$ children contributes the difference along its heavy edge together with $\lfloor g/2\rfloor$ sibling pairs, $1+\lfloor g/2\rfloor\geq(g+1)/2\text{,}$ and the child counts of the internal vertices sum to $n-1\text{.}$ Each vertex $u$ enters at most three statistics: its own difference $X_{u}$ when internal, the difference $X_{\operatorname{pa}(u)}$ when it is the size-heavy child of its parent, and at most one pair. Scan the family in a fixed order and retain every statistic both of whose coordinates are unused by the statistics retained so far: a retained statistic blocks at most four others, two through each coordinate, so at least a fifth of the family is retained. This produces a deterministic subfamily, relabeled $X_{1},\dots,X_{N}\text{,}$ with $N\geq(n-1)/10$ and pairwise disjoint coordinate pairs; the $X_{i}$ are therefore independent, with $X_{i}-\mathbb{E}X_{i}\sim N(0,2\sigma^{2})\text{.}$

Proof.

Call $X_{i}$ clean when $|\mathbb{E}X_{i}|\leq\sigma/8\text{.}$ The contamination count Equation S.6.12 at $\varepsilon=1/8\text{,}$ applied to the full family and hence to the subfamily, bounds the number of statistics that are not clean by $8Vw_{T}/\sigma\leq n/160\leq N/8\text{,}$ the last step because $N\geq(n-1)/10\geq n/20$ for $n\geq 2\text{.}$ A clean statistic satisfies, for every $t\geq 0\text{,}$

and two numerical evaluations of the standard normal distribution function give

If $\operatorname{med}|X|<\sigma/2\text{,}$ at least $\lceil N/2\rceil$ of the absolute values are below $\sigma/2\text{,}$ of which at least $N/2-N/8=3N/8$ belong to clean statistics, and each clean statistic falls below $\sigma/2$ with probability less than $0.35\text{.}$ If $\operatorname{med}|X|>9\sigma/5\text{,}$ at least $N-\lceil N/2\rceil+1\geq N/2$ of the absolute values exceed $9\sigma/5\text{,}$ at least $3N/8$ of them clean, each clean statistic exceeding $9\sigma/5$ with probability less than $0.24\text{.}$ In either case, a count of at most $N$ independent indicators, each of success probability at most a fixed $p<3/8\text{,}$ must reach $3N/8\text{.}$ For $\lambda>0\text{,}$ Markov’s inequality applied to the exponential of $\lambda$ times this count bounds the probability by $[e^{-3\lambda/8}(1-p+pe^{\lambda})]^{N}\text{,}$ each missing indicator only lowering the moment generating function below the factor $1-p+pe^{\lambda}>1\text{;}$ the bracket equals $1$ at $\lambda=0$ with derivative $p-\tfrac{3}{8}<0\text{,}$ so a fixed small $\lambda$ makes it $e^{-c}<1\text{,}$ and each probability is at most $e^{-cN}\leq e^{-c(n-1)/10}\text{;}$ renaming $c\text{,}$ the two events together have probability at most $2e^{-c(n-1)}\text{,}$ the claimed exceptional probability. On the complement of the two events, $\operatorname{med}|X|\in[\sigma/2,\,9\sigma/5]\text{;}$ since $\Phi_{\mathcal{N}}(0.6718)<\tfrac{3}{4}<\Phi_{\mathcal{N}}(0.6788)$ by a numerical evaluation, the denominator $\sqrt{2}\,\Phi_{\mathcal{N}}^{-1}(3/4)$ lies in $(0.95,\,0.96)\text{,}$ and

Completion of the proof of Theorem 4.

For $n<n_{\star}$ return $Y\text{,}$ whose risk $n\sigma^{2}\leq n_{\star}\sigma^{2}$ is absorbed as before; assume $n\geq n_{\star}\text{.}$ The estimator computes $\widehat{\sigma}\text{;}$ on the null event $\{\widehat{\sigma}=0\}$ it returns $Y\text{,}$ and otherwise it rounds upward to $\widetilde{\sigma}:=2^{\lceil\log_{2}\widehat{\sigma}\rceil}$ and runs the selection of Theorem 3 at working scale $s=\widetilde{\sigma}\text{,}$ with the weight of every subspace and point model increased by two and the penalties built from these shifted weights at scale $\widetilde{\sigma}\text{.}$ The estimator depends only on $(T,Y)\text{,}$ and its running time adds $O(n\log n)$ for the statistics and the median to the polynomial cost already accounted. We prove the risk bound with $c=1/1280$ in the regime condition.

Let $\widehat{E}:=\{\widehat{\sigma}\in[\sigma/2,2\sigma]\}\text{,}$ so that $\mathbb{P}(\widehat{E}^{c})\leq 2e^{-c(n-1)}$ by Lemma S.6.8 under the regime condition. On $\widehat{E}\text{,}$ the rounding gives $\widetilde{\sigma}\in[\sigma/2,4\sigma]\text{,}$ and $\widetilde{\sigma}$ is a power of two in that interval, hence takes at most four values determined by $\sigma\text{.}$

On $\widehat{E}\text{.}$ Condition on $Y_{o}=y_{0}\text{.}$ The realized candidate-and-penalty system is one of the four deterministic systems indexed by the possible values of $\widetilde{\sigma}\text{;}$ the subspace candidates are common to all four, while the grids differ. The penalties satisfy the bracketing of Lemma S.6.1 with respect to the true $\sigma$ on $\widehat{E}\text{:}$ with shifted weights $\Delta_{m}+2\text{,}$ since $\widetilde{\sigma}^{2}\in[\sigma^{2}/4,16\sigma^{2}]$ and $C_{2}/4=32\text{,}$

and likewise for the full model, so $E=\widehat{E}$ and $\bar{\kappa}=16C_{2}\text{.}$ The proof of Lemma S.6.1 is repeated with one change: the deviation variable is the supremum over the four systems, each paired with its own comparison model. The weight shift by two keeps the combined Kraft sum below one, since $4e^{-2}\bigl(0.53+\tfrac{1}{8}\bigr)<1$ by Equation S.6.4 and the subspace sum, so the expectation of the deviation variable is still at most one; the basic inequality is unchanged, the selected and the comparison model both lying in the realized subsystem. The conditional oracle bound of Lemma S.6.1 therefore holds on $\widehat{E}$ for the realized system.

Coverage now runs as in the completion of Theorem 3, at the realized scale $s=\widetilde{\sigma}\in[\sigma/2,4\sigma]\text{,}$ with $k_{a}(s):=k_{\mathrm{alg}}(T,V,s)$ and $r_{s}:=\min\{V^{2}H_{T},s^{2}k_{a}(s)\}\text{;}$ by Equation S.6.3, $r_{s}\leq CR^{*}_{T}(V,\sigma)$ uniformly over the four values, and the weight shift adds $2\sigma^{2}$ to every oracle value, absorbed by the additive term. In the diameter regime, the pointwise bound through $\operatorname{span}(p_{o})$ is unchanged. In the entropy regime with $k_{a}(s)\leq k^{\star}/2\text{,}$ the surrogate crossing at scale $s$ gives $V^{2}\overline{\delta}_{k_{a}(s)}\leq 2A_{0}s^{2}k_{a}(s)\text{,}$ and the subspace bound reads $22V^{2}\overline{\delta}_{k}\leq 44A_{0}s^{2}k_{a}(s)\leq Cr_{s}\text{.}$ In the entropy regime with $k_{a}(s)>k^{\star}/2\text{:}$ for $V\geq s/2\text{,}$ Lemma S.6.5(1) gives, pointwise,

using $s/V\leq 2$ and $\sigma\leq 2s\text{,}$ so Equation S.6.5, Lemma S.6.2, and Lemma S.6.5(1) give the bound $C(R^{*}_{T}(V,\sigma)+\sigma^{2})$ in expectation as before. For $V<s/2\text{,}$ the index $j^{*}=\lfloor\log_{2}(s/V)\rfloor$ again lies in $\{1,\dots,J^{-}\}\text{,}$ since $s^{2}k_{a}(s)<V^{2}H_{T}\leq V^{2}n\text{;}$ the amplitude $v^{-}_{j^{*}}=2^{-j^{*}}\widetilde{\sigma}$ now depends on the data through $\widetilde{\sigma}\text{,}$ so no independence from $Z_{o}$ is available, and the root-coordinate term of Equation S.6.6 is bounded pathwise on $\widehat{E}$ instead:

using $v^{-}_{j^{*}}\in[V,2V]$ and $V<s/2\leq 2\sigma\text{,}$ of expectation $O(\sigma^{2})\text{;}$ the weight term $\sigma^{2}\log(1+j^{*})\leq C\sigma^{2}k_{a}(s)=Cr_{s}$ as before. Finally, for every realized $s$ the omitted-anchor event is contained in $\{Z_{o}<-2(n+1)\}$ by Lemma S.6.5(2), and Lemma S.6.5(3) with $s^{2}\leq 16\sigma^{2}$ bounds its loss contribution by $C\sigma^{2}\text{.}$ Splitting along the realized anchor event and applying the pathwise root replacement Equation S.6.9 on it, as in the completion of Theorem 3, gives $\mathbb{E}[\|\widehat{\mu}-\mu\|_{2}^{2}\,\mathbf{1}_{\widehat{E}}]\leq C(R^{*}_{T}(V,\sigma)+\sigma^{2})\text{.}$

Off $\widehat{E}\text{.}$ On $\{\widehat{\sigma}=0\}$ the loss is $\sigma^{2}\|Z\|_{2}^{2}\text{.}$ On $\{\widehat{\sigma}>0\}\cap\widehat{E}^{c}\text{,}$ compare the selected criterion with $\operatorname{span}(p_{o})\text{,}$ of dimension one and shifted weight three:

so $\|\widehat{\mu}-\mu\|_{2}\leq\|\widehat{\mu}-Y\|_{2}+\|Y-\mu\|_{2}\leq 2\|Y\|_{2}+\|\mu\|_{2}+2\sqrt{C_{2}}\,\widetilde{\sigma}\text{.}$ Pathwise, $\widetilde{\sigma}\leq 2\widehat{\sigma}\leq 3\operatorname{med}|X|\leq 3\max_{i}|X_{i}|\leq 6\|Y\|_{\infty}\leq 6\|Y\|_{2}\text{,}$ each $X_{i}$ being a difference of two coordinates of $Y\text{,}$ so all losses off $\widehat{E}$ obey $\|\widehat{\mu}-\mu\|_{2}\leq C(\|Y\|_{2}+\|\mu\|_{2})\text{.}$ For the moments: $\mu(u)\leq V$ at every vertex and $\sum_{u}\mu(u)=\sum_{x}s_{x}(\operatorname{depth}(x)+1)\leq Vn$ by Lemma 2.1, so $\|\mu\|_{2}^{2}\leq V^{2}n\text{;}$ $\mathbb{E}\|Z\|_{2}^{4}\leq 3n^{2}$ gives $\mathbb{E}\|Y\|_{2}^{4}\leq 8(\|\mu\|_{2}^{4}+\sigma^{4}\mathbb{E}\|Z\|_{2}^{4})\leq 8(V^{4}n^{2}+3\sigma^{4}n^{2})\text{;}$ and the regime condition with $w_{T}\geq 1$ gives $V\leq\sigma n/1280\text{,}$ hence $V^{4}n^{2}\leq\sigma^{4}n^{6}\text{.}$ The squared loss therefore has second moment at most $C\sigma^{4}n^{6}$ off $\widehat{E}\text{,}$ and the Cauchy–Schwarz inequality gives

Adding the two contributions proves Theorem 4. ∎

The width of the benchmark families is read off the definition in Section 4.3. A path has no light edge and no branching vertex, so $w_{T}=1\text{.}$ On the complete binary tree of height $h\text{,}$ every internal vertex has one light child edge, and a root-to-leaf path may cross a light edge and a branching vertex at each of its $h$ internal levels, so $w_{T}=(1+h)+h=2h+1\text{.}$ On a star with $m\geq 2$ leaves, and on the broom of Theorem 5, a root-to-leaf path crosses at most one light edge and one branching vertex, so $w_{T}\leq 3\text{.}$

The regime of Theorem 4 cannot be removed entirely by a better noise estimate. The following converse, promised at the end of Section 4.3, shows that once budgets of order $\sigma n\sqrt{\log n}$ are admitted, no estimator lands strictly within a factor $\sqrt{2}$ of the noise level, uniformly, on any tree.

Proof.

The mechanism is a scale mixture: doubling the noise of a Gaussian shift is a random perturbation of its mean, and a signal whose flow inequalities all carry enough slack absorbs the perturbation without leaving the cone.

Step 1: the mixture identity. In one coordinate, with $a:=3\sigma^{2}$ and $b:=\sigma^{2}\text{,}$ the exponent of the convolution integrand of $N(0,a)$ and $N(0,b)$ completes the square as

and integrating out $w$ leaves a Gaussian integral at variance $ab/(a+b)\text{;}$ the normalizers combine into that of $N(0,a+b)\text{,}$ so the convolution is $N(0,4\sigma^{2})\text{.}$ Coordinates being independent, with $\gamma:=N(0,3\sigma^{2}I_{n})$ and any fixed $\mu_{0}\in\mathbb{R}^{n}\text{,}$

the law of $Y$ at signal $\mu_{0}$ and noise $2\sigma$ is a $\gamma$-mixture of laws at noise $\sigma$ and shifted signals.

Step 2: a signal with slack. Define $\mu_{0}$ through its leaks,

so that $\mu_{0}\in\mathcal{F}_{V_{0}}(T)$ by Lemma 2.1. The Cauchy–Schwarz inequality and $\sum_{v}(1+|\operatorname{ch}(v)|)=n+(n-1)\leq 2n$ give $V_{0}\leq\sigma\sqrt{6\lambda_{n}}\,\sqrt{n}\,\sqrt{2n}=\sigma n\sqrt{12\lambda_{n}}\leq V_{1}\text{,}$ so $\mu_{0}$ is admitted. Define the legality event

The leak map is linear, so on $A$ the leak of $\mu_{0}+w$ at $v$ is $s_{v}+(w_{v}-\sum_{c}w_{c})\geq 0\text{:}$ the shifted signal is a monotone flow, of root value

hence admitted. Under $\gamma\text{,}$ the constraint at $v$ fails when a centered Gaussian of variance $3\sigma^{2}(1+|\operatorname{ch}(v)|)$ exceeds $s_{v}\text{,}$ and the root cap fails when a centered Gaussian of variance $3\sigma^{2}$ exceeds $\sigma\sqrt{6\lambda_{n}}\text{;}$ by the Gaussian tail bound each failure has probability at most $e^{-\lambda_{n}}\text{,}$ so

Step 3: two inseparable hypotheses. Let $P:=N(\mu_{0},4\sigma^{2}I_{n})\text{,}$ the law of $Y$ at the admitted pair $(\mu_{0},2\sigma)\text{,}$ and let

a mixture of laws at admitted pairs with noise level $\sigma\text{.}$ Splitting Equation S.6.14 over $A$ and $A^{c}$ gives $P=\gamma(A)Q_{A}+\gamma(A^{c})Q_{A^{c}}\text{,}$ so every event $B$ satisfies

Given $\widehat{s}\text{,}$ let $B:=\{\widehat{s}<\sqrt{2}\,\sigma\}\text{.}$ Then $Q_{A}(B^{c})+P(B)=1-[Q_{A}(B)-P(B)]\geq\tfrac{3}{4}\text{,}$ so at least one term is at least $\tfrac{3}{8}\text{.}$ If $P(B)\geq\tfrac{3}{8}\text{:}$ at $(\mu_{0},2\sigma)$ the event $B$ reads $\{\widehat{s}<s/\sqrt{2}\}\text{,}$ outside the window. If $Q_{A}(B^{c})\geq\tfrac{3}{8}\text{:}$ a mixture average is at least $\tfrac{3}{8}\text{,}$ so some $w\in A$ has $\mathbb{P}_{\mu_{0}+w,\,\sigma}(B^{c})\geq\tfrac{3}{8}\text{,}$ and at $(\mu_{0}+w,\sigma)$ the event $B^{c}$ reads $\{\widehat{s}\geq\sqrt{2}\,s\}\text{,}$ outside the window. A randomized estimator is handled by averaging the display over its internal randomness. ∎

The statements deferred from Section 4.3 are now all in place.

This section proves the upper bound of Theorem 5, following the three blocks sketched in Section 5: the localized projection principle (Lemma S.7.1), the truth-localized width bound (5.10) (Lemma S.7.4), which rests on a noise-compatible choice of centers in the coded cover (Lemma S.7.3), and the closure of the exponent, for which Lemma S.7.5 supplies the height branch. The capped order-statistics bound of Lemma S.7.2 does the repeated work inside Lemma S.7.3.

Throughout, $Z\sim N(0,I_{n})$ is the noise, $\ell_{n}:=1+\log(en)\text{,}$ and, for an integer $2\leq k\leq n/C_{\star}\text{,}$ the construction of Proposition 3.1 is in force with the notation and of Section S.2: the working scale $\bar{\alpha}=k\overline{\delta}_{k}(T)\text{,}$ the nets $R_{j}$ with level weights $m_{j}=2^{j}$ and deepest-ancestor maps $a_{j}(\cdot)\text{,}$ and, for a signal $f\in\mathcal{F}_{1}(T)\text{,}$ the terminal cells $L$ with masses $\lambda_{L}$ and levels $m(L)\text{,}$ the collapse $g\text{,}$ the skeleton $g_{0}$ supported on $U\text{,}$ its rounding $\bar{g}_{0}\text{,}$ the exits $q_{L}\text{,}$ and the sampling variables $Z_{L}$ with selection weight $W\text{,}$ a notation fixed in the proof of Proposition 3.1; the unsubscripted $Z$ is always the noise. Root coordinates never contribute: every point of $\mathcal{F}_{V}(T)$ has root coordinate $V\text{,}$ so every difference below vanishes there. The Gaussian tail bound $\mathbb{P}(N(0,\tau^{2})\geq u)\leq e^{-u^{2}/(2\tau^{2})}\text{,}$ valid for $u\geq 0\text{,}$ and Gaussian concentration for Lipschitz functions (Borell, 1975; Cirel’son et al., 1976), namely $\mathbb{P}\bigl(F(Z)\geq\mathbb{E}F(Z)+u\bigr)\leq e^{-u^{2}/(2\Lambda^{2})}$ for $\Lambda$-Lipschitz $F:\mathbb{R}^{n}\to\mathbb{R}\text{,}$ are used without further comment.

The first lemma turns a bound on the localized Gaussian width into a risk bound for the projection. It is the fixed-point principle of Chatterjee’s analysis of least squares (Chatterjee, 2014), in the form quoted in Section 5; nothing in it refers to trees.

Proof.

Write $\widehat{z}:=\widehat{\mu}-\mu$ and, for $s>0\text{,}$ let $X_{s}$ denote the supremum in Equation S.7.1, so that the hypothesis reads $\mathbb{E}X_{s}\leq s^{2}/(4\sigma)$ for $s\geq t\text{.}$ The projection is the nearest point of $C$ and $\mu\in C\text{,}$ so $\|Y-\widehat{\mu}\|_{2}^{2}\leq\|Y-\mu\|_{2}^{2}\text{;}$ expanding both sides at $Y=\mu+\sigma Z$ and cancelling $\sigma^{2}\|Z\|_{2}^{2}$ gives

Fix $s\geq t$ and suppose $\|\widehat{z}\|_{2}\geq s\text{.}$ The point $\mu+s\widehat{z}/\|\widehat{z}\|_{2}$ lies in $C$ by convexity, on the segment from $\mu$ to $\widehat{\mu}\text{,}$ and within distance $s$ of $\mu\text{,}$ so

the middle inequality by Equation S.7.2. As a function of $Z$ the supremum $X_{s}$ is $s$-Lipschitz, being a maximum of linear functionals with gradients of norm at most $s\text{,}$ so concentration and $\mathbb{E}X_{s}\leq s^{2}/(4\sigma)$ give

The layer-cake formula integrates the tail:

the last step by $t\geq\sigma\text{.}$ ∎

For $C=\mathcal{F}_{V}(T)$ the expectation in Equation S.7.1 is the localized width $w_{\mu}(s)$ of Section 5, and the lemma is the principle stated there. Bounding $w_{\mu}$ requires expected maxima of many correlated Gaussian terms whose weights are capped individually and in total; the next lemma is the tool. For $a\in(0,1]$ and $y\in\mathbb{R}^{M}$ define

the largest weighted sum under a cap on each weight and on the total.

Proof.

Write $G_{(1)}^{+}\geq G_{(2)}^{+}\geq\cdots$ for the decreasing rearrangement of the positive parts $[G_{i}]_{+}$ and $Q_{(1)}\geq Q_{(2)}\geq\cdots$ for that of the squares $G_{i}^{2}\text{,}$ and set $q:=\min\{\lceil 1/a\rceil,M\}\text{.}$

Reduction to order statistics. A feasible weight vector puts total weight at most $1\text{,}$ each entry at most $a\text{,}$ and gains nothing from coordinates where $G_{i}<0\text{;}$ moving weight from a smaller to a larger positive coordinate only increases the sum, so the supremum is attained by filling the largest positive coordinates to capacity $a\text{,}$ with at most one fractional entry. Since $aq\geq 1$ when $q=\lceil 1/a\rceil\text{,}$ while all $M$ coordinates are already covered when $q=M\text{,}$

Tails of the order statistics. If $G_{(j)}^{+}\geq u$ for some $u>0\text{,}$ at least $j$ of the $G_{i}$ are at least $u\text{;}$ Markov’s inequality applied to the count, whose mean is at most $Me^{-u^{2}/(2\tau^{2})}$ by the Gaussian tail bound, gives

the second by the same argument applied to $|G_{i}|\text{.}$ Splitting the first tail at $u_{j}\text{,}$ where $u_{j}^{2}:=2\tau^{2}\log(eM/j)\text{,}$ gives

where the integrand is at most $(u/u_{j})\,e^{-u^{2}/(2\tau^{2})}\text{.}$ Splitting the second tail at $2\tau^{2}\log(2eM/j)$ gives

Summation. Summing the first bound over $j\leq q$ and applying the Cauchy–Schwarz inequality to the average,

using $\sum_{j\leq q}\log(eM/j)=q\log(eM)-\log q!\leq q\bigl(2+\log(M/q)\bigr)\text{,}$ by $\log q!\geq q\log q-q\text{.}$ Now $aq\leq a\lceil 1/a\rceil\leq 1+a\leq 2\text{;}$ and either $q=\lceil 1/a\rceil\text{,}$ in which case $M/q\leq Ma\text{,}$ or $q=M\text{,}$ in which case $\log(M/q)=0\text{.}$ In both cases the right side is at most $C\tau\sqrt{1+[\log(Ma)]_{+}}\text{,}$ which with Equation S.7.4 proves the first claim. The second is identical with $\tau^{2}\log(eM/j)$ in place of $\tau\sqrt{\log(eM/j)}\text{,}$ without the Cauchy–Schwarz step. ∎

The heart of the matter is the next lemma: for each signal and noise realization, take the best accurate member of the coded cover; the resulting pairing with the noise, maximized over the body, is small in expectation. Its proof prices the three residuals of the construction separately, and only the last one, the sampled exits, needs the noise-dependent choice.

Proof.

Fix $f$ and run the proof of Proposition 3.1 on it, retaining its objects. Each realization of the sampling defines the candidate $\nu:=\bar{g}_{0}+\sum_{L}Z_{L}q_{L}\text{,}$ and the error decomposes as there:

On the sampling event of that proof, call it $A\text{,}$ of probability at least $\tfrac{1}{4}\text{,}$ where $W\leq 2k$ and $\|\sum_{L}(Z_{L}-\lambda_{L})q_{L}\|_{2}^{2}\leq 8\bar{\alpha}/k\text{,}$ the candidate lies in $\mathcal{D}_{k}\text{,}$ and the three residuals assemble, as in Section S.2, to $\|f-\nu\|_{2}^{2}\leq 3(3+6+8)\bar{\alpha}/k=51\,\overline{\delta}_{k}(T)\text{:}$ the feasible set of Equation S.7.5 is nonempty, for every $f$ and irrespective of $Z\text{.}$ Pairing Equation S.7.7 with the noise and taking on $A$ the realization that minimizes the third term,

The three terms are bounded uniformly over $f$ in turn; the first carries the main contribution, the second is a union bound over few subspaces, and the third is where choosing the center after the noise pays.

The collapse residual. Let $\tau(u)$ be the level of the terminal cell containing $u\text{,}$ so that $g=\sum_{u}\lambda_{u}\,p_{a_{\tau(u)}(u)}$ and the difference telescopes through the levels:

Fix a level $j<J$ and group the contributions by the level-$(j{+}1)$ root: by Lemma S.2.2(3), $a_{j}(u)=a_{j}(b)$ whenever $a_{j+1}(u)=b\text{,}$ so the level-$j$ increment of every $u$ in the group of $b$ is the same vector $p_{b}-p_{a_{j}(b)}\text{,}$ of squared norm at most $d_{T}(a_{j}(b),b)\leq\bar{\alpha}/m_{j}$ by Lemma S.2.2(4). The group mass

is capped: each member of the group lies in the level-$(j{+}1)$ cell of $b$ and in its own terminal cell, which is coarser and hence contains that whole cell; two terminal cells with a common vertex coincide, the terminal cells being a partition, so the group shares one terminal cell, stopped at a level at most $j<J$ and hence light, whence $\lambda_{b}\leq m_{j}/k$ by the monotonicity of the level weights. The group masses are nonnegative and total at most one, each $\lambda_{u}$ entering at most one group, so, with $M_{j}\leq\min\{n,\,|R_{j+1}|\}\leq\min\{n,\,2ke^{2m_{j}}\}$ possible groups (Lemma S.2.1(3)),

by Lemma S.7.2 with variance bound $\bar{\alpha}/m_{j}$ and cap $m_{j}/k\text{:}$ its logarithmic factor $1+[\log(M_{j}m_{j}/k)]_{+}$ is at most $\min\{5m_{j},\,\ell_{n}\}\text{,}$ being at most $1+\log 2+\log m_{j}+2m_{j}\leq 5m_{j}$ from $M_{j}m_{j}/k\leq 2m_{j}e^{2m_{j}}\text{,}$ and at most $1+\log n\leq\ell_{n}$ from $M_{j}m_{j}/k\leq n\text{.}$ Summing the dyadic levels: those with $m_{j}\leq\ell_{n}$ number at most $C\log(2+\ell_{n})$ and contribute $C\sqrt{\bar{\alpha}}$ each, while over the rest $\sqrt{\ell_{n}/m_{j}}$ is geometrically decaying from below one, and sums to a constant. The final increments $p_{u}-p_{a_{J}(u)}$ number at most $n$ and have squared norms at most $\bar{\alpha}/m_{J}\leq 2\overline{\delta}_{k}(T)\text{,}$ and their mass-weighted sum is a feasible value of $\mathfrak{M}_{1}\text{;}$ so Lemma S.7.2 with cap $1$ and variance bound $2\overline{\delta}_{k}(T)$ bounds its expected supremum by $C\sqrt{\overline{\delta}_{k}(T)}\,\sqrt{1+\log n}\leq C\sqrt{\overline{\delta}_{k}(T)\,\ell_{n}}\text{.}$ Altogether

The rounding residual. The difference $g_{0}-\bar{g}_{0}$ has squared norm at most $6\bar{\alpha}/k\text{,}$ by the constant recorded after Lemma S.2.3, and lies in the span of $\{p_{h}:h\in U\}\text{.}$ The set $U\setminus R_{0}$ consists of heavy roots, of total activation charge below $2k$ by Lemma S.2.3(3); it is therefore one of the charged parts counted in the proof of Lemma S.2.5, so at most $e^{19k}$ sets $U\text{,}$ hence at most $e^{19k}$ subspaces $V_{U}:=\operatorname{span}\{p_{h}:h\in U\}\text{,}$ occur as $f$ varies. Each has dimension $|U|\leq|R_{0}|+k\leq ek+k\leq 4k\text{,}$ since a heavy root outside $R_{0}$ carries charge at least $m_{1}=2\text{.}$ For any fixed $U\text{,}$

and $\|P_{V_{U}}Z\|_{2}$ is a $1$-Lipschitz function of $Z$ with mean at most $\sqrt{\dim V_{U}}\leq 2\sqrt{k}\text{.}$ Concentration and a union bound give, for $u\geq 0\text{,}$ $\mathbb{P}(\max_{U}\|P_{V_{U}}Z\|_{2}\geq 2\sqrt{k}+\sqrt{38k}+u)\leq e^{19k}e^{-(\sqrt{38k}+u)^{2}/2}\leq e^{-u^{2}/2}\text{,}$ so $\mathbb{E}\max_{U}\|P_{V_{U}}Z\|_{2}\leq 2\sqrt{k}+\sqrt{38k}+2\leq C\sqrt{k}$ and

The exit pairing. Condition on $Z$ and on $f\text{,}$ so that only the sampling is random, and write $X:=\langle Z,\sum_{L}(\lambda_{L}-Z_{L})q_{L}\rangle\text{.}$ The sampling variables are independent with $\mathbb{E}Z_{L}=\lambda_{L}$ and $\operatorname{Var}(Z_{L})\leq\lambda_{L}m(L)/k\text{,}$ so $X$ is centered with

Centeredness and the Cauchy–Schwarz inequality give

and some realization in $A$ is no larger than this conditional expectation. Hence the third term of Equation S.7.8 is at most $4S_{f}(Z)\text{,}$ and it remains to prove

which gives $\mathbb{E}\sup_{f}S_{f}(Z)\leq\sqrt{\mathbb{E}\sup_{f}S_{f}(Z)^{2}}\leq C\sqrt{\bar{\alpha}}$ by Jensen’s inequality. An exit $q_{L}$ is determined by the root $a_{L}$ of its cell: its other endpoint is the root of the parent cell (Lemma S.2.2(3)), so at level $m$ the possible exits number at most $\min\{n,2ke^{m}\}\text{,}$ with $\|q_{L}\|_{2}^{2}\leq 2\bar{\alpha}/m$ by the parent cell’s radius. Split $S_{f}(Z)^{2}$ by levels. At a level $m\leq\ell_{n}\text{,}$ the weights $\lambda_{L}\leq m/k$ are again capped with total at most one, so Lemma S.7.2, applied to the squares with variance bound $2\bar{\alpha}/m$ and cap $m/k\text{,}$ bounds the expected supremum of the level’s sum by $C(2\bar{\alpha}/m)\bigl(1+[\log(2me^{m})]_{+}\bigr)\leq C\bar{\alpha}\text{,}$ since $1+\log(2me^{m})\leq 4m\text{;}$ with the prefactor $m/k$ the level contributes $C\bar{\alpha}\,m/k\text{,}$ and the dyadic sum over $m<k$ is at most $C\bar{\alpha}\text{.}$ At the levels $m>\ell_{n}\text{,}$ the prefactor obeys $m/k\leq 1$ and the weights total at most one, so the combined contribution is a feasible value of $\mathfrak{M}_{1}$ over the possible exits at these levels, at most $n(1+\log_{2}k)$ vectors of variance at most $2\bar{\alpha}/\ell_{n}\text{;}$ Lemma S.7.2 with cap $1\text{,}$ applied to the squares, bounds its expectation by $C(\bar{\alpha}/\ell_{n})\bigl(1+\log(n(1+\log_{2}k))\bigr)\leq C\bar{\alpha}\text{,}$ since $1+\log\bigl(n(1+\log_{2}k)\bigr)\leq 2\ell_{n}\text{.}$ This proves Equation S.7.11.

Combining Equation S.7.8 with Equations S.7.9, S.7.10 and S.7.11,

and $\sqrt{\bar{\alpha}}\leq\sqrt{\bar{\alpha}}\log(2+\ell_{n})$ absorbs the last two terms into the first. ∎

The width bound follows by recentering the local ball at a deterministic member of the cover.

Proof.

Abbreviate $\overline{\delta}:=\overline{\delta}_{k}(T)\text{.}$ Amplitudes rescale: for $\theta\in\mathcal{F}_{V}(T)$ the normalized signal $\theta/V$ lies in $\mathcal{F}_{1}(T)\text{,}$ and multiplying a member of the unit-amplitude cover by $V$ gives a member of $\mathcal{D}_{k}$ at amplitude $V\text{.}$ The feasible set of Equation S.7.5 does not depend on $Z$ and is never empty, so fix $\nu_{\mu}\text{,}$ $V$ times one of its members at $\mu/V\text{:}$ then $\|\mu-\nu_{\mu}\|_{2}\leq V\sqrt{51\overline{\delta}}$ and $\nu_{\mu}$ is deterministic. For each $\theta$ with $\|\theta-\mu\|_{2}\leq t$ and each realization of $Z\text{,}$ let $\nu_{\theta}$ be $V$ times a minimizer of Equation S.7.5 at $\theta/V\text{,}$ so that $\|\theta-\nu_{\theta}\|_{2}\leq V\sqrt{51\overline{\delta}}$ and $\langle Z,\theta-\nu_{\theta}\rangle=V\,\mathfrak{r}_{Z}(\theta/V)\text{.}$ Decompose

The last term does not depend on $\theta$ and has expectation zero, $\nu_{\mu}$ being deterministic, so it drops from the expected supremum. The middle term is at most $V\sup_{f\in\mathcal{F}_{1}(T)}\mathfrak{r}_{Z}(f)\text{,}$ whose expectation Lemma S.7.3 bounds by the second group of the claim. For the first term, the triangle inequality confines every center met to a deterministic ball:

so the first term is at most the maximum of $\langle Z,\nu-\nu_{\mu}\rangle$ over $\{\nu\in\mathcal{D}_{k}:\|\nu-\nu_{\mu}\|_{2}\leq\rho\}\text{,}$ a fixed set of at most $e^{C_{1}k}$ centered Gaussians of standard deviation at most $\rho\text{.}$ The maximum is a feasible value of $\mathfrak{M}_{1}\text{,}$ so Lemma S.7.2 with cap $1$ bounds its expectation by $C\rho\sqrt{1+C_{1}k}\leq C(t+V\sqrt{\overline{\delta}}\,)\sqrt{k}\text{,}$ the first group of the claim. ∎

The second comparison branch of Section 5 rests on the profile remembering the height of the tree.

Proof.

Write $h:=h_{T}\text{,}$ so that $H_{T}\leq 2h\text{,}$ and fix a root-to-leaf path with $h$ edges; every ancestor of a vertex of the path lies on the path, so ancestor covering restricted to it is interval covering of its $h+1$ vertices, as on the path of Lemma S.4.1.

If $h\geq 4k\text{,}$ set $q:=\lfloor h/(2k)\rfloor-1\geq 1\text{.}$ A center covers at most $q+1$ consecutive path vertices, so

whence $[\log(N^{\uparrow}_{T}(q)/k)]_{+}\geq\log 2$ and the term of the discrete formula (2.3) at $q$ is at least $(q+1)\log 2\text{.}$ Since $q+1=\lfloor h/(2k)\rfloor>h/(2k)-1\geq h/(4k)\text{,}$

If $h<4k\text{,}$ the term of (2.3) at $q=0$ is $\min\{k,[\log(n/k)]_{+}\}\geq\min\{k,2\}\geq 1\text{,}$ since $n/k\geq C_{\star}=e^{2}\text{;}$ hence $\delta_{k}\geq 1/k>H_{T}\log 2/(8k^{2})\text{,}$ using $H_{T}\leq 2h<8k$ and $\log 2<1\text{.}$ ∎

The blocks are in place, and it remains to assemble them along the case analysis of Section 5.

Completion of Theorem 5, upper bound.

The skeleton, the meeting of the two branches at $k_{0}=\ell_{n}^{1/5}\text{,}$ and the resulting bound $C(1+\log(en))^{2/5}$ are in Section 5; deferred here are the fixed-point verification behind (5.11), the height branch (5.12), and the endpoint cases.

The interior case: the width branch (5.11). Let $2\leq k_{0}\leq K:=\lfloor n/C_{\star}\rfloor\text{,}$ so that the crossing clause fired at $k_{0}\text{:}$ $V^{2}\delta_{k_{0}}\leq A_{0}\sigma^{2}k_{0}\text{,}$ and $R^{*}_{T}\asymp\sigma^{2}k_{0}$ by the interior case of Section 3.3. Lemma 2.3 gives $\overline{\delta}_{k_{0}}\leq 2\delta_{k_{0}}\text{,}$ so

and Lemma S.7.4 at $k=k_{0}$ yields, for every $s>0\text{,}$

with one universal constant $C\text{,}$ uniformly over $\mu\in\mathcal{F}_{V}(T)\text{:}$ the term $CV\sqrt{\overline{\delta}_{k_{0}}}\,\sqrt{k_{0}}\leq C^{\prime}\sigma k_{0}$ from the first group, and both terms of the second group after the two displayed substitutions, are absorbed into $C\sigma B\text{,}$ since $k_{0}\leq B/\log 2\text{.}$ Set $t^{2}:=C_{\mathrm{loc}}\sigma^{2}B$ with $C_{\mathrm{loc}}:=64C^{2}/\log 2+8C+1\text{.}$ Then $t\geq\sigma\text{,}$ since $B\geq k_{0}\log 2\geq 2\log 2>1\text{;}$ and for every $s\geq t\text{,}$

the first term because $s\geq t\geq\sqrt{C_{\mathrm{loc}}k_{0}\log 2}\,\sigma\geq 8C\sigma\sqrt{k_{0}}\text{,}$ and the second because $C\sigma^{2}B=Ct^{2}/C_{\mathrm{loc}}\leq t^{2}/8\leq s^{2}/8\text{.}$ Lemma S.7.1 applies at every $\mu$ and gives

dividing by $R^{*}_{T}\asymp\sigma^{2}k_{0}$ proves (5.11).

The interior case: the height branch (5.12). Still for $2\leq k_{0}\leq K\text{,}$ Lemma S.7.5 applies at $k_{0}$ and combines with the crossing:

Both $\mu$ and its projection lie in the body, so $\|\widehat{\mu}_{\mathrm{LSE}}-\mu\|_{2}^{2}\leq\operatorname{diam}^{2}\mathcal{F}_{V}(T)=V^{2}H_{T}$ pathwise, and dividing by $R^{*}_{T}\asymp\sigma^{2}k_{0}$ proves (5.12).

The endpoints. The projection onto a convex set is a contraction, so $\|\widehat{\mu}_{\mathrm{LSE}}-\mu\|_{2}=\|\Pi_{\mathcal{F}_{V}(T)}(Y)-\Pi_{\mathcal{F}_{V}(T)}(\mu)\|_{2}\leq\|Y-\mu\|_{2}$ and $R^{\mathrm{worst}}_{\mathrm{LSE}}\leq\sigma^{2}n$ always; together with the diameter,

If $k_{0}=K+1$ with $n\geq C_{\star}\text{,}$ the dimension case of Section 3.3 gives $R^{*}_{T}\asymp\sigma^{2}n\text{,}$ and Equation S.7.12 bounds the ratio by a constant. If $k_{0}=1\text{,}$ the two-point bound (3.8) gives $R^{*}_{T}\geq c\min\{V^{2}H_{T},\sigma^{2}\}$ for $n\geq 2\text{,}$ and there are two subcases. When $n<C_{\star}\text{,}$ the right side of Equation S.7.12 is at most $C_{\star}\min\{V^{2}H_{T},\sigma^{2}\}\text{:}$ its second branch is $\sigma^{2}n\leq C_{\star}\sigma^{2}\text{,}$ and its first is unchanged. When the crossing clause fired at $k=1\text{,}$ the second case of Section 3.3 gives $V^{2}H_{T}\leq 2V^{2}h_{T}\leq(2A_{0}/\log 2)\,\sigma^{2}\text{,}$ so the right side of Equation S.7.12 is again at most $C\min\{V^{2}H_{T},\sigma^{2}\}\text{:}$ if $V^{2}H_{T}\leq\sigma^{2}$ it equals the first branch, and otherwise it is at most $C\sigma^{2}\text{.}$ In both subcases $R^{\mathrm{worst}}_{\mathrm{LSE}}\leq C\,R^{*}_{T}\text{.}$ The three cases are exhaustive: $k_{0}=K+1$ with $n<C_{\star}$ means $K=0$ and $k_{0}=1\text{,}$ which the last case covers. Together with the two interior branches and the case analysis of Section 5, the upper bound of Theorem 5 is proved; with the lower bound established there, so is the theorem. ∎