論文の概要: Heavy-Tail Phenomenon in Decentralized SGD

• arxiv url: http://arxiv.org/abs/2205.06689v2
• Date: Mon, 16 May 2022 14:31:35 GMT
• ステータス: 処理完了
• システム内更新日: 2022-05-17 11:48:20.744122
• Title: Heavy-Tail Phenomenon in Decentralized SGD
• Title（参考訳）: 分散型SGDにおける重機現象
• Authors: Mert Gurbuzbalaban, Yuanhan Hu, Umut Simsekli, Kun Yuan, Lingjiong Zhu
• Abstract要約: 分散勾配降下(DE-SGD)における重鎖の出現について検討する。 また,分権化が尾の挙動に及ぼす影響についても検討した。 我々の理論は、テールとネットワーク構造の間の興味深い相互作用を明らかにする。
• 参考スコア（独自算出の注目度）: 33.63000461985398
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recent theoretical studies have shown that heavy-tails can emerge in stochastic optimization due to `multiplicative noise', even under surprisingly simple settings, such as linear regression with Gaussian data. While these studies have uncovered several interesting phenomena, they consider conventional stochastic optimization problems, which exclude decentralized settings that naturally arise in modern machine learning applications. In this paper, we study the emergence of heavy-tails in decentralized stochastic gradient descent (DE-SGD), and investigate the effect of decentralization on the tail behavior. We first show that, when the loss function at each computational node is twice continuously differentiable and strongly convex outside a compact region, the law of the DE-SGD iterates converges to a distribution with polynomially decaying (heavy) tails. To have a more explicit control on the tail exponent, we then consider the case where the loss at each node is a quadratic, and show that the tail-index can be estimated as a function of the step-size, batch-size, and the topological properties of the network of the computational nodes. Then, we provide theoretical and empirical results showing that DE-SGD has heavier tails than centralized SGD. We also compare DE-SGD to disconnected SGD where nodes distribute the data but do not communicate. Our theory uncovers an interesting interplay between the tails and the network structure: we identify two regimes of parameters (stepsize and network size), where DE-SGD can have lighter or heavier tails than disconnected SGD depending on the regime. Finally, to support our theoretical results, we provide numerical experiments conducted on both synthetic data and neural networks.
• Abstract（参考訳）: 近年の理論的研究により、ガウスデータによる線形回帰のような驚くほど単純な設定でも「乗法雑音」による確率的最適化において重項が現れることが示されている。 これらの研究はいくつかの興味深い現象を明らかにしているが、現代の機械学習アプリケーションで自然に発生する分散型設定を除外する従来の確率最適化問題を考察している。 本稿では,分散確率勾配降下(de-sgd)におけるヘビーテールの出現と,分散がテール挙動に及ぼす影響について検討する。 まず、各計算ノードの損失関数がコンパクト領域の外側で連続的に微分可能であり、強い凸であるとき、DEC-SGDの法則は多項式的に減衰する(重)尾を持つ分布に収束することを示す。 次に,各ノードにおける損失が二次的である場合について,より明示的な制御を行うために,各ノードのネットワークのステップサイズ,バッチサイズ,および位相特性の関数としてテールインデックスを推定可能であることを示す。 次に,D-SGDが集中型SGDよりも重い尾を持つことを示す理論的,実証的な結果を示す。 また,ノードがデータを分散するが通信しない非分離sgdと比較した。 我々の理論は、テールとネットワーク構造の間の興味深い相互作用を明らかにしている: ステップサイズとネットワークサイズ(de-sgdが、レジームに応じて切断されたsgdよりも軽いかより重いテールを持つことができる2つのパラメータのレジーム(ステップサイズとネットワークサイズ)を識別する。 最後に, 理論的結果を支援するため, 合成データとニューラルネットワークの両方で数値実験を行った。

関連論文リスト

• Stability and Generalization of the Decentralized Stochastic Gradient Descent Ascent Algorithm [80.94861441583275]
  本稿では,分散勾配勾配(D-SGDA)アルゴリズムの一般化境界の複雑さについて検討する。 本研究は,D-SGDAの一般化における各因子の影響を解析した。 また、最適凸凹設定を得るために一般化とバランスをとる。
  論文  参考訳（メタデータ） (2023-10-31T11:27:01Z)
• Approximate Heavy Tails in Offline (Multi-Pass) Stochastic Gradient Descent [33.9917975060585]
  オフライン(マルチパスとも呼ばれる)SGDの定常分布は「近似的な」パワーローテールを示す。 データポイントの数が増加するにつれて、オフラインのSGDはますます「大義的」に振る舞うのが主な特徴です。
  論文  参考訳（メタデータ） (2023-10-27T20:06:03Z)
• Differentially Private Non-convex Learning for Multi-layer Neural Networks [35.24835396398768]
  本稿では,単一出力ノードを持つ(多層)完全連結ニューラルネットワークに対する差分的タンジェント最適化の問題に焦点をあてる。 ニューラルカーネル理論の最近の進歩を利用して、サンプルサイズとネットワーク幅の両方が十分に大きい場合に、最初の過剰人口リスクを提供する。
  論文  参考訳（メタデータ） (2023-10-12T15:48:14Z)
• Law of Balance and Stationary Distribution of Stochastic Gradient Descent [11.937085301750288]
  我々は、損失関数が再スケーリング対称性を含む場合、勾配降下(SGD)のミニバッチノイズが平衡解に対する解を正則化することを証明した。 次に、任意の深さと幅を持つ対角線ネットワークの勾配流の定常分布を導出する。 これらの現象はディープ・ネットワークに独自に存在することが示され、ディープ・モデルと浅瀬モデルの間に根本的な違いが示唆される。
  論文  参考訳（メタデータ） (2023-08-13T03:13:03Z)
• Machine learning in and out of equilibrium [58.88325379746631]
  我々の研究は、統計物理学から適応したフォッカー・プランク法を用いて、これらの平行線を探索する。 我々は特に、従来のSGDでは平衡が切れている長期的限界におけるシステムの定常状態に焦点を当てる。 本稿では,ミニバッチの置き換えを伴わない新しいランゲヴィンダイナミクス(SGLD)を提案する。
  論文  参考訳（メタデータ） (2023-06-06T09:12:49Z)
• Decentralized SGD and Average-direction SAM are Asymptotically Equivalent [101.37242096601315]
  分散勾配降下(D-SGD)は、中央サーバを制御せずに大規模デバイス上で協調学習を可能にする。 既存の理論では、分散化は必ず一般化される。
  論文  参考訳（メタデータ） (2023-06-05T14:19:52Z)
• BCD Nets: Scalable Variational Approaches for Bayesian Causal Discovery [97.79015388276483]
  構造方程式モデル(SEM)は、有向非巡回グラフ(DAG)を介して表される因果関係を推論する効果的な枠組みである。 近年の進歩により、観測データからDAGの有効最大点推定が可能となった。 線形ガウス SEM を特徴付ける DAG 上の分布を推定するための変分フレームワークである BCD Nets を提案する。
  論文  参考訳（メタデータ） (2021-12-06T03:35:21Z)
• Mean-field Analysis of Piecewise Linear Solutions for Wide ReLU Networks [83.58049517083138]
  勾配勾配勾配を用いた2層ReLUネットワークについて検討する。 SGDは単純な解に偏りがあることが示される。 また,データポイントと異なる場所で結び目が発生するという経験的証拠も提供する。
  論文  参考訳（メタデータ） (2021-11-03T15:14:20Z)
• On the Double Descent of Random Features Models Trained with SGD [78.0918823643911]
  勾配降下(SGD)により最適化された高次元におけるランダム特徴(RF)回帰特性について検討する。 本研究では, RF回帰の高精度な非漸近誤差境界を, 定常および適応的なステップサイズSGD設定の下で導出する。 理論的にも経験的にも二重降下現象を観察する。
  論文  参考訳（メタデータ） (2021-10-13T17:47:39Z)
• The Heavy-Tail Phenomenon in SGD [7.366405857677226]
  最小損失のHessianの構造に依存すると、SGDの反復はエンフェビーテールの定常分布に収束する。 深層学習におけるSGDの行動に関する知見に分析結果を変換する。
  論文  参考訳（メタデータ） (2020-06-08T16:43:56Z)

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

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