論文の概要: Two-Sample Testing for Inhomogeneous Random Graphs in Non-Integral $L_r$ Norms

• arxiv url: http://arxiv.org/abs/2609.33968v1
• Date: Sun, 27 Sep 2026 22:12:15 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-04 08:18:53.297284
• Title: Two-Sample Testing for Inhomogeneous Random Graphs in Non-Integral $L_r$ Norms
• Title（参考訳）: 非整数$L_r$ノルムにおける不均質ランダムグラフの2サンプル検定
• Abstract要約: 2つのネットワークが同じエッジ確率を共有するかどうかをテストすることは、推論ネットワークにおける基本的な問題である。 非積分$r>2$の場合、既知の上界と下界は一致せず、下界は厳密であると推測された。 我々は、同じデータ上で、2ドルの注文と$lceil rrceil$の2つの統計データを発行し、どちらかが拒否した場合に拒否するテストを提案する。 このテストが予想される速度に達することを証明します。
• 参考スコア（独自算出の注目度）: 13.142220109832197
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Testing whether two populations of networks share the same edge probabilities is a basic problem in network inference. How hard it is depends on the norm used to measure the difference. For the inhomogeneous Erdős--Rényi (IER) model, the optimal sample complexity is known for every integer $L_r$ norm and for $1\le r<2$. For non-integral $r>2$, however, the known upper and lower bounds do not match, and the lower bound was conjectured to be tight. We study this gap for two-sample testing on aligned vertices. We propose a test that runs two published statistics, of orders $2$ and $\lceil r\rceil$, on the same data and rejects if either one rejects. Its thresholds come from Hölder interpolation, so that both statistics have the same sample cost. We prove that this test attains the conjectured rate. Combined with earlier results, this shows that for every fixed $r\ge1$ the minimax sample complexity is of order $n^{\max\{4/r-1,\,2/r\}}/ε^2$, even when the separation changes with $n$. In simulations with $n$ between 32 and 256, the number of graphs needed for 80\% power at level $0.05$ grows with $n$ at a rate consistent with the theory. For $r=2.5$, for example, the fitted exponent is $0.78$, against the theoretical value $0.8$. Interestingly, the two statistics split the work as the interpolation argument suggests: the higher-order statistic is more powerful when only a few edges change, and the $L_2$ statistic when many edges change.
• Abstract（参考訳）: 2つのネットワークの集団が同じエッジ確率を共有するかどうかをテストすることは、ネットワーク推論における基本的な問題である。 どれだけ難しいかは、その差を測定するのに使われる基準に依存します。 非同質なエルデシュ-レーニ(英語版)(IER)モデルでは、最適なサンプル複雑性はすべての整数$L_r$ノルムと1\le r<2$に対して知られている。 しかし、非積分$r>2$の場合、既知の上界と下界は一致せず、下界は厳密であると推測された。 本研究は, 両サンプル試験において, 整列頂点上でのギャップについて検討する。 我々は、同じデータ上で、2ドルの注文と$\lceil r\rceil$の2つの統計データを実行するテストを提案し、どちらかが拒否した場合は拒否する。 そのしきい値はヘルダー補間によるもので、両方の統計値が同じサンプルコストを持つ。 このテストが予想される速度に達することを証明します。 以前の結果と組み合わせると、すべての固定された$r\ge1$に対して、ミニマックスサンプルの複雑さは$n$に変化しても$n^{\max\{4/r-1,\,2/r\}}/ε^2$である。 32から256の間の$n$のシミュレーションでは、レベル0.05$の80\%のパワーに必要なグラフの数は、理論と一致する速度で$n$で増加する。 例えば$r=2.5$の場合、適合指数は$0.78$であり、理論値$0.8$である。 興味深いことに、この2つの統計学は補間論の主張によって研究を分割した: 数個のエッジだけを変えると高次統計学がより強力になり、多くのエッジが変化すると$L_2$統計学がより強力になる。

関連論文リスト

• Estimating the size of a set using cascading exclusion [2.1665689529884697]
  一般的な非漸近論が展開されている。 一般定理は、すべての場合において非パラメトリック有限$n$誤差境界を与える。
  論文  参考訳（メタデータ） (2025-08-07T23:36:42Z)
• The Sample Complexity of Simple Binary Hypothesis Testing [7.127829790714167]
  単純な二項仮説テストのサンプルの複雑さは、いずれの設定でも$p$と$q$の2つの分布を区別するのに必要となる最小のi.d.サンプルである。 i) all $0 le alpha, beta le 1/8$ in the pre-free set, and (ii) all $delta le pi/4$ in the Bayesian set。
  論文  参考訳（メタデータ） (2024-03-25T17:42:32Z)
• Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond [89.72693227960274]
  本稿では,グループ分散ロバスト最適化 (GDRO) を,$m$以上の異なる分布をうまく処理するモデルを学習する目的で検討する。 各ラウンドのサンプル数を$m$から1に抑えるため、GDROを2人でプレイするゲームとして、一方のプレイヤーが実行し、他方のプレイヤーが非公開のマルチアームバンディットのオンラインアルゴリズムを実行する。 第2のシナリオでは、最大リスクではなく、平均的最上位k$リスクを最適化し、分散の影響を軽減することを提案する。
  論文  参考訳（メタデータ） (2023-02-18T09:24:15Z)
• Sharp Constants in Uniformity Testing via the Huber Statistic [16.384142529375435]
  一様性テスト(英: Uniformity testing)は、プロパティテストにおいて最もよく研究されている問題の1つである。 1-デルタ確率を持つ任意の$epsilon$-far分布と$m$要素上の均一分布を区別する最適なサンプル複雑性は$nであることが知られている。 衝突試験機は, 均一入力と非一様入力の分離の標準偏差数において, 急激な最大定数を達成することを示す。
  論文  参考訳（メタデータ） (2022-06-21T20:43:53Z)
• The Sample Complexity of Robust Covariance Testing [56.98280399449707]
  i. i. d. 形式 $Z = (1-epsilon) X + epsilon B$ の分布からのサンプル。ここで $X$ はゼロ平均で未知の共分散である Gaussian $mathcalN(0, Sigma)$ である。 汚染がない場合、事前の研究は、$O(d)$サンプルを使用するこの仮説テストタスクの単純なテスターを与えた。 サンプル複雑性の上限が $omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma であることを証明します。
  論文  参考訳（メタデータ） (2020-12-31T18:24:41Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。 我々はCIFARに関する実験結果を示し,その理論を検証した。
  論文  参考訳（メタデータ） (2020-02-08T22:02:14Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。