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.
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.
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