論文の概要: Convergence analysis of a family of Zermelo-type iterations for the Bradley--Terry model

• arxiv url: http://arxiv.org/abs/2607.22221v1
• Date: Fri, 24 Jul 2026 11:39:24 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-27 20:58:57.119884
• Title: Convergence analysis of a family of Zermelo-type iterations for the Bradley--Terry model
• Title（参考訳）: Bradley-Terryモデルに対するゼルメロ型反復の収束解析
• Abstract要約: 我々は,ZermeloのアルゴリズムがBradley-Terry(BT)モデルの下でかなり高速に収束することを示す。 さらに、BTモデルに基づく集団収束の近似結果を確立し、その実践的妥当性を正当化する。
• 参考スコア（独自算出の注目度）: 6.011136456835614
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Zermelo's algorithm is a classical method for computing the maximum likelihood estimator in the Bradley--Terry (BT) model, but its convergence can be slow in practice. To accelerate computation, Newman introduced a family of Zermelo-type fixed-point iterations parameterized by $α$, with Zermelo's algorithm recovered at $α=1$. Empirical evidence suggests that the choice $α=0$ often converges substantially faster, making it a promising alternative, yet the mechanism underlying this acceleration remains elusive. This paper provides theoretical insight into this phenomenon through a systematic local convergence analysis. We derive closed-form expressions for local convergence factors under synchronous and asynchronous updates and analyze their dependence on $α$ via spectral analysis of the associated Jacobian matrices. For synchronous updates, we show that the algorithm may fail to converge when $α<1$, and its local convergence factor is quasi-convex in $α$ under the population BT model. In contrast, asynchronous updates are always locally convergent, and their local convergence factor is provably monotonically increasing in $α$ under the population BT model of consistently ordered bipartite comparison graphs, establishing the optimality of $α=0$ in this setting. We further establish asymptotic approximation results for the population convergence factors under the BT model, justifying their practical relevance. Numerical experiments on synthetic and real-world datasets confirm the theory. Our analysis complements existing convergence results and shows that the acceleration of $α=0$ arises not only from the parameter choice but, more importantly, from the use of asynchronous updates.
• Abstract（参考訳）: ZermeloのアルゴリズムはBradley-Terry(BT)モデルにおける最大極大推定器を計算するための古典的な方法であるが、実際は収束が遅い。 計算を高速化するため、ニューマンはZermelo型固定点反復のファミリーを$α$でパラメータ化し、Zermeloのアルゴリズムは$α=1$で回復した。 実証的な証拠は、$α=0$という選択は、しばしばかなり早く収束し、有望な代替物となるが、この加速のメカニズムはいまだ解明されていないことを示唆している。 本稿では,系統的な局所収束解析を通じて,この現象に関する理論的知見を提供する。 同期および非同期更新下での局所収束係数の閉形式式を導出し、関連するヤコビ行列のスペクトル解析により、そのα$への依存度を解析する。 同期更新の場合、アルゴリズムは$α<1$のときに収束せず、その局所収束係数は、BTモデルの下では$α$の準凸であることを示す。 対照的に、非同期更新は常に局所収束し、その局所収束係数は、一貫した順序付き二部比較グラフの集団BTモデルの下で、一様に$α$で増加し、この設定で$α=0$の最適性を確立する。 さらに、BTモデルに基づく集団収束係数の漸近近似結果を確立し、それらの実用的妥当性を正当化する。 合成および実世界のデータセットに関する数値実験は、この理論を裏付けるものである。 我々の分析は既存の収束結果を補完し、$α=0$の加速はパラメータ選択から生じるだけでなく、より重要なのは非同期更新から生じることを示している。

関連論文リスト

• Statistical inverse learning and $\ell^1$-regularization [0.27998963147546135]
  統計的逆学習の枠組みにおいて,有限,雑音,間接的な観測からスパース関数の回復について検討した。 我々は、ほぼ公約指数を確立し、予測基準と$ell1$復元基準の両方において、非漸近的高確率収束率を導出する。
  論文  参考訳（メタデータ） (2026-07-08T14:32:08Z)
• Unregularized Linear Convergence in Zero-Sum Game from Preference Feedback [50.89125374999765]
  NLHFにおける最適乗算重み更新(mathtOMWU$)に対する最初の収束保証を提供する。 本分析では, 稀に発生する行動の確率が指数関数的に小さい値から指数関数的に増大する新たな限界収束挙動を同定する。
  論文  参考訳（メタデータ） (2025-12-31T12:08:29Z)
• A Class of Accelerated Fixed-Point-Based Methods with Delayed Inexact Oracles and Its Applications [3.6997773420183866]
  我々は,非拡張作用素の固定点を近似するために,遅延不正確なオラクルを用いた固定点ベースのフレームワークを開発する。 本手法はネステロフ加速法とクラスノセル・スキーマン(KM)反復法の両方を利用する。
  論文  参考訳（メタデータ） (2025-12-15T17:06:22Z)
