論文の概要: Approximation of Box Decomposition Algorithm for Fast Hypervolume-Based Multi-Objective Optimization
- arxiv url: http://arxiv.org/abs/2512.05825v1
- Date: Fri, 05 Dec 2025 15:43:06 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-12-13 22:40:57.088949
- Title: Approximation of Box Decomposition Algorithm for Fast Hypervolume-Based Multi-Objective Optimization
- Title（参考訳）: 高速ハイパーボリュームに基づく多目的最適化のためのボックス分解アルゴリズムの近似
- Authors: Shuhei Watanabe,
- Abstract要約: ハイパーボリューム(HV)に基づくベイズ最適化(BO)は、多目的意思決定における標準的なアプローチの1つである。
取得関数を最適化する計算コストは依然として大きなボトルネックである。
現在、厳密なアルゴリズムの記述が文献から欠落している。
- 参考スコア（独自算出の注目度）: 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.
- Abstract（参考訳）: ハイパーボリューム(HV)に基づくベイズ最適化(BO)は、多目的意思決定における標準的なアプローチの1つである。
しかし、取得関数を最適化する計算コストは、主にHV改善計算の費用がかかるため、大きなボトルネックのままである。
HVボックス分解は、しばしば正確な改善計算に対処する効率的な方法であるが、Lacour et al (2017) が提案した最悪のケースでは、超ポリノミカルメモリの複雑さ$O(MN^{\lfloor \frac{M + 1}{2} \rfloor})$に悩まされている。
この問題を解決するため、Couckuyt et al (2012) は近似アルゴリズムを採用した。
しかし、現在では厳密なアルゴリズムの記述が文献から欠落している。
本稿では,この近似アルゴリズムの数学的およびアルゴリズム的詳細を包括的に提供することにより,このギャップを埋める。
関連論文リスト
- Approximation Algorithms for Preference Aggregation Using CP-Nets [3.337244446073836]
本稿では,条件付き選好ネットワーク(CP-nets)上での選好を集約する近似アルゴリズムの設計と解析について述べる。
その焦点は、一般に最適な解が指数関数的な大きさであることが知られている、いわゆる「エンフスワップ」よりも、優先的な選好を集約することである。
論文 参考訳（メタデータ） (2023-12-14T17:31:38Z) - Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。
多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。
そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文 参考訳（メタデータ） (2023-07-17T20:11:56Z) - Learning distributed representations with efficient SoftMax normalization [3.8673630752805437]
有界ノルムを持つ埋め込みベクトルに対して$rm SoftMax(XYT)$の正規化定数を計算する線形時間近似を提案する。
本稿では,提案手法が競合手法よりも高い精度あるいは同等の精度を達成できるような事前学習した埋め込みデータセットについて述べる。
提案アルゴリズムは解釈可能で,任意の埋め込み問題に容易に適応できる。
論文 参考訳（メタデータ） (2023-03-30T15:48:26Z) - A One-Sample Decentralized Proximal Algorithm for Non-Convex Stochastic
Composite Optimization [10.762749887051546]
本稿では,Proxcal$DASA-GTとProxcal$DASA-Aの2時間スケールアルゴリズムを提案する。
以前の作業とは異なり、我々のアルゴリズムは、大きなバッチサイズ、より複雑な単位演算、より強い仮定を必要とせずに、同等の複雑さを達成する。
論文 参考訳（メタデータ） (2023-02-20T05:16:18Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳（メタデータ） (2023-01-30T15:46:39Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳（メタデータ） (2021-06-08T21:05:30Z) - Bayesian Algorithm Execution: Estimating Computable Properties of
Black-box Functions Using Mutual Information [78.78486761923855]
多くの現実世界では、T関数の評価の予算を考えると、高価なブラックボックス関数 f の性質を推測したい。
本稿では,アルゴリズムの出力に対して相互情報を最大化するクエリを逐次選択する手法InfoBAXを提案する。
これらの問題に対してInfoBAXは、元のアルゴリズムで要求されるより500倍少ないクエリをfに使用する。
論文 参考訳（メタデータ） (2021-04-19T17:22:11Z) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。
Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。
本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文 参考訳（メタデータ） (2020-05-10T19:52:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。