Coordinate Splitting and Dimension-Dependent Localization

Why Coordinate-Wise Localization Matters

An axis-aligned tree partitions the predictor space by repeatedly cutting one coordinate at a time. A cell can become narrow in some directions while remaining broad in another. Consequently, a small overall cell diameter cannot be taken for granted merely because the tree is deep: localization requires enough effective cuts in every relevant coordinate, as well as cuts that actually reduce widths.

This tutorial makes that requirement quantitative. It connects three ingredients: the probability that a split uses coordinate $j$, the number of splits along a path, and the amount by which each such split contracts the cell width. The resulting bounds also show why dimension matters: a guarantee for one coordinate need not hold simultaneously for all coordinates when there are many of them.

Cell Widths and Coordinate Split Counts

Work in a rectangular predictor domain in $p$ dimensions. Fix a prediction point $x$, and follow the path through the tree to the leaf containing $x$. After $D$ splits on this path, write $C_D(x)$ for its cell and $W_{j,D}(x)$ for the width of that cell in coordinate $j$. Let $L_j$ be the initial width in coordinate $j$, and let $N_j(D)$ count how many of the $D$ splits use that coordinate. Thus $\sum_{j=1}^p N_j(D)=D$ when each split uses exactly one coordinate.

Definition: Coordinate $j$ has a per-split contraction bound $\rho_j$ if $0<\rho_j<1$ and every split on coordinate $j$ reduces the width of the child cell containing $x$ to at most $\rho_j$ times the parent width. Under this condition, $$ W_{j,D}(x)\leq L_j\rho_j^{N_j(D)}. $$ A coordinate split that does not satisfy such a bound may fail to reduce the width by a fixed proportion; split count alone then does not establish shrinkage.

For example, if a cut divides the current interval at a fraction $u$ of its width, the child containing $x$ has width at most $\max(u,1-u)$ times the parent width. If all cuts in coordinate $j$ use fractions bounded away from 0 and 1, one can take a common $\rho_j<1$. The contraction assumption concerns the child containing the prediction point, not an average over both children.

To model coordinate selection, suppose there is a lower bound $q_j>0$ on the conditional probability that the next split along the path uses coordinate $j$, given the preceding splits and any information available before that choice. This permits dependent split choices; the lower bound must hold at every one of the $D$ steps. An exact fixed selection probability is a special case.

Worked Example: Converting Split Counts to Widths

Suppose an initial cell has width $L_j=2$ in coordinate $j$, and every split in that coordinate contracts the width by at most $\rho_j=0.8$. Along a particular path, coordinate $j$ is split 8 times. Then $$ W_{j,D}(x)\leq 2(0.8)^8 =2(0.16777216) =0.33554432. $$

This is an upper bound, not necessarily the exact width: a cut may contract more than the guaranteed factor. If the coordinate had instead been split only twice, the same guarantee would give $W_{j,D}(x)\leq2(0.8)^2=1.28$. The total path depth does not enter either calculation except through its contribution to $N_j(D)$.

A Lower-Tail Bound for Coordinate Split Counts

A probability lower bound on choosing coordinate $j$ gives a useful guarantee against too few splits in that coordinate. The bound below does not require independent split choices.

Theorem: Suppose there are $D$ split choices and, at each choice, the conditional probability of selecting coordinate $j$ is at least $q_j>0$. Then $$ P\left\{N_j(D)<\frac{Dq_j}{2}\right\} \leq \exp\left\{-cDq_j\right\}, \qquad c=\frac{1-\log 2}{2}. $$

Proof. Let $I_{j,t}$ equal 1 if split $t$ uses coordinate $j$, and 0 otherwise. Given the history before split $t$, its conditional probability of being 1 is at least $q_j$. For any $s>0$, $$ E\left[\exp(-s I_{j,t})\mid\text{history before split }t\right] =1-P(I_{j,t}=1\mid\text{history})(1-e^{-s}) \leq 1-q_j(1-e^{-s}) \leq \exp\{-q_j(1-e^{-s})\}. $$ Iterating conditional expectations over the $D$ choices gives $$ E[\exp\{-sN_j(D)\}] \leq \exp\{-Dq_j(1-e^{-s})\}. $$ On the event $N_j(D)<Dq_j/2$, $\exp\{-sN_j(D)\}>\exp\{-sDq_j/2\}$. Markov's inequality therefore yields $$ P\left\{N_j(D)<\frac{Dq_j}{2}\right\} \leq \exp\{sDq_j/2-Dq_j(1-e^{-s})\}. $$ Set $s=\log 2$, so $e^{-s}=1/2$. The exponent becomes $$ \frac{Dq_j\log 2}{2}-\frac{Dq_j}{2} =-\frac{1-\log 2}{2}Dq_j. $$ This proves the bound. $\square$

