論文の概要: Top-$K$ ranking with a monotone adversary

• arxiv url: http://arxiv.org/abs/2402.07445v2
• Date: Thu, 20 Jun 2024 04:56:35 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-22 05:29:03.359325
• Title: Top-$K$ ranking with a monotone adversary
• Title（参考訳）: 単調な相手によるトップ$Kのランキング
• Authors: Yuepeng Yang, Antares Chen, Lorenzo Orecchia, Cong Ma,
• Abstract要約: 比較グラフがランダムに生成され、敵が任意のエッジを追加することができるシナリオを考える。 統計学者の目標は、ペア比較に基づいて、上位$K$の推奨項目を正確に識別することである。 本論文の主な貢献は, ほぼ最適サンプル複雑性を実現するための重み付き最大極大推定器(MLE)を開発することである。
• 参考スコア（独自算出の注目度）: 19.871049853222132
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we address the top-$K$ ranking problem with a monotone adversary. We consider the scenario where a comparison graph is randomly generated and the adversary is allowed to add arbitrary edges. The statistician's goal is then to accurately identify the top-$K$ preferred items based on pairwise comparisons derived from this semi-random comparison graph. The main contribution of this paper is to develop a weighted maximum likelihood estimator (MLE) that achieves near-optimal sample complexity, up to a $\log^2(n)$ factor, where $n$ denotes the number of items under comparison. This is made possible through a combination of analytical and algorithmic innovations. On the analytical front, we provide a refined~$\ell_\infty$ error analysis of the weighted MLE that is more explicit and tighter than existing analyses. It relates the~$\ell_\infty$ error with the spectral properties of the weighted comparison graph. Motivated by this, our algorithmic innovation involves the development of an SDP-based approach to reweight the semi-random graph and meet specified spectral properties. Additionally, we propose a first-order method based on the Matrix Multiplicative Weight Update (MMWU) framework. This method efficiently solves the resulting SDP in nearly-linear time relative to the size of the semi-random comparison graph.
• Abstract（参考訳）: 本稿では,単調な逆数による上位$Kのランキング問題に対処する。 比較グラフがランダムに生成され、敵が任意のエッジを追加することができるシナリオを考える。 統計学者の目標は、この半ランダム比較グラフから得られるペア比較に基づいて、上位$K$の推奨項目を正確に識別することである。 本論文の主な貢献は,最大値の最大値の最大値(MLE)を最大値$\log^2(n)$係数で表し,比較対象の項目数を表す重み付き最大値推定器(MLE)を開発することである。 これは分析的イノベーションとアルゴリズム的イノベーションの組み合わせによって実現される。 解析面では、既存の解析よりも明確で厳密な重み付きMLEの洗練された~$\ell_\infty$誤差解析を提供する。 これは、~$\ell_\infty$エラーと重み付き比較グラフのスペクトル特性を関連付ける。 アルゴリズムの革新は、半ランダムグラフを再重み付けし、特定のスペクトル特性を満たすSDPベースのアプローチの開発を伴う。 さらに,行列乗算重み更新(MMWU)フレームワークに基づく一階法を提案する。 この方法は半ランダム比較グラフのサイズに対してほぼ直線時間で結果のSDPを効率よく解く。

関連論文リスト

• Sparse Gaussian Graphical Models with Discrete Optimization: Computational and Statistical Perspectives [8.403841349300103]
  本研究では,無向ガウス図形モデルに基づくスパースグラフの学習問題を考察する。 擬似微分関数の $ell_0$-penalized バージョンに基づく新しい推定器 GraphL0BnB を提案する。 実/合成データセットに関する数値実験により,本手法がほぼ最適に,p = 104$の問題を解けることが示唆された。
  論文  参考訳（メタデータ） (2023-07-18T15:49:02Z)
• Stochastic Approximation Approaches to Group Distributionally Robust Optimization [96.26317627118912]
  群分散ロバスト最適化(GDRO) オンライン学習技術は、各ラウンドに必要なサンプル数をm$から1$に減らし、同じサンプルを保持する。 分布依存収束率を導出できる重み付きGDROの新規な定式化。
  論文  参考訳（メタデータ） (2023-02-18T09:24:15Z)
• Uncertainty Quantification of MLE for Entity Ranking with Covariates [3.2839905453386162]
  本稿では,ペア比較に基づくランキング問題の統計的推定と推定について検討する。 我々は、有名なBradley-Terry-Luceモデルを拡張した新しいモデルCAREモデルを提案する。 我々は、スパース比較グラフの下で、$alpha_i*_i=1n$と$beta*$の最大確率推定器を導出する。 大規模数値研究による理論結果の検証と相互資金保有データセットへの適用について検討する。
  論文  参考訳（メタデータ） (2022-12-20T02:28:27Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Seeded graph matching for the correlated Gaussian Wigner model via the projected power method [5.639451539396459]
  グラフマッチングアルゴリズムとして,Emphprojected Power Method (PPM) の性能解析を行った。 PPM は定数 $sigma$ の反復でも機能し、(Mao et al. 2023) のスパース相関エルドス・レニー(CER) モデルに対する解析を (dense) CGW モデルに拡張する。
  論文  参考訳（メタデータ） (2022-04-08T14:31:26Z)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。 具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
  論文  参考訳（メタデータ） (2021-11-14T21:49:58Z)
• 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)
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model [50.38446482252857]
  本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。 最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。 対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
  論文  参考訳（メタデータ） (2020-05-26T17:53:18Z)
• Ranking a set of objects: a graph based least-square approach [70.7866286425868]
  同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。 品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
  論文  参考訳（メタデータ） (2020-02-26T16:19:09Z)

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

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