論文の概要: Provable Acceleration of Nesterov's Accelerated Gradient for Rectangular Matrix Factorization and Linear Neural Networks

• arxiv url: http://arxiv.org/abs/2410.09640v1
• Date: Mon, 21 Oct 2024 08:33:44 GMT
• ステータス: 処理完了
• システム内更新日: 2024-10-30 09:06:07.710457
• Title: Provable Acceleration of Nesterov's Accelerated Gradient for Rectangular Matrix Factorization and Linear Neural Networks
• Title（参考訳）: 直交行列分解と線形ニューラルネットワークのためのネステロフ加速勾配の確率的加速
• Authors: Zhenghao Xu, Yuqing Wang, Tuo Zhao, Rachel Ward, Molei Tao,
• Abstract要約: 我々はネステロフの加速勾配が複雑性$O(kappalogfrac1epsilon)$に達することを証明している。 特に,NAGが線形収束速度を加速できることを示す。
• 参考スコア（独自算出の注目度）: 46.04785603483612
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the convergence rate of first-order methods for rectangular matrix factorization, which is a canonical nonconvex optimization problem. Specifically, given a rank-$r$ matrix $\mathbf{A}\in\mathbb{R}^{m\times n}$, we prove that gradient descent (GD) can find a pair of $\epsilon$-optimal solutions $\mathbf{X}_T\in\mathbb{R}^{m\times d}$ and $\mathbf{Y}_T\in\mathbb{R}^{n\times d}$, where $d\geq r$, satisfying $\lVert\mathbf{X}_T\mathbf{Y}_T^\top-\mathbf{A}\rVert_\mathrm{F}\leq\epsilon\lVert\mathbf{A}\rVert_\mathrm{F}$ in $T=O(\kappa^2\log\frac{1}{\epsilon})$ iterations with high probability, where $\kappa$ denotes the condition number of $\mathbf{A}$. Furthermore, we prove that Nesterov's accelerated gradient (NAG) attains an iteration complexity of $O(\kappa\log\frac{1}{\epsilon})$, which is the best-known bound of first-order methods for rectangular matrix factorization. Different from small balanced random initialization in the existing literature, we adopt an unbalanced initialization, where $\mathbf{X}_0$ is large and $\mathbf{Y}_0$ is $0$. Moreover, our initialization and analysis can be further extended to linear neural networks, where we prove that NAG can also attain an accelerated linear convergence rate. In particular, we only require the width of the network to be greater than or equal to the rank of the output label matrix. In contrast, previous results achieving the same rate require excessive widths that additionally depend on the condition number and the rank of the input data matrix.
• Abstract（参考訳）: 正準非凸最適化問題である長方行列分解の一階法の収束率について検討する。 具体的には、階数-$r$行列 $\mathbf{A}\in\mathbb{R}^{m\times n}$ が与えられたとき、勾配降下 (GD) が $\epsilon$-optimal solution $\mathbf{X}_T\in\mathbb{R}^{m\times d}$ と $\mathbf{Y}_T\in\mathbb{R}^{n\times d}$ と $d\geq r$ が $\lVert\mathbf{X}_T\mathbf{Y}_T^\top-\mathbf{A}\rVert_\mathrm{F}\leq\epsilon\lVert\mathbf{A}\rVert_\mathrm{F}\leq\leq\epsilon$R}^{m\times d}$ であることを示す。 さらに、ネステロフの加速勾配 (NAG) が、長方行列分解のための一階法の最もよく知られた境界である$O(\kappa\log\frac{1}{\epsilon})$の反復複雑性に達することを証明している。 既存の文献では、小さなバランスの取れたランダムな初期化とは異なり、$\mathbf{X}_0$ が大きければ$\mathbf{Y}_0$ が$0$ となるアンバランスな初期化を採用する。 さらに、我々の初期化と解析は線形ニューラルネットワークにさらに拡張することができ、NAGが加速された線形収束率に達することも証明できる。 特に、ネットワークの幅が出力ラベル行列のランクより大きいか等しいかだけを要求します。 対照的に、同じレートを達成する前の結果は、入力データ行列の条件数とランクに依存する余分な幅を必要とする。

関連論文リスト

• 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)
• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。 これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。 また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
  論文  参考訳（メタデータ） (2024-08-16T02:33:07Z)
• Provably learning a multi-head attention layer [55.2904547651831]
  マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。 本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。 最悪の場合、$m$に対する指数的依存は避けられないことを示す。
  論文  参考訳（メタデータ） (2024-02-06T15:39:09Z)
• Optimal Estimator for Linear Regression with Shuffled Labels [17.99906229036223]
  本稿では,シャッフルラベルを用いた線形回帰の課題について考察する。 mathbb Rntimes m の $mathbf Y、mathbb Rntimes p の mathbf Pi、mathbb Rptimes m$ の mathbf B、mathbb Rntimes m$ の $mathbf Win mathbb Rntimes m$ である。
  論文  参考訳（メタデータ） (2023-10-02T16:44:47Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。 目標は、低ランク因子の積として$mathbfA$を近似することである。 我々の手法はBMF問題の他の一般的な変種に一般化する。
  論文  参考訳（メタデータ） (2023-06-02T18:55:27Z)
• 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)
• Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization [49.090785356633695]
  非対称な低ランク分解問題: [mathbbRm min d , mathbfU$ および MathV$ について検討する。
  論文  参考訳（メタデータ） (2021-06-27T17:25:24Z)

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

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