論文の概要: Dimension Dependent Correlation Gap Bounds under Restricted Independence
- arxiv url: http://arxiv.org/abs/2609.02659v1
- Date: Wed, 02 Sep 2026 14:33:55 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-03 17:53:18.415886
- Title: Dimension Dependent Correlation Gap Bounds under Restricted Independence
- Title（参考訳）: 拘束独立下における次元依存性相関ギャップ境界
- Abstract要約: 最悪の場合、ペアの独立な相関ギャップが$e/(e-1)$allyに達することを示す。
対の独立は、$t$-wiseの独立階層の中で、最も制限的な独立形態であるにもかかわらず、最悪の場合において、相互独立と同様に制限的である。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The pairwise independent correlation gap is the ratio of the maximum expected value of a set function under arbitrary dependence to that under pairwise independence, measuring the loss from this independence restriction. Under mutual independence, this gap is universally bounded by $e/(e-1)$ for monotone submodular functions. With pairwise independence, a tighter $4/3$ upper bound was established for several special cases, including $n=3$, and conjectured to hold universally. A recent AI-assisted counterexample disproved this conjecture for $n=5$, leaving the validity of the $n=4$ bound and the tight worst case bound open. We resolve both questions. First, for $n=4$, we establish that the $4/3$ bound holds universally and is tight using an AI-assisted proof combining theoretical analysis and computational verification. The proof combines a structural characterization of optimal numerator vertices, permutation symmetry, cone certificate systems, Bernstein polynomial representations, recursive simplex subdivision, and verification of $2,745$ Bernstein coefficient systems. Second, we show that the worst case pairwise independent correlation gap attains $e/(e-1)$ asymptotically by constructing an instance with identical marginal probabilities and a monotone submodular union coverage function on a ground set partitioned into $m$ blocks. The number of blocks grows sublinearly with the ground set size. The result follows by constructing a feasible solution to a scaled asymptotic reduced dual of the pairwise independent linear program and immediately extends to $t$-wise independent random elements ($t\ge2$), since $t$-wise independence implies pairwise independence. Thus, pairwise independence, despite being the least restrictive form of independence in the $t$-wise independence hierarchy, can be as restrictive as mutual independence in the worst case.
- Abstract（参考訳）: 対独立相関ギャップ(英: pairwise independent correlation gap)とは、任意の依存の下で設定された関数の最大期待値の比率であり、この独立制限からの損失を測定する。
相互独立性の下では、このギャップは単調部分モジュラ函数に対して$e/(e-1)$で普遍的に有界である。
対独立により、$n=3$を含むいくつかの特別なケースに対してより厳密な4/3$の上界が確立され、普遍的に保持されると予想された。
最近のAI支援の反例では、この予想を$n=5$で反証し、$n=4$バウンドと厳密な最悪のケースバウンドの妥当性を残した。
どちらの問題も解決する。
まず、$n=4$の場合、理論解析と計算検証を組み合わせたAI支援の証明を用いて、4/3$のバウンドが普遍的に成り立つことを確かめる。
この証明は、最適数値頂点、置換対称性、円錐証明系、ベルンシュタイン多項式表現、再帰的単純な部分分割、および2,745ドルのベルンシュタイン係数系の検証という構造的特徴を組み合わせたものである。
第2に、同じ辺縁確率を持つインスタンスと、$m$ブロックに分割された基底集合上の単調な部分モジュラーユニオンカバレッジ関数を構築することで、最悪の場合、ペア独立な相関ギャップが、漸近的に$e/(e-1)$に達することを示す。
ブロックの数は、グラウンドセットサイズとサブリニアに増加する。
結果は、スケールされた漸近還元双対のペア独立線形プログラムに対して実現可能な解を構築し、すぐに$t$-wise独立ランダム要素(t\ge2$)に拡張する。
したがって、対の独立は、$t$-wiseの独立階層において最も制約の少ない独立形態であるにもかかわらず、最悪の場合において相互独立と同様に制限を受けることができる。
関連論文リスト
- Sample Complexity of Multicalibration for Multilevel Properties [52.27687531970317]
我々は、前のプロパティが固定されたときに各プロパティが識別可能な$k$プロパティの列に対する多重校正について検討する。
多対数的に多くの二元群が存在するにもかかわらず、多重校正誤差$varepsilon$を達成するには$widetilde(varepsilon-(k+2))$サンプルが必要である。
論文 参考訳（メタデータ） (2026-08-04T23:38:54Z) - Near-Optimal Dimension Lower Bounds for Single-Vector Embeddings of Maximum Inner Product Similarity [75.14269295861845]
シングルトンクエリでは、Chamferは最大内部積類似度(MAX-IP)になる。
すべての固定$in(0,1)$に対して、定数は$A_,c_>0$である。
単位球MAX-IPマトリクスは、DNFパターンマトリクスの正確な2値アフィンイメージであり、少なくとも8ドルのギャップがある。
論文 参考訳（メタデータ） (2026-07-22T17:27:20Z) - State-independent uncertainty relations on multipartite spin $1/2$-systems [0.0]
不確実性関係は、量子可観測物の同時測定に関する基本的な限界を定量化する。
我々は,集合スピン=tfrac12$システムにおける多部SIURの表現論的フレームワークを開発する。
これらの結果は、量子アンサンブルにおける多部分散に基づくSIURに対する最初の統一的代数的フレームワークを確立する。
論文 参考訳（メタデータ） (2026-07-15T21:28:02Z) - AI-Assisted Discovery of Convex Relaxations via Dual Agents [56.60366723277675]
すべての許容関数に対して下界が成り立ち、より強い境界を与える凸緩和から従うことを示す。
理論は各エージェントを検証し、反例を検索し、報告されたすべての境界はインターバルにおける明示的な二重実現可能な点によって認証される。
論文 参考訳（メタデータ） (2026-06-30T06:10:25Z) - All you need is log [0.42671348654734564]
次数 $in[0,infty]$ の Rényi の発散は、データ処理および独立製品への添加物の下でのユニークな族単調であることを示す。
多くの問題は一度に2つ以上の分布を比較する - マルチポピュレーションフェアネス、マルチプライオリPAC-Bayes境界、マルチヒポテシステスト。
レニイ族の右多分布一般化は開問題である。
論文 参考訳（メタデータ） (2026-06-25T17:54:49Z) - Odds Law: The Decomposition Algebra On How Intelligence Organizes Itself to Solve Difficult Problems Reliably [0.5414847001704247]
信頼性は、合成によって配置された独立した情報で購入され、検証者によって拘束されることを示す。
つまり、信頼性は自由でも魔法でもなく、独立した情報で購入され、構成によって配置され、検証者によって拘束される。
論文 参考訳（メタデータ） (2026-06-14T09:53:11Z) - Hardness of High-Dimensional Linear Classification [58.29089693778071]
我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。
どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
論文 参考訳（メタデータ） (2026-03-19T15:53:41Z) - Pairwise independent correlation gap [2.0979696058875446]
我々は、n$元上で定義される任意の非負の単調部分モジュラー集合関数に対して、この比は4/3$で上界となることを示す。
これは、相互独立を保ち、相互独立と相互独立の根本的な違いを示す「相関ギャップの境界」とは異なる。
論文 参考訳（メタデータ） (2022-09-18T13:11:44Z) - Scattering data and bound states of a squeezed double-layer structure [77.34726150561087]
2つの平行な均質層からなる構造は、その幅が$l_j$と$l_j$であり、それらの間の距離が$r$を同時に0に縮めるように、極限において研究される。
非自明な有界状態の存在は、ディラックのデルタ関数の微分の形で圧縮ポテンシャルの特別な例を含む、スクイーズ極限で証明される。
有限系の有限個の有界状態から、一個の有界状態が圧縮された系で生き残るシナリオを詳述する。
論文 参考訳（メタデータ） (2020-11-23T14:40:27Z) - Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。
理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。
我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
論文 参考訳（メタデータ） (2020-05-13T16:44:12Z) - Optimal rates for independence testing via $U$-statistic permutation
tests [7.090165638014331]
独立分布と同一分布のペアが$sigma$-finiteで分離可能な測度空間で値を取る独立性テストの問題について検討する。
最初に、独立性の有効なテストはなく、$f: D(f) geq rho2 $ という形の代替と一様に一致していることを示す。
論文 参考訳（メタデータ） (2020-01-15T19:04:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。