論文の概要: Entrywise Error Bounds for Spectral Ranking with Semi-Random Adversaries

• arxiv url: http://arxiv.org/abs/2605.23854v1
• Date: Fri, 22 May 2026 17:08:07 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-25 17:29:20.438936
• Title: Entrywise Error Bounds for Spectral Ranking with Semi-Random Adversaries
• Title（参考訳）: 半ランダム共振器を用いたスペクトルランク付けにおける入射誤差境界
• Authors: Dongmin Lee, Anuran Makur, Japneet Singh,
• Abstract要約: 本稿では,半ランダム逆問題に対するスペクトルアルゴリズムのエントリーワイド誤差について検討する。 本研究では,一様にサンプリングされたグラフに近づく性能を,観測されたエッジを適切に重み付けすることで回復できることを示す。
• 参考スコア（独自算出の注目度）: 11.014454221295795
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Bradley-Terry-Luce (BTL) model estimation is a well-established strategy to rank a collection of items given a dataset of pairwise comparisons. Although the theoretical performance of BTL estimation methods, such as spectral and maximum likelihood estimation, is well studied in the regime of uniformly sampled graphs, generalizing such results to a wider class of random graphs has proved challenging. In this work, we investigate the entry-wise error of spectral algorithms against a semi-random adversary that can arbitrarily boost the sampling probabilities of certain edges. We find that the performance of the unweighted spectral method is heavily dependent on the spectral properties of the generated graph. Furthermore, we show that asymptotic performance approaching that of uniformly sampled graphs can be recovered by appropriately reweighting the observed edges to counteract the adversary and restore the spectral gap. Finally, we provide numerical simulations that support our theoretical findings.
• Abstract（参考訳）: Bradley-Terry-Luceモデル推定(BTL)は、ペア比較のデータセットが与えられた項目の集合をランク付けするための、確立された戦略である。 スペクトル推定や最大推定のようなBTL推定法の理論的性能は、一様サンプリンググラフの体系においてよく研究されているが、そのような結果をより広いランダムグラフのクラスに一般化することは困難である。 本研究では,特定のエッジのサンプリング確率を任意に向上できる半ランダム逆数に対するスペクトルアルゴリズムのエントリーワイド誤差について検討する。 非重み付きスペクトル法の性能は、生成したグラフのスペクトル特性に大きく依存していることが分かる。 さらに,一様にサンプリングされたグラフに近づいた漸近的性能は,観測されたエッジを適切に重み付けして敵の反応を防止し,スペクトルギャップを回復することで回復可能であることを示す。 最後に,理論的な知見を裏付ける数値シミュレーションを提案する。

関連論文リスト

• SIGMA: Scalable Spectral Insights for LLM Collapse [51.863164847253366]
  SIGMA(Spectral Inequalities for Gram Matrix Analysis)は,モデル崩壊のための統一的なフレームワークである。 行列のスペクトル上の決定論的境界を導出するベンチマークを利用することで、SIGMAは表現空間の収縮を追跡するために数学的に基底化された計量を提供する。 我々は、SIGMAが状態への遷移を効果的に捉え、崩壊のメカニズムに関する理論的知見の両方を提供することを示した。
  論文  参考訳（メタデータ） (2026-01-06T19:47:11Z)
• Spectral Ranking Inferences based on General Multiway Comparisons [7.222667862159246]
  本研究では,2段階のスペクトル法により,最大近似エスタと同じバニラ効率が得られることを示す。 有効な2サンプルランク試験法が提案されたのはこれが初めてである。
  論文  参考訳（メタデータ） (2023-08-05T16:31:32Z)
• Spectral Feature Augmentation for Graph Contrastive Learning and Beyond [64.78221638149276]
  グラフ(および画像)におけるコントラスト学習のための新しいスペクトル特徴論法を提案する。 各データビューに対して,特徴写像毎の低ランク近似を推定し,その近似を地図から抽出して補数を求める。 これは、2つの価値ある副産物(単に1つまたは2つのイテレーション)を楽しむ非標準パワーレジームである、ここで提案された不完全パワーイテレーションによって達成される。 グラフ/画像データセットの実験では、スペクトルフィーチャの増大がベースラインを上回ります。
  論文  参考訳（メタデータ） (2022-12-02T08:48:11Z)
• Spectral Decomposition Representation for Reinforcement Learning [100.0424588013549]
  本稿では, スペクトル分解表現法(SPEDER)を提案する。この手法は, データ収集ポリシーに急激な依存を生じさせることなく, ダイナミックスから状態-作用の抽象化を抽出する。 理論的解析により、オンライン設定とオフライン設定の両方において提案アルゴリズムのサンプル効率が確立される。 実験により、いくつかのベンチマークで現在の最先端アルゴリズムよりも優れた性能を示す。
  論文  参考訳（メタデータ） (2022-08-19T19:01:30Z)
• Spectral learning of multivariate extremes [0.0]
  多変量極度の依存構造を解析するためのスペクトルクラスタリングアルゴリズムを提案する。 本研究は,極端サンプルから構築したランダムな$k-アネレスト近傍グラフに基づくスペクトルクラスタリングの理論的性能について検討した。 角測度を学習するための簡易な一貫した推定手法を提案する。
  論文  参考訳（メタデータ） (2021-11-15T14:33:06Z)
• Heavy-tailed Streaming Statistical Estimation [58.70341336199497]
  ストリーミング$p$のサンプルから重み付き統計推定の課題を考察する。 そこで我々は,傾きの雑音に対して,よりニュアンスな条件下での傾きの傾きの低下を設計し,より詳細な解析を行う。
  論文  参考訳（メタデータ） (2021-08-25T21:30:27Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  本稿では,ランダムウォークラプラシアンを用いたグラフスペクトル埋め込みが,ノード次数に対して完全に補正されたベクトル表現を生成することを示す。 次数補正ブロックモデルの特別な場合、埋め込みはK個の異なる点に集中し、コミュニティを表す。
  論文  参考訳（メタデータ） (2021-05-03T16:36:27Z)

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

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