論文の概要: Batch greedy maximization of non-submodular functions: Guarantees and
applications to experimental design
- arxiv url: http://arxiv.org/abs/2006.04554v3
- Date: Tue, 10 Aug 2021 20:17:42 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-25 18:47:15.970057
- Title: Batch greedy maximization of non-submodular functions: Guarantees and
applications to experimental design
- Title(参考訳): 非モジュラー関数のバッチグリーディ最大化:保証と実験設計への応用
- Authors: Jayanth Jagalur-Mohan, Youssef Marzouk
- Abstract要約: 非部分モジュラーな非退化集合関数の濃度制約に対するグリーディを解析する。
我々の理論的保証は、部分モジュラリティと超モジュラリティ比の組み合わせによって特徴づけられる。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose and analyze batch greedy heuristics for cardinality constrained
maximization of non-submodular non-decreasing set functions. We consider the
standard greedy paradigm, along with its distributed greedy and stochastic
greedy variants. Our theoretical guarantees are characterized by the
combination of submodularity and supermodularity ratios. We argue how these
parameters define tight modular bounds based on incremental gains, and provide
a novel reinterpretation of the classical greedy algorithm using the
minorize-maximize (MM) principle. Based on that analogy, we propose a new class
of methods exploiting any plausible modular bound. In the context of optimal
experimental design for linear Bayesian inverse problems, we bound the
submodularity and supermodularity ratios when the underlying objective is based
on mutual information. We also develop novel modular bounds for the mutual
information in this setting, and describe certain connections to polyhedral
combinatorics. We discuss how algorithms using these modular bounds relate to
established statistical notions such as leverage scores and to more recent
efforts such as volume sampling. We demonstrate our theoretical findings on
synthetic problems and on a real-world climate monitoring example.
- Abstract(参考訳): 非部分モジュラー非減少集合関数の濃度制約最大化のためのバッチグリーディヒューリスティックスを提案し,解析する。
我々は、標準グリーディパラダイムと、その分散グリーディおよび確率的グリーディ変種を考える。
理論的な保証は、サブモジュラリティとスーパーモジュラリティ比の組み合わせによって特徴づけられる。
これらのパラメータが増分ゲインに基づいてタイトなモジュラー境界をどのように定義するかを議論し、最小化最大化(MM)原理を用いた古典的グリードアルゴリズムの新たな解釈を提供する。
その類似性に基づいて、任意の可算モジュラー境界を利用する新しい手法のクラスを提案する。
線形ベイズ逆問題に対する最適実験設計の文脈において,基礎となる目的が相互情報に基づく場合,サブモジュラリティとスーパーモジュラリティ比を限定した。
また、この設定における相互情報のための新しいモジュラー境界を開発し、多面体組合せ系との特定の接続を記述する。
これらのモジュラー境界を用いたアルゴリズムは、レバレッジスコアのような確立された統計的概念と、ボリュームサンプリングのようなより最近の取り組みとどのように関係しているかを論じる。
合成問題に関する理論的知見と実世界の気候モニタリングの例を示す。
関連論文リスト
- Randomized Greedy Learning for Non-monotone Stochastic Submodular
Maximization Under Full-bandit Feedback [98.29086113546045]
本稿では,非拘束型マルチアームバンディットのフルバンドフィードバックとサブモジュール性に対する報奨問題について検討する。
RGLは、サブモジュールおよび非サブモジュール設定において、他のフルバンド変種よりも経験的に優れていることを示す。
論文 参考訳(メタデータ) (2023-02-02T18:52:14Z) - When to Update Your Model: Constrained Model-based Reinforcement
Learning [50.74369835934703]
モデルベースRL(MBRL)の非遅延性能保証のための新規で一般的な理論スキームを提案する。
続いて導いた境界は、モデルシフトとパフォーマンス改善の関係を明らかにします。
さらなる例では、動的に変化する探索からの学習モデルが、最終的なリターンの恩恵をもたらすことが示されている。
論文 参考訳(メタデータ) (2022-10-15T17:57:43Z) - Interactive Combinatorial Bandits: Balancing Competitivity and
Complementarity [20.31674763393817]
オンライン対話型バンディット設定における非モジュール機能について検討する。
純粋に劣モジュラーなアプローチを2つの方法で拡張する。
我々は、MovieLensデータセットと、分類のためのトレーニングサブセットの選択を数値的に研究する。
論文 参考訳(メタデータ) (2022-07-07T05:10:15Z) - Supermodular $\mf$-divergences and bounds on lossy compression and
generalization error with mutual $\mf$-information [17.441807469515254]
超モジュラーな$mf$-divergencesを導入し、3つのアプリケーションを提供します。
本稿では,有界入力/出力相互$mf$-informationと一般化レート歪み問題との相関関係について述べる。
我々の境界は、以前最もよく知られていた境界よりも厳密に改善されるレート歪曲関数上の新しい下限に基づいている。
論文 参考訳(メタデータ) (2022-06-21T09:17:06Z) - Scalable Distributed Algorithms for Size-Constrained Submodular
Maximization in the MapReduce and Adaptive Complexity Models [19.626627053947423]
MapReduceモデルのサブモジュール関数は、多くの注目を集めています。
単調および部分モジュラー関数のサイズ制約に対して、いくつかの部分制約適応アルゴリズムが整合性を満たすことを示す。
また,この問題に対して,定数MRラウンドを用いた最初の線形分散アルゴリズムを開発した。
論文 参考訳(メタデータ) (2022-06-20T04:17:32Z) - Fast Feature Selection with Fairness Constraints [49.142308856826396]
モデル構築における最適特徴の選択に関する基礎的問題について検討する。
この問題は、greedyアルゴリズムの変種を使用しても、大規模なデータセットで計算的に困難である。
適応クエリモデルは,最近提案された非モジュラー関数に対する直交整合探索のより高速なパラダイムに拡張する。
提案アルゴリズムは、適応型クエリモデルにおいて指数関数的に高速な並列実行を実現する。
論文 参考訳(メタデータ) (2022-02-28T12:26:47Z) - Harnessing Heterogeneity: Learning from Decomposed Feedback in Bayesian
Modeling [68.69431580852535]
サブグループフィードバックを取り入れた新しいGPレグレッションを導入する。
我々の修正された回帰は、以前のアプローチと比べて、明らかにばらつきを減らし、したがってより正確な後続を減らした。
我々は2つの異なる社会問題に対してアルゴリズムを実行する。
論文 参考訳(メタデータ) (2021-07-07T03:57:22Z) - Continuous Submodular Function Maximization [91.17492610120324]
連続部分モジュラリティ (continuous submodularity) は、幅広い応用を持つ関数のクラスである。
連続的な部分モジュラ最適化の応用は、影響、推論のMAP、フィールドへの推論など多岐にわたる。
論文 参考訳(メタデータ) (2020-06-24T04:37:31Z) - Streaming Submodular Maximization under a $k$-Set System Constraint [42.31117997337689]
非単調な部分モジュラーのストリーミングを非単調な部分モジュラーのストリーミングに変換する新しいフレームワークを提案する。
また,$k$ible $k$-setシステム制約を考慮したモノトンサブモジュールストリーミングのアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-02-09T12:32:14Z) - Adaptive Correlated Monte Carlo for Contextual Categorical Sequence
Generation [77.7420231319632]
我々は,モンテカルロ (MC) ロールアウトの集合を分散制御のために評価する政策勾配推定器に,カテゴリー列の文脈的生成を適用する。
また,二分木ソフトマックスモデルに相関したMCロールアウトを用いることで,大語彙シナリオにおける高生成コストを低減できることを示す。
論文 参考訳(メタデータ) (2019-12-31T03:01:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。