Adaptive Splits for Spatially Uneven Smoothness

Why Leaf Allocation Should Vary Across Space

A tree with a fixed number of leaves must decide not only how many leaves to use, but also where to use them. If a regression function changes gently in one part of the predictor space and rapidly in another, equal spatial refinement can spend leaves where they add little accuracy while leaving the difficult region under-resolved. The relevant comparison is between the approximation gained by refining a region and the cost of using another leaf there.

We formalize that comparison with a regional approximation model. The resulting allocation is an oracle benchmark: it uses the regional approximation rates as if they were known. It does not, by itself, describe a data-driven rule for discovering those rates or guarantee that every allocation can be represented by a particular tree.

Definition: Let the predictor domain be divided into $J$ disjoint regions $R_1,\ldots,R_J$, with $P(X\in R_j)=p_j>0$ and $\sum_{j=1}^J p_j=1$. If region $R_j$ receives $k_j$ leaves, suppose its contribution to integrated squared approximation error is bounded by $p_j C_j k_j^{-\alpha_j}$, where $C_j>0$ and $\alpha_j>0$. The resulting regional approximation bound is $$ B(k_1,\ldots,k_J)=\sum_{j=1}^J p_j C_j k_j^{-\alpha_j}. $$

The factor $p_j$ weights error by how often observations fall in region $R_j$; $C_j$ captures the difficulty of approximating the regression function there; and $\alpha_j$ describes how quickly approximation improves as leaves are added. For example, for piecewise-constant approximation to a sufficiently smooth function in $d$ dimensions, a common rate has $\alpha=2s/d$ when the function has smoothness $s$ and the cells are regular. Such a rate is a modeling assumption about approximation, not a universal identity for every tree partition or function.

When the regional exponents differ, simply assigning leaves in proportion to region volume is not generally optimal. We first derive the exact allocation for a fixed budget when all regions share an exponent, then allow the exponents to vary.

A Fixed Leaf Budget and a Shared Approximation Rate

Assume every region has the same exponent $\alpha>0$. Write $a_j=p_jC_j$, and relax the leaf counts to positive real numbers temporarily. With a budget of $K$ leaves, the oracle minimizes $\sum_j a_j k_j^{-\alpha}$ subject to $\sum_j k_j=K$. The continuous relaxation isolates the allocation principle; actual leaf counts must be integers.

Theorem: If $a_j>0$, $\alpha>0$, and the continuous allocations satisfy $k_j>0$, the unique minimizer under $\sum_j k_j=K$ is $$ k_j^*=K\frac{a_j^{1/(\alpha+1)}}{\sum_{\ell=1}^J a_\ell^{1/(\alpha+1)}}. $$ The minimized approximation bound is $$ B^*(K)=K^{-\alpha}\left(\sum_{j=1}^J a_j^{1/(\alpha+1)}\right)^{\alpha+1}. $$

Proof. Each term $a_j k_j^{-\alpha}$ is strictly convex for $k_j>0$, since its second derivative is $\alpha(\alpha+1)a_j k_j^{-\alpha-2}>0$. Thus the objective is strictly convex on the positive part of the constraint set, so any stationary point there is the unique minimizer. Introduce a multiplier $\nu$ for the budget constraint. Differentiating the Lagrangian with respect to $k_j$ gives $$ -\alpha a_j k_j^{-\alpha-1}+\nu=0. $$ Therefore $k_j=(\alpha a_j/\nu)^{1/(\alpha+1)}$. Summing over regions and imposing $\sum_j k_j=K$ gives $(\alpha/\nu)^{1/(\alpha+1)}=K/\sum_\ell a_\ell^{1/(\alpha+1)}$, which yields the stated allocation. To evaluate the objective, set $S=\sum_\ell a_\ell^{1/(\alpha+1)}$. Then $k_j^*=K a_j^{1/(\alpha+1)}/S$, so $$ \sum_j a_j(k_j^*)^{-\alpha} =\sum_j a_j\left(\frac{K a_j^{1/(\alpha+1)}}{S}\right)^{-\alpha} =K^{-\alpha}S^\alpha\sum_j a_j^{1/(\alpha+1)} =K^{-\alpha}S^{\alpha+1}. $$ This proves both claims. $\square$

