論文の概要: Distributed saddle point problems for strongly concave-convex functions
- arxiv url: http://arxiv.org/abs/2202.05812v1
- Date: Fri, 11 Feb 2022 18:21:23 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-14 14:50:16.868256
- Title: Distributed saddle point problems for strongly concave-convex functions
- Title（参考訳）: 強凹凸関数に対する分散サドル点問題
- Authors: Muhammad I. Qureshi and Usman A. Khan
- Abstract要約: GT-GDA は、$G(cdot)$ が滑らかで凸であり、$H(cdot)$ が滑らかで強凸であり、大域的結合行列 $overlineP$ が全列ランクを持つとき、一意のサドル点解に線型収束することを示す。
次に、GT-GDAのユニークなサドル点の周りの誤差への線形収束を示し、結合コスト$langle mathbf y, overlineP mathbf x rangle$がすべてのノードに共通であるときにゼロになる。
- 参考スコア（独自算出の注目度）: 8.325327265120283
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we propose GT-GDA, a distributed optimization method to solve
saddle point problems of the form: $\min_{\mathbf{x}} \max_{\mathbf{y}}
\{F(\mathbf{x},\mathbf{y}) :=G(\mathbf{x}) + \langle \mathbf{y}, \overline{P}
\mathbf{x} \rangle - H(\mathbf{y})\}$, where the functions $G(\cdot)$,
$H(\cdot)$, and the the coupling matrix $\overline{P}$ are distributed over a
strongly connected network of nodes. GT-GDA is a first-order method that uses
gradient tracking to eliminate the dissimilarity caused by heterogeneous data
distribution among the nodes. In the most general form, GT-GDA includes a
consensus over the local coupling matrices to achieve the optimal (unique)
saddle point, however, at the expense of increased communication. To avoid
this, we propose a more efficient variant GT-GDA-Lite that does not incur the
additional communication and analyze its convergence in various scenarios. We
show that GT-GDA converges linearly to the unique saddle point solution when
$G(\cdot)$ is smooth and convex, $H(\cdot)$ is smooth and strongly convex, and
the global coupling matrix $\overline{P}$ has full column rank. We further
characterize the regime under which GT-GDA exhibits a network
topology-independent convergence behavior. We next show the linear convergence
of GT-GDA to an error around the unique saddle point, which goes to zero when
the coupling cost ${\langle \mathbf y, \overline{P} \mathbf x \rangle}$ is
common to all nodes, or when $G(\cdot)$ and $H(\cdot)$ are quadratic. Numerical
experiments illustrate the convergence properties and importance of GT-GDA and
GT-GDA-Lite for several applications.
- Abstract（参考訳）: 本稿では、この形式のサドル点問題を解く分散最適化手法であるGT-GDAを提案する。 $\min_{\mathbf{x}} \max_{\mathbf{y}} \{F(\mathbf{x},\mathbf{y}) :=G(\mathbf{x}) + \langle \mathbf{y}, \overline{P} \mathbf{x} \rangle - H(\mathbf{y})\,} ここで、関数 $G(\cdot)$, $H(\cdot)$, 結合行列 $\overline{P}$ は、ノードの強連結ネットワーク上で分散される。
GT-GDAは、ノード間の不均一なデータ分布に起因する相違を取り除くために勾配追跡を利用する一階法である。
最も一般的な形では、gt-gda は通信量の増加を犠牲にして最適な(統一的な)鞍点を達成するための局所結合行列に関するコンセンサスを含んでいる。
これを回避するため,より効率的なGT-GDA-Liteを提案する。
GT-GDA は、$G(\cdot)$ が滑らかで凸であり、$H(\cdot)$ が滑らかで強凸であり、大域結合行列 $\overline{P}$ が全列ランクを持つとき、一意のサドル点解に線型収束することを示す。
我々は、GT-GDAがネットワークトポロジに依存しない収束挙動を示す体制をさらに特徴づける。
次に、GT-GDA の特異なサドル点の周りの誤差への線形収束を示し、これは結合コスト ${\langle \mathbf y, \overline{P} \mathbf x \rangle}$ がすべてのノードに共通であるか、あるいは$G(\cdot)$ と $H(\cdot)$ が二次であるときにゼロとなる。
数値実験は、GT-GDAとGT-GDA-Liteの収束特性と重要性をいくつかの用途に示す。
関連論文リスト
- Improved convergence rate of kNN graph Laplacians [11.93971616098517]
k$NNグラフの一般クラスで、グラフ親和性は$W_ij = epsilon-d/2 である。
制限多様体作用素に対する$k$NNグラフ Laplacian の点収束性を証明する。
論文 参考訳（メタデータ） (2024-10-30T17:01:00Z) - Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization [77.3396841985172]
我々は、構造化された非極小最適化問題の解法として、2時間勾配上昇(TTGDA)を統一的に解析する。
我々の貢献はTTGDAアルゴリズムを設計することであり、設定を超えて効果的です。
論文 参考訳（メタデータ） (2024-08-21T20:14:54Z) - Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect
Alignment [51.74913666829224]
強い反相関を持つデータセットに対して、適切なグラフは正および負のエッジ重みの両方を含むことを示す。
本稿では,平衡符号グラフの概念に着目した線形時間符号グラフサンプリング手法を提案する。
実験結果から, 署名付きグラフサンプリング手法は, 各種データセットにおいて, 既存の高速サンプリング方式よりも優れた性能を示した。
論文 参考訳（メタデータ） (2022-08-18T09:19:01Z) - On Convergence of Gradient Descent Ascent: A Tight Local Analysis [30.206431787797776]
GDA(Gradient Descent Ascent)法は、GAN(Generative Adversarial Network)における最小最適化のためのアルゴリズムである。
段差比eta_mathbfx$/eta_mathbfx=Theta(kappa2)によるGDAの収束を証明する。
我々はさらに収束保証を GDA および Extra-gradient Method (EG) に拡張する。
論文 参考訳（メタデータ） (2022-07-03T05:04:46Z) - Topology-aware Generalization of Decentralized SGD [89.25765221779288]
本稿では,分散型Valpha-10安定降下(D-SGD)の一般化可能性について検討する。
D-SGDの一般化性は、初期訓練段階における接続性と正の相関があることを証明した。
論文 参考訳（メタデータ） (2022-06-25T16:03:48Z) - A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
凸凹対象 $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, ここで、$f$ は局所リプシッツ勾配を持つ凸関数であり、$g$ は凸かつ非滑らかである。
主勾配ステップと2段ステップを交互に交互に行うCondat-Vuアルゴリズムの適応バージョンを提案する。
論文 参考訳（メタデータ） (2021-10-28T14:19:30Z) - Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization [59.65871549878937]
実用的な単一ループ加速勾配追跡には$O(fracgamma1-sigma_gamma)2sqrtfracLepsilon)$が必要であることを証明している。
我々の収束率は$O(frac1epsilon5/7)$と$O(fracLmu)5/7frac1(1-sigma)1.5logfrac1epsilon)$よりも大幅に改善した。
論文 参考訳（メタデータ） (2021-04-06T15:34:14Z) - Proximal Gradient Descent-Ascent: Variable Convergence under K{\L}
Geometry [49.65455534654459]
有限降下指数パラメータ (GDA) はミニマックス最適化問題の解法として広く応用されている。
本稿では、KL-L型幾何学の収束を研究することにより、そのようなギャップを埋める。
論文 参考訳（メタデータ） (2021-02-09T05:35:53Z) - Convergence of Graph Laplacian with kNN Self-tuned Kernels [14.645468999921961]
自己チューニングされたカーネルは、各点に$sigma_i$ を $k$-nearest neighbor (kNN) 距離で適応的に設定する。
本稿では、グラフラプラシアン作用素$L_N$を、kNN自己チューニングカーネルの新しい族に対する多様体(重み付き)ラプラシアンに収束することを証明する。
論文 参考訳（メタデータ） (2020-11-03T04:55:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。