論文の概要: High-Probability Convergence of SGD via Batched Updates

• arxiv url: http://arxiv.org/abs/2609.12765v1
• Date: Fri, 11 Sep 2026 12:17:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-15 07:38:31.738057
• Title: High-Probability Convergence of SGD via Batched Updates
• Title（参考訳）: バッチ更新によるSGDの高確率収束
• Abstract要約: Batched SGDは、オンラインエポックを最適化に反復するシンプルなバリエーションである。 我々の主な貢献は、このメカニズムが驚くほど単純な高確率解析を可能にすることを示している。
• 参考スコア（独自算出の注目度）: 4.862625283098196
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Stochastic gradient descent (SGD) is the primary workhorse for large-scale optimization. While the average behavior of its iterates, typically characterized by mean-squared error bounds, is well-understood, obtaining high-probability guarantees for the last iterate remains challenging. Prior approaches to this problem have either imposed restrictive assumptions (such as bounded domains or gradients) or relied on complex proofs involving auxiliary sequences. In this work, we propose Batched SGD, a simple variant that partitions online samples into epochs and performs a single update per epoch using a refined, low-variance gradient estimate. Our main contribution demonstrates that this batching mechanism enables a surprisingly simple high-probability analysis that avoids both restrictive assumptions and auxiliary sequences. Under standard smoothness and norm-sub-Gaussian noise assumptions, we establish near-optimal rates for both strongly convex and non-convex objectives. Furthermore, we show that our batching idea extends naturally to federated learning (FL). We provide the first high-probability guarantees for FL, achieving logarithmic communication complexity, linear speedup in the number of agents, and resilience to data heterogeneity.
• Abstract（参考訳）: 確率勾配勾配勾配(SGD)は大規模最適化のための主要な作業場である。 平均二乗誤差境界を特徴とするイテレートの平均挙動はよく理解されているが、最後のイテレートに対する高い確率保証を得ることは依然として困難である。 この問題に対する以前のアプローチは、制限的な仮定(有界領域や勾配など)を課すか、あるいは補助列を含む複素証明に依存するかのどちらかであった。 本研究では,オンラインサンプルをエポックに分割し,改良された低分散勾配推定を用いてエポック毎に1回の更新を行う,シンプルな変種であるBatched SGDを提案する。 我々の主な貢献は、このバッチリング機構が、制限的な仮定と補助的なシーケンスの両方を避ける、驚くほど単純な高確率解析を可能にすることを示しています。 標準の滑らかさとノルム・サブ・ガウス雑音の仮定の下では、強い凸と非凸の両方の目的に対して、ほぼ最適な速度を確立する。 さらに,我々のバッチ化のアイデアは,フェデレートラーニング(FL)に自然に及んでいることを示す。 FLに対する最初の高確率保証、対数通信の複雑性の実現、エージェント数の線形高速化、データの不均一性に対するレジリエンスを提供する。

関連論文リスト

• Beyond Optimal Rates in Stochastic Optimization: Trajectory-Adaptive Stopping Rules [42.38093055717409]
  我々は、新しい信頼系列法と、適応されたプロセスに対する時間一様経験的バーンスタイン不等式を開発する。 結果の停止規則は、自然勾配の地平線より少ない数桁の順序を必要とすることが示される。
  論文  参考訳（メタデータ） (2026-08-26T09:02:46Z)
• Sharp Convergence Rates for Masked Diffusion Models [53.117058231393834]
  制約を克服するオイラー法に対する全変分に基づく解析法を開発した。 その結果、スコア推定の仮定を緩和し、パラメータ依存性を改善し、収束保証を確立する。 全体としては,CTMC軌道に沿った直接テレビによる誤り分解と,FHSのためのデカップリングに基づく経路解析を導入している。
  論文  参考訳（メタデータ） (2026-02-26T00:47:51Z)
• Stopping Rules for Stochastic Gradient Descent via Anytime-Valid Confidence Sequences [51.56484100374058]
  凸最適化のための勾配降下(SGD)の停止規則について検討した。 我々は、投影されたSGDの重み付き平均準最適度に対して、任意の有意、データ依存の高信頼シーケンスを開発する。 これらは、厳格でタイムユニフォームなパフォーマンス保証と、有限時間$varepsilon$-optimality証明書である。
  論文  参考訳（メタデータ） (2025-12-15T09:26:45Z)
• From Gradient Clipping to Normalization for Heavy Tailed SGD [19.369399536643773]
  最近の実証的な証拠は、機械学習の応用が重尾ノイズを伴い、実際に有界分散の標準的な仮定に挑戦していることを示している。 本稿では, 勾配依存型雑音収束問題において, テール雑音下での厳密性を実現することができることを示す。
  論文  参考訳（メタデータ） (2024-10-17T17:59:01Z)
• Faster Convergence of Stochastic Accelerated Gradient Descent under Interpolation [51.248784084461334]
  我々はNesterov加速度アンダーホ条件の一般化版に対する新しい収束率を証明した。 本分析により, 従来の研究に比べて, 強い成長定数への依存度を$$$から$sqrt$に下げることができた。
  論文  参考訳（メタデータ） (2024-04-03T00:41:19Z)
• Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems [56.86067111855056]
  構造密度の重み付き雑音によるクリップ最適化問題を考察する。 勾配が有限の順序モーメントを持つとき、$mathcalO(K-(alpha - 1)/alpha)$よりも高速な収束率が得られることを示す。 得られた推定値が無視可能なバイアスと制御可能な分散を持つことを示す。
  論文  参考訳（メタデータ） (2023-11-07T17:39:17Z)
• Large deviations rates for stochastic gradient descent with strongly convex functions [11.247580943940916]
  勾配降下を伴う一般高確率境界の研究のための公式な枠組みを提供する。 強い凸関数を持つSGDの上限となる大きな偏差が見つかる。
  論文  参考訳（メタデータ） (2022-11-02T09:15:26Z)
• Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noise [64.85879194013407]
  単調なVIPと非単調なVIPの解法における信頼度に対数的依存を持つ最初の高確率結果が証明された。 この結果は光尾の場合で最もよく知られたものと一致し,非単調な構造問題に新鮮である。 さらに,多くの実用的な定式化の勾配雑音が重く,クリッピングによりSEG/SGDAの性能が向上することを示す。
  論文  参考訳（メタデータ） (2022-06-02T15:21:55Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• Generalizing Variational Autoencoders with Hierarchical Empirical Bayes [6.273154057349038]
  確率的生成モデルのための計算的に安定なフレームワークである階層的経験的ベイズオートエンコーダ(HEBAE)を提案する。 鍵となる貢献は2つであり、まず、符号化分布を階層的に優先することで、再構成損失関数の最小化と過正規化の回避とのトレードオフを適応的にバランスさせることで、利益を得る。
  論文  参考訳（メタデータ） (2020-07-20T18:18:39Z)

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

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