No-regret Algorithms for Multi-task Bayesian Optimization

Sayak Ray Chowdhury, Aditya Gopalan

Abstract

We consider multi-objective optimization (MOO) of an unknown vector-valued function in the non-parametric Bayesian optimization (BO) setting, with the aim being to learn points on the Pareto front of the objectives. 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 scalarizations 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.

Introduction

In many scientific and engineering domains—ranging from drug discovery to sensor network tuning—researchers face the challenge of Multi-Objective Optimization (MOO). The goal is to simultaneously optimize multiple, often conflicting, objectives to find the Pareto front: the set of points where no objective can be improved without degrading another.

While Bayesian Optimization (BO) has become a standard approach for optimizing expensive black-box functions, traditional methods often treat each objective as an independent entity. This approach ignores potential correlations between tasks, missing opportunities to accelerate learning by transferring information across related objectives. Furthermore, existing multi-task BO heuristics frequently lack rigorous theoretical foundations. This paper addresses these gaps by introducing two novel algorithms, MT-KB and MT-BKB, which utilize multi-task kernels to exploit inter-task dependencies while providing the first finite-time "no-regret" guarantees for this setting.

Methodology

Multi-task Kernel Framework

The core of the proposed approach is the use of vector-valued kernel ridge regression. Unlike standard BO, which might use a separate Gaussian Process for each task, this framework employs a joint multi-task kernel. This kernel models dependencies across both the input space and the task space, allowing the algorithm to quantify how an observation in one task informs the estimate of another.

MT-KB and MT-BKB Algorithms

To navigate the multi-objective landscape, the authors utilize random scalarizations. At each iteration, the algorithms select a random weight vector to collapse the vector-valued problem into a single-objective scalar problem, which is then solved using an Upper Confidence Bound (UCB) strategy.

  1. MT-KB (Multi-task Kernelized Bandits): This algorithm constructs a confidence ellipsoid around the vector-valued function using the multi-task kernel. It selects points that maximize the scalarized UCB, effectively balancing exploration of uncertain regions with exploitation of known high-performing areas.
  2. MT-BKB (Multi-task Budgeted Kernelized Bandits): A significant challenge with kernel methods is their $O(t^3)$ computational complexity. MT-BKB addresses this by employing Nyström approximation, a data-sketching technique. By maintaining a small "dictionary" of representative points, MT-BKB achieves near-linear scaling without sacrificing the theoretical convergence guarantees of the full MT-KB algorithm.

Theoretical Contributions

A primary contribution of this work is the derivation of worst-case regret bounds that explicitly account for inter-task structure. The authors introduce a new vector-valued concentration inequality for martingales in Hilbert spaces, which allows for tighter error bounds than those obtained by simply aggregating individual task bounds.

This theoretical framework reveals a "similarity bonus": when tasks are highly correlated (indicated by the eigenvalues of the task-similarity matrix), the maximum information gain required to map the Pareto front decreases. This provides a mathematical proof that learning related tasks together is fundamentally more efficient than learning them in isolation.

Empirical Evaluation

The algorithms were benchmarked against several synthetic and real-world datasets:

  • Synthetic Benchmarks: Testing on functions generated from Reproducing Kernel Hilbert Spaces (RKHS) and the Perturbed Sine function demonstrated that the multi-task approach significantly outperforms independent baselines, especially as the number of tasks increases (e.g., $n=20$).
  • Shifted Branin-Hoo: A standard BO benchmark adapted for multi-tasking confirmed the robustness of the scalarization approach.
  • Intel Berkeley Research Lab Sensor Data: In a real-world application involving temperature, light, and humidity data from 54 sensors, the multi-task algorithms exploited cross-variable correlations to reach the Pareto front much faster than traditional MOBO (Multi-Objective Bayesian Optimization) methods.

Conclusion

This research provides a rigorous foundation for multi-task multi-objective optimization. By combining vector-valued kernels with random scalarization, the MT-KB and MT-BKB algorithms offer both computational efficiency and provable convergence.

Future work remains in several areas, including the development of "batch-UCB" variants for parallel experimentation and extending the theory to accommodate "heavy-tailed" noise distributions often found in messy, real-world data. Additionally, while the current bounds capture inter-task structure, determining the absolute mathematical optimality of these dependencies remains an open question.

Summary updated

Abstract

We consider multi-objective optimization (MOO) of an unknown vector-valued function in the non-parametric Bayesian optimization (BO) setting, with the aim being to learn points on the Pareto front of the objectives. 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 scalarizations 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