Approximation of Box Decomposition Algorithm for Fast Hypervolume-Based Multi-Objective Optimization

• URL: http://arxiv.org/abs/2512.05825v1
• Date: Fri, 05 Dec 2025 15:43:06 GMT
• Title: Approximation of Box Decomposition Algorithm for Fast Hypervolume-Based Multi-Objective Optimization
• Authors: Shuhei Watanabe,
• Abstract summary: Hypervolume (HV)-based Bayesian optimization (BO) is one of the standard approaches for multi-objective decision-making.<n>The computational cost of optimizing the acquisition function remains a significant bottleneck.<n>A rigorous algorithmic description is currently absent from the literature.
• Score: 4.629694186457132
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Hypervolume (HV)-based Bayesian optimization (BO) is one of the standard approaches for multi-objective decision-making. However, the computational cost of optimizing the acquisition function remains a significant bottleneck, primarily due to the expense of HV improvement calculations. While HV box-decomposition offers an efficient way to cope with the frequent exact improvement calculations, it suffers from super-polynomial memory complexity $O(MN^{\lfloor \frac{M + 1}{2} \rfloor})$ in the worst case as proposed by Lacour et al. (2017). To tackle this problem, Couckuyt et al. (2012) employed an approximation algorithm. However, a rigorous algorithmic description is currently absent from the literature. This paper bridges this gap by providing comprehensive mathematical and algorithmic details of this approximation algorithm.

Related papers

• Approximation Algorithms for Preference Aggregation Using CP-Nets [3.337244446073836]
  This paper studies the design and analysis of approximation algorithms for aggregating preferences over Conditional Preference Networks (CP-nets) Its focus is on aggregating preferences over so-called emphswaps, for which optimal solutions in general are already known to be of exponential size.
  arXiv  Detail & Related papers  (2023-12-14T17:31:38Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  A current standard approach to solving convex discrete optimization problems is the use of cutting-plane algorithms. Despite the existence of a number of general-purpose cut-generating algorithms, large-scale discrete optimization problems continue to suffer from intractability. We propose a method for accelerating cutting-plane algorithms via reinforcement learning.
  arXiv  Detail & Related papers  (2023-07-17T20:11:56Z)
• Learning distributed representations with efficient SoftMax normalization [3.8673630752805437]
  We propose a linear-time approximation to compute the normalization constants of $rm SoftMax(XYT)$ for embedding vectors with bounded norms.<n>We show on some pre-trained embedding datasets that the proposed estimation method achieves higher or comparable accuracy with competing methods.<n>The proposed algorithm is interpretable and easily adapted to arbitrary embedding problems.
  arXiv  Detail & Related papers  (2023-03-30T15:48:26Z)
• A One-Sample Decentralized Proximal Algorithm for Non-Convex Stochastic Composite Optimization [10.762749887051546]
  We propose two-time scale algorithms: ProxDAS-A and Proxcal$DASA-GT. Unlike prior work, our algorithms achieve comparable complexity without requiring large batch sizes, more complex per-it operations, or stronger assumptions.
  arXiv  Detail & Related papers  (2023-02-20T05:16:18Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  Efficient computation of the optimal transport distance between two distributions serves as an algorithm that empowers various applications. This paper develops a scalable first-order optimization-based method that computes optimal transport to within $varepsilon$ additive accuracy.
  arXiv  Detail & Related papers  (2023-01-30T15:46:39Z)
• BiAdam: Fast Adaptive Bilevel Optimization Methods [104.96004056928474]
  Bilevel optimization has attracted increased interest in machine learning due to its many applications. We provide a useful analysis framework for both the constrained and unconstrained optimization.
  arXiv  Detail & Related papers  (2021-06-21T20:16:40Z)
• Ada-BKB: Scalable Gaussian Process Optimization on Continuous Domain by Adaptive Discretization [21.859940486704264]
  An algorithm such as GPUCB has prohibitive computational complexity. A norere algorithm for functions corroborates the real problem of continuous optimization.
  arXiv  Detail & Related papers  (2021-06-16T07:55:45Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  Bilevel optimization has been widely applied in many important machine learning applications. We propose two new algorithms for bilevel optimization. We show that both algorithms achieve the complexity of $mathcalO(epsilon-1.5)$, which outperforms all existing algorithms by the order of magnitude.
  arXiv  Detail & Related papers  (2021-06-08T21:05:30Z)
• Bayesian Algorithm Execution: Estimating Computable Properties of Black-box Functions Using Mutual Information [78.78486761923855]
  In many real world problems, we want to infer some property of an expensive black-box function f, given a budget of T function evaluations. We present a procedure, InfoBAX, that sequentially chooses queries that maximize mutual information with respect to the algorithm's output. On these problems, InfoBAX uses up to 500 times fewer queries to f than required by the original algorithm.
  arXiv  Detail & Related papers  (2021-04-19T17:22:11Z)
• Grouped Variable Selection with Discrete Optimization: Computational and Statistical Perspectives [9.593208961737572]
  We present a new algorithmic framework for grouped variable selection that is based on discrete mathematical optimization. Our methodology covers both high-dimensional linear regression and non- additive modeling with sparse programming. Our exact algorithm is based on a standalone branch-and-bound (BnB) framework, which can solve the associated mixed integer (MIP) problem to certified optimality.
  arXiv  Detail & Related papers  (2021-04-14T19:21:59Z)
• Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
  We study the problem of minimizing the population loss given i.i.d. samples from a distribution over convex loss functions. A recent work of Bassily et al. has established the optimal bound on the excess population loss achievable given $n$ samples. We describe two new techniques for deriving convex optimization algorithms both achieving the optimal bound on excess loss and using $O(minn, n2/d)$ gradient computations.
  arXiv  Detail & Related papers  (2020-05-10T19:52:03Z)

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.