論文の概要: Fast decentralized non-convex finite-sum optimization with recursive
variance reduction
- arxiv url: http://arxiv.org/abs/2008.07428v6
- Date: Sat, 18 Sep 2021 17:26:49 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-28 03:44:38.530191
- Title: Fast decentralized non-convex finite-sum optimization with recursive
variance reduction
- Title（参考訳）: 再帰的分散低減による高速分散非凸有限和最適化
- Authors: Ran Xin and Usman A. Khan and Soummya Kar
- Abstract要約: 本稿では,SARAH型分散低減技術を用いたGT-SARAHと呼ばれる一階勾配法について述べる。
特に、$n = O(Nfrac12(lambda)3)$のようなビッグデータでは、ネットワークの複雑さとは無関係に、この複雑さは$O(Nfrac12Lepsilon-2)$に減少する。
さらに、局所的なミニバッチサイズの適切な選択は、勾配複雑性と通信複雑性のトレードオフをバランスさせる。
- 参考スコア（独自算出の注目度）: 19.540926205375857
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper considers decentralized minimization of $N:=nm$ smooth non-convex
cost functions equally divided over a directed network of $n$ nodes.
Specifically, we describe a stochastic first-order gradient method, called
GT-SARAH, that employs a SARAH-type variance reduction technique and gradient
tracking (GT) to address the stochastic and decentralized nature of the
problem. We show that GT-SARAH, with appropriate algorithmic parameters, finds
an $\epsilon$-accurate first-order stationary point with
$O\big(\max\big\{N^{\frac{1}{2}},n(1-\lambda)^{-2},n^{\frac{2}{3}}m^{\frac{1}{3}}(1-\lambda)^{-1}\big\}L\epsilon^{-2}\big)$
gradient complexity, where ${(1-\lambda)\in(0,1]}$ is the spectral gap of the
network weight matrix and $L$ is the smoothness parameter of the cost
functions. This gradient complexity outperforms that of the existing
decentralized stochastic gradient methods. In particular, in a big-data regime
such that ${n = O(N^{\frac{1}{2}}(1-\lambda)^{3})}$, this gradient complexity
furthers reduces to ${O(N^{\frac{1}{2}}L\epsilon^{-2})}$, independent of the
network topology, and matches that of the centralized near-optimal
variance-reduced methods. Moreover, in this regime GT-SARAH achieves a
non-asymptotic linear speedup, in that, the total number of gradient
computations at each node is reduced by a factor of $1/n$ compared to the
centralized near-optimal algorithms that perform all gradient computations at a
single node. To the best of our knowledge, GT-SARAH is the first algorithm that
achieves this property. In addition, we show that appropriate choices of local
minibatch size balance the trade-offs between the gradient and communication
complexity of GT-SARAH. Over infinite time horizon, we establish that all nodes
in GT-SARAH asymptotically achieve consensus and converge to a first-order
stationary point in the almost sure and mean-squared sense.
- Abstract（参考訳）: 本稿では,$N:=nm$スムーズな非凸コスト関数の分散最小化を,$n$ノードの有向ネットワーク上で等しく分割する。
具体的には,サラ型分散低減法(gt)と勾配追跡法(gt)を用いた確率的一階勾配法(gt-sarah)について述べる。
GT-SARAHは、適切なアルゴリズムパラメータで、$O\big(\max\big\{N^{\frac{1}{2}},n(1-\lambda)^{-2},n^{\frac{2}{3}}m^{\frac{1}{3}}(1-\lambda)^{-1}\big\}L\epsilon^{-2}\big)$勾配複雑性(${(1-\lambda)\in(0,1])$はネットワーク重み行列のスペクトルギャップであり、$L$はコスト関数の滑らか性パラメータであることを示す。
この勾配複雑性は、既存の分散確率勾配法よりも優れている。
特に、${n = o(n^{\frac{1}{2}}(1-\lambda)^{3})} のようなビッグ・データ・レジームでは、この勾配複雑性はネットワークトポロジとは独立に${o(n^{\frac{1}{2}}l\epsilon^{-2})} にさらに減少し、集中型オプティカルな分散削減法と一致する。
さらに、GT-SARAHは、非漸近線形高速化を実現し、各ノードでの勾配計算の総数は、単一のノードですべての勾配計算を実行する集中的近似アルゴリズムと比較して1/n$の係数で減少する。
我々の知る限り、GT-SARAHはこの特性を達成する最初のアルゴリズムである。
さらに,gt-sarahの勾配と通信複雑性のトレードオフは,局所的なミニバッチサイズの適切な選択と一致することを示す。
無限時間地平線上で、GT-SARAH のすべてのノードが漸近的にコンセンサスを達成し、ほぼ確実かつ平均二乗の意味で一階定常点に収束することを確立する。
関連論文リスト
- Graphon Particle Systems, Part II: Dynamics of Distributed Stochastic Continuum Optimization [5.685037987395183]
ノード連続体を持つグラフオン上での分散最適化問題について検討する。
グラノン上での勾配降下と勾配追従アルゴリズムを提案する。
時間変化アルゴリズムを適切に選択することにより、すべてのノードの状態が接続されたグラフに対して$mathcalLinfty$-consensusを達成することを示す。
論文 参考訳（メタデータ） (2024-07-03T02:47:39Z) - ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。
我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-01-01T18:51:29Z) - An Optimal Stochastic Algorithm for Decentralized Nonconvex Finite-sum
Optimization [25.21457349137344]
私たちは、DEARESTが少なくとも$mathcal O(+sqrtmnLvarepsilon-2)$ 1次オラクル(IFO)コールと$mathcal O(Lvarepsilon-2/sqrt1-lambda_W)$通信ラウンドを必要とすることを示す証拠を示します。
論文 参考訳（メタデータ） (2022-10-25T11:37:11Z) - Sharper Convergence Guarantees for Asynchronous SGD for Distributed and
Federated Learning [77.22019100456595]
通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。
本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。
また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
論文 参考訳（メタデータ） (2022-06-16T17:10:57Z) - A Variance Controlled Stochastic Method with Biased Estimation for
Faster Non-convex Optimization [0.0]
減少勾配(SVRG)の性能を向上させるために, 分散制御勾配(VCSG)という新しい手法を提案する。
ラムダ$はVCSGで導入され、SVRGによる分散の過剰還元を避ける。
$mathcalO(min1/epsilon3/2,n1/4/epsilon)$ 勾配評価の数。
論文 参考訳（メタデータ） (2021-02-19T12:22:56Z) - A hybrid variance-reduced method for decentralized stochastic non-convex
optimization [15.447966950703947]
textttGTHSGDアルゴリズムは、グローバルな勾配を追跡するためにネットワークを実装している。
textttGTHSGDは、必要なエラートレランス$epsilon$が十分小さいときに、ネットワークの複雑さを$O(n-1)$にします。
論文 参考訳（メタデータ） (2021-02-12T20:13:05Z) - A New Framework for Variance-Reduced Hamiltonian Monte Carlo [88.84622104944503]
分散還元型ハミルトン・モンテカルロ法 (HMC) の新たなフレームワークを提案し,$L$-smooth および $m$-strongly log-concave 分布からサンプリングする。
本研究では,SAGA法やSVRG法をベースとした非バイアス勾配推定器を用いて,バッチサイズを小さくすることで,高い勾配効率が得られることを示す。
総合的および実世界のベンチマークデータによる実験結果から、我々の新しいフレームワークは、完全な勾配と勾配HMCアプローチを著しく上回っていることが示された。
論文 参考訳（メタデータ） (2021-02-09T02:44:24Z) - Hybrid Stochastic-Deterministic Minibatch Proximal Gradient:
Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。
損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
論文 参考訳（メタデータ） (2020-09-18T02:18:44Z) - On the Almost Sure Convergence of Stochastic Gradient Descent in
Non-Convex Problems [75.58134963501094]
本稿では,勾配降下(SGD)の軌跡を解析する。
我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
論文 参考訳（メタデータ） (2020-06-19T14:11:26Z) - S-ADDOPT: Decentralized stochastic first-order optimization over
directed graphs [16.96562173221624]
有向ネットワークノード上に分散する関数のスムーズかつ高コストな関数の和を最小化するために,分散凸最適化を提案する。
特に,各ノードに1次オラクルを仮定するtextbftextttS-ADDOPTアルゴリズムを提案する。
崩壊するステップサイズ$mathcalO (1/k)$に対して、textbfttS-ADDOPT が$mathcalO (1/k)$ で正解に達し、その収束はネットワーク非依存であることを示す。
論文 参考訳（メタデータ） (2020-05-15T21:14:22Z) - Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。
特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
論文 参考訳（メタデータ） (2020-02-10T23:23:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。