論文の概要: Convergence Rates for Stochastic Approximation: Biased Noise with
Unbounded Variance, and Applications
- arxiv url: http://arxiv.org/abs/2312.02828v1
- Date: Tue, 5 Dec 2023 15:22:39 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-06 15:22:21.914364
- Title: Convergence Rates for Stochastic Approximation: Biased Noise with
Unbounded Variance, and Applications
- Title（参考訳）: 確率近似の収束率:非有界分散バイアス雑音とその応用
- Authors: Rajeeva L. Karandikar and M. Vidyasagar
- Abstract要約: 1951年にRobinsとMonroによって導入された近似アルゴリズムは、$mathbff(boldsymbol the) = mathbf0という形の方程式を解く標準的な方法である。
我々はSA理論を拡張し、非ゼロ条件平均および/または条件分散と同期SAとの誤差を包含する。
- 参考スコア（独自算出の注目度）: 2.3134637611088653
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The Stochastic Approximation (SA) algorithm introduced by Robbins and Monro
in 1951 has been a standard method for solving equations of the form
$\mathbf{f}({\boldsymbol {\theta}}) = \mathbf{0}$, when only noisy measurements
of $\mathbf{f}(\cdot)$ are available. If $\mathbf{f}({\boldsymbol {\theta}}) =
\nabla J({\boldsymbol {\theta}})$ for some function $J(\cdot)$, then SA can
also be used to find a stationary point of $J(\cdot)$. In much of the
literature, it is assumed that the error term ${\boldsymbol {xi}}_{t+1}$ has
zero conditional mean, and that its conditional variance is bounded as a
function of $t$ (though not necessarily with respect to ${\boldsymbol
{\theta}}_t$). Also, for the most part, the emphasis has been on
``synchronous'' SA, whereby, at each time $t$, \textit{every} component of
${\boldsymbol {\theta}}_t$ is updated. Over the years, SA has been applied to a
variety of areas, out of which two are the focus in this paper: Convex and
nonconvex optimization, and Reinforcement Learning (RL). As it turns out, in
these applications, the above-mentioned assumptions do not always hold. In
zero-order methods, the error neither has zero mean nor bounded conditional
variance. In the present paper, we extend SA theory to encompass errors with
nonzero conditional mean and/or unbounded conditional variance, and also
asynchronous SA. In addition, we derive estimates for the rate of convergence
of the algorithm. Then we apply the new results to problems in nonconvex
optimization, and to Markovian SA, a recently emerging area in RL. We prove
that SA converges in these situations, and compute the ``optimal step size
sequences'' to maximize the estimated rate of convergence.
- Abstract（参考訳）: 1951年にRobinsとMonroによって導入された確率近似(SA)アルゴリズムは、$\mathbf{f}({\boldsymbol {\theta}}) = \mathbf{0}$という形の方程式を解く標準的な方法である。
もしある関数 $J(\cdot)$ に対して $\mathbf{f}({\boldsymbol {\theta}}) = \nabla J({\boldsymbol {\theta}})$ であれば、SA は $J(\cdot)$ の定常点を見つけるためにも使うことができる。
多くの文献において、誤差項 ${\boldsymbol {xi}}_{t+1}$ は条件付き平均がゼロであり、条件付き分散は$t$の関数として有界であると仮定されている(ただし、必ずしも${\boldsymbol {\theta}}_t$ についてはそうではない)。
また、ほとんどの部分は ``synchronous'' SA に重点を置いており、${\boldsymbol {\theta}}_t$ の $t$, \textit{every} コンポーネントが更新される。
長年にわたり、saは様々な分野に適用されてきたが、そのうちの2つは、convexとnonconvexの最適化と強化学習(rl)である。
これらの応用において、上記の仮定は常に成り立つとは限らない。
ゼロ次法では、誤差は平均値も有界条件分散も持たない。
本稿では,非ゼロ条件平均および/または非有界条件分散による誤差を包含するSA理論を拡張し,非同期SAについても述べる。
さらに,アルゴリズムの収束率の推定値も導出する。
次に,新しい結果を非凸最適化の問題に適用し,最近登場したrl領域であるマルコビアンsaに適用する。
これらの状況においてsaが収束することを証明し, ‘optimal step size sequences’’ を計算して収束率を最大化する。
関連論文リスト
- A Unified Analysis for Finite Weight Averaging [50.75116992029417]
Gradient Descent(SGD)の平均イテレーションは、SWA(Weight Averaging)、EMA(Exponential moving Average)、LAWA(Latest Weight Averaging)といったディープラーニングモデルのトレーニングにおいて、経験的な成功を収めている。
本稿では、LAWAを有限重み平均化(FWA)として一般化し、最適化と一般化の観点からSGDと比較して、それらの利点を説明する。
論文 参考訳（メタデータ） (2024-11-20T10:08:22Z) - Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods [25.831462008050387]
グラディエント・Descent(SGD)アルゴリズムは、実際の性能が良く、理論的な理解が欠如していることから、人々の関心を喚起している。
有限収束がより広い合成最適化や非ユークリッドノルムに証明可能な拡張が可能かどうかはまだ不明である。
論文 参考訳（メタデータ） (2023-12-13T21:41:06Z) - Demystifying the Myths and Legends of Nonconvex Convergence of SGD [17.445810977264067]
勾配勾配勾配(SGD)とその変種は、大規模最適化問題の解法の主要な仕事場である。
分析として,勾配の非収束に関連する神話や伝説について考察した。
論文 参考訳（メタデータ） (2023-10-19T17:58:59Z) - Randomized Coordinate Subgradient Method for Nonsmooth Composite
Optimization [11.017632675093628]
非滑らかな問題に対処するコーディネート型劣階法は、リプシッツ型仮定の性質のセットのため、比較的過小評価されている。
論文 参考訳（メタデータ） (2022-06-30T02:17:11Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳（メタデータ） (2022-06-17T06:10:20Z) - Sharper Rates and Flexible Framework for Nonconvex SGD with Client and
Data Sampling [64.31011847952006]
我々は、平均$n$スムーズでおそらくは非カラー関数のほぼ定常点を求める問題を再考する。
我々は$smallsfcolorgreen$を一般化し、事実上あらゆるサンプリングメカニズムで確実に動作するようにします。
我々は、スムーズな非カラー状態における最適境界の最も一般的な、最も正確な解析を提供する。
論文 参考訳（メタデータ） (2022-06-05T21:32:33Z) - Convergence Rates of Stochastic Gradient Descent under Infinite Noise
Variance [14.06947898164194]
ヘビーテールは様々なシナリオで勾配降下 (sgd) で現れる。
SGDの収束保証は、潜在的に無限のばらつきを持つ状態依存性および重尾ノイズ下で提供します。
その結果,SGDは無限に分散した重尾雑音下であっても,地球最適値に収束できることが示された。
論文 参考訳（メタデータ） (2021-02-20T13:45:11Z) - Faster Convergence of Stochastic Gradient Langevin Dynamics for
Non-Log-Concave Sampling [110.88857917726276]
我々は,非log-concaveとなる分布のクラスからサンプリングするために,勾配ランゲヴィンダイナミクス(SGLD)の新たな収束解析を行う。
我々のアプローチの核心は、補助的時間反転型マルコフ連鎖を用いたSGLDのコンダクタンス解析である。
論文 参考訳（メタデータ） (2020-10-19T15:23:18Z) - On the Almost Sure Convergence of Stochastic Gradient Descent in
Non-Convex Problems [75.58134963501094]
本稿では,勾配降下(SGD)の軌跡を解析する。
我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
論文 参考訳（メタデータ） (2020-06-19T14:11:26Z) - Almost sure convergence rates for Stochastic Gradient Descent and
Stochastic Heavy Ball [17.33867778750777]
一般近似問題に対する勾配降下法(SGD)と重球法(SHB)について検討した。
SGD の場合、凸と滑らかな設定において、イテレートの重み付き平均に対して、最初の最も確実な収束式を提供する。
論文 参考訳（メタデータ） (2020-06-14T11:12:05Z) - A Simple Convergence Proof of Adam and Adagrad [74.24716715922759]
我々はAdam Adagradと$O(d(N)/st)$アルゴリズムの収束の証明を示す。
Adamはデフォルトパラメータで使用する場合と同じ収束$O(d(N)/st)$で収束する。
論文 参考訳（メタデータ） (2020-03-05T01:56:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。