論文の概要: Submodularity, pairwise independence and correlation gap
- arxiv url: http://arxiv.org/abs/2209.08563v2
- Date: Tue, 19 Dec 2023 02:12:44 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-21 03:24:34.963287
- Title: Submodularity, pairwise independence and correlation gap
- Title（参考訳）: 部分モジュラリティ、対独立および相関ギャップ
- Authors: Arjun Ramachandra and Karthik Natarajan
- Abstract要約: ランダム入力間の任意の依存度を持つ関数の最大期待値の比率について検討する。
a) 4/3$ for $n = 3$ with general marginal probabilities and any monotone submodular set function。
- 参考スコア（独自算出の注目度）: 2.357907589265434
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: In this paper, we provide a characterization of the expected value of
monotone submodular set functions with $n$ pairwise independent random inputs.
Inspired by the notion of ``correlation gap'', we study the ratio of the
maximum expected value of a function with arbitrary dependence among the random
inputs with given marginal probabilities to the maximum expected value of the
function with pairwise independent random inputs and the same marginal
probabilities. Our results show that the ratio is upper bounded by: (a) $4/3$
for $n = 3$ with general marginal probabilities and any monotone submodular set
function (b) $4/3$ for general $n$ with small and large marginal probabilities
and any monotone submodular set function and (c) $4k/(4k-1)$ for general $n$,
general identical probabilities and rank functions of $k$-uniform matroids. The
bound is tight in all three cases. This contrasts with the $e/(e-1)$ bound on
the correlation gap ratio for monotone submodular set functions with mutually
independent random inputs (which is known to be tight in case (b)), and
illustrates a fundamental difference in the behavior of submodular functions
with weaker notions of independence. These results can be immediately extended
beyond pairwise independence to correlated random inputs. We discuss
applications in distributionally robust optimization and mechanism design and
end the paper with a conjecture.
- Abstract（参考訳）: 本稿では,単調部分モジュラー集合関数の期待値が$n$のペア独立なランダム入力を持つ場合のキャラクタリゼーションについて述べる。
相関ギャップ'という概念に触発されて,与えられた限界確率を持つランダム入力間の任意の依存性を持つ関数の最大期待値と,ペアワイズ独立なランダム入力と同じ限界確率を持つ関数の最大期待値の比率について検討した。
以上の結果から,この比率は下記の通りである。
(a)4/3$ for $n = 3$ 一般限界確率と任意の単調部分モジュラー集合関数
(b)小・大辺縁確率と任意の単調部分モジュラー集合関数を持つ一般のn$に対して4/3$
(c)$k/(4k-1)$ 一般の$n$、一般の同一確率、および $k$-uniform matroids のランク関数。
境界は3つのケースすべてで厳密である。
これは、互いに独立なランダム入力を持つ単調部分モジュラー集合関数の相関ギャップ比の$e/(e-1)$バウンドと対比する。
(b)) で、より弱い独立性の概念を持つ部分モジュラー関数の挙動の基本的な違いを示す。
これらの結果は、ペアの独立性を超えて、相関ランダムな入力に即座に拡張できる。
本稿では,分散的ロバストな最適化と機構設計の応用について論じる。
関連論文リスト
- Rényi divergence-based uniformity guarantees for $k$-universal hash functions [59.90381090395222]
普遍ハッシュ関数は、ソースの出力を有限アルファベット上のランダム文字列にマッピングする。
ミンエントロピーによって測定されるように、ほぼ均一なランダムビットを蒸留することが可能であることを示す。
論文 参考訳（メタデータ） (2024-10-21T19:37:35Z) - Complexity-Theoretic Implications of Multicalibration [8.315801422499863]
多精度予測器はより強い条件を満たす:それらはコレクションの各セットで校正される。
この複雑性理論的正則性レンマは、異なる領域に影響を及ぼすことが知られている。
すべての函数(その硬さによらず)が不随伴なハードコア集合の小さな集合を持つことが示される。
論文 参考訳（メタデータ） (2023-12-28T18:53:21Z) - Randomized Greedy Learning for Non-monotone Stochastic Submodular
Maximization Under Full-bandit Feedback [98.29086113546045]
本稿では,非拘束型マルチアームバンディットのフルバンドフィードバックとサブモジュール性に対する報奨問題について検討する。
RGLは、サブモジュールおよび非サブモジュール設定において、他のフルバンド変種よりも経験的に優れていることを示す。
論文 参考訳（メタデータ） (2023-02-02T18:52:14Z) - A Nearly Tight Bound for Fitting an Ellipsoid to Gaussian Random Points [50.90125395570797]
このことは対数的因子の中でのciteSaundersonCPW12 の予想をほぼ成立させる。
後者の予想は、機械学習とある種の統計上の問題に対する2乗下界との結びつきから、過去10年間で大きな注目を集めている。
論文 参考訳（メタデータ） (2022-12-21T17:48:01Z) - Feature Cross Search via Submodular Optimization [58.15569071608769]
機能工学の基本的な基礎として機能横断探索について研究する。
この問題に対して単純なgreedy $(1-1/e)$-approximationアルゴリズムが存在することを示す。
論文 参考訳（メタデータ） (2021-07-05T16:58:31Z) - Submodular + Concave [53.208470310734825]
第一次最適化法が凹関数の最大目的値に収束できることはよく確立されている。
本研究では、滑らかな函数凸体(英語版)の行列式を$F(x) = G(x) +C(x)$で始める。
このクラスの函数は、保証がないような凹凸函数と連続DR-部分モジュラ函数の両方の拡張である。
論文 参考訳（メタデータ） (2021-06-09T01:59:55Z) - Joint quasiprobability distribution on the measurement outcomes of
MUB-driven operators [2.9005223064604078]
メソッドは、Mutually Unbiased Basesに関連する正規直交可換作用素の完全な集合に基づいている。
準確率分布が非負である状態の集合を幾何学的に特徴づける。
集合は$(n2-1)$-次元凸ポリトープで、純状態は$n+1$、高次元の面は$n+1$、辺は$n3(n+1)/2$である。
論文 参考訳（メタデータ） (2021-01-20T13:10:26Z) - Finding Global Minima via Kernel Approximations [90.42048080064849]
関数評価のみに基づく滑らかな関数のグローバル最小化を考える。
本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
論文 参考訳（メタデータ） (2020-12-22T12:59:30Z) - Optimal Bounds between $f$-Divergences and Integral Probability Metrics [8.401473551081748]
確率分布の類似性を定量化するために、$f$-divergencesとIntegral Probability Metricsが広く使われている。
両家系の関係を凸双対性の観点から体系的に研究する。
我々は、Hoeffdingの補題のような統一的な方法でよく知られた結果を回復しながら、新しい境界を得る。
論文 参考訳（メタデータ） (2020-06-10T17:39:11Z) - Regularized Submodular Maximization at Scale [45.914693923126826]
亜モジュラリティは本質的に多様性、カバレッジ、代表性の概念に関係している。
正規化部分モジュラ函数 $f = g ell$ を行列式部分モジュラ関数 $g$ とモジュラ関数 $ell$ の差分として最大化する手法を提案する。
論文 参考訳（メタデータ） (2020-02-10T02:37:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。