Piecewise-Polynomial Leaves and Local Approximation

From Constant Leaves to Polynomial Leaves

A regression tree can use more than a constant prediction in each leaf. If the regression function bends smoothly within a cell, a local polynomial can represent that curvature instead of requiring the partition to split the cell into smaller pieces. This tutorial studies the approximation side of that choice: how well can polynomials of a chosen degree approximate a smooth function on a fixed partition?

The bound developed below is deterministic once the partition and regression function are fixed. It does not say how accurately data estimate the polynomial coefficients, or how well a data-selected tree performs. Those are separate questions. Here the issue is the best possible squared approximation error within a specified piecewise-polynomial class.

A polynomial of total degree at most \(q\) is a linear combination of monomials \(x_1^{\alpha_1}\cdots x_d^{\alpha_d}\) for nonnegative integer indices satisfying \(\alpha_1+\cdots+\alpha_d\le q\). For example, when \(d=2\) and \(q=1\), each leaf has an affine prediction \(a+b_1x_1+b_2x_2\). When \(q=2\), quadratic terms such as \(x_1^2\) and \(x_1x_2\) are also allowed.

A Taylor Bound for a Fixed Partition

For a smooth function, Taylor expansion supplies a particular polynomial candidate on each cell. Comparing the best local polynomial with this candidate gives an upper bound for \(A_q(\mathcal{P})\). We use Euclidean distance and write \(\operatorname{diam}(C)=\sup_{x,z\in C}\|x-z\|\).

Proof. Choose an anchor \(a_j\in C_j\) for each cell. On \(C_j\), use the degree-\(q\) Taylor polynomial of \(m\) about \(a_j\), denoted \(T_{q,a_j}\). For \(x\in C_j\), set \(u=x-a_j\) and consider the one-variable function \(\phi(t)=m(a_j+tu)\), \(0\le t\le1\). Convexity ensures that the whole line segment lies in the region where the derivative assumptions hold. The one-variable Taylor formula with integral remainder gives \[ m(x)-T_{q,a_j}(x)=\frac{1}{q!}\int_0^1(1-t)^q\phi^{(q+1)}(t)\,dt. \] The chain rule gives \(\phi^{(q+1)}(t)=D^{q+1}m(a_j+tu)[u,\ldots,u]\). Thus its absolute value is at most \(M\|u\|^{q+1}\). Since \(\int_0^1(1-t)^q\,dt=1/(q+1)\), it follows that \[ |m(x)-T_{q,a_j}(x)|\le \frac{M}{(q+1)!}\|x-a_j\|^{q+1} \le \frac{M}{(q+1)!}\operatorname{diam}(C_j)^{q+1}. \] The function formed by using \(T_{q,a_j}\) on each cell is an admissible piecewise-polynomial predictor. Squaring the bound, integrating over each cell, and summing yields the stated upper bound for this candidate's error. The infimum over all admissible predictors cannot be larger. \(\square\)

For affine leaves, \(q=1\), the condition is a bound on the Hessian in every direction. If \(|D^2m(z)[v,v]|\le M\|v\|^2\), the pointwise Taylor remainder is at most \(M\|x-a_j\|^2/2\). Squaring introduces the coefficient \(M^2/4\), not \(M/4\) or \(M^2/16\). In one dimension, a sufficient condition is \(|m''(x)|\le M\).

Multivariate Cells and Diameter

The same argument applies in several dimensions. The derivative condition in the theorem measures curvature along every direction, while the cell diameter controls how far a point can lie from the Taylor anchor. For axis-aligned rectangular tree cells, the Euclidean diameter is the square root of the sum of squared side lengths. A long, narrow rectangle can therefore have a substantial diameter even if one of its sides is small.

What Increasing Degree or Refining Cells Can Guarantee

The Taylor bound makes the role of degree explicit. Under its derivative condition, degree \(q\) gives a pointwise remainder of order \(\operatorname{diam}(C)^{q+1}\), and a squared-error bound of order \(\operatorname{diam}(C)^{2(q+1)}\), multiplied by a derivative-dependent constant. This is an approximation statement, not an automatic guarantee that a fitted tree will improve in practice: estimating more coefficients can require more data.

Proof. Every polynomial of degree at most \(q\) is also a polynomial of degree at most \(q+1\). Thus every predictor admissible for \(A_q(\mathcal{P})\) is admissible for \(A_{q+1}(\mathcal{P})\), so taking the infimum over the larger class cannot increase the error. For refinement, take any degree-\(q\) predictor on \(\mathcal{P}\) and restrict its polynomial on each original cell to each of the smaller cells in \(\mathcal{P}'\). The restricted functions remain degree at most \(q\), and the resulting predictor has exactly the same predictions, hence the same error. Taking infima proves the second inequality. \(\square\)

The proposition concerns the best approximation in a class. It does not say that estimated predictions have lower prediction error after increasing degree or refining a tree. The enlarged class can be harder to estimate from finite data. Separating approximation from estimation is essential when interpreting the Taylor bound.

Common Mistake: Losing the Squared Remainder Constant

A frequent error is to correctly obtain a Taylor remainder bound \(M h^2/2\) for affine leaves, then report \(M h^4/4\) or \(M^2h^4/4\) incorrectly after squaring. The square must apply to the entire coefficient: \[ \left(\frac{M}{2}h^2\right)^2=\frac{M^2}{4}h^4. \] For \(m(x)=x^2\), \(M=2\), so the coefficient is \(2^2/4=1\), and the bound is \(h^4\). It is not \(h^4/4\). Another mistake is to use cell width as though it were a radius around the Taylor anchor. The theorem uses \(\|x-a\|\le\operatorname{diam}(C)\); a smaller radius can be used only when it is verified for the chosen anchor and cell.