A Bayesian Optimization Framework for Finding Local Optima in Expensive Multi-Modal Functions

• URL: http://arxiv.org/abs/2210.06635v2
• Date: Sun, 6 Aug 2023 03:35:20 GMT
• Title: A Bayesian Optimization Framework for Finding Local Optima in Expensive Multi-Modal Functions
• Authors: Yongsheng Mei, Tian Lan, Mahdi Imani, Suresh Subramaniam
• Abstract summary: This paper develops a multimodal BO framework to find a set of local/global solutions for expensive-to-evaluate multimodal objective functions. We analytically derive the joint distribution of the objective function and its first-order derivatives. We introduce variants of the well-known BO acquisition functions to the multimodal setting and demonstrate the performance of the proposed framework.
• Score: 18.570591025615453
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Bayesian optimization (BO) is a popular global optimization scheme for sample-efficient optimization in domains with expensive function evaluations. The existing BO techniques are capable of finding a single global optimum solution. However, finding a set of global and local optimum solutions is crucial in a wide range of real-world problems, as implementing some of the optimal solutions might not be feasible due to various practical restrictions (e.g., resource limitation, physical constraints, etc.). In such domains, if multiple solutions are known, the implementation can be quickly switched to another solution, and the best possible system performance can still be obtained. This paper develops a multimodal BO framework to effectively find a set of local/global solutions for expensive-to-evaluate multimodal objective functions. We consider the standard BO setting with Gaussian process regression representing the objective function. We analytically derive the joint distribution of the objective function and its first-order derivatives. This joint distribution is used in the body of the BO acquisition functions to search for local optima during the optimization process. We introduce variants of the well-known BO acquisition functions to the multimodal setting and demonstrate the performance of the proposed framework in locating a set of local optimum solutions using multiple optimization problems.

Related papers

• Learning Multiple Initial Solutions to Optimization Problems [52.9380464408756]
  Sequentially solving similar optimization problems under strict runtime constraints is essential for many applications. We propose learning to predict emphmultiple diverse initial solutions given parameters that define the problem instance. We find significant and consistent improvement with our method across all evaluation settings and demonstrate that it efficiently scales with the number of initial solutions required.
  arXiv  Detail & Related papers  (2024-11-04T15:17:19Z)
• Localized Zeroth-Order Prompt Optimization [54.964765668688806]
  We propose a novel algorithm, namely localized zeroth-order prompt optimization (ZOPO) ZOPO incorporates a Neural Tangent Kernel-based derived Gaussian process into standard zeroth-order optimization for an efficient search of well-performing local optima in prompt optimization. Remarkably, ZOPO outperforms existing baselines in terms of both the optimization performance and the query efficiency.
  arXiv  Detail & Related papers  (2024-03-05T14:18:15Z)
• High-dimensional Bayesian Optimization via Covariance Matrix Adaptation Strategy [16.521207412129833]
  We propose a novel technique for defining the local regions using the Covariance Matrix Adaptation (CMA) strategy. Based on this search distribution, we then define the local regions consisting of data points with high probabilities of being the global optimum. Our approach serves as a meta-algorithm as it can incorporate existing black-box BOs, such as BO, TuRBO, and BAxUS, to find the global optimum.
  arXiv  Detail & Related papers  (2024-02-05T15:32:10Z)
• Analyzing and Enhancing the Backward-Pass Convergence of Unrolled Optimization [50.38518771642365]
  The integration of constrained optimization models as components in deep networks has led to promising advances on many specialized learning tasks. A central challenge in this setting is backpropagation through the solution of an optimization problem, which often lacks a closed form. This paper provides theoretical insights into the backward pass of unrolled optimization, showing that it is equivalent to the solution of a linear system by a particular iterative method. A system called Folded Optimization is proposed to construct more efficient backpropagation rules from unrolled solver implementations.
  arXiv  Detail & Related papers  (2023-12-28T23:15:18Z)
• Federated Multi-Level Optimization over Decentralized Networks [55.776919718214224]
  We study the problem of distributed multi-level optimization over a network, where agents can only communicate with their immediate neighbors. We propose a novel gossip-based distributed multi-level optimization algorithm that enables networked agents to solve optimization problems at different levels in a single timescale. Our algorithm achieves optimal sample complexity, scaling linearly with the network size, and demonstrates state-of-the-art performance on various applications.
  arXiv  Detail & Related papers  (2023-10-10T00:21:10Z)
• Learning Regions of Interest for Bayesian Optimization with Adaptive Level-Set Estimation [84.0621253654014]
  We propose a framework, called BALLET, which adaptively filters for a high-confidence region of interest. We show theoretically that BALLET can efficiently shrink the search space, and can exhibit a tighter regret bound than standard BO.
  arXiv  Detail & Related papers  (2023-07-25T09:45:47Z)
• Discovering Many Diverse Solutions with Bayesian Optimization [7.136022698519586]
  We propose Rank-Ordered Bayesian Optimization with Trust-regions (ROBOT) ROBOT aims to find a portfolio of high-performing solutions that are diverse according to a user-specified diversity metric. We show that it can discover large sets of high-performing diverse solutions while requiring few additional function evaluations.
  arXiv  Detail & Related papers  (2022-10-20T01:56:38Z)
• Joint Entropy Search for Multi-objective Bayesian Optimization [0.0]
  We propose a novel information-theoretic acquisition function for BO called Joint Entropy Search. We showcase the effectiveness of this new approach on a range of synthetic and real-world problems in terms of the hypervolume and its weighted variants.
  arXiv  Detail & Related papers  (2022-10-06T13:19:08Z)
• Enhanced Opposition Differential Evolution Algorithm for Multimodal Optimization [0.2538209532048866]
  Most of the real-world problems are multimodal in nature that consists of multiple optimum values. Classical gradient-based methods fail for optimization problems in which the objective functions are either discontinuous or non-differentiable. We have proposed an algorithm known as Enhanced Opposition Differential Evolution (EODE) algorithm to solve the MMOPs.
  arXiv  Detail & Related papers  (2022-08-23T16:18:27Z)
• Dynamic Multi-objective Ensemble of Acquisition Functions in Batch Bayesian Optimization [1.1602089225841632]
  The acquisition function plays a crucial role in the optimization process. Three acquisition functions are dynamically selected from a set based on their current and historical performance. Using an evolutionary multi-objective algorithm to optimize such a MOP, a set of non-dominated solutions can be obtained.
  arXiv  Detail & Related papers  (2022-06-22T14:09:18Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  We present an end-to-end method to learn the proximal operator across non-family problems. We show that for weakly-ized objectives and under mild conditions, the method converges globally.
  arXiv  Detail & Related papers  (2022-01-28T05:53:28Z)

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.