論文の概要: High-Probability PL-SGD with Markovian Noise: Optimal Mixing and Tail Dependence
- arxiv url: http://arxiv.org/abs/2606.26316v1
- Date: Wed, 24 Jun 2026 19:00:56 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-26 18:46:32.060382
- Title: High-Probability PL-SGD with Markovian Noise: Optimal Mixing and Tail Dependence
- Title（参考訳）: マルコフ雑音による高確率PL-SGD:最適混合と土壌依存性
- Abstract要約: マルコフ連鎖によって試料が生成された場合,ポリアク・オジャシエヴィチ(PL)条件を満たす目的の1次法について検討した。
ライトテール設定では、標準成長エンベロープスケールの通常のグラディエントD(SGD)に対して、以前の均一時間高確率境界を$widetildeO(t_mix/k)$とする。
我々は、この混合時間に対する線形依存が、持続的2で駆動される二次目的物上の一致する$(2 t_mix/k)$下界によって最適であることを示す。
- 参考スコア（独自算出の注目度）: 41.64418624570687
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study first-order methods for smooth objectives satisfying the Polyak-Łojasiewicz (PL) condition when gradient samples are generated by an exogenous Markov chain. In the light-tailed setting, prior uniform-in-time high-probability bounds for ordinary Stochastic Gradient Descent (SGD) under a standard growth envelope scale as $\widetilde{O}(t_{mix}^2/k)$, leaving a gap with the $\widetilde{O}(t_{mix}/k)$ expectation bounds. We close this gap using a lag-blocking argument to establish a uniform high-probability guarantee with a leading stochastic term of $\widetilde{O}(t_{mix}/(k+K_0))$ under geometric mixing. We prove this linear dependence on the mixing time is optimal via a matching $Ω(σ^2 t_{mix}/k)$ lower bound on a quadratic objective driven by a persistent two-state chain. We then extend this framework to heavy-tailed Markovian gradients satisfying a stationary finite-$p$-moment condition, $p \in (1,2]$. We design an all-samples clipped block method that uses every Markov transition while mitigating Markovian bias. Under a transition budget $T$, this algorithm achieves a high-probability stochastic error of $\widetilde{O}(σ_p^2(t_{mix}/T)^{2(p-1)/p})$. We establish a matching lower bound by reducing PL optimization to heavy-tailed mean estimation for a sticky Markov chain. Ultimately, this work tightly characterizes the optimal polynomial dependence on mixing time for light-tailed PL-SGD, and the optimal heavy-tail exponent and effective-sample-size dependence in the robust regime.
- Abstract（参考訳）: マルコフ連鎖によって勾配試料が生成されるとき, ポリアック・オジャシエヴィチ (PL) 条件を満たすスムーズな目的のための一階法について検討した。
光尾設定では、標準成長包絡スケール$\widetilde{O}(t_{mix}^2/k)$で、通常の確率勾配 Descent (SGD) に対する以前の均一時間高確率境界は$\widetilde{O}(t_{mix}^2/k)$であり、$\widetilde{O}(t_{mix}/k)$期待境界とのギャップを残している。
このギャップは、ラグブロッキング(lag-blocking)の引数を用いて、均一な高確率保証を確立するために、幾何混合の下で、$\widetilde{O}(t_{mix}/(k+K_0)$の確率項で閉じる。
この混合時間に対する線形依存は、持続的な二状態連鎖によって駆動される二次的対象上の$Ω(σ^2 t_{mix}/k)$下界によって最適であることを示す。
すると、このフレームワークを、定常有限$p$-モーメント条件、$p \in (1,2]$を満たす重尾のマルコフ勾配に拡張する。
マルコフバイアスを緩和しつつ,すべてのマルコフ遷移を利用する全サンプルクリッピングブロック法を設計する。
遷移予算$T$では、このアルゴリズムは$\widetilde{O}(σ_p^2(t_{mix}/T)^{2(p-1)/p})$の高確率確率確率誤差を達成する。
ステッキーマルコフ連鎖に対する重み付き平均推定にPL最適化を還元することにより、一致した下界を確立する。
最終的に、この研究は、光尾PL-SGDの混合時間に対する最適多項式依存と、ロバストな状態における最適重テール指数と有効サンプルサイズ依存を強く特徴づける。
関連論文リスト
- Variance-Reduced Conditional Gradient Methods under Markovian Sampling for Nonconvex Composite Optimization [0.0]
我々は,1つのエルゴード連鎖に対する非制約モンテカルロ最適化を新たに提案する。
特に、一般化されたCarlo-Wolfevious gradient $MC-ALFCFCを用いてプロジェクションフリー設定に対処する。
本手法は,期待されるサンプルの複雑さを$widetildeO(_mathrmmix2G_+_mathrmmix5G_2)varepsilon-3+_mathrmmix5varepsilon-2で実現することを示す。
論文 参考訳（メタデータ） (2026-07-28T14:37:47Z) - A Single Stepsize Suffices for Unprojected Linear TD(0): Simultaneous Robust and Fast Rates via Polyak--Ruppert Averaging [11.513419525702924]
我々は、Polyak-Ruppert平均化を用いた非計画的TD(0)アルゴリズムの高確率保証を提供する。
この結果に基づいて,PR平均に対する同時高確率収束保証を確立する。
論文 参考訳（メタデータ） (2026-06-23T13:37:01Z) - Finite-Depth, Finite-Shot Guarantees for Constrained Quantum Optimization via Fejér Filtering [0.2578242050187029]
本研究では, 高調波格子に対するコスト角の制限は, コスト相ユニタリ$U_C()=e-iH_C$ emphin に作用する正のFejérフィルタを公開することを示す。
ラップされた位相分離条件の下では、最適解をサンプリングする成功確率について、エンフェディメンションのない有限深度と有限ショットの下界が得られる。
論文 参考訳（メタデータ） (2026-03-02T12:44:19Z) - Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
一般的な嗜好を伴う文脈的オンラインRLHFの問題を考える。
一般化された双線形選好モデルを用いて、低ランクなスキュー対称行列による選好を捉える。
グリーディポリシーの双対ギャップは推定誤差の正方形によって有界であることを示す。
論文 参考訳（メタデータ） (2026-02-26T15:27:53Z) - Discrete Double-Bracket Flows for Isotropic-Noise Invariant Eigendecomposition [7.186083931122418]
本研究では,行列ベクトル積 (MVP) のオラクルによる行列フリー固有分解について検討した。
標準的な近似法では、安定性を$|C_k|$に結合する固定ステップを使用するか、あるいは更新の消滅によって遅くなる適応ステップを使用する。
対角化目標と入力-状態安定性解析のための厳密なサドルと、トレースフリーな摂動の下での複雑さのスケーリングを$O(|C_e|2 / (2))$とすることで、グローバル収束を確立する。
論文 参考訳（メタデータ） (2026-02-14T13:09:29Z) - Can SGD Handle Heavy-Tailed Noise? [6.111519084375339]
Gradient Descent (SGD) は大規模最適化のための機械学習プロジェクトであるが、重尾雑音下での理論的挙動は理解されていない。
このような悪条件下でSGDが確実に成功できるかどうかを精査する。
論文 参考訳（メタデータ） (2025-08-06T20:09:41Z) - Nonlinear Stochastic Gradient Descent and Heavy-tailed Noise: A Unified Framework and High-probability Guarantees [56.80920351680438]
本研究では,重音の存在下でのオンライン学習における高確率収束について検討する。
ノイズモーメントを仮定することなく、幅広い種類の非線形性を保証する。
論文 参考訳（メタデータ） (2024-10-17T18:25:28Z) - Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems [56.86067111855056]
構造密度の重み付き雑音によるクリップ最適化問題を考察する。
勾配が有限の順序モーメントを持つとき、$mathcalO(K-(alpha - 1)/alpha)$よりも高速な収束率が得られることを示す。
得られた推定値が無視可能なバイアスと制御可能な分散を持つことを示す。
論文 参考訳（メタデータ） (2023-11-07T17:39:17Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳（メタデータ） (2022-06-17T06:10:20Z) - Optimal and instance-dependent guarantees for Markovian linear stochastic approximation [47.912511426974376]
標準スキームの最後の繰り返しの2乗誤差に対して、$t_mathrmmix tfracdn$の非漸近境界を示す。
マルコフ雑音による政策評価について,これらの結果のまとめを導出する。
論文 参考訳（メタデータ） (2021-12-23T18:47:50Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳（メタデータ） (2020-06-04T17:51:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。