論文の概要: On Linear Convergence of PI Consensus Algorithm under the Restricted Secant Inequality

• arxiv url: http://arxiv.org/abs/2310.00419v2
• Date: Mon, 28 Oct 2024 13:26:59 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-29 12:15:24.615260
• Title: On Linear Convergence of PI Consensus Algorithm under the Restricted Secant Inequality
• Title（参考訳）: 制限付きセカント不等式下におけるPIコンセンサスアルゴリズムの線形収束性について
• Authors: Kushal Chakrabarti, Mayank Baranwal,
• Abstract要約: 本稿では,ピアツーピアマルチエージェントネットワークにおける分散最適化問題について考察する。 比例積分 (PI) 制御戦略を用いることで, 固定段数をもつ様々なアルゴリズムが開発されている。
• 参考スコア（独自算出の注目度）: 5.35599092568615
• License:
• Abstract: This paper considers solving distributed optimization problems in peer-to-peer multi-agent networks. The network is synchronous and connected. By using the proportional-integral (PI) control strategy, various algorithms with fixed stepsize have been developed. Two notable among them are the PI algorithm and the PI consensus algorithm. Although the PI algorithm has provable linear or exponential convergence without the standard requirement of (strong) convexity, a similar guarantee for the PI consensus algorithm is unavailable. In this paper, using Lyapunov theory, we guarantee exponential convergence of the PI consensus algorithm for global cost functions that satisfy the restricted secant inequality, with rate-matching discretization, without requiring convexity. To accelerate the PI consensus algorithm, we incorporate local pre-conditioning in the form of constant positive definite matrices and numerically validate its efficiency compared to the prominent distributed convex optimization algorithms. Unlike classical pre-conditioning, where only the gradients are multiplied by a pre-conditioner, the proposed pre-conditioning modifies both the gradients and the consensus terms, thereby controlling the effect of the communication graph on the algorithm.
• Abstract（参考訳）: 本稿では,ピアツーピアマルチエージェントネットワークにおける分散最適化問題について考察する。 ネットワークは同期して接続される。 比例積分 (PI) 制御戦略を用いることで, 固定段数をもつ様々なアルゴリズムが開発されている。 中でも注目すべきは、PIアルゴリズムとPIコンセンサスアルゴリズムである。 PIアルゴリズムは、(強い)凸性の標準的な要求なしに、証明可能な線形あるいは指数収束を持つが、PIコンセンサスアルゴリズムの同様の保証は利用できない。 本稿では、リアプノフ理論を用いて、不等式制約を満たす大域的コスト関数に対するPIコンセンサスアルゴリズムの指数収束を、凸性を必要としない速度整合離散化で保証する。 PIコンセンサスアルゴリズムを高速化するため,定定値行列の形式に局所的プレコンディショニングを導入し,その効率を分散凸最適化アルゴリズムと比較して数値的に検証する。 従来のプレコンディショニングとは異なり、プレコンディショニングはグラデーションとコンセンサスの両方を修正し、通信グラフがアルゴリズムに与える影響を制御する。

関連論文リスト

• Decentralized Sum-of-Nonconvex Optimization [42.04181488477227]
  我々は、平均的な非合意数である保証関数(sum-of-non function)の最適化問題を考察する。 本稿では,勾配,速度追跡,マルチコンセンサスといった手法を用いて,高速化された分散化1次アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-02-04T05:48:45Z)
• From Optimization to Control: Quasi Policy Iteration [3.4376560669160394]
  準政治反復(QPI)と呼ばれる新しい制御アルゴリズムを提案する。 QPIは、政策反復アルゴリズムにおける「ヘシアン」行列の新たな近似に基づいて、MDPに特有の2つの線形構造制約を利用する。 これは、割引係数に対する感度が極めて低い政策反復と同様の実証的な収束挙動を示す。
  論文  参考訳（メタデータ） (2023-11-18T21:00:14Z)
• Decentralized Inexact Proximal Gradient Method With Network-Independent Stepsizes for Convex Composite Optimization [39.352542703876104]
  本稿では,非方向および接続ネットワーク上での分散凸複合最適化について考察する。 CTA(Combine-Then-Adapt)に基づく新しい分散アルゴリズムは、非協調的なネットワーク非依存の定数ステップサイズの下で提案される。
  論文  参考訳（メタデータ） (2023-02-07T03:50:38Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• First-Order Algorithms for Nonlinear Generalized Nash Equilibrium Problems [88.58409977434269]
  非線形一般化ナッシュ均衡問題(NGNEP)における平衡計算の問題を考える。 我々の貢献は、2次ペナルティ法と拡張ラグランジアン法に基づく2つの単純な一階アルゴリズムフレームワークを提供することである。 これらのアルゴリズムに対する漸近的理論的保証を提供する。
  論文  参考訳（メタデータ） (2022-04-07T00:11:05Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。 この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。 古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
  論文  参考訳（メタデータ） (2020-07-01T18:43:32Z)
• Optimal and Practical Algorithms for Smooth and Strongly Convex Decentralized Optimization [21.555331273873175]
  ネットワークのノードにまたがるスムーズな凸関数の和を分散化最小化する作業について検討する。 本稿では,この分散最適化問題に対する2つの新しいアルゴリズムを提案し,複雑性を保証する。
  論文  参考訳（メタデータ） (2020-06-21T11:23:20Z)
• A Gradient-Aware Search Algorithm for Constrained Markov Decision Processes [9.728259735794987]
  まず,有限CMDPの双対線型計画における最適化目標が,ラグランジュのペナルティ乗算器に対する一方向線型凸関数であることを証明した。 有限CMDPの最適状態値関数とラグランジュペナルティ乗算器を求めるために,PWLC構造を利用した2レベルグラディエント・アウェア・サーチ(GAS)アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-05-07T19:38:09Z)
• Adaptivity of Stochastic Gradient Methods for Nonconvex Optimization [71.03797261151605]
  適応性は現代最適化理論において重要であるが、研究されていない性質である。 提案アルゴリズムは,PL目標に対して既存のアルゴリズムよりも優れた性能を保ちながら,PL目標に対して最適な収束性を実現することを実証した。
  論文  参考訳（メタデータ） (2020-02-13T05:42:27Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。