論文の概要: S-ADDOPT: Decentralized stochastic first-order optimization over
directed graphs
- arxiv url: http://arxiv.org/abs/2005.07785v3
- Date: Wed, 22 Jul 2020 19:15:28 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-02 23:00:40.265664
- Title: S-ADDOPT: Decentralized stochastic first-order optimization over
directed graphs
- Title（参考訳）: S-ADDOPT:有向グラフ上の分散確率的一階最適化
- Authors: Muhammad I. Qureshi, Ran Xin, Soummya Kar, and Usman A. Khan
- Abstract要約: 有向ネットワークノード上に分散する関数のスムーズかつ高コストな関数の和を最小化するために,分散凸最適化を提案する。
特に,各ノードに1次オラクルを仮定するtextbftextttS-ADDOPTアルゴリズムを提案する。
崩壊するステップサイズ$mathcalO (1/k)$に対して、textbfttS-ADDOPT が$mathcalO (1/k)$ で正解に達し、その収束はネットワーク非依存であることを示す。
- 参考スコア（独自算出の注目度）: 16.96562173221624
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this report, we study decentralized stochastic optimization to minimize a
sum of smooth and strongly convex cost functions when the functions are
distributed over a directed network of nodes. In contrast to the existing work,
we use gradient tracking to improve certain aspects of the resulting algorithm.
In particular, we propose the~\textbf{\texttt{S-ADDOPT}} algorithm that assumes
a stochastic first-order oracle at each node and show that for a constant
step-size~$\alpha$, each node converges linearly inside an error ball around
the optimal solution, the size of which is controlled by~$\alpha$. For decaying
step-sizes~$\mathcal{O}(1/k)$, we show that~\textbf{\texttt{S-ADDOPT}} reaches
the exact solution sublinearly at~$\mathcal{O}(1/k)$ and its convergence is
asymptotically network-independent. Thus the asymptotic behavior
of~\textbf{\texttt{S-ADDOPT}} is comparable to the centralized stochastic
gradient descent. Numerical experiments over both strongly convex and
non-convex problems illustrate the convergence behavior and the performance
comparison of the proposed algorithm.
- Abstract（参考訳）: 本稿では,ノードの有向ネットワーク上に分散する関数のスムーズかつ強凸なコスト関数の和を最小化する分散確率最適化について検討する。
既存の研究とは対照的に、我々は勾配追跡を用いて、結果のアルゴリズムの特定の側面を改善する。
特に,各ノードの確率的一階オラクルを仮定する~\textbf{\texttt{S-ADDOPT}}アルゴリズムを提案し,各ノードが最適解の周りの誤差球内に直線的に収束し,そのサイズは~$\alpha$によって制御されることを示す。
分解ステップサイズ~$\mathcal{o}(1/k)$ に対して、~\textbf{\texttt{s-addopt}} は−$\mathcal{o}(1/k)$ で完全解に到達し、その収束は漸近的にネットワークに依存しない。
したがって、~\textbf{\texttt{S-ADDOPT}} の漸近挙動は集中確率勾配勾配に匹敵する。
強凸問題と非凸問題の両方に対する数値実験は,提案アルゴリズムの収束挙動と性能比較を示している。
関連論文リスト
- Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
複素勾配問題に対する2つの分散化ZO推定器を提案する。
我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
論文 参考訳（メタデータ） (2024-10-03T15:04:01Z) - Graphon Particle Systems, Part II: Dynamics of Distributed Stochastic Continuum Optimization [5.685037987395183]
ノード連続体を持つグラフオン上での分散最適化問題について検討する。
グラノン上での勾配降下と勾配追従アルゴリズムを提案する。
時間変化アルゴリズムを適切に選択することにより、すべてのノードの状態が接続されたグラフに対して$mathcalLinfty$-consensusを達成することを示す。
論文 参考訳（メタデータ） (2024-07-03T02:47:39Z) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。
本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文 参考訳（メタデータ） (2022-07-18T12:03:26Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳（メタデータ） (2022-06-17T06:10:20Z) - Stochastic Zeroth order Descent with Structured Directions [10.604744518360464]
我々は, 有限差分法であるStructured Zeroth Order Descent (SSZD)を導入・解析し, 集合 $lleq d 方向の勾配を近似し, $d は周囲空間の次元である。
凸凸に対して、すべての$c1/2$に対して$O( (d/l) k-c1/2$)$ 上の関数の収束はほぼ確実に証明する。
論文 参考訳（メタデータ） (2022-06-10T14:00:06Z) - Convergence Analysis of Nonconvex Distributed Stochastic Zeroth-order
Coordinate Method [3.860616339202303]
本稿では,$ZOn$局所コスト関数の合計により形成されるグローバルコスト関数を最小化する分散非最適化問題について検討する。
エージェントは問題を解くためにzo座標法を近似する。
論文 参考訳（メタデータ） (2021-03-24T03:07:46Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。
我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。
有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
論文 参考訳（メタデータ） (2020-08-28T14:46:56Z) - 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) - Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。
特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
論文 参考訳（メタデータ） (2020-02-10T23:23:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。