論文の概要: Distributed Optimization via Energy Conservation Laws in Dilated Coordinates

• arxiv url: http://arxiv.org/abs/2409.19279v1
• Date: Sat, 28 Sep 2024 08:02:43 GMT
• ステータス: 処理完了
• システム内更新日: 2024-11-06 00:08:33.408218
• Title: Distributed Optimization via Energy Conservation Laws in Dilated Coordinates
• Title（参考訳）: 拡張座標系におけるエネルギー保存則による分散最適化
• Authors: Mayank Baranwal, Kushal Chakrabarti,
• Abstract要約: 本稿では,拡張座標における連続時間力学系の解析のためのエネルギー保存手法を提案する。 収束率を逆時間差係数で明示的に表すことができる。 その高速化された収束挙動は、実用的、大規模問題に対する様々な最先端分散最適化アルゴリズムに対してベンチマークされる。
• 参考スコア（独自算出の注目度）: 5.35599092568615
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Optimizing problems in a distributed manner is critical for systems involving multiple agents with private data. Despite substantial interest, a unified method for analyzing the convergence rates of distributed optimization algorithms is lacking. This paper introduces an energy conservation approach for analyzing continuous-time dynamical systems in dilated coordinates. Instead of directly analyzing dynamics in the original coordinate system, we establish a conserved quantity, akin to physical energy, in the dilated coordinate system. Consequently, convergence rates can be explicitly expressed in terms of the inverse time-dilation factor. Leveraging this generalized approach, we formulate a novel second-order distributed accelerated gradient flow with a convergence rate of $O\left(1/t^{2-\epsilon}\right)$ in time $t$ for $\epsilon>0$. We then employ a semi second-order symplectic Euler discretization to derive a rate-matching algorithm with a convergence rate of $O\left(1/k^{2-\epsilon}\right)$ in $k$ iterations. To the best of our knowledge, this represents the most favorable convergence rate for any distributed optimization algorithm designed for smooth convex optimization. Its accelerated convergence behavior is benchmarked against various state-of-the-art distributed optimization algorithms on practical, large-scale problems.
• Abstract（参考訳）: 分散的な方法で問題を最適化することは、複数のエージェントとプライベートデータを含むシステムにとって重要である。 かなりの関心があるにもかかわらず、分散最適化アルゴリズムの収束率を分析する統一的な方法が欠落している。 本稿では,拡張座標における連続時間力学系の解析のためのエネルギー保存手法を提案する。 元の座標系における力学を直接解析する代わりに、拡張座標系において物理エネルギーに似た保存量を確立する。 その結果、収束率を逆時間差係数で明示的に表すことができる。 この一般化されたアプローチを利用して、新しい二階分散加速勾配流を$O\left(1/t^{2-\epsilon}\right)$ in time $t$ for $\epsilon>0$で定式化する。 次に、半二階シンプレクティックなオイラー離散化を用いて、$k$反復で$O\left(1/k^{2-\epsilon}\right)$の収束率を持つレートマッチングアルゴリズムを導出する。 我々の知る限り、これはスムーズな凸最適化のために設計された分散最適化アルゴリズムにおいて最も好ましい収束率を示している。 その高速化された収束挙動は、実用的、大規模問題に対する様々な最先端分散最適化アルゴリズムに対してベンチマークされる。

関連論文リスト

• Decentralized Inexact Proximal Gradient Method With Network-Independent Stepsizes for Convex Composite Optimization [39.352542703876104]
  本稿では,非方向および接続ネットワーク上での分散凸複合最適化について考察する。 CTA(Combine-Then-Adapt)に基づく新しい分散アルゴリズムは、非協調的なネットワーク非依存の定数ステップサイズの下で提案される。
  論文  参考訳（メタデータ） (2023-02-07T03:50:38Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• Breaking the Convergence Barrier: Optimization via Fixed-Time Convergent Flows [4.817429789586127]
  本稿では, 固定時間安定力学系の概念に基づいて, 加速を実現するための多言語最適化フレームワークを提案する。 提案手法の高速化された収束特性を,最先端の最適化アルゴリズムに対して様々な数値例で検証する。
  論文  参考訳（メタデータ） (2021-12-02T16:04:40Z)
• On Accelerating Distributed Convex Optimizations [0.0]
  本稿では,分散マルチエージェント凸最適化問題について検討する。 提案アルゴリズムは, 従来の勾配偏光法よりも収束率を向上し, 線形収束することを示す。 実ロジスティック回帰問題の解法として,従来の分散アルゴリズムと比較して,アルゴリズムの性能が優れていることを示す。
  論文  参考訳（メタデータ） (2021-08-19T13:19:54Z)
• Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
  高精度リコール曲線(AUPRC)に基づく領域の最適化について検討し,不均衡なタスクに広く利用されている。 我々は、$O (1/epsilon4)$のより優れた反復による、$epsilon$定常解を見つけるための新しい運動量法を開発する。 また,O(1/epsilon4)$と同じ複雑さを持つ適応手法の新たなファミリを設計し,実際により高速な収束を享受する。
  論文  参考訳（メタデータ） (2021-07-02T16:21:52Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• Convergence Analysis of Nonconvex Distributed Stochastic Zeroth-order Coordinate Method [3.860616339202303]
  本稿では,$ZOn$局所コスト関数の合計により形成されるグローバルコスト関数を最小化する分散非最適化問題について検討する。 エージェントは問題を解くためにzo座標法を近似する。
  論文  参考訳（メタデータ） (2021-03-24T03:07:46Z)
• Bilevel Optimization: Convergence Analysis and Enhanced Design [63.64636047748605]
  バイレベル最適化は多くの機械学習問題に対するツールである。 Stoc-BiO という新しい確率効率勾配推定器を提案する。
  論文  参考訳（メタデータ） (2020-10-15T18:09:48Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)

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

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