論文の概要: Bridging Convex and Nonconvex Optimization in Robust PCA: Noise,
Outliers, and Missing Data
- arxiv url: http://arxiv.org/abs/2001.05484v2
- Date: Sun, 28 Feb 2021 20:05:35 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-11 06:33:23.940476
- Title: Bridging Convex and Nonconvex Optimization in Robust PCA: Noise,
Outliers, and Missing Data
- Title(参考訳): ロバストpcaにおけるブリッジング凸と非凸最適化:ノイズ、異常値、欠落データ
- Authors: Yuxin Chen, Jianqing Fan, Cong Ma, Yuling Yan
- Abstract要約: 本稿では,低ランク行列推定における凸プログラミング手法の理論的保証を改良した。
原理的凸プログラムはユークリッド損失とell_infty$損失の両方の観点から、ほぼ最適統計精度を達成することを示す。
- 参考スコア(独自算出の注目度): 20.31071912733189
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper delivers improved theoretical guarantees for the convex
programming approach in low-rank matrix estimation, in the presence of (1)
random noise, (2) gross sparse outliers, and (3) missing data. This problem,
often dubbed as robust principal component analysis (robust PCA), finds
applications in various domains. Despite the wide applicability of convex
relaxation, the available statistical support (particularly the stability
analysis vis-\`a-vis random noise) remains highly suboptimal, which we
strengthen in this paper. When the unknown matrix is well-conditioned,
incoherent, and of constant rank, we demonstrate that a principled convex
program achieves near-optimal statistical accuracy, in terms of both the
Euclidean loss and the $\ell_{\infty}$ loss. All of this happens even when
nearly a constant fraction of observations are corrupted by outliers with
arbitrary magnitudes. The key analysis idea lies in bridging the convex program
in use and an auxiliary nonconvex optimization algorithm, and hence the title
of this paper.
- Abstract(参考訳): 本稿では,(1)ランダムノイズ,(2)粗疎外乱,(3)欠落データの存在下で,低ランク行列推定における凸プログラミング手法に関する理論的保証を改良した。
この問題はロバスト主成分分析 (robust pca) と呼ばれ、様々な領域で応用されている。
凸緩和の幅広い適用性にもかかわらず、利用可能な統計的支援(特に安定性解析 vis-\`a-visランダムノイズ)は、非常に最適であり、本論文ではさらに強化する。
未知行列がよく条件付きで、一貫性がなく、一定ランクのとき、ユークリッド損失と$\ell_{\infty}$損失の両方の観点から、原理化された凸プログラムがほぼ最適の統計精度を達成することを示す。
これらは、ほぼ一定数の観測が任意の大きさの外れ値によって崩壊しても起こる。
重要な分析の考え方は、使用中の凸プログラムと補助的な非凸最適化アルゴリズムをブリッジすることであり、したがって本論文の題名である。
関連論文リスト
- Exploring the Algorithm-Dependent Generalization of AUPRC Optimization
with List Stability [107.65337427333064]
AUPRC(Area Under the Precision-Recall Curve)の最適化は、機械学習にとって重要な問題である。
本研究では, AUPRC最適化の単依存一般化における最初の試行について述べる。
3つの画像検索データセットの実験は、我々のフレームワークの有効性と健全性に言及する。
論文 参考訳(メタデータ) (2022-09-27T09:06:37Z) - Robust Matrix Completion with Heavy-tailed Noise [0.5837881923712392]
本稿では,重み付き潜在的非対称雑音の存在下での低ランク行列の完全性について検討する。
本稿では,大規模かつ非対称な誤りに対して頑健な重み付き雑音に適応するハマー損失を適応的に適用する。
誤差の2番目のモーメント条件下では、ユークリッド誤差は最小値の統計的推定誤差に到達するまで幾何的に早く落ちることが証明される。
論文 参考訳(メタデータ) (2022-06-09T04:48:48Z) - Support Recovery in Sparse PCA with Incomplete Data [27.3669650952144]
主成分分析(PCA)不完全データに対する実用的アルゴリズムを用いる。
未知の真のSDPが不完全支持行列を正確に復元できるという理論的および実験的証拠を提供する。
不完全データを用いて理論結果を検証し、分散表現において有意義な結果を示す。
論文 参考訳(メタデータ) (2022-05-30T16:17:39Z) - Computationally Efficient and Statistically Optimal Robust Low-rank
Matrix and Tensor Estimation [15.389011827844572]
低ランク線形収縮推定法では, どちらも統計的に困難である。
本稿では,計算効率だけでなく,統計的に最適である新しいサブオリエント(RsGrad)を提案する。
論文 参考訳(メタデータ) (2022-03-02T09:05:15Z) - Outlier-Robust Sparse Estimation via Non-Convex Optimization [73.18654719887205]
空間的制約が存在する場合の高次元統計量と非破壊的最適化の関連について検討する。
これらの問題に対する新規で簡単な最適化法を開発した。
結論として、効率よくステーションに収束する一階法は、これらのタスクに対して効率的なアルゴリズムを導出する。
論文 参考訳(メタデータ) (2021-09-23T17:38:24Z) - High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。
そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
論文 参考訳(メタデータ) (2021-06-10T17:54:21Z) - Nearly Optimal Robust Method for Convex Compositional Problems with
Heavy-Tailed Noise [46.94819585976063]
我々は、$f(E_xi g(cdot; xi)) + r(cdot)$という形の凸合成問題を解くための頑健なアルゴリズムを提案する。
我々の知る限りでは、これは重尾の仮定の下で構成問題に対するほぼ最適な準ガウス的自信境界を確立する最初の研究である。
論文 参考訳(メタデータ) (2020-06-17T18:36:05Z) - Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses [52.039438701530905]
任意のリプシッツ非平滑凸損失に対して,数種類の勾配勾配降下(SGD)に対して,鋭い上下境界を与える。
我々の限界は、極端に過剰な集団リスクを伴う、微分的にプライベートな非平滑凸最適化のための新しいアルゴリズムを導出することを可能にする。
論文 参考訳(メタデータ) (2020-06-12T02:45:21Z) - High-Dimensional Robust Mean Estimation via Gradient Descent [73.61354272612752]
一定対向分数の存在下でのロバスト平均推定の問題は勾配降下によって解けることを示す。
我々の研究は、近辺の非補題推定とロバスト統計の間の興味深い関係を確立する。
論文 参考訳(メタデータ) (2020-05-04T10:48:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。