• Beyond likelihood ratio bias: Nested multi-time-scale stochastic approximation for likelihood-free parameter estimation [49.78792404811239]
  確率分析形式が不明なシミュレーションベースモデルにおける推論について検討する。 我々は、スコアを同時に追跡し、パラメータ更新を駆動する比率のないネスト型マルチタイムスケール近似(SA)手法を用いる。 我々のアルゴリズムは、オリジナルのバイアス$Obig(sqrtfrac1Nbig)$を排除し、収束率を$Obig(beta_k+sqrtfracalpha_kNbig)$から加速できることを示す。
  論文  参考訳（メタデータ） (2024-11-20T02:46:15Z)
• Online Learning Guided Quasi-Newton Methods with Global Non-Asymptotic Convergence [20.766358513158206]
  双対性ギャップの観点から、大域収束率を$O(min1/k,sqrtd/k1.25)$とする。 これらの結果は、外勾配法よりも準ニュートン法の証明可能な利点を示す最初の大域収束結果である。
  論文  参考訳（メタデータ） (2024-10-03T16:08:16Z)
• Fast Nonlinear Two-Time-Scale Stochastic Approximation: Achieving $O(1/k)$ Finite-Sample Complexity [2.5382095320488665]
  本稿では,2つの結合非線形作用素の根を探すために,2時間スケールのモノトン近似の新しい変種を開発することを提案する。 私たちのキーとなるアイデアは、古典的なRuppert-Polyak平均化技術を活用して、それらのサンプルを通して演算子を動的に推定することです。 これらの平均ステップの見積値は、望まれる解を見つけるために、2時間スケールの近似更新で使用される。
  論文  参考訳（メタデータ） (2024-01-23T13:44:15Z)
• Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games [71.73971094342349]
  本稿では,Regret$+$ (RM$+$) に基づく2プレーヤゼロサムゲーム解決アルゴリズムの終点収束特性について検討する。 我々の分析は、アルゴリズムの極限点の幾何学的構造を新たに解析し、最終点収束に関する文献の大半から大きく離れていることを示す。
  論文  参考訳（メタデータ） (2023-11-01T17:34:58Z)
• Towards Faster Non-Asymptotic Convergence for Diffusion-Based Generative Models [49.81937966106691]
  我々は拡散モデルのデータ生成過程を理解するための非漸近理論のスイートを開発する。 従来の研究とは対照的に,本理論は基本的だが多目的な非漸近的アプローチに基づいて開発されている。
  論文  参考訳（メタデータ） (2023-06-15T16:30:08Z)
• Explicit Second-Order Min-Max Optimization: Practical Algorithms and Complexity Analysis [71.05708939639537]
  本研究では,非制約問題に対するグローバルなサドル点を求めるために,不正確なNewton型手法をいくつか提案し,解析する。 提案手法は,Sur分解の必要回数の$O(log(1/eps)$因子をシェービングすることで,既存のライン検索に基づくmin-max最適化を改善する。
  論文  参考訳（メタデータ） (2022-10-23T21:24:37Z)
• A globally convergent fast iterative shrinkage-thresholding algorithm with a new momentum factor for single and multi-objective convex optimization [0.0]
  提案手法はまた,任意の$(a,b)$に対して,大域収束率$O(1/k2)$を持つことを示す。 様々な$(a,b)$で数値結果を報告し、これらの選択のいくつかが古典的な運動量因子よりも良い結果をもたらすことを示す。
  論文  参考訳（メタデータ） (2022-05-11T04:26:00Z)
• Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergence [69.65563161962245]
  ニュートン法を用いて,滑らかで強凸な目的関数を考える。 最適段階において局所収束に遷移する普遍重み付き平均化スキームが存在することを示す。
  論文  参考訳（メタデータ） (2022-04-20T07:14:21Z)
• Finite-Time Analysis for Double Q-learning [50.50058000948908]
  二重Q-ラーニングのための非漸近的有限時間解析を初めて提供する。 同期と非同期の二重Q-ラーニングの両方が,グローバル最適化の$epsilon$-accurate近辺に収束することが保証されていることを示す。
  論文  参考訳（メタデータ） (2020-09-29T18:48:21Z)
• Non-asymptotic Superlinear Convergence of Standard Quasi-Newton Methods [26.328847475942894]
  準ニュートンアルゴリズムのブロイデン級の非漸近超線型収束速度を証明した。 この結果は, 準ニュートン法に対する非漸近超線形収束率を示すのが最初である。
  論文  参考訳（メタデータ） (2020-03-30T16:42:41Z)

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

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