論文の概要: Split-Merge: A Difference-based Approach for Dominant Eigenvalue Problem

• arxiv url: http://arxiv.org/abs/2501.15131v2
• Date: Thu, 26 Jun 2025 03:45:17 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-27 19:53:09.79988
• Title: Split-Merge: A Difference-based Approach for Dominant Eigenvalue Problem
• Title（参考訳）: Split-Merge: 優位固有値問題に対する差分に基づくアプローチ
• Authors: Xiaozhi Liu, Yong Xia,
• Abstract要約: Split-Mergeはスペクトル知識を必要とせずに加速収束を達成するアルゴリズムである。 効率性とスケーラビリティの両面で、最先端のメソッドを一貫して上回ります。 従来のパワーメソッドよりも$boldsymbol10times$のスピードアップを実現している。
• 参考スコア（独自算出の注目度）: 6.938695246282628
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The computation of the dominant eigenvector of symmetric positive semidefinite matrices is a cornerstone operation in numerous optimization-driven applications. Traditional methods, typically based on the \textit{Quotient} formulation, often suffer from challenges related to computational efficiency and reliance on prior spectral knowledge. In this work, we leverage the alternative \textit{Difference} formulation to reinterpret the classical power method as a first-order optimization algorithm. This perspective allows for a novel convergence analysis and facilitates the development of accelerated variants with larger step-sizes, achieving faster convergence without additional computational cost. Building on this insight, we introduce a generalized family of Difference-based methods, with the power method as a special case. Within this family, we propose Split-Merge, an algorithm that attains accelerated convergence without requiring spectral knowledge and operates solely via matrix-vector products. Extensive experiments on both synthetic and real-world datasets demonstrate that Split-Merge consistently outperforms state-of-the-art methods in both efficiency and scalability. In particular, it achieves more than a $\boldsymbol{10\times}$ speedup over the classical power method, underscoring its practical effectiveness for large-scale problems.
• Abstract（参考訳）: 対称正の半定値行列の支配的固有ベクトルの計算は、多くの最適化駆動の応用において基礎となる演算である。 伝統的な手法は、典型的には \textit{Quotient} の定式化に基づいており、しばしば計算効率と事前のスペクトル知識への依存に関する問題に悩まされる。 そこで本研究では,従来の電力法を一階最適化アルゴリズムとして再解釈するために,代用 \textit{Difference} の定式化を利用する。 この観点は、新しい収束解析を可能にし、より大きなステップサイズを持つ加速された変種の開発を促進し、追加の計算コストなしでより高速な収束を達成する。 この知見に基づいて、パワーメソッドを特殊なケースとして、差分法を一般化したファミリを導入する。 このファミリー内では、スペクトル知識を必要とせずに収束を加速し、行列ベクトル生成物を介してのみ動作するアルゴリズムであるSplit-Mergeを提案する。 合成データセットと実世界のデータセットの両方に対する大規模な実験により、Split-Mergeは、効率性とスケーラビリティの両方において、最先端の手法を一貫して上回っていることが示された。 特に、$\boldsymbol{10\times}$ more than a $\boldsymbol{10\times}$ speedup over the classical power method。

関連論文リスト

• Nonlinear Operator Learning Using Energy Minimization and MLPs [0.5898893619901381]
  偏微分方程式による非線形問題に対する解演算子学習法を開発し,評価する。 アプローチは有限要素の離散化に基づいており、潜伏変数を入力とする反復によって解演算子を表現することを目的としている。
  論文  参考訳（メタデータ） (2024-12-05T20:19:16Z)
• The Stochastic Conjugate Subgradient Algorithm For Kernel Support Vector Machines [1.738375118265695]
  本稿では,カーネルサポートベクトルマシン(SVM)に特化して設計された革新的な手法を提案する。 イテレーション毎のイテレーションを高速化するだけでなく、従来のSFO技術と比較して収束度も向上する。 実験の結果,提案アルゴリズムはSFO法のスケーラビリティを維持できるだけでなく,潜在的に超越していることが示された。
  論文  参考訳（メタデータ） (2024-07-30T17:03:19Z)
• l1-norm regularized l1-norm best-fit lines [3.0963566281269594]
  簡単な比率とソート手法を用いた新しいフィッティング法を提案する。 提案アルゴリズムは、O$(n2 m log n)$の最悪の時間複雑性を示し、ある場合にはスパース部分空間に対する大域的最適性を達成する。
  論文  参考訳（メタデータ） (2024-02-26T16:30:58Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。 このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。 本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-09-30T15:57:14Z)
• One-step differentiation of iterative algorithms [7.9495796547433395]
  本稿では, 自動微分法としての一段階微分法, あるいはジャコビアンフリーバックプロパゲーションについて検討する。 両レベル最適化の結果とともに, 具体例を用いた完全理論的近似解析を行う。
  論文  参考訳（メタデータ） (2023-05-23T07:32:37Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。 微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
  論文  参考訳（メタデータ） (2023-02-24T18:41:48Z)
• Making Linear MDPs Practical via Contrastive Representation Learning [101.75885788118131]
  マルコフ決定過程(MDP)における次元性の呪いに、低ランク表現を利用することで対処することが一般的である。 本稿では,効率的な表現学習を可能にしつつ,正規化を自動的に保証する線形MDPの代替的定義について考察する。 いくつかのベンチマークにおいて、既存の最先端モデルベースおよびモデルフリーアルゴリズムよりも優れた性能を示す。
  論文  参考訳（メタデータ） (2022-07-14T18:18:02Z)
• Amortized Implicit Differentiation for Stochastic Bilevel Optimization [53.12363770169761]
  決定論的条件と決定論的条件の両方において、二段階最適化問題を解決するアルゴリズムのクラスについて検討する。 厳密な勾配の推定を補正するために、ウォームスタート戦略を利用する。 このフレームワークを用いることで、これらのアルゴリズムは勾配の偏りのない推定値にアクセス可能な手法の計算複雑性と一致することを示す。
  論文  参考訳（メタデータ） (2021-11-29T15:10:09Z)
• A Discrete Variational Derivation of Accelerated Methods in Optimization [68.8204255655161]
  最適化のための異なる手法を導出できる変分法を導入する。 我々は1対1の対応において最適化手法の2つのファミリを導出する。 自律システムのシンプレクティシティの保存は、ここでは繊維のみに行われる。
  論文  参考訳（メタデータ） (2021-06-04T20:21:53Z)
• Approximation Algorithms for Sparse Principal Component Analysis [57.5357874512594]
  主成分分析(PCA)は、機械学習と統計学において広く使われている次元削減手法である。 スパース主成分分析(Sparse principal Component Analysis)と呼ばれる,スパース主成分負荷を求める様々な手法が提案されている。 本研究では,SPCA問題に対するしきい値の精度,時間,近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-23T04:25:36Z)
• Statistically Guided Divide-and-Conquer for Sparse Factorization of Large Matrix [2.345015036605934]
  統計的問題をスパース係数回帰として定式化し、分割コンカレントアプローチでそれに取り組む。 第1段階分割では、タスクを1組の同時並列推定(CURE)問題に単純化するための2つの潜時並列アプローチについて検討する。 第2段階分割では、CUREの全解を効率的に追跡するために、一連の単純な増分経路からなる段階学習手法を革新する。
  論文  参考訳（メタデータ） (2020-03-17T19:12:21Z)

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

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