論文の概要: Analysis of Multitasking Pareto Optimization for Monotone Submodular Problems
- arxiv url: http://arxiv.org/abs/2604.15068v1
- Date: Thu, 16 Apr 2026 14:31:19 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-04-17 21:29:31.946601
- Title: Analysis of Multitasking Pareto Optimization for Monotone Submodular Problems
- Title（参考訳）: 単調部分モジュラ問題に対するマルチタスクパレート最適化の解析
- Authors: Liam Wigney, Frank Neumann,
- Abstract要約: 一つの実行で複数の関連する問題を解くのに有効な方法であるマルチタスクの定式化を導入する。
厳密な実行時解析を用いて,導入したマルチタスクアプローチが与えられた各問題に対して1-1/eの$-approximationを得るまでの期待時間を分析する。
- 参考スコア（独自算出の注目度）: 6.164863213336097
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Pareto optimization via evolutionary multi-objective algorithms has been shown to efficiently solve constrained monotone submodular functions. Traditionally when solving multiple problems, the algorithm is run for each problem separately. We introduce multitasking formulations of these problems that are an effective way to solve multiple related problems with a single run. In our setting the given problems share a monotone submodular function $f$ but have different knapsack constraints. We examine the case where elements within a constraint have the same cost and show that our multitasking formulations result in small Pareto fronts. This allows the population to share solutions between all problems leading to significant improvements compared to running several classical approaches independently. Using rigorous runtime analysis, we analyze the expected time until the introduced multitasking approaches obtain a $(1-1/e)$-approximation for each of the given problems. Our experimental investigations for the maximum coverage problem give further insight into the dynamics behind how the approach works and doesn't work in practice for problems where elements within a constraint also have varied costs.
- Abstract（参考訳）: 進化的多目的アルゴリズムによるパレート最適化は、制約付き単調部分モジュラ函数を効率的に解くことが示されている。
伝統的に、複数の問題を解決する場合、アルゴリズムは各問題に対して別々に実行される。
一つの実行で複数の関連する問題を解くのに有効な方法である,これらの問題のマルチタスク定式化を導入する。
我々の設定では、与えられた問題は単調部分モジュラ函数$f$を共有するが、異なるknapsack制約を持つ。
制約内の要素が同じコストを持つ場合について検討し、マルチタスクの定式化によってパレートフロントが小さくなることを示す。
これにより、複数の古典的アプローチを独立して実行することと比較して、すべての問題間で解を共有することができる。
厳密な実行時解析を用いて,導入したマルチタスクアプローチが与えられた各問題に対して1-1/eの$-approximationを得るまでの期待時間を分析する。
最大カバレッジ問題に対する実験的な調査は、アプローチの動作の背景にあるダイナミクスについてさらなる洞察を与え、制約内の要素がコストも異なる問題に対して実際に機能しないようにする。
関連論文リスト
- Consistent Submodular Maximization [27.266085572522847]
定性制約下での単調部分モジュラ関数の最大化は、データマイニングや機械学習におけるいくつかの応用において古典的な最適化課題である。
本稿では, 安定解を持ちながら, ストリーミング方式で要素が到着し, 最適解に対する定数近似が維持されるという, 一貫性の制約のある動的環境において, この問題を考察する。
この設定では、一貫性と近似品質のトレードオフが異なるアルゴリズムを提供しています。
論文 参考訳（メタデータ） (2024-05-30T11:59:58Z) - UCB-driven Utility Function Search for Multi-objective Reinforcement Learning [51.00436121587591]
マルチオブジェクト強化学習(MORL)エージェントでは、意思決定行動の最適化を行う。
重みベクトル w でパラメトリした線型効用関数の場合に焦点を当てる。
学習過程の異なる段階で最も有望な重みベクトルを効率的に探索する上信頼境界に基づく手法を提案する。
論文 参考訳（メタデータ） (2024-05-01T09:34:42Z) - Multi-Task Learning with Multi-Task Optimization [31.518330903602095]
最適化されているが、よく分散されたモデルの集合が、1つのアルゴリズムパスで異なるトレードオフを具現化していることを示す。
様々な問題設定を解決するために,マルチタスク最適化を用いたマルチタスク学習を提案する。
論文 参考訳（メタデータ） (2024-03-24T14:04:40Z) - Pareto Manifold Learning: Tackling multiple tasks via ensembles of
single-task models [50.33956216274694]
マルチタスク学習(MTL)では、タスクは、ソリューションへの最適化を導くのではなく、互いに達成したパフォーマンスを競い、制限することができる。
重み空間におけるアンサンブル手法であるTextitPareto Manifold Learningを提案する。
論文 参考訳（メタデータ） (2022-10-18T11:20:54Z) - Pareto Set Learning for Neural Multi-objective Combinatorial
Optimization [6.091096843566857]
多目的最適化(MOCO)の問題は、現実世界の多くのアプリケーションで見られる。
我々は,与えられたMOCO問題に対するパレート集合全体を,探索手順を伴わずに近似する学習ベースアプローチを開発した。
提案手法は,多目的走行セールスマン問題,マルチコンディショニング車両ルーティング問題,複数クナップサック問題において,ソリューションの品質,速度,モデル効率の面で,他の方法よりも優れていた。
論文 参考訳（メタデータ） (2022-03-29T09:26:22Z) - Efficient Continuous Pareto Exploration in Multi-Task Learning [34.41682709915956]
本稿では,機械学習問題における最適解の連続解析手法を提案する。
サンプルベーススパース線形システムを提案することにより、現代の機械学習問題に対する多目的最適化の理論結果をスケールアップする。
論文 参考訳（メタデータ） (2020-06-29T23:36:20Z) - Pareto Multi-Task Learning [53.90732663046125]
マルチタスク学習は複数の相関タスクを同時に解くための強力な方法である。
異なるタスクが互いに衝突する可能性があるため、すべてのタスクを最適化するひとつのソリューションを見つけることは、しばしば不可能である。
近年,マルチタスク学習を多目的最適化として活用することにより,タスク間のトレードオフが良好である1つのパレート最適解を求める方法が提案されている。
論文 参考訳（メタデータ） (2019-12-30T08:58:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。