論文の概要: Online covariance estimation for stochastic gradient descent under Markovian sampling

• arxiv url: http://arxiv.org/abs/2308.01481v2
• Date: Sun, 5 Nov 2023 04:12:57 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-07 21:24:53.426495
• Title: Online covariance estimation for stochastic gradient descent under Markovian sampling
• Title（参考訳）: マルコフサンプリングによる確率勾配勾配のオンライン共分散推定
• Authors: Abhishek Roy, Krishnakumar Balasubramanian
• Abstract要約: 位数$Obig(sqrtd,n-1/8(log n)1/4big)$の収束率は、状態依存および状態依存マルコフサンプリングの下で確立される。 本手法はロジスティック回帰を用いた戦略分類に適用され, 学習中の特徴を適応的に修正し, 対象クラス分類に影響を与える。
• 参考スコア（独自算出の注目度）: 20.02012768403544
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We investigate the online overlapping batch-means covariance estimator for Stochastic Gradient Descent (SGD) under Markovian sampling. Convergence rates of order $O\big(\sqrt{d}\,n^{-1/8}(\log n)^{1/4}\big)$ and $O\big(\sqrt{d}\,n^{-1/8}\big)$ are established under state-dependent and state-independent Markovian sampling, respectively, where $d$ is the dimensionality and $n$ denotes observations or SGD iterations. These rates match the best-known convergence rate for independent and identically distributed (i.i.d) data. Our analysis overcomes significant challenges that arise due to Markovian sampling, leading to the introduction of additional error terms and complex dependencies between the blocks of the batch-means covariance estimator. Moreover, we establish the convergence rate for the first four moments of the $\ell_2$ norm of the error of SGD dynamics under state-dependent Markovian data, which holds potential interest as an independent result. Numerical illustrations provide confidence intervals for SGD in linear and logistic regression models under Markovian sampling. Additionally, our method is applied to the strategic classification with logistic regression, where adversaries adaptively modify features during training to affect target class classification.
• Abstract（参考訳）: マルコビアンサンプリングによる確率勾配Descent (SGD) のオンライン重なり合うバッチ平均共分散推定器について検討した。 位数$O\big(\sqrt{d}\,n^{-1/8}(\log n)^{1/4}\big)$と$O\big(\sqrt{d}\,n^{-1/8}\big)$の収束率は、それぞれ状態依存および状態非依存マルコフサンプリングの下で確立される。 これらのレートは、独立かつ同一分散(i.i.d)データの最もよく知られた収束率に合致する。 我々の分析はマルコフサンプリングによって生じる重要な課題を克服し、バッチ平均共分散推定器のブロック間に追加のエラー項と複雑な依存関係を導入する。 さらに、状態依存マルコフデータの下でSGDダイナミックスの誤差の$\ell_2$ノルムの最初の4つのモーメントに対する収束率を確立し、独立な結果として潜在的関心を持つ。 数値挿絵はマルコフサンプリングの下で線形およびロジスティック回帰モデルにおいてsgdの信頼区間を与える。 さらに,本手法をロジスティック回帰を用いた戦略分類に適用し,対象クラス分類に影響を及ぼすために,学習中の特徴を適応的に修正する。

関連論文リスト

• Markov Chain Variance Estimation: A Stochastic Approximation Approach [14.883782513177094]
  マルコフ連鎖上で定義される関数の分散を推定する問題は、定常平均の統計的推測の重要なステップである。 我々は,各ステップで$O(1)$を必要とする新しい再帰的推定器を設計し,過去のサンプルやラン長の知識を一切必要とせず,証明可能な有限サンプル保証付き平均二乗誤差(MSE)に対する最適な$O(frac1n)の収束率を有する。
  論文  参考訳（メタデータ） (2024-09-09T15:42:28Z)
• Adaptive Mean Estimation in the Hidden Markov sub-Gaussian Mixture Model [2.07180164747172]
  まず, 高次元設定における既存の結果の限界について検討し, 中心推定問題に対する最小限の最適手順を提案する。 我々の手順は、$sqrtdelta d/n + d/n$ ではなく、$sqrtdelta d/n + d/n$ という順序の最適値に達することを示し、$delta in(0, 1)$ はラベル間の依存パラメータである。
  論文  参考訳（メタデータ） (2024-06-18T09:48:21Z)
