論文の概要: Computationally Efficient and Statistically Optimal Robust Low-rank Matrix and Tensor Estimation

• arxiv url: http://arxiv.org/abs/2203.00953v4
• Date: Thu, 11 May 2023 01:20:06 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-12 19:18:24.695968
• Title: Computationally Efficient and Statistically Optimal Robust Low-rank Matrix and Tensor Estimation
• Title（参考訳）: 計算効率と統計的に最適ロバストな低ランク行列とテンソル推定
• Authors: Yinan Shen and Jingyang Li and Jian-Feng Cai and Dong Xia
• Abstract要約: 低ランク線形収縮推定法では, どちらも統計的に困難である。 本稿では,計算効率だけでなく,統計的に最適である新しいサブオリエント(RsGrad)を提案する。
• 参考スコア（独自算出の注目度）: 15.389011827844572
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Low-rank matrix estimation under heavy-tailed noise is challenging, both computationally and statistically. Convex approaches have been proven statistically optimal but suffer from high computational costs, especially since robust loss functions are usually non-smooth. More recently, computationally fast non-convex approaches via sub-gradient descent are proposed, which, unfortunately, fail to deliver a statistically consistent estimator even under sub-Gaussian noise. In this paper, we introduce a novel Riemannian sub-gradient (RsGrad) algorithm which is not only computationally efficient with linear convergence but also is statistically optimal, be the noise Gaussian or heavy-tailed. Convergence theory is established for a general framework and specific applications to absolute loss, Huber loss, and quantile loss are investigated. Compared with existing non-convex methods, ours reveals a surprising phenomenon of dual-phase convergence. In phase one, RsGrad behaves as in a typical non-smooth optimization that requires gradually decaying stepsizes. However, phase one only delivers a statistically sub-optimal estimator which is already observed in the existing literature. Interestingly, during phase two, RsGrad converges linearly as if minimizing a smooth and strongly convex objective function and thus a constant stepsize suffices. Underlying the phase-two convergence is the smoothing effect of random noise to the non-smooth robust losses in an area close but not too close to the truth. Lastly, RsGrad is applicable for low-rank tensor estimation under heavy-tailed noise where a statistically optimal rate is attainable with the same phenomenon of dual-phase convergence, and a novel shrinkage-based second-order moment method is guaranteed to deliver a warm initialization. Numerical simulations confirm our theoretical discovery and showcase the superiority of RsGrad over prior methods.
• Abstract（参考訳）: 重項雑音下での低位行列推定は, 計算量と統計量の両方において困難である。 凸アプローチは統計的に最適であることが証明されているが、特にロバストな損失関数は通常スムースではないため計算コストが高い。 より最近では、サブ勾配降下による計算速度の速い非凸アプローチが提案されているが、残念ながらサブガウス雑音下でも統計的に一貫した推定器を提供していない。 本稿では,線形収束により計算効率が向上するだけでなく,ガウス雑音や重み付き雑音に対して統計的に最適である,新しいリーマン部分勾配アルゴリズムを提案する。 一般の枠組みとして収束理論を確立し,絶対損失,ハマー損失,量子損失に対する特定の応用について検討した。 既存の非凸法と比較して, 2相収束の驚くべき現象が明らかになった。 フェーズ1では、rsgradは徐々に崩壊するステップを必要とする典型的な非スムース最適化のように振る舞う。 しかし、第1相は、既存の文献で既に観察されている統計的に準最適推定器のみを提供する。 興味深いことに、位相 2 のとき、RsGrad は滑らかで強凸な目的関数を最小化するように線型収束し、したがって一定の段階化が成立する。 位相2収束の根底にあるのは、無作為なノイズが近接する領域における非スムースなロバストな損失に対して平滑化効果である。 最後に、重項雑音下での低ランクテンソル推定にはrsgradが適用可能であり、双相収束の同じ現象で統計的に最適速度が達成でき、新しい縮約に基づく二階モーメント法によって温暖初期化が保証される。 数値シミュレーションにより, 理論的な発見を確認し, rsgradが先行手法よりも優れていることを示す。

関連論文リスト

• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• Learning Unnormalized Statistical Models via Compositional Optimization [73.30514599338407]
  実データと人工雑音のロジスティックな損失として目的を定式化することにより, ノイズコントラスト推定(NCE)を提案する。 本稿では,非正規化モデルの負の対数類似度を最適化するための直接的アプローチについて検討する。
  論文  参考訳（メタデータ） (2023-06-13T01:18:16Z)
• Online Bootstrap Inference with Nonconvex Stochastic Gradient Descent Estimator [0.0]
  本稿では,凸問題の文脈における統計的推論のための勾配降下(SGD)の理論的性質について検討する。 多重誤差最小値を含む2つの干渉手順を提案する。
  論文  参考訳（メタデータ） (2023-06-03T22:08:10Z)
• Computationally Efficient and Statistically Optimal Robust High-Dimensional Linear Regression [15.389011827844572]
  重み付き雑音や客観的腐敗の下での高テール線形回帰は、どちらも統計的に困難である。 本稿では,ノイズガウスあるいは重度1+エプシロン回帰問題に対するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-05-10T14:31:03Z)
• Robust Matrix Completion with Heavy-tailed Noise [0.5837881923712392]
  本稿では,重み付き潜在的非対称雑音の存在下での低ランク行列の完全性について検討する。 本稿では,大規模かつ非対称な誤りに対して頑健な重み付き雑音に適応するハマー損失を適応的に適用する。 誤差の2番目のモーメント条件下では、ユークリッド誤差は最小値の統計的推定誤差に到達するまで幾何的に早く落ちることが証明される。
  論文  参考訳（メタデータ） (2022-06-09T04:48:48Z)
• Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergence [69.65563161962245]
  ニュートン法を用いて,滑らかで強凸な目的関数を考える。 最適段階において局所収束に遷移する普遍重み付き平均化スキームが存在することを示す。
  論文  参考訳（メタデータ） (2022-04-20T07:14:21Z)
• Differentiable Annealed Importance Sampling and the Perils of Gradient Noise [68.44523807580438]
  Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。 差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。 我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
  論文  参考訳（メタデータ） (2021-07-21T17:10:14Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)

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

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