論文の概要: Biased Pareto Optimization for Subset Selection with Dynamic Cost Constraints

• arxiv url: http://arxiv.org/abs/2406.12383v2
• Date: Mon, 9 Sep 2024 07:37:07 GMT
• ステータス: 処理完了
• システム内更新日: 2024-09-11 02:01:46.345898
• Title: Biased Pareto Optimization for Subset Selection with Dynamic Cost Constraints
• Title（参考訳）: 動的コスト制約付きサブセット選択のためのバイアスパレート最適化
• Authors: Dan-Xuan Liu, Chao Qian,
• Abstract要約: コスト制約付きサブセット選択は、与えられた予算を超えることなく、単調な目的関数を最大化するための基底セットからサブセットを選択することを目的としている。 我々は、動的環境に適した偏り選択とウォームアップ戦略でPOMCを強化したBPODCを提案する。
• 参考スコア（独自算出の注目度）: 23.67466377818849
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Subset selection with cost constraints aims to select a subset from a ground set to maximize a monotone objective function without exceeding a given budget, which has various applications such as influence maximization and maximum coverage. In real-world scenarios, the budget, representing available resources, may change over time, which requires that algorithms must adapt quickly to new budgets. However, in this dynamic environment, previous algorithms either lack theoretical guarantees or require a long running time. The state-of-the-art algorithm, POMC, is a Pareto optimization approach designed for static problems, lacking consideration for dynamic problems. In this paper, we propose BPODC, enhancing POMC with biased selection and warm-up strategies tailored for dynamic environments. We focus on the ability of BPODC to leverage existing computational results while adapting to budget changes. We prove that BPODC can maintain the best known $(\alpha_f/2)(1-e^{-\alpha_f})$-approximation guarantee when the budget changes. Experiments on influence maximization and maximum coverage show that BPODC adapts more effectively and rapidly to budget changes, with a running time that is less than that of the static greedy algorithm.
• Abstract（参考訳）: コスト制約付きサブセット選択は、与えられた予算を超えることなく単調な目的関数を最大化するための基底セットからサブセットを選択することを目的としており、影響の最大化や最大カバレッジなど様々な応用がある。 現実のシナリオでは、利用可能なリソースを表す予算は時間とともに変化する可能性があるため、アルゴリズムは新しい予算に迅速に適応する必要がある。 しかし、この動的な環境では、従来のアルゴリズムは理論的な保証を欠いているか、長い時間を要するかのいずれかである。 最先端のアルゴリズムであるPOMCは静的問題に対するPareto最適化手法であり、動的問題に対する考慮を欠いている。 本稿では,BPODCを提案し,偏りのある選択と動的環境に適したウォームアップ戦略でPOMCを向上する。 我々は予算変更に適応しながら既存の計算結果を活用するBPODCの能力に焦点を当てる。 BPODCは予算変更時に最もよく知られた$(\alpha_f/2)(1-e^{-\alpha_f})$-approximationを維持できることを示す。 影響の最大化と最大カバレッジの実験により、BPODCは静的グリードアルゴリズムよりも実行時間が短いため、予算変更に対してより効率的かつ迅速に適応できることが示された。

関連論文リスト

• An accelerate Prediction Strategy for Dynamic Multi-Objective Optimization [7.272641346606365]
  本稿では,進化的アルゴリズムフレームワークにおける予測戦略の高速化のための新しいアプローチを提案する。 本稿では,アルゴリズムの探索動作を予測・調整するために,二階微分を組み込んだ適応予測戦略を提案する。 標準DMOPのベンチマーク問題を用いて,提案手法の性能を4つの最先端アルゴリズムと比較した。
  論文  参考訳（メタデータ） (2024-10-08T08:13:49Z)
