The most remarkable aspect of boosting is how simple components combine to create powerful predictors. A single decision stump—a tree with just one split—is barely better than random guessing. Yet hundreds of stumps, carefully combined, can rival the performance of deep neural networks on tabular data.

The mathematical structure enabling this alchemy is the additive model: the final prediction is simply a weighted sum of base learner outputs. This seemingly simple constraint has profound implications for how we train boosted ensembles, analyze their behavior, and regularize them to prevent overfitting.

An additive model expresses the prediction function as a sum of simpler component functions, called basis functions or base learners.

Formal Definition:

$$F(x) = \sum_{m=1}^{M} \beta_m \cdot b(x; \gamma_m)$$

where:

• F(x) is the final prediction for input x
• M is the number of base learners (terms)
• βₘ ∈ ℝ are the weights (coefficients) for each term
• b(x; γₘ) is the m-th base learner with parameters γₘ
• γₘ parameterizes the base learner (e.g., tree structure for decision trees)

The Structure:

Each base learner b(x; γ) maps input x to a scalar output. The parameters γ can be simple (a threshold value for a stump) or complex (the complete structure of a decision tree). The final model is the sum of all base learners, each scaled by its weight β.

A natural question arises: how powerful are additive models? Can they approximate any function, or are they fundamentally limited?

Universal Approximation:

With sufficiently flexible base learners and enough terms, additive models can approximate any continuous function to arbitrary precision. This is a form of the universal approximation property.

Theorem (Informal): If the base learner class ℋ is "rich enough" (e.g., contains all indicator functions 𝟙(x ∈ R) for measurable regions R), then additive models over ℋ can approximate any integrable function.

Practical Implications:

For boosted decision trees:

1. Stumps (depth-1 trees): Can represent any function on the training data by using axis-aligned step functions. The approximation quality depends on M.

2. Shallow trees (depth 2-4): Each tree captures interactions between a few features. The ensemble captures complex multi-way interactions through composition.

3. Deeper trees: More expressive per-tree, but risk overfitting. Usually depth 4-8 is optimal for boosting.

How Additive Models Build Complexity:

Consider approximating a complex 2D function using additive stumps. Each stump partitions the plane with a single axis-aligned cut, assigning different constant values to each side.

Iteration 1: One cut creates 2 regions Iteration 2: Another cut creates up to 4 regions
Iteration M: M cuts can create up to M+1 regions along each axis

By summing many stumps with different orientations and thresholds, we can approximate smooth curves, sharp boundaries, and complex contours. The granularity improves with M.

Example: Approximating x²

Suppose we want to approximate f(x) = x² on [0, 1] using stumps:

• Stump 1: b₁(x) = 0.1 · 𝟙(x > 0.1) ≈ small step
• Stump 2: b₂(x) = 0.1 · 𝟙(x > 0.2) ≈ another step
• ...
• Stump 10: b₁₀(x) = 0.1 · 𝟙(x > 0.9) ≈ final step

The sum Σᵢ bᵢ(x) is a staircase approximating x². More stumps = finer staircase = better approximation.

Additive models can be understood through the lens of basis function expansion—a foundational concept in approximation theory and functional analysis.

The Idea:

Just as any vector in ℝ³ can be expressed as a linear combination of basis vectors {e₁, e₂, e₃}, any function (in a suitable function space) can be expressed as a combination of basis functions.

Classical Examples:

Fourier Series: $$f(x) = a_0 + \sum_{n=1}^{\infty} \left[a_n \cos(nx) + b_n \sin(nx)\right]$$

Basis functions: {1, cos(x), sin(x), cos(2x), sin(2x), ...}

Polynomial Expansion: $$f(x) = \sum_{k=0}^{K} a_k x^k$$

Basis functions: {1, x, x², x³, ...}

Boosting Analogy:

In boosting, the base learners form an adaptively-chosen basis. Unlike fixed bases (Fourier, polynomial), the boosting basis is determined by the data and the training procedure.

Why Adaptive Bases Excel:

Consider approximating a function with a sharp spike at x = 0.73. A polynomial basis would need many high-degree terms to capture this localized feature. A Fourier basis would exhibit Gibbs phenomenon (ringing artifacts).

A boosted stump basis, however, would naturally place thresholds near 0.73, focusing basis function resolution exactly where it's needed. The basis adapts to the target function's structure.

The Trade-off:

Adaptive bases are more powerful but harder to fit:

• Must search over both basis structure (γ) and coefficients (β)
• No closed-form solution; requires iterative optimization
• Risk of overfitting if not properly regularized

Boosting navigates this trade-off through the greedy stagewise procedure we'll examine next.

Given the additive model structure F(x) = Σₘ βₘb(x; γₘ), how do we find the optimal parameters {βₘ, γₘ} for m = 1, ..., M?

The Objective:

$$\min_{{\beta_m, \gamma_m}{m=1}^{M}} \sum{i=1}^{n} \ell\left(y_i, \sum_{m=1}^{M} \beta_m b(x_i; \gamma_m)\right)$$

This is generally a challenging optimization problem because:

1. Non-convexity in γ: The base learner parameters (e.g., tree structure) make the problem highly non-convex
2. Combinatorial explosion: With M terms, we have M pairs of (β, γ) to optimize jointly
3. Coupling: The optimal β₁ depends on what γ₂...γₘ are, and vice versa

Approaches to Optimization:

Forward Stagewise Additive Modeling (FSAM):

The dominant approach in boosting is forward stagewise optimization. Instead of optimizing all M terms jointly, we:

