🤖 machine learning

Frugal Bayesian Optimization: Scalable Surrogates for Data- and Resource-Limited Discovery

This paper introduces "Frugal Bayesian Optimization" (FruBO), a compute-aware framework demonstrating that scalable surrogate models like Random Forests and NGBoost often outperform traditional Gaussian Processes in both optimization quality and computational efficiency, while providing a predictive tool to recommend the most suitable surrogate based on dataset characteristics.

Original authors: Panagiotis Krokidas, Christoforos Rekatsinas, Vassilis Sioros, Grigorios M. Chatziathanasiou, Efi-Maria Papia, George Giannakopoulos

Published 2026-08-03

📖 3 min read☕ Coffee break read

CC BY 4.0

Original authors: Panagiotis Krokidas, Christoforos Rekatsinas, Vassilis Sioros, Grigorios M. Chatziathanasiou, Efi-Maria Papia, George Giannakopoulos

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a treasure hunter trying to find the single best spot to dig for gold in a massive, foggy desert. You have a limited supply of water and a small team, so you can't just dig everywhere. You need a smart strategy to guess where the gold is without wasting your resources. This is the world of scientific discovery, where researchers try to find the perfect recipe for a new battery, the most effective drug, or the strongest bridge material. They can't test every single possibility because it would take too long and cost too much.

To solve this, scientists use a clever trick called Bayesian Optimization. Think of it as having a "crystal ball" (a mathematical model) that learns from every tiny dig you make. After you dig one hole and find a little bit of gold, the crystal ball updates its map, guesses where the next best spot might be, and tells you where to dig next. The goal is to find the absolute best spot using the fewest number of digs possible. For a long time, scientists have used a specific type of crystal ball called a Gaussian Process. It's very good at guessing, but it has a secret weakness: as you dig more holes, the crystal ball gets heavier and slower, eventually becoming so heavy that it breaks your backpack (your computer's memory) and stops you from digging anymore.

This paper, titled "Frugal Bayesian Optimization," asks a simple but revolutionary question: Do we really need the heavy crystal ball? The authors, a team of researchers from Greece, decided to test if there are lighter, faster crystal balls that can do the same job without breaking your back. They didn't just look at how well the models found the gold; they also weighed how much energy and computer power each one ate up. They tested four different types of "crystal balls" across eight fake desert maps and nine real-world treasure hunts, ranging from designing new materials to teaching robots how to land on the moon.

Here is what they found: The old favorite, the Gaussian Process, was indeed the heaviest. It took up a massive amount of memory and time, growing slower and slower the more data it collected. Surprisingly, this extra weight didn't actually help it find the gold any better than the others. In fact, the "lightweight" alternatives—specifically Random Forests, NGBoost, and BASS—were just as good at finding the best solutions, but they were incredibly frugal. They ran faster, used a tiny fraction of the computer's memory, and didn't slow down even when the dataset got huge.

The researchers discovered that for most real-world problems, sticking with the heavy Gaussian Process is like trying to carry a watermelon to a picnic when you could just bring a sandwich. It's unnecessary and wasteful. To help scientists choose the right tool for the job, the team built a smart "recommendation system." This system looks at a few simple facts about a new problem (like how big the data is or how complex the map is) and instantly predicts which lightweight crystal ball will work best.

In short, this paper suggests that we don't need to spend a fortune on super-computers to find scientific breakthroughs. By switching to these lighter, faster models, researchers can save time, money, and energy while finding just as good, if not better, solutions. It's a call to be "frugal" with our computing resources, proving that sometimes the smallest, lightest tools are the ones that can carry the heaviest discoveries.

Technical Summary: Frugal Bayesian Optimization (FruBO)

Problem Statement

Bayesian Optimization (BO) is a standard approach for data-efficient optimization in scientific and engineering domains, particularly where objective evaluations are expensive (e.g., materials discovery, drug screening). However, the field has historically prioritized sample efficiency (minimizing the number of function evaluations) while neglecting the computational cost of the optimization process itself.

The dominant surrogate model in BO, the Gaussian Process (GP), suffers from severe scalability limitations. GP training involves covariance matrix factorizations with $O(N^3)$ time complexity and $O(N^2)$ memory growth, where $N$ is the number of acquisitions. As $N$ increases, the wall-clock time and memory overhead of updating the GP surrogate often become the bottleneck, rendering BO impractical on standard hardware even when the objective function evaluations are inexpensive. While various sparse GP approximations exist, they introduce additional engineering complexity and hyperparameter tuning without eliminating the fundamental memory growth.

There is a lack of systematic, quantitative evidence comparing alternative, scalable surrogate models against GPs across both optimization quality and computational resource usage. Consequently, researchers often default to GPs without knowing if a more frugal alternative could achieve equal or better performance with significantly lower computational costs.

Methodology

The authors introduce FruBO (Frugal Bayesian Optimization), a framework that redefines BO evaluation along two axes: optimization quality and computational frugality (time and memory).

