論文の概要: The Power of Preconditioning in Overparameterized Low-Rank Matrix
Sensing
- arxiv url: http://arxiv.org/abs/2302.01186v2
- Date: Tue, 6 Jun 2023 16:36:11 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-07 20:56:49.559088
- Title: The Power of Preconditioning in Overparameterized Low-Rank Matrix
Sensing
- Title（参考訳）: 過パラメータ低ランクマトリクスセンシングにおけるプリコンディショニングのパワー
- Authors: Xingyu Xu, Yandi Shen, Yuejie Chi, Cong Ma
- Abstract要約: $textsfScaledGD($lambda$)$は、低ランク行列センシング問題に取り組むための事前条件付き勾配降下法である。
我々は、$textsfScaledGD($lambda$)$が、少数の反復の後、一定の線形速度で真の低ランク行列に収束することを示す。
- 参考スコア（独自算出の注目度）: 29.75164824243405
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We propose $\textsf{ScaledGD($\lambda$)}$, a preconditioned gradient descent
method to tackle the low-rank matrix sensing problem when the true rank is
unknown, and when the matrix is possibly ill-conditioned. Using
overparametrized factor representations, $\textsf{ScaledGD($\lambda$)}$ starts
from a small random initialization, and proceeds by gradient descent with a
specific form of damped preconditioning to combat bad curvatures induced by
overparameterization and ill-conditioning. At the expense of light
computational overhead incurred by preconditioners,
$\textsf{ScaledGD($\lambda$)}$ is remarkably robust to ill-conditioning
compared to vanilla gradient descent ($\textsf{GD}$) even with
overprameterization. Specifically, we show that, under the Gaussian design,
$\textsf{ScaledGD($\lambda$)}$ converges to the true low-rank matrix at a
constant linear rate after a small number of iterations that scales only
logarithmically with respect to the condition number and the problem dimension.
This significantly improves over the convergence rate of vanilla $\textsf{GD}$
which suffers from a polynomial dependency on the condition number. Our work
provides evidence on the power of preconditioning in accelerating the
convergence without hurting generalization in overparameterized learning.
- Abstract（参考訳）: 真のランクが不明な場合や、行列が不条件である場合の低ランク行列センシング問題に対処するための事前条件付き勾配降下法である、$\textsf{scaledgd($\lambda$)}$を提案する。
オーバーパラメータ化係数表現を使用すると、$\textsf{ScaledGD($\lambda$)}$は小さなランダム初期化から始まり、減衰プレコンディショニングの特定の形式で勾配降下して、オーバーパラメータ化や悪曲率に対処する。
プリコンディショナーによって引き起こされる光計算オーバーヘッドを犠牲にして、$\textsf{ScaledGD($\lambda$)}$は、過小評価でさえもバニラ勾配降下($\textsf{GD}$)と比較して非常に堅牢である。
具体的には、ガウス設計の下で、$\textsf{ScaledGD($\lambda$)}$は条件数と問題次元に関して対数的にしかスケールしない少数の反復の後に、真の低ランク行列に一定の線形速度で収束することを示す。
これにより、条件数に対する多項式依存に苦しむvanilla $\textsf{GD}$の収束率を大幅に改善する。
我々の研究は、過パラメータ学習における一般化を損なうことなく収束を加速する前処理の力を示す。
関連論文リスト
- Convergence Rate Analysis of LION [54.28350823319057]
LION は、勾配カルシュ=クーン=T (sqrtdK-)$で測定された $cal(sqrtdK-)$ の反復を収束する。
従来のSGDと比較して,LIONは損失が小さく,性能も高いことを示す。
論文 参考訳（メタデータ） (2024-11-12T11:30:53Z) - Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity [50.25258834153574]
我々は、(強に)凸 $(L0)$-smooth 関数のクラスに焦点を当て、いくつかの既存のメソッドに対する新しい収束保証を導出する。
特に,スムーズなグラディエント・クリッピングを有するグラディエント・ディフレッシュと,ポリアク・ステップサイズを有するグラディエント・ディフレッシュのコンバージェンス・レートの改善を導出した。
論文 参考訳（メタデータ） (2024-09-23T13:11:37Z) - On the Linear Convergence of Policy Gradient under Hadamard
Parameterization [4.182089296199263]
本研究では,アダマールパラメータ化に基づく決定論的政策勾配の収束性について検討する。
すべてのイテレーションに対して$O(frac1k)$レートでエラーが減少することを示す。
論文 参考訳（メタデータ） (2023-05-31T05:51:15Z) - Restricted Strong Convexity of Deep Learning Models with Smooth
Activations [31.003601717265006]
本研究では,スムーズなアクティベーション機能を持つディープラーニングモデルの最適化問題について検討する。
Restricted Strong Convexity (RSC) に基づく最適化の新しい解析手法を提案する。
深層学習モデルのためのRCCに基づくGDの幾何収束性を確立するための最初の結果である。
論文 参考訳（メタデータ） (2022-09-29T21:24:26Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳（メタデータ） (2022-06-17T06:10:20Z) - Preconditioned Gradient Descent for Overparameterized Nonconvex
Burer--Monteiro Factorization with Global Optimality Certification [14.674494335647841]
非函数 $f(X)=phi(XXT)$ を$ntimes r$ factor matrix $X$ で最小化するために勾配降下を考える。
本稿では,勾配降下の収束率を線形に戻すための安価なプレコンディショナーを提案する。
論文 参考訳（メタデータ） (2022-06-07T14:26:49Z) - A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
凸凹対象 $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, ここで、$f$ は局所リプシッツ勾配を持つ凸関数であり、$g$ は凸かつ非滑らかである。
主勾配ステップと2段ステップを交互に交互に行うCondat-Vuアルゴリズムの適応バージョンを提案する。
論文 参考訳（メタデータ） (2021-10-28T14:19:30Z) - WARPd: A linearly convergent first-order method for inverse problems
with approximate sharpness conditions [0.0]
シャープネス条件は1次法のリスタートスキームのリカバリ性能を直接制御する。
重み付き, 加速度付き, 再起動されたプリマルデュアル(WARPd)の1次手法を提案する。
一般的な近似的シャープネス条件の下では、WARPd は所望のベクトルに対して安定な線形収束を達成する。
本稿では、WARPdが専門的な最先端手法と比較し、大規模問題の解決に最適であることを示す。
論文 参考訳（メタデータ） (2021-10-24T13:19:41Z) - Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled
Gradient Descent [34.0533596121548]
低ランク行列推定は凸問題を収束させ、信号処理、機械学習、画像科学に多くの応用を見出す。
低ランク行列の個数の観点から,ScaledGDが最良となることを示す。
我々の分析は、低ランク勾配降下に類似した一般損失にも適用できる。
論文 参考訳（メタデータ） (2020-05-18T17:17:16Z) - Differentially Quantized Gradient Methods [53.3186247068836]
微分量子化グラディエントDescence (DQ-GD) が$maxsigma_mathrmGD, rhon 2-R$の線形収縮係数を得ることを示す。
あるクラス内のアルゴリズムは$maxsigma_mathrmGD, 2-R$よりも早く収束できない。
論文 参考訳（メタデータ） (2020-02-06T20:40:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。