SGLB: Stochastic Gradient Langevin Boosting

Aleksei Ustimenko, Liudmila Prokhorenkova

Abstract

This paper introduces Stochastic Gradient Langevin Boosting (SGLB) - a powerful and efficient machine learning framework that may deal with a wide range of loss functions and has provable generalization guarantees. The method is based on a special form of the Langevin diffusion equation specifically designed for gradient boosting. This allows us to theoretically guarantee the global convergence even for multimodal loss functions, while standard gradient boosting algorithms can guarantee only local optimum. We also empirically show that SGLB outperforms classic gradient boosting when applied to classification tasks with 0-1 loss function, which is known to be multimodal.

Introduction

Gradient boosting (GB) is widely considered the "gold standard" for tabular data, forming the backbone of popular libraries such as XGBoost, LightGBM, and CatBoost. However, standard GB implementations face a significant theoretical and practical hurdle: they are primarily designed for convex loss functions. In the presence of non-convex or multimodal loss landscapes—where the error surface contains numerous local optima—standard GB often converges to suboptimal solutions.

Furthermore, while stochastic variants of GB are frequently employed to enhance performance, there has been a notable lack of rigorous theoretical guarantees regarding their generalization capabilities on non-convex objectives. This research introduces SGLB to bridge this gap, providing a globally convergent boosting algorithm with provable generalization bounds.

Methodology

The proposed framework, SGLB, integrates Gradient Boosting with Stochastic Gradient Langevin Dynamics (SGLD). SGLD is an optimization technique that injects controlled Gaussian noise into gradient updates, enabling the optimizer to escape local minima and converge toward a global optimum.

To adapt this to the boosting paradigm, the authors implement three primary modifications:

  1. Model Shrinkage: $L_2$ regularization is applied at each step, shrinking the current model before the addition of a new weak learner.
  2. Gradient Noise: Gaussian noise is injected directly into the stochastic gradient estimates used for training each new tree.
  3. Selection Noise: Noise is added to the tree structure selection process, promoting broader exploration of the model space.

The authors demonstrate that as the learning rate approaches zero, this discrete process approximates a continuous Stochastic Differential Equation (SDE) that eventually settles into a global optimum.

Experimental Setup

The efficacy of SGLB was evaluated across both synthetic and real-world benchmarks:

  • Synthetic Data: A 3D dataset characterized by high noise and multimodality was used to verify the algorithm's global convergence properties.
  • Real-World Benchmarks: Ten diverse datasets were utilized, ranging from large-scale (Higgs with 11M examples, Epsilon, Click) to medium and small-scale (Adult, Amazon, Churn, etc.).

Key Results

The empirical evaluation highlights several advantages of the SGLB framework:

  • Superiority on 0-1 Loss: By utilizing a Smooth Loss Approximation (SLA), SGLB consistently outperformed standard Stochastic Gradient Boosting (SGB) across most real-world datasets. On datasets like "Adult" and "Amazon," SGLB achieved statistically significant improvements in accuracy.
  • Robustness on Large-Scale Data: On massive datasets such as Higgs and Epsilon, SGLB surpassed standard methods even when using traditional convex LogLoss. This suggests that Langevin noise serves as an effective regularizer, mitigating overfitting.
  • Global Convergence: On synthetic multimodal data, SGLB successfully identified the global optimum, whereas standard GB and SGB remained trapped in inferior local minima.
Comparison of 0-1 loss across different boosting approaches on a representative dataset.

Discussion and Future Work

SGLB represents a significant step toward optimizing "unoptimizable" objectives like the 0-1 loss directly. By adapting noise injection techniques from deep learning to decision trees, the authors provide a robust theoretical foundation for boosting.

However, several areas for future research remain:

  • Independence Assumption: The current generalization proofs assume linear independence of weak learners, which is restrictive for decision trees.
  • Computational Efficiency: While theoretically efficient, the practical overhead of noise sampling at every iteration warrants further investigation.
  • Advanced Dynamics: Incorporating momentum-based methods, such as Hamiltonian Monte Carlo, could potentially accelerate convergence.

The SGLB method is currently available as a feature in the CatBoost library via the langevin=True parameter.

Summary updated

Abstract

This paper introduces Stochastic Gradient Langevin Boosting (SGLB) - a powerful and efficient machine learning framework that may deal with a wide range of loss functions and has provable generalization guarantees. The method is based on a special form of the Langevin diffusion equation specifically designed for gradient boosting. This allows us to theoretically guarantee the global convergence even for multimodal loss functions, while standard gradient boosting algorithms can guarantee only local optimum. We also empirically show that SGLB outperforms classic gradient boosting when applied to classification tasks with 0-1 loss function, which is known to be multimodal.
BibTeX
@inproceedings{ustimenko2021sglb,
  author = {Aleksei Ustimenko and Liudmila Prokhorenkova},
  title = {{SGLB: Stochastic Gradient Langevin Boosting}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=EeXTZY5zk90},
}
Figure