論文の概要: Provably Accelerating Ill-Conditioned Low-rank Estimation via Scaled Gradient Descent, Even with Overparameterization

• arxiv url: http://arxiv.org/abs/2310.06159v1
• Date: Mon, 9 Oct 2023 21:16:57 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-11 21:39:25.077978
• Title: Provably Accelerating Ill-Conditioned Low-rank Estimation via Scaled Gradient Descent, Even with Overparameterization
• Title（参考訳）: 過パラメータ化でさえも、スケールドグラディエントDescentによるIll-Conditioned Low-rank Estimationの確率的高速化
• Authors: Cong Ma, Xingyu Xu, Tian Tong, Yuejie Chi
• Abstract要約: この章では、スケールドグラデーション(ScaledGD)と呼ばれる新しいアルゴリズムアプローチを紹介します。 低ランク物体の条件数に依存しない定数速度で直線的に収束する。 様々なタスクに対して、勾配降下の低い摂動コストを維持できる。
• 参考スコア（独自算出の注目度）: 48.65416821017865
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Many problems encountered in science and engineering can be formulated as estimating a low-rank object (e.g., matrices and tensors) from incomplete, and possibly corrupted, linear measurements. Through the lens of matrix and tensor factorization, one of the most popular approaches is to employ simple iterative algorithms such as gradient descent (GD) to recover the low-rank factors directly, which allow for small memory and computation footprints. However, the convergence rate of GD depends linearly, and sometimes even quadratically, on the condition number of the low-rank object, and therefore, GD slows down painstakingly when the problem is ill-conditioned. This chapter introduces a new algorithmic approach, dubbed scaled gradient descent (ScaledGD), that provably converges linearly at a constant rate independent of the condition number of the low-rank object, while maintaining the low per-iteration cost of gradient descent for a variety of tasks including sensing, robust principal component analysis and completion. In addition, ScaledGD continues to admit fast global convergence to the minimax-optimal solution, again almost independent of the condition number, from a small random initialization when the rank is over-specified in the presence of Gaussian noise. In total, ScaledGD highlights the power of appropriate preconditioning in accelerating nonconvex statistical estimation, where the iteration-varying preconditioners promote desirable invariance properties of the trajectory with respect to the symmetry in low-rank factorization without hurting generalization.
• Abstract（参考訳）: 科学や工学で遭遇する多くの問題は、不完全でおそらくは破損した線形測定から低ランクな物体(行列やテンソルなど)を推定するものとして定式化することができる。 行列とテンソル因子化のレンズを通じて、最も一般的なアプローチの1つは、勾配降下(GD)のような単純な反復アルゴリズムを用いて、低ランク因子を直接回収することで、メモリと計算のフットプリントを小さくすることができる。 しかしながら、gdの収束速度は、低ランク対象の条件数に線形に依存し、時には二次的にも依存するので、問題に悪条件がある場合、gdは痛むのを遅くする。 本章では,低ランク対象の条件数に依存しない一定速度で線形収束し,センサ,ロバストな主成分分析,完了を含む様々なタスクに対して,勾配降下の低着氷コストを維持しながら,スケールド勾配降下(Scaled gradient descent,ScaledGD)と呼ばれる新しいアルゴリズム的アプローチを紹介する。 さらに、スケールドGD は、ガウスノイズの存在下でランクが過剰に特定されたときの小さなランダム初期化から、条件数からほぼ独立なミニマックス最適解への高速な大域収束を認め続けている。 総じて、scaledgdは、非凸統計推定の加速における適切な事前条件付けの力を強調しており、反復変動前条件器は、一般化を損なうことなく、低ランク因子分解の対称性に関して軌道の望ましい不変性を促進する。

関連論文リスト

• Max-affine regression via first-order methods [7.12511675782289]
  最大アフィンモデルは信号処理と統計学の応用においてユビキタスに現れる。 最大アフィン回帰に対する勾配降下(GD)とミニバッチ勾配降下(SGD)の非漸近収束解析を行った。
  論文  参考訳（メタデータ） (2023-08-15T23:46:44Z)
• Implicit Bias of Gradient Descent for Logistic Regression at the Edge of Stability [69.01076284478151]
  機械学習の最適化において、勾配降下(GD)はしばしば安定性の端(EoS)で動く 本稿では,EoS系における線形分離可能なデータに対するロジスティック回帰のための定数段差GDの収束と暗黙バイアスについて検討する。
  論文  参考訳（メタデータ） (2023-05-19T16:24:47Z)
• Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization [61.26619639722804]
  滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。 提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
  論文  参考訳（メタデータ） (2022-02-26T19:10:48Z)
• Global Convergence of Sub-gradient Method for Robust Matrix Recovery: Small Initialization, Noisy Measurements, and Over-parameterization [4.7464518249313805]
  サブグラディエント法(Sub-gradient method, SubGM)は, 限られた測定値から低ランク行列を復元するために用いられる。 我々は、SubGMが任意の大きさの高密度ノイズ値の下でも、真の解に収束することを示す。
  論文  参考訳（メタデータ） (2022-02-17T17:50:04Z)
• Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems [98.34292831923335]
  オンライン相関解析の問題から,emphStochastic Scaled-Gradient Descent (SSD)アルゴリズムを提案する。 我々はこれらのアイデアをオンライン相関解析に適用し、局所収束率を正規性に比例した最適な1時間スケールのアルゴリズムを初めて導いた。
  論文  参考訳（メタデータ） (2021-12-29T18:46:52Z)
• On Asymptotic Linear Convergence of Projected Gradient Descent for Constrained Least Squares [22.851500417035947]
  この写本は、制約最小二乗の文脈における射影勾配降下の解析のための統一的な枠組みを提示する。 本稿では,PGDの収束解析のレシピを提示し,このレシピを4つの基本的な問題に応用して実証する。
  論文  参考訳（メタデータ） (2021-12-22T09:49:51Z)
• Differentiable Annealed Importance Sampling and the Perils of Gradient Noise [68.44523807580438]
  Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。 差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。 我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
  論文  参考訳（メタデータ） (2021-07-21T17:10:14Z)
• Benign Overfitting of Constant-Stepsize SGD for Linear Regression [122.70478935214128]
  帰納バイアスは 経験的に過剰フィットを防げる中心的存在です この研究は、この問題を最も基本的な設定として考慮している: 線形回帰に対する定数ステップサイズ SGD。 我々は、(正規化されていない)SGDで得られるアルゴリズム正則化と、通常の最小二乗よりも多くの顕著な違いを反映する。
  論文  参考訳（メタデータ） (2021-03-23T17:15:53Z)
• Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent [34.0533596121548]
  低ランク行列推定は凸問題を収束させ、信号処理、機械学習、画像科学に多くの応用を見出す。 低ランク行列の個数の観点から,ScaledGDが最良となることを示す。 我々の分析は、低ランク勾配降下に類似した一般損失にも適用できる。
  論文  参考訳（メタデータ） (2020-05-18T17:17:16Z)
• On the Convergence of Stochastic Gradient Descent with Low-Rank Projections for Convex Low-Rank Matrix Problems [19.24470467199451]
  本研究では, 凸緩和に有効な凸最適化問題の解法として, SGD (Gradient Descent) の利用を再検討する。 我々は,SGDが低ランク行列回復問題の大規模凸緩和に実際に適用可能であることを示した。
  論文  参考訳（メタデータ） (2020-01-31T06:00:34Z)

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

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