論文の概要: Multinoulli Extension: A Lossless Continuous Relaxation for Partition-Constrained Subset Selection

• arxiv url: http://arxiv.org/abs/2603.21492v1
• Date: Mon, 23 Mar 2026 02:30:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-24 19:11:39.446316
• Title: Multinoulli Extension: A Lossless Continuous Relaxation for Partition-Constrained Subset Selection
• Title（参考訳）: Multinoulli Extension: 分割制約されたサブセット選択のためのロスレス連続緩和
• Authors: Qixin Zhang, Wei Huang, Yan Sun, Yao Shu, Yi Yu, Dacheng Tao,
• Abstract要約: 我々はパラメータフリーで、歪んだ局所探索法と同じ近似保証を実現できるMultinoulliSCGという新しいアルゴリズムを導入する。 また、分割制約に関する未探索オンラインサブセット選択問題に対して、Multinoulli-CGとMultinoulli-GAGAという2つの新しいオンラインアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 60.07018090570548
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Identifying the most representative subset for a close-to-submodular objective while satisfying the predefined partition constraint is a fundamental task with numerous applications in machine learning. However, the existing distorted local-search methods are often hindered by their prohibitive query complexities and the rigid requirement for prior knowledge of difficult-to-obtain structural parameters. To overcome these limitations, we introduce a novel algorithm titled Multinoulli-SCG, which not only is parameter-free, but also can achieve the same approximation guarantees as the distorted local-search methods with significantly fewer function evaluations. More specifically, when the objective function is monotone $α$-weakly DR-submodular or $(γ,β)$-weakly submodular, our Multinoulli-SCG algorithm can attain a value of $(1-e^{-α})\text{OPT}-ε$ or $(\frac{γ^{2}(1-e^{-(β(1-γ)+γ^2)})}{β(1-γ)+γ^2})\text{OPT}-ε$ with only $O(1/ε^{2})$ function evaluations, where OPT denotes the optimal value. The cornerstone of our Multinoulli-SCG algorithm is an innovative continuous-relaxation framework named Multinoulli Extension(ME), which can effectively convert the discrete subset selection problem subject to partition constraints into a solvable continuous maximization focused on learning the optimal multinoulli priors across the concerned partition. In sharp contrast with the well-established multi-linear extension for submodular subset selection, a notable advantage of our proposed ME is its intrinsic capacity to provide a lossless rounding scheme for any set function. Furthermore, based on our proposed ME, we also present two novel online algorithms, namely, Multinoulli-OSCG and Multinoulli-OSGA, for the unexplored online subset selection problems over partition constraints.
• Abstract（参考訳）: 定義済みのパーティション制約を満足しながら、サブモジュールに近い目的のために最も代表的なサブセットを特定することは、機械学習における多くのアプリケーションに対する基本的なタスクである。 しかし、既存のゆがんだ局所探索法は、しばしばその禁止されたクエリの複雑さと、難解な構造パラメータの事前知識に対する厳密な要求によって妨げられる。 これらの制約を克服するため,Multinoulli-SCGという新しいアルゴリズムを導入し,パラメータフリーだけでなく,関数評価が著しく少ない歪み局所探索法と同じ近似保証を実現する。 より具体的には、目的関数がモノトン$α$-weakly DR-submodularまたは$(γ,β)$-weakly submodularであるとき、我々のMultinoulli-SCGアルゴリズムは、$(1-e^{-α})text{OPT}-ε$または$(\frac{γ^{2}(1-e^{-(β(1-γ)+γ^2)})}{β(1-γ)+γ^2})text{OPT}-ε$の値を得ることができる。 本アルゴリズムの基盤は,分割制約を受ける離散部分集合選択問題を,関係する分割にまたがる最適乗算前の学習に焦点をあてた解決可能な連続最大化に効果的に変換できる,Multinoulli Extension(ME)と呼ばれる革新的連続緩和フレームワークである。 部分モジュラー部分集合選択のためのよく確立された多重線型拡張とは対照的に、提案した ME の顕著な利点は、任意の集合関数に対して損失のない丸めスキームを提供する本質的な能力である。 さらに,提案したMEに基づいて,分割制約に関する未探索オンラインサブセット選択問題に対して,Multinoulli-OSCGとMultinoulli-OSGAという2つの新しいオンラインアルゴリズムを提案する。

関連論文リスト

• $γ$-weakly $θ$-up-concavity: Linearizable Non-Convex Optimization with Applications to DR-Submodular and OSS Functions [52.031993908548294]
  このような関数の広範な近似を特徴付ける新しい一階述語条件である$-weakly $-up-concavityを導入する。 本フレームワークは,DR-サブモジュラークラスに対する最適係数を復元し,既存の近似係数を大幅に改善する。
  論文  参考訳（メタデータ） (2026-02-13T22:34:44Z)
• Effective Policy Learning for Multi-Agent Online Coordination Beyond Submodular Objectives [64.16056378603875]
  マルチエージェントオンライン協調問題に対する2つのポリシー学習アルゴリズムを提案する。 1つめの textttMA-SPL は MA-OC 問題に対して最適な$(fracce)$-approximation を達成することができる。 第2のオンラインアルゴリズムである textttMA-MPL は同じ近似比を同時に維持できる。
  論文  参考訳（メタデータ） (2025-09-26T17:16:34Z)
• 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)
• Decomposed Global Optimization for Robust Point Matching with Low-Dimensional Branching [41.05165517541873]
  部分重なり合う点集合を整列する新しい大域的最適化手法を提案する。 本手法は非剛性変形, 位置雑音, 外れ値に優れた強靭性を示す。 2次元および3次元合成および実世界のデータを用いた実験により,本手法は最先端の手法と比較して,外れ値に対して優れた強靭性を示すことが示された。
  論文  参考訳（メタデータ） (2024-05-14T13:28:57Z)
• Non-monotone Sequential Submodular Maximization [13.619980548779687]
  我々は、$k$の重み付けが最大になるように、基底セット$V$から$k$の項目群を選択してランク付けすることを目指している。 本研究の結果は,レコメンデーションシステムや最適化など,様々な分野に影響を及ぼす。
  論文  参考訳（メタデータ） (2023-08-16T19:32:29Z)
• Robust Subset Selection by Greedy and Evolutionary Pareto Optimization [23.0838604893412]
  サブセット選択は、ある目的関数を最大化するために、グラウンドセットからサブセットを選択することを目的としている。 グリーディアルゴリズムは1-e-betagamma$の近似比を得ることができ、$beta$と$gamma$は対象関数の相関と部分モジュラリティ比である。
  論文  参考訳（メタデータ） (2022-05-03T11:00:54Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• Submodular Maximization in Clean Linear Time [42.51873363778082]
  我々は,濃度(サイズ)制約下での部分モジュライメーションの厳密な1-1/e$近似を保証する,最初の決定論的アルゴリズムを提供する。 解に対して許容される濃度が一定であるとき、関数評価のサブ線形数を作るアルゴリズムは、任意の定数比を保証できないことを示す。 我々は,映画推薦,位置情報要約,twitterテキスト要約,ビデオ要約など,複数のリアルタイム機械学習アプリケーションにおいて,我々のアルゴリズムを広範囲に評価する。
  論文  参考訳（メタデータ） (2020-06-16T17:06:45Z)

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

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