Axis-Aligned Trees for Smooth Regression Functions

Why the Direction of a Split Matters

A tree with many leaves need not approximate a smooth regression function well. Its effectiveness depends on where those leaves are placed: a split that halves a cell along a rapidly changing coordinate can reduce approximation error more than a split along a nearly irrelevant one. This tutorial quantifies that geometric effect for axis-aligned trees, whose splits are threshold cuts in one coordinate at a time.

We study approximation of a regression function \(m\) on \([0,1]^d\). The bounds below concern the function itself and do not require a finite second moment for the response. When we identify a cellwise conditional mean as the best predictor under squared-error risk, we state the additional square-integrability condition explicitly.

For a fixed partition \(\mathcal P\), a simple approximation assigns a representative value \(m(x_C)\) to each cell, where \(x_C\in C\). Its error depends on how much \(m\) can vary within each cell. For population prediction, the more usual choice is the cellwise mean. Define \(m_{\mathcal P}(X)=E[m(X)\mid \sigma(\mathcal P)]\), where \(\sigma(\mathcal P)\) records which cell contains \(X\). Cells with probability zero can be assigned any value without affecting the risk.

Lipschitz Functions and Cell Diameters

Suppose \(m\) is \(L\)-Lipschitz in Euclidean distance: for all \(x,z\in[0,1]^d\), \(|m(x)-m(z)|\le L\|x-z\|_2\). If a cell has coordinate widths \(h_1,\ldots,h_d\), its Euclidean diameter is at most \((\sum_{j=1}^d h_j^2)^{1/2}\). Thus the function's oscillation on that cell is bounded by \(L(\sum_j h_j^2)^{1/2}\). Squaring this bound gives a direct squared-error approximation bound.

For the cell-mean claim, compare the value \(m(x)\) with an average of \(m(X)\) over the same cell. The mean is not necessarily the value at the center, but it cannot be farther from \(m(x)\) than the largest within-cell difference. This argument requires no density or uniformity assumption on \(X\).

Anisotropic Smoothness

A single Lipschitz constant treats all directions alike. Many functions instead vary at different rates by coordinate. For \(0<\beta_j\le 1\), suppose that \[ |m(x)-m(z)|\le \sum_{j=1}^d L_j|x_j-z_j|^{\beta_j} \] for all \(x,z\in[0,1]^d\), with constants \(L_j\ge 0\). The exponents \(\beta_j\) and constants \(L_j\) describe coordinate-specific smoothness and scale. A smaller \(\beta_j\), or a larger \(L_j\), generally calls for more resolution in coordinate \(j\).

To verify the first inequality, take any \(x\) in a cell \(C\) with representative \(x_C\). Each coordinate difference is at most \(h_j\), so the assumed smoothness condition gives \(|m(x)-m(x_C)|\le\sum_j L_jh_j^{\beta_j}\). For the cell mean, condition on the cell and let \(X'\) have the conditional distribution of \(X\) there. Then \[ |m(x)-E[m(X')\mid X'\in C]| \le E[|m(x)-m(X')|\mid X'\in C] \le \sum_j L_jh_j^{\beta_j}. \] This holds for almost every \(x\) in each positive-probability cell. Squaring and averaging proves the stated squared-error bound.

In particular, if \(m\) is \(L\)-Lipschitz in Euclidean distance, it also satisfies the coordinatewise bound with \(\beta_j=1\) and \(L_j=L\): the inequality \(\|x-z\|_2\le\sum_j|x_j-z_j|\) gives the claim. This recovers a bound in terms of the sum of cell widths. The Euclidean-diameter bound can be sharper, but both show that reducing widths in important directions improves approximation.

How to Allocate a Leaf Budget

A Cartesian grid with \(N_j\) equal intervals in coordinate \(j\) has \(\prod_jN_j\) cells and widths \(h_j=1/N_j\). Such a grid can be formed by recursive axis-aligned splits: cut each coordinate into its intervals, applying the needed cuts within the resulting cells. A binary tree with \(K\) leaves has \(K-1\) internal splits, so the product of the interval counts is also the leaf budget for this construction.

The anisotropic bound for this grid is controlled by \(\sum_j L_jN_j^{-\beta_j}\). Treating \(N_j\) temporarily as positive real numbers and fixing \(\prod_jN_j=K\), one can see the preferred allocation by minimizing this sum. Set \(u_j=\log N_j\); the constraint is \(\sum_j u_j=\log K\). At an interior minimum, a Lagrange multiplier \(\lambda\) gives \[ \beta_jL_jN_j^{-\beta_j}=\lambda \quad\text{for each }j. \] Thus the terms do not generally receive equal numbers of intervals: the balance is between their smoothness-weighted marginal reductions. In particular, when all \(L_j\) are positive and the unconstrained solution has \(N_j\ge1\), it satisfies \[ N_j=\left(\frac{\beta_jL_j}{\lambda}\right)^{1/\beta_j}, \qquad \prod_jN_j=K. \] Actual trees use integer counts and may use dyadic subdivisions, so this continuous calculation guides the allocation rather than specifying an exact tree in every case.

Cell Means and Finite Squared-Error Risk

The preceding approximation bounds concern a bounded smooth function \(m\) and its cellwise average; they do not, by themselves, assert that a response-based predictor has finite squared-error risk. For that prediction claim, suppose \(m(X)=E[Y\mid X]\) and \(E[Y^2]<\infty\). Then \(m(X)\) is square-integrable, and the partition mean \(m_{\mathcal P}(X)=E[Y\mid\sigma(\mathcal P)]\) is also square-integrable. It is the best squared-error predictor among functions constant on each cell.

For the proof, write \(Y-g=(Y-m_{\mathcal P})+(m_{\mathcal P}-g)\), square, and take expectations. The cross term is zero because \(m_{\mathcal P}-g\) is measurable with respect to the partition, while \(E[Y-m_{\mathcal P}\mid\sigma(\mathcal P)]=0\). Hence \[ E[(Y-m_{\mathcal P})(m_{\mathcal P}-g)] =E[E[Y-m_{\mathcal P}\mid\sigma(\mathcal P)](m_{\mathcal P}-g)] =0. \] All terms are integrable by square-integrability and the Cauchy–Schwarz inequality. The identity follows, and its second term is nonnegative. \(\square\)

Common Mistake

• Wrong reasoning: “The conditional mean in each cell always minimizes squared-error risk, so no moment assumption is needed.” A conditional mean may exist when \(Y\) has a finite first moment but an infinite second moment; in that case the squared-error risks need not be finite, and the usual finite-risk projection argument does not apply.
• Correction: Require \(E[Y^2]<\infty\) for the finite-risk best-predictor identity. Keep this separate from smoothness-based approximation bounds for \(m\), which can be established without a second-moment assumption on \(Y\).
• Wrong reasoning: “A tree with the same number of leaves has the same approximation quality, whatever its split directions.” Leaf count alone does not determine cell widths or function variation within cells.
• Correction: Track coordinate widths and smoothness. Allocate more splits to coordinates with larger or less regular changes, and avoid spending splits on directions with negligible variation when the goal is approximation.