論文の概要: Submodularity and pairwise independence
- arxiv url: http://arxiv.org/abs/2209.08563v1
- Date: Sun, 18 Sep 2022 13:11:44 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-26 04:40:49.687305
- Title: Submodularity and pairwise independence
- Title（参考訳）: 部分モジュラリティとペア独立
- Authors: Arjun Ramachandra and Karthik Natarajan
- Abstract要約: ランダム入力間の任意の依存度を持つ関数の最大期待値の比率について検討する。
この結果は、独立性の弱い部分モジュラ函数の挙動の根本的な違いを示している。
- 参考スコア（独自算出の注目度）: 2.3231802473649554
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we provide a characterization of the expected value of
submodular set functions with pairwise independent random input. The set of
pairwise independent (uncorrelated) probability distributions contains the
mutually independent distribution and is contained within the set of
arbitrarily dependent (correlated) distributions. We study the ratio of the
maximum expected value of a function with arbitrary dependence among the random
input with given marginal probabilities to the maximum expected value of the
function with pairwise independent random input with the same marginal
probabilities. The definition of the ratio is inspired from the correlation gap
ratio of Agrawal et al. (2012) and Calinescu et al. (2007). Our results show
that for any monotone submodular set function defined on n variables, the ratio
is bounded from above by 4/3 in the following cases: (a) for small n
(specifically n = 2, 3) with general marginal probabilities, and (b) for
general n with small marginal probabilities. The bound is tight in cases (a)
and (b). This contrasts with the e/(e-1) bound on the correlation gap ratio for
monotone submodular set functions with mutually independent random input which
is known to be tight in case (b). Our results illustrate a fundamental
difference in the behavior of submodular functions with weaker notions of
independence. We discuss an application in distributionally robust optimization
and end the paper with a conjecture.
- Abstract（参考訳）: 本稿では、ペア独立なランダム入力を持つ部分モジュラー集合関数の期待値の特性について述べる。
ペア独立な(非関連な)確率分布の集合は互いに独立な分布を含み、任意の依存(関連のある)分布の集合に含まれる。
与えられた辺縁確率を持つ確率入力の任意の依存度を持つ関数の最大期待値と、同じ辺縁確率を持つペア独立なランダム入力を持つ関数の最大期待値との比について検討する。
この比の定義は、Agrawal et al. (2012) と Calinescu et al. (2007) の相関ギャップ比から着想を得ている。
我々の結果は、n 変数上で定義される任意の単調部分モジュラー集合関数に対して、この比は以下の場合において上から 4/3 で有界であることを示す。
(a)一般限界確率を持つ小さいn(特にn = 2, 3)について、及び
(b) 限界確率が小さい一般nについて。
場合、境界は厳密である
(a)及び
(b)
これは、互いに独立なランダム入力を持つ単調部分モジュラー集合関数の相関ギャップ比に束縛された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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。