論文の概要: Finite-Time Analysis of Stochastic Gradient Descent under Markov
Randomness
- arxiv url: http://arxiv.org/abs/2003.10973v2
- Date: Wed, 1 Apr 2020 17:50:14 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-20 09:44:56.030490
- Title: Finite-Time Analysis of Stochastic Gradient Descent under Markov
Randomness
- Title(参考訳): マルコフランダム性下における確率勾配の有限時間解析
- Authors: Thinh T. Doan, Lam M. Nguyen, Nhan H. Pham, Justin Romberg
- Abstract要約: 勾配降下(SGD)は強化学習や機械学習に使用される。
SGDはマルコフ勾配試料と独立勾配試料とほぼ同じ速度で収束することを示す。
- 参考スコア(独自算出の注目度): 27.027583559295365
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Motivated by broad applications in reinforcement learning and machine
learning, this paper considers the popular stochastic gradient descent (SGD)
when the gradients of the underlying objective function are sampled from Markov
processes. This Markov sampling leads to the gradient samples being biased and
not independent. The existing results for the convergence of SGD under Markov
randomness are often established under the assumptions on the boundedness of
either the iterates or the gradient samples. Our main focus is to study the
finite-time convergence of SGD for different types of objective functions,
without requiring these assumptions. We show that SGD converges nearly at the
same rate with Markovian gradient samples as with independent gradient samples.
The only difference is a logarithmic factor that accounts for the mixing time
of the Markov chain.
- Abstract(参考訳): 本稿では,強化学習と機械学習の幅広い応用に動機づけられ,対象関数の勾配がマルコフ過程からサンプリングされた場合の一般的な確率的勾配降下(sgd)について考察する。
このマルコフサンプリングは勾配サンプルに偏りがあり、独立ではない。
マルコフランダム性の下でのSGDの収束に関する既存の結果は、しばしば反復あるいは勾配サンプルの有界性に関する仮定の下で確立される。
目的関数の異なる種類のsgdの有限時間収束について,これらの仮定を必要とせずに検討する。
SGDはマルコフ勾配試料と独立勾配試料とほぼ同じ速度で収束することを示す。
唯一の違いは、マルコフ連鎖の混合時間を説明する対数係数である。
関連論文リスト
- Stochastic-Constrained Stochastic Optimization with Markovian Data [2.1756081703276]
マルコフ連鎖からデータサンプルが引き出され、したがって独立性がなく、同一に分布しないような環境について検討する。
ドリフト・プラス・ペナルティの2つの変種を提案する。ひとつは、基礎となるマルコフ鎖の混合時間を知る場合である。
我々のアルゴリズムは、制約関数列がマルコフ連鎖に従うような制約付きオンライン凸最適化のより一般的な設定に適用できる。
論文 参考訳(メタデータ) (2023-12-07T14:09:27Z) - Online covariance estimation for stochastic gradient descent under
Markovian sampling [20.02012768403544]
位数$Obig(sqrtd,n-1/8(log n)1/4big)$の収束率は、状態依存および状態依存マルコフサンプリングの下で確立される。
本手法はロジスティック回帰を用いた戦略分類に適用され, 学習中の特徴を適応的に修正し, 対象クラス分類に影響を与える。
論文 参考訳(メタデータ) (2023-08-03T00:21:30Z) - Adaptive Annealed Importance Sampling with Constant Rate Progress [68.8204255655161]
Annealed Importance Smpling (AIS)は、抽出可能な分布から重み付けされたサンプルを合成する。
本稿では,alpha$-divergencesに対する定数レートAISアルゴリズムとその効率的な実装を提案する。
論文 参考訳(メタデータ) (2023-06-27T08:15:28Z) - Doubly Stochastic Models: Learning with Unbiased Label Noises and
Inference Stability [85.1044381834036]
勾配降下のミニバッチサンプリング設定におけるラベル雑音の暗黙的正則化効果について検討した。
そのような暗黙的正則化器は、パラメータの摂動に対してモデル出力を安定化できる収束点を好んでいる。
我々の研究は、SGDをオルンシュタイン-ウレンベック類似の過程とはみなせず、近似の収束によってより一般的な結果を得る。
論文 参考訳(メタデータ) (2023-04-01T14:09:07Z) - Restoration-Degradation Beyond Linear Diffusions: A Non-Asymptotic
Analysis For DDIM-Type Samplers [90.45898746733397]
本研究では拡散生成モデルに用いる決定論的サンプリング器の非漸近解析のためのフレームワークを開発する。
確率フローODEに沿った1ステップは,1) 条件付き対数線上を無限に先行して上昇する回復ステップ,2) 雑音を現在の勾配に向けて前向きに進行する劣化ステップの2段階で表すことができる。
論文 参考訳(メタデータ) (2023-03-06T18:59:19Z) - Stochastic Gradient Descent under Markovian Sampling Schemes [3.04585143845864]
マルコフ型サンプリングスキームにのみアクセス可能なバニラ勾配勾配の変動について検討する。
我々は、基礎となるマルコフ連鎖で可能な最小限の制限的な仮定の下で収束率を得ることに焦点をあてる。
論文 参考訳(メタデータ) (2023-02-28T09:18:00Z) - Score-based Continuous-time Discrete Diffusion Models [102.65769839899315]
連続時間マルコフ連鎖を介して逆過程が認知されるマルコフジャンププロセスを導入することにより、拡散モデルを離散変数に拡張する。
条件境界分布の単純なマッチングにより、偏りのない推定器が得られることを示す。
提案手法の有効性を,合成および実世界の音楽と画像のベンチマークで示す。
論文 参考訳(メタデータ) (2022-11-30T05:33:29Z) - Markov Chain Score Ascent: A Unifying Framework of Variational Inference
with Markovian Gradients [7.461223697336269]
勾配降下(SGD)による包摂的クルバック・リーブラー分岐の最小化は、その勾配が後部上の積分として定義されるため困難である。
本稿では,これらの手法の非漸近収束解析として,混合速度と勾配のばらつきを確立した。
論文 参考訳(メタデータ) (2022-06-13T16:25:08Z) - Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector
Problems [98.34292831923335]
オンライン相関解析の問題から,emphStochastic Scaled-Gradient Descent (SSD)アルゴリズムを提案する。
我々はこれらのアイデアをオンライン相関解析に適用し、局所収束率を正規性に比例した最適な1時間スケールのアルゴリズムを初めて導いた。
論文 参考訳(メタデータ) (2021-12-29T18:46:52Z) - Unbiased Estimation of the Gradient of the Log-Likelihood for a Class of
Continuous-Time State-Space Models [0.0]
連続時間状態空間モデルのクラスに対する静的パラメータ推定について検討する。
私たちのゴールは、ログライクリフの勾配(スコア関数)の偏りのない推定値を得ることです。
論文 参考訳(メタデータ) (2021-05-24T20:31:48Z) - Faster Convergence of Stochastic Gradient Langevin Dynamics for
Non-Log-Concave Sampling [110.88857917726276]
我々は,非log-concaveとなる分布のクラスからサンプリングするために,勾配ランゲヴィンダイナミクス(SGLD)の新たな収束解析を行う。
我々のアプローチの核心は、補助的時間反転型マルコフ連鎖を用いたSGLDのコンダクタンス解析である。
論文 参考訳(メタデータ) (2020-10-19T15:23:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。