論文の概要: Optimal Gradient Sliding and its Application to Distributed Optimization
Under Similarity
- arxiv url: http://arxiv.org/abs/2205.15136v1
- Date: Mon, 30 May 2022 14:28:02 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-31 18:34:02.185590
- Title: Optimal Gradient Sliding and its Application to Distributed Optimization
Under Similarity
- Title（参考訳）: 最適勾配すべりと類似性を考慮した分散最適化への応用
- Authors: Dmitry Kovalev, Aleksandr Beznosikov, Ekaterina Borodich, Alexander
Gasnikov, Gesualdo Scutari
- Abstract要約: 積 $r:=p + q$, ここで$r$は$mu$-strong convex類似性である。
エージェントの通信やローカルコールにマスターされた問題を解決する方法を提案する。
提案手法は$mathcalO(sqrtL_q/mu)$法よりもはるかにシャープである。
- 参考スコア（独自算出の注目度）: 121.83085611327654
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study structured convex optimization problems, with additive objective
$r:=p + q$, where $r$ is ($\mu$-strongly) convex, $q$ is $L_q$-smooth and
convex, and $p$ is $L_p$-smooth, possibly nonconvex. For such a class of
problems, we proposed an inexact accelerated gradient sliding method that can
skip the gradient computation for one of these components while still achieving
optimal complexity of gradient calls of $p$ and $q$, that is,
$\mathcal{O}(\sqrt{L_p/\mu})$ and $\mathcal{O}(\sqrt{L_q/\mu})$,
respectively. This result is much sharper than the classic black-box complexity
$\mathcal{O}(\sqrt{(L_p+L_q)/\mu})$, especially when the difference between
$L_q$ and $L_q$ is large. We then apply the proposed method to solve
distributed optimization problems over master-worker architectures, under
agents' function similarity, due to statistical data similarity or otherwise.
The distributed algorithm achieves for the first time lower complexity bounds
on {\it both} communication and local gradient calls, with the former having
being a long-standing open problem. Finally the method is extended to
distributed saddle-problems (under function similarity) by means of solving a
class of variational inequalities, achieving lower communication and
computation complexity bounds.
- Abstract（参考訳）: そこで、$r$は$\mu$-strongly)、$q$は$l_q$-smoothとconvex、$p$は$l_p$-smooth、おそらく非凸である。
このような問題に対して,各成分の勾配計算を省略し,それぞれ$p$ と $q$ の勾配呼び出しの最適複雑性,すなわち $\mathcal{o}(\sqrt{l_p/\mu})$ と $\mathcal{o}(\sqrt{l_q/\mu})$ をそれぞれ達成できる,不正確な加速度勾配スライディング法を提案した。
この結果は古典的なブラックボックスの複雑さである$\mathcal{o}(\sqrt{(l_p+l_q)/\mu})$よりもはるかにシャープである。
次に,提案手法を適用し,統計データの類似性などにより,エージェントの関数類似性の下で,マスタワーカアーキテクチャ上の分散最適化問題を解く。
分散アルゴリズムは、通信と局所的なグラデーション呼び出しにおいて、初めてより低い複雑性境界を達成し、前者は長年の未解決問題である。
最後に、変分不等式クラスを解き、より低い通信と計算複雑性の境界を達成することにより、分散saddle-problem(関数類似性の下で)に拡張する。
関連論文リスト
- An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Beyond Uniform Smoothness: A Stopped Analysis of Adaptive SGD [38.221784575853796]
この研究は、勾配を用いて潜在的に一定の滑らかさを持つ非アトー関数の1次定常点を求める問題を考える。
我々は、ノイズに一様境界を仮定することなく$mathcalO(fracmathrmpolylog(T)sigmatT)$収束率を証明できる技術を開発した。
論文 参考訳（メタデータ） (2023-02-13T18:13:36Z) - ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。
我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-01-01T18:51:29Z) - Decomposable Non-Smooth Convex Optimization with Nearly-Linear Gradient
Oracle Complexity [15.18055488087588]
上記の凸定式化を$widetildeO(sum_i=1n d_i log (1 /epsilon))$グラデーション計算で$epsilon$-accuracyに最小化するアルゴリズムを与える。
我々の主な技術的貢献は、カットプレーン法とインテリアポイント法を組み合わせた新しい組み合わせにより、各イテレーションで$f_i$項を選択する適応的な手順である。
論文 参考訳（メタデータ） (2022-08-07T20:53:42Z) - 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) - 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) - Hybrid Stochastic-Deterministic Minibatch Proximal Gradient:
Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。
損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
論文 参考訳（メタデータ） (2020-09-18T02:18:44Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳（メタデータ） (2020-04-16T19:16:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。