1. Start with F₀(x) = 0 (or a constant)
2. For m = 1, 2, ..., M:
   • Fix all previous terms {β₁,...,βₘ₋₁} and {γ₁,...,γₘ₋₁}
   • Find the best new term (βₘ, γₘ) to add
   • Update: Fₘ(x) = Fₘ₋₁(x) + βₘb(x; γₘ)

The Stagewise Optimization:

At stage m, we solve:

$$(\beta_m, \gamma_m) = \arg\min_{\beta, \gamma} \sum_{i=1}^{n} \ell(y_i, F_{m-1}(x_i) + \beta \cdot b(x_i; \gamma))$$

This is a greedy approach: each step optimizes myopically, adding the single best term given the current model. Previous terms are never revised.

The additive structure provides natural regularization opportunities. Since the model is a sum of base learners, we can control complexity by constraining:

1. Number of terms M (early stopping)
2. Complexity of each term (tree depth, leaf count)
3. Magnitude of coefficients βₘ (shrinkage/L1/L2)
4. Combination of above

Shrinkage (Learning Rate):

Instead of adding βₘb(x; γₘ) at each step, we add a shrunken version:

$$F_m(x) = F_{m-1}(x) + u \cdot \beta_m b(x; \gamma_m)$$

where ν ∈ (0, 1] is the shrinkage factor (learning rate). Smaller ν means:

• Each term contributes less
• More terms needed for same training accuracy
• Better generalization (empirically verified)
• Slower training

Why Shrinkage Works:

Shrinkage works through a mechanism similar to L2 regularization. Mathematical analysis shows that:

$$F_M(x) = \sum_{m=1}^{M} u \cdot \beta_m b_m(x) = u \sum_{m=1}^{M} \beta_m b_m(x)$$

With small ν, the final model magnitude is constrained. Moreover, shrinkage allows more terms to contribute, averaging out the idiosyncrasies of any single base learner.

Intuition: With ν = 1.0, each tree greedily grabs as much signal as possible, including noise. With ν = 0.1, each tree only takes 10% of available signal, leaving room for subsequent trees to capture different aspects. The averaging effect reduces variance.

The Trade-off:

• More terms + shrinkage = better generalization but slower training
• Typical practice: ν ∈ [0.01, 0.3], with M = 100-10,000 depending on ν

Not all ensemble methods produce additive models. Understanding the differences reveals what makes additive structure special for boosting.

Comparison of Ensemble Structures:

Why Additive Structure Suits Boosting:

1. Incremental Updates: Adding a new term Fₘ = Fₘ₋₁ + βₘhₘ is simple when structure is additive. No need to recompute how previous terms interact.

2. Gradient Interpretation: The additive update Fₘ = Fₘ₋₁ + η·h corresponds exactly to taking a gradient step in function space.

3. Analysis: Additive models admit clean theoretical analysis. Training error bounds, convergence rates, and generalization bounds are well-understood.

4. Regularization: Smooth operators (shrinkage, early stopping) apply naturally to sums.

What Additive Structure Cannot Capture Directly:

Pure additive models cannot represent certain interaction patterns efficiently:

• Multiplicative effects: f(x) = x₁ · x₂ requires many additive terms
• XOR-like patterns: Need exponentially many stumps to capture exactly
• Complex feature interactions: Each tree term helps, but it's indirect

This is why boosting often uses shallow trees (depth 2-6) as base learners—each tree captures some feature interactions within its structure, then these are combined additively.

Additive models have a rich history in statistics, particularly in the form of Generalized Additive Models (GAMs).

Classical GAM:

$$F(x) = \beta_0 + \sum_{j=1}^{d} f_j(x_j)$$

where each fⱼ is a smooth function of the j-th feature. Unlike linear models (where fⱼ(xⱼ) = βⱼxⱼ), GAMs allow nonlinear effects while maintaining additive structure.

Key Property: Main Effects Only

Classical GAMs model only main effects—each feature contributes independently to the prediction. There are no interaction terms fⱼₖ(xⱼ, xₖ).

Boosted GAMs:

When boosting uses stumps (single-split trees) as base learners, the result is essentially a GAM:

$$F(x) = \sum_m \beta_m \cdot \mathbf{1}(x_{j_m} > t_m)$$

Each stump is a step function of one feature. The sum of stumps for feature j approximates a smooth function fⱼ(xⱼ). This connection enables interpretable gradient boosting (see: Explainable Boosting Machines, InterpretML).

GA²M: Adding Pairwise Interactions

A natural extension is to include pairwise interaction terms:

$$F(x) = \beta_0 + \sum_{j=1}^{d} f_j(x_j) + \sum_{j<k} f_{jk}(x_j, x_k)$$

This is called GA²M (Generalized Additive Model plus Interactions). It retains interpretability (can visualize each main effect and each pairwise interaction) while capturing important nonlinear interactions.

Explainable Boosting Machines (EBM):

Microsoft's InterpretML implements EBM, which is essentially boosted GA²M:

1. Round-robin boosting across features one at a time (main effects)
2. Optional second phase for pairwise interactions
3. Produces interpretable models competitive with black-box boosting

We've developed a comprehensive understanding of additive models as the structural foundation of boosting. Let's consolidate the key insights:

What's Next:

We've established that boosting builds additive models through a forward stagewise procedure. The next page examines stage-wise optimization in detail: how exactly do we find the best base learner to add at each stage? This is where the connection to gradient descent becomes algorithmic—the fitting of base learners to negative gradients.

Understanding stagewise optimization will complete the picture: functional gradient descent (the principle) + additive models (the structure) + stagewise optimization (the algorithm) together define modern gradient boosting.