Abstract
Recently, there has been rising interest in Bayesian optimization – the optimization of an unknown function with assumptions usually expressed by a Gaussian Process (GP) prior. We study an optimization strategy (EST) that selects the next point to evaluate by directly estimating which point is most likely to be the function's maximum.
Introduction
Bayesian Optimization (BO) is a powerful framework for optimizing expensive-to-evaluate "black-box" functions, such as hyperparameter tuning in deep learning or trajectory optimization in robotics. Standard BO approaches rely on acquisition functions like Upper Confidence Bound (GP-UCB) or Probability of Improvement (GP-PI). However, these methods typically require manual tuning of "nuisance parameters" that govern the exploration-exploitation tradeoff. Incorrect settings can lead to suboptimal performance or inefficient exploration.
This paper introduces the Estimation Strategy (EST), a parameter-free approach that eliminates the need for manual meta-optimization. By framing optimization as an estimation problem—specifically, identifying the point most likely to be the global maximizer—EST naturally balances exploration and exploitation.
Methodology
The core idea of EST is to select the next evaluation point $x$ based on the probability that it is the global maximizer of the function.
Mean-Field Approximation
Calculating the exact probability of a point being the maximum is computationally intensive. The authors employ a "mean-field" approach, treating function values at different points as independent Gaussian variables. This approximation makes the computation tractable while maintaining effective exploration.
Plug-in Maximum Estimate
Since the global maximum value $m$ is unknown, EST utilizes a posterior expectation to estimate it ($\hat{m}$). The paper offers two implementations: ESTn, which uses numerical integration, and ESTa, which utilizes a faster Laplace approximation.
Theoretical Bridge
A significant contribution of this work is the mathematical proof that EST is equivalent to adaptive versions of GP-UCB and GP-PI. This provides a theoretical justification for EST's performance, showing that it effectively "auto-tunes" exploration parameters at every step based on the model's current uncertainty.
Experimental Evaluation
The EST strategy was evaluated across three distinct domains:
- Synthetic Functions: 1-D and 2-D functions sampled from Gaussian Processes to test convergence speed.
- Robotics: Trajectory optimization for a "2D Airplane" problem where the goal is to find a collision-free path with the highest reward.
- Computer Vision: Hyperparameter tuning for linear SVMs across six benchmark datasets, including Caltech101 and SUN397.
Key Results
EST demonstrated strong performance across all benchmarks without requiring manual parameter tuning.
In synthetic 1-D tests, ESTn reached the optimum in approximately half the iterations required by UCB. For 2-D functions, ESTn and ESTa achieved zero median regret significantly faster than traditional methods like PI or UCB.
In computer vision tasks, ESTa and ESTn consistently outperformed baselines. On datasets such as Action40 and SUN397, the auto-tuned parameters of EST led to a 3-4% increase in classification accuracy compared to standard tuning methods. In robotics, EST performed on par with the best-tuned competitors while requiring zero manual configuration.
Discussion and Future Work
EST offers a robust, parameter-free alternative for Bayesian Optimization. By focusing on the probability of being the argmax, the exploration-exploitation tradeoff emerges naturally. The "mean-field" assumption, while a simplification, tends to favor exploration, preventing the algorithm from becoming trapped in local optima.
Future work includes addressing the challenges of scaling EST to high-dimensional spaces, as the current implementation relies on discretization of the input space. Additionally, while EST is more efficient than Entropy Search methods, it still carries more computational overhead per iteration than simple UCB, suggesting potential for further algorithmic optimization.
Summary updated