論文の概要: IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method
- arxiv url: http://arxiv.org/abs/2006.06733v1
- Date: Thu, 11 Jun 2020 18:49:06 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-22 14:34:24.528585
- Title: IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method
- Title(参考訳): IDEAL: 個別分散高速化ラグランジアン法
- Authors: Yossi Arjevani, Joan Bruna, Bugra Can, Mert G\"urb\"uzbalaban,
Stefanie Jegelka, Hongzhou Lin
- Abstract要約: 本稿では,局所関数が滑らかで凸な分散最適化環境下での原始的手法設計のためのフレームワークを提案する。
提案手法は,加速ラグランジアン法により誘導されるサブプロブレム列を概ね解いたものである。
加速度勾配降下と組み合わせることで,収束速度が最適で,最近導出された下界と一致した新しい原始アルゴリズムが得られる。
- 参考スコア(独自算出の注目度): 64.15649345392822
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We introduce a framework for designing primal methods under the decentralized
optimization setting where local functions are smooth and strongly convex. Our
approach consists of approximately solving a sequence of sub-problems induced
by the accelerated augmented Lagrangian method, thereby providing a systematic
way for deriving several well-known decentralized algorithms including EXTRA
arXiv:1404.6264 and SSDA arXiv:1702.08704. When coupled with accelerated
gradient descent, our framework yields a novel primal algorithm whose
convergence rate is optimal and matched by recently derived lower bounds. We
provide experimental results that demonstrate the effectiveness of the proposed
algorithm on highly ill-conditioned problems.
- Abstract(参考訳): 本稿では,局所関数が滑らかで凸な分散最適化環境下でのプライマリメソッド設計フレームワークを提案する。
提案手法は, 高速化されたラグランジアン法により誘導される一連のサブプロブレムを概ね解くことで, EXTRA arXiv:1404.6264 や SSDA arXiv:1702.08704 などのよく知られた分散アルゴリズムを導出する体系的な方法を提供する。
加速度勾配降下と組み合わせることで,収束速度が最適で,最近導出された下界と一致した新しい原始アルゴリズムが得られる。
提案手法の有効性を示す実験結果について述べる。
関連論文リスト
- Incremental Quasi-Newton Methods with Faster Superlinear Convergence
Rates [50.36933471975506]
各成分関数が強く凸であり、リプシッツ連続勾配とヘシアンを持つ有限和最適化問題を考える。
最近提案されたインクリメンタル準ニュートン法は、BFGSの更新に基づいて、局所的な超線形収束率を達成する。
本稿では、対称ランク1更新をインクリメンタルフレームワークに組み込むことにより、より効率的な準ニュートン法を提案する。
論文 参考訳(メタデータ) (2024-02-04T05:54:51Z) - Generalized Gradient Flows with Provable Fixed-Time Convergence and Fast
Evasion of Non-Degenerate Saddle Points [8.452349885923507]
グラディエントベースの1次凸最適化アルゴリズムは、機械学習タスクを含むさまざまな領域で広く適用可能である。
最適時間の固定時間理論の最近の進歩に触発されて,高速化最適化アルゴリズムを設計するための枠組みを導入する。
非ド・サドル点を許容する関数に対しては、これらのサドル点を避けるのに必要な時間は初期条件すべてに一様有界であることを示す。
論文 参考訳(メタデータ) (2022-12-07T16:36:23Z) - A Variance-Reduced Stochastic Gradient Tracking Algorithm for
Decentralized Optimization with Orthogonality Constraints [7.028225540638832]
直交制約付き分散最適化のための新しいアルゴリズムを提案する。
VRSGTは、サンプリングと通信の複雑さを同時に低減する直交制約付き分散最適化のための最初のアルゴリズムである。
数値実験では、VRGTSは現実の自律的なサンプルにおいて有望な性能を持つ。
論文 参考訳(メタデータ) (2022-08-29T14:46:44Z) - Continuation Newton methods with deflation techniques for global
optimization problems [3.705839280172101]
最適化問題のグローバルな最小点はエンジニアリングである。
本稿では,この非線形大規模問題に対する新しいメメティックアルゴリズムについて考察する。
我々の数値実験によると、新しいアルゴリズムは制約のない未制約問題に対してうまく機能する。
論文 参考訳(メタデータ) (2021-07-29T09:53:49Z) - Zeroth and First Order Stochastic Frank-Wolfe Algorithms for Constrained
Optimization [13.170519806372075]
2組の制約を持つ凸最適化の問題は、半定値プログラミングの文脈で頻繁に発生する。
最初の制約セットへのプロジェクションは困難であるため、プロジェクションフリーなアルゴリズムを探索する必要がある。
提案アルゴリズムの有効性は, スパース行列推定, 半定緩和によるクラスタリング, および一様スペースカット問題の適用性について検証した。
論文 参考訳(メタデータ) (2021-07-14T08:01:30Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳(メタデータ) (2021-06-08T15:54:44Z) - Delayed Projection Techniques for Linearly Constrained Problems:
Convergence Rates, Acceleration, and Applications [24.763531954075656]
線形制約問題(LCP)に対する新しいプロジェクションベースアルゴリズムのクラスについて検討する。
そこで本研究では,射影を一時的に呼び出す遅延射影手法を提案し,射影周波数を下げ,射影効率を向上させる。
強凸, 一般凸のどちらの場合においても, 投射効率を向上させることが可能であることを示す。
論文 参考訳(メタデータ) (2021-01-05T13:42:41Z) - An Asymptotically Optimal Primal-Dual Incremental Algorithm for
Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。
非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文 参考訳(メタデータ) (2020-10-23T09:12:47Z) - 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) - Second-Order Guarantees in Centralized, Federated and Decentralized
Nonconvex Optimization [64.26238893241322]
単純なアルゴリズムは、多くの文脈において優れた経験的結果をもたらすことが示されている。
いくつかの研究は、非最適化問題を研究するための厳密な分析的正当化を追求している。
これらの分析における重要な洞察は、摂動が局所的な降下アルゴリズムを許容する上で重要な役割を担っていることである。
論文 参考訳(メタデータ) (2020-03-31T16:54:22Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。