No-regret Algorithms for Multi-task Bayesian Optimization
- URL: http://arxiv.org/abs/2008.08885v1
- Date: Thu, 20 Aug 2020 10:55:20 GMT
- Title: No-regret Algorithms for Multi-task Bayesian Optimization
- Authors: Sayak Ray Chowdhury, Aditya Gopalan
- Abstract summary: We consider multi-objective optimization (MOO) of an unknown vector-valued function in the non-parametric Bayesian optimization setting.
We develop two novel BO algorithms based on random scalarizations of the objectives.
We numerically benchmark our algorithms on both synthetic and real-life MOO problems, and show the advantages offered by learning with multi-task kernels.
- Score: 26.13594355150718
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- 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.
Related papers
- Parametric-Task MAP-Elites [3.499042782396682]
Parametric-Task MAP-Elites (PT-ME) is a new black-box algorithm for continuous multi-task optimization problems.
We show that PT-ME outperforms all baselines, including the deep reinforcement learning algorithm PPO on two parametric-task toy problems and a robotic problem in simulation.
arXiv Detail & Related papers (2024-02-02T10:04:29Z) - Equation Discovery with Bayesian Spike-and-Slab Priors and Efficient Kernels [57.46832672991433]
We propose a novel equation discovery method based on Kernel learning and BAyesian Spike-and-Slab priors (KBASS)
We use kernel regression to estimate the target function, which is flexible, expressive, and more robust to data sparsity and noises.
We develop an expectation-propagation expectation-maximization algorithm for efficient posterior inference and function estimation.
arXiv Detail & Related papers (2023-10-09T03:55:09Z) - An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
Clustered multi-task compressive sensing is a hierarchical model that solves multiple compressive sensing tasks.
The existing inference algorithm for this model is computationally expensive and does not scale well in high dimensions.
We propose a new algorithm that substantially accelerates model inference by avoiding the need to explicitly compute these covariance matrices.
arXiv Detail & Related papers (2023-09-30T15:57:14Z) - A Scale-Independent Multi-Objective Reinforcement Learning with
Convergence Analysis [0.6091702876917281]
Many sequential decision-making problems need optimization of different objectives which possibly conflict with each other.
We develop a single-agent scale-independent multi-objective reinforcement learning on the basis of the Advantage Actor-Critic (A2C) algorithm.
A convergence analysis is then done for the devised multi-objective algorithm providing a convergence-in-mean guarantee.
arXiv Detail & Related papers (2023-02-08T16:38:55Z) - Multi-Task Learning with Prior Information [5.770309971945476]
We propose a multi-task learning framework, where we utilize prior knowledge about the relations between features.
We also impose a penalty on the coefficients changing for each specific feature to ensure related tasks have similar coefficients on common features shared among them.
arXiv Detail & Related papers (2023-01-04T12:48:05Z) - Lifelong Bandit Optimization: No Prior and No Regret [70.94238868711952]
We develop LIBO, an algorithm which adapts to the environment by learning from past experience.
We assume a kernelized structure where the kernel is unknown but shared across all tasks.
Our algorithm can be paired with any kernelized or linear bandit algorithm and guarantees optimal performance.
arXiv Detail & Related papers (2022-10-27T14:48:49Z) - Tree ensemble kernels for Bayesian optimization with known constraints
over mixed-feature spaces [54.58348769621782]
Tree ensembles can be well-suited for black-box optimization tasks such as algorithm tuning and neural architecture search.
Two well-known challenges in using tree ensembles for black-box optimization are (i) effectively quantifying model uncertainty for exploration and (ii) optimizing over the piece-wise constant acquisition function.
Our framework performs as well as state-of-the-art methods for unconstrained black-box optimization over continuous/discrete features and outperforms competing methods for problems combining mixed-variable feature spaces and known input constraints.
arXiv Detail & Related papers (2022-07-02T16:59:37Z) - Many Objective Bayesian Optimization [0.0]
Multi-objective Bayesian optimization (MOBO) is a set of methods that has been successfully applied for the simultaneous optimization of black-boxes.
In particular, MOBO methods have problems when the number of objectives in a multi-objective optimization problem are 3 or more, which is the many objective setting.
We show empirical evidence in a set of toy, synthetic, benchmark and real experiments that GPs predictive distributions of the effectiveness of the metric and the algorithm.
arXiv Detail & Related papers (2021-07-08T21:57:07Z) - Random Features for the Neural Tangent Kernel [57.132634274795066]
We propose an efficient feature map construction of the Neural Tangent Kernel (NTK) of fully-connected ReLU network.
We show that dimension of the resulting features is much smaller than other baseline feature map constructions to achieve comparable error bounds both in theory and practice.
arXiv Detail & Related papers (2021-04-03T09:08:12Z) - Multi-task Supervised Learning via Cross-learning [102.64082402388192]
We consider a problem known as multi-task learning, consisting of fitting a set of regression functions intended for solving different tasks.
In our novel formulation, we couple the parameters of these functions, so that they learn in their task specific domains while staying close to each other.
This facilitates cross-fertilization in which data collected across different domains help improving the learning performance at each other task.
arXiv Detail & Related papers (2020-10-24T21:35:57Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.