論文の概要: Global Convergence of Sub-gradient Method for Robust Matrix Recovery: Small Initialization, Noisy Measurements, and Over-parameterization

• arxiv url: http://arxiv.org/abs/2202.08788v1
• Date: Thu, 17 Feb 2022 17:50:04 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-18 14:59:20.088334
• Title: Global Convergence of Sub-gradient Method for Robust Matrix Recovery: Small Initialization, Noisy Measurements, and Over-parameterization
• Title（参考訳）: ロバスト行列回復のための下位勾配法のグローバル収束:小さな初期化、雑音測定、過度パラメータ化
• Authors: Jianhao Ma and Salar Fattahi
• Abstract要約: サブグラディエント法(Sub-gradient method, SubGM)は, 限られた測定値から低ランク行列を復元するために用いられる。 我々は、SubGMが任意の大きさの高密度ノイズ値の下でも、真の解に収束することを示す。
• 参考スコア（独自算出の注目度）: 4.7464518249313805
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this work, we study the performance of sub-gradient method (SubGM) on a natural nonconvex and nonsmooth formulation of low-rank matrix recovery with $\ell_1$-loss, where the goal is to recover a low-rank matrix from a limited number of measurements, a subset of which may be grossly corrupted with noise. We study a scenario where the rank of the true solution is unknown and over-estimated instead. The over-estimation of the rank gives rise to an over-parameterized model in which there are more degrees of freedom than needed. Such over-parameterization may lead to overfitting, or adversely affect the performance of the algorithm. We prove that a simple SubGM with small initialization is agnostic to both over-parameterization and noise in the measurements. In particular, we show that small initialization nullifies the effect of over-parameterization on the performance of SubGM, leading to an exponential improvement in its convergence rate. Moreover, we provide the first unifying framework for analyzing the behavior of SubGM under both outlier and Gaussian noise models, showing that SubGM converges to the true solution, even under arbitrarily large and arbitrarily dense noise values, and--perhaps surprisingly--even if the globally optimal solutions do not correspond to the ground truth. At the core of our results is a robust variant of restricted isometry property, called Sign-RIP, which controls the deviation of the sub-differential of the $\ell_1$-loss from that of an ideal, expected loss. As a byproduct of our results, we consider a subclass of robust low-rank matrix recovery with Gaussian measurements, and show that the number of required samples to guarantee the global convergence of SubGM is independent of the over-parameterized rank.
• Abstract（参考訳）: 本研究では,低階行列回復の自然な非凸に対するサブ段階法(SubGM)の性能と,低階行列回復を$\ell_1$-lossで定式化する手法について検討する。 真の解のランクが未知であり、代わりに過大評価されるシナリオを研究する。 ランクの過度な推定は、必要以上の自由度を持つ過度なパラメータ化されたモデルをもたらす。 このような過度パラメータ化はアルゴリズムの性能に過度に適合するか、悪影響を及ぼす可能性がある。 初期化が小さい単純なsubgmは、測定値の過パラメータ化とノイズの両方に無依存であることが証明される。 特に, 極小初期化は, SubGMの性能に及ぼす過パラメータ化の影響を無効化し, 収束率を指数的に向上させることを示した。 さらに, 外部雑音モデルとガウス雑音モデルの両方の下でのSubGMの挙動を解析するための最初の統一フレームワークを提案し, 任意に大きく, 任意の密度の雑音値の下でもSubGMが真の解に収束することを示した。 我々の結果の核となるのは、Sign-RIPと呼ばれる制限された等距離特性の頑健な変種であり、これは理想的な期待損失から$\ell_1$-lossの偏差を制御している。 以上の結果の副産物として,ガウス計測によるロバストな低ランク行列復元のサブクラスを考察し,subgmのグローバル収束を保証するために必要なサンプル数が過パラメータのランクとは無関係であることを示す。

関連論文リスト

• Fundamental limits of Non-Linear Low-Rank Matrix Estimation [18.455890316339595]
  ベイズ最適性能は、有効前のガウスモデルによって特徴づけられる。 信号を正確に再構成するためには、Nfrac 12 (1-1/k_F)$として増加する信号対雑音比が必要であり、$k_F$は関数の最初のゼロでないフィッシャー情報係数である。
  論文  参考訳（メタデータ） (2024-03-07T05:26:52Z)
• Provably Accelerating Ill-Conditioned Low-rank Estimation via Scaled Gradient Descent, Even with Overparameterization [48.65416821017865]
  この章では、スケールドグラデーション(ScaledGD)と呼ばれる新しいアルゴリズムアプローチを紹介します。 低ランク物体の条件数に依存しない定数速度で直線的に収束する。 様々なタスクに対して、勾配降下の低い摂動コストを維持できる。
  論文  参考訳（メタデータ） (2023-10-09T21:16:57Z)
• Rank Overspecified Robust Matrix Recovery: Subgradient Method and Exact Recovery [37.05862765171643]
  我々は、ランクに関する事前の知識を持たない低ランク行列のロバストな分解を考える。 本稿では,行列のサイズを小さくする設計により,過度に最適化されたモデルにおける過度な適合を効果的に防止できることを示す。
  論文  参考訳（メタデータ） (2021-09-23T05:54:46Z)
• Near-Optimal High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [63.304196997102494]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 既存の非滑らか凸最適化法は、負のパワーまたは対数的な信頼度に依存する境界の複雑さを持つ。 クリッピングを用いた2つの勾配法に対して, 新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• Implicit Regularization of Sub-Gradient Method in Robust Matrix Recovery: Don't be Afraid of Outliers [6.320141734801679]
  簡単な部分勾配法が真の低ランク解に効率的に収束することを示す。 また,本手法のロバスト性を証明するために,シグナ-RIPと呼ばれる制限等尺性の概念を新たに構築する。
  論文  参考訳（メタデータ） (2021-02-05T02:52:00Z)
• 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)
• Understanding Implicit Regularization in Over-Parameterized Single Index Model [55.41685740015095]
  我々は高次元単一インデックスモデルのための正規化自由アルゴリズムを設計する。 暗黙正則化現象の理論的保証を提供する。
  論文  参考訳（メタデータ） (2020-07-16T13:27:47Z)
• Robust Compressed Sensing using Generative Models [98.64228459705859]
  本稿では,Median-of-Means (MOM) にヒントを得たアルゴリズムを提案する。 我々のアルゴリズムは、外れ値が存在する場合でも、重み付きデータの回復を保証する。
  論文  参考訳（メタデータ） (2020-06-16T19:07:41Z)
• Approximation Schemes for ReLU Regression [80.33702497406632]
  我々はReLU回帰の根本的な問題を考察する。 目的は、未知の分布から引き出された2乗損失に対して、最も適したReLUを出力することである。
  論文  参考訳（メタデータ） (2020-05-26T16:26:17Z)

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

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