論文の概要: Graphon Particle Systems, Part II: Dynamics of Distributed Stochastic Continuum Optimization
- arxiv url: http://arxiv.org/abs/2407.02765v1
- Date: Wed, 3 Jul 2024 02:47:39 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-04 15:54:34.701760
- Title: Graphon Particle Systems, Part II: Dynamics of Distributed Stochastic Continuum Optimization
- Title（参考訳）: Graphon Particle Systems, Part II: Distributed Stochastic Continuum Optimizationのダイナミクス
- Authors: Yan Chen, Tao Li,
- Abstract要約: ノード連続体を持つグラフオン上での分散最適化問題について検討する。
グラノン上での勾配降下と勾配追従アルゴリズムを提案する。
時間変化アルゴリズムを適切に選択することにより、すべてのノードの状態が接続されたグラフに対して$mathcalLinfty$-consensusを達成することを示す。
- 参考スコア（独自算出の注目度）: 5.685037987395183
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the distributed optimization problem over a graphon with a continuum of nodes, which is regarded as the limit of the distributed networked optimization as the number of nodes goes to infinity. Each node has a private local cost function. The global cost function, which all nodes cooperatively minimize, is the integral of the local cost functions on the node set. We propose stochastic gradient descent and gradient tracking algorithms over the graphon. We establish a general lemma for the upper bound estimation related to a class of time-varying differential inequalities with negative linear terms, based upon which, we prove that for both kinds of algorithms, the second moments of the nodes' states are uniformly bounded. Especially, for the stochastic gradient tracking algorithm, we transform the convergence analysis into the asymptotic property of coupled nonlinear differential inequalities with time-varying coefficients and develop a decoupling method. For both kinds of algorithms, we show that by choosing the time-varying algorithm gains properly, all nodes' states achieve $\mathcal{L}^{\infty}$-consensus for a connected graphon. Furthermore, if the local cost functions are strongly convex, then all nodes' states converge to the minimizer of the global cost function and the auxiliary states in the stochastic gradient tracking algorithm converge to the gradient value of the global cost function at the minimizer uniformly in mean square.
- Abstract（参考訳）: ノード数が無限になるにつれて、分散ネットワーク最適化の限界と見なされるノードの連続体を持つグラフオン上での分散最適化問題について検討する。
各ノードは、プライベートなローカルコスト関数を持つ。
すべてのノードが協力的に最小となるグローバルコスト関数は、ノードセット上の局所コスト関数の積分である。
グラフオン上での確率的勾配勾配勾配と勾配追跡アルゴリズムを提案する。
我々は、負の線形項を持つ時間変化微分不等式のクラスに関連する上限推定の一般補題を確立し、このクラスに基づいて、両方の種類のアルゴリズムに対して、ノードの状態の2番目のモーメントが一様有界であることを証明した。
特に、確率勾配追跡アルゴリズムでは、収束解析を時間変化係数と結合した非線形微分不等式の漸近特性に変換し、デカップリング法を開発する。
どちらのアルゴリズムに対しても、時間変化のアルゴリズムを適切に選択することで、すべてのノードの状態が連結グラフロンに対して$\mathcal{L}^{\infty}$-consensusが得られることを示す。
さらに、局所的なコスト関数が強凸であれば、全てのノードの状態は大域的なコスト関数の最小値に収束し、確率勾配追跡アルゴリズムの補助状態は小域的な平均平方における大域的なコスト関数の勾配値に収束する。
関連論文リスト
- Convergence of Adam Under Relaxed Assumptions [72.24779199744954]
我々は、アダムがより現実的な条件下で、$O(epsilon-4)$勾配複雑性で$epsilon$-定常点に収束することを示している。
また、Adamの分散還元版を$O(epsilon-3)$の加速勾配複雑性で提案する。
論文 参考訳（メタデータ） (2023-04-27T06:27:37Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳（メタデータ） (2023-02-01T08:50:48Z) - Gradient-Free Methods for Deterministic and Stochastic Nonsmooth
Nonconvex Optimization [94.19177623349947]
非滑らかな非最適化問題は、機械学習とビジネス製造に現れる。
2つのコア課題は、有限収束を保証する効率的な方法の開発を妨げる。
GFMとSGFMの2相版も提案され, 改良された大規模評価結果が得られた。
論文 参考訳（メタデータ） (2022-09-12T06:53:24Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳（メタデータ） (2022-06-17T06:10:20Z) - Push--Pull with Device Sampling [8.344476599818826]
複数のエージェントが協力して、基礎となる通信グラフを交換することで、ローカル関数の平均を最小化する分散最適化問題を考察する。
ネットワーク全体の勾配追跡と分散低減を併用したアルゴリズムを提案する。
理論解析により,局所目的関数が強凸である場合,アルゴリズムは線形に収束することを示した。
論文 参考訳（メタデータ） (2022-06-08T18:18:18Z) - Improving the Transient Times for Distributed Stochastic Gradient
Methods [5.215491794707911]
拡散適応段階法(EDAS)と呼ばれる分散勾配アルゴリズムについて検討する。
EDASが集中勾配降下(SGD)と同じネットワーク独立収束率を達成することを示す。
我々の知る限り、EDASは$n$のコスト関数の平均が強い凸である場合に最も短い時間を達成する。
論文 参考訳（メタデータ） (2021-05-11T08:09:31Z) - Convergence Analysis of Nonconvex Distributed Stochastic Zeroth-order
Coordinate Method [3.860616339202303]
本稿では,$ZOn$局所コスト関数の合計により形成されるグローバルコスト関数を最小化する分散非最適化問題について検討する。
エージェントは問題を解くためにzo座標法を近似する。
論文 参考訳（メタデータ） (2021-03-24T03:07:46Z) - Fast decentralized non-convex finite-sum optimization with recursive
variance reduction [19.540926205375857]
本稿では,SARAH型分散低減技術を用いたGT-SARAHと呼ばれる一階勾配法について述べる。
特に、$n = O(Nfrac12(lambda)3)$のようなビッグデータでは、ネットワークの複雑さとは無関係に、この複雑さは$O(Nfrac12Lepsilon-2)$に減少する。
さらに、局所的なミニバッチサイズの適切な選択は、勾配複雑性と通信複雑性のトレードオフをバランスさせる。
論文 参考訳（メタデータ） (2020-08-17T15:51:32Z) - A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis
and Application to Actor-Critic [142.1492359556374]
双レベル最適化は、2レベル構造を示す問題のクラスである。
このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。
本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
論文 参考訳（メタデータ） (2020-07-10T05:20:02Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。