The rule allocates more leaves to regions with larger $p_jC_j$, but not in direct proportion to that quantity: the exponent $1/(\alpha+1)$ moderates the allocation. If all regions have the same $p_jC_j$, they receive equal counts. If a continuous solution conflicts with a requirement such as at least one leaf per region, the constrained optimum must respect that requirement and the remaining budget must be reallocated.

Worked Example: A Difficult Region Gets More Than Its Share

Suppose two regions have $p_1=0.8$, $C_1=1$, $p_2=0.2$, $C_2=9$, and a shared exponent $\alpha=1$. There are $K=100$ leaves. Compare uniform spatial refinement with the oracle allocation.

For this exponent, $a_1=p_1C_1=0.8$ and $a_2=p_2C_2=1.8$. The allocation ratio is $\sqrt{0.8}:\sqrt{1.8}$. Since $0.8+1.8=2.6$, the counts are $$ k_1^*=100\frac{\sqrt{0.8}}{\sqrt{0.8}+\sqrt{1.8}}=40,\qquad k_2^*=100\frac{\sqrt{1.8}}{\sqrt{0.8}+\sqrt{1.8}}=60. $$

Uniform spatial refinement gives $k_1=0.8(100)=80$ and $k_2=0.2(100)=20$. Its approximation bound is $0.8/80+1.8/20=0.01+0.09=0.10$. The oracle bound is $0.8/40+1.8/60=0.02+0.03=0.05$. With the same total number of leaves, allocating more to the high-difficulty region halves this bound. The example uses exact integer counts, so no rounding adjustment is needed.

Different Smoothness Across Regions

When the exponents vary, a fixed-budget allocation still has a well-defined optimum, but it generally has no single proportional-allocation formula of the preceding form. A useful alternative is to include a per-leaf complexity cost $\lambda>0$ and minimize $$ Q_\lambda(k_1,\ldots,k_J)=\sum_{j=1}^J p_jC_jk_j^{-\alpha_j}+\lambda\sum_{j=1}^J k_j. $$

This is an oracle approximation-penalty criterion. In statistical risk comparisons, a leaf penalty can represent the cost of estimating additional cellwise parameters; in many settings its scale is related to noise variance divided by sample size. The criterion is a transparent allocation model, not an exact finite-sample risk identity without further assumptions on sampling, cell occupancy, and estimation.

Theorem: For $p_jC_j>0$, $\alpha_j>0$, and $\lambda>0$, the unique minimizer of $Q_\lambda$ over positive real $k_j$ is $$ k_j^*=\left(\frac{\alpha_jp_jC_j}{\lambda}\right)^{1/(\alpha_j+1)}. $$

Derivation. For each $j$, the derivative of the $j$th contribution to $Q_\lambda$ is $-\alpha_jp_jC_j k_j^{-\alpha_j-1}+\lambda$, and its second derivative is $\alpha_j(\alpha_j+1)p_jC_j k_j^{-\alpha_j-2}>0$. The objective is separable and strictly convex, so its unique minimizer is where each derivative is zero. Solving $\alpha_jp_jC_j k_j^{-\alpha_j-1}=\lambda$ gives the displayed formula. Also, the objective tends to infinity as $k_j$ approaches zero or infinity for any one coordinate while the others are fixed; hence this stationary point is the minimizer. $\square$

The allocation responds to three quantities at once: regional probability, approximation difficulty, and the regional approximation exponent. A larger exponent means approximation error falls more rapidly with added leaves, which can make refinement particularly productive at smaller leaf counts. The marginal improvement from one additional continuous leaf in region $j$ is $\alpha_jp_jC_j k_j^{-\alpha_j-1}$; the optimum balances that improvement against the common cost $\lambda$.

Worked Example: Smooth and Rough Regions Under a Leaf Penalty

Consider two equally probable regions. In region 1, let $C_1=1$ and $\alpha_1=2$; in region 2, let $C_2=2$ and $\alpha_2=1$. Set $\lambda=1/64$. The oracle formula gives $$ k_1^*=\left(\frac{2(0.5)(1)}{1/64}\right)^{1/3}=64^{1/3}=4,\qquad k_2^*=\left(\frac{1(0.5)(2)}{1/64}\right)^{1/2}=64^{1/2}=8. $$

