論文の概要: 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)原理を用いた古典的グリードアルゴリズムの新たな解釈を提供する。
その類似性に基づいて、任意の可算モジュラー境界を利用する新しい手法のクラスを提案する。
線形ベイズ逆問題に対する最適実験設計の文脈において,基礎となる目的が相互情報に基づく場合,サブモジュラリティとスーパーモジュラリティ比を限定した。
また、この設定における相互情報のための新しいモジュラー境界を開発し、多面体組合せ系との特定の接続を記述する。
これらのモジュラー境界を用いたアルゴリズムは、レバレッジスコアのような確立された統計的概念と、ボリュームサンプリングのようなより最近の取り組みとどのように関係しているかを論じる。
合成問題に関する理論的知見と実世界の気候モニタリングの例を示す。
関連論文リスト
- Accelerated zero-order SGD under high-order smoothness and overparameterized regime [79.85163929026146]
凸最適化問題を解くための新しい勾配のないアルゴリズムを提案する。
このような問題は医学、物理学、機械学習で発生する。
両種類の雑音下で提案アルゴリズムの収束保証を行う。
論文 参考訳（メタデータ） (2024-11-21T10:26:17Z) - Optimal Multi-Distribution Learning [88.3008613028333]
マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。
本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-12-08T16:06:29Z) - Randomized Greedy Learning for Non-monotone Stochastic Submodular
Maximization Under Full-bandit Feedback [98.29086113546045]
本稿では,非拘束型マルチアームバンディットのフルバンドフィードバックとサブモジュール性に対する報奨問題について検討する。
RGLは、サブモジュールおよび非サブモジュール設定において、他のフルバンド変種よりも経験的に優れていることを示す。
論文 参考訳（メタデータ） (2023-02-02T18:52:14Z) - Online SuBmodular + SuPermodular (BP) Maximization with Bandit Feedback [23.665149409064814]
我々は純粋に部分モジュラーな前処理をより一般的な非部分モジュラー目的に拡張する。
これにより、オブジェクト間の競合(部分モジュラー)だけでなく、補完的(超モジュラー)な関係を表現することができる。
論文 参考訳（メタデータ） (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 [17.462968952951883]
MapReduce(MR)モデルのサブモジュラー関数は注目されている。
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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。