論文の概要: 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''' を計算し,収束率を最大化する。
関連論文リスト
- Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳(メタデータ) (2023-06-02T18:55:27Z) - Convergence of a Normal Map-based Prox-SGD Method under the KL
Inequality [0.0]
我々は、$symbol$k$収束問題に対して、新しいマップベースのアルゴリズム(mathsfnorMtext-mathsfSGD$)を提案する。
論文 参考訳(メタデータ) (2023-05-10T01:12:11Z) - Random matrices in service of ML footprint: ternary random features with
no performance loss [55.30329197651178]
我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。
3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。
提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
論文 参考訳(メタデータ) (2021-10-05T09:33:49Z) - Nonasymptotic one-and two-sample tests in high dimension with unknown
covariance structure [0.0]
テストの問題は、$mu が 0 に対して $eta-閉である場合、すなわち $|mu| geq (eta + delta)$ に対して $|mu| leq eta である。
本研究の目的は,I型とII型の両方の誤差を所定のレベルで制御できるように,最小分離距離$の漸近的上下境界を求めることである。
論文 参考訳(メタデータ) (2021-09-01T06:22:53Z) - Minimax Optimal Regression over Sobolev Spaces via Laplacian
Regularization on Neighborhood Graphs [25.597646488273558]
非パラメトリック回帰に対するグラフに基づくアプローチであるラプラシア平滑化の統計的性質について検討する。
ラプラシアン滑らか化が多様体適応であることを証明する。
論文 参考訳(メタデータ) (2021-06-03T01:20:41Z) - Optimal Mean Estimation without a Variance [103.26777953032537]
本研究では,データ生成分布の分散が存在しない環境での重み付き平均推定問題について検討する。
最小の信頼区間を$n,d,delta$の関数として得る推定器を設計する。
論文 参考訳(メタデータ) (2020-11-24T22:39:21Z) - Sparse sketches with small inversion bias [79.77110958547695]
逆バイアスは、逆の共分散に依存する量の推定を平均化するときに生じる。
本研究では、確率行列に対する$(epsilon,delta)$-unbiased estimatorという概念に基づいて、逆バイアスを解析するためのフレームワークを開発する。
スケッチ行列 $S$ が密度が高く、すなわちサブガウスのエントリを持つとき、$(epsilon,delta)$-unbiased for $(Atop A)-1$ は $m=O(d+sqrt d/ のスケッチを持つ。
論文 参考訳(メタデータ) (2020-11-21T01:33:15Z) - Accelerating Optimization and Reinforcement Learning with
Quasi-Stochastic Approximation [2.294014185517203]
本稿では、収束理論を準確率近似に拡張することを目的とする。
強化学習のためのグラデーションフリー最適化とポリシー勾配アルゴリズムへの応用について説明する。
論文 参考訳(メタデータ) (2020-09-30T04:44:45Z) - Extensions to the Proximal Distance Method of Constrained Optimization [7.813460653362097]
損失 $f(boldsymbolx)$ を S$ の $boldsymbolx の形に制約する問題について検討する。
融合制約は、滑らかさ、疎さ、あるいはより一般的な制約パターンをキャプチャすることができる。
論文 参考訳(メタデータ) (2020-09-02T03:32:41Z) - Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and
ReLUs under Gaussian Marginals [49.60752558064027]
ガウス境界の下では、半空間とReLUを不可知的に学習する基本的な問題について検討する。
我々の下限は、これらのタスクの現在の上限が本質的に最良のものであるという強い証拠を与える。
論文 参考訳(メタデータ) (2020-06-29T17:10:10Z) - Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
論文 参考訳(メタデータ) (2020-05-29T07:20:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。