At $(4,8)$, the approximation part is $0.5(1)(4^{-2})+0.5(2)(8^{-1})=1/32+1/8=0.15625$. The penalty is $(4+8)/64=0.1875$. Thus $Q_\lambda=0.34375$. For comparison, assigning six leaves to each region gives approximation $0.5/36+1/6=0.180555\ldots$, penalty $12/64=0.1875$, and total $0.368055\ldots$. The adaptive allocation lowers the criterion. Its optimality follows from the derivative equations: the marginal reductions are $1/4^3=1/64$ and $1/8^2=1/64$, both equal to the leaf cost.

Spatial Refinement: A Two-Dimensional Illustration

For piecewise-constant approximation to a Lipschitz regression function on regular two-dimensional cells, the familiar approximation exponent is $\alpha=2s/d=1$ when $s=1$ and $d=2$. The next calculation uses that rate as a regional model. It shows why area-proportional refinement can be inefficient when approximation constants differ substantially.

Worked Example: Fixed-Budget Refinement in Two Dimensions

Let region 1 have probability $p_1=0.9$ and constant $C_1=1$, while region 2 has probability $p_2=0.1$ and constant $C_2=25$. Both have $\alpha=1$, and the total budget is $K=100$. The coefficients are $a_1=0.9$ and $a_2=2.5$. The continuous oracle allocation is $$ k_1^*=100\frac{\sqrt{0.9}}{\sqrt{0.9}+\sqrt{2.5}}=37.5,\qquad k_2^*=100\frac{\sqrt{2.5}}{\sqrt{0.9}+\sqrt{2.5}}=62.5. $$

With integer counts $(38,62)$, the bound is $0.9/38+2.5/62\approx0.02368421+0.04032258=0.06400679$. Uniform spatial refinement gives $(90,10)$ and bound $0.9/90+2.5/10=0.01+0.25=0.26$. The comparison is between the stated regional bound values; the rounded allocation is close to the continuous oracle, while the uniform allocation leaves the difficult region with only ten leaves.

What the Oracle Comparison Does—and Does Not—Say

These calculations explain why spatial adaptivity can matter: allocation should respond to approximation difficulty, not merely to region size. They also give a benchmark for reasoning about data-adaptive trees. A learned tree may not know $p_j$, $C_j$, or $\alpha_j$, and its candidate splits may not permit arbitrary independent choices of $k_j$. If regions are not aligned with feasible tree cells, a desired allocation may require extra splits or may be impossible to realize exactly. The oracle criterion identifies a target, not a promise that a greedy splitting procedure will attain it.

A separate statistical issue is estimation. More leaves can reduce approximation error while increasing the cost of estimating leaf values. The penalty $\lambda\sum_j k_j$ expresses that tension in a simple form. For an actual risk bound, one must justify the penalty scale and account for sample sizes in the leaves, including possible sparse or empty cells; the allocation formulas alone do not establish those guarantees.

Common Mistake

Wrong reasoning: “Region 1 contains 80% of the observations, so it should receive 80% of the leaves.” This confuses probability mass with approximation difficulty and ignores the diminishing returns from repeated refinement.
Correction: Under a shared exponent and a fixed budget, the continuous oracle allocation is proportional to $(p_jC_j)^{1/(\alpha+1)}$, not $p_j$. With different exponents, use the regional marginal-improvement equations for the criterion being optimized. These formulas remain benchmarks under the stated approximation model; realizable tree structure and estimation constraints must still be considered.

Key takeaway: Uniform spatial refinement is appropriate only when it matches the regional approximation structure. With a common approximation exponent, a fixed-budget oracle allocates leaves in proportion to $(p_jC_j)^{1/(\alpha+1)}$; with region-specific exponents and a leaf penalty, it balances each region’s marginal approximation gain against that penalty.

Check Your Understanding

Use the regional approximation model and distinguish its oracle conclusions from claims about data-adaptive tree construction.

For two regions with a shared exponent $\alpha=1$, $p_1C_1=1$, and $p_2C_2=9$, what fraction of a fixed continuous leaf budget goes to region 2?
Why does a larger $p_j$ not, by itself, imply that region $j$ should receive a proportionally larger leaf count?
For the penalized criterion, explain what quantity is equalized across regions at an interior optimum.
In the two-dimensional example, why does area-proportional allocation perform poorly under the given approximation constants?
Name one reason the oracle allocation may not be realized exactly by a data-selected tree.