論文の概要: Difference vs. Quotient: A Novel Algorithm for Dominant Eigenvalue Problem

• arxiv url: http://arxiv.org/abs/2501.15131v1
• Date: Sat, 25 Jan 2025 08:37:17 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-29 16:40:28.667373
• Title: Difference vs. Quotient: A Novel Algorithm for Dominant Eigenvalue Problem
• Title（参考訳）: Different vs. Quotient: 支配固有値問題に対する新しいアルゴリズム
• Authors: Xiaozhi Liu, Yong Xia,
• Abstract要約: 本稿では,非制約差分法を用いて固有値問題を修正し,新しい視点を紹介する。 そこで本研究では,スペクトル事前知識を使わずに最大加速度を実現するSplit-Mergeアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 6.938695246282628
• License:
• Abstract: The computation of the dominant eigenvector of symmetric positive semidefinite matrices is a cornerstone operation in numerous machine learning applications. Traditional approaches predominantly rely on the constrained Quotient formulation, which underpins most existing methods. However, these methods often suffer from challenges related to computational efficiency and dependence on spectral prior knowledge. This paper introduces a novel perspective by reformulating the eigenvalue problem using an unconstrained Difference formulation. This new approach sheds light on classical methods, revealing that the power method can be interpreted as a specific instance of Difference of Convex Algorithms. Building on this insight, we develop a generalized family of Difference-Type methods, which encompasses the power method as a special case. Within this family, we propose the Split-Merge algorithm, which achieves maximal acceleration without spectral prior knowledge and operates solely through matrix-vector products, making it both efficient and easy to implement. Extensive empirical evaluations on both synthetic and real-world datasets highlight that the Split-Merge algorithm achieves over a $\boldsymbol{10\times}$ speedup compared to the basic power method, offering significant advancements in efficiency and practicality for large-scale machine learning problems.
• Abstract（参考訳）: 対称正の半定値行列の優性固有ベクトルの計算は多くの機械学習応用において基礎となる演算である。 伝統的なアプローチは、主に既存の方法の根底にある制約付き定式化に依存している。 しかしながら、これらの手法は、計算効率とスペクトル事前知識への依存に関連する課題に悩まされることが多い。 本稿では,非制約差分法を用いて固有値問題を修正し,新しい視点を紹介する。 この新しいアプローチは古典的な手法に光を当て、このパワーメソッドは凸アルゴリズムの差の特定の例として解釈できることを示した。 この知見に基づいて、パワーメソッドを特殊なケースとして含む、一般化された差分型手法のファミリーを開発する。 このファミリー内では、スペクトル事前知識を使わずに最大加速度を達成し、行列ベクトル生成物のみで動作し、効率的かつ実装が容易なSplit-Mergeアルゴリズムを提案する。 Split-Mergeアルゴリズムは、ベーシックパワーメソッドと比較して、$\boldsymbol{10\times}$のスピードアップを達成し、大規模な機械学習問題に対する効率と実用性を大幅に向上させる。

関連論文リスト

• The Stochastic Conjugate Subgradient Algorithm For Kernel Support Vector Machines [1.738375118265695]
  本稿では,カーネルサポートベクトルマシン(SVM)に特化して設計された革新的な手法を提案する。 イテレーション毎のイテレーションを高速化するだけでなく、従来のSFO技術と比較して収束度も向上する。 実験の結果,提案アルゴリズムはSFO法のスケーラビリティを維持できるだけでなく,潜在的に超越していることが示された。
  論文  参考訳（メタデータ） (2024-07-30T17:03:19Z)
• Tensor networks based quantum optimization algorithm [0.0]
  最適化において、よく知られた古典的アルゴリズムの1つは電力反復である。 我々はこの落とし穴を回避するために量子化を提案する。 我々の手法はインスタンス非依存となり、量子コンピューティングの枠組みの中でブラックボックス最適化に対処することができる。
  論文  参考訳（メタデータ） (2024-04-23T13:49:11Z)
• 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)

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

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