論文の概要: Approximating Pareto Frontiers in Stochastic Multi-Objective Optimization via Hashing and Randomization
- arxiv url: http://arxiv.org/abs/2604.01098v1
- Date: Wed, 01 Apr 2026 16:24:13 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-04-02 16:44:32.087528
- Title: Approximating Pareto Frontiers in Stochastic Multi-Objective Optimization via Hashing and Randomization
- Title（参考訳）: ハッシュとランダム化による確率的多目的最適化におけるパレートフロンティアの近似
- Authors: Jinzhao Li, Nan Jiang, Yexiang Xue,
- Abstract要約: SMOO(Multi-Objective Optimization)は、不確実な環境での複数の目的のトレードオフを行う上で重要である。
我々は,確率1-$のアルゴリズムであるXOR-SMOOを提案し,SMOOのパレートフロンティアを$$ $-approximate Pareto Frontiers で取得する。
XOR-SMOOはSMOOソルバの実用性と信頼性を著しく向上させた。
- 参考スコア（独自算出の注目度）: 21.60781694711817
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Stochastic Multi-Objective Optimization (SMOO) is critical for decision-making trading off multiple potentially conflicting objectives in uncertain environments. SMOO aims at identifying the Pareto frontier, which contains all mutually non-dominating decisions. The problem is highly intractable due to the embedded probabilistic inference, such as computing the marginal, posterior probabilities, or expectations. Existing methods, such as scalarization, sample average approximation, and evolutionary algorithms, either offer arbitrarily loose approximations or may incur prohibitive computational costs. We propose XOR-SMOO, a novel algorithm that with probability $1-δ$, obtains $γ$-approximate Pareto frontiers ($γ>1$) for SMOO by querying an SAT oracle poly-log times in $γ$ and $δ$. A $γ$-approximate Pareto frontier is only below the true frontier by a fixed, multiplicative factor $γ$. Thus, XOR-SMOO solves highly intractable SMOO problems (\#P-hard) with only queries to SAT oracles while obtaining tight, constant factor approximation guarantees. Experiments on real-world road network strengthening and supply chain design problems demonstrate that XOR-SMOO outperforms several baselines in identifying Pareto frontiers that have higher objective values, better coverage of the optimal solutions, and the solutions found are more evenly distributed. Overall, XOR-SMOO significantly enhanced the practicality and reliability of SMOO solvers.
- Abstract（参考訳）: 確率的多目的最適化(Stochastic Multi-Objective Optimization, SMOO)は、不確実な環境で複数の潜在的に矛盾する目標をトレードオフするために重要である。
SMOOはParetoフロンティアを識別することを目的としている。
この問題は、限界確率、後続確率、または期待値の計算のような組込み確率的推論のため、非常に難解である。
スカラー化、サンプル平均近似、進化的アルゴリズムといった既存の手法は、任意に緩やかな近似を提供するか、禁止的な計算コストを発生させる可能性がある。
我々は,確率1-δ$のアルゴリズムであるXOR-SMOOを提案する。このアルゴリズムは,SATオラクルのポリログを$γ$と$δ$でクエリすることで,SMOOに対して$γ$-approximate Pareto Frontiers(γ>1$)を得る。
γ$-近似パレートフロンティアは、固定された乗法係数$γ$によって真のフロンティアより下にある。
したがって、XOR-SMOOはSATオーラクルへのクエリのみを伴って高度に難解なSMOO問題(\#P-hard)を解決し、厳密な定数係数近似の保証を得る。
実世界の道路網の強化とサプライチェーン設計問題に対する実験により、XOR-SMOOは、より高い目標値を持つパレートフロンティアを識別し、最適解のカバレッジを向上し、より均等に分散したソリューションを識別する上で、いくつかのベースラインよりも優れていることが示された。
全体として、XOR-SMOOはSMOOソルバの実用性と信頼性を著しく向上させた。
関連論文リスト
- Multi-LLM Query Optimization [1.7435005683276596]
我々は、ステートワイドなエラー制約を受ける総クエリコストを最小限に抑える、堅牢でオフラインなクエリ計画問題を定式化する。
本研究は,サロゲート保存コストと真の最適コストとの比が,誤差耐性が小さくなるにつれて1つに収束することを示す。
論文 参考訳（メタデータ） (2026-03-24T19:51:57Z) - Almost Asymptotically Optimal Active Clustering Through Pairwise Observations [59.20614082241528]
そこで本研究では, ノイズと能動的に収集された応答を用いて, M$アイテムを未知数の$K$個別グループにクラスタリングするための新しい分析フレームワークを提案する。
クラスタリングの精度に対する望ましい信頼性を達成するのに必要なクエリ数の基本的下位境界を確立する。
我々は、一般化された同値比統計の計算可能な変種を開発し、その下限に対する性能ギャップを正確に推定できることを実証的に示す。
論文 参考訳（メタデータ） (2026-02-05T14:16:47Z) - First-order methods for stochastic and finite-sum convex optimization with deterministic constraints [1.411894456054802]
決定論的制約を伴う有限サム凸最適化問題のクラスについて検討する。
本稿では,$epsilon$-$surely feasible optimal$$(epsilon$-SFSO) を求める一階法を提案する。
副生成物として、$epsilon$-SFSOの計算におけるサンプル平均近似法の1次オラクル複雑性結果も導出する。
論文 参考訳（メタデータ） (2025-06-25T17:26:02Z) - Solving Robust Markov Decision Processes: Generic, Reliable, Efficient [3.789219860006095]
マルコフ決定プロセス(MDP)は確率の存在下でのシーケンシャルな意思決定のための確立されたモデルである。
我々は、汎用的で信頼性があり、効率的なRMDPを解くためのフレームワークを提供する。
我々のプロトタイプ実装は、既存のツールよりも桁違いに優れている。
論文 参考訳（メタデータ） (2024-12-13T14:55:48Z) - Theoretical Advantage of Multiobjective Evolutionary Algorithms for Problems with Different Degrees of Conflict [4.8951183832371]
OneMaxMin$_k$ベンチマーククラスは、COCZとOneMinMaxの一般化版である。
2つの典型的な非MOEAアプローチ、スカラー化(重み付きサム法)と$epsilon$-constraint法が検討されている。
我々は、(G)SEMO、MOEA/D、NSGA-II、SMS-EMOAがパレートフロント全体を$O(maxk,1nln n)$でカバーできることを証明する。
論文 参考訳（メタデータ） (2024-08-08T04:09:52Z) - Multi-Agent Bayesian Optimization with Coupled Black-Box and Affine
Constraints [21.38692458445459]
ブラックボックス制約と既知のアフィン制約を結合した分散マルチエージェントベイズ最適化の問題について検討する。
単一エージェントの場合と同様の後悔/違反境界を実現するアルゴリズムが提案されている。
論文 参考訳（メタデータ） (2023-10-02T08:07:36Z) - Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement
Learning: Adaptivity and Computational Efficiency [90.40062452292091]
本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。
我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。
また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-02-21T00:17:24Z) - Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation
Constrained Optimization [88.0031283949404]
多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。
提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
論文 参考訳（メタデータ） (2022-12-19T14:48:54Z) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。
本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文 参考訳（メタデータ） (2022-07-18T12:03:26Z) - Instance-optimality in optimal value estimation: Adaptivity via
variance-reduced Q-learning [99.34907092347733]
本稿では,マルコフ決定過程における最適な$Q$値関数を離散状態と動作で推定する問題を解析する。
局所的なミニマックスフレームワークを用いて、この関数は任意の推定手順の精度の低い境界に現れることを示す。
他方,Q$ラーニングの分散還元版を解析することにより,状態と行動空間の対数的要因まで,下位境界のシャープさを確立する。
論文 参考訳（メタデータ） (2021-06-28T00:38:54Z) - Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
マルコフ決定過程における純粋探索問題について検討する。
エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
論文 参考訳（メタデータ） (2021-06-05T09:16:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。