論文の概要: The case for and against fixed step-size: Stochastic approximation algorithms in optimization and machine learning
- arxiv url: http://arxiv.org/abs/2309.02944v3
- Date: Wed, 03 Sep 2025 02:47:11 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-09-04 21:40:46.163868
- Title: The case for and against fixed step-size: Stochastic approximation algorithms in optimization and machine learning
- Title（参考訳）: 確率近似アルゴリズムの最適化と機械学習への応用
- Authors: Caio Kalil Lauand, Ioannis Kontoyiannis, Sean Meyn,
- Abstract要約: 近似の理論と応用は、最適化と強化学習の応用により、ますます関連性が高まっている。
本稿では, ステップサイズ$alpha>0$のSAを再帰で定義し, $$theta_n+1 = theta_n+ alpha f(theta_n,Phi_n+1)$$$, $theta_ninmathbbRd$と$Phi_n$をマルコフ連鎖とする。
- 参考スコア（独自算出の注目度）: 6.416429054645991
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Theory and application of stochastic approximation (SA) have become increasingly relevant due in part to applications in optimization and reinforcement learning. This paper takes a new look at SA with constant step-size $\alpha>0$, defined by the recursion, $$\theta_{n+1} = \theta_{n}+ \alpha f(\theta_n,\Phi_{n+1})$$ in which $\theta_n\in\mathbb{R}^d$ and $\{\Phi_{n}\}$ is a Markov chain. The goal is to approximately solve root finding problem $\bar{f}(\theta^*)=0$, where $\bar{f}(\theta)=\mathbb{E}[f(\theta,\Phi)]$ and $\Phi$ has the steady-state distribution of $\{\Phi_{n}\}$. The following conclusions are obtained under an ergodicity assumption on the Markov chain, compatible assumptions on $f$, and for $\alpha>0$ sufficiently small: $\textbf{1.}$ The pair process $\{(\theta_n,\Phi_n)\}$ is geometrically ergodic in a topological sense. $\textbf{2.}$ For every $1\le p\le 4$, there is a constant $b_p$ such that $\limsup_{n\to\infty}\mathbb{E}[\|\theta_n-\theta^*\|^p]\le b_p \alpha^{p/2}$ for each initial condition. $\textbf{3.}$ The Polyak-Ruppert-style averaged estimates $\theta^{\text{PR}}_n=n^{-1}\sum_{k=1}^{n}\theta_k$ converge to a limit $\theta^{\text{PR}}_\infty$ almost surely and in mean square, which satisfies $\theta^{\text{PR}}_\infty=\theta^*+\alpha \bar{\Upsilon}^*+O(\alpha^2)$ for an identified non-random $\bar{\Upsilon}^*\in\mathbb{R}^d$. Moreover, the covariance is approximately optimal: The limiting covariance matrix of $\theta{\text PR}_n$ is approximately minimal in a matricial sense. The two main take-aways for practitioners are application-dependent. It is argued that, in applications to optimization, constant gain algorithms may be preferable even when the objective has multiple local minima; while a vanishing gain algorithm is preferable in applications to reinforcement learning due to the presence of bias.
- Abstract（参考訳）: 確率近似(SA)の理論と応用は、最適化と強化学習の応用により、ますます関連性が高まっている。
本稿では, ステップサイズが一定となる$\alpha>0$, 再帰で定義される$$\theta_{n+1} = \theta_{n}+ \alpha f(\theta_n,\Phi_{n+1})$$$ ここでは$\theta_n\in\mathbb{R}^d$, $\{\Phi_{n}\}$はマルコフ連鎖である。
ここで、$\bar{f}(\theta)=\mathbb{E}[f(\theta,\Phi)]$と$\Phi$は$\{\Phi_{n}\}$の定常分布を持つ。
次の結論はマルコフ連鎖上のエルゴード性仮定の下で得られ、$f$ と $\alpha>0$ に対する互換仮定は十分小さい: $\textbf{1.}$ 対プロセス $\{(\theta_n,\Phi_n)\}$ は位相的意味で幾何学的にエルゴード的である。
$\textbf{2.}$ すべての$\le p\le 4$に対して、各初期条件に対して$\limsup_{n\to\infty}\mathbb{E}[\|\theta_n-\theta^*\|^p]\le b_p \alpha^{p/2}$となるような定数$b_p$が存在する。
$\textbf{3.}$ The Polyak-Ruppert-style averaged estimates $\theta^{\text{PR}}_n=n^{-1}\sum_{k=1}^{n}\theta_k$ converge to a limit $\theta^{\text{PR}}_\infty$ almost surely and in mean square, which satisf $\theta^{\text{PR}}_\infty=\theta^*+\alpha \bar{\Upsilon}^*+O(\alpha^2)$ for an identified non-random $\bar{\Upsilon}^*\in\mathbb{R}^d$。
さらに、共分散は概して最適である:$\theta{\text PR}_n$ の制限共分散行列は、マトリカルな意味では、ほぼ最小である。
実践者のための2つの主要なテイクアウトは、アプリケーション依存である。
最適化への応用においては、目的が複数の局所最小値を持つ場合でも一定のゲインアルゴリズムが好まれるが、バイアスの存在による強化学習への応用においては、消滅ゲインアルゴリズムが好まれる。
関連論文リスト
- Online Covariance Estimation in Nonsmooth Stochastic Approximation [14.818683408659764]
非滑らかな変分包含問題を解くために近似法(SA)を適用することを検討する。
我々の収束構造は、統計的推定法で最もよく知られているものを確立する。
論文 参考訳（メタデータ） (2025-02-07T20:16:51Z) - Convergence of Adam Under Relaxed Assumptions [72.24779199744954]
我々は、アダムがより現実的な条件下で、$O(epsilon-4)$勾配複雑性で$epsilon$-定常点に収束することを示している。
また、Adamの分散還元版を$O(epsilon-3)$の加速勾配複雑性で提案する。
論文 参考訳（メタデータ） (2023-04-27T06:27:37Z) - Kernel-based off-policy estimation without overlap: Instance optimality
beyond semiparametric efficiency [53.90687548731265]
本研究では,観測データに基づいて線形関数を推定するための最適手順について検討する。
任意の凸および対称函数クラス $mathcalF$ に対して、平均二乗誤差で有界な非漸近局所ミニマックスを導出する。
論文 参考訳（メタデータ） (2023-01-16T02:57:37Z) - Off-policy estimation of linear functionals: Non-asymptotic theory for
semi-parametric efficiency [59.48096489854697]
観測データに基づいて線形汎関数を推定する問題は、因果推論と包帯文献の両方において標準的である。
このような手順の平均二乗誤差に対して非漸近上界を証明した。
非漸近的局所ミニマックス下限をマッチングすることにより、有限標本のインスタンス依存最適性を確立する。
論文 参考訳（メタデータ） (2022-09-26T23:50:55Z) - Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with
Variance Reduction and its Application to Optimization [50.83356836818667]
勾配ランゲヴィン・ダイナミクスは非エプス最適化問題を解くための最も基本的なアルゴリズムの1つである。
本稿では、このタイプの2つの変種、すなわち、分散還元ランジュバンダイナミクスと再帰勾配ランジュバンダイナミクスを示す。
論文 参考訳（メタデータ） (2022-03-30T11:39:00Z) - Benign Overfitting of Constant-Stepsize SGD for Linear Regression [122.70478935214128]
帰納バイアスは 経験的に過剰フィットを防げる中心的存在です
この研究は、この問題を最も基本的な設定として考慮している: 線形回帰に対する定数ステップサイズ SGD。
我々は、(正規化されていない)SGDで得られるアルゴリズム正則化と、通常の最小二乗よりも多くの顕著な違いを反映する。
論文 参考訳（メタデータ） (2021-03-23T17:15:53Z) - Binary Classification of Gaussian Mixtures: Abundance of Support
Vectors, Benign Overfitting and Regularization [39.35822033674126]
生成ガウス混合モデルに基づく二項線形分類について検討する。
後者の分類誤差に関する新しい非漸近境界を導出する。
この結果は, 確率が一定である雑音モデルに拡張される。
論文 参考訳（メタデータ） (2020-11-18T07:59:55Z) - Sample Complexity Bounds for Two Timescale Value-based Reinforcement
Learning Algorithms [65.09383385484007]
2つの時間スケール近似(SA)は、値に基づく強化学習アルゴリズムで広く使われている。
本稿では,2つの時間スケール線形および非線形TDCとGreedy-GQアルゴリズムの漸近収束率について検討する。
論文 参考訳（メタデータ） (2020-11-10T11:36:30Z) - Convergence Analysis of Riemannian Stochastic Approximation Schemes [39.32179384256228]
本稿では,最適化問題に取り組むための相関近似 (SA) スキームのクラスを解析する。
得られた条件は, 従来よりかなり軽度であることを示す。
第3に、平均場関数を小さなバイアスにしか推定できない場合、および/または、サンプルが鎖から引き出される場合を考える。
論文 参考訳（メタデータ） (2020-05-27T11:24:58Z) - On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and
Non-Asymptotic Concentration [115.1954841020189]
The inequality and non-asymptotic properties of approximation procedure with Polyak-Ruppert averaging。
一定のステップサイズと無限大となる反復数を持つ平均的反復数に対する中心極限定理(CLT)を証明する。
論文 参考訳（メタデータ） (2020-04-09T17:54:18Z) - Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis [102.29671176698373]
我々は、割引決定過程における政策評価の問題に対処し、生成モデルの下で、ll_infty$errorに対するマルコフに依存した保証を提供する。
我々は、ポリシー評価のために、局所ミニマックス下限の両漸近バージョンと非漸近バージョンを確立し、アルゴリズムを比較するためのインスタンス依存ベースラインを提供する。
論文 参考訳（メタデータ） (2020-03-16T17:15:28Z) - A Precise High-Dimensional Asymptotic Theory for Boosting and
Minimum-$\ell_1$-Norm Interpolated Classifiers [3.167685495996986]
本稿では,分離可能なデータの強化に関する高精度な高次元理論を確立する。
統計モデルのクラスでは、ブースティングの普遍性誤差を正確に解析する。
また, 推力試験誤差と最適ベイズ誤差の関係を明示的に説明する。
論文 参考訳（メタデータ） (2020-02-05T00:24:53Z) - On Low-rank Trace Regression under General Sampling Distribution [9.699586426043885]
クロスバリデード推定器は一般仮定でほぼ最適誤差境界を満たすことを示す。
また, クロスバリデーション推定器はパラメータ選択理論に着想を得た手法よりも優れていることを示す。
論文 参考訳（メタデータ） (2019-04-18T02:56:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。