論文の概要: Low-Rank Matrix Recovery with Scaled Subgradient Methods: Fast and Robust Convergence Without the Condition Number

• arxiv url: http://arxiv.org/abs/2010.13364v2
• Date: Thu, 22 Apr 2021 15:09:42 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-02 18:58:45.353922
• Title: Low-Rank Matrix Recovery with Scaled Subgradient Methods: Fast and Robust Convergence Without the Condition Number
• Title（参考訳）: スケール劣化法による低ランク行列回復:条件数のない高速・ロバスト収束
• Authors: Tian Tong, Cong Ma, Yuejie Chi
• Abstract要約: データ科学における多くの問題は、高度に不完全で、時には腐敗した観測から低いランクを推定するものとして扱われる。 1つの一般的なアプローチは行列分解に頼り、低ランク行列因子は滑らかな損失に対して一階法によって最適化される。
• 参考スコア（独自算出の注目度）: 34.0533596121548
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many problems in data science can be treated as estimating a low-rank matrix from highly incomplete, sometimes even corrupted, observations. One popular approach is to resort to matrix factorization, where the low-rank matrix factors are optimized via first-order methods over a smooth loss function, such as the residual sum of squares. While tremendous progresses have been made in recent years, the natural smooth formulation suffers from two sources of ill-conditioning, where the iteration complexity of gradient descent scales poorly both with the dimension as well as the condition number of the low-rank matrix. Moreover, the smooth formulation is not robust to corruptions. In this paper, we propose scaled subgradient methods to minimize a family of nonsmooth and nonconvex formulations -- in particular, the residual sum of absolute errors -- which is guaranteed to converge at a fast rate that is almost dimension-free and independent of the condition number, even in the presence of corruptions. We illustrate the effectiveness of our approach when the observation operator satisfies certain mixed-norm restricted isometry properties, and derive state-of-the-art performance guarantees for a variety of problems such as robust low-rank matrix sensing and quadratic sampling.
• Abstract（参考訳）: データサイエンスにおける多くの問題は、高度に不完全で時には腐敗した観測から低ランク行列を推定することとして扱うことができる。 1つの一般的なアプローチは行列分解に頼り、低ランク行列因子は正方形の残余和のような滑らかな損失関数上の一階法によって最適化される。 近年は大きな進展が見られたが、自然に滑らかな定式化は2つの不調の原因に苦しんでおり、勾配降下の反復複雑性は次元と低ランク行列の条件数の両方で小さくスケールしている。 さらに、スムーズな定式化は腐敗に対して堅牢ではない。 本稿では,非滑らかで非凸な定式化の族(特に絶対誤差の残余和)を,条件数にほぼ依存せず,条件数に依存しない高速で収束させることが保証される,スケール段階的な方法を提案する。 本稿では,観測演算子がある種の混合ノルム制限等長性を満たす場合と,ロバストな低ランク行列センシングや二次サンプリングといった様々な問題に対する最先端の性能保証を行う場合の有効性を示す。

関連論文リスト

• 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)
• A Novel Maximum-Entropy-Driven Technique for Low-Rank Orthogonal Nonnegative Matrix Factorization with $\ell_0$-Norm sparsity Constraint [0.0]
  データ駆動制御と機械学習では、大きな行列を小さく、低ランクな要素に分解する、という一般的な要件がある。 本稿では,直交非負行列分解(ONMF)問題に対する革新的な解を提案する。 提案手法は,文献と同等あるいは改善された復元誤差を実現する。
  論文  参考訳（メタデータ） (2022-10-06T04:30:59Z)
• 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)
• 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)
• Robust Low-rank Matrix Completion via an Alternating Manifold Proximal Gradient Continuation Method [47.80060761046752]
  ロバスト低ランク行列補完(RMC)は、コンピュータビジョン、信号処理、機械学習アプリケーションのために広く研究されている。 この問題は、部分的に観察された行列を低ランク行列とスパース行列の重ね合わせに分解することを目的とした。 RMCに取り組むために広く用いられるアプローチは、低ランク行列の核ノルム(低ランク性を促進するために)とスパース行列のl1ノルム(空間性を促進するために)を最小化する凸定式化を考えることである。 本稿では、近年のローワークの動機付けについて述べる。
  論文  参考訳（メタデータ） (2020-08-18T04:46:22Z)
• 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)
• Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent [34.0533596121548]
  低ランク行列推定は凸問題を収束させ、信号処理、機械学習、画像科学に多くの応用を見出す。 低ランク行列の個数の観点から,ScaledGDが最良となることを示す。 我々の分析は、低ランク勾配降下に類似した一般損失にも適用できる。
  論文  参考訳（メタデータ） (2020-05-18T17:17:16Z)

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

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