TREGO: a Trust-Region Framework for Efficient Global Optimization

• URL: http://arxiv.org/abs/2101.06808v3
• Date: Tue, 2 Feb 2021 12:05:29 GMT
• Title: TREGO: a Trust-Region Framework for Efficient Global Optimization
• Authors: Youssef Diouane and Victor Picheny and Rodolphe Le Riche and Alexandre Scotto Di Perrotolo
• Abstract summary: We propose and analyze a trust-region-like EGO method (TREGO) TREGO alternates between regular EGO steps and local steps within a trust region. Our algorithm enjoys strong global convergence properties, while departing from EGO only for a subset of optimization steps.
• Score: 63.995130144110156
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Efficient Global Optimization (EGO) is the canonical form of Bayesian optimization that has been successfully applied to solve global optimization of expensive-to-evaluate black-box problems. However, EGO struggles to scale with dimension, and offers limited theoretical guarantees. In this work, we propose and analyze a trust-region-like EGO method (TREGO). TREGO alternates between regular EGO steps and local steps within a trust region. By following a classical scheme for the trust region (based on a sufficient decrease condition), we demonstrate that our algorithm enjoys strong global convergence properties, while departing from EGO only for a subset of optimization steps. Using extensive numerical experiments based on the well-known COCO benchmark, we first analyze the sensitivity of TREGO to its own parameters, then show that the resulting algorithm is consistently outperforming EGO and getting competitive with other state-of-the-art global optimization methods. The method is available both in the R package DiceOptim (https://cran.r-project.org/package=DiceOptim) and Python library trieste (https://secondmind-labs.github.io/trieste/).

Related papers

• LLaMA-Berry: Pairwise Optimization for O1-like Olympiad-Level Mathematical Reasoning [56.273799410256075]
  The framework combines Monte Carlo Tree Search (MCTS) with iterative Self-Refine to optimize the reasoning path. The framework has been tested on general and advanced benchmarks, showing superior performance in terms of search efficiency and problem-solving capability.
  arXiv  Detail & Related papers  (2024-10-03T18:12:29Z)
• 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)
• LABCAT: Locally adaptive Bayesian optimization using principal-component-aligned trust regions [0.0]
  We propose the LABCAT algorithm, which extends trust-region-based BO. We show that the algorithm outperforms several state-of-the-art BO and other black-box optimization algorithms.
  arXiv  Detail & Related papers  (2023-11-19T13:56:24Z)
• 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)
• A Bayesian Optimization Framework for Finding Local Optima in Expensive Multi-Modal Functions [18.570591025615453]
  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.
  arXiv  Detail & Related papers  (2022-10-13T00:10:13Z)
• MBORE: Multi-objective Bayesian Optimisation by Density-Ratio Estimation [0.01652719262940403]
  optimisation problems often have multiple conflicting objectives that can be computationally and/or financially expensive. Mono-surrogate Bayesian optimisation (BO) is a popular model-based approach for optimising such black-box functions. We extend previous work on BO by density-ratio estimation (BORE) to the multi-objective setting.
  arXiv  Detail & Related papers  (2022-03-31T09:27:59Z)
• Learning to Hash Robustly, with Guarantees [79.68057056103014]
  In this paper, we design an NNS algorithm for the Hamming space that has worst-case guarantees essentially matching that of theoretical algorithms. We evaluate the algorithm's ability to optimize for a given dataset both theoretically and practically. Our algorithm has a 1.8x and 2.1x better recall on the worst-performing queries to the MNIST and ImageNet datasets.
  arXiv  Detail & Related papers  (2021-08-11T20:21:30Z)
• Stochastic Optimization Forests [60.523606291705214]
  We show how to train forest decision policies by growing trees that choose splits to directly optimize the downstream decision quality, rather than splitting to improve prediction accuracy as in the standard random forest algorithm. We show that our approximate splitting criteria can reduce running time hundredfold, while achieving performance close to forest algorithms that exactly re-optimize for every candidate split.
  arXiv  Detail & Related papers  (2020-08-17T16:56:06Z)

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.