論文の概要: Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization

• arxiv url: http://arxiv.org/abs/2106.14289v1
• Date: Sun, 27 Jun 2021 17:25:24 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-29 13:51:58.695781
• Title: Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization
• Title（参考訳）: 非対称低ランク行列因子分解のための勾配のグローバル収束
• Authors: Tian Ye and Simon S. Du
• Abstract要約: 非対称な低ランク分解問題: [mathbbRm min d , mathbfU$ および MathV$ について検討する。
• 参考スコア（独自算出の注目度）: 49.090785356633695
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the asymmetric low-rank factorization problem: \[\min_{\mathbf{U} \in \mathbb{R}^{m \times d}, \mathbf{V} \in \mathbb{R}^{n \times d}} \frac{1}{2}\|\mathbf{U}\mathbf{V}^\top -\mathbf{\Sigma}\|_F^2\] where $\mathbf{\Sigma}$ is a given matrix of size $m \times n$ and rank $d$. This is a canonical problem that admits two difficulties in optimization: 1) non-convexity and 2) non-smoothness (due to unbalancedness of $\mathbf{U}$ and $\mathbf{V}$). This is also a prototype for more complex problems such as asymmetric matrix sensing and matrix completion. Despite being non-convex and non-smooth, it has been observed empirically that the randomly initialized gradient descent algorithm can solve this problem in polynomial time. Existing theories to explain this phenomenon all require artificial modifications of the algorithm, such as adding noise in each iteration and adding a balancing regularizer to balance the $\mathbf{U}$ and $\mathbf{V}$. This paper presents the first proof that shows randomly initialized gradient descent converges to a global minimum of the asymmetric low-rank factorization problem with a polynomial rate. For the proof, we develop 1) a new symmetrization technique to capture the magnitudes of the symmetry and asymmetry, and 2) a quantitative perturbation analysis to approximate matrix derivatives. We believe both are useful for other related non-convex problems.
• Abstract（参考訳）: 非対称な低ランク分解問題を研究する: \[\min_{\mathbf{U} \in \mathbb{R}^{m \times d}, \mathbf{V} \in \mathbb{R}^{n \times d}} \frac{1}{2}\|\mathbf{U}\mathbf{V}^\top -\mathbf{\Sigma}\|_F^2\] ここで$\mathbf{\Sigma}$は$m \times n$と$d$の与えられた行列である。 これは最適化における2つの困難を許容する正準問題である: 1)非凸性と2)非滑らか性($\mathbf{u}$ と $\mathbf{v}$ の不均衡により)。 これは非対称行列センシングや行列補完のようなより複雑な問題のプロトタイプでもある。 非凸かつ非滑らかであるにもかかわらず、ランダムに初期化された勾配降下アルゴリズムは多項式時間でこの問題を解くことができる。 この現象を説明する既存の理論はすべてアルゴリズムの人工的な修正を必要とする。例えば、各イテレーションにノイズを追加し、$\mathbf{u}$と$\mathbf{v}$のバランスをとるためのバランス調整器を追加するなどである。 本稿では,無作為初期化勾配降下が多項式率の非対称低ランク分解問題の大域的最小値に収束することを示す最初の証明を示す。 この証明のために, 1) 対称性と非対称性の大きさを捉える新しい対称性化法, 2) 近似行列微分に対する定量的摂動解析を開発する。 どちらも他の非凸問題に有用であると考えています。

関連論文リスト

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Provable Acceleration of Nesterov's Accelerated Gradient for Rectangular Matrix Factorization and Linear Neural Networks [46.04785603483612]
  我々はネステロフの加速勾配が複雑性$O(kappalogfrac1epsilon)$に達することを証明している。 特に,NAGが線形収束速度を加速できることを示す。
  論文  参考訳（メタデータ） (2024-10-12T20:33:37Z)
• In-depth Analysis of Low-rank Matrix Factorisation in a Federated Setting [21.002519159190538]
  我々は分散アルゴリズムを解析し、$N$クライアント上で低ランク行列の分解を計算する。 グローバルな$mathbfV$ in $mathbbRd times r$をすべてのクライアントに共通とし、ローカルな$mathbfUi$ in $mathbbRn_itimes r$を得る。
  論文  参考訳（メタデータ） (2024-09-13T12:28:42Z)
• Provably learning a multi-head attention layer [55.2904547651831]
  マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。 本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。 最悪の場合、$m$に対する指数的依存は避けられないことを示す。
  論文  参考訳（メタデータ） (2024-02-06T15:39:09Z)
• How Over-Parameterization Slows Down Gradient Descent in Matrix Sensing: The Curses of Symmetry and Initialization [46.55524654398093]
  過パラメータ化が降下の収束挙動をどのように変化させるかを示す。 目的は、ほぼ等方的線形測定から未知の低ランクの地上構造行列を復元することである。 本稿では,GDの一段階だけを修飾し,$alpha$に依存しない収束率を求める手法を提案する。
  論文  参考訳（メタデータ） (2023-10-03T03:34:22Z)
• Convergence of Alternating Gradient Descent for Matrix Factorization [5.439020425819001]
  非対称行列分解対象に一定のステップサイズを施した交互勾配降下(AGD)について検討した。 階数-r$行列 $mathbfA in mathbbRm times n$, smoothness $C$ in the complexity $T$ to be a absolute constant。
  論文  参考訳（メタデータ） (2023-05-11T16:07:47Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。 学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
  論文  参考訳（メタデータ） (2022-06-17T17:55:43Z)
• Multiplicative updates for symmetric-cone factorizations [0.0]
  コーンの分解を計算するための対称錐乗算更新(SCMU)アルゴリズムを導入,解析する。 SCMUアルゴリズムの軌道に沿って2乗損失目標が非減少していることを示す。
  論文  参考訳（メタデータ） (2021-08-02T09:23:39Z)

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

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