論文の概要: Computationally Efficient and Statistically Optimal Robust High-Dimensional Linear Regression

• arxiv url: http://arxiv.org/abs/2305.06199v1
• Date: Wed, 10 May 2023 14:31:03 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-11 12:44:18.924257
• Title: Computationally Efficient and Statistically Optimal Robust High-Dimensional Linear Regression
• Title（参考訳）: 計算効率と統計的に最適ロバストな高次元線形回帰
• Authors: Yinan Shen, Jingyang Li, Jian-Feng Cai, Dong Xia
• Abstract要約: 重み付き雑音や客観的腐敗の下での高テール線形回帰は、どちらも統計的に困難である。 本稿では,ノイズガウスあるいは重度1+エプシロン回帰問題に対するアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 15.389011827844572
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: High-dimensional linear regression under heavy-tailed noise or outlier corruption is challenging, both computationally and statistically. Convex approaches have been proven statistically optimal but suffer from high computational costs, especially since the 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 projected sub-gradient descent algorithm for both the sparse linear regression and low-rank linear regression problems. The algorithm is not only computationally efficient with linear convergence but also statistically optimal, be the noise Gaussian or heavy-tailed with a finite 1 + epsilon moment. The convergence theory is established for a general framework and its specific applications to absolute loss, Huber loss and quantile loss are investigated. Compared with existing non-convex methods, ours reveals a surprising phenomenon of two-phase convergence. In phase one, the algorithm behaves as in 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, the algorithm 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. Numerical simulations confirm our theoretical discovery and showcase the superiority of our algorithm over prior methods.
• Abstract（参考訳）: 重み付き雑音や外乱による高次元線形回帰は、計算的・統計的に困難である。 凸アプローチは統計的に最適であることが証明されているが、特にロバスト損失関数は通常スムースではないため計算コストが高い。 より最近では、サブ勾配降下による計算速度の速い非凸アプローチが提案されているが、残念ながらサブガウス雑音下でも統計的に一貫した推定器を提供していない。 本稿では,スパース線形回帰問題と低ランク線形回帰問題の両方に対して,投影された下位勾配降下アルゴリズムを提案する。 このアルゴリズムは線形収束により計算効率が向上するだけでなく、ガウスのノイズや有限の1 + エプシロンモーメントの重み付きなど、統計的に最適である。 収束理論は, 一般的な枠組みとして確立され, 絶対損失, フーバー損失, 量的損失に対する具体的応用が検討されている。 既存の非凸法と比較して, 2相収束の驚くべき現象が明らかになった。 フェーズ1では、アルゴリズムは徐々に減衰するステップを必要とする典型的な非スムース最適化のように振る舞う。 しかし、第1相は、既存の文献で既に観察されている統計的に準最適推定器のみを提供する。 興味深いことに、第2相の間、アルゴリズムは滑らかで強い凸対象関数を最小化するように線形収束するので、一定ステップで十分である。 位相2収束の根底にあるのは、無作為なノイズが近接する領域における非スムースなロバストな損失に対して平滑化効果である。 数値シミュレーションにより理論的な発見を確認し,先行手法よりもアルゴリズムの優越性を示す。

関連論文リスト

• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• Low-rank Tensor Learning with Nonconvex Overlapped Nuclear Norm Regularization [44.54772242784423]
  低ランク学習行列に対する効率的な非正規化アルゴリズムを開発した。 提案アルゴリズムは、高価な折り畳み/折り畳み問題を回避することができる。 実験の結果,提案アルゴリズムは既存の状態よりも効率的で空間が広いことがわかった。
  論文  参考訳（メタデータ） (2022-05-06T07:47:10Z)
• Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergence [69.65563161962245]
  ニュートン法を用いて,滑らかで強凸な目的関数を考える。 最適段階において局所収束に遷移する普遍重み付き平均化スキームが存在することを示す。
  論文  参考訳（メタデータ） (2022-04-20T07:14:21Z)
• Computationally Efficient and Statistically Optimal Robust Low-rank Matrix and Tensor Estimation [15.389011827844572]
  低ランク線形収縮推定法では, どちらも統計的に困難である。 本稿では,計算効率だけでなく,統計的に最適である新しいサブオリエント(RsGrad)を提案する。
  論文  参考訳（メタデータ） (2022-03-02T09:05:15Z)
• 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)
• Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
  近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
  論文  参考訳（メタデータ） (2020-12-11T08:28:51Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Provably Convergent Working Set Algorithm for Non-Convex Regularized Regression [0.0]
  本稿では、収束保証付き非正則正規化器のためのワーキングセットアルゴリズムを提案する。 その結果,ブロックコーディネートや勾配ソルバの完全解法と比較して高い利得を示した。
  論文  参考訳（メタデータ） (2020-06-24T07:40:31Z)
• The estimation error of general first order methods [12.472245917779754]
  我々は,高次元回帰と低次元行列推定という2種類の推定問題を考察する。 我々は、観測数とパラメータ数の両方が分岐する高次元最適値の誤差を下界に導出する。 これらの下界は、推定誤差が下界とわずかに無視可能な項に一致するアルゴリズムが存在することを意味している。
  論文  参考訳（メタデータ） (2020-02-28T18:13:47Z)

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

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