論文の概要: Convergence of Alternating Gradient Descent for Matrix Factorization
- arxiv url: http://arxiv.org/abs/2305.06927v1
- Date: Thu, 11 May 2023 16:07:47 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-12 14:04:13.533349
- Title: Convergence of Alternating Gradient Descent for Matrix Factorization
- Title(参考訳): マトリックス因子化のための交互勾配の収束
- Authors: Rachel Ward and Tamara G. Kolda
- Abstract要約: mathbbRm × n の階数-$r 行列 $mathbfA に対して、 = left( left()A)sigma_r(mathbfA)right を示す。
交互勾配降下の反復は、$epsilon$-optimal factorization $| mathbfA に到達するのに十分である。
我々の証明は概念的には単純であり、一様PL不等式と一様リプシッツ定数は十分多くの反復に対して保証される。
- 参考スコア(独自算出の注目度): 3.655021726150368
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider alternating gradient descent (AGD) with fixed step size $\eta >
0$, applied to the asymmetric matrix factorization objective. We show that, for
a rank-$r$ matrix $\mathbf{A} \in \mathbb{R}^{m \times n}$, $T = \left(
\left(\frac{\sigma_1(\mathbf{A})}{\sigma_r(\mathbf{A})}\right)^2
\log(1/\epsilon)\right)$ iterations of alternating gradient descent suffice to
reach an $\epsilon$-optimal factorization $\| \mathbf{A} -
\mathbf{X}_T^{\vphantom{\intercal}} \mathbf{Y}_T^{\intercal} \|_{\rm F}^2 \leq
\epsilon \| \mathbf{A} \|_{\rm F}^2$ with high probability starting from an
atypical random initialization. The factors have rank $d>r$ so that
$\mathbf{X}_T\in\mathbb{R}^{m \times d}$ and $\mathbf{Y}_T \in\mathbb{R}^{n
\times d}$. Experiments suggest that our proposed initialization is not merely
of theoretical benefit, but rather significantly improves convergence of
gradient descent in practice. Our proof is conceptually simple: a uniform
PL-inequality and uniform Lipschitz smoothness constant are guaranteed for a
sufficient number of iterations, starting from our random initialization. Our
proof method should be useful for extending and simplifying convergence
analyses for a broader class of nonconvex low-rank factorization problems.
- Abstract(参考訳): 非対称行列分解の目的に対して, 一定のステップサイズが$\eta > 0$の交互勾配降下 (AGD) を考える。
階数-$r$行列 $\mathbf{A} \in \mathbb{R}^{m \times n}$, $T = \left( \left(\frac{\sigma_1(\mathbf{A})}\right)^2 \log(1/\epsilon)\right)^2 \log(1/\epsilon)\right)$\epsilon$-optimal factorization $\| \mathbf{A}\mathbf{X}_T^{\vphantom {\intercal}} \mathbf{Y}_T^{\vphantom \intercal} \|_{\rm F}^2 \leq \epsilon \mathbf{A} \|F2\rm F}=2\leq \mathbf{A} \mathbf{A})\right)$ $\epsilon$-optimal factorization $\| \mathbf{A}\mathbf{X}_T^{\vphantom \times n}$であることを示す。
これらの因子は$d>r$を付け、$\mathbf{x}_t\in\mathbb{r}^{m \times d}$ と$\mathbf{y}_t \in\mathbb{r}^{n \times d}$ となる。
実験により,提案する初期化は理論上の利点に留まらず,実際には勾配降下の収束を著しく改善することが示唆された。
我々の証明は概念的には単純であり、一様PL不等式と一様リプシッツ滑らか性定数は、我々のランダム初期化から始まる十分数の反復に対して保証される。
本手法は,非凸低ランク因子分解問題のより広いクラスに対する収束解析の拡張と単純化に有用である。
関連論文リスト
- 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) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳(メタデータ) (2023-09-25T17:54:19Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳(メタデータ) (2023-06-30T08:34:29Z) - Near Optimal Heteroscedastic Regression with Symbiotic Learning [29.16456701187538]
我々は不連続線形回帰の問題を考察する。
正則ノルムにおいて$mathbfw*$を$tildeOleft(|mathbff*|2cdot left(frac1n + left(dnright)2right)$の誤差まで推定し、一致する下界を証明できる。
論文 参考訳(メタデータ) (2023-06-25T16:32:00Z) - Convergence of a Normal Map-based Prox-SGD Method under the KL
Inequality [0.0]
我々は、$symbol$k$収束問題に対して、新しいマップベースのアルゴリズム(mathsfnorMtext-mathsfSGD$)を提案する。
論文 参考訳(メタデータ) (2023-05-10T01:12:11Z) - Faster Gradient-Free Algorithms for Nonsmooth Nonconvex Stochastic
Optimization [14.960834297685366]
我々は、mathbbRd f(x) 三角形q mathbbE_xi [Fxi]$inf(x)$ Lipschitz における $min_x という形式の問題を考察する。
最近提案された勾配なし法は、少なくとも$mathcalO(L4 d3/2 epsilon-4 + Goldstein L d3/2 delta-1 epsilon-4)$ 0次複雑性を必要とする。
論文 参考訳(メタデータ) (2023-01-16T13:33:37Z) - 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) - Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
論文 参考訳(メタデータ) (2020-05-29T07:20:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。