論文の概要: Revisiting Step-Size Assumptions in Stochastic Approximation
- arxiv url: http://arxiv.org/abs/2405.17834v3
- Date: Fri, 01 Aug 2025 23:52:01 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-08-05 18:25:21.524489
- Title: Revisiting Step-Size Assumptions in Stochastic Approximation
- Title(参考訳): 確率近似におけるステップサイズ推定の再検討
- Authors: Caio Kalil Lauand, Sean Meyn,
- Abstract要約: この仮定は、収束とより微細な結果には必要ないことが初めて示される。
標準アルゴリズムおよびPolyakとRuppertの平均化手法を用いて得られた推定値に対して収束率を求める。
数値実験の結果,乗法雑音とマルコフ記憶の組み合わせにより,$beta_theta$が大きくなる可能性が示唆された。
- 参考スコア(独自算出の注目度): 1.3654846342364308
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Many machine learning and optimization algorithms are built upon the framework of stochastic approximation (SA), for which the selection of step-size (or learning rate) $\{\alpha_n\}$ is crucial for success. An essential condition for convergence is the assumption that $\sum_n \alpha_n = \infty$. Moreover, in all theory to date it is assumed that $\sum_n \alpha_n^2 < \infty$ (the sequence is square summable). In this paper it is shown for the first time that this assumption is not required for convergence and finer results. The main results are restricted to the special case $\alpha_n = \alpha_0 n^{-\rho}$ with $\rho \in (0,1)$. The theory allows for parameter dependent Markovian noise as found in many applications of interest to the machine learning and optimization research communities. Rates of convergence are obtained for the standard algorithm, and for estimates obtained via the averaging technique of Polyak and Ruppert. $\bullet$ Parameter estimates converge with probability one, and in $L_p$ for any $p\ge 1$. Moreover, the rate of convergence of the the mean-squared error (MSE) is $O(\alpha_n)$, which is improved to $O(\max\{ \alpha_n^2,1/n \})$ with averaging. Finer results are obtained for linear SA: $\bullet$ The covariance of the estimates is optimal in the sense of prior work of Polyak and Ruppert. $\bullet$ Conditions are identified under which the bias decays faster than $O(1/n)$. When these conditions are violated, the bias at iteration $n$ is approximately $\beta_\theta\alpha_n$ for a vector $\beta_\theta$ identified in the paper. Results from numerical experiments illustrate that $\beta_\theta$ may be large due to a combination of multiplicative noise and Markovian memory.
- Abstract(参考訳): 多くの機械学習と最適化アルゴリズムは確率近似(SA)の枠組みに基づいて構築されており、ステップサイズ(または学習率)$\{\alpha_n\}$の選択は成功に不可欠である。
収束の必須条件は、$\sum_n \alpha_n = \infty$ という仮定である。
さらに、今までのすべての理論において、$\sum_n \alpha_n^2 < \infty$(この列は正方和である)と仮定される。
本稿では、この仮定が収束およびより微細な結果に必要ではないことを初めて示す。
主な結果は特殊ケース $\alpha_n = \alpha_0 n^{-\rho}$ と $\rho \in (0,1)$ に制限される。
この理論は、機械学習と最適化研究コミュニティへの関心の多くの応用で見られるパラメータ依存マルコフ雑音を許容する。
標準アルゴリズムおよびPolyakとRuppertの平均化手法を用いて得られた推定値に対して収束率を求める。
$\bullet$パラメータ推定は確率 1 と収束し、任意の$p\ge 1$に対して$L_p$となる。
さらに、平均二乗誤差(MSE)の収束率は$O(\alpha_n)$であり、平均化により$O(\max\{ \alpha_n^2,1/n \})$に改善される。
線形 SA: $\bullet$ 推定の共分散は、Polyak と Ruppert の以前の仕事という意味で最適である。
$\bullet$条件は、そのバイアスが$O(1/n)$よりも早く減衰する条件である。
これらの条件が破られた場合、反復$n$のバイアスは約$\beta_\theta\alpha_n$ for a vector $\beta_\theta$ in the paper。
数値実験の結果,乗法ノイズとマルコフメモリの組み合わせにより,$\beta_\theta$が大きくなる可能性が示唆された。
関連論文リスト
- Allocating Variance to Maximize Expectation [2.25491649634702]
ガウス確率変数の系列の上限を最大化するための効率的な近似アルゴリズムを設計する。
このような期待問題は、ユーティリティオークションから、定量的遺伝学の混合モデルを学ぶことまで、様々な応用で発生する。
論文 参考訳(メタデータ) (2025-02-25T18:59:46Z) - Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳(メタデータ) (2024-08-16T02:33:07Z) - Robust Distribution Learning with Local and Global Adversarial Corruptions [17.22168727622332]
誤差を$sqrtvarepsilon k + rho + tildeO(dsqrtkn-1/(k lor2)$で有界な共分散を持つ場合、効率的な有限サンプルアルゴリズムを開発する。
我々の効率的な手順は、理想的だが難解な2-ワッサーシュタイン射影推定器の新たなトレースノルム近似に依存する。
論文 参考訳(メタデータ) (2024-06-10T17:48:36Z) - On the $O(\frac{\sqrt{d}}{T^{1/4}})$ Convergence Rate of RMSProp and Its Momentum Extension Measured by $\ell_1$ Norm [59.65871549878937]
本稿では、RMSPropとその運動量拡張を考察し、$frac1Tsum_k=1Tの収束速度を確立する。
我々の収束率は、次元$d$を除くすべての係数に関して下界と一致する。
収束率は$frac1Tsum_k=1Tと類似していると考えられる。
論文 参考訳(メタデータ) (2024-02-01T07:21:32Z) - Solving Dense Linear Systems Faster Than via Preconditioning [1.8854491183340518]
我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$であることを示す。
特に、我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$である。
主アルゴリズムはランダム化ブロック座標降下法とみなすことができる。
論文 参考訳(メタデータ) (2023-12-14T12:53:34Z) - Finite-Sample Symmetric Mean Estimation with Fisher Information Rate [15.802475232604667]
未知の分散-$sigma2$分布の意味は、分散$fracsigma2n$とほぼ対応する準ガウス速度を持つ$n$サンプルから推定できる。
f$が翻訳で知られている場合、$frac1nmathcal I$に改善することができる。
論文 参考訳(メタデータ) (2023-06-28T21:31:46Z) - High-dimensional Location Estimation via Norm Concentration for Subgamma
Vectors [15.802475232604667]
位置推定では、既知の分布から$n$のサンプルが与えられます。
漸近的に、最大推定は誤差$mathcal N(0, frac1nmathcal I)$のクラム・ラオ境界を達成する。
我々は、Emphsmoothed estimator を用いて、$mathcal I_r$, the Fisher information of the $r$-smoothed の有限$n$の誤差を束縛する理論を構築した。
論文 参考訳(メタデータ) (2023-02-05T22:17:04Z) - A spectral least-squares-type method for heavy-tailed corrupted
regression with unknown covariance \& heterogeneous noise [2.019622939313173]
重み付き最小二乗線形回帰は、少なくとも$epsilon n$ arbitrary outliersの$n$のラベル特徴サンプルを破損させたと仮定して再検討する。
本稿では,$(Sigma,Xi) や $Xi$ の演算ノルムに関する知識を前提に,電力法に基づくほぼ最適に計算可能な推定器を提案する。
論文 参考訳(メタデータ) (2022-09-06T23:37:31Z) - Finite-Sample Maximum Likelihood Estimation of Location [16.44999338864628]
固定$f$ の場合、最大類似度推定 (MLE) は infty$ に対して$n の極限で最適であることが知られている。
任意の$f$と$n$について、滑らかな$f$のフィッシャー情報に基づいて同様の理論を復元できることを示し、そこでは滑らかな半径が$n$で崩壊する。
論文 参考訳(メタデータ) (2022-06-06T04:33:41Z) - TURF: A Two-factor, Universal, Robust, Fast Distribution Learning
Algorithm [64.13217062232874]
最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。
本稿では,この数値をほぼ最適に推定する手法を提案する。
論文 参考訳(メタデータ) (2022-02-15T03:49:28Z) - Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。
我々はこの$d$への依存が対数的要因まで最適であることを示す。
また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
論文 参考訳(メタデータ) (2021-11-09T00:20:01Z) - 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) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳(メタデータ) (2020-06-06T13:34:41Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳(メタデータ) (2020-04-16T19:16:38Z) - Agnostic Q-learning with Function Approximation in Deterministic
Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。
もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
論文 参考訳(メタデータ) (2020-02-17T18:41:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。