Diverse Parallel Boosting Rounds Under Heavy-Tailed Label Noise

Gradient boosting builds a model one small tree at a time, and each tree corrects the errors left by all earlier trees. That chain is the reason boosting is accurate, and also the reason it is slow: tree 50 cannot start until tree 49 is done. The obvious shortcut is to train $K$ trees at once against the same current errors. It works poorly because the $K$ trees are fitted to the same targets and learn nearly the same correction, so adding them overshoots. In the vocabulary of ensembles, the concurrent trees lack diversity. When the labels contain heavy-tailed noise (occasional huge errors, as in Student's $t$ or Cauchy noise rather than Gaussian), every one of the $K$ trees is also pulled toward the same few outliers.

We propose to make concurrent boosting work by deciding which data each concurrent tree sees. In each round, the training points are split into $K$ disjoint subsamples. Points are drawn with probability proportional to a redescending influence score, a robust measure of how much each point should move the model that falls back toward zero for extreme residuals, so outliers are rarely sampled. The split is also arranged so the $K$ trees correct different parts of the current error. A cheap $K\times K$ robust least-squares step then sets how much each tree contributes. The claim is that one parallel round of this kind replaces most of $K$ sequential rounds, and that the gain holds under heavy-tailed noise only when the sampling weights redescend. If both hold, the number of sequential stages drops by close to $K$, test error on clean labels stays as good as robust sequential boosting, and the subsample sizes stay small.

Core Claim and How It Differs From Prior Work

The proposal treats the four directions unevenly. The sequential bottleneck is the target. Representative subsampling is the mechanism. The accuracy-diversity trade-off is the quantity the mechanism has to control. Heavy-tailed noise is the regime where naive versions of the mechanism break.

Three pieces of prior work motivate the design. Algorithms and hardness results for parallel large margin learning proves that with black-box weak-learner queries, boosting needs $\Omega(\gamma^{-2}\log(1/\epsilon))$ sequential stages no matter how many parallel queries are made. This constrains our ambitions. We do not claim to beat that bound. We open the black box by choosing each learner's data and re-combining learners after fitting, which is the kind of departure from the oracle model the same paper shows is necessary. Our target is a constant-factor reduction in rounds in practice, not an asymptotic one.

Multicalibration as Boosting for Regression supplies the closest existing method. Its LSBoost splits the data by the current model's discretized prediction value and fits squared-error regressors in parallel on each level set, reporting speedups "often 2x to 8x faster with large ensembles" on Folktables income data. Our approach differs in three ways. Our partition is chosen to make the concurrent learners complementary, not to follow prediction level sets. We draw subsamples inside the partition rather than using every point. Our fitting and combination are robust, whereas LSBoost uses squared error and is described as fragmenting the data and overfitting with expressive learners.

Probabilistic Gradient Boosting Machines shows boosting with Student's $t$ and Laplace likelihoods at the 10.5-million-sample scale on GPU, but its rounds remain strictly sequential.

Two papers supply the subsampling machinery. Optimal Subsampling with Influence Functions shows that sampling proportional to influence-function norms, with inverse-probability weights, minimizes asymptotic variance for generalized linear models. It reaches uniform-sampling accuracy on CASP with "1/3 to 1/2 of the data." Robust Gradient-Based Markov Subsampling shows why naive gradient-based sampling fails under heavy-tailed noise: on Online News Popularity at a 0.1% ratio, gradient sampling reaches estimation error 36.4 against 18.1 for uniform and 11.4 for its small-gradient Markov chain.

Both of these papers address one-shot estimation of a single convex model. Neither addresses boosting, concurrency, or diversity. We replace the Markov chain, which adds sequential burn-in that would reintroduce the bottleneck, with independent draws from a closed-form robust influence score.

Two papers motivate using data allocation to create diversity. SharpBalance shows that routing different data subsets to different ensemble members restores diversity in deep classifiers at about 1% overhead, but it relies on a sharpness heuristic for image networks. Orthogonal Gradient Boosting removes redundancy by projecting each new rule away from the span of the existing ensemble, at a cost of being 2x to 5x slower. We take SharpBalance's idea of making diversity through data allocation and OGB's goal of non-redundant additions. We obtain non-redundancy through disjoint, complementary subsamples followed by a small re-weighting step, not through projection over the full data.

Research Program

At round $t$ the current ensemble $F_t$ has residuals $r_i = y_i - F_t(x_i)$ and a running robust scale $\hat\sigma$. Under a Student's $t$ loss with $\nu$ degrees of freedom, the per-point gradient is

$$\psi_\nu(r_i) = \frac{(\nu+1)\, r_i}{\nu\hat\sigma^2 + r_i^2},$$

which rises with $|r_i|$ for moderate residuals and decays to zero for extreme ones. This is the redescending behavior described in Robust Survey Aggregation with Student-t Distribution and Sparse Representation.

Each point gets the sampling score $s_i = \max(\alpha, |\psi_\nu(r_i)|)$, where the floor $\alpha$ keeps inverse-probability weights finite. Choosing $\alpha$ is one of the open tuning problems the file identifies, and we will study it directly.

The allocation step runs in two stages. First, points are grouped into $K$ regions by a cheap clustering of (features, sign and size of $\psi_\nu$), in the spirit of the seed-then-assign clustering approaches in the file. Second, each concurrent tree $h_k$ receives a subsample of size $n_{sub}$ drawn from its region with probability proportional to $s_i$, and is fitted to $\psi_\nu$ targets weighted by inverse probability. Disjoint regions make the trees' corrections nearly non-overlapping by construction, which is the diversity half of the design. Redescending scores keep outliers out of every subsample, which is the robustness half.

The combination step solves for weights $\beta\in\mathbb{R}^K$ by minimizing the Student's $t$ loss of $F_t + \sum_k \beta_k h_k$ on a separate small uniform subsample, using a few iteratively reweighted least-squares steps on a $K\times K$ system. This takes the "re-optimize the weights of the new learners jointly" idea from LP-based totally corrective boosting (Boosting Revisited), but applies it only to the $K$ new learners, so it avoids the growing master-problem cost that paper reports.

The off-diagonal entries of the learners' prediction Gram matrix on this subsample give a direct measure of redundancy. We will log them every round as the diversity statistic.

On the analysis side, we will prove a per-round bound. For squared loss, the loss decrease from one combined parallel round is at least the sequential decrease of the best single learner, plus a term that grows with $K$ and shrinks with the largest correlation between concurrent learners' fitted vectors. This is a standard block-coordinate (Jacobi versus Gauss–Seidel) argument. We will then extend it to the Student's $t$ loss in a neighborhood where the loss is locally convex. We will also characterize how the score floor $\alpha$ trades variance from importance weights against contamination from outliers, using a contamination model with a known fraction of Cauchy-distributed labels.

Baselines

The naive reference point is standard sequential gradient boosting with squared loss and uniform row subsampling, run on the same tree depth, learning rate grid, and total tree budget. It shows what is at stake on both accuracy and wall-clock.

The strongest accuracy competitor is robust sequential boosting: PGBM's autodiff path with a Student's $t$ loss (PGBM), plus a Huber-loss sequential booster. These represent the best quality one can get while still paying the full sequential cost. The relevant reported number is PGBM's 15% average CRPS improvement over NGBoost and 20% RMSE improvement on UCI benchmarks. No reported result was found on Lacuna for PGBM or any boosting method under injected heavy-tailed label noise, so we will establish this baseline ourselves.

Beating it means matching its clean-label test RMSE and MAE within one standard error over seeds, while using at least $K/2$ times fewer sequential stages and less wall-clock time at equal hardware.

The strongest parallelism competitor is LSBoost (Multicalibration as Boosting for Regression), whose reported figure is the 2x to 8x speedup over gradient boosting on Folktables. We will also run a Huber-loss variant of LSBoost so its lack of robustness is not its only handicap. Beating it means lower clean-label error at equal or better speed once label noise has $\nu \le 3$, with no loss on clean data.

Three ablations isolate the proposal's ingredients. The first gives the $K$ concurrent trees disjoint uniform random subsamples of the same size, removing the influence scores. The second keeps the influence scores but uses the non-redescending score $|r_i|$, which shows whether redescending matters. The third replaces the $K\times K$ combination with fixed weights $1/K$.

All methods get the same data splits, the same per-method budget of 30 hyperparameter configurations chosen on a validation set with clean labels, and the same hardware. Results are reported over five seeds.

Why not just…?

Why not just use LightGBM or XGBoost with a Huber loss and row subsampling, sequentially? This is the most serious threat. Inside a single tree, histogram construction already parallelizes well, so for medium datasets on one machine the sequential chain may cost little in wall-clock time. We take this seriously by reporting two separate quantities: sequential stages to reach a target loss, and wall-clock time. We also test the regime where per-tree parallelism saturates, namely many shallow trees on Higgs-scale data spread across workers. If the optimized sequential booster wins on wall-clock even there, the honest conclusion is that the contribution is limited to the stage count, and we will say so. Huber's gradient is bounded but does not decay to zero (On Mean Absolute Error for Deep Neural Network Based Vector-to-Vector Regression), so under Cauchy-like noise we expect it to remain biased. The noise sweep tests this directly.

Why not just split the data randomly across $K$ concurrent trees and shrink the learning rate by $K$? Random disjoint splits already give some diversity, and shrinkage controls overshoot. This is exactly the first ablation. If it matches the full method, the clustering and influence scores are unnecessary and the idea reduces to a known trick. The evidence that it might fall short comes from the subsampling literature: uniform draws need 2x to 3x more data on CASP (Optimal Subsampling with Influence Functions) and lose to robust non-uniform draws at small ratios on Online News Popularity (Robust Gradient-Based Markov Subsampling). Those results are for linear models, so boosting must be checked separately.

Why not just bag several robust sequential boosters? Bagging parallelizes across ensemble members but does not shorten any member's chain, so time to a given accuracy is unchanged. Random restarts also often converge to the same decision boundaries, as the Ionosphere comparison shows (AUC 0.87 against 0.96 for LIT in Ensembles of Locally Independent Prediction Models). We include bagged PGBM at matched total compute as an additional comparison.

Proposed Experiments

The main testbeds are regression datasets from the file. Folktables income provides the LSBoost comparison. CASP and Wave Energy Converters connect to the subsampling literature. SARCOS provides robotics dynamics regression. Higgs, treated as a regression target on its continuous columns or as a classification problem with logistic loss, provides the scale test. On each dataset we inject label noise into training labels only, drawn from Student's $t$ with $\nu\in\{1, 2, 3, 10\}$ and from a contamination model with 0% to 10% Cauchy shocks, and we evaluate on clean held-out labels.

Metrics are clean-label RMSE and MAE, sequential stages to reach the robust sequential baseline's final loss, wall-clock time for $K\in\{2,4,8,16\}$, and the per-round redundancy statistic, meaning the mean absolute correlation between concurrent trees' fitted vectors.

Three checks decide whether the idea holds. First, the redundancy statistic should predict how close a parallel round comes to $K$ sequential rounds, as the per-round bound implies. If it does not, the diversity explanation is wrong. Second, the gap between redescending and non-redescending scores should be near zero at $\nu=10$ and grow as $\nu$ falls. If it does not grow, heavy-tail handling is not why the method works. Third, the full method must beat the random-split ablation at $K\ge 8$. If it does not, we drop the allocation machinery and report shrunken random-split parallel boosting as the practical finding.