• Demystifying SGD with Doubly Stochastic Gradients [13.033133586372612]
  一般条件下では、独立なミニバッチとランダムリシャッフルを併用した2重SGDの収束特性を確立する。 ランダムリシャッフルによりサブサンプリングノイズの複雑性依存性が向上することが証明された。
  論文  参考訳（メタデータ） (2024-06-03T01:13:19Z)
• Delta-AI: Local objectives for amortized inference in sparse graphical models [64.5938437823851]
  スパース確率的グラフィカルモデル(PGM)における補正推論のための新しいアルゴリズムを提案する。 提案手法は, PGMにおける変数のサンプリングをエージェントが行う一連の行動とみなす場合, エージェントのポリシー学習目的において, PGMの疎結合が局所的な信用割当を可能にするという観察に基づいている。 合成PGMからサンプリングし、スパース因子構造を持つ潜在変数モデルを訓練するための$Delta$-AIの有効性について説明する。
  論文  参考訳（メタデータ） (2023-10-03T20:37:03Z)
• Generalized equivalences between subsampling and ridge regularization [3.1346887720803505]
  アンサンブルリッジ推定器におけるサブサンプリングとリッジ正則化の間の構造的およびリスク等価性を証明した。 我々の同値性の間接的な意味は、最適に調整されたリッジ回帰は、データアスペクト比において単調な予測リスクを示すことである。
  論文  参考訳（メタデータ） (2023-05-29T14:05:51Z)
• Policy evaluation from a single path: Multi-step methods, mixing and mis-specification [45.88067550131531]
  無限水平$gamma$-discounted Markov rewardプロセスの値関数の非パラメトリック推定について検討した。 カーネルベースの多段階時間差推定の一般的なファミリーに対して、漸近的でない保証を提供する。
  論文  参考訳（メタデータ） (2022-11-07T23:15:25Z)
• Adaptive Sketches for Robust Regression with Importance Sampling [64.75899469557272]
  我々は、勾配降下(SGD)による頑健な回帰を解くためのデータ構造を導入する。 我々のアルゴリズムは、サブ線形空間を使用し、データに1回パスするだけで、SGDの$T$ステップを重要サンプリングで効果的に実行します。
  論文  参考訳（メタデータ） (2022-07-16T03:09:30Z)
• CARMS: Categorical-Antithetic-REINFORCE Multi-Sample Gradient Estimator [60.799183326613395]
  本稿では, 相互に負に相関した複数のサンプルに基づく分類的確率変数の非バイアス推定器を提案する。 CARMSは、ReINFORCEとコプラベースのサンプリングを組み合わせることで、重複サンプルを回避し、その分散を低減し、重要サンプリングを使用して推定器を偏りなく維持する。 我々は、生成的モデリングタスクと構造化された出力予測タスクに基づいて、いくつかのベンチマークデータセット上でCARMSを評価し、強力な自己制御ベースラインを含む競合する手法より優れていることを示す。
  論文  参考訳（メタデータ） (2021-10-26T20:14:30Z)
• SLOE: A Faster Method for Statistical Inference in High-Dimensional Logistic Regression [68.66245730450915]
  実用データセットに対する予測の偏見を回避し、頻繁な不確実性を推定する改善された手法を開発している。 私たちの主な貢献は、推定と推論の計算時間をマグニチュードの順序で短縮する収束保証付き信号強度の推定器SLOEです。
  論文  参考訳（メタデータ） (2021-03-23T17:48:56Z)
• Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms [69.45237691598774]
  マルコフ連鎖からデータポイントが依存しサンプリングされる最小二乗線形回帰問題について検討する。 この問題を$tau_mathsfmix$という観点から、鋭い情報理論のミニマックス下限を確立する。 本稿では,経験的リプレイに基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-16T04:26:50Z)
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
  非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。 Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
  論文  参考訳（メタデータ） (2020-06-04T17:51:00Z)

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

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