論文の概要: 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)などのベクトル外挿法を用い、収束率の向上と数値安定性の向上を図る。
合成および実世界のデータに関する大規模な実験により、提案手法は、効率、堅牢性、拡張性の観点から、古典的なニュートンベースの解法よりも大幅に優れていることが示された。
関連論文リスト
- Multiscale Aggregated Hierarchical Attention (MAHA): A Game Theoretic and Optimization Driven Approach to Efficient Contextual Modeling in Large Language Models [0.0]
マルチスケール集約階層的注意(MAHA)は、階層的分解と数学的に厳密な集約を通じて注意機構を再構築する新しいアーキテクチャフレームワークである。
MAHAは、入力シーケンスを学習可能なダウンサンプリング演算子を介して階層スケールに動的に分割する。
実験的なFLOP解析により,4096のシークエンス長で計算コストが81%削減されたことが確認された。
論文 参考訳（メタデータ） (2025-12-16T21:27:21Z) - A joint optimization approach to identifying sparse dynamics using least squares kernel collocation [70.13783231186183]
本研究では,通常の微分方程式(ODE)の学習システムを,状態の不足,部分的,ノイズの多い観測から学習するためのオール・アット・オンス・モデリング・フレームワークを開発する。
提案手法は,関数ライブラリ上でのODEのスパースリカバリ戦略とカーネルヒルベルト空間(RKHS)理論による状態推定とODEの離散化の手法を組み合わせたものである。
論文 参考訳（メタデータ） (2025-11-23T18:04:15Z) - High-Fidelity Scientific Simulation Surrogates via Adaptive Implicit Neural Representations [51.90920900332569]
入射神経表現(INR)は空間的に構造化されたデータをモデリングするためのコンパクトで連続的なフレームワークを提供する。
近年のアプローチでは、剛性幾何学的構造に沿った付加的な特徴を導入することでこの問題に対処している。
機能適応型INR(FA-INR)を提案する。
論文 参考訳（メタデータ） (2025-06-07T16:45:17Z) - Generalization Bounds of Surrogate Policies for Combinatorial Optimization Problems [53.03951222945921]
我々はスムーズな(摂動された)ポリシーを解析し、線形オラクルが使用する方向に対して制御されたランダムな摂動を付加する。
我々の主な貢献は、過剰リスクを摂動バイアス、統計的推定誤差、最適化誤差に分解する一般化境界である。
車両のスケジューリングやスムーズ化がトラクタブルトレーニングと制御された一般化の両方を可能にしていることを示す。
論文 参考訳（メタデータ） (2024-07-24T12:00:30Z) - A fast neural hybrid Newton solver adapted to implicit methods for nonlinear dynamics [6.642649934130245]
本稿では,厳密な時間進化非線形方程式に対する非線形時間ステップシステムのこの解を高速化する,新しいディープラーニングに基づくハイブリッドニュートン法を提案する。
ニュートン法における量的改善率を示し、教師なし学習戦略の一般化誤差の上限を解析する。
論文 参考訳（メタデータ） (2024-07-04T14:02:10Z) - Distributionally Robust Model-based Reinforcement Learning with Large
State Spaces [55.14361269378122]
強化学習における3つの大きな課題は、大きな状態空間を持つ複雑な力学系、コストのかかるデータ取得プロセス、トレーニング環境の展開から現実の力学を逸脱させることである。
広範に用いられているKullback-Leibler, chi-square, および全変分不確実性集合の下で, 連続状態空間を持つ分布ロバストなマルコフ決定過程について検討した。
本稿では,ガウス過程と最大分散削減アルゴリズムを用いて,多出力名目遷移力学を効率的に学習するモデルベースアプローチを提案する。
論文 参考訳（メタデータ） (2023-09-05T13:42:11Z) - Minimizing Quasi-Self-Concordant Functions by Gradient Regularization of
Newton Method [4.62316736194615]
準自己調和平滑成分を用いた複合凸最適化問題について検討する。
この問題クラスは、古典的な自己調和函数とリプシッツ連続ヘッセン函数の間に自然に補間する。
準自己協和関数を最小化するためには、グラディエント正規化を伴う基本ニュートン法を用いることができる。
論文 参考訳（メタデータ） (2023-08-28T17:43:04Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。