論文の概要: The Symmetric Generalized Eigenvalue Problem as a Nash Equilibrium

• arxiv url: http://arxiv.org/abs/2206.04993v2
• Date: Tue, 25 Apr 2023 10:28:54 GMT
• ステータス: 処理完了
• システム内更新日: 2023-04-27 00:09:13.392791
• Title: The Symmetric Generalized Eigenvalue Problem as a Nash Equilibrium
• Title（参考訳）: nash平衡としての対称一般化固有値問題
• Authors: Ian Gemp, Charlie Chen, Brian McWilliams
• Abstract要約: 対称一般化固有値問題(SGEP)は数値線型代数の基本概念である。 現在の最先端のメソッドでは、イテレーション毎に$O(d2k)$ランタイムの複雑さが必要です。 我々は、この並列アプローチを$O(dk)$ランタイムの複雑さを達成するためにどのように修正するかを示す。
• 参考スコア（独自算出の注目度）: 6.295616917309867
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The symmetric generalized eigenvalue problem (SGEP) is a fundamental concept in numerical linear algebra. It captures the solution of many classical machine learning problems such as canonical correlation analysis, independent components analysis, partial least squares, linear discriminant analysis, principal components and others. Despite this, most general solvers are prohibitively expensive when dealing with streaming data sets (i.e., minibatches) and research has instead concentrated on finding efficient solutions to specific problem instances. In this work, we develop a game-theoretic formulation of the top-$k$ SGEP whose Nash equilibrium is the set of generalized eigenvectors. We also present a parallelizable algorithm with guaranteed asymptotic convergence to the Nash. Current state-of-the-art methods require $O(d^2k)$ runtime complexity per iteration which is prohibitively expensive when the number of dimensions ($d$) is large. We show how to modify this parallel approach to achieve $O(dk)$ runtime complexity. Empirically we demonstrate that this resulting algorithm is able to solve a variety of SGEP problem instances including a large-scale analysis of neural network activations.
• Abstract（参考訳）: 対称一般化固有値問題(SGEP)は、数値線型代数の基本概念である。 標準相関解析、独立成分分析、部分最小二乗法、線形判別分析、主成分など、多くの古典的機械学習問題の解を捉えている。 それにもかかわらず、ほとんどの一般的なソルバは、ストリーミングデータセット(ミニバッチ)を扱う場合、制限的に高価であり、研究は、特定の問題インスタンスに対する効率的なソリューションを見つけることに集中している。 本研究では,nash 平衡が一般化固有ベクトルの集合であるトップ-$k$ sgep のゲーム理論的定式化を考案する。 また,Nashへの漸近収束を保証した並列化可能なアルゴリズムを提案する。 現在の最先端のメソッドは、1回のイテレーションで$o(d^2k)$ランタイムの複雑さを必要とします。 私たちは、この並列アプローチを$O(dk)$ランタイムの複雑さを達成する方法を示します。 実験の結果,ニューラルネットワークのアクティベーションの大規模解析を含む様々なsgep問題に対して,このアルゴリズムが解決できることを実証する。

関連論文リスト

• Eigenpath traversal by Poisson-distributed phase randomisation [0.08192907805418585]
  本稿では,AQC(Adiabatic Quantum Computation)と同様,量子計算のためのフレームワークを提案する。 ポアソン過程によって決定された間隔でランダムデファーズ演算を行うことにより、特定の固有値に関連する固有空間を追跡することができる。 有限性に対する単純な微分方程式を導出し、アルゴリズムのクラスの時間複雑性を境界とする一般定理を導出する。
  論文  参考訳（メタデータ） (2024-06-06T11:33:29Z)
• Optimization without Retraction on the Random Generalized Stiefel Manifold [9.301728976515255]
  本稿では,B$のランダムな推定値にのみアクセスしながら,最適化問題を解く,安価な反復法を提案する。 我々の方法はすべての反復において制約を強制するのではなく、予想で定義される一般化されたスティーフェル多様体上の臨界点に収束する反復を生成する。
  論文  参考訳（メタデータ） (2024-05-02T19:55:30Z)
• Matching the Statistical Query Lower Bound for k-sparse Parity Problems with Stochastic Gradient Descent [83.85536329832722]
  勾配勾配降下(SGD)は,$d$次元ハイパーキューブ上の$k$パリティ問題を効率的に解くことができることを示す。 次に、SGDでトレーニングされたニューラルネットワークがどのようにして、小さな統計的エラーで$k$-parityの問題を解決するかを実証する。
  論文  参考訳（メタデータ） (2024-04-18T17:57:53Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。 我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
  論文  参考訳（メタデータ） (2024-03-08T18:50:19Z)
• A Novel Normalized-Cut Solver with Nearest Neighbor Hierarchical Initialization [107.07093621337084]
  正規化カット(N-Cut)は、スペクトルクラスタリングの有名なモデルである。 1)正規化ラプラシア行列の連続スペクトル埋め込みを計算する; 2)$K$-meansまたはスペクトル回転による離散化。 有名な座標降下法に基づく新しいN-Cut解法を提案する。
  論文  参考訳（メタデータ） (2023-11-26T07:11:58Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Statistical-Computational Tradeoffs in Mixed Sparse Linear Regression [20.00109111254507]
  この問題は、$frackSNR2$-to-$frack2SNR2$statistic-to-computational gapである。 また,この問題が困難な狭い状況以外では,関連する混合回帰検出問題を解くための簡単なしきい値決定アルゴリズムも分析する。
  論文  参考訳（メタデータ） (2023-03-03T18:03:49Z)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。 本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
  論文  参考訳（メタデータ） (2022-07-18T12:03:26Z)
• An Online Riemannian PCA for Stochastic Canonical Correlation Analysis [37.8212762083567]
  投影行列の再パラメータ化を用いた正準相関解析(CCA)のための効率的なアルゴリズム(RSG+)を提案する。 本論文は,その特性の定式化と技術的解析に主眼を置いているが,本実験により,一般的なデータセットに対する経験的挙動が極めて有望であることが確認された。
  論文  参考訳（メタデータ） (2021-06-08T23:38:29Z)
• Stochastic Approximation for Online Tensorial Independent Component Analysis [98.34292831923335]
  独立成分分析(ICA)は統計機械学習や信号処理において一般的な次元削減ツールである。 本稿では,各独立成分を推定する副産物オンライン時系列アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-12-28T18:52:37Z)

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

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