論文の概要: Single-Timescale Multi-Sequence Stochastic Approximation Without Fixed Point Smoothness: Theories and Applications

• arxiv url: http://arxiv.org/abs/2410.13743v1
• Date: Thu, 17 Oct 2024 16:39:53 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-18 13:18:51.881742
• Title: Single-Timescale Multi-Sequence Stochastic Approximation Without Fixed Point Smoothness: Theories and Applications
• Title（参考訳）: 固定点平滑性のない単一時間マルチシーケンス確率近似:理論と応用
• Authors: Yue Huang, Zhaoxian Wu, Shiqian Ma, Qing Ling,
• Abstract要約: マルチシーケンス近似(Multi-sequence Approximation, SA)は、信号処理や機械学習の分野において、多列SA(Multi-sequence SA)として知られる複数の結合配列を含む。 固定点の滑らかさを仮定することなく,MSSAに対してより厳密な単一時間スケール解析を行う。 これらの理論的知見を双方向の最適化と通信効率のよい分散学習に適用することにより、性能保証を伴う緩和された仮定および/またはより単純なアルゴリズムを提供する。
• 参考スコア（独自算出の注目度）: 33.21958331056391
• License:
• Abstract: Stochastic approximation (SA) that involves multiple coupled sequences, known as multiple-sequence SA (MSSA), finds diverse applications in the fields of signal processing and machine learning. However, existing theoretical understandings {of} MSSA are limited: the multi-timescale analysis implies a slow convergence rate, whereas the single-timescale analysis relies on a stringent fixed point smoothness assumption. This paper establishes tighter single-timescale analysis for MSSA, without assuming smoothness of the fixed points. Our theoretical findings reveal that, when all involved operators are strongly monotone, MSSA converges at a rate of $\tilde{\mathcal{O}}(K^{-1})$, where $K$ denotes the total number of iterations. In addition, when all involved operators are strongly monotone except for the main one, MSSA converges at a rate of $\mathcal{O}(K^{-\frac{1}{2}})$. These theoretical findings align with those established for single-sequence SA. Applying these theoretical findings to bilevel optimization and communication-efficient distributed learning offers relaxed assumptions and/or simpler algorithms with performance guarantees, as validated by numerical experiments.
• Abstract（参考訳）: 確率近似(Stochastic Approximation、SA)は、マルチシーケンスSA(Multiple-Sequence SA、MSSA)として知られる複数の結合配列を含む、信号処理と機械学習の分野における多様な応用を見出す。 しかし、既存の理論的理解 {of} MSSA は限定的であり、マルチタイムスケール解析は収束速度が遅いことを意味し、一方シングルタイムスケール解析は厳密な不動点の滑らかさの仮定に依存している。 固定点の滑らかさを仮定することなく,MSSAに対してより厳密な単一時間スケール解析を行う。 我々の理論的な結果は、すべての作用素が強い単調であるとき、MSSAは$\tilde{\mathcal{O}}(K^{-1})$で収束し、ここでは$K$は反復の総数を表す。 さらに、すべての関連する作用素が主作用素を除いて強い単調であるとき、MSSAは$\mathcal{O}(K^{-\frac{1}{2}})$で収束する。 これらの理論的知見は, 単一系列SAで確立されたものと一致した。 これらの理論的な知見を双方向の最適化と通信効率のよい分散学習に適用することで、数値実験によって検証されるように、緩和された仮定および/または性能保証付きより単純なアルゴリズムを提供する。

関連論文リスト

• MGDA Converges under Generalized Smoothness, Provably [27.87166415148172]
  多目的最適化(MOO)はマルチタスク学習など様々な分野で注目を集めている。 最近の研究は、理論解析を伴う効果的なアルゴリズムを提供しているが、それらは標準の$L$-smoothあるいは有界勾配仮定によって制限されている。 一般化された$ell$-smooth損失関数のより一般的で現実的なクラスについて研究し、$ell$は勾配ノルムの一般非減少関数である。
  論文  参考訳（メタデータ） (2024-05-29T18:36:59Z)
• DASA: Delay-Adaptive Multi-Agent Stochastic Approximation [64.32538247395627]
  我々は,N$エージェントが並列に動作し,中央サーバと通信することで,一般的な近似問題を高速化することを目的とした設定を考える。 遅延とストラグラーの効果を軽減するために,マルチエージェント近似のための遅延適応アルゴリズムである textttDASA を提案する。
  論文  参考訳（メタデータ） (2024-03-25T22:49:56Z)
• Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling [73.5602474095954]
  マルコフサンプリングの遅延更新による近似スキームの非漸近的性能について検討した。 我々の理論的な発見は、幅広いアルゴリズムの遅延の有限時間効果に光を当てた。
  論文  参考訳（メタデータ） (2024-02-19T03:08:02Z)
• Metric Entropy-Free Sample Complexity Bounds for Sample Average Approximation in Convex Stochastic Programming [0.6906005491572401]
  本稿では,凸問題や強凸プログラミング(SP)問題におけるサンプル平均近似(SAA)について検討する。 SAAのサンプルの複雑さは、計量エントロピーの定量化から完全に解放されることを示している。
  論文  参考訳（メタデータ） (2024-01-01T04:35:53Z)
• A Convergence Theory for Federated Average: Beyond Smoothness [28.074273047592065]
  フェデレートラーニングにより、大量のエッジコンピューティングデバイスが、データ共有を併用せずにモデルを学習できるようになる。 この設定における主要なアルゴリズムとして、ローカルデバイス上でGradient Descent(SGD)を並列に実行するFederated Average FedAvgが広く使用されている。 本稿では,フェデレートラーニングに関する理論的収束研究について述べる。
  論文  参考訳（メタデータ） (2022-11-03T04:50:49Z)
• A Single-Timescale Analysis For Stochastic Approximation With Multiple Coupled Sequences [21.50207156675195]
  複数の結合配列を持つ非線形近似の有限時間収束について検討する。 我々の分析の核心は、多くの応用において保持される多列SAの固定点の滑らか性である。
  論文  参考訳（メタデータ） (2022-06-21T14:13:20Z)
• Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization [61.26619639722804]
  滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。 提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
  論文  参考訳（メタデータ） (2022-02-26T19:10:48Z)
• Variance-Reduced Splitting Schemes for Monotone Stochastic Generalized Equations [0.0]
  演算子を期待値とする単調な包摂問題を考える。 分割スキームの直接適用は、各ステップにおける期待値マップによる問題解決の必要性により複雑である。 本稿では,不確実性に対処する手法を提案する。
  論文  参考訳（メタデータ） (2020-08-26T02:33:27Z)
• Convergence of Meta-Learning with Task-Specific Adaptation over Partial Parameters [152.03852111442114]
  モデルに依存しないメタラーニング(MAML)は非常に成功したアルゴリズムメタラーニングの実践であるが、高い計算複雑性を持つ。 本稿では,その複雑さがANILの全体的な収束性能に大きく影響することを示す。
  論文  参考訳（メタデータ） (2020-06-16T19:57:48Z)
• Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition [52.08417569774822]
  本稿では,深層学習(深層AUC)により注目度が高まっている,円滑な非凹部min-max問題の解法に焦点をあてる。
  論文  参考訳（メタデータ） (2020-06-12T00:32:21Z)
• 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)

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

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