論文の概要: Statistical and computational challenges in ranking

• arxiv url: http://arxiv.org/abs/2512.21111v1
• Date: Wed, 24 Dec 2025 11:18:06 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-12-25 19:43:21.765527
• Title: Statistical and computational challenges in ranking
• Title（参考訳）: ランク付けにおける統計的および計算的課題
• Authors: Alexandra Carpentier, Nicolas Verzelen,
• Abstract要約: 質問に対する回答の正しさに基づいて,専門家の能力に応じて$n$をランク付けする問題を考察する。 ここでは,この問題に対する統計的に最適かつ計算学的に効率的な手順の存在について検討する。
• 参考スコア（独自算出の注目度）: 53.03724383992195
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the problem of ranking $n$ experts according to their abilities, based on the correctness of their answers to $d$ questions. This is modeled by the so-called crowd-sourcing model, where the answer of expert $i$ on question $k$ is modeled by a random entry, parametrized by $M_{i,k}$ which is increasing linearly with the expected quality of the answer. To enable the unambiguous ranking of the experts by ability, several assumptions on $M$ are available in the literature. We consider here the general isotonic crowd-sourcing model, where $M$ is assumed to be isotonic up to an unknown permutation $π^*$ of the experts - namely, $M_{π^{*-1}(i),k} \geq M_{π^{*-1}(i+1),k}$ for any $i\in [n-1], k \in [d]$. Then, ranking experts amounts to constructing an estimator of $π^*$. In particular, we investigate here the existence of statistically optimal and computationally efficient procedures and we describe recent results that disprove the existence of computational-statistical gaps for this problem. To provide insights on the key ideas, we start by discussing simpler and yet related sub-problems, namely sub-matrix detection and estimation. This corresponds to specific instances of the ranking problem where the matrix $M$ is constrained to be of the form $λ\mathbf 1\{S\times T\}$ where $S\subset [n], T\subset [d]$. This model has been extensively studied. We provide an overview of the results and proof techniques for this problem with a particular emphasis on the computational lower bounds based on low-degree polynomial methods. Then, we build upon this instrumental sub-problem to discuss existing results and algorithmic ideas for the general ranking problem.
• Abstract（参考訳）: 質問に対する回答の正しさに基づいて,専門家の能力に応じて$n$をランク付けする問題を考察する。 これは、いわゆるクラウドソーシングモデルによってモデル化され、専門家の$i$ on question$k$の答えはランダムなエントリによってモデル化され、M_{i,k}$でパラメータ化され、答えの期待品質と線形に増加する。 専門家の能力による明確なランク付けを可能にするために、文献でM$に対するいくつかの仮定が利用可能である。 ここで、一般等方的クラウドソーシングモデルを考えると、$M$は未知の置換(英語版)$π^*$、すなわち$M_{π^{*-1}(i),k} \geq M_{π^{*-1}(i+1),k}$、任意の$i\in [n-1], k \in [d]$に対して等方的であると仮定される。 すると、ランキングの専門家は$π^*$の推定器を構築する。 特に, 統計学的に最適かつ計算学的に効率的な手順の存在について検討し, この問題に対する計算統計的ギャップの存在を否定する最近の結果について述べる。 キーとなるアイデアに関する洞察を提供するために、我々は、よりシンプルで、関連するサブプロブレム、すなわちサブマトリックスの検出と推定について議論することから始める。 これは行列 $M$ が $λ\mathbf 1\{S\times T\}$, $S\subset [n], T\subset [d]$ の形に制約されるランク問題の特定の例に対応する。 このモデルは広く研究されている。 本稿では,低次多項式法に基づく計算下界に特に重点を置いて,この問題に対する結果と証明手法の概要について述べる。 そこで,本稿では,一般的なランキング問題に対する既存の結果とアルゴリズム的アイデアについて議論するために,このインストゥルメンタルサブプロブレムを構築した。

関連論文リスト

• Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
  このタスクに対する効率的な統計的クエリアルゴリズムは、VSTATの複雑さを少なくとも$tildeOmega(d1/2/alpha2)$で要求する。
  論文  参考訳（メタデータ） (2025-10-12T15:42:44Z)
• A computational transition for detecting multivariate shuffled linear regression by low-degree polynomials [0.0]
  モデル $Y=tfrac1sqrt1+sigma2(Pi_* X Q_* + sigma Z) について検討する。 このモデルを$X$と$Y$の場合と区別する仮説テスト問題を考える。 その結果、この問題に対する低次アルゴリズムの有効性の円滑な遷移が確立された。
  論文  参考訳（メタデータ） (2025-04-04T00:32:38Z)
• Optimal level set estimation for non-parametric tournament and crowdsourcing problems [49.75262185577198]
  クラウドソーシングによって動機づけられた我々は、$d$の質問に対する$n$の専門家の回答の正しさを部分的に観察する問題を考える。 本稿では、専門家$i$が疑問に答える確率を含む行列$M$が、行と列の置換までの双等方性であることを仮定する。 我々は,この分類問題に対して最小限のアルゴリズムを最適に構築する。
  論文  参考訳（メタデータ） (2024-08-27T18:28:31Z)
• A Spectral Approach to Item Response Theory [6.5268245109828005]
  本稿では,Raschモデルに対する新しい項目推定アルゴリズムを提案する。 我々のアルゴリズムの中核は、アイテム-イムグラフ上で定義されたマルコフ連鎖の定常分布の計算である。 合成および実生活データセットの実験により、我々のアルゴリズムは、文献でよく使われている手法とスケーラブルで正確で競合することを示した。
  論文  参考訳（メタデータ） (2022-10-09T18:57:08Z)
• Spectral properties of sample covariance matrices arising from random matrices with independent non identically distributed columns [50.053491972003656]
  関数 $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$. ここでは、$|mathbb E[R(z)] - tilde R(z)|_F を示す。
  論文  参考訳（メタデータ） (2021-09-06T14:21:43Z)
• 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)
• Sample Efficient Reinforcement Learning via Low-Rank Matrix Estimation [30.137884459159107]
  連続状態と行動空間を用いた強化学習において,Q$関数を効率よく学習する方法を考える。 我々は、$epsilon$-Schmidt $Q$-functionと$widetildeO(frac1epsilonmax(d1, d_2)+2)$のサンプル複雑性を求める単純な反復学習アルゴリズムを開発する。
  論文  参考訳（メタデータ） (2020-06-11T00:55:35Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)

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

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