Non-smooth Bayesian Optimization in Tuning Problems

Hengrui Luo, James Weldon Demmel, Younghyun Cho, Xiaoye S. Li, Yang LiuarXiv 2021 · arXiv

Abstract

Standard Bayesian Optimization (BO) typically assumes that the objective functions are smooth. However, in real-world hardware tuning, performance often exhibits discontinuities due to architectural constraints like cache limits. This paper introduces the Clustered Gaussian Process (cGP), a surrogate model designed to detect and partition non-smooth regions, enabling more efficient and accurate optimization in discontinuous search spaces.

Introduction

In computational science, "tuning" involves finding the optimal algorithmic parameters—such as block sizes in matrix multiplication—to maximize performance on specific hardware. Because running these simulations is computationally expensive, researchers often use Bayesian Optimization (BO) to build a "surrogate model" that predicts performance across the parameter space.

The standard surrogate model for BO is the Gaussian Process (GP). However, GPs are inherently smooth, assuming that small changes in parameters lead to small changes in output. In reality, hardware performance is often non-smooth. For example, if a matrix block size exceeds a processor's L2 cache, performance can drop abruptly. Standard GPs attempt to "average out" these sharp drops, resulting in a poor model that misses the true optimal settings.

Standard GP failing to capture a discontinuity.

The Clustered Gaussian Process (cGP) Framework

To address this, we introduce the Clustered Gaussian Process (cGP). Instead of fitting a single smooth model to the entire search space, cGP partitions the space into distinct "regimes" of behavior using a cluster-classify framework.

  1. Clustering: The algorithm identifies pairs of inputs ($x$) and performance outputs ($y$). If two points are spatially close but have wildly different performance values, the algorithm recognizes a "jump" and assigns them to different clusters.
  2. Classification: A classifier (e.g., k-Nearest Neighbors) is trained to draw boundaries around these clusters, partitioning the parameter space. This allows the model to "discover" hardware limits, such as cache sizes, without requiring prior architectural knowledge.
  3. Local Surrogates: Inside each partition, an independent, simpler GP is fitted. This allows the model to be smooth within a regime but discontinuous between them.
  4. Weighted Acquisition: To decide where to sample next, the model uses a weighted acquisition function that accounts for the size and uncertainty of each cluster.
cGP successfully modeling a non-smooth function with a jump.

This approach is also computationally efficient: inverting several small matrices for local GPs is significantly faster than inverting one massive matrix for a global GP, improving scalability for large datasets.

Experimental Evaluation

The authors evaluated cGP using synthetic benchmarks and real-world high-performance computing (HPC) problems.

Key Results

  • Matrix Multiplication Tuning: cGP successfully identified performance "cliffs" at block sizes 160 and 500, which correspond to specific cache boundaries on the test hardware.
  • SuperLU_DIST: The cGP model achieved up to a 7.3% improvement in factorization time compared to standard GP-based tuning across 11 different matrix types used in physics and chemistry.
  • Synthetic Benchmarks: In tests using functions like Bukin N.6, which feature sharp ridges, cGP outperformed standard GPs in 90% of cases, finding better minima with the same number of samples.
  • Efficiency: For large sample sizes ($n=190$), cGP was significantly faster to train because it distributed the workload across smaller, independent local components.

Conclusion

The Clustered Gaussian Process offers a powerful solution for tuning problems where performance is non-smooth. By treating discontinuities as structural information rather than noise, cGP provides a more accurate representation of the underlying hardware behavior. Crucially, experiments show that if the underlying function is smooth, cGP performs just as well as a standard GP, making it a robust and flexible choice for modern optimization tasks.

Summary updated

Abstract

Building surrogate models is one common approach when we attempt to learn unknown black-box functions. Bayesian optimization provides a framework which allows us to build surrogate models based on sequential samples drawn from the function and find the optimum. Tuning algorithmic parameters to optimize the performance of large, complicated "black-box" application codes is a specific important application, which aims at finding the optima of black-box functions. Within the Bayesian optimization framework, the Gaussian process model produces smooth or continuous sample paths. However, the black-box function in the tuning problem is often non-smooth. This difficult tuning problem is worsened by the fact that we usually have limited sequential samples from the black-box function. Motivated by these issues encountered in tuning, we propose a novel additive Gaussian process model called clustered Gaussian process (cGP), where the additive components are induced by clustering. In the examples we studied, the performance can be improved by as much as 90% among repetitive experiments. By using this surrogate model, we want to capture the non-smoothness of the black-box function. In addition to an algorithm for constructing this model, we also apply the model to several artificial and real applications to evaluate it.
BibTeX
@misc{luo2021non,
  author = {Hengrui Luo and James Weldon Demmel and Younghyun Cho and Xiaoye S. Li and Yang Liu},
  title = {{Non-smooth Bayesian Optimization in Tuning Problems}},
  year = {2021},
  eprint = {2109.07563},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2109.07563},
}
Figure