論文の概要: Convergence Rates for Stochastic Approximation: Biased Noise with
Unbounded Variance, and Applications
- arxiv url: http://arxiv.org/abs/2312.02828v2
- Date: Tue, 9 Jan 2024 07:18:24 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-10 19:34:28.226845
- 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(boldsymboltheta) = mathbf0 という形の方程式を解く標準的な方法である。
本稿では,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)$. At each time $t$, the
current guess ${\boldsymbol {\theta}}_t$ is updated to ${\boldsymbol
{\theta}}_{t+1}$ using a noisy measurement of the form $\mathbf{f}({\boldsymbol
{\theta}}_t) + {\boldsymbol {\xi}}_{t+1}$. In much of the literature, it is
assumed that the error term ${\boldsymbol {\xi}}_{t+1}$ has zero conditional
mean, and/or that its conditional variance is bounded as a function of $t$
(though not necessarily with respect to ${\boldsymbol {\theta}}_t$). Over the
years, SA has been applied to a variety of areas, out of which the focus in
this paper is on convex and nonconvex optimization. As it turns out, in these
applications, the above-mentioned assumptions on the measurement error 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. In
addition, we derive estimates for the rate of convergence of the algorithm, 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 {\theta}}_t$ は ${\boldsymbol {\theta}}_{t+1}$ に更新され、 $\mathbf{f}({\boldsymbol {\theta}}_t) + {\boldsymbol {\xi}}_{t+1}$ という形の雑音の測定値を使用する。
多くの文献において、誤差項 ${\boldsymbol {\xi}}_{t+1}$ は条件付き平均がゼロであり、その条件付き分散は$t$の関数として有界であると仮定されている(ただし、必ずしも${\boldsymbol {\theta}}_t$ についてはそうではない)。
長年にわたり、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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。