Uniform Risk Bounds Over Tree Classes

Why Uniform Risk Bounds Need a Complexity Count

A tree may fit the observed sample well simply because its splits and leaf predictions were selected from many possibilities. A uniform risk bound quantifies how much the empirical risk can differ from population risk across the entire candidate class, rather than for one tree fixed in advance. The key ingredients are a finite count of candidate trees and concentration for each tree’s bounded loss.

The count must describe the class being searched. A finite set of split rules gives a direct count; a leaf budget limits how many rules a tree can use. Leaf predictions also contribute to the count if they are allowed to vary over a finite set. These details matter: partition counting alone does not automatically control every class with continuously varying split locations or leaf values.

Counting Trees Under a Leaf Budget

For a concrete count, suppose every internal node chooses from a fixed dictionary of \(J\) split rules. Each rule specifies how to send an observation to one of two ordered children. Consider full binary trees with at most \(K\) leaves, and suppose each leaf receives one label from a finite set \(\mathcal A\) of size \(q\). A tree with \(m\) leaves has \(m-1\) internal nodes: each internal node adds one leaf relative to a single-leaf tree.

The number of ordered full binary tree shapes with \(m\) leaves is the Catalan number \(C_{m-1}=\frac{1}{m}\binom{2m-2}{m-1}\). For each shape, there are at most \(J^{m-1}\) assignments of split rules to internal nodes and \(q^m\) assignments of labels to leaves. Some such assignments may produce the same predictor, or an empty cell; counting them anyway gives a valid upper bound.

A Uniform Deviation Theorem

Assume \(\mathcal G\) is a finite class of \(N\) measurable predictors, the observations are independent and identically distributed, and every loss satisfies \(0\leq \ell_g(Z)\leq1\). The bound below applies to the finite tree class just counted. Boundedness could be replaced by other tail assumptions, but then the concentration inequality would change.

Proof. Fix one predictor \(g\). Its \(n\) losses are independent random variables in \([0,1]\). Hoeffding’s inequality gives, for every \(t>0\), $$ P\bigl(|R_n(g)-R(g)|>t\bigr)\leq 2\exp(-2nt^2). $$ Taking a union bound over the \(N\) predictors, $$ P\left(\sup_{g\in\mathcal G}|R_n(g)-R(g)|>t\right) \leq 2N\exp(-2nt^2). $$ Set \(t=\sqrt{\log(2N/\delta)/(2n)}\). Then \(2N\exp(-2nt^2)=\delta\), which proves the claim. The class is finite, so the supremum is measurable. \(\square\)

Applying the theorem to the tree count replaces \(N\) by the upper bound \(N_K\). In particular, with probability at least \(1-\delta\), $$ \sup_{g\in\mathcal G_K}|R_n(g)-R(g)| \leq \sqrt{\frac{\log(2N_K/\delta)}{2n}}. $$ The dependence on the number of candidate trees is logarithmic. Increasing the tree class can worsen the guarantee, but the effect is through \(\log N_K\), not \(N_K\) itself.

Consequences for Empirical Risk Minimization

Uniform control is useful because it transfers an empirical comparison into a population-risk comparison. Let \(\hat g\) minimize \(R_n(g)\) over a finite class \(\mathcal G\), and let \(g^\star\) minimize \(R(g)\) over that class. If the uniform deviation is at most \(\varepsilon\), then $$ R(\hat g)\leq R_n(\hat g)+\varepsilon \leq R_n(g^\star)+\varepsilon \leq R(g^\star)+2\varepsilon. $$ The middle inequality follows from empirical minimization. The first and last follow from uniform deviation, once for \(\hat g\) and once for \(g^\star\). Thus empirical risk minimization is within \(2\varepsilon\) of the best population risk available in the candidate class.

Continuous Leaf Values and the Limits of Counting

Regression trees often use real-valued leaf predictions rather than a finite label set. One simple finite reduction is available when predictions lie in \([0,1]\), responses lie in \([0,1]\), and the loss is squared error. Round every leaf prediction to the nearest point on a grid in \([0,1]\) with spacing at most \(h\). If \(a\) is a leaf value and \(a'\) its rounded value, then \(|a-a'|\leq h/2\), and for any response \(y\in[0,1]\), $$ |(a-y)^2-(a'-y)^2| =|a-a'||a+a'-2y| \leq |a-a'|\cdot2 \leq h. $$ Consequently, both the empirical risk and population risk change by at most \(h\) on rounding, so the absolute deviation changes by at most \(2h\).

The qualification about the split dictionary is essential. If split locations can vary continuously, the set of possible partitions is generally not finite, and counting tree shapes alone does not bound the number of predictors. A split can move between observed covariate values without changing the sample partition while changing predictions away from the sample. Controlling that broader class requires an appropriate complexity or entropy argument, such as one based on a growth function or covering numbers; the finite-class union bound above does not provide it by itself.

Common Pitfall and Practical Meaning

A common mistake is to count only the tree topologies and then claim a uniform bound for every tree with arbitrary split locations and real-valued leaves. The topology count omits both the choices of split rules and the choices of leaf predictions. Even if the sample induces only a limited number of observed partitions, trees that agree on the sample need not have the same population risk. The correction is to state exactly what is finite, count all choices that make the candidate class distinct, and use a concentration result justified for that class.

Within a finite candidate class, the result explains a basic trade-off: allowing more leaves can make better-fitting trees available, but also increases the count \(N_K\) and therefore the uniform deviation term. A risk analysis must keep these two effects separate. The bound controls estimation across the searched class; it does not say that the best tree in that class approximates the underlying regression or classification rule well.