論文の概要: On the Complexity of Decentralized Smooth Nonconvex Finite-Sum Optimization

• arxiv url: http://arxiv.org/abs/2210.13931v4
• Date: Sat, 11 Jan 2025 14:59:50 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-14 14:21:29.461078
• Title: On the Complexity of Decentralized Smooth Nonconvex Finite-Sum Optimization
• Title（参考訳）: 分散平滑な非凸有限和最適化の複雑さについて
• Authors: Luo Luo, Yunyan Bai, Lesi Chen, Yuxing Liu, Haishan Ye,
• Abstract要約: 分散最適化問題 $min_bf xinmathbb Rd f(bf x)triq frac1msum_i=1m f_i(bf x)triq frac1nsum_j=1n。
• 参考スコア（独自算出の注目度）: 21.334985032433778
• License:
• Abstract: We study the decentralized optimization problem $\min_{{\bf x}\in{\mathbb R}^d} f({\bf x})\triangleq \frac{1}{m}\sum_{i=1}^m f_i({\bf x})$, where the local function on the $i$-th agent has the form of $f_i({\bf x})\triangleq \frac{1}{n}\sum_{j=1}^n f_{i,j}({\bf x})$ and every individual $f_{i,j}$ is smooth but possibly nonconvex. We propose a stochastic algorithm called DEcentralized probAbilistic Recursive gradiEnt deScenT (DEAREST) method, which achieves an $\epsilon$-stationary point at each agent with the communication rounds of $\tilde{\mathcal O}(L\epsilon^{-2}/\sqrt{\gamma}\,)$, the computation rounds of $\tilde{\mathcal O}(n+(L+\min\{nL, \sqrt{n/m}\bar L\})\epsilon^{-2})$, and the local incremental first-oracle calls of ${\mathcal O}(mn + {\min\{mnL, \sqrt{mn}\bar L\}}{\epsilon^{-2}})$, where $L$ is the smoothness parameter of the objective function, $\bar L$ is the mean-squared smoothness parameter of all individual functions, and $\gamma$ is the spectral gap of the mixing matrix associated with the network. We then establish the lower bounds to show that the proposed method is near-optimal. Notice that the smoothness parameters $L$ and $\bar L$ used in our algorithm design and analysis are global, leading to sharper complexity bounds than existing results that depend on the local smoothness. We further extend DEAREST to solve the decentralized finite-sum optimization problem under the Polyak-{\L}ojasiewicz condition, also achieving the near-optimal complexity bounds.
• Abstract（参考訳）: 分散最適化問題 $\min_{{\bf x}\in{\mathbb R}^d} f({\bf x})\triangleq \frac{1}{m}\sum_{i=1}^m f_i({\bf x})$ ここで、$i$-th エージェント上の局所関数は $f_i({\bf x})\triangleq \frac{1}{n}\sum_{j=1}^n f_{i,j}({\bf x})$ であり、それぞれの$f_{i,j}$ は滑らかであるが、おそらく非凸である。 DEAREST(Decentralized ProbAbilistic Recursive gradiEnt deScenT)法という確率的アルゴリズムを提案し、各エージェントに$\tilde{\mathcal O}(L\epsilon^{-2}/\sqrt{\gamma}\,)$,$\tilde{\mathcal O}(n+(L+\min\{nL, \sqrt{n/m}\bar L\})\epsilon^{-2})$,${\mathcal O}(m + {\displaystyle \min\{nL, \sqrt{n/m}\bar L\})\epsilon^{-2})$,$$$\tilde{\mathcal O}(L}/\sqrt{\gamma}\,)$,$$$\tilde{\mathcal O}(L+(L+\min\min\{nL, \sqrt{n/m}\bar L\bar L\})\epsilon^{-2})$,$$$,$L,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$,$, $,$,$,$,$,$,$,$,$,$2,$,$,$,$,$,$,$,$,$,$,$,$,$,$のパラメータのパラメータのパラメータのパラメータのパラメータのパラメータのパラメータのパラメータのパラメータのパラメータである。 次に,提案手法がほぼ最適であることを示すために,下界を確立する。 アルゴリズムの設計と解析に使用される滑らか度パラメータ$L$と$\bar L$がグローバルであることに注意してください。 さらにDEARESTを拡張して、Polyak-{\L}ojasiewicz条件下での分散有限サム最適化問題を解くとともに、近似複雑性境界を達成する。

関連論文リスト

• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。