論文の概要: Achievability and Impossibility of Exact Pairwise Ranking

• arxiv url: http://arxiv.org/abs/2111.10021v1
• Date: Fri, 19 Nov 2021 03:16:29 GMT
• ステータス: 処理完了
• システム内更新日: 2021-11-23 02:11:13.178078
• Title: Achievability and Impossibility of Exact Pairwise Ranking
• Title（参考訳）: 完全対数ランキングの達成可能性と不可能性
• Authors: Yihan He
• Abstract要約: 雑音のあるペアワイズ比較に基づいて,$n$アイテムのランクを回復する問題を考察する。 本分析では, パラメトリック限界と正確に一致した, 正確な要件に対して, 情報理論上および下限の鋭い情報を与えた。
• 参考スコア（独自算出の注目度）: 1.0878040851638
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the problem of recovering the rank of a set of $n$ items based on noisy pairwise comparisons. We assume the SST class as the family of generative models. Our analysis gave sharp information theoretic upper and lower bound for the exact requirement, which matches exactly in the parametric limit. Our tight analysis on the algorithm induced by the moment method gave better constant in Minimax optimal rate than ~\citet{shah2017simple} and contribute to their open problem. The strategy we used in this work to obtain information theoretic bounds is based on combinatorial arguments and is of independent interest.
• Abstract（参考訳）: 我々は,一組のn$項目のランクを,うるさい対数比較に基づいて回復する問題を考える。 我々は、SSTクラスを生成モデルのファミリとみなす。 本解析は, パラメトリック限界に適合する正確な要件に対して, 鋭い情報理論上および下限を与えた。 モーメント法により誘導されるアルゴリズムの厳密な解析により, ~\citet{shah2017simple} よりもミニマックスの最適速度の定数が向上し, 開問題に寄与した。 情報理論的な境界を得るためにこの研究で使った戦略は、組合せ論に基づいており、独立した興味を持っている。

関連論文リスト

• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。 本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
  論文  参考訳（メタデータ） (2024-06-28T02:56:22Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Revisiting Inexact Fixed-Point Iterations for Min-Max Problems: Stochasticity and Structured Nonconvexity [18.427215139020632]
  1L 1$は、マルチレベルなCarloイテレーションであっても、最先端の問題を改善するために使用できることを示す。 解に関する唯一のホールドが新しい1L 1$理論である場合、不正確なハルパーネス推定器を1L 1$で解析する。
  論文  参考訳（メタデータ） (2024-02-07T18:22:41Z)
• Optimal PAC Bounds Without Uniform Convergence [11.125968799758436]
  我々は、一様収束論の極限を超えるフレームワークを通して、最適な高確率リスク境界を提供する。 我々のフレームワークは、置換不変予測器の残余誤差を高い確率リスク境界に変換する。 具体的には, 1-inclusion graph アルゴリズムの特定のアグリゲーションが最適であることを示す。
  論文  参考訳（メタデータ） (2023-04-18T17:57:31Z)
• Smoothed Analysis of Sequential Probability Assignment [16.090378928208885]
  本稿では,情報理論的に最適であるminmaxレートと,最大極大推定器オラクルを含むアルゴリズム削減の枠組みについて検討する。 提案手法は,スムーズな逆数に対する逐次確率割当のためのミニマックスレートから,トランスダクティブ学習のためのミニマックスレートへの汎用的な削減を実現する。
  論文  参考訳（メタデータ） (2023-03-08T19:25:57Z)
• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。 予測と高い確率で、新しい過剰なリスク境界を提供する。 我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
  論文  参考訳（メタデータ） (2022-11-03T12:40:24Z)
• STORM+: Fully Adaptive SGD with Momentum for Nonconvex Optimization [74.1615979057429]
  本研究では,スムーズな損失関数に対する期待値である非バッチ最適化問題について検討する。 我々の研究は、学習率と運動量パラメータを適応的に設定する新しいアプローチとともに、STORMアルゴリズムの上に構築されている。
  論文  参考訳（メタデータ） (2021-11-01T15:43:36Z)
• Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
  マルコフ決定過程における純粋探索問題について検討する。 エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
  論文  参考訳（メタデータ） (2021-06-05T09:16:28Z)
• Ranking a set of objects: a graph based least-square approach [70.7866286425868]
  同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。 品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
  論文  参考訳（メタデータ） (2020-02-26T16:19:09Z)

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

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