論文の概要: Partially Observed Sparse Graphs: The Unknown Sampling Rate is a Tail Index
- arxiv url: http://arxiv.org/abs/2609.26199v1
- Date: Fri, 14 Aug 2026 06:38:46 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-28 05:09:55.920008
- Title: Partially Observed Sparse Graphs: The Unknown Sampling Rate is a Tail Index
- Title（参考訳）: 部分観察されたスパースグラフ:未知サンプリングレートはタイル指数である
- Abstract要約: スパース交換可能な(グラフ)モデルの下では、期待される非孤立分率は$n_s/n_1to s1+$に従うので、テールインデックスが$のときサンプリングレートは推定可能となる。
尾部インデックス推定器では、削減は平常であることを示します -- 公表されたクローズドフォームで満たされ、13ドル以上のネットワークで21.7%、不適合なサンプリング予算で39ドルに達しています。
- 参考スコア（独自算出の注目度）: 31.082191748525137
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: A large graph is often available only in part: a crawl stopped by its budget, a panel, a partial dump. When the sampled fraction $s$ is known by design the total edge count follows from $\hat e=e_s/s^2$ and no model is needed. We treat the case where $s$ is unknown and the population size is known. Our main result is a reduction: under a sparse exchangeable (graphex) model the expected non-isolated fraction obeys $n_s/n_1\to s^{1+σ}$, so the sampling rate becomes estimable once the tail index $σ$ is, and substituting it back gives $e_s(n_1/n_s)^{2/(1+σ)}$ -- the same estimator, with the design quantity inferred. Estimating global edge cardinality in a sparse graph is therefore, in expectation, tail-index estimation, and the quadratic graphon estimator is the case $σ=0$: it fails by an identity rather than by a fit ($260\%$ median error against $27\%$). We bound the finite-size error of the substitution and show the reduction is \emph{modular} in the tail-index estimator --- filled with a published closed-form one it reaches $21.7\%$ over $13$ networks and $39$ sampling budgets with no fitting at all. Fitting a full graphex additionally returns the degree distribution at any size and a generative object, in a representation where sparsity is a coordinate and the interpolation path is dictated rather than chosen. Two limits are exact: rank-one graphexes have transitivity fixed by the degree profile, so high-clustering graphs lie outside the class; and under snowball or random-walk crawls every method here fails, the design-based oracle worst of all ($7.8\%$ to $588\%$).
- Abstract（参考訳）: 大きなグラフは、予算によって停止されたクロール、パネル、部分的なダンプなど、部分的にのみ利用可能であることが多い。
サンプリングされた分数$s$が設計によって知られているとき、総エッジカウントは$\hat e=e_s/s^2$から続き、モデルを必要としない。
s$が不明で集団サイズが不明な場合に対処する。
我々の主な結果は、疎交換可能な(グラフ)モデルの下では、予想される非孤立分画は$n_s/n_1\to s^{1+σ}$に従うので、サンプリングレートはテールインデックスが$σ$になったときに推定可能となり、それを置換すると$e_s(n_1/n_s)^{2/(1+σ)}$ -- 同じ推定値が推測される。
したがって、スパースグラフにおける大域的エッジ濃度の推定は、予想、尾インデクス推定においてであり、二次グラフオン推定器は、$σ=0$: 適合する(260\%$中央値エラー対27\%$)ではなくアイデンティティーによって失敗する。
置換の有限サイズの誤差を束縛し、還元がテールインデックス推定器で \emph{modular} であることを示します。
フルグラフのフィッティングは任意の大きさの次数分布と生成対象を、空間が座標であり補間経路が選択されるよりもむしろ宣言される表現として返す。
ランク1グラフは階数プロファイルによって推移性が固定されるので、高いクラスタリンググラフはクラス外に置かれる;そして雪玉やランダムウォークの全てのメソッドが失敗すると、デザインベースのオラクルは最悪のもの($7.8\%から$588\%)となる。
関連論文リスト
- Proving the Limited Scalability of Centralized Distributed Optimization via a New Lower Bound Construction [57.93371273485736]
我々は、すべての労働者が同一の分布にアクセスする均質な(すなわちd.d.)場合であっても、すべての労働者が非バイアス付き境界 LDeltaepsilon2,$$$$$ のポリ対数的により良いポリ対数を求める集中型分散学習環境を考える。
論文 参考訳（メタデータ） (2025-06-30T13:27:39Z) - Joint estimation of smooth graph signals from partial linear measurements [5.2395896768723045]
弱い一貫性は、個々の$G_t$sが非常に疎結合で非連結である場合でも、$G$の特定の選択に対して確立される。
結果は、$x_t$が$n$アイテムのコレクションの潜在強度に対応するマルチレイヤのランキング問題に拡張される。
論文 参考訳（メタデータ） (2025-05-29T08:41:45Z) - Entangled Mean Estimation in High-Dimensions [36.97113089188035]
信号のサブセットモデルにおける高次元エンタングルド平均推定の課題について検討する。
最適誤差(polylogarithmic factor)は$f(alpha,N) + sqrtD/(alpha N)$であり、$f(alpha,N)$は1次元問題の誤差であり、第二項は準ガウス誤差率である。
論文 参考訳（メタデータ） (2025-01-09T18:31:35Z) - Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。
本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-11-01T17:59:53Z) - Minimax Optimality of Score-based Diffusion Models: Beyond the Density Lower Bound Assumptions [11.222970035173372]
カーネルベースのスコア推定器は$widetildeOleft(n-1 t-fracd+22(tfracd2 vee 1)rightの最適平均二乗誤差を達成する
核を用いたスコア推定器は,拡散モデルで生成した試料の分布の総変動誤差に対して,極小ガウスの下での最大平均2乗誤差を$widetildeOleft(n-1/2 t-fracd4right)$上界で達成することを示す。
論文 参考訳（メタデータ） (2024-02-23T20:51:31Z) - Semidefinite programming relaxations and debiasing for MAXCUT-based clustering [1.9761774213809036]
2つのガウス分布を$mathbbRp$で混合して引き出す小さなデータサンプルを$n$で分割する問題を考察する。
グラフ上の最大カットを求めるように定式化された整数二次プログラムの半定値プログラミング緩和を用いる。
論文 参考訳（メタデータ） (2024-01-16T03:14:24Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - Causal Bandits for Linear Structural Equation Models [58.2875460517691]
本稿では,因果図形モデルにおける最適な介入順序を設計する問題について検討する。
グラフの構造は知られており、ノードは$N$である。
頻繁性(UCBベース)とベイズ的設定に2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-08-26T16:21:31Z) - Sparse sketches with small inversion bias [79.77110958547695]
逆バイアスは、逆の共分散に依存する量の推定を平均化するときに生じる。
本研究では、確率行列に対する$(epsilon,delta)$-unbiased estimatorという概念に基づいて、逆バイアスを解析するためのフレームワークを開発する。
スケッチ行列 $S$ が密度が高く、すなわちサブガウスのエントリを持つとき、$(epsilon,delta)$-unbiased for $(Atop A)-1$ は $m=O(d+sqrt d/ のスケッチを持つ。
論文 参考訳（メタデータ） (2020-11-21T01:33:15Z) - Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
論文 参考訳（メタデータ） (2020-05-29T07:20:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。