論文の概要: On the Divergence of Decentralized Non-Convex Optimization

• arxiv url: http://arxiv.org/abs/2006.11662v1
• Date: Sat, 20 Jun 2020 21:42:06 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-18 23:03:48.292348
• Title: On the Divergence of Decentralized Non-Convex Optimization
• Title（参考訳）: 分散非凸最適化の発散について
• Authors: Mingyi Hong, Siliang Zeng, Junyu Zhang, Haoran Sun
• Abstract要約: 局所関数 $nabla f_iilons 上の局所条件 (LLC) が満たされない場合、既存の分散アルゴリズムのほとんどは分岐する。 特に,提案アルゴリズムは特定の$epsilon-stationary 解に部分収束することを示す。
• 参考スコア（独自算出の注目度）: 44.743563268496715
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study a generic class of decentralized algorithms in which $N$ agents jointly optimize the non-convex objective $f(u):=1/N\sum_{i=1}^{N}f_i(u)$, while only communicating with their neighbors. This class of problems has become popular in modeling many signal processing and machine learning applications, and many efficient algorithms have been proposed. However, by constructing some counter-examples, we show that when certain local Lipschitz conditions (LLC) on the local function gradient $\nabla f_i$'s are not satisfied, most of the existing decentralized algorithms diverge, even if the global Lipschitz condition (GLC) is satisfied, where the sum function $f$ has Lipschitz gradient. This observation raises an important open question: How to design decentralized algorithms when the LLC, or even the GLC, is not satisfied? To address the above question, we design a first-order algorithm called Multi-stage gradient tracking algorithm (MAGENTA), which is capable of computing stationary solutions with neither the LLC nor the GLC. In particular, we show that the proposed algorithm converges sublinearly to certain $\epsilon$-stationary solution, where the precise rate depends on various algorithmic and problem parameters. In particular, if the local function $f_i$'s are $Q$th order polynomials, then the rate becomes $\mathcal{O}(1/\epsilon^{Q-1})$. Such a rate is tight for the special case of $Q=2$ where each $f_i$ satisfies LLC. To our knowledge, this is the first attempt that studies decentralized non-convex optimization problems with neither the LLC nor the GLC.
• Abstract（参考訳）: 我々は,非凸対象である$f(u):=1/N\sum_{i=1}^{N}f_i(u)$を,隣人とのみ通信しながら,N$エージェントが共同で最適化する分散アルゴリズムの一般的なクラスを研究する。 このタイプの問題は、多くの信号処理や機械学習アプリケーションのモデリングで人気となり、多くの効率的なアルゴリズムが提案されている。 しかし、いくつかの逆例を構築することにより、局所関数勾配$\nabla f_i$s 上の局所リプシッツ条件 (LLC) が満たされないとき、既存の分散アルゴリズムのほとんどは、たとえ大域リプシッツ条件 (GLC) が満たされたとしても、和関数$f$ がリプシッツ勾配を持つことを示す。 この観察は、重要なオープンな疑問を提起する: LLCやGLCが満足していないとき、どのように分散アルゴリズムを設計するか? 上記の問題に対処するため,我々は,LLC と GLC のどちらを用いても定常解を計算可能な,Multi-stage gradient tracking algorithm (MAGENTA) と呼ばれる一階法アルゴリズムを設計した。 特に,提案アルゴリズムは,様々なアルゴリズムおよび問題パラメータに依存するような,一定の$\epsilon$-stationary解にサブ線形収束することを示す。 特に、局所関数 $f_i$'s が q$th 次多項式であれば、レートは $\mathcal{o}(1/\epsilon^{q-1})$ となる。 このようなレートは、それぞれ$f_i$ satisfies LLC となる$Q=2$の特別な場合に対して厳密である。 私たちの知る限りでは、llc も glc も持たない非凸最適化問題を研究する最初の試みである。

関連論文リスト

• Certified Multi-Fidelity Zeroth-Order Optimization [4.450536872346658]
  様々な近似レベルで関数を$f$で評価できる多要素ゼロ階最適化の問題を考察する。 我々は、MFDOOアルゴリズムの証明された変種を提案し、そのコスト複雑性を任意のリプシッツ関数$f$に対して有界に導出する。 また、このアルゴリズムがほぼ最適コストの複雑さを持つことを示す$f$-dependent lower boundも証明する。
  論文  参考訳（メタデータ） (2023-08-02T07:20:37Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
  相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。 注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。 本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
  論文  参考訳（メタデータ） (2023-06-30T08:34:29Z)
• A One-Sample Decentralized Proximal Algorithm for Non-Convex Stochastic Composite Optimization [10.762749887051546]
  本稿では,Proxcal$DASA-GTとProxcal$DASA-Aの2時間スケールアルゴリズムを提案する。 以前の作業とは異なり、我々のアルゴリズムは、大きなバッチサイズ、より複雑な単位演算、より強い仮定を必要とせずに、同等の複雑さを達成する。
  論文  参考訳（メタデータ） (2023-02-20T05:16:18Z)
• Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
  次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。 我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
  論文  参考訳（メタデータ） (2023-02-16T13:57:19Z)
• Randomized Block-Coordinate Optimistic Gradient Algorithms for Root-Finding Problems [11.15373699918747]
  大規模設定における非線形方程式の解を近似する2つの新しいアルゴリズムを開発した。 本稿では,機械学習,統計的学習,ネットワーク最適化などにおける顕著な応用を網羅した大規模有限サム包含のクラスに適用する。
  論文  参考訳（メタデータ） (2023-01-08T21:46:27Z)
• Optimal Gradient Sliding and its Application to Distributed Optimization Under Similarity [121.83085611327654]
  積 $r:=p + q$, ここで$r$は$mu$-strong convex類似性である。 エージェントの通信やローカルコールにマスターされた問題を解決する方法を提案する。 提案手法は$mathcalO(sqrtL_q/mu)$法よりもはるかにシャープである。
  論文  参考訳（メタデータ） (2022-05-30T14:28:02Z)
• Derivative-free Alternating Projection Algorithms for General Nonconvex-Concave Minimax Problems [9.173866646584031]
  本稿では,非滑らかなゼロ次ミニマックス問題に対するアルゴリズムを提案する。 また,非コンケーブミニマックス問題に対処できることを示す。
  論文  参考訳（メタデータ） (2021-08-01T15:23:49Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)

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

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