The constant $c=(1-\log 2)/2$ is about $0.1534$. It matters when comparing the probability bound with a growing number of coordinates; it cannot be omitted from a sufficient condition derived from this inequality.

Worked Example: A Simultaneous Guarantee in Three Coordinates

Suppose $D=100$, the conditional coordinate probabilities are $q_1=0.5$, $q_2=0.3$, and $q_3=0.2$, and the contraction factor is $0.8$ in every coordinate. Let every initial width be 1. If each coordinate receives at least half its lower-bound expected count, then the width bounds are $$ W_{1,D}(x)\leq 0.8^{25}\approx0.00378,\qquad W_{2,D}(x)\leq 0.8^{15}\approx0.03518,\qquad W_{3,D}(x)\leq 0.8^{10}\approx0.10737. $$

The probability that any of the three count thresholds fails is at most the sum of the three lower-tail bounds: $$ \exp(-50c)+\exp(-30c)+\exp(-20c) \approx 0.000466+0.0100+0.0465 \approx 0.0570. $$ Thus, with probability at least about $0.943$, all three widths are no larger than the displayed thresholds. The least frequently split coordinate determines the largest of these width guarantees.

Simultaneous Localization

For each coordinate, the preceding theorem controls an event on which the split count is unusually small. A union bound controls the chance that any coordinate has this problem. Width contraction supplies the separate requirement that successful split counts actually make the cells narrow.

Theorem: Suppose that, for each $j\leq p$, the conditional probability of selecting coordinate $j$ at every one of $D$ splits is at least $q_j>0$, and every split in coordinate $j$ contracts the width by at most $\rho_j\in(0,1)$. Then, with probability at least $$ 1-\sum_{j=1}^{p}\exp(-cDq_j), $$ all coordinates satisfy $$ W_{j,D}(x)\leq L_j\rho_j^{Dq_j/2}. $$

Proof. Define the good event for coordinate $j$ by $N_j(D)\geq Dq_j/2$. The lower-tail theorem bounds the probability that this event fails by $\exp(-cDq_j)$. By the union bound, the probability that at least one coordinate's event fails is at most $\sum_{j=1}^{p}\exp(-cDq_j)$. On the event that none fail, the contraction inequality and $0<\rho_j<1$ imply $$ W_{j,D}(x)\leq L_j\rho_j^{N_j(D)} \leq L_j\rho_j^{Dq_j/2} $$ for every coordinate $j$. This proves the claim. $\square$

In a sequence of problems where $p$, $D$, and the other quantities can vary, this theorem gives a direct sufficient condition for simultaneous localization in probability: both $$ \sum_{j=1}^{p}\exp(-cDq_j)\longrightarrow 0 \qquad\text{and}\qquad \max_{1\leq j\leq p}L_j\rho_j^{Dq_j/2}\longrightarrow 0. $$ The first condition makes the probability of a deficient split count vanish. The second makes the width bounds on the good event vanish. Neither condition replaces the other.

If $q_j\geq q_{\min,D}$ for every coordinate, the probability sum is at most $p_D\exp(-cDq_{\min,D})$. A sufficient condition for this bound to tend to zero is $$ cDq_{\min,D}-\log p_D\longrightarrow\infty. $$ The factor $c$ is part of this sufficient condition. For example, a claim based only on $Dq_{\min,D}-\log p_D\to\infty$ does not follow from this bound.

Worked Example: Uniform Feature Probabilities as Dimension Grows

