論文の概要: Revisiting EXTRA for Smooth Distributed Optimization
- arxiv url: http://arxiv.org/abs/2002.10110v2
- Date: Thu, 18 Jun 2020 04:38:13 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-29 04:48:12.821358
- Title: Revisiting EXTRA for Smooth Distributed Optimization
- Title(参考訳): 平滑な分散最適化のためのEXTRAの再検討
- Authors: Huan Li and Zhouchen Lin
- Abstract要約: 改良された$Oleft(left(fracLmu+frac11-sigma_2(W)right)logfrac1epsilon (1-sigma_2(W))right)$。
高速化されたEXTRAの通信複雑性は、$left(logfracLmu (1-sigma_2(W))right)$と$left(logfrac1epsilon (1。
- 参考スコア(独自算出の注目度): 70.65867695317633
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: EXTRA is a popular method for dencentralized distributed optimization and has
broad applications. This paper revisits EXTRA. First, we give a sharp
complexity analysis for EXTRA with the improved
$O\left(\left(\frac{L}{\mu}+\frac{1}{1-\sigma_2(W)}\right)\log\frac{1}{\epsilon(1-\sigma_2(W))}\right)$
communication and computation complexities for $\mu$-strongly convex and
$L$-smooth problems, where $\sigma_2(W)$ is the second largest singular value
of the weight matrix $W$. When the strong convexity is absent, we prove the
$O\left(\left(\frac{L}{\epsilon}+\frac{1}{1-\sigma_2(W)}\right)\log\frac{1}{1-\sigma_2(W)}\right)$
complexities. Then, we use the Catalyst framework to accelerate EXTRA and
obtain the $O\left(\sqrt{\frac{L}{\mu(1-\sigma_2(W))}}\log\frac{
L}{\mu(1-\sigma_2(W))}\log\frac{1}{\epsilon}\right)$ communication and
computation complexities for strongly convex and smooth problems and the
$O\left(\sqrt{\frac{L}{\epsilon(1-\sigma_2(W))}}\log\frac{1}{\epsilon(1-\sigma_2(W))}\right)$
complexities for non-strongly convex ones. Our communication complexities of
the accelerated EXTRA are only worse by the factors of
$\left(\log\frac{L}{\mu(1-\sigma_2(W))}\right)$ and
$\left(\log\frac{1}{\epsilon(1-\sigma_2(W))}\right)$ from the lower complexity
bounds for strongly convex and non-strongly convex problems, respectively.
- Abstract(参考訳): extraは分散最適化の一般的な方法であり、幅広いアプリケーションがある。
この論文はEXTRAを再考する。
まず、改良された$o\left(\left(\left(\frac{l}{\mu}+\frac{1}{1-\sigma_2(w)}\right)\log\frac{1}{\epsilon(1-\sigma_2(w))}\right)$の通信と計算の複雑さを、$\mu$-strongly convex と $l$-smooth 問題に対して与える。
強い凸性が存在しないとき、$O\left(\left(\frac{L}{\epsilon}+\frac{1}{1-\sigma_2(W)}\right)\log\frac{1}{1-\sigma_2(W)}\right)$複雑さを証明する。
次に、触媒フレームワークを用いて余剰を加速し、非強凸かつ滑らかな問題に対する通信および計算の複雑さと、非強凸の複素数に対する$o\left(\sqrt{\frac{l}{\mu(1-\sigma_2(w))}}\log\frac{1}{\epsilon(1-\sigma_2(w))}\right)$(\sqrt{\frac{l}{\epsilon(1-\sigma_2(w))}}\log\frac{1}{\epsilon(1-\sigma_2(w)}\right)$ を得る。
加速余剰の通信の複雑さは、強凸問題と非強凸問題に対して、それぞれ$\left(\log\frac{l}{\mu(1-\sigma_2(w))}\right)$と$\left(\log\frac{1}{\epsilon(1-\sigma_2(w))}\right)$の因子によってのみ悪化する。
関連論文リスト
- 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) - Lifted Primal-Dual Method for Bilinearly Coupled Smooth Minimax
Optimization [47.27237492375659]
双線型結合されたミニマックス問題:$min_x max_y f(x) + ytop A x - h(y)$, ここでは$f$と$h$はどちらも強凸滑らかな関数である。
Omega(sqrtfracL_xmu_x + frac|A|sqrtmu_x,mu_y) log(frac1vareps) の低い複雑性境界を達成した1次アルゴリズムは知られていない。
論文 参考訳(メタデータ) (2022-01-19T05:56:19Z) - Accelerated Gradient Tracking over Time-varying Graphs for Decentralized
Optimization [77.57736777744934]
この論文は、広く使用されている加速勾配追跡を再検討し、拡張する。
私たちの複雑さは $cal O(frac1epsilon5/7)$ と $cal O(fracLmu)5/7frac1 (1-sigma)1.5logfrac1epsilon)$ で大幅に改善します。
論文 参考訳(メタデータ) (2021-04-06T15:34:14Z) - Infinite-Horizon Offline Reinforcement Learning with Linear Function
Approximation: Curse of Dimensionality and Algorithm [46.36534144138337]
本稿では,オフライン強化学習におけるポリシー評価のサンプル複雑さについて検討する。
低分布シフトの仮定の下では、最大$oleft(maxleft fracleftvert thetapirightvert _24varepsilon4logfracddelta,frac1varepsilon2left(d+logfrac1deltaright)right right)$サンプルを必要とするアルゴリズムがあることを示す。
論文 参考訳(メタデータ) (2021-03-17T18:18:57Z) - 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) - Improved Algorithms for Convex-Concave Minimax Optimization [10.28639483137346]
本稿では、ミニマックス最適化問題$min_x max_y f(x,y)$, $f(x,y)$が$x$, $m_y$-strongly concaveに対して$m_x$-strongly convexが$y$および$(L_x,L_xy,L_y)$-smoothに関して$m_x$-strongly concaveについて検討する。
論文 参考訳(メタデータ) (2020-06-11T12:21:13Z) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳(メタデータ) (2020-06-06T13:34:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。