論文の概要: Robust Matrix Completion with Heavy-tailed Noise
- arxiv url: http://arxiv.org/abs/2206.04276v1
- Date: Thu, 9 Jun 2022 04:48:48 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-10 14:09:10.657218
- Title: Robust Matrix Completion with Heavy-tailed Noise
- Title(参考訳): 重み付き雑音によるロバストマトリックス補完
- Authors: Bingyan Wang, Jianqing Fan
- Abstract要約: 本稿では,重み付き潜在的非対称雑音の存在下での低ランク行列の完全性について検討する。
本稿では,大規模かつ非対称な誤りに対して頑健な重み付き雑音に適応するハマー損失を適応的に適用する。
誤差の2番目のモーメント条件下では、ユークリッド誤差は最小値の統計的推定誤差に到達するまで幾何的に早く落ちることが証明される。
- 参考スコア(独自算出の注目度): 0.5837881923712392
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper studies low-rank matrix completion in the presence of heavy-tailed
and possibly asymmetric noise, where we aim to estimate an underlying low-rank
matrix given a set of highly incomplete noisy entries. Though the matrix
completion problem has attracted much attention in the past decade, there is
still lack of theoretical understanding when the observations are contaminated
by heavy-tailed noises. Prior theory falls short of explaining the empirical
results and is unable to capture the optimal dependence of the estimation error
on the noise level. In this paper, we adopt an adaptive Huber loss to
accommodate heavy-tailed noise, which is robust against large and possibly
asymmetric errors when the parameter in the loss function is carefully designed
to balance the Huberization biases and robustness to outliers. Then, we propose
an efficient nonconvex algorithm via a balanced low-rank Burer-Monteiro matrix
factorization and gradient decent with robust spectral initialization. We prove
that under merely bounded second moment condition on the error distributions,
rather than the sub-Gaussian assumption, the Euclidean error of the iterates
generated by the proposed algorithm decrease geometrically fast until achieving
a minimax-optimal statistical estimation error, which has the same order as
that in the sub-Gaussian case. The key technique behind this significant
advancement is a powerful leave-one-out analysis framework. The theoretical
results are corroborated by our simulation studies.
- Abstract(参考訳): 本稿では、重み付きおよびおそらく非対称な雑音の存在下での低ランク行列の完備化について検討し、高不完全雑音成分の集合から下層の低ランク行列を推定することを目的とする。
行列完備問題は過去10年間に多くの注目を集めてきたが、重い音によって観測が汚染された場合の理論的理解が不足している。
先行理論は実験結果を説明するのに至らず、ノイズレベルに対する推定誤差の最適依存性を捉えることができない。
本稿では,損失関数のパラメータがフーバ化バイアスと外れ値とのロバスト性とをバランスさせるために慎重に設計されている場合,大きな非対称誤差に対して頑健な重み付き雑音に対応する適応フーバ損失を採用する。
そこで我々は,安定なスペクトル初期化を伴うバランスの低いBurer-Monteiro行列因数分解と勾配による効率的な非凸アルゴリズムを提案する。
提案アルゴリズムにより生成したイテレートのユークリッド誤差は, 誤差分布上でのみ有界な第2モーメント条件の下では, 準ガウスの場合と同じ順序の最小値の統計的推定誤差に到達するまで, 幾何的に急速に減少することを示した。
この重要な進歩の背後にある重要なテクニックは、強力な左利き分析フレームワークである。
理論的結果はシミュレーション研究によって裏付けられている。
関連論文リスト
- Computationally Efficient and Statistically Optimal Robust
High-Dimensional Linear Regression [15.389011827844572]
重み付き雑音や客観的腐敗の下での高テール線形回帰は、どちらも統計的に困難である。
本稿では,ノイズガウスあるいは重度1+エプシロン回帰問題に対するアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-05-10T14:31:03Z) - Optimizing the Noise in Self-Supervised Learning: from Importance
Sampling to Noise-Contrastive Estimation [80.07065346699005]
GAN(Generative Adversarial Networks)のように、最適な雑音分布はデータ分布に等しくなると広く想定されている。
我々は、この自己教師型タスクをエネルギーベースモデルの推定問題として基礎づけるノイズ・コントラスト推定に目を向ける。
本研究は, 最適雑音のサンプリングは困難であり, 効率性の向上は, データに匹敵する雑音分布を選択することに比べ, 緩やかに行うことができると結論付けた。
論文 参考訳(メタデータ) (2023-01-23T19:57:58Z) - The price of ignorance: how much does it cost to forget noise structure
in low-rank matrix estimation? [21.3083877172595]
本稿では,構造的回転不変雑音によるランク1信号の誤差を推定する問題を考察する。
我々は,ノイズ統計量である強いミスマッチ源の効果を理解するための一歩を踏み出した。
この性能差は信号ノルムの誤推定によるものであることを示す。
論文 参考訳(メタデータ) (2022-05-20T07:54:21Z) - Computationally Efficient and Statistically Optimal Robust Low-rank
Matrix and Tensor Estimation [15.389011827844572]
低ランク線形収縮推定法では, どちらも統計的に困難である。
本稿では,計算効率だけでなく,統計的に最適である新しいサブオリエント(RsGrad)を提案する。
論文 参考訳(メタデータ) (2022-03-02T09:05:15Z) - Optimizing Information-theoretical Generalization Bounds via Anisotropic
Noise in SGLD [73.55632827932101]
SGLDにおけるノイズ構造を操作することにより,情報理論の一般化を最適化する。
低経験的リスクを保証するために制約を課すことで、最適なノイズ共分散が期待される勾配共分散の平方根であることを証明する。
論文 参考訳(メタデータ) (2021-10-26T15:02:27Z) - Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。
我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。
MRP のサブクラスに対する minimax の下位境界を証明する。
論文 参考訳(メタデータ) (2021-09-24T14:48:20Z) - Heavy-tailed Streaming Statistical Estimation [58.70341336199497]
ストリーミング$p$のサンプルから重み付き統計推定の課題を考察する。
そこで我々は,傾きの雑音に対して,よりニュアンスな条件下での傾きの傾きの低下を設計し,より詳細な解析を行う。
論文 参考訳(メタデータ) (2021-08-25T21:30:27Z) - Near-Optimal High Probability Complexity Bounds for Non-Smooth
Stochastic Optimization with Heavy-Tailed Noise [63.304196997102494]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
既存の非滑らか凸最適化法は、負のパワーまたは対数的な信頼度に依存する境界の複雑さを持つ。
クリッピングを用いた2つの勾配法に対して, 新たなステップサイズルールを提案する。
論文 参考訳(メタデータ) (2021-06-10T17:54:21Z) - On the Role of Entropy-based Loss for Learning Causal Structures with
Continuous Optimization [27.613220411996025]
因果構造学習問題を最小二乗損失を用いた連続最適化問題として定式化する。
ガウス雑音の仮定に違反すると因果方向の同定が妨げられることを示す。
より一般的なエントロピーに基づく損失は、任意の雑音分布下での確率スコアと理論的に一致している。
論文 参考訳(メタデータ) (2021-06-05T08:29:51Z) - Robust Compressed Sensing using Generative Models [98.64228459705859]
本稿では,Median-of-Means (MOM) にヒントを得たアルゴリズムを提案する。
我々のアルゴリズムは、外れ値が存在する場合でも、重み付きデータの回復を保証する。
論文 参考訳(メタデータ) (2020-06-16T19:07:41Z) - Bridging Convex and Nonconvex Optimization in Robust PCA: Noise,
Outliers, and Missing Data [20.31071912733189]
本稿では,低ランク行列推定における凸プログラミング手法の理論的保証を改良した。
原理的凸プログラムはユークリッド損失とell_infty$損失の両方の観点から、ほぼ最適統計精度を達成することを示す。
論文 参考訳(メタデータ) (2020-01-15T18:54:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。