論文の概要: On Centralized and Distributed Mirror Descent: Exponential Convergence Analysis Using Quadratic Constraints

• arxiv url: http://arxiv.org/abs/2105.14385v1
• Date: Sat, 29 May 2021 23:05:56 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-01 16:49:29.745238
• Title: On Centralized and Distributed Mirror Descent: Exponential Convergence Analysis Using Quadratic Constraints
• Title（参考訳）: 集中および分散ミラー降下について:二次制約を用いた指数収束解析
• Authors: Youbang Sun, Mahyar Fazlyab, Shahin Shahrampour
• Abstract要約: ミラー降下(MD)は、勾配降下(GD)を含むいくつかのアルゴリズムを仮定する強力な一階最適化手法である。 本研究では,強い凸と滑らかな問題に対して,集中型および分散型のMDの正確な収束率について検討した。
• 参考スコア（独自算出の注目度）: 8.336315962271396
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Mirror descent (MD) is a powerful first-order optimization technique that subsumes several optimization algorithms including gradient descent (GD). In this work, we study the exact convergence rate of MD in both centralized and distributed cases for strongly convex and smooth problems. We view MD with a dynamical system lens and leverage quadratic constraints (QCs) to provide convergence guarantees based on the Lyapunov stability. For centralized MD, we establish a semi-definite programming (SDP) that certifies exponentially fast convergence of MD subject to a linear matrix inequality (LMI). We prove that the SDP always has a feasible solution that recovers the optimal GD rate. Next, we analyze the exponential convergence of distributed MD and characterize the rate using two LMIs. To the best of our knowledge, the exact (exponential) rate of distributed MD has not been previously explored in the literature. We present numerical results as a verification of our theory and observe that the richness of the Lyapunov function entails better (worst-case) convergence rates compared to existing works on distributed GD.
• Abstract（参考訳）: ミラー降下 (MD) は、勾配降下 (GD) を含むいくつかの最適化アルゴリズムを仮定する強力な一階最適化手法である。 本研究では,強い凸と滑らかな問題に対して,集中型および分散型両方のケースにおけるMDの正確な収束率について検討する。 動的システムレンズでMDを観察し,2次制約(QC)を活用し,リアプノフ安定性に基づく収束保証を提供する。 集中型MDでは、線形行列不等式(LMI)を受けるMDの指数的高速収束を証明できる半定値プログラミング(SDP)を確立する。 我々は、SDPは常に最適GDレートを回復する実現可能な解を持っていることを証明した。 次に、分散MDの指数収束を分析し、2つのLMIを用いて速度を特徴付ける。 我々の知る限り、分散MDの正確な(指数的な)速度は文献ではこれまで研究されていない。 我々の理論の検証として数値的な結果を示し、リャプノフ関数のリッチさは分散GDの既存の研究よりも(Worst-case)収束率が高いことを観察する。

関連論文リスト

• Distributed Markov Chain Monte Carlo Sampling based on the Alternating Direction Method of Multipliers [143.6249073384419]
  本論文では,乗算器の交互方向法に基づく分散サンプリング手法を提案する。 我々は,アルゴリズムの収束に関する理論的保証と,その最先端性に関する実験的証拠の両方を提供する。 シミュレーションでは,線形回帰タスクとロジスティック回帰タスクにアルゴリズムを配置し,その高速収束を既存の勾配法と比較した。
  論文  参考訳（メタデータ） (2024-01-29T02:08:40Z)
• Stability and Generalization of the Decentralized Stochastic Gradient Descent Ascent Algorithm [80.94861441583275]
  本稿では,分散勾配勾配(D-SGDA)アルゴリズムの一般化境界の複雑さについて検討する。 本研究は,D-SGDAの一般化における各因子の影響を解析した。 また、最適凸凹設定を得るために一般化とバランスをとる。
  論文  参考訳（メタデータ） (2023-10-31T11:27:01Z)
