論文の概要: 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)$の因子によってのみ悪化する。
関連論文リスト
- Tight Lower Bounds under Asymmetric High-Order Hölder Smoothness and Uniform Convexity [6.972653925522813]
我々は、高次H'olderの滑らかかつ一様凸関数を最小化するオラクル複雑性に対して、厳密な下界を提供する。
解析は、一階および二階の滑らかさの下での関数の以前の下界を一様凸関数と同様に一般化する。
論文 参考訳（メタデータ） (2024-09-16T23:17:33Z) - 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 Query Complexities for Dynamic Trace Estimation [59.032228008383484]
我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。
我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。
我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
論文 参考訳（メタデータ） (2022-09-30T04:15:44Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。