論文の概要: An Optimal Stochastic Algorithm for Decentralized Nonconvex Finite-sum
Optimization
- arxiv url: http://arxiv.org/abs/2210.13931v1
- Date: Tue, 25 Oct 2022 11:37:11 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-26 16:02:04.226124
- Title: An Optimal Stochastic Algorithm for Decentralized Nonconvex Finite-sum
Optimization
- Title（参考訳）: 分散非凸有限サム最適化のための最適確率アルゴリズム
- Authors: Luo Luo, Haishan Ye
- Abstract要約: 私たちは、DEARESTが少なくとも$mathcal O(+sqrtmnLvarepsilon-2)$ 1次オラクル(IFO)コールと$mathcal O(Lvarepsilon-2/sqrt1-lambda_W)$通信ラウンドを必要とすることを示す証拠を示します。
- 参考スコア（独自算出の注目度）: 25.21457349137344
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper studies the synchronized decentralized nonconvex optimization
problem of the form $\min_{x\in{\mathbb R}^d} f(x)\triangleq
\frac{1}{m}\sum_{i=1}^m f_i(x)$, where $f_i(x)\triangleq
\frac{1}{n}\sum_{j=1}^n f_{i,j}(x)$ is the local function on $i$-th agent of
the connected network. We propose a novel stochastic algorithm called
DEcentralized probAbilistic Recursive gradiEnt deScenT (DEAREST), which
integrates the techniques of variance reduction, gradient tracking and
multi-consensus. We construct a Lyapunov function that simultaneously
characterizes the function value, the gradient estimation error and the
consensus error for the convergence analysis. Based on this measure, we provide
a concise proof to show DEAREST requires at most ${\mathcal
O}(mn+\sqrt{mn}L\varepsilon^{-2})$ incremental first-order oracle (IFO) calls
and ${\mathcal O}(L\varepsilon^{-2}/\sqrt{1-\lambda_2(W)}\,)$ communication
rounds to find an $\varepsilon$-stationary point in expectation, where $L$ is
the smoothness parameter and $\lambda_2(W)$ is the second-largest eigenvalues
of the gossip matrix $W$. We can verify both of the IFO complexity and
communication complexity match the lower bounds. To the best of our knowledge,
DEAREST is the first optimal algorithm for decentralized nonconvex finite-sum
optimization.
- Abstract（参考訳）: 本稿では、$\min_{x\in{\mathbb R}^d} f(x)\triangleq \frac{1}{m}\sum_{i=1}^m f_i(x)$, ここで$f_i(x)\triangleq \frac{1}{n}\sum_{j=1}^n f_{i,j}(x)$は、接続ネットワークの$i$-thエージェント上の局所関数である。
分散化確率的再帰的グラディエント deScenT (DEAREST) と呼ばれる新しい確率的アルゴリズムを提案する。
我々は,関数値,勾配推定誤差,収束解析のコンセンサス誤差を同時に特徴付けるリアプノフ関数を構築する。
この尺度に基づいて、最善の要求を最大${\mathcal o}(mn+\sqrt{mn}l\varepsilon^{-2})$インクリメンタルファーストオーダーオラクル(ifo)コールと${\mathcal o}(l\varepsilon^{-2}/\sqrt{1-\lambda_2(w)}\,)$通信ラウンドが期待値の$\varepsilon$-stationary pointを見つけるために、$l$が滑らかさパラメータ、$\lambda_2(w)$が$w$の2番目に大きな固有値であることを示す簡潔な証明を提供する。
IFOの複雑さと通信の複雑さの両方が下限と一致することを検証できます。
我々の知る限りでは、DEARESTは分散化された非凸有限サム最適化のための最初の最適アルゴリズムである。
関連論文リスト
- 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) - Near-Optimal Distributed Minimax Optimization under the Second-Order Similarity [22.615156512223763]
本研究では,有限サム構造を目的とする分散楽観的すべり(SVOGS)法を提案する。
我々は$mathcal O(delta D2/varepsilon)$、$mathcal O(n+sqrtndelta D2/varepsilon)$、$tildemathcal O(n+sqrtndelta+L)D2/varepsilon)$の局所呼び出しを証明している。
論文 参考訳（メタデータ） (2024-05-25T08:34:49Z) - Nearly Optimal Regret for Decentralized Online Convex Optimization [53.433398074919]
分散オンライン凸最適化(D-OCO)は,局所計算と通信のみを用いて,グローバルな損失関数の列を最小化することを目的としている。
我々は凸関数と強い凸関数の残差をそれぞれ低減できる新しいD-OCOアルゴリズムを開発した。
我々のアルゴリズムは、$T$、$n$、$rho$の点でほぼ最適です。
論文 参考訳（メタデータ） (2024-02-14T13:44:16Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Near-Optimal Non-Convex Stochastic Optimization under Generalized
Smoothness [21.865728815935665]
2つの最近の研究は、$O(epsilon-3)$サンプル複雑性を確立し、$O(epsilon)$-定常点を得る。
しかし、どちらも$mathrmploy(epsilon-1)$という大きなバッチサイズを必要とする。
本研究では,STORMアルゴリズムの単純な変種を再検討することにより,従来の2つの問題を同時に解決する。
論文 参考訳（メタデータ） (2023-02-13T00:22:28Z) - ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。
我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-01-01T18:51:29Z) - An Efficient Stochastic Algorithm for Decentralized Nonconvex-Strongly-Concave Minimax Optimization [25.00475462213752]
Decentralized Recursive Dec. Method (DREAM)
具体的には、$mathcalO(minminappaappa3eps-3,kappa2N)$ one-order oracle (SFO)コールと$tildemathcalO(kappa2 epsilon-2)通信ラウンドが必要です。
我々の数値実験は,従来の手法の優越性を検証した。
論文 参考訳（メタデータ） (2022-12-05T16:09:39Z) - Decentralized Stochastic Variance Reduced Extragradient Method [25.21457349137344]
本稿では,$min_xmax_y fx,y triqfrac1msumi=1m f_i triqfrac1msumi=1m f_i triqfrac1msumi=1m f_i triqfrac1msumi=1m f_i triqfrac1msumiの分散凸-凹極小最適化問題を考察する。
論文 参考訳（メタデータ） (2022-02-01T16:06:20Z) - DoCoM: Compressed Decentralized Optimization with Near-Optimal Sample
Complexity [25.775517797956237]
本稿では,Douubly Compressed Momentum-assisted tracking algorithm $ttDoCoM$ for communicationを提案する。
我々のアルゴリズムは、実際にいくつかの最先端のアルゴリズムより優れていることを示す。
論文 参考訳（メタデータ） (2022-02-01T07:27:34Z) - Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$
Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。
損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文 参考訳（メタデータ） (2021-03-02T06:53:44Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。