論文の概要: 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の性能を検証する実験を行う。
関連論文リスト
- Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
離散部分モジュラー問題を連続的に最適化するために,$textbfMA-OSMA$アルゴリズムを提案する。
また、一様分布を混合することによりKLの発散を効果的に活用する、プロジェクションフリーな$textbfMA-OSEA$アルゴリズムも導入する。
我々のアルゴリズムは最先端OSGアルゴリズムによって提供される$(frac11+c)$-approximationを大幅に改善する。
論文 参考訳（メタデータ） (2025-02-07T15:57:56Z) - Pareto Optimization with Robust Evaluation for Noisy Subset Selection [34.83487850400559]
サブセット選択は最適化の基本的な問題であり、影響やスパース回帰といった幅広い応用がある。
欲求アルゴリズムや進化進化的POSSを含む従来のアルゴリズムは、ノイズの多い環境で苦労するか、過剰な計算資源を消費する。
本稿では,頑健な評価関数を最大化し,同時にサブセットサイズを最小化する,雑音性サブセット選択(PORE)のためのロバスト評価を用いたパレート最適化に基づく新しい手法を提案する。
論文 参考訳（メタデータ） (2025-01-12T14:04:20Z) - Fair Submodular Cover [18.37610521373708]
フェア・サブモジュラー被覆 (FSC) の研究は、与えられた基底集合$U$, 単調部分モジュラー関数 $f:2UtomathbbR_ge 0$, しきい値$tau$ が与えられる。
まず、二項近似比を$(frac1epsilon, 1-O(epsilon))$とするFSCの離散アルゴリズムを導入する。
次に、$(frac1epsilon, 1-O(epsilon))$-を達成する連続アルゴリズムを示す。
論文 参考訳（メタデータ） (2024-07-05T18:37:09Z) - Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
本稿では,バッチ取得のための新しいグリーディ型サブセット選択アルゴリズムを提案する。
赤蛍光タンパク質に関する実験により,提案手法は1.69倍少ないクエリでベースライン性能を達成できることが判明した。
論文 参考訳（メタデータ） (2024-06-21T05:57:08Z) - 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) - 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) - High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。
そこで我々は,勾配クリッピングを伴う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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。