論文の概要: Graph-monotone entrywise guarantees for MLE and Rank Centrality on general comparison graphs
- arxiv url: http://arxiv.org/abs/2610.09030v1
- Date: Tue, 06 Oct 2026 19:30:51 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-08 21:58:22.57164
- Title: Graph-monotone entrywise guarantees for MLE and Rank Centrality on general comparison graphs
- Title（参考訳）: 一般比較グラフ上でのMLEとランク中心性に対するグラフ単調なエントリーワイド保証
- Abstract要約: 最小仮定のBradley-Terry-Luceモデルの下で任意の固定比較グラフについて検討する。
標準極大推定器とランク中央度の両方が1/sqrt_mathcalD$の進入誤差率を対数的および動的レンジ因子まで高い確率で達成できることを証明した。
- 参考スコア（独自算出の注目度）: 7.5686409814551245
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Pairwise comparisons are widely used to infer latent scores and identify top-ranked items. Although sharp statistical guarantees are available under uniform sampling, real data often induce irregular comparison graphs with heterogeneous observation counts across pairs. In this paper, we study an arbitrary fixed comparison graph under the Bradley--Terry--Luce model with minimal assumptions. We prove that both the standard maximum likelihood estimator and Rank Centrality achieve a high-probability entrywise error rate of order $1/\sqrt{λ_{\mathcal{D}}}$ up to logarithmic and dynamic-range factors, where $λ_{\mathcal{D}}$ is the algebraic connectivity of the count-weighted observation graph. This guarantee is graph-monotone since $λ_{\mathcal{D}}$ cannot decrease when additional comparisons are added. Under heterogeneous sampling, where comparison pairs are sampled independently with unequal probabilities, our guarantee improves existing error bounds or requires weaker assumptions. We further extend our analysis to show that both estimators are robust against outcome-adaptive augmentation, where an adversary can choose additional comparison pairs after observing the initial outcomes.
- Abstract（参考訳）: ペアワイズ比較は、遅延スコアを推測し、トップランクのアイテムを特定するために広く使用される。
急激な統計的保証は、一様サンプリングの下で利用できるが、実データは、ペア間での不均一な観測数を持つ不規則な比較グラフを誘導することが多い。
本稿では,最小仮定のBradley-Terry-Luceモデルの下で,任意の固定比較グラフについて検討する。
標準極大推定器とランク中央度の両方が1/\sqrt{λ_{\mathcal{D}}}$を対数的および動的レンジ因子まで高確率なエントリーワイド誤差率を達成することを証明し、ここでは、λ_{\mathcal{D}}$を数重化観測グラフの代数的接続とする。
この保証はグラフ単調であり、$λ_{\mathcal{D}}$は追加比較を追加すると減少できない。
不均質なサンプリングでは、比較ペアが不均一な確率で独立してサンプリングされるが、保証は既存のエラー境界を改善するか、より弱い仮定を必要とする。
さらに解析を拡張し、両推定器が結果適応的拡張に対して堅牢であることを示し、敵が最初の結果を観察した後、追加の比較ペアを選択することができることを示した。
関連論文リスト
- Two-Sample Testing via Generative Processes [60.42943145582429]
生成輸送は、2つのサンプルが同じ分布から来るかどうかを決定する新しい方法を提供する。
2つのサンプルの間に直接補間体を構築し、対称スケジュールでは、その法則が時間反射の下で不変であることを観察する。
したがって、t と 1-t の辺辺が、Jensen-Shannon の発散を計算することで一致するかどうかをテストする。
論文 参考訳（メタデータ） (2026-10-06T12:48:27Z) - Bradley-Terry model under general comparison graphs [5.781735038283894]
我々は、一般決定論的比較設計の下で、最大極大推定器の一様整合性を確立する。
応用として、最小エッジ確率がエルドス・レニー接続閾値を超えると、独立エッジランダムグラフ設計に対して一様整合が得られる。
論文 参考訳（メタデータ） (2026-10-05T12:39:40Z) - Almost Asymptotically Optimal Active Clustering Through Pairwise Observations [59.20614082241528]
そこで本研究では, ノイズと能動的に収集された応答を用いて, M$アイテムを未知数の$K$個別グループにクラスタリングするための新しい分析フレームワークを提案する。
クラスタリングの精度に対する望ましい信頼性を達成するのに必要なクエリ数の基本的下位境界を確立する。
我々は、一般化された同値比統計の計算可能な変種を開発し、その下限に対する性能ギャップを正確に推定できることを実証的に示す。
論文 参考訳（メタデータ） (2026-02-05T14:16:47Z) - Minimax Rates for the Estimation of Eigenpairs of Weighted Laplace-Beltrami Operators on Manifolds [7.639886528552829]
楕円微分作用素の固有ペアを、多様体$M$で支えられる分布$rho$のサンプルから推定する問題について検討する。
グラフラプラシアンの固有ペアは、近似の誤差で正規性多様体推定器を誘導し、対数補正まで、我々の下界と一致する。
論文 参考訳（メタデータ） (2025-05-30T19:19:25Z) - Minimax Hypothesis Testing for the Bradley-Terry-Luce Model [6.5990719141691825]
ブラッドリー・テリー・ルーシ(Bradley-Terry-Luce、BTL)モデルは、アイテムやエージェントのコレクションをランク付けする最も広く使われているモデルの一つである。
与えられたペア比較データセットとエージェントペアあたりの$k$の比較が、基礎となるBTLモデルに由来するかどうかを判定する仮説テストを提案する。
論文 参考訳（メタデータ） (2024-10-10T20:28:05Z) - Ranking from Pairwise Comparisons in General Graphs and Graphs with
Locality [3.1219977244201056]
本稿では,古典的Bradley-Terry-Luceモデル(BTL)のペア比較によるランキング問題について検討する。
十分に多くのサンプルを用いて,Cram'er-Rao の下界と一致するエントリワイズ推定誤差が得られることを示す。
我々は、最も広いサンプルを持つ体制においても、同様の保証を確実に達成できる分割対コンカマーのアルゴリズムについて検討する。
論文 参考訳（メタデータ） (2023-04-13T21:14:30Z) - Statistical Efficiency of Score Matching: The View from Isoperimetry [96.65637602827942]
本研究では, スコアマッチングの統計的効率と推定される分布の等尺性との間に, 密接な関係を示す。
これらの結果はサンプル状態と有限状態の両方で定式化する。
論文 参考訳（メタデータ） (2022-10-03T06:09:01Z) - BCD Nets: Scalable Variational Approaches for Bayesian Causal Discovery [97.79015388276483]
構造方程式モデル(SEM)は、有向非巡回グラフ(DAG)を介して表される因果関係を推論する効果的な枠組みである。
近年の進歩により、観測データからDAGの有効最大点推定が可能となった。
線形ガウス SEM を特徴付ける DAG 上の分布を推定するための変分フレームワークである BCD Nets を提案する。
論文 参考訳（メタデータ） (2021-12-06T03:35:21Z) - The Performance of the MLE in the Bradley-Terry-Luce Model in
$\ell_{\infty}$-Loss and under General Graph Topologies [76.61051540383494]
我々はBradley-Terry-Luceモデルの$ell_infty$推定誤差に関する新しい一般上限を導出する。
導出された境界は良好に機能し、場合によっては既知の結果よりもシャープであることを示す。
論文 参考訳（メタデータ） (2021-10-20T23:46:35Z) - Prototypical Graph Contrastive Learning [141.30842113683775]
本稿では,有意なサンプリングバイアスを緩和するために,プロトタイプグラフコントラスト学習(PGCL)手法を提案する。
具体的には、PGCLは、グラフデータの基盤となる意味構造を、意味論的に類似したグラフを同じグループにクラスタリングすることでモデル化し、同時に、同じグラフの異なる拡張に対するクラスタリング一貫性を奨励する。
クエリのために、PGCLはさらに、プロトタイプ(クラスタセントロイド)とクエリプロトタイプの間の距離に基づいて、負のサンプルを再重み付けする。
論文 参考訳（メタデータ） (2021-06-17T16:45:31Z) - Fairness constraints can help exact inference in structured prediction [37.76221231305701]
直交連結グラフ$G$と2進ラベルの真のベクトルを持つ生成モデルについて検討する。
フェアネスとモデル性能の間の既知のトレードオフとは対照的に、フェアネス制約の追加は正確なリカバリの確率を向上させる。
論文 参考訳（メタデータ） (2020-07-01T04:11:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。