論文の概要: Partial Recovery for Top-$k$ Ranking: Optimality of MLE and
Sub-Optimality of Spectral Method
- arxiv url: http://arxiv.org/abs/2006.16485v2
- Date: Thu, 15 Jul 2021 06:47:53 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-15 06:14:32.278048
- Title: Partial Recovery for Top-$k$ Ranking: Optimality of MLE and
Sub-Optimality of Spectral Method
- Title（参考訳）: 最高ランク付けのための部分回復:MLEの最適性とスペクトル法の準最適性
- Authors: Pinhan Chen, Chao Gao, Anderson Y. Zhang
- Abstract要約: 上位ランクのミスの割合で部分回復誤差を特徴づける。
また、最上位のk$セットの正確な回復のために最適な信号対雑音比条件を導出する。
- 参考スコア（独自算出の注目度）: 20.81132428224778
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Given partially observed pairwise comparison data generated by the
Bradley-Terry-Luce (BTL) model, we study the problem of top-$k$ ranking. That
is, to optimally identify the set of top-$k$ players. We derive the minimax
rate with respect to a normalized Hamming loss. This provides the first result
in the literature that characterizes the partial recovery error in terms of the
proportion of mistakes for top-$k$ ranking. We also derive the optimal signal
to noise ratio condition for the exact recovery of the top-$k$ set. The maximum
likelihood estimator (MLE) is shown to achieve both optimal partial recovery
and optimal exact recovery. On the other hand, we show another popular
algorithm, the spectral method, is in general sub-optimal. Our results
complement the recent work by Chen et al. (2019) that shows both the MLE and
the spectral method achieve the optimal sample complexity for exact recovery.
It turns out the leading constants of the sample complexity are different for
the two algorithms. Another contribution that may be of independent interest is
the analysis of the MLE without any penalty or regularization for the BTL
model. This closes an important gap between theory and practice in the
literature of ranking.
- Abstract（参考訳）: Bradley-Terry-Luce(BTL)モデルによって生成されたペアワイズ比較データから,トップ$kのランク付けの問題を検討した。
つまり、最上位の$k$プレーヤーのセットを最適に識別する。
我々は正規化ハミング損失に関してミニマックスレートを導出する。
これは、トップ$k$ランキングの誤りの割合で部分回復エラーを特徴付ける文献の最初の結果を提供する。
また、最上位のk$セットの正確な回復のために最適な信号対雑音比条件を導出する。
最大極大推定器 (MLE) は最適部分回復と最適精度回復の両立を図っている。
一方、スペクトル法という別の一般的なアルゴリズムは、一般に準最適であることを示す。
この結果は,MLE法とスペクトル法の両方が正確な回収のために最適な試料複雑性を実現することを示すChenらによる最近の研究を補完するものである。
この2つのアルゴリズムでは、サンプル複雑性の主定数が異なることが判明した。
独立した関心を持つ別の貢献は、BTLモデルに対するペナルティや規則化のないMLEの分析である。
これは、ランキング文学における理論と実践の間に重要なギャップを埋める。
関連論文リスト
- Top-$K$ ranking with a monotone adversary [19.871049853222132]
比較グラフがランダムに生成され、敵が任意のエッジを追加することができるシナリオを考える。
統計学者の目標は、ペア比較に基づいて、上位$K$の推奨項目を正確に識別することである。
本論文の主な貢献は, ほぼ最適サンプル複雑性を実現するための重み付き最大極大推定器(MLE)を開発することである。
論文 参考訳（メタデータ） (2024-02-12T06:57:34Z) - Faster Convergence with Multiway Preferences [99.68922143784306]
本稿では,符号関数に基づく比較フィードバックモデルについて考察し,バッチとマルチウェイの比較による収束率の解析を行う。
本研究は,マルチウェイ選好による凸最適化の問題を初めて研究し,最適収束率を解析するものである。
論文 参考訳（メタデータ） (2023-12-19T01:52:13Z) - Maximum Likelihood Estimation is All You Need for Well-Specified
Covariate Shift [34.414261291690856]
現代の機械学習システムの鍵となる課題は、アウト・オブ・ディストリビューション(OOD)の一般化を達成することである。
音源データを用いた古典的最大等化推定(MLE)が極小最適化を実現することを示す。
3つの具体例にインスタンス化することで、フレームワークの幅広い適用性を説明します。
論文 参考訳（メタデータ） (2023-11-27T16:06:48Z) - Improved theoretical guarantee for rank aggregation via spectral method [1.0152838128195467]
複数の項目間のペアワイズ比較を与えられた場合、ランキングが観測値と一致するようにランク付けする方法?
ランクアグリゲーションとして知られるこの問題は、スポーツ、レコメンデーションシステム、その他のウェブアプリケーションに多くの応用を見出している。
ここで、各ペア比較は真のスコア差の破損したコピーである。
論文 参考訳（メタデータ） (2023-09-07T16:01:47Z) - Optimal and Private Learning from Human Response Data [13.869502085838452]
最近、NguyenとZhangは、効率的かつ正確な新しいスペクトル推定アルゴリズムを提案した。
結果は2つの重要な方法で拡張します。
我々は、独自のマルコフ連鎖の定式化と離散ガウス機構を利用して、スペクトルアルゴリズムのプライベート拡張を開発する。
論文 参考訳（メタデータ） (2023-03-10T22:52:12Z) - Principled Reinforcement Learning with Human Feedback from Pairwise or
$K$-wise Comparisons [79.98542868281473]
RLHF(Reinforcement Learning with Human Feedback)の理論的枠組みを提供する。
学習した報酬モデルに基づいてポリシーをトレーニングする際、MLEは失敗し、悲観的なMLEは特定のカバレッジ仮定の下で性能を改善したポリシーを提供する。
論文 参考訳（メタデータ） (2023-01-26T18:07:21Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Mean-based Best Arm Identification in Stochastic Bandits under Reward
Contamination [80.53485617514707]
本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。
具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
論文 参考訳（メタデータ） (2021-11-14T21:49:58Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳（メタデータ） (2020-09-28T15:22:24Z) - Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal
Sample Complexity [67.02490430380415]
モデルに基づくMARLは、Nash平衡値(NE)を求めるために$tilde O(|S||B|(gamma)-3epsilon-2)$のサンプル複雑性を実現する。
また、アルゴリズムが報酬に依存しない場合、そのようなサンプル境界は最小値(対数因子まで)であり、アルゴリズムは報酬知識のない遷移サンプルを問合せする。
論文 参考訳（メタデータ） (2020-07-15T03:25:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。