Consider a sequence with $p$ coordinates, $D=p^2$ splits, and uniform coordinate probabilities $q_j=1/p$. Suppose $L_j\leq1$ and $\rho_j=0.9$ for every coordinate. The failure-probability sum is bounded by $$ p\exp(-cD/p)=p\exp(-cp), $$ which tends to zero as $p$ grows. On the good event, all widths are at most $$ 0.9^{D/(2p)}=0.9^{p/2}, $$ which also tends to zero. Both requirements for simultaneous localization are satisfied. By contrast, checking only the split-count bound would not establish that widths vanish if the contraction factors or initial widths were allowed to vary unfavourably with $p$.

How Feature Sampling Enters

Feature sampling affects localization through the probability that a coordinate is available and ultimately chosen for splitting. These are not automatically the same probability. For example, if a feature is included among candidate variables with probability $a_j$, and its conditional probability of being selected for the split when available is at least $b_j$, then the probability of selecting it is at least $a_jb_j$, provided these bounds hold conditional on the preceding path history. One may use $q_j=a_jb_j$ in the results above.

Worked Example: Candidate Sampling and Required Depth

At each node, suppose 5 of 20 features are sampled uniformly as candidates. A particular feature is therefore available with probability $5/20=0.25$. Suppose that, when available, it has conditional probability at least $1/5=0.2$ of being selected for the split. Its conditional probability of being selected at a node is at least $$ q_j\geq 0.25(0.2)=0.05. $$

With $D=2000$, the lower-tail theorem bounds the probability of fewer than $Dq_j/2=50$ splits on this coordinate by $$ \exp(-c(2000)(0.05))=\exp(-100c)\approx2.17\times10^{-7}. $$ If its initial width is at most 1 and its contraction factor is 0.9, then on the complementary event its width is at most $$ 0.9^{50}\approx0.00515. $$ This is a coordinate-specific guarantee. To guarantee the result for many features together, the failure probabilities must be summed over those features, and the simultaneous width thresholds must still tend to zero.

Common Mistakes and Why the Conditions Matter

Using split counts as if they were widths. A large $N_j(D)$ only implies a small width when the splits contract by a controlled amount. The inequality $W_{j,D}(x)\leq L_j\rho_j^{N_j(D)}$ requires $\rho_j<1$ and the stated per-split contraction property.
Checking the probability bound but not the width threshold. A vanishing failure probability says that counts are usually adequate; it does not itself imply that the widths on the good event vanish. For example, with $p=1$, $q_1=1$, $L_1=1$, and contraction factor $\rho_D=1-D^{-2}$, the lower-tail bound tends to zero. Yet if every split contracts by exactly $\rho_D$, then $$ W_{1,D}(x)=(1-D^{-2})^D\longrightarrow 1, $$ not 0. The count condition and the width condition must both be checked.
Dropping the constant in a dimension-dependent bound. The union bound here is $p_D\exp(-cDq_{\min,D})$. Its convergence to zero is ensured by $cDq_{\min,D}-\log p_D\to\infty$, not merely by $Dq_{\min,D}-\log p_D\to\infty$.
Treating feature availability as selection. Being offered as a candidate does not guarantee a split on that coordinate. The conditional probability of selection when available must also be accounted for.

Coordinate-wise localization is a useful way to audit a tree or forest construction: identify a lower bound on each coordinate's selection probability, verify a contraction condition, and then check the dimension-dependent probability and width requirements. In settings where prediction weights concentrate on cells around the query point, this analysis clarifies exactly which coordinate directions are guaranteed to become local and which assumptions are doing the work.

Check Your Understanding

Use the definitions and bounds above to answer the following questions.

If a coordinate has initial width $L_j$, contraction factor $\rho_j$, and is split $k$ times, what upper bound follows for its final width?
Why does the lower-tail bound for split counts remain valid when the coordinate choices are dependent but have conditional probabilities bounded below by $q_j$?
For a sequence with growing dimension, name both conditions needed by the simultaneous localization bound.
If $p_D$ coordinates all have $q_j\geq q_{\min,D}$, what sufficient condition from the union bound makes the failure-probability sum vanish?
A feature is a candidate with probability $a_j$, and, when available, is selected with conditional probability at least $b_j$. Under the stated conditional assumptions, what lower bound can be used for $q_j$?