No-regret Algorithms for Multi-task Bayesian Optimization

Sayak Ray Chowdhury, Aditya Gopalan

Introduction

Bayesian Optimization (BO) has become a cornerstone for optimizing expensive-to-evaluate black-box functions. In many practical applications, such as drug discovery or engineering design, practitioners must optimize multiple related objectives simultaneously. Traditional BO approaches often treat these objectives as independent tasks, failing to exploit the underlying correlations between them. This paper introduces two novel algorithms, MT-KB and MT-BKB, which leverage multi-task kernels to model inter-task dependencies, providing the first rigorous "no-regret" guarantees for multi-task optimization.

Problem Statement: The Multi-Task Challenge

Multi-Objective Optimization (MOO) requires finding the Pareto front—the set of optimal trade-offs between competing goals. While many heuristics exist for multi-task BO, they frequently lack theoretical guarantees. A "no-regret" algorithm is essential because it ensures that the average performance of the optimizer converges to the theoretical optimum over time. Ignoring task correlations leads to inefficient exploration, especially as the number of tasks increases.

Methodology

The authors propose a framework based on vector-valued kernel ridge regression combined with the Upper Confidence Bound (UCB) strategy.

1. MT-KB (Multi-task Kernelized Bandits)

MT-KB utilizes a multi-task kernel (e.g., the Intrinsic Coregionalization Model) to model all objectives simultaneously. It employs a scalarization technique where multiple objectives are aggregated into a single utility function. By handling a distribution of weights, the algorithm effectively explores the entire Pareto front.

2. MT-BKB (Multi-task Budgeted Kernelized Bandits)

To address the $O(t^3)$ computational complexity inherent in standard kernel methods, MT-BKB incorporates Nyström approximation. This sketching technique maintains a "dictionary" of representative points, reducing computational costs to near-linear levels while preserving the no-regret guarantee.

Theoretical Contributions

The core of the paper is a new concentration inequality for vector-valued functions in a Reproducing Kernel Hilbert Space (RKHS). This allows for tighter regret bounds. The authors prove that if tasks are highly correlated, the regret grows significantly slower. Specifically, learning $n$ identical tasks is shown to be as efficient as learning a single task, whereas independent learning is $\sqrt{n}$ times harder.

Experimental Evaluation

The algorithms were tested on synthetic RKHS functions, standard optimization benchmarks (Perturbed Sine, Shifted Branin-Hoo), and real-world environmental data from the Intel Berkeley Research Lab.

Comparison of average cumulative regret on synthetic benchmarks showing the superior convergence of multi-task (MT) methods over independent task (IT) baselines.

As shown in the experimental results, both MT-KB and MT-BKB achieve significantly lower regret faster than their independent counterparts (IT-KB and IT-BKB). This gap is particularly pronounced in high-dimensional task spaces.

Average cumulative regret across complex benchmarks, demonstrating that MT-BKB maintains performance despite computational approximations.

Key Insights

  • Correlation Efficiency: Exploiting task similarity leads to a $\sqrt{n}$ factor improvement in theoretical regret bounds compared to naive independent task modeling.
  • Scalability: MT-BKB demonstrates that "budgeted" kernel methods can maintain theoretical guarantees while being practical for large-scale data.
  • Robustness: The framework remains effective even when objective functions deviate slightly from the assumed kernel structure.

Conclusion and Future Work

This work bridges the gap between multi-task BO heuristics and formal learning theory. While the current algorithms require prior knowledge of the task-similarity matrix, future research could focus on learning this structure online. Additionally, optimizing the acquisition function remains a computational bottleneck that warrants further investigation.

Summary updated

Abstract

We consider multi-objective optimization (MOO) of an unknown vector-valued function in the non-parametric Bayesian optimization (BO) setting. Our aim is to maximize the expected cumulative utility of all objectives, as expressed by a given prior over a set of scalarization functions. Most existing BO algorithms do not model the fact that the multiple objectives, or equivalently, tasks can share similarities, and even the few that do lack rigorous, finite-time regret guarantees that capture explicitly inter-task structure. In this work, we address this problem by modelling inter-task dependencies using a multi-task kernel and develop two novel BO algorithms based on random scalarization of the objectives. Our algorithms employ vector-valued kernel regression as a stepping stone and belong to the upper confidence bound class of algorithms. Under a smoothness assumption that the unknown vector-valued function is an element of the reproducing kernel Hilbert space associated with the multi-task kernel, we derive worst-case regret bounds for our algorithms that explicitly capture the similarities between tasks. We numerically benchmark our algorithms on both synthetic and real-life MOO problems, and show the advantages offered by learning with multi-task kernels.
BibTeX
@inproceedings{chowdhury2021no,
  author = {Sayak Ray Chowdhury and Aditya Gopalan},
  title = {{No-regret Algorithms for Multi-task Bayesian Optimization}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2021},
  url = {https://openreview.net/forum?id=ZyMpCZuU3Sj},
}
Figure