論文の概要: An improved convergence analysis for decentralized online stochastic
non-convex optimization
- arxiv url: http://arxiv.org/abs/2008.04195v2
- Date: Tue, 29 Dec 2020 02:20:10 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-31 22:46:52.639736
- Title: An improved convergence analysis for decentralized online stochastic
non-convex optimization
- Title（参考訳）: 分散オンライン確率的非凸最適化のための収束解析の改良
- Authors: Ran Xin, Usman A. Khan, and Soummya Kar
- Abstract要約: 本稿では,GT-Loakjasiewics(GT-Loakjasiewics)と呼ばれる手法が,GT-Loakjasiewics(GT-Loakjasiewics)が現在の収束率を満たすことを示す。
結果はすぐに適用できるだけでなく、現在知られている最高の収束率にも適用できる。
- 参考スコア（独自算出の注目度）: 17.386715847732468
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we study decentralized online stochastic non-convex
optimization over a network of nodes. Integrating a technique called gradient
tracking in decentralized stochastic gradient descent, we show that the
resulting algorithm, GT-DSGD, enjoys certain desirable characteristics towards
minimizing a sum of smooth non-convex functions. In particular, for general
smooth non-convex functions, we establish non-asymptotic characterizations of
GT-DSGD and derive the conditions under which it achieves network-independent
performances that match the centralized minibatch SGD. In contrast, the
existing results suggest that GT-DSGD is always network-dependent and is
therefore strictly worse than the centralized minibatch SGD. When the global
non-convex function additionally satisfies the Polyak-Lojasiewics (PL)
condition, we establish the linear convergence of GT-DSGD up to a steady-state
error with appropriate constant step-sizes. Moreover, under stochastic
approximation step-sizes, we establish, for the first time, the optimal global
sublinear convergence rate on almost every sample path, in addition to the
asymptotically optimal sublinear rate in expectation. Since strongly convex
functions are a special case of the functions satisfying the PL condition, our
results are not only immediately applicable but also improve the currently
known best convergence rates and their dependence on problem parameters.
- Abstract（参考訳）: 本稿では,ノードネットワーク上での分散オンライン確率的非凸最適化について検討する。
分散確率勾配降下における勾配追跡と呼ばれる手法を統合することで, 結果のアルゴリズムであるGT-DSGDが, 滑らかな非凸関数の和を最小化する上で, 望ましい特性を享受できることが分かる。
特に,一般の滑らかな非凸関数に対して,gt-dsgd の非漸近的特徴付けを確立し,集中型ミニバッチ sgd に適合するネットワーク独立な性能を実現する条件を導出する。
対照的に、既存の結果はGT-DSGDが常にネットワークに依存していることを示唆している。
大域的非凸関数がさらにpolyak-lojasiewics (pl)条件を満たすとき、gt-dsgdの線形収束を適切な定数のステップサイズを持つ定常誤差まで確立する。
さらに, 確率近似ステップサイズの下では, 期待値における漸近的最適部分線形率に加えて, ほぼすべてのサンプルパス上の最適大域的部分線形収束率を初めて確立する。
強凸関数はpl条件を満たす関数の特別な場合であるため,本手法は直ちに適用できるだけでなく,現在知られている最良収束率とその問題パラメータ依存性も改善する。
関連論文リスト
- Achieving Near-Optimal Convergence for Distributed Minimax Optimization with Adaptive Stepsizes [22.022674600775993]
分散ミニマックス問題に直接適応的手法を適用することで,非収束性が得られることを示す。
追跡追跡プロトコルを用いた分散分散分散ミニマックス法であるD-AdaSTを提案する。
論文 参考訳（メタデータ） (2024-06-05T04:54:36Z) - Convergence of mean-field Langevin dynamics: Time and space
discretization, stochastic gradient, and variance reduction [49.66486092259376]
平均場ランゲヴィンダイナミクス(英: mean-field Langevin dynamics、MFLD)は、分布依存のドリフトを含むランゲヴィン力学の非線形一般化である。
近年の研究では、MFLDは測度空間で機能するエントロピー規則化された凸関数を地球規模で最小化することが示されている。
有限粒子近似,時間分散,勾配近似による誤差を考慮し,MFLDのカオスの均一時間伝播を示す枠組みを提供する。
論文 参考訳（メタデータ） (2023-06-12T16:28:11Z) - On Convergence of Incremental Gradient for Non-Convex Smooth Functions [63.51187646914962]
機械学習とネットワーク最適化では、ミスの数と優れたキャッシュを最小化するため、シャッフルSGDのようなアルゴリズムが人気である。
本稿では任意のデータ順序付けによる収束特性SGDアルゴリズムについて述べる。
論文 参考訳（メタデータ） (2023-05-30T17:47:27Z) - Fully Stochastic Trust-Region Sequential Quadratic Programming for
Equality-Constrained Optimization Problems [62.83783246648714]
目的と決定論的等式制約による非線形最適化問題を解くために,逐次2次プログラミングアルゴリズム(TR-StoSQP)を提案する。
アルゴリズムは信頼領域半径を適応的に選択し、既存の直線探索StoSQP方式と比較して不確定なヘッセン行列を利用することができる。
論文 参考訳（メタデータ） (2022-11-29T05:52:17Z) - Tackling benign nonconvexity with smoothing and stochastic gradients [28.197694894254305]
非最適化問題は機械学習、特にディープラーニングでは一般的な問題である。
本稿では,そのような問題を解決するために勾配勾配勾配を利用する方法を示す。
論文 参考訳（メタデータ） (2022-02-18T07:27:32Z) - Optimal Rates for Random Order Online Optimization [60.011653053877126]
敵が損失関数を選択できるカテットガルバー2020onlineについて検討するが、一様にランダムな順序で提示される。
2020onlineアルゴリズムが最適境界を達成し,安定性を著しく向上することを示す。
論文 参考訳（メタデータ） (2021-06-29T09:48:46Z) - A Retrospective Approximation Approach for Smooth Stochastic
Optimization [0.2867517731896504]
グラディエント(グラディエント、英: Gradient、SG)とは、最適化(SO)問題をスムーズ(ノンフィクション)な目標値で解くための補足的反復手法である。
論文 参考訳（メタデータ） (2021-03-07T16:29:36Z) - A fast randomized incremental gradient method for decentralized
non-convex optimization [19.540926205375857]
我々は,GT-SAGA GTSAGAと呼ばれる単一時間ランダム化手法を,バッチ・ノン有限サム文脈問題に対して解析する。
GT-SAGAのほぼ確実に1次勾配定常点への収束を示す。
論文 参考訳（メタデータ） (2020-11-07T21:30:42Z) - ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。
我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。
有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
論文 参考訳（メタデータ） (2020-08-28T14:46:56Z) - SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and
Interpolation [17.199023009789308]
予想されるSGD(SGD)の仮定は、非アーティザン関数に対して日常的に使われている。
本稿では,スムーズな非線形設定への収束のパラダイムを示す。
また,異なるステップサイズ条件の理論的保証も提供する。
論文 参考訳（メタデータ） (2020-06-18T07:05:56Z) - Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses [52.039438701530905]
任意のリプシッツ非平滑凸損失に対して,数種類の勾配勾配降下(SGD)に対して,鋭い上下境界を与える。
我々の限界は、極端に過剰な集団リスクを伴う、微分的にプライベートな非平滑凸最適化のための新しいアルゴリズムを導出することを可能にする。
論文 参考訳（メタデータ） (2020-06-12T02:45:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。