論文の概要: Preconditioned Gradient Descent for Over-Parameterized Nonconvex Matrix Factorization
- arxiv url: http://arxiv.org/abs/2504.09708v1
- Date: Sun, 13 Apr 2025 20:06:49 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-04-15 16:53:53.979057
- Title: Preconditioned Gradient Descent for Over-Parameterized Nonconvex Matrix Factorization
- Title（参考訳）: 過パラメータ非凸行列分解のためのプレコンディショニンググラディエント染料
- Authors: Gavin Zhang, Salar Fattahi, Richard Y. Zhang,
- Abstract要約: 非特定行列分解の実例では、真の解体$のランクはしばしば未知であるため、モデルのランク子$は$r>rstar$として特異である。
本稿では,行列センサの非行列因数分解のための安価なサブプロセッサを提案し,非依存の場合においても収束係数を線形に復元する。
我々の数値実験により、PrecGD は他の変種非行列分解の収束を回復する上でも同様にうまく機能することがわかった。
- 参考スコア（独自算出の注目度）: 19.32160757444549
- License:
- Abstract: In practical instances of nonconvex matrix factorization, the rank of the true solution $r^{\star}$ is often unknown, so the rank $r$ of the model can be overspecified as $r>r^{\star}$. This over-parameterized regime of matrix factorization significantly slows down the convergence of local search algorithms, from a linear rate with $r=r^{\star}$ to a sublinear rate when $r>r^{\star}$. We propose an inexpensive preconditioner for the matrix sensing variant of nonconvex matrix factorization that restores the convergence rate of gradient descent back to linear, even in the over-parameterized case, while also making it agnostic to possible ill-conditioning in the ground truth. Classical gradient descent in a neighborhood of the solution slows down due to the need for the model matrix factor to become singular. Our key result is that this singularity can be corrected by $\ell_{2}$ regularization with a specific range of values for the damping parameter. In fact, a good damping parameter can be inexpensively estimated from the current iterate. The resulting algorithm, which we call preconditioned gradient descent or PrecGD, is stable under noise, and converges linearly to an information theoretically optimal error bound. Our numerical experiments find that PrecGD works equally well in restoring the linear convergence of other variants of nonconvex matrix factorization in the over-parameterized regime.
- Abstract（参考訳）: 非凸行列分解の実例では、真の解 $r^{\star}$ のランクはしばしば不明であるため、モデルの階数 $r$ は $r>r^{\star}$ として過剰に特定することができる。
この行列因数分解の過度パラメータ化規則は,$r=r^{\star}$の線形速度から$r>r^{\star}$の線形速度まで,局所探索アルゴリズムの収束を著しく遅くする。
本研究では,非凸行列因数分解の行列センシング変種に対する安価なプレコンディショナーを提案する。
解の近傍における古典的な勾配降下は、モデル行列因子が特異になる必要性のために遅くなる。
我々の重要な結果は、この特異性は減衰パラメータの特定の範囲の値で$\ell_{2}$正規化によって修正できるということである。
実際、現在の繰り返しから優れた減衰パラメータを安価に推定することができる。
予備条件勾配降下(PrecGD)と呼ばれる結果のアルゴリズムは雑音下で安定であり、理論上最適誤差境界に線形収束する。
我々の数値実験により、PrecGDは、過パラメータ化状態における他の非凸行列分解の線形収束を復元する上でも同様にうまく機能することがわかった。
関連論文リスト
- Efficient Over-parameterized Matrix Sensing from Noisy Measurements via Alternating Preconditioned Gradient Descent [17.73720530889677]
行列センシング問題の収束を早めるためのプレコンディショニング手法が提案されている。
本稿では,2因子パラメータを交互に更新するAPGDアルゴリズムを提案する。
理論的には、任意の乱数から始まる線形速度で APGD が準最適収束を達成することを証明している。
論文 参考訳（メタデータ） (2025-02-01T15:44:39Z) - Stochastic Optimization for Non-convex Problem with Inexact Hessian
Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。
TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文 参考訳（メタデータ） (2023-10-18T10:29:58Z) - Asymmetric matrix sensing by gradient descent with small random
initialization [0.8611782340880084]
いくつかの線形測定値から低ランク行列を再構成する問題について検討する。
私たちの重要な貢献は、$texted gradient flow$と呼ぶ連続的な勾配流方程式の導入です。
論文 参考訳（メタデータ） (2023-09-04T20:23:35Z) - Constrained Optimization via Exact Augmented Lagrangian and Randomized
Iterative Sketching [55.28394191394675]
等式制約付き非線形非IBS最適化問題に対する適応的不正確なニュートン法を開発した。
ベンチマーク非線形問題,LVMのデータによる制約付きロジスティック回帰,PDE制約問題において,本手法の優れた性能を示す。
論文 参考訳（メタデータ） (2023-05-28T06:33:37Z) - Neural incomplete factorization: learning preconditioners for the conjugate gradient method [2.899792823251184]
我々は、効率的なプレコンディショナーの生成を加速するためのデータ駆動型アプローチを開発する。
一般的に手動のプリコンディショナーをグラフニューラルネットワークの出力に置き換える。
本手法は, 行列の不完全分解を発生させ, 神経不完全分解(NeuralIF)と呼ばれる。
論文 参考訳（メタデータ） (2023-05-25T11:45:46Z) - Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。
我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。
MRP のサブクラスに対する minimax の下位境界を証明する。
論文 参考訳（メタデータ） (2021-09-24T14:48:20Z) - Reducing the Variance of Gaussian Process Hyperparameter Optimization
with Preconditioning [54.01682318834995]
プレコンディショニングは、行列ベクトル乗算を含む反復的な方法にとって非常に効果的なステップである。
プレコンディショニングには、これまで検討されていなかった付加的なメリットがあることを実証する。
基本的に無視可能なコストで、同時に分散を低減することができる。
論文 参考訳（メタデータ） (2021-07-01T06:43:11Z) - Exact Linear Convergence Rate Analysis for Low-Rank Symmetric Matrix
Completion via Gradient Descent [22.851500417035947]
因数分解に基づく勾配降下は、因数分解行列の完備化を解くためのスケーラブルで効率的なアルゴリズムである。
勾配勾配降下は, 地球自然問題の解を推定するために, 高速収束を楽しむことを示す。
論文 参考訳（メタデータ） (2021-02-04T03:41:54Z) - Understanding Implicit Regularization in Over-Parameterized Single Index
Model [55.41685740015095]
我々は高次元単一インデックスモデルのための正規化自由アルゴリズムを設計する。
暗黙正則化現象の理論的保証を提供する。
論文 参考訳（メタデータ） (2020-07-16T13:27:47Z) - Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled
Gradient Descent [34.0533596121548]
低ランク行列推定は凸問題を収束させ、信号処理、機械学習、画像科学に多くの応用を見出す。
低ランク行列の個数の観点から,ScaledGDが最良となることを示す。
我々の分析は、低ランク勾配降下に類似した一般損失にも適用できる。
論文 参考訳（メタデータ） (2020-05-18T17:17:16Z) - Implicit differentiation of Lasso-type models for hyperparameter
optimization [82.73138686390514]
ラッソ型問題に適した行列逆転のない効率的な暗黙微分アルゴリズムを提案する。
提案手法は,解の空間性を利用して高次元データにスケールする。
論文 参考訳（メタデータ） (2020-02-20T18:43:42Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。