Fully Distributed Bayesian Optimization with Stochastic Policies

Javier Garcia-Barcos, Ruben Martinez-CantinIJCAI 2019 · DOI

TL;DR

This paper introduces a novel method for fully distributed Bayesian Optimization (BO) that leverages stochastic policies, specifically the Boltzmann policy. This approach allows for high scalability and parallelism, overcoming the sequential nature of traditional BO and enabling asynchronous execution, which is crucial for high-throughput computing environments.

What Problem Does This Paper Address?

Bayesian Optimization (BO) is a powerful technique for efficiently finding optimal parameters in expensive black-box functions, commonly used in hyperparameter tuning and computer experiment design. However, BO is inherently sequential, meaning each new data point is processed before the next can be selected. While parallel BO methods exist, they often require a central node for coordination and can be synchronous, limiting their scalability and robustness. Existing fully distributed methods, like Thompson sampling, are known to be suboptimal compared to other acquisition functions. This paper addresses the need for a fully distributed BO method that is both scalable and can utilize any acquisition function, overcoming the limitations of existing approaches.

Methods

The core innovation lies in reframing Bayesian Optimization as a Partially Observable Markov Decision Process (POMDP). This allows the authors to introduce stochastic policies, specifically the Boltzmann policy, for selecting the next query point. Instead of greedily picking the single best point, the Boltzmann policy samples from a probability distribution over potential query points, influenced by the acquisition function and a temperature parameter ($\beta$). This stochasticity allows for exploration even when the surrogate model is uncertain.

Crucially, this stochastic policy enables a fully distributed BO implementation. Each node in the distributed system maintains its own surrogate model and independently samples the next query point. Nodes only need to broadcast their queries and observed values, minimizing communication bandwidth and allowing for asynchronous updates. This contrasts with traditional parallel BO methods that rely on a central coordinator. The paper also provides theoretical analysis showing that this stochastic policy achieves near-optimal convergence rates, similar to greedy policies in the limit, without needing explicit e-greedy strategies.

Datasets

The paper evaluates its method on:

  • Benchmark Functions: A suite of standard global optimization test problems (e.g., Bohachevsky, Branin, Ackley, Rosenbrock, Eggholder, Schubert, Hartmann 6D).
  • Random Functions from a GP: To assess performance in a controlled setting, random functions are generated from a Gaussian Process (GP) with both Matérn and Rational Quadratic kernels.
  • Robot Pushing Setup: An active learning for robot pushing task, using both 3D and 4D input spaces.
  • Hyperparameter Tuning of Neural Networks:
    • Variational Autoencoder (VAE) on MNIST: Tuning hyperparameters like hidden layer nodes, learning rate, learning rate decay, and ADAM optimizer's $\epsilon$.
  • Feedforward Network on Boston Housing: Tuning hyperparameters such as hidden layer nodes, learning rate, learning rate decay, and RMSprop's $\rho$.

No new benchmarks were introduced; existing, well-established problems and datasets were used for evaluation.

Key Insights and Ideas

  • BO as a POMDP: This conceptual shift provides a powerful framework for understanding and developing new BO algorithms, particularly for exploring stochastic policies.
  • Stochastic Policies for Exploration: The Boltzmann policy allows for exploration even when the surrogate model is highly uncertain or biased, preventing premature convergence to suboptimal solutions.
  • True Parallelism and Scalability: The proposed method achieves genuine distributed BO without a central coordinator, making it highly scalable and robust to node failures or asynchronous communication.
  • Any Acquisition Function Compatibility: The stochastic policy framework is agnostic to the specific acquisition function used, offering broad applicability.
  • Theoretical Guarantees: The stochastic policy is shown to achieve theoretical convergence rates comparable to greedy methods, providing a strong foundation for its practical effectiveness.

Key Results

The proposed stochastic policy (SP) for distributed BO, combined with various acquisition functions (SP-EI, SP-UCB, SP-PI), consistently outperforms or matches the state-of-the-art distributed method (Parallel and Distributed Thompson Sampling - PDTS) across most benchmark functions and real-world applications.

  • Benchmark Functions: SP-EI shows consistent performance, often achieving better or similar results to alternatives. The stochastic policy helps in difficult functions like Schubert by inducing exploration.
  • Robot Pushing: SP-EI and SP-PI demonstrate faster convergence than GP-PDTS.
  • Hyperparameter Tuning: SP-EI and SP-PI consistently outperform PDTS for both VAE and Feedforward network tuning.
  • GP Sampled Functions: SP-EI is comparable to PDTS for both within-model and out-of-model GP-based experiments.

Limitations and Future Work

  • Sampling Strategy: While the paper discusses sampling from the Boltzmann policy, it notes that it can be non-trivial for multimodal acquisition functions. They suggest using techniques like importance sampling or tempered transitions, and found that a mixture of Gaussians with different variances worked well in practice for small dimensional problems.
  • Temperature Parameter ($\beta$): The choice of the temperature parameter $\beta$ is crucial for balancing exploration and exploitation. The paper suggests that different $\beta$ values can lead to more exploitative ($\beta \to \infty$) or exploratory ($\beta \to 0$) nodes, hinting at potential for combining configurations.
  • Future Work: The authors suggest exploring multitask and multifidelity BO by leveraging the POMDP framework and transition functions between states (representing different tasks or fidelities). They also propose using the stochastic policy for a full Bayesian treatment of dynamic programming in BO, similar to value iteration. The potential for combining different node configurations (analogous to parallel tempering) is also highlighted.

Summary updated

BibTeX
@inproceedings{garciabarcos2019fully,
  author = {Javier Garcia-Barcos and Ruben Martinez-Cantin},
  title = {{Fully Distributed Bayesian Optimization with Stochastic Policies}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/327},
}
Figure