論文の概要: High-Probability Bounds for SGD under the Polyak-Lojasiewicz Condition with Markovian Noise

• arxiv url: http://arxiv.org/abs/2603.14514v1
• Date: Sun, 15 Mar 2026 17:50:03 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-17 16:19:35.861458
• Title: High-Probability Bounds for SGD under the Polyak-Lojasiewicz Condition with Markovian Noise
• Title（参考訳）: マルコフ雑音を伴うポリアク・ロジャシエヴィチ条件下でのSGDの高確率境界
• Authors: Avik Kar, Siddharth Chandak, Rahul Singh, Eric Moulines, Shalabh Bhatnagar, Nicholas Bambos,
• Abstract要約: PL条件下でのSGDの1次均一時間高確率結合について検討し, 勾配雑音はマルコフ差成分とマルティンゲール差成分の両方を含むことを示した。 これはPL条件が多くの機械学習モデルやディープラーニングモデルで生じるため、有限時間保証の範囲を大幅に広げる。
• 参考スコア（独自算出の注目度）: 27.3629260943211
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present the first uniform-in-time high-probability bound for SGD under the PL condition, where the gradient noise contains both Markovian and martingale difference components. This significantly broadens the scope of finite-time guarantees, as the PL condition arises in many machine learning and deep learning models while Markovian noise naturally arises in decentralized optimization and online system identification problems. We further allow the magnitude of noise to grow with the function value, enabling the analysis of many practical sampling strategies. In addition to the high-probability guarantee, we establish a matching $1/k$ decay rate for the expected suboptimality. Our proof technique relies on the Poisson equation to handle the Markovian noise and a probabilistic induction argument to address the lack of almost-sure bounds on the objective. Finally, we demonstrate the applicability of our framework by analyzing three practical optimization problems: token-based decentralized linear regression, supervised learning with subsampling for privacy amplification, and online system identification.
• Abstract（参考訳）: PL条件下でのSGDの1次均一時間高確率結合について検討し, 勾配雑音はマルコフ差成分とマルティンゲール差成分の両方を含むことを示した。 これはPL条件が多くの機械学習モデルやディープラーニングモデルで発生するのに対して、マルコフのノイズは分散最適化やオンラインシステム識別問題で自然に発生するため、有限時間保証の範囲を大きく広げる。 さらに、関数値によって雑音の大きさが大きくなることを許容し、多くの実用的なサンプリング戦略の分析を可能にする。 高確率保証に加えて、期待される準最適度に対して、一致する1/k$の減衰率を確立する。 我々の証明手法は、マルコフ雑音を扱うためにポアソン方程式と、目的のほとんど余剰境界の欠如に対処するための確率的帰納論に依存する。 最後に、トークンベースの分散線形回帰、プライバシー増幅のためのサブサンプリングによる教師付き学習、オンラインシステム識別の3つの実用的な最適化問題を解析して、フレームワークの適用性を示す。

関連論文リスト

• Decoded Quantum Interferometry Under Noise [4.180458188910334]
  雑音下でのデコード量子干渉法(DQI)の厳密な解析について述べる。 最大線形充足性問題に対して、ノイズの存在下では、性能はインスタンス行列の雑音重み付き空間パラメータによって制御されることを示す。 現実雑音下でのDQIの潜在的な量子優位性を維持するためのガイダンスを提供する。
  論文  参考訳（メタデータ） (2025-08-14T15:08:09Z)
• Differentially Private Clipped-SGD: High-Probability Convergence with Arbitrary Clipping Level [18.723330586196997]
  本研究では,DPのクリッピングレベルが固定された最初の高確率収束解析法を提案する。 提案手法は,固定クリッピングレベルにおいて,既存の方法よりも高速に近傍最適解に収束することを示す。 この地区は、DPが導入した騒音とバランスが取れており、収束速度とプライバシー保証のトレードオフが洗練されている。
  論文  参考訳（メタデータ） (2025-07-31T12:48:29Z)
• CoLiDE: Concomitant Linear DAG Estimation [12.415463205960156]
  観測データから線形方程式への非巡回グラフ構造学習の問題に対処する。 本稿では,空間認識学習DAGのための新しい凸スコア関数を提案する。
  論文  参考訳（メタデータ） (2023-10-04T15:32:27Z)
• First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities [91.46841922915418]
  本稿では,一階変分法の理論解析のための統一的アプローチを提案する。 提案手法は非線形勾配問題とモンテカルロの強い問題の両方をカバーする。 凸法最適化問題の場合、オラクルに強く一致するような境界を与える。
  論文  参考訳（メタデータ） (2023-05-25T11:11:31Z)
• Log Barriers for Safe Black-box Optimization with Application to Safe Reinforcement Learning [72.97229770329214]
  本稿では,学習時の安全性維持が不可欠である高次元非線形最適化問題に対する一般的なアプローチを提案する。 LBSGDと呼ばれるアプローチは、慎重に選択されたステップサイズで対数障壁近似を適用することに基づいている。 安全強化学習における政策課題の違反を最小限に抑えるためのアプローチの有効性を実証する。
  論文  参考訳（メタデータ） (2022-07-21T11:14:47Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。