論文の概要: Adaptive Sketches for Robust Regression with Importance Sampling

• arxiv url: http://arxiv.org/abs/2207.07822v1
• Date: Sat, 16 Jul 2022 03:09:30 GMT
• ステータス: 処理完了
• システム内更新日: 2022-07-20 07:45:22.787195
• Title: Adaptive Sketches for Robust Regression with Importance Sampling
• Title（参考訳）: 重要サンプリングを用いたロバスト回帰のための適応スケッチ
• Authors: Sepideh Mahabadi, David P. Woodruff, Samson Zhou
• Abstract要約: 我々は、勾配降下(SGD)による頑健な回帰を解くためのデータ構造を導入する。 我々のアルゴリズムは、サブ線形空間を使用し、データに1回パスするだけで、SGDの$T$ステップを重要サンプリングで効果的に実行します。
• 参考スコア（独自算出の注目度）: 64.75899469557272
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce data structures for solving robust regression through stochastic gradient descent (SGD) by sampling gradients with probability proportional to their norm, i.e., importance sampling. Although SGD is widely used for large scale machine learning, it is well-known for possibly experiencing slow convergence rates due to the high variance from uniform sampling. On the other hand, importance sampling can significantly decrease the variance but is usually difficult to implement because computing the sampling probabilities requires additional passes over the data, in which case standard gradient descent (GD) could be used instead. In this paper, we introduce an algorithm that approximately samples $T$ gradients of dimension $d$ from nearly the optimal importance sampling distribution for a robust regression problem over $n$ rows. Thus our algorithm effectively runs $T$ steps of SGD with importance sampling while using sublinear space and just making a single pass over the data. Our techniques also extend to performing importance sampling for second-order optimization.
• Abstract（参考訳）: 本研究では,確率勾配勾配を標準値に比例してサンプリングすることで,確率勾配勾配勾配(SGD)による頑健な回帰を解くためのデータ構造を導入する。 SGDは大規模機械学習に広く用いられているが、一様サンプリングのばらつきが大きいため、収束速度が遅いことが知られている。 一方で、サンプリングの重要性は分散を著しく減少させるが、サンプリング確率を計算するにはデータに対する追加のパスが必要であり、標準勾配降下 (gd) を代わりに使用できるため、通常は実装が困難である。 本稿では,約$T$グラデーションを,$n$行を超えるロバスト回帰問題に対して,最も重要なサンプリング分布から,約$d$のディメンションをサンプリングするアルゴリズムを提案する。 したがって,本アルゴリズムは,sgd の$t$ ステップを効果的に実行し,サブリニア空間を用いてデータに1回のパスを行う。 また,2次最適化のための重要サンプリングも行う。

関連論文リスト

• Improving the Convergence Rates of Forward Gradient Descent with Repeated Sampling [5.448070998907116]
  前向き勾配降下(FGD)は、生物学的により妥当な勾配降下の代替として提案されている。 本稿では、各トレーニングサンプルに基づいて、$ell$FGDステップを計算することにより、この亜最適係数が$d/(ell wedge d)$となることを示す。 また、繰り返しサンプリングしたFGDは入力分布の低次元構造に適応できることを示す。
  論文  参考訳（メタデータ） (2024-11-26T16:28:16Z)
• Efficient Gradient Estimation via Adaptive Sampling and Importance Sampling [34.50693643119071]
  適応的あるいは重要なサンプリングは、勾配推定におけるノイズを低減する。 本稿では,既存の重要関数をフレームワークに組み込むアルゴリズムを提案する。 計算オーバーヘッドを最小限に抑えた分類・回帰タスクにおける収束性の改善を観察する。
  論文  参考訳（メタデータ） (2023-11-24T13:21:35Z)
• Preferential Subsampling for Stochastic Gradient Langevin Dynamics [3.158346511479111]
  勾配MCMCは、データの小さな一様重み付きサブサンプルを持つ対数姿勢の勾配をバイアスなく見積もっている。 得られた勾配推定器は、高いばらつきおよび衝撃サンプリング性能を示すことができる。 このような手法は,使用中の平均サブサンプルサイズを大幅に削減しつつ,同じレベルの精度を維持することができることを示す。
  論文  参考訳（メタデータ） (2022-10-28T14:56:18Z)
• SIMPLE: A Gradient Estimator for $k$-Subset Sampling [42.38652558807518]
  この作業では、フォワードパスの離散$k$-subsetサンプリングに戻ります。 勾配推定器 SIMPLE は, 最先端推定器と比較して, バイアスやばらつきが低いことを示す。 実験結果から,線形回帰を説明・スパースする学習性能が向上した。
  論文  参考訳（メタデータ） (2022-10-04T22:33:16Z)
• Heavy-tailed Streaming Statistical Estimation [58.70341336199497]
  ストリーミング$p$のサンプルから重み付き統計推定の課題を考察する。 そこで我々は,傾きの雑音に対して,よりニュアンスな条件下での傾きの傾きの低下を設計し,より詳細な解析を行う。
  論文  参考訳（メタデータ） (2021-08-25T21:30:27Z)
• Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors [59.33977545294148]
  O(k log L)$サンプルは振幅に基づく経験損失関数を最小化する任意のベクトルに信号が近いことを保証するのに十分であることを示す。 この結果はスパース位相検索に適応し、基底信号が$s$-sparseおよび$n$-dimensionalである場合、$O(s log n)$サンプルは同様の保証に十分であることを示す。
  論文  参考訳（メタデータ） (2021-06-29T12:49:54Z)
• Attentional-Biased Stochastic Gradient Descent [74.49926199036481]
  深層学習におけるデータ不均衡やラベルノイズ問題に対処するための証明可能な手法(ABSGD)を提案する。 本手法は運動量SGDの簡易な修正であり,各試料に個別の重み付けを行う。 ABSGDは追加コストなしで他の堅牢な損失と組み合わせられるほど柔軟である。
  論文  参考訳（メタデータ） (2020-12-13T03:41:52Z)
• Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms [69.45237691598774]
  マルコフ連鎖からデータポイントが依存しサンプリングされる最小二乗線形回帰問題について検討する。 この問題を$tau_mathsfmix$という観点から、鋭い情報理論のミニマックス下限を確立する。 本稿では,経験的リプレイに基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-16T04:26:50Z)
• Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
  カラムサブセット選択、部分空間近似、射影クラスタリング、および空間サブリニアを$n$で使用するターンタイルストリームのボリュームに対する最初の相対エラーアルゴリズムを提供する。 我々の適応的なサンプリング手法は、様々なデータ要約問題に多くの応用をもたらしており、これは最先端を改善するか、より緩和された行列列モデルで以前に研究されただけである。
  論文  参考訳（メタデータ） (2020-04-23T05:00:21Z)
• Online stochastic gradient descent on non-convex losses from high-dimensional inference [2.2344764434954256]
  勾配降下(SGD)は高次元タスクにおける最適化問題に対する一般的なアルゴリズムである。 本稿では,データから非自明な相関関係を推定する。 本稿では、位相探索や一般化モデルの推定といった一連のタスクに適用することで、我々のアプローチを説明する。
  論文  参考訳（メタデータ） (2020-03-23T17:34:06Z)

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

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