論文の概要: Robust Subset Selection by Greedy and Evolutionary Pareto Optimization
- arxiv url: http://arxiv.org/abs/2205.01415v2
- Date: Sun, 8 May 2022 12:52:44 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-14 12:00:58.464104
- Title: Robust Subset Selection by Greedy and Evolutionary Pareto Optimization
- Title(参考訳): グレディと進化的パレート最適化によるロバストサブセット選択
- Authors: Chao Bian, Yawen Zhou, Chao Qian
- Abstract要約: サブセット選択は、ある目的関数を最大化するために、グラウンドセットからサブセットを選択することを目的としている。
グリーディアルゴリズムは1-e-betagamma$の近似比を得ることができ、$beta$と$gamma$は対象関数の相関と部分モジュラリティ比である。
- 参考スコア(独自算出の注目度): 23.0838604893412
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Subset selection, which aims to select a subset from a ground set to maximize
some objective function, arises in various applications such as influence
maximization and sensor placement. In real-world scenarios, however, one often
needs to find a subset which is robust against (i.e., is good over) a number of
possible objective functions due to uncertainty, resulting in the problem of
robust subset selection. This paper considers robust subset selection with
monotone objective functions, relaxing the submodular property required by
previous studies. We first show that the greedy algorithm can obtain an
approximation ratio of $1-e^{-\beta\gamma}$, where $\beta$ and $\gamma$ are the
correlation and submodularity ratios of the objective functions, respectively;
and then propose EPORSS, an evolutionary Pareto optimization algorithm that can
utilize more time to find better subsets. We prove that EPORSS can also be
theoretically grounded, achieving a similar approximation guarantee to the
greedy algorithm. In addition, we derive the lower bound of $\beta$ for the
application of robust influence maximization, and further conduct experiments
to validate the performance of the greedy algorithm and EPORSS.
- Abstract(参考訳): ある目的関数を最大化するために基底集合からサブセットを選択することを目的としたサブセット選択は、影響の最大化やセンサ配置などの様々な応用に現れる。
しかし、現実のシナリオでは、不確実性によって起こりうる多くの客観的関数に対してロバストな部分集合を見つけることがしばしば必要であり、結果としてロバストな部分集合の選択が問題となる。
本稿では,単調目的関数を用いたロバスト部分集合の選択を考察し,これまでの研究で要求される部分モジュラー特性を緩和する。
まず, 目的関数の相関係数と部分モジュラリティ比である$\beta$と$\gamma$の近似比を求め, そして, より優れた部分集合を見つけるためにより多くの時間を利用する進化的パレート最適化アルゴリズムであるEPORSSを提案する。
我々は、EPORSSも理論的に基礎化可能であることを証明し、greedyアルゴリズムに類似した近似保証を実現する。
さらに,ロバストな影響最大化の適用のために$\beta$の上限を導出し,さらにグリーディアルゴリズムとeporsの性能を検証する実験を行う。
関連論文リスト
- Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳(メタデータ) (2023-12-13T11:08:25Z) - Composable Coresets for Determinant Maximization: Greedy is Almost
Optimal [2.849878266188877]
a set of $n$ in $mathbbRd$, the emphdeterminant problem of the emphdeterminant problem to pick $k$ vectors with the maximum volume。
広く使われているGreedyアルゴリズムは、O(k)3k$の近似係数がほぼ最適である構成可能なコアセットも提供する。
論文 参考訳(メタデータ) (2023-09-26T21:46:44Z) - Submodular Reinforcement Learning [77.97471858326077]
強化学習(RL)では、状態の報酬は通常加法的と見なされ、マルコフの仮定に従って、それらは以前に訪れた状態に対して$textitindependent$である。
カバー範囲制御、実験設計、情報経路計画といった多くの重要な応用において、報酬は自然にリターンを減少させ、すなわち、それらの価値は以前に訪れた同様の状態から減少する。
減少するリターンをキャプチャするサブモジュール集合関数をモデルとした,より汎用的で非付加的(かつ履歴に依存しない)報酬を最適化するパラダイムである$textitsubmodular RL$ (SubRL)を提案する。
論文 参考訳(メタデータ) (2023-07-25T09:46:02Z) - BOtied: Multi-objective Bayesian optimization with tied multivariate
ranks [49.85896045032822]
非支配解と最高多変量階との自然な関係を示し、これは合同累積分布関数(CDF)の最外層線と一致する。
我々はCDFインジケータに基づくBOtiedと呼ばれる取得関数を提案する。
論文 参考訳(メタデータ) (2023-06-01T04:50:06Z) - Multiobjective Ranking and Selection Using Stochastic Kriging [0.0]
我々は,複数の矛盾する目的を同時に最適化し,シミュレーションによってのみ観測できる多目的シミュレーション最適化問題を考察する。
最適性は、他の目的の質を損なうことなく、目的を改善できないことを意味する。
提案手法は, 最適性能の解を同定する際の誤差を減らすため, 多目的ランキングと選択法を提案する。
論文 参考訳(メタデータ) (2022-09-05T23:51:07Z) - 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) - Near-Optimal High Probability Complexity Bounds for Non-Smooth
Stochastic Optimization with Heavy-Tailed Noise [63.304196997102494]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
既存の非滑らか凸最適化法は、負のパワーまたは対数的な信頼度に依存する境界の複雑さを持つ。
クリッピングを用いた2つの勾配法に対して, 新たなステップサイズルールを提案する。
論文 参考訳(メタデータ) (2021-06-10T17:54:21Z) - Bayesian Optimization of Risk Measures [7.799648230758491]
我々は、$rho[F(x, W) ]$ という形の目的関数のベイズ最適化を考える。
目的関数の構造を利用してサンプリング効率を大幅に向上する新しいベイズ最適化アルゴリズム群を提案する。
論文 参考訳(メタデータ) (2020-07-10T18:20:46Z) - Differentiable Greedy Submodular Maximization: Guarantees, Gradient
Estimators, and Applications [15.191184049312467]
我々は,単調部分関数のグリーディアルゴリズムを微分可能とする理論的に保証された多元性フレームワークを確立する。
乱数化によってグリーディアルゴリズムを滑らかにし、濃度や$kappa$-extensible(拡張可能なシステム制約)の場合に期待する元の近似保証をほぼ回復することを示した。
論文 参考訳(メタデータ) (2020-05-06T03:33:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。