• A Unified Momentum-based Paradigm of Decentralized SGD for Non-Convex Models and Heterogeneous Data [0.261072980439312]
  非汎用目的に対する収束保証を提供するU.MP,D-MP,GT-Dという統一パラダイムを提案する。 理論的には、これらの非MPアルゴリズムに対して収束解析目的を2つのアプローチで提供する。
  論文  参考訳（メタデータ） (2023-03-01T02:13:22Z)
• Optimization of Annealed Importance Sampling Hyperparameters [77.34726150561087]
  Annealed Importance Smpling (AIS) は、深層生成モデルの難易度を推定するために使われる一般的なアルゴリズムである。 本稿では、フレキシブルな中間分布を持つパラメータAISプロセスを提案し、サンプリングに少ないステップを使用するようにブリッジング分布を最適化する。 我々は, 最適化AISの性能評価を行い, 深部生成モデルの限界推定を行い, 他の推定値と比較した。
  論文  参考訳（メタデータ） (2022-09-27T07:58:25Z)
• DR-DSGD: A Distributionally Robust Decentralized Learning Algorithm over Graphs [54.08445874064361]
  本稿では,分散環境下での正規化された分散ロバストな学習問題を解くことを提案する。 Kullback-Liebler正規化関数をロバストなmin-max最適化問題に追加することにより、学習問題を修正されたロバストな問題に還元することができる。 提案アルゴリズムは, 最低分布検定精度を最大10%向上できることを示す。
  論文  参考訳（メタデータ） (2022-08-29T18:01:42Z)
• Utilising the CLT Structure in Stochastic Gradient based Sampling : Improved Analysis and Faster Algorithms [14.174806471635403]
  粒子ダイナミック(IPD)に対するグラディエント・ランゲヴィン・ダイナミクス(SGLD)やランダムバッチ法(RBM)などのサンプリングアルゴリズムの近似を考察する。 近似によって生じる雑音は中央極限定理(CLT)によりほぼガウス的であるが、ブラウン運動はまさにガウス的である。 この構造を利用して拡散過程内の近似誤差を吸収し、これらのアルゴリズムの収束保証を改善する。
  論文  参考訳（メタデータ） (2022-06-08T10:17:40Z)
• False Correlation Reduction for Offline Reinforcement Learning [115.11954432080749]
  本稿では,実効的かつ理論的に証明可能なアルゴリズムであるオフラインRLに対するfalSe Correlation Reduction (SCORE)を提案する。 SCOREは、標準ベンチマーク(D4RL)において、様々なタスクにおいて3.1倍の高速化でSoTA性能を達成することを実証的に示す。
  論文  参考訳（メタデータ） (2021-10-24T15:34:03Z)
• Exact and Approximation Algorithms for Sparse PCA [1.7640556247739623]
  本稿では,MISDP(MISDP)とMISDP(MISDP)について述べる。 次に、それらの連続緩和値の理論的最適性ギャップを分析し、それらが最先端の値よりも強いことを証明する。 市販の解法は一般にMISDPを解くのが難しいため,MISDPと同等の大きさのMILP(mixed-integer linear program)を用いてSPCAを任意の精度で近似する。
  論文  参考訳（メタデータ） (2020-08-28T02:07:08Z)
• A Decentralized Approach to Bayesian Learning [26.74338464389837]
  機械学習に対する分散型アプローチを動機として,分散ランゲヴィン力学の形式を取り入れた協調学習を提案する。 解析の結果,マルコフ連鎖の初期KL偏差は指数関数的に減少していることがわかった。 ローカルに利用可能なデータを持つ個々のエージェントの性能は、中央集権的な設定と同等であり、レートは大幅に改善されている。
  論文  参考訳（メタデータ） (2020-07-14T03:59:17Z)
• Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition [52.08417569774822]
  本稿では,深層学習(深層AUC)により注目度が高まっている,円滑な非凹部min-max問題の解法に焦点をあてる。
  論文  参考訳（メタデータ） (2020-06-12T00:32:21Z)

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

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