論文の概要: Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction

• arxiv url: http://arxiv.org/abs/2106.15013v1
• Date: Mon, 28 Jun 2021 22:52:39 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-30 15:31:38.610339
• Title: Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction
• Title（参考訳）: スペクトル学習に類似した小さなランダム初期化:過パラメータ化低ランク行列再構成の最適化と一般化保証
• Authors: Dominik St\"oger and Mahdi Soltanolkotabi
• Abstract要約: 本稿では,小さなランダム初期化が完全には理解されていないことを示す。 我々は、小さな乱数行列から勾配を再構成し、低い乱数行列から最適勾配に類似した解を求める。
• 参考スコア（独自算出の注目度）: 35.585697639325105
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recently there has been significant theoretical progress on understanding the convergence and generalization of gradient-based methods on nonconvex losses with overparameterized models. Nevertheless, many aspects of optimization and generalization and in particular the critical role of small random initialization are not fully understood. In this paper, we take a step towards demystifying this role by proving that small random initialization followed by a few iterations of gradient descent behaves akin to popular spectral methods. We also show that this implicit spectral bias from small random initialization, which is provably more prominent for overparameterized models, also puts the gradient descent iterations on a particular trajectory towards solutions that are not only globally optimal but also generalize well. Concretely, we focus on the problem of reconstructing a low-rank matrix from a few measurements via a natural nonconvex formulation. In this setting, we show that the trajectory of the gradient descent iterations from small random initialization can be approximately decomposed into three phases: (I) a spectral or alignment phase where we show that that the iterates have an implicit spectral bias akin to spectral initialization allowing us to show that at the end of this phase the column space of the iterates and the underlying low-rank matrix are sufficiently aligned, (II) a saddle avoidance/refinement phase where we show that the trajectory of the gradient iterates moves away from certain degenerate saddle points, and (III) a local refinement phase where we show that after avoiding the saddles the iterates converge quickly to the underlying low-rank matrix. Underlying our analysis are insights for the analysis of overparameterized nonconvex optimization schemes that may have implications for computational problems beyond low-rank reconstruction.
• Abstract（参考訳）: 近年、過パラメータモデルによる非凸損失に対する勾配に基づく手法の収束と一般化の理解に関する理論的な進歩が著しい。 それでも、最適化と一般化の多くの側面、特に小さなランダム初期化の重要な役割は、完全には理解されていない。 本稿では、この役割をデミスティフィケートするために、小さなランダム初期化と数回の勾配降下の繰り返しが一般的なスペクトル法に類似していることを証明する。 また,この非ランダム初期化による暗黙のスペクトルバイアスは,過パラメータモデルでは顕著に顕著であり,勾配降下の反復は,グローバルに最適であるだけでなく,よく一般化する解へと向けられることを示した。 具体的には, 自然非凸定式化による数種類の測定値から低ランク行列を再構成する問題に着目する。 In this setting, we show that the trajectory of the gradient descent iterations from small random initialization can be approximately decomposed into three phases: (I) a spectral or alignment phase where we show that that the iterates have an implicit spectral bias akin to spectral initialization allowing us to show that at the end of this phase the column space of the iterates and the underlying low-rank matrix are sufficiently aligned, (II) a saddle avoidance/refinement phase where we show that the trajectory of the gradient iterates moves away from certain degenerate saddle points, and (III) a local refinement phase where we show that after avoiding the saddles the iterates converge quickly to the underlying low-rank matrix. 我々の分析は、低階再構成以上の計算問題に影響を及ぼす可能性のある、過度にパラメータ化された非凸最適化スキームの分析のための洞察である。

関連論文リスト

• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。 本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
  論文  参考訳（メタデータ） (2024-06-28T02:56:22Z)
• Symmetric Matrix Completion with ReLU Sampling [15.095194065320987]
  エントリー依存サンプリングによる対称正半定値低ランク行列補完(MC)の問題について検討する。 特に、静止点のみを観測する修正線形単位(ReLU)サンプリングについて検討する。
  論文  参考訳（メタデータ） (2024-06-09T15:14:53Z)
• Riemannian stochastic optimization methods avoid strict saddle points [68.80251170757647]
  研究中のポリシーは、確率 1 の厳密なサドル点/部分多様体を避けていることを示す。 この結果は、アルゴリズムの極限状態が局所最小値にしかならないことを示すため、重要な正当性チェックを提供する。
  論文  参考訳（メタデータ） (2023-11-04T11:12:24Z)
• Provably Accelerating Ill-Conditioned Low-rank Estimation via Scaled Gradient Descent, Even with Overparameterization [48.65416821017865]
  この章では、スケールドグラデーション(ScaledGD)と呼ばれる新しいアルゴリズムアプローチを紹介します。 低ランク物体の条件数に依存しない定数速度で直線的に収束する。 様々なタスクに対して、勾配降下の低い摂動コストを維持できる。
  論文  参考訳（メタデータ） (2023-10-09T21:16:57Z)
• Curvature-Independent Last-Iterate Convergence for Games on Riemannian Manifolds [77.4346324549323]
  本研究では, 多様体の曲率に依存しないステップサイズが, 曲率非依存かつ直線的最終点収束率を達成することを示す。 我々の知る限りでは、曲率非依存率や/または最終点収束の可能性はこれまでに検討されていない。
  論文  参考訳（メタデータ） (2023-06-29T01:20:44Z)
• The Inductive Bias of Flatness Regularization for Deep Matrix Factorization [58.851514333119255]
  この研究は、ディープ線形ネットワークにおけるヘッセン解の最小トレースの帰納バイアスを理解するための第一歩となる。 測定値の標準等尺性(RIP)が1より大きいすべての深さについて、ヘッセンのトレースを最小化することは、対応する終端行列パラメータのシャッテン 1-ノルムを最小化するのとほぼ同値であることを示す。
  論文  参考訳（メタデータ） (2023-06-22T23:14:57Z)
• Implicit Balancing and Regularization: Generalization and Convergence Guarantees for Overparameterized Asymmetric Matrix Sensing [28.77440901439686]
  最近の一連の論文は、非ランダムな正準決定(PSD)行列センシング問題に対して、この役割を一般化し始めている。 本稿では,小さなランダムな測定から得られる勾配降下の軌跡が,どちらも地球規模で良好である解へと移動することを示す。
  論文  参考訳（メタデータ） (2023-03-24T19:05:52Z)
• Algorithmic Regularization in Model-free Overparametrized Asymmetric Matrix Factorization [16.325663190517773]
  我々は、任意の過パラメータ化を持つ自然な非定式化の下で、非対称な分解問題を考察する。 観測された行列に対して最高の低ランク近似を生成する。
  論文  参考訳（メタデータ） (2022-03-06T00:07:53Z)
• 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)

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

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