論文の概要: Finite-Time Decoupled Convergence in Nonlinear Two-Time-Scale Stochastic
Approximation
- arxiv url: http://arxiv.org/abs/2401.03893v1
- Date: Mon, 8 Jan 2024 13:44:35 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-09 16:31:32.560040
- Title: Finite-Time Decoupled Convergence in Nonlinear Two-Time-Scale Stochastic
Approximation
- Title(参考訳): 非線形2時間スケール確率近似における有限時間デカップリング収束
- Authors: Yuze Han, Xiang Li, Zhihua Zhang
- Abstract要約: 本稿では,非線形二時間スケール近似における有限時間デカップリング収束の可能性について検討する。
分離収束は相変わらず実現可能であり、滑らか度パラメータに関連するステップサイズの選択に留意する。
- 参考スコア(独自算出の注目度): 30.313512704085184
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In two-time-scale stochastic approximation (SA), two iterates are updated at
varying speeds using different step sizes, with each update influencing the
other. Previous studies in linear two-time-scale SA have found that the
convergence rates of the mean-square errors for these updates are dependent
solely on their respective step sizes, leading to what is referred to as
decoupled convergence. However, the possibility of achieving this decoupled
convergence in nonlinear SA remains less understood. Our research explores the
potential for finite-time decoupled convergence in nonlinear two-time-scale SA.
We find that under a weaker Lipschitz condition, traditional analyses are
insufficient for achieving decoupled convergence. This finding is further
numerically supported by a counterexample. But by introducing an additional
condition of nested local linearity, we show that decoupled convergence is
still feasible, contingent on the appropriate choice of step sizes associated
with smoothness parameters. Our analysis depends on a refined characterization
of the matrix cross term between the two iterates and utilizes fourth-order
moments to control higher-order approximation errors induced by the local
linearity assumption.
- Abstract(参考訳): 2時間スケールの確率近似(sa)では、2つのイテレートが異なるステップサイズで異なる速度で更新され、それぞれの更新が他方に影響を与える。
線形二時間スケールsaにおける以前の研究では、これらの更新に対する平均二乗誤差の収束率は、それぞれのステップサイズのみに依存しており、分離収束と呼ばれる。
しかし、この分離収束を非線形saで達成する可能性はまだ分かっていない。
本研究は,非線形2時間スケールSAにおける有限時間疎結合収束の可能性を探る。
より弱いリプシッツ条件下では、従来の解析は疎収束を達成するには不十分である。
この発見は反例によってさらに数値的に支持される。
しかし,入れ子付き局所線形性の条件を付加することにより,分離収束は相変わらず実現可能であり,滑らか性パラメータに関連するステップサイズの選択が適切であることを示す。
本解析は, 2つのイテレート間の行列クロス項の洗練されたキャラクタリゼーションに依存し, 4次モーメントを用いて局所線形性仮定による高次近似誤差を制御する。
関連論文リスト
- Smoothing ADMM for Sparse-Penalized Quantile Regression with Non-Convex
Penalties [8.294148737585543]
本稿では,非二次絶対および非平滑収束ペナルティの存在下での凹凸および切断された量子レグレッションについて検討する。
本稿では,スパース回帰に特化してSIADと呼ばれるペナルティ乗算器が増加する新しいループADMアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-09-04T21:48:51Z) - Dynamics of correlation spreading in low-dimensional transverse-field
Ising models [0.0]
1(1D)と2次元(2D)における横場イジングモデルにおける磁気乱れ状態から始まる量子クエンチ後の相関の動的拡散について検討する。
いくつかの手法を用いて縦・横スピン相関関数を等時解析する。
本研究は, 将来のリブ・ロビンソン境界の相関拡散と理論的洗練に関する量子シミュレーション実験に有用なベンチマークを提供する。
論文 参考訳(メタデータ) (2023-01-04T02:02:21Z) - Fixed-Time Convergence for a Class of Nonconvex-Nonconcave Min-Max
Problems [5.787117733071416]
min-max問題を解くための固定時間収束サドル点力学系を開発した。
提案手法は他のどの状態法と比較しても高速に実現できる。
論文 参考訳(メタデータ) (2022-07-26T12:25:05Z) - Beyond the Edge of Stability via Two-step Gradient Updates [49.03389279816152]
Gradient Descent(GD)は、現代の機械学習の強力な仕事場である。
GDが局所最小値を見つける能力は、リプシッツ勾配の損失に対してのみ保証される。
この研究は、2段階の勾配更新の分析を通じて、単純だが代表的でありながら、学習上の問題に焦点をあてる。
論文 参考訳(メタデータ) (2022-06-08T21:32:50Z) - Superdiffusion in random two dimensional system with time-reversal
symmetry and long-range hopping [50.113286076477]
次元$d=2$とホッピング$V(r)proto r-2$の交叉系における局所化問題は、まだ解決されていない。
二次元異方性双極子-双極子相互作用によって決定されるホッピングには、弱い障害と強い障害の2つの区別可能な位相が存在することを示す。
論文 参考訳(メタデータ) (2022-05-29T16:53:20Z) - Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth
Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
本稿では,SGDA と SCO の最終的な収束保証として,期待されるコヒーレンシティ条件を導入し,その利点を説明する。
定常的なステップサイズを用いた場合、両手法の線形収束性を解の近傍に証明する。
我々の収束保証は任意のサンプリングパラダイムの下で保たれ、ミニバッチの複雑さに関する洞察を与える。
論文 参考訳(メタデータ) (2021-06-30T18:32:46Z) - On the Convergence of Stochastic Extragradient for Bilinear Games with
Restarted Iteration Averaging [96.13485146617322]
本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。
平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
論文 参考訳(メタデータ) (2021-06-30T17:51:36Z) - Sample Complexity Bounds for Two Timescale Value-based Reinforcement
Learning Algorithms [65.09383385484007]
2つの時間スケール近似(SA)は、値に基づく強化学習アルゴリズムで広く使われている。
本稿では,2つの時間スケール線形および非線形TDCとGreedy-GQアルゴリズムの漸近収束率について検討する。
論文 参考訳(メタデータ) (2020-11-10T11:36:30Z) - Nonlinear Two-Time-Scale Stochastic Approximation: Convergence and
Finite-Time Performance [1.52292571922932]
非線形2時間スケール近似の収束と有限時間解析について検討する。
特に,本手法は期待値の収束を$mathcalO (1/k2/3)$で達成し,$k$は反復数であることを示す。
論文 参考訳(メタデータ) (2020-11-03T17:43:39Z) - Linear Last-iterate Convergence in Constrained Saddle-point Optimization [48.44657553192801]
我々は、OGDA(Optimistic Gradient Descent Ascent)とOMWU(Optimistic Multiplicative Weights Update)に対する最終段階の独特さの理解を著しく拡大する。
平衡が一意である場合、線形終端収束は、値が普遍定数に設定された学習速度で達成されることを示す。
任意のポリトープ上の双線型ゲームがこの条件を満たすことを示し、OGDAは一意の平衡仮定なしで指数関数的に高速に収束することを示した。
論文 参考訳(メタデータ) (2020-06-16T20:53:04Z) - Consistent Online Gaussian Process Regression Without the Sample
Complexity Bottleneck [14.309243378538012]
本稿では,現在の後方中心のHellingerメトリックに対して,エラー近傍を修正可能なオンライン圧縮方式を提案する。
一定の誤差半径の場合、POG は集団後部の近傍 (Theorem 1(ii)) に収束するが、特徴空間の計量エントロピーによって決定される有限メモリのオン・ウォーストに収束する。
論文 参考訳(メタデータ) (2020-04-23T11:52:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。