論文の概要: An Accelerated Newton-GMRES Method for Multilinear PageRank

• arxiv url: http://arxiv.org/abs/2509.23374v1
• Date: Sat, 27 Sep 2025 15:45:57 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-30 22:32:19.192012
• Title: An Accelerated Newton-GMRES Method for Multilinear PageRank
• Title（参考訳）: 多線形ページランドに対する高速化Newton-GMRES法
• Authors: Maryam Boubekraoui, Ridwane Tahiri,
• Abstract要約: マルチ線形ページランク問題は、高階マルコフ連鎖の研究において自然に生じるもので、そのような相互作用を捉えるための強力な枠組みである。 ニュートン法はこの問題に対して局所的な二次収束を達成できるが、各反復で大きな線形系を解く必要がある。 我々は、クリロフ部分空間技術を利用して、大きなヤコビ行列を明示的に形成せずにニュートンステップを近似する加速ニュートン-GMRES法を提案する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Modeling complex multiway relationships in large-scale networks is becoming more and more challenging in data science. The multilinear PageRank problem, arising naturally in the study of higher-order Markov chains, is a powerful framework for capturing such interactions, with applications in web ranking, recommendation systems, and social network analysis. It extends the classical Google PageRank model to a tensor-based formulation, leading to a nonlinear system that captures multi-way dependencies between states. Newton-based methods can achieve local quadratic convergence for this problem, but they require solving a large linear system at each iteration, which becomes too costly for large-scale applications. To address this challenge, we present an accelerated Newton-GMRES method that leverages Krylov subspace techniques to approximate the Newton step without explicitly forming the large Jacobian matrix. We further employ vector extrapolation methods, including Minimal Polynomial Extrapolation (MPE), Reduced Rank Extrapolation (RRE), and Anderson Acceleration (AA), to improve the convergence rate and enhance numerical stability. Extensive experiments on synthetic and real-world data demonstrate that the proposed approach significantly outperforms classical Newton-based solvers in terms of efficiency, robustness, and scalability.
• Abstract（参考訳）: 大規模ネットワークにおける複雑なマルチウェイ関係のモデリングは、データサイエンスにおいてますます困難になりつつある。 マルチリニアなPageRank問題は、高階マルコフ連鎖の研究で自然に発生するもので、Webランキング、レコメンデーションシステム、ソーシャルネットワーク分析など、そのような相互作用を捉えるための強力なフレームワークである。 これは、古典的なGoogle PageRankモデルをテンソルベースの定式化に拡張し、状態間のマルチウェイ依存関係をキャプチャする非線形システムに繋がる。 ニュートン法はこの問題に対して局所的な二次収束を達成できるが、各イテレーションで大きな線形系を解く必要があり、大規模なアプリケーションにはコストがかかりすぎる。 この課題に対処するために、クリャロフ部分空間技術を利用して、大きなヤコビ行列を明示的に形成することなくニュートンステップを近似する、加速ニュートン-GMRES法を提案する。 さらに、最小多項式外挿法(MPE)、低ランク外挿法(RRE)、アンダーソン加速度法(AA)などのベクトル外挿法を用い、収束率の向上と数値安定性の向上を図る。 合成および実世界のデータに関する大規模な実験により、提案手法は、効率、堅牢性、拡張性の観点から、古典的なニュートンベースの解法よりも大幅に優れていることが示された。

関連論文リスト

• High-Fidelity Scientific Simulation Surrogates via Adaptive Implicit Neural Representations [51.90920900332569]
  入射神経表現(INR)は空間的に構造化されたデータをモデリングするためのコンパクトで連続的なフレームワークを提供する。 近年のアプローチでは、剛性幾何学的構造に沿った付加的な特徴を導入することでこの問題に対処している。 機能適応型INR(FA-INR)を提案する。
  論文  参考訳（メタデータ） (2025-06-07T16:45:17Z)
• Distributionally Robust Model-based Reinforcement Learning with Large State Spaces [55.14361269378122]
  強化学習における3つの大きな課題は、大きな状態空間を持つ複雑な力学系、コストのかかるデータ取得プロセス、トレーニング環境の展開から現実の力学を逸脱させることである。 広範に用いられているKullback-Leibler, chi-square, および全変分不確実性集合の下で, 連続状態空間を持つ分布ロバストなマルコフ決定過程について検討した。 本稿では,ガウス過程と最大分散削減アルゴリズムを用いて,多出力名目遷移力学を効率的に学習するモデルベースアプローチを提案する。
  論文  参考訳（メタデータ） (2023-09-05T13:42:11Z)
• Adaptive pruning-based Newton's method for distributed learning [14.885388389215587]
  本稿では,分散適応ニュートン学習(textttDANL)という,新規で効率的なアルゴリズムを提案する。 textttDANLは、利用可能なリソースに効率よく適応し、高い効率を維持しながら、線形収束率を達成する。 実験により、textttDANLは、効率的な通信と異なるデータセット間の強い性能で線形収束を実現することが示された。
  論文  参考訳（メタデータ） (2023-08-20T04:01:30Z)
• Towards a Better Theoretical Understanding of Independent Subnetwork Training [56.24689348875711]
  独立サブネットワークトレーニング(IST)の理論的考察 ISTは、上記の問題を解決するための、最近提案され、非常に効果的である。 圧縮通信を用いた分散手法など,ISTと代替手法の基本的な違いを同定する。
  論文  参考訳（メタデータ） (2023-06-28T18:14:22Z)
• FedNew: A Communication-Efficient and Privacy-Preserving Newton-Type Method for Federated Learning [75.46959684676371]
  我々は、クライアントからPSにヘッセン情報を送信する必要がないFedNewという新しいフレームワークを紹介した。 FedNewは勾配情報を隠蔽し、既存の最先端技術と比べてプライバシー保護のアプローチをもたらす。
  論文  参考訳（メタデータ） (2022-06-17T15:21:39Z)
• Efficient Model-Based Multi-Agent Mean-Field Reinforcement Learning [89.31889875864599]
  マルチエージェントシステムにおける学習に有効なモデルベース強化学習アルゴリズムを提案する。 我々の理論的な貢献は、MFCのモデルベース強化学習における最初の一般的な後悔の限界である。 コア最適化問題の実用的なパラメトリゼーションを提供する。
  論文  参考訳（メタデータ） (2021-07-08T18:01:02Z)
• Deep Magnification-Flexible Upsampling over 3D Point Clouds [103.09504572409449]
  本稿では,高密度点雲を生成するためのエンドツーエンド学習ベースのフレームワークを提案する。 まずこの問題を明示的に定式化し、重みと高次近似誤差を判定する。 そこで我々は,高次改良とともに,統一重みとソート重みを適応的に学習する軽量ニューラルネットワークを設計する。
  論文  参考訳（メタデータ） (2020-11-25T14:00:18Z)

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

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