論文の概要: Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms

• arxiv url: http://arxiv.org/abs/2006.08916v1
• Date: Tue, 16 Jun 2020 04:26:50 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-20 19:09:16.035577
• Title: Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms
• Title（参考訳）: マルコフデータによる最小二乗回帰:基本限界とアルゴリズム
• Authors: Guy Bresler, Prateek Jain, Dheeraj Nagaraj, Praneeth Netrapalli and Xian Wu
• Abstract要約: マルコフ連鎖からデータポイントが依存しサンプリングされる最小二乗線形回帰問題について検討する。 この問題を$tau_mathsfmix$という観点から、鋭い情報理論のミニマックス下限を確立する。 本稿では,経験的リプレイに基づくアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 69.45237691598774
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of least squares linear regression where the data-points are dependent and are sampled from a Markov chain. We establish sharp information theoretic minimax lower bounds for this problem in terms of $\tau_{\mathsf{mix}}$, the mixing time of the underlying Markov chain, under different noise settings. Our results establish that in general, optimization with Markovian data is strictly harder than optimization with independent data and a trivial algorithm (SGD-DD) that works with only one in every $\tilde{\Theta}(\tau_{\mathsf{mix}})$ samples, which are approximately independent, is minimax optimal. In fact, it is strictly better than the popular Stochastic Gradient Descent (SGD) method with constant step-size which is otherwise minimax optimal in the regression with independent data setting. Beyond a worst case analysis, we investigate whether structured datasets seen in practice such as Gaussian auto-regressive dynamics can admit more efficient optimization schemes. Surprisingly, even in this specific and natural setting, Stochastic Gradient Descent (SGD) with constant step-size is still no better than SGD-DD. Instead, we propose an algorithm based on experience replay--a popular reinforcement learning technique--that achieves a significantly better error rate. Our improved rate serves as one of the first results where an algorithm outperforms SGD-DD on an interesting Markov chain and also provides one of the first theoretical analyses to support the use of experience replay in practice.
• Abstract（参考訳）: データポイントが依存し、マルコフ連鎖からサンプルされる最小二乗線形回帰の問題について検討する。 この問題に対して,基礎となるマルコフ連鎖の混合時間である$\tau_{\mathsf{mix}}$を用いて,異なる雑音条件下で,鋭い情報理論のミニマックス下界を確立する。 我々の結果は、マルコフデータによる最適化は、独立データによる最適化よりも厳密なものであり、ほぼ独立のサンプルである$\tilde{\Theta}(\tau_{\mathsf{mix}})$の1つでのみ動作する自明なアルゴリズム(SGD-DD)が極小であることを示す。 実際、SGD(Stochastic Gradient Descent)法はステップサイズが一定であり、それ以外は独立なデータ設定による回帰において最小限の最適値である。 最悪のケース分析の他に、ガウス自動回帰力学のような実際に見られる構造化データセットがより効率的な最適化スキームを許容できるかどうかを調査する。 驚くべきことに、この特異で自然な設定であっても、ステップサイズが一定であるSGD(Stochastic Gradient Descent)は依然としてSGD-DDに劣らない。 代わりに,経験的リプレイに基づくアルゴリズムを提案する。これは一般的な強化学習手法であり,エラー率を大幅に向上させる。 我々の改善率は、アルゴリズムが興味深いマルコフ連鎖上でsgd-ddを上回る最初の結果の1つとなり、実際経験リプレイの使用をサポートする最初の理論的分析の1つを提供する。

関連論文リスト

• On the Performance of Empirical Risk Minimization with Smoothed Data [59.3428024282545]
  経験的リスク最小化(Empirical Risk Minimization、ERM)は、クラスがiidデータで学習可能であれば、サブ線形誤差を達成できる。 We show that ERM can able to achieve sublinear error when a class are learnable with iid data。
  論文  参考訳（メタデータ） (2024-02-22T21:55:41Z)
• Robust Stochastic Optimization via Gradient Quantile Clipping [6.2844649973308835]
  グラディエントDescent(SGD)のための量子クリッピング戦略を導入する。 通常のクリッピングチェーンとして、グラデーション・ニュー・アウトリージを使用します。 本稿では,Huberiles を用いたアルゴリズムの実装を提案する。
  論文  参考訳（メタデータ） (2023-09-29T15:24:48Z)
• Statistical Inference with Stochastic Gradient Methods under $\phi$-mixing Data [9.77185962310918]
  データが$phi$-mixingの場合の統計的推測のためのミニバッチSGD推定器を提案する。 信頼区間は、関連するミニバッチSGDプロシージャを用いて構成される。 提案手法はメモリ効率が高く,実装が容易である。
  論文  参考訳（メタデータ） (2023-02-24T16:16:43Z)
• SketchySGD: Reliable Stochastic Optimization via Randomized Curvature Estimates [19.420605210427635]
  SketchySGDは、サブサンプルヘッセンに対するランダム化低ランク近似を用いることで、機械学習の既存の勾配法を改善する。 固定段数を持つSketchySGDが最適の周りの小さな球に線形に収束することを理論的に示す。 条件のない設定では、最小二乗問題に対してSketchySGDはSGDよりも高速に収束することを示す。
  論文  参考訳（メタデータ） (2022-11-16T01:05:41Z)
• Adaptive Sketches for Robust Regression with Importance Sampling [64.75899469557272]
  我々は、勾配降下(SGD)による頑健な回帰を解くためのデータ構造を導入する。 我々のアルゴリズムは、サブ線形空間を使用し、データに1回パスするだけで、SGDの$T$ステップを重要サンプリングで効果的に実行します。
  論文  参考訳（メタデータ） (2022-07-16T03:09:30Z)
• Differentiable Annealed Importance Sampling and the Perils of Gradient Noise [68.44523807580438]
  Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。 差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。 我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
  論文  参考訳（メタデータ） (2021-07-21T17:10:14Z)
• Robust Regression Revisited: Acceleration and Improved Estimation Rates [25.54653340884806]
  強い汚染モデルの下で, 統計的回帰問題に対する高速アルゴリズムについて検討する。 目的は、逆向きに破損したサンプルを与えられた一般化線形モデル(GLM)を概ね最適化することである。 実行時や推定保証が改善された頑健な回帰問題に対して,ほぼ直線的な時間アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-06-22T17:21:56Z)
• Attentional-Biased Stochastic Gradient Descent [74.49926199036481]
  深層学習におけるデータ不均衡やラベルノイズ問題に対処するための証明可能な手法(ABSGD)を提案する。 本手法は運動量SGDの簡易な修正であり,各試料に個別の重み付けを行う。 ABSGDは追加コストなしで他の堅牢な損失と組み合わせられるほど柔軟である。
  論文  参考訳（メタデータ） (2020-12-13T03:41:52Z)
• Direction Matters: On the Implicit Bias of Stochastic Gradient Descent with Moderate Learning Rate [105.62979485062756]
  本稿では,中等度学習におけるSGDの特定の正規化効果を特徴付けることを試みる。 SGDはデータ行列の大きな固有値方向に沿って収束し、GDは小さな固有値方向に沿って収束することを示す。
  論文  参考訳（メタデータ） (2020-11-04T21:07:52Z)
• Quasi-Newton Solver for Robust Non-Rigid Registration [35.66014845211251]
  データフィッティングと正規化のための大域的スムーズなロバスト推定器に基づくロバストな非剛性登録のための定式化を提案する。 本稿では,L-BFGS を用いた最小二乗問題の解法に,各繰り返しを減らし,最大化最小化アルゴリズムを適用した。
  論文  参考訳（メタデータ） (2020-04-09T01:45:05Z)

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

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