論文の概要: A hybrid variance-reduced method for decentralized stochastic non-convex
optimization
- arxiv url: http://arxiv.org/abs/2102.06752v1
- Date: Fri, 12 Feb 2021 20:13:05 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-16 15:53:42.490490
- Title: A hybrid variance-reduced method for decentralized stochastic non-convex
optimization
- Title（参考訳）: 分散確率非凸最適化のためのハイブリッド分散還元法
- Authors: Ran Xin and Usman A. Khan and Soummya Kar
- Abstract要約: textttGTHSGDアルゴリズムは、グローバルな勾配を追跡するためにネットワークを実装している。
textttGTHSGDは、必要なエラートレランス$epsilon$が十分小さいときに、ネットワークの複雑さを$O(n-1)$にします。
- 参考スコア（独自算出の注目度）: 15.447966950703947
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper considers decentralized stochastic optimization over a network
of~$n$ nodes, where each node possesses a smooth non-convex local cost function
and the goal of the networked nodes is to find an~$\epsilon$-accurate
first-order stationary point of the sum of the local costs. We focus on an
online setting, where each node accesses its local cost only by means of a
stochastic first-order oracle that returns a noisy version of the exact
gradient. In this context, we propose a novel single-loop decentralized hybrid
variance-reduced stochastic gradient method, called \texttt{GT-HSGD}, that
outperforms the existing approaches in terms of both the oracle complexity and
practical implementation. The \texttt{GT-HSGD} algorithm implements specialized
local hybrid stochastic gradient estimators that are fused over the network to
track the global gradient. Remarkably, \texttt{GT-HSGD} achieves a
network-independent oracle complexity of~$O(n^{-1}\epsilon^{-3})$ when the
required error tolerance~$\epsilon$ is small enough, leading to a linear
speedup with respect to the centralized optimal online variance-reduced
approaches that operate on a single node. Numerical experiments are provided to
illustrate our main technical results.
- Abstract（参考訳）: 本稿では,各ノードがスムーズな非凸局所コスト関数を持ち,ネットワークノードの目的が局所コストの和の−$\epsilon$-accurate 1次定常点を見つけることにある,−$n$ノードのネットワーク上の分散確率最適化について考察する。
我々は、各ノードが、正確な勾配のノイズバージョンを返す確率的な1次オラクルによってのみ、そのローカルコストにアクセスするオンライン設定に焦点を当てる。
そこで,本研究では,既存のアプローチを複雑性と実用性の両方で上回る,単一ループ分散分散型確率勾配法である \texttt{GT-HSGD} を提案する。
\texttt{GT-HSGD}アルゴリズムは、ネットワーク上に融合してグローバル勾配を追跡する特殊なローカルハイブリッド確率勾配推定器を実装している。
注目すべきことに、 \texttt{GT-HSGD} は、必要な誤差公差~$\epsilon$ が十分に小さい場合、ネットワークに依存しないオーラクル複雑性 _$O(n^{-1}\epsilon^{-3})$ を達成し、単一のノードで動作する集中型最適オンライン分散還元アプローチに関して線形速度アップをもたらす。
主な技術的結果を説明するために数値実験を行いました。
関連論文リスト
- Online Optimization Perspective on First-Order and Zero-Order Decentralized Nonsmooth Nonconvex Stochastic Optimization [8.670873561640903]
分散環境下での非平滑な非平滑な目的に対する(delta,,ilon$)-定常点の有限時間解析について検討する。
$Oは分散非滑らかな最適化のための最初の有限時間保証である。
論文 参考訳（メタデータ） (2024-06-03T16:09:34Z) - Decentralized Riemannian Algorithm for Nonconvex Minimax Problems [82.50374560598493]
ニューラルネットワークのためのミニマックスアルゴリズムは、多くの問題を解決するために開発された。
本稿では,2種類のミニマックスアルゴリズムを提案する。
そこで我々は, DRSGDAを提案し, 本手法が勾配を達成することを証明した。
論文 参考訳（メタデータ） (2023-02-08T01:42:45Z) - On the Effective Number of Linear Regions in Shallow Univariate ReLU
Networks: Convergence Guarantees and Implicit Bias [50.84569563188485]
我々は、ラベルが$r$のニューロンを持つターゲットネットワークの符号によって決定されるとき、勾配流が方向収束することを示す。
我々の結果は、標本サイズによらず、幅が$tildemathcalO(r)$である、緩やかなオーバーパラメータ化をすでに維持しているかもしれない。
論文 参考訳（メタデータ） (2022-05-18T16:57:10Z) - Escaping Saddle Points with Bias-Variance Reduced Local Perturbed SGD
for Communication Efficient Nonconvex Distributed Learning [58.79085525115987]
ローカル手法は通信時間を短縮する有望なアプローチの1つである。
局所的データセットが局所的損失の滑らかさよりも小さい場合,通信の複雑さは非局所的手法よりも優れていることを示す。
論文 参考訳（メタデータ） (2022-02-12T15:12:17Z) - Decentralized Multi-Task Stochastic Optimization With Compressed
Communications [22.31884634659446]
本稿では,ノードにおけるローカル情報可用性の2つのモデルに対して,アルゴリズムを開発し,性能バウンダリを求める。
グローバルな最小値からの逸脱と制約の違反は$mathcalO(T-frac12)$と$mathcalO(T-frac14)$によって上界されることを示す。
論文 参考訳（メタデータ） (2021-12-23T05:54:42Z) - Decentralized Stochastic Proximal Gradient Descent with Variance
Reduction over Time-varying Networks [30.231314171218994]
分散学習において、ノードのネットワークは、通常、その局所的な目的の有限サムである全体的な目的関数を最小化するために協力する。
そこで本研究では,分散縮小手法を利用して分散学習を高速化する新しいアルゴリズムDPSVRGを提案する。
論文 参考訳（メタデータ） (2021-12-20T08:23:36Z) - On Stochastic Moving-Average Estimators for Non-Convex Optimization [105.22760323075008]
本稿では,移動平均(SEMA)問題に基づく広く利用されている推定器のパワーを実証する。
これらすべてのアートな結果に対して、これらのアートな問題に対する結果も提示します。
論文 参考訳（メタデータ） (2021-04-30T08:50:24Z) - Byzantine-Resilient Non-Convex Stochastic Gradient Descent [61.6382287971982]
敵対的レジリエントな分散最適化。
機械は独立して勾配を計算し 協力することができます
私達のアルゴリズムは新しい集中の技術およびサンプル複雑性に基づいています。
それは非常に実用的です:それはないときすべての前の方法の性能を改善します。
セッティングマシンがあります。
論文 参考訳（メタデータ） (2020-12-28T17:19:32Z) - Fast decentralized non-convex finite-sum optimization with recursive
variance reduction [19.540926205375857]
本稿では,SARAH型分散低減技術を用いたGT-SARAHと呼ばれる一階勾配法について述べる。
特に、$n = O(Nfrac12(lambda)3)$のようなビッグデータでは、ネットワークの複雑さとは無関係に、この複雑さは$O(Nfrac12Lepsilon-2)$に減少する。
さらに、局所的なミニバッチサイズの適切な選択は、勾配複雑性と通信複雑性のトレードオフをバランスさせる。
論文 参考訳（メタデータ） (2020-08-17T15:51:32Z) - Fully Asynchronous Policy Evaluation in Distributed Reinforcement
Learning over Networks [14.636457985379746]
本稿では,有向ピアツーピアネットワーク上での分散強化学習(DisRL)のポリシー評価問題に対する非同期手法を提案する。
ネットワークの他のノードを待つことなく、各ノードは隣人からの(おそらく遅れた)情報を使用して、いつでもローカルに値関数を更新できる。
論文 参考訳（メタデータ） (2020-03-01T08:12:08Z) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳（メタデータ） (2019-12-26T22:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。