CoffeeBoost: Gradient Boosting Native Conformal Inference for Bayesian Optimization

Yuanhao Lai, Pengfei Zheng, Chenpeng Ji, Cheng Qiu, Tingkai Wang, Songhan Zhang, Zhengang Wang, Yunfei DuAAAI 2025 · DOI

TL;DR

This paper introduces CoffeeBoost, a novel Bayesian Optimization (BO) framework that leverages Gradient Boosting Decision Trees (GBDTs) with conformal inference to create more robust and accurate surrogate models. By moving away from the restrictive assumptions of Gaussian Processes, CoffeeBoost significantly improves performance in complex software auto-tuning tasks.

What Problem Does This Paper Address?

Bayesian Optimization (BO) is a powerful technique for optimizing expensive black-box functions, commonly used in areas like hyperparameter tuning and robotics. However, traditional BO methods often rely on Gaussian Processes (GPs) as their surrogate model. GPs make strong assumptions about the data (e.g., continuity, Gaussianity) that are frequently violated in real-world scenarios, especially when tuning complex software systems. These systems often involve high-dimensional, heterogeneous (discrete and continuous) variables with non-stationary, noisy measurements. Such violations can severely degrade the effectiveness and efficiency of GP-based BO. While tree-based models like Random Forests (RF) and Gradient Boosting Decision Trees (GBDTs) are more flexible, effectively quantifying uncertainty for GBDTs has been a long-standing challenge, hindering their full potential in BO.

Methods

CoffeeBoost addresses these limitations through two primary innovations:

  • GBDT-Native Distribution-Free Surrogate Model: Instead of GPs, CoffeeBoost uses Stochastic Gradient Boosting Ensembles (SGBE) to build its surrogate models. SGBE aggregates multiple GBDT models, offering better predictive accuracy on complex, heterogeneous data. Crucially, it employs distribution-free conformal predictive systems (CPS) to quantify probabilistic distributions. This means it doesn't assume a specific underlying data distribution, making it more robust.
  • GBDT-Native Difficulty Estimator: A key challenge in conformal inference is accurately estimating the "difficulty" of making predictions for specific data points. CoffeeBoost introduces a novel GBDT-native approach to this problem. It leverages the "residual paths" within GBDTs – the sequence of errors corrected by each new tree – to create a more adaptive and accurate difficulty estimate. This allows for tighter and more reliable prediction intervals.

Datasets

The paper evaluates CoffeeBoost on eight open benchmarks for database performance auto-tuning: TWITTER, TATP, VOTER, SMALLBANK, YCSB, TPC-C, SYSBENCH, and JOB. These benchmarks involve optimizing configuration inputs for database systems under various workloads. The simulators used for these benchmarks were originally based on Random Forests but were replaced with transformer-based simulators (using SAINT) to avoid giving tree-based optimizers an unfair advantage.

Key Insights and Ideas

  • The limitations of Gaussian Processes in real-world BO are significant: The paper strongly argues that the rigid assumptions of GPs are a bottleneck for complex optimization tasks like software tuning.
  • Distribution-free methods are crucial for robustness: Relying on conformal inference, which makes no assumptions about the data distribution, is key to achieving reliable uncertainty estimates and better performance across diverse problems.
  • GBDTs have untapped potential for BO: While RF-based BO (like SMAC) has shown success, GBDTs, with their ability to model complex interactions, offer a promising avenue, provided their uncertainty quantification challenges are addressed.
  • A native GBDT approach to difficulty estimation is more effective: CoffeeBoost's method of using boosted residuals to estimate prediction difficulty outperforms existing approaches like Error Re-weighted Conformal (ERC), especially when dealing with the inherent complexities of GBDT models.
  • Uncertainty estimation is more critical than point-estimate accuracy for final performance: The study highlights that the quality of the probabilistic prediction (measured by NCRPS) is a better indicator of final performance gain than the point-estimate accuracy (R2).

Key Results

  • Superior Performance: CoffeeBoost consistently outperformed existing Bayesian Optimization methods, including GP-based, tree-ensemble-based, and other conformalized-GBDT approaches, across all eight database auto-tuning benchmarks.
  • Significant Performance Gain: On average, CoffeeBoost achieved a 109.7% performance gain improvement compared to SMAC (an RF-based BO method), and a 58.5% gain compared to other tree-ensemble BOs.
  • Robustness to Distribution Assumptions: Unlike NGBoost and PGBM, which showed varying performance depending on the assumed posterior distribution, CoffeeBoost's distribution-free nature made it robust and consistently high-performing.
  • Improved Surrogate Accuracy: CoffeeBoost achieved the highest R2 (point-estimate accuracy) and NCRPS (uncertainty estimation accuracy) among all optimizers evaluated, demonstrating the effectiveness of its surrogate model.

Limitations and Future Work

  • Computational Cost: The paper acknowledges that using SGBE with multiple GBDTs increases computational time compared to a single GBDT. This is presented as a trade-off for improved performance.
  • Future Work: The authors suggest that further research could explore optimizing the selection of iteration sets for the boosted residuals to potentially reduce computational overhead without sacrificing performance. Investigating other tree-based ensemble methods for surrogate modeling in BO could also be a fruitful direction.

Summary updated

BibTeX
@inproceedings{lai2025coffeeboost,
  author = {Yuanhao Lai and Pengfei Zheng and Chenpeng Ji and Cheng Qiu and Tingkai Wang and Songhan Zhang and Zhengang Wang and Yunfei Du},
  title = {{CoffeeBoost: Gradient Boosting Native Conformal Inference for Bayesian Optimization}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i17.33982},
}
Figure