論文の概要: 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の信頼区間を与える。
さらに,本手法をロジスティック回帰を用いた戦略分類に適用し,対象クラス分類に影響を及ぼすために,学習中の特徴を適応的に修正する。
関連論文リスト
- TIC-TAC: A Framework To Learn And Evaluate Your Covariance [119.82937345718378]
State-of-the-art method predict the mean $f_theta(x)$ and covariance $textrmCov(f_theta(x))$ of the target distribution through the two neural network using the negative log-likelihood。
1)予測共分散は予測平均のランダム性を真に捉えているのか?
論文 参考訳(メタデータ) (2023-10-29T09:54:03Z) - Delta-AI: Local objectives for amortized inference in sparse graphical models [64.5938437823851]
スパース確率的グラフィカルモデル(PGM)における補正推論のための新しいアルゴリズムを提案する。
提案手法は, PGMにおける変数のサンプリングをエージェントが行う一連の行動とみなす場合, エージェントのポリシー学習目的において, PGMの疎結合が局所的な信用割当を可能にするという観察に基づいている。
合成PGMからサンプリングし、スパース因子構造を持つ潜在変数モデルを訓練するための$Delta$-AIの有効性について説明する。
論文 参考訳(メタデータ) (2023-10-03T20:37:03Z) - Covariate shift in nonparametric regression with Markovian design [0.0]
ナダラヤ・ワトソン核推定器の滑らかさリスクに対する収束速度は、ソースとターゲットマルコフ連鎖に関連する不変分布の類似性によって決定されることを示す。
我々は、Kpotufe と Martinet からの分布指数の概念を、一様エルゴードなマルコフ鎖の核移動指数に拡張する。
論文 参考訳(メタデータ) (2023-07-17T14:24:27Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。