論文の概要: On the Convergence of Stochastic Gradient Descent with Low-Rank Projections for Convex Low-Rank Matrix Problems

• arxiv url: http://arxiv.org/abs/2001.11668v2
• Date: Sun, 14 Jun 2020 14:26:36 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-05 06:22:15.671693
• Title: On the Convergence of Stochastic Gradient Descent with Low-Rank Projections for Convex Low-Rank Matrix Problems
• Title（参考訳）: 凸低ランク行列問題に対する低ランク射影を伴う確率勾配の収束性について
• Authors: Dan Garber
• Abstract要約: 本研究では, 凸緩和に有効な凸最適化問題の解法として, SGD (Gradient Descent) の利用を再検討する。 我々は,SGDが低ランク行列回復問題の大規模凸緩和に実際に適用可能であることを示した。
• 参考スコア（独自算出の注目度）: 19.24470467199451
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We revisit the use of Stochastic Gradient Descent (SGD) for solving convex optimization problems that serve as highly popular convex relaxations for many important low-rank matrix recovery problems such as \textit{matrix completion}, \textit{phase retrieval}, and more. The computational limitation of applying SGD to solving these relaxations in large-scale is the need to compute a potentially high-rank singular value decomposition (SVD) on each iteration in order to enforce the low-rank-promoting constraint. We begin by considering a simple and natural sufficient condition so that these relaxations indeed admit low-rank solutions. This condition is also necessary for a certain notion of low-rank-robustness to hold. Our main result shows that under this condition which involves the eigenvalues of the gradient vector at optimal points, SGD with mini-batches, when initialized with a "warm-start" point, produces iterates that are low-rank with high probability, and hence only a low-rank SVD computation is required on each iteration. This suggests that SGD may indeed be practically applicable to solving large-scale convex relaxations of low-rank matrix recovery problems. Our theoretical results are accompanied with supporting preliminary empirical evidence. As a side benefit, our analysis is quite simple and short.
• Abstract（参考訳）: 確率的勾配降下 (sgd) を用いて, \textit{matrix completion} や \textit{phase retrieval} などの多くの重要な低ランク行列回復問題に対して,高人気な凸緩和となる凸最適化問題を解く。 これらの緩和を大規模に解くためにSGDを適用することの計算上の限界は、低ランク化の制約を強制するために、各イテレーションで潜在的に高ランクな特異値分解(SVD)を計算する必要があることである。 まず、これらの緩和が実際に低ランク解を許容するように、単純で自然な状態を考える。 この条件は、保持する低ランクのロバスト性の概念にも必要である。 この条件下では、最適点における勾配ベクトルの固有値を含むSGDが「ウォームスタート」点で初期化されると、高い確率で低ランクの反復を生成するため、各イテレーションで低ランクのSVD計算が必要とされる。 これは、SGDが低ランク行列回復問題の大規模凸緩和に実際に適用可能であることを示唆している。 我々の理論的結果には予備的な証拠が伴っている。 副次的な利点として、私たちの分析は非常に単純で短いです。

関連論文リスト

• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。 本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
  論文  参考訳（メタデータ） (2024-06-28T02:56:22Z)
• Provably Accelerating Ill-Conditioned Low-rank Estimation via Scaled Gradient Descent, Even with Overparameterization [48.65416821017865]
  この章では、スケールドグラデーション(ScaledGD)と呼ばれる新しいアルゴリズムアプローチを紹介します。 低ランク物体の条件数に依存しない定数速度で直線的に収束する。 様々なタスクに対して、勾配降下の低い摂動コストを維持できる。
  論文  参考訳（メタデータ） (2023-10-09T21:16:57Z)
• Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization [61.26619639722804]
  滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。 提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
  論文  参考訳（メタデータ） (2022-02-26T19:10:48Z)
• Low-Rank Extragradient Method for Nonsmooth and Low-Rank Matrix Optimization Problems [19.930021245647705]
  低ランクおよび非滑らかな行列最適化問題は統計学や機械学習における多くの基本的なタスクを捉えている。 本稿では,このような問題に対する標準凸緩和について考察する。 テキストテキストラグラディエント法は,1イテレーションあたり2つのテキスト低ランクSVDしか必要とせず,$O (1/t)$のレートで最適解に収束することを示す。
  論文  参考訳（メタデータ） (2022-02-08T17:47:40Z)
• Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems [98.34292831923335]
  オンライン相関解析の問題から,emphStochastic Scaled-Gradient Descent (SSD)アルゴリズムを提案する。 我々はこれらのアイデアをオンライン相関解析に適用し、局所収束率を正規性に比例した最適な1時間スケールのアルゴリズムを初めて導いた。
  論文  参考訳（メタデータ） (2021-12-29T18:46:52Z)
• Provable Low Rank Plus Sparse Matrix Separation Via Nonconvex Regularizers [0.0]
  本稿では,低ランク行列やスパースベクトルをある種の測定値から回収しようとする大問題について考察する。 凸偏差推定器に基づく手法は、ランクや空間の偏りに悩まされているが、非正則化器を用いる。 本稿では,このような問題に適用した近似交互バイアス降下アルゴリズムの新たな解析法を提案する。
  論文  参考訳（メタデータ） (2021-09-26T22:09:42Z)
• Low-rank matrix recovery with non-quadratic loss: projected gradient method and regularity projection oracle [23.84884127542249]
  低ランク行列回復の既往の結果は2次損失に大きく影響した。 非二次的損失を伴う証明可能な低ランク回復における重要な要素が正規性予測であることを示す。
  論文  参考訳（メタデータ） (2020-08-31T17:56:04Z)
• A Scalable, Adaptive and Sound Nonconvex Regularizer for Low-rank Matrix Completion [60.52730146391456]
  そこで我々は,適応的かつ音質の高い"核フロベニウスノルム"と呼ばれる新しい非スケーラブルな低ランク正規化器を提案する。 特異値の計算をバイパスし、アルゴリズムによる高速な最適化を可能にする。 既存の行列学習手法では最速でありながら、最先端の回復性能が得られる。
  論文  参考訳（メタデータ） (2020-08-14T18:47:58Z)
• Approximation Schemes for ReLU Regression [80.33702497406632]
  我々はReLU回帰の根本的な問題を考察する。 目的は、未知の分布から引き出された2乗損失に対して、最も適したReLUを出力することである。
  論文  参考訳（メタデータ） (2020-05-26T16:26:17Z)
• Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent [34.0533596121548]
  低ランク行列推定は凸問題を収束させ、信号処理、機械学習、画像科学に多くの応用を見出す。 低ランク行列の個数の観点から,ScaledGDが最良となることを示す。 我々の分析は、低ランク勾配降下に類似した一般損失にも適用できる。
  論文  参考訳（メタデータ） (2020-05-18T17:17:16Z)

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

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