Experimental Setup

The study benchmarks four surrogate models across two distinct classes of datasets:

Eight Benchmark Functions: Standard test functions (e.g., Rastrigin, Ackley, Michalewicz) with known optima, used to control for landscape characteristics.
Nine Real-World Datasets: Spanning materials science, mechanics, robotics, chemistry, and machine learning. These include:
- Covalent Organic Frameworks (COFs) for methane capacity.
- Moiré-pattern multilayer materials for pore-size uniformity.
- LunarLander control sequences.
- Molecular docking (Ro4) and QM9 quantum chemistry datasets.
- High-pressure vessel designs and semi-active tuned mass dampers.
- C. elegans mechanics and neural network hyperparameter tuning.

Surrogate Models Evaluated

Gaussian Processes (GP): The standard baseline (SingleTaskGP with ARD kernels).
Random Forests (RF): Non-parametric ensemble models using regression trees.
NGBoost (NGB): Natural Gradient Boosting, a probabilistic boosting framework.
Bayesian Adaptive Spline Surfaces (BASS): A nonparametric Bayesian regression model using adaptive splines and reversible-jump MCMC.

Evaluation Metrics

Performance is measured by:

Optimization Quality: Best-found objective value and the identification rate of the top-100 solutions.
Computational Frugality: Wall-clock training time and GPU memory consumption as a function of the number of acquisitions ( $N$ ).
Aggregated Metrics: The Area Under the Curve (AUC) is calculated for performance vs. time and performance vs. samples to provide a single comparative score.

Surrogate Recommendation System

Motivated by the empirical results, the authors develop a surrogate-recommendation framework. This system uses a lightweight set of dataset characteristics (dataset size, dimensionality, fractal dimension, and an estimate of target variance) to train multi-output classifiers. These classifiers predict the ranking of the four surrogates for a new dataset under either compute-time-limited or sample-acquisition-limited regimes.

Key Results

1. Computational Scaling

GPs: Exhibit superlinear growth in training time and linear growth in GPU memory usage as $N$ increases. In many real-world scenarios, GP-based BO terminates prematurely on standard workstations due to memory pressure.
Scalable Alternatives (RF, NGB, BASS): Demonstrate nearly linear time scaling and effectively bounded (constant) memory usage regardless of the number of acquisitions. They remain stable and efficient even as $N$ grows large.

2. Optimization Performance

Contrary to the assumption that GPs are superior due to their principled uncertainty quantification:

Benchmark Functions: RF consistently achieved the fastest convergence in wall-clock time. NGB often led in sample efficiency. GPs frequently ranked last or second-to-last in both metrics.
Real-World Datasets: GPs ranked first in compute-time performance only twice (Moiré and C. elegans datasets) and in sample efficiency only once. In all other cases, GPs were second-to-last or last.
Overall: RF, NGB, and BASS consistently matched or surpassed GP-based BO in finding optimal values and identifying top candidates, while doing so at a fraction of the computational cost.

3. Surrogate Recommendation

The meta-classifier trained to predict surrogate rankings achieved high Normalized Discounted Cumulative Gain (nDCG) scores.

The model successfully predicted the optimal surrogate for a given dataset based on simple characteristics.
Prediction accuracy was particularly high for computational-efficiency rankings, suggesting that the relationship between dataset properties and surrogate scalability is learnable.

Key Contributions

Systematic Benchmarking: The first comprehensive study to jointly evaluate BO surrogate models across optimization quality and computational resources (time/memory) on a diverse set of 17 datasets.
Redefinition of BO Efficiency: Establishes that "efficiency" in BO must account for the computational cost of the surrogate, not just the number of samples.
FruBO Framework: Provides a reproducible, open-source baseline for compute-aware BO evaluation.
Surrogate Recommendation Tool: Introduces a data-driven method to select the most appropriate surrogate model a priori based on dataset characteristics, removing the need for costly pilot studies.

Significance and Claims

The paper argues that the default reliance on Gaussian Processes is often unjustified and computationally wasteful. The authors claim that:

Scalability is a Primary Determinant: The choice of surrogate is not a secondary modeling detail but a primary factor in the feasibility of BO, especially as datasets grow.
Frugality Enables Discovery: By adopting scalable surrogates (RF, NGB, BASS), researchers can perform BO on standard hardware without requiring specialized GPUs or HPC clusters, democratizing access to optimization tools.
Resource-Aware ML: In the context of rising energy costs and environmental concerns in AI, adopting a "resource-aware" mindset is essential. This work demonstrates that high-quality optimization can be achieved with significantly reduced energy and time footprints.
No Universal Surrogate: There is no single best surrogate for all problems; the optimal choice depends on the specific constraints (time vs. samples) and dataset characteristics.

The authors conclude that FruBO provides a practical methodology for deploying BO in resource-constrained settings, shifting the paradigm from "sample efficiency at any cost" to "balanced efficiency."