論文の概要: 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は分散化された非凸有限サム最適化のための最初の最適アルゴリズムである。
関連論文リスト
- Complexity of Minimizing Projected-Gradient-Dominated Functions with Stochastic First-order Oracles [38.45952947660789]
本稿では,$(alpha,tau,mathcal)$-projected-dominanceプロパティの下で関数を最小化する一階法の性能限界について検討する。
論文 参考訳（メタデータ） (2024-08-03T18:34:23Z) - 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) - Optimal and Efficient Algorithms for Decentralized Online Convex Optimization [51.00357162913229]
分散オンライン凸最適化(D-OCO)は、局所計算と通信のみを用いて、グローバルな損失関数の列を最小化するように設計されている。
我々は,凸関数と強凸関数の残差を$tildeO(nrho-1/4sqrtT)$と$tildeO(nrho-1/2log T)$に削減できる新しいD-OCOアルゴリズムを開発した。
我々の分析によると、射影自由多様体は$O(nT3/4)$と$O(n)を達成できる。
論文 参考訳（メタデータ） (2024-02-14T13:44:16Z) - On the Complexity of Finite-Sum Smooth Optimization under the
Polyak-{\L}ojasiewicz Condition [14.781921087738967]
本稿では、$min_bf xinmathbb Rd f(bf x)triangleq frac1nsum_i=1n f_i(bf x)$, ここで、$f(cdot)$はパラメータ$mu$と$f_i(cdot)_i=1n$は$L$-mean-squared smoothである。
論文 参考訳（メタデータ） (2024-02-04T17:14:53Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。
我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-01-01T18:51:29Z) - Optimal Gradient Sliding and its Application to Distributed Optimization
Under Similarity [121.83085611327654]
積 $r:=p + q$, ここで$r$は$mu$-strong convex類似性である。
エージェントの通信やローカルコールにマスターされた問題を解決する方法を提案する。
提案手法は$mathcalO(sqrtL_q/mu)$法よりもはるかにシャープである。
論文 参考訳（メタデータ） (2022-05-30T14:28:02Z) - Sharper Rates for Separable Minimax and Finite Sum Optimization via
Primal-Dual Extragradient Methods [39.87865197769047]
分離可能なミニマックス最適化問題 $min_x max_y f(x) - g(y) + h(x, y)$, where $f$ and $g$ have smoothness and strong convexity parameters $(Lx, mux)$, $(Ly, muy)$, and $h$ is convex-concave with a $(Lambdaxx, Lambdaxy, Lambdayymuyright)$。
論文 参考訳（メタデータ） (2022-02-09T18:57:47Z) - 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) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - On the Complexity of Minimizing Convex Finite Sums Without Using the
Indices of the Individual Functions [62.01594253618911]
有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。
同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
論文 参考訳（メタデータ） (2020-02-09T03:39:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。