• An adaptive approach to Bayesian Optimization with switching costs [0.8246494848934447]
  逐次実験設計の資源制約設定に対するベイズ最適化の修正について検討する。 この逐次的問題定式化にプロセス制約付きバッチアルゴリズムを2つ適用し,コスト認識とコスト非依存の2つの新しい手法を提案する。
  論文  参考訳（メタデータ） (2024-05-14T21:55:02Z)
• Stochastic Multi-round Submodular Optimization with Budget [7.902059578326225]
  我々は、アイテムの部分集合上で定義された単調部分モジュラー目的関数の和を、複数のラウンドで適応的に最大化することを目指している。 目的関数はイベントの実現にも依存しており、全てのラウンドで選択できるアイテムの総数は、限られた予算で制限されている。
  論文  参考訳（メタデータ） (2024-04-21T18:24:43Z)
• Welfare Maximization Algorithm for Solving Budget-Constrained Multi-Component POMDPs [2.007262412327553]
  本稿では,多成分予算制約POMDPの最適ポリシを求めるアルゴリズムを提案する。 提案アルゴリズムは,現在実施中であるポリシーを大幅に上回っていることを示す。
  論文  参考訳（メタデータ） (2023-03-18T01:43:47Z)
• Robust Subset Selection by Greedy and Evolutionary Pareto Optimization [23.0838604893412]
  サブセット選択は、ある目的関数を最大化するために、グラウンドセットからサブセットを選択することを目的としている。 グリーディアルゴリズムは1-e-betagamma$の近似比を得ることができ、$beta$と$gamma$は対象関数の相関と部分モジュラリティ比である。
  論文  参考訳（メタデータ） (2022-05-03T11:00:54Z)
• Result Diversification by Multi-objective Evolutionary Algorithms with Theoretical Guarantees [94.72461292387146]
  両目的探索問題として結果の多様化問題を再構成し,多目的進化アルゴリズム(EA)を用いて解くことを提案する。 GSEMOが最適時間近似比1/2$を達成できることを理論的に証明する。 目的関数が動的に変化すると、GSEMOはこの近似比をランニングタイムで維持することができ、Borodinらによって提案されたオープンな問題に対処する。
  論文  参考訳（メタデータ） (2021-10-18T14:00:22Z)
• Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
  高精度リコール曲線(AUPRC)に基づく領域の最適化について検討し,不均衡なタスクに広く利用されている。 我々は、$O (1/epsilon4)$のより優れた反復による、$epsilon$定常解を見つけるための新しい運動量法を開発する。 また,O(1/epsilon4)$と同じ複雑さを持つ適応手法の新たなファミリを設計し,実際により高速な収束を享受する。
  論文  参考訳（メタデータ） (2021-07-02T16:21:52Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• On the Optimality of Batch Policy Optimization Algorithms [106.89498352537682]
  バッチポリシー最適化は、環境と対話する前に既存のデータをポリシー構築に活用することを検討する。 信頼調整インデックスアルゴリズムは楽観的,悲観的,中立的いずれであってもミニマックス最適であることを示す。 最適値予測の本来の難易度を考慮した新しい重み付き最小値基準を提案する。
  論文  参考訳（メタデータ） (2021-04-06T05:23:20Z)
• Adaptivity of Stochastic Gradient Methods for Nonconvex Optimization [71.03797261151605]
  適応性は現代最適化理論において重要であるが、研究されていない性質である。 提案アルゴリズムは,PL目標に対して既存のアルゴリズムよりも優れた性能を保ちながら,PL目標に対して最適な収束性を実現することを実証した。
  論文  参考訳（メタデータ） (2020-02-13T05:42:27Z)
• Provably Efficient Exploration in Policy Optimization [117.09887790160406]
  本稿では,最適化アルゴリズム(OPPO)の最適変種を提案する。 OPPO は $tildeO(sqrtd2 H3 T )$ regret を達成する。 我々の知る限りでは、OPPOは、探索する最初の証明可能な効率的なポリシー最適化アルゴリズムである。
  論文  参考訳（メタデータ） (2019-12-12T08:40:02Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。