Gradient Boosting & AdaBoost in C++

June 2026 · 22 min read

The random forest in Part 3 grows its trees independently and averages them. Boosting takes the opposite approach: trees are grown in sequence, and each new tree is told to fix the mistakes the current ensemble is still making. This part builds both classic forms from scratch, reusing the regression tree from Part 2: gradient boosting for regression, and AdaBoost for classification. The conceptual derivations live in the companion Decision Trees · Boosting & AdaBoost notes.

Gradient Boosting: Fit the Residuals

Start the prediction at the mean of the targets, $F_0 = \bar{y}$. Then repeatedly add a small correction. Tree $m$ is trained not on $y$ but on the current residuals $r_i = y_i - F(x_i)$, and the ensemble is nudged toward it by a learning rate $\nu$:

This is gradient descent in function space. For squared loss $L = \tfrac12 (y - F)^2$, the negative gradient with respect to the prediction is exactly the residual:

The GBM, Built on the Regression Tree

Each booster is a shallow regression tree (depth 3 here) so that no single tree does too much. The RegTree is the same squared-error tree from Part 2.

struct GBM {
    int M; double lr;                 // number of trees, learning rate
    double F0 = 0;
    vector<RegTree> trees;
    GBM(int m, double l) : M(m), lr(l) {}

    void fit(const Matrix& X, const vector<double>& y) {
        int N = X.size();
        F0 = accumulate(y.begin(), y.end(), 0.0) / N;     // start at the mean
        vector<double> F(N, F0);
        for (int m = 0; m < M; ++m) {
            vector<double> r(N);
            for (int i = 0; i < N; ++i) r[i] = y[i] - F[i]; // residual = neg. gradient
            RegTree t(/*depth*/3, /*minSamples*/5);
            t.fit(X, r);                                    // fit tree to residuals
            for (int i = 0; i < N; ++i) F[i] += lr * t.predict(X[i]);
            trees.push_back(move(t));
        }
    }
    double predict(const vector<double>& x) const {
        double f = F0;
        for (auto& t : trees) f += lr * t.predict(x);       // sum of corrections
        return f;
    }
};

On the same noisy sine target from Part 2, with $\nu = 0.1$, adding trees steadily drives the test RMSE down:

AdaBoost: Reweight the Mistakes

AdaBoost classifies with labels in $\{-1, +1\}$ and combines weak learners, here decision stumps (depth-one trees). It keeps a weight $w_i$ on every sample, starting uniform. Each round it picks the stumps that minimizes the weighted error $\varepsilon$, gives it a vote

then multiplies the weight of each point by $e^{-\alpha\, y_i\, h(x_i)}$ and renormalizes. Correctly classified points get lighter; misclassified points get heavier, so the next stump is forced to focus on them. The final prediction is the sign of the weighted vote $\sum_t \alpha_t h_t(x)$.

The AdaBoost Code

struct Stump {
    int feature = 0; double threshold = 0; int polarity = 1; double alpha = 0;
    int predict(const vector<double>& x) const {
        return (x[feature] > threshold) ? polarity : -polarity;
    }
};
struct AdaBoost {
    int T; vector<Stump> stumps;
    AdaBoost(int t) : T(t) {}

    void fit(const Matrix& X, const vector<int>& y) {
        int N = X.size(), D = X[0].size();
        vector<double> w(N, 1.0 / N);
        for (int t = 0; t < T; ++t) {
            // find the stump with the lowest weighted error
            Stump best;
            double bestErr = 1e9;
            for (int f = 0; f < D; ++f) {
                vector<double> vals;
                for (auto& row : X) vals.push_back(row[f]);
                sort(vals.begin(), vals.end());
                vals.erase(unique(vals.begin(), vals.end()), vals.end());
                for (size_t k = 0; k + 1 < vals.size(); ++k) {
                    double thr = (vals[k] + vals[k + 1]) / 2;
                    for (int pol : {1, -1}) {
                        double err = 0;
                        for (int i = 0; i < N; ++i) {
                            int pred = (X[i][f] > thr) ? pol : -pol;
                            if (pred != y[i]) err += w[i];
                        }
                        if (err < bestErr) {
                            bestErr = err;
                            best.feature = f;
                            best.threshold = thr;
                            best.polarity = pol;
                        }
                    }
                }
            }
            double eps = max(1e-10, min(1 - 1e-10, bestErr));
            best.alpha = 0.5 * log((1 - eps) / eps);         // stump's vote
            double Z = 0;
            for (int i = 0; i < N; ++i) {                    // reweight + renormalize
                w[i] *= exp(-best.alpha * y[i] * best.predict(X[i]));
                Z += w[i];
            }
            for (int i = 0; i < N; ++i) w[i] /= Z;
            stumps.push_back(best);
        }
    }
    int predict(const vector<double>& x) const {
        double s = 0;
        for (auto& st : stumps) s += st.alpha * st.predict(x);
        return s >= 0 ? 1 : -1;
    }
};

The test data is deliberately not linearly separable: a tight blob at the center (class $-1$) surrounded by a ring (class $+1$). A single stump can only cut on one axis, so it barely beats a coin flip; stacking them carves out the ring.

Bagging versus Boosting

The two ensembles in Parts 3 and 4 pull on different levers. A forest reduces variance by averaging many independent low-bias trees, so its trees are deep and trained in parallel. Boosting reduces bias by adding many shallow high-bias learners in sequence, each correcting the last. That is why the GBM and AdaBoost here use depth-3 trees and stumps, while the forest used depth-20 trees.