論文の概要: Enhancing Convergence of Decentralized Gradient Tracking under the KL Property
- arxiv url: http://arxiv.org/abs/2412.09556v1
- Date: Thu, 12 Dec 2024 18:44:36 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-13 17:02:03.150849
- Title: Enhancing Convergence of Decentralized Gradient Tracking under the KL Property
- Title（参考訳）: KL特性下における分散勾配追従の収束性向上
- Authors: Xiaokai Chen, Tianyu Cao, Gesualdo Scutari,
- Abstract要約: 我々は,分散勾配追跡に基づくアルゴリズムであるSONATAに対して,同じタイプの収束性を確立する。
これは、いつを除いて集中的な勾配アルゴリズムの収束挙動と一致する。
thetain (1/2,1)$, sub rate is confirmed; and
textbf(iii)$ if $thetain (1/2, 1)$, sub rate is certificate; and
textbf(iii)$ if $thetain (1/2,1)$, sub rate が認証される。
- 参考スコア（独自算出の注目度）: 10.925931212031692
- License:
- Abstract: We study decentralized multiagent optimization over networks, modeled as undirected graphs. The optimization problem consists of minimizing a nonconvex smooth function plus a convex extended-value function, which enforces constraints or extra structure on the solution (e.g., sparsity, low-rank). We further assume that the objective function satisfies the Kurdyka-{\L}ojasiewicz (KL) property, with given exponent $\theta\in [0,1)$. The KL property is satisfied by several (nonconvex) functions of practical interest, e.g., arising from machine learning applications; in the centralized setting, it permits to achieve strong convergence guarantees. Here we establish convergence of the same type for the notorious decentralized gradient-tracking-based algorithm SONATA. Specifically, $\textbf{(i)}$ when $\theta\in (0,1/2]$, the sequence generated by SONATA converges to a stationary solution of the problem at R-linear rate;$ \textbf{(ii)} $when $\theta\in (1/2,1)$, sublinear rate is certified; and finally $\textbf{(iii)}$ when $\theta=0$, the iterates will either converge in a finite number of steps or converges at R-linear rate. This matches the convergence behavior of centralized proximal-gradient algorithms except when $\theta=0$. Numerical results validate our theoretical findings.
- Abstract（参考訳）: ネットワーク上での分散マルチエージェント最適化を非指向グラフとしてモデル化する。
最適化問題は、非凸滑らかな関数と凸拡張値関数を最小化し、解の制約や余分な構造(例えば、疎度、低ランク)を強制する。
さらに、目的関数がクルディカ={\L}ojasiewicz (KL) の性質を満たすと仮定し、指数 $\theta\in [0,1)$ が与えられる。
KL特性は、例えば機械学習アプリケーションから生じるいくつかの(非凸)関数によって満足されるが、集中的な環境では、強い収束保証を達成することができる。
ここでは、分散勾配追跡に基づくアルゴリズムSONATAについて、同じタイプの収束を確立する。
具体的には$\textbf{
(i)}$$$\theta\in (0,1/2]$の場合、SONATAによって生成される列は、R-線型レートで問題の定常解に収束する;$ \textbf{
(ii)} $when $\theta\in (1/2,1)$, sublinear rateが認証され、最後に$\textbf{
(iii)}$が$\theta=0$のとき、イテレートは有限のステップに収束するか、R-線型速度で収束する。
これは、$\theta=0$のときを除いて、集中的近位勾配アルゴリズムの収束挙動と一致する。
数値的な結果から理論的な結果が得られた。
関連論文リスト
- Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization [77.3396841985172]
我々は、構造化された非極小最適化問題の解法として、2時間勾配上昇(TTGDA)を統一的に解析する。
我々の貢献はTTGDAアルゴリズムを設計することであり、設定を超えて効果的です。
論文 参考訳（メタデータ） (2024-08-21T20:14:54Z) - Optimal and Efficient Algorithms for Decentralized Online Convex Optimization [51.00357162913229]
分散オンライン凸最適化(D-OCO)は、局所計算と通信のみを用いて、グローバルな損失関数の列を最小化するように設計されている。
我々は,凸関数と強凸関数の残差を$tildeO(nrho-1/4sqrtT)$と$tildeO(nrho-1/2log T)$に削減できる新しいD-OCOアルゴリズムを開発した。
我々の分析によると、射影自由多様体は$O(nT3/4)$と$O(n)を達成できる。
論文 参考訳（メタデータ） (2024-02-14T13:44:16Z) - Convergence of a Normal Map-based Prox-SGD Method under the KL
Inequality [0.0]
我々は、$symbol$k$収束問題に対して、新しいマップベースのアルゴリズム(mathsfnorMtext-mathsfSGD$)を提案する。
論文 参考訳（メタデータ） (2023-05-10T01:12:11Z) - 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) - Nonsmooth Nonconvex-Nonconcave Minimax Optimization: Primal-Dual Balancing and Iteration Complexity Analysis [23.80683445944524]
PLDAの新たな解析手法を導入し,その鍵となるのは,新たに開発された非滑らかかつ二重なエラー反復である。
PLDA が $thetain [0,12]$ のとき、緩やかな仮定の下で最適な $mathcalO()$ を達成する。
論文 参考訳（メタデータ） (2022-09-22T07:12: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) - Decentralized Riemannian Gradient Descent on the Stiefel Manifold [39.750623187256735]
エージェントのネットワークがStiefel多様体上のグローバル関数を最小化することを目的としている分散非センシアン最適化を考える。
一定の使用条件を満たすために、Stiefel多様体のための分散勾配(DRA)も提案する。
論文 参考訳（メタデータ） (2021-02-14T07:30:23Z) - Proximal Gradient Descent-Ascent: Variable Convergence under K{\L}
Geometry [49.65455534654459]
有限降下指数パラメータ (GDA) はミニマックス最適化問題の解法として広く応用されている。
本稿では、KL-L型幾何学の収束を研究することにより、そのようなギャップを埋める。
論文 参考訳（メタデータ） (2021-02-09T05:35:53Z) - S-ADDOPT: Decentralized stochastic first-order optimization over
directed graphs [16.96562173221624]
有向ネットワークノード上に分散する関数のスムーズかつ高コストな関数の和を最小化するために,分散凸最適化を提案する。
特に,各ノードに1次オラクルを仮定するtextbftextttS-ADDOPTアルゴリズムを提案する。
崩壊するステップサイズ$mathcalO (1/k)$に対して、textbfttS-ADDOPT が$mathcalO (1/k)$ で正解に達し、その収束はネットワーク非依存であることを示す。
論文 参考訳（メタデータ） (2020-05-15T21:14:22Z) - Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。
特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
論文 参考訳（メタデータ） (2020-02-10T23:23:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。