論文の概要: Implicit Regularization of Sub-Gradient Method in Robust Matrix Recovery: Don't be Afraid of Outliers

• arxiv url: http://arxiv.org/abs/2102.02969v1
• Date: Fri, 5 Feb 2021 02:52:00 GMT
• ステータス: 処理完了
• システム内更新日: 2021-02-08 14:49:44.749869
• Title: Implicit Regularization of Sub-Gradient Method in Robust Matrix Recovery: Don't be Afraid of Outliers
• Title（参考訳）: ロバスト行列回復におけるサブグラデーション法の暗黙的正規化:アウトプライヤを脅かすな
• Authors: Jianhao Ma and Salar Fattahi
• Abstract要約: 簡単な部分勾配法が真の低ランク解に効率的に収束することを示す。 また,本手法のロバスト性を証明するために,シグナ-RIPと呼ばれる制限等尺性の概念を新たに構築する。
• 参考スコア（独自算出の注目度）: 6.320141734801679
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: It is well-known that simple short-sighted algorithms, such as gradient descent, generalize well in the over-parameterized learning tasks, due to their implicit regularization. However, it is unknown whether the implicit regularization of these algorithms can be extended to robust learning tasks, where a subset of samples may be grossly corrupted with noise. In this work, we provide a positive answer to this question in the context of robust matrix recovery problem. In particular, we consider the problem of recovering a low-rank matrix from a number of linear measurements, where a subset of measurements are corrupted with large noise. We show that a simple sub-gradient method converges to the true low-rank solution efficiently, when it is applied to the over-parameterized l1-loss function without any explicit regularization or rank constraint. Moreover, by building upon a new notion of restricted isometry property, called sign-RIP, we prove the robustness of the sub-gradient method against outliers in the over-parameterized regime. In particular, we show that, with Gaussian measurements, the sub-gradient method is guaranteed to converge to the true low-rank solution, even if an arbitrary fraction of the measurements are grossly corrupted with noise.
• Abstract（参考訳）: 勾配降下のような単純な短視野アルゴリズムは、暗黙の正規化のために、過パラメータ化された学習タスクでよく一般化されることが知られている。 しかし、これらのアルゴリズムの暗黙的な正規化が頑健な学習タスクにまで拡張できるかどうかは不明である。 本研究では,ロバスト行列回復問題の文脈において,この問題に対する肯定的な回答を提供する。 特に、いくつかの線形測定から低ランク行列を回復する問題を検討し、その場合、測定のサブセットは大きなノイズで破損する。 過パラメータ化 l1-ロス関数に適用した場合, 厳密な正規化や階数制約を伴わずに, 単純な部分勾配法が真の低階解に効率的に収束することを示す。 さらに、Sign-RIPと呼ばれる制限アイソメトリー特性の新しい概念を構築することによって、オーバーパラメータ化された体制における外れ値に対するサブグラデーション手法の堅牢性を証明する。 特に, ガウス計測では, 任意の割合がノイズで完全に崩壊した場合でも, 下位勾配法は真の低ランク解に収束することが保証されている。

関連論文リスト

• Riemannian stochastic optimization methods avoid strict saddle points [68.80251170757647]
  研究中のポリシーは、確率 1 の厳密なサドル点/部分多様体を避けていることを示す。 この結果は、アルゴリズムの極限状態が局所最小値にしかならないことを示すため、重要な正当性チェックを提供する。
  論文  参考訳（メタデータ） (2023-11-04T11:12:24Z)
• Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learning [53.445068584013896]
  低ランク構造を持つ強化学習(RL)における行列推定問題について検討した。 低ランク帯では、回収される行列は期待される腕の報酬を指定し、低ランクマルコフ決定プロセス(MDP)では、例えばMDPの遷移カーネルを特徴付ける。 簡単なスペクトルベースの行列推定手法は,行列の特異部分空間を効率よく復元し,ほぼ最小の入力誤差を示すことを示す。
  論文  参考訳（メタデータ） (2023-10-10T17:06:41Z)
• Robust online joint state/input/parameter estimation of linear systems [0.0]
  本稿では,線形システムの状態,入力,パラメータをオンライン形式で共同で推定する手法を提案する。 この方法は、非ガウス雑音や外れ値で劣化した測定のために特別に設計されている。
  論文  参考訳（メタデータ） (2022-04-12T09:41:28Z)
• 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)
• Rank Overspecified Robust Matrix Recovery: Subgradient Method and Exact Recovery [37.05862765171643]
  我々は、ランクに関する事前の知識を持たない低ランク行列のロバストな分解を考える。 本稿では,行列のサイズを小さくする設計により,過度に最適化されたモデルにおける過度な適合を効果的に防止できることを示す。
  論文  参考訳（メタデータ） (2021-09-23T05:54:46Z)
• Solving weakly supervised regression problem using low-rank manifold regularization [77.34726150561087]
  我々は弱い教師付き回帰問題を解く。 weakly"の下では、いくつかのトレーニングポイントではラベルが知られ、未知のものもあれば、無作為なノイズの存在やリソースの欠如などの理由によって不確かであることが分かっています。 数値的な節ではモンテカルロモデルを用いて提案手法を人工と実のデータセットに適用した。
  論文  参考訳（メタデータ） (2021-04-13T23:21:01Z)
• Dimension Free Generalization Bounds for Non Linear Metric Learning [61.193693608166114]
  我々はスパース体制と非スパース体制という2つの体制に対して一様一般化境界を提供する。 解の異なる新しい性質を頼りにすることで、次元自由一般化保証を提供することができることを示す。
  論文  参考訳（メタデータ） (2021-02-07T14:47:00Z)
• Low-Rank Matrix Recovery with Scaled Subgradient Methods: Fast and Robust Convergence Without the Condition Number [34.0533596121548]
  データ科学における多くの問題は、高度に不完全で、時には腐敗した観測から低いランクを推定するものとして扱われる。 1つの一般的なアプローチは行列分解に頼り、低ランク行列因子は滑らかな損失に対して一階法によって最適化される。
  論文  参考訳（メタデータ） (2020-10-26T06:21:14Z)
• Learning Mixtures of Low-Rank Models [89.39877968115833]
  低ランクモデルの計算混合を学習する問題について検討する。 ほぼ最適サンプルを用いて未知の行列を復元することが保証されるアルゴリズムを開発する。 さらに,提案アルゴリズムはランダムノイズに対して確実に安定である。
  論文  参考訳（メタデータ） (2020-09-23T17:53:48Z)
• Robust Compressed Sensing using Generative Models [98.64228459705859]
  本稿では,Median-of-Means (MOM) にヒントを得たアルゴリズムを提案する。 我々のアルゴリズムは、外れ値が存在する場合でも、重み付きデータの回復を保証する。
  論文  参考訳（メタデータ） (2020-06-16T19:07:41Z)

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

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