論文の概要: Stochastic Distributed Optimization under Average Second-order Similarity: Algorithms and Analysis

• arxiv url: http://arxiv.org/abs/2304.07504v2
• Date: Mon, 30 Oct 2023 14:18:37 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-02 03:04:52.031516
• Title: Stochastic Distributed Optimization under Average Second-order Similarity: Algorithms and Analysis
• Title（参考訳）: 平均二階類似性に基づく確率的分散最適化:アルゴリズムと解析
• Authors: Dachao Lin, Yuze Han, Haishan Ye, Zhihua Zhang
• Abstract要約: マスタノードと$n-1$ローカルノードを含む有限サム分散最適化問題について検討する。 本稿では,SVRSとAccSVRSの2つの新しいアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 36.646876613637325
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study finite-sum distributed optimization problems involving a master node and $n-1$ local nodes under the popular $\delta$-similarity and $\mu$-strong convexity conditions. We propose two new algorithms, SVRS and AccSVRS, motivated by previous works. The non-accelerated SVRS method combines the techniques of gradient sliding and variance reduction and achieves a better communication complexity of $\tilde{\mathcal{O}}(n {+} \sqrt{n}\delta/\mu)$ compared to existing non-accelerated algorithms. Applying the framework proposed in Katyusha X, we also develop a directly accelerated version named AccSVRS with the $\tilde{\mathcal{O}}(n {+} n^{3/4}\sqrt{\delta/\mu})$ communication complexity. In contrast to existing results, our complexity bounds are entirely smoothness-free and exhibit superiority in ill-conditioned cases. Furthermore, we establish a nearly matched lower bound to verify the tightness of our AccSVRS method.
• Abstract（参考訳）: 一般化された$\delta$- similarity と $\mu$-strong convexity 条件の下でマスターノードと$n-1$ローカルノードを含む有限サム分散最適化問題を調べる。 本稿では,SVRSとAccSVRSの2つの新しいアルゴリズムを提案する。 非加速SVRS法は、勾配スライディングと分散低減の技法を組み合わせて、既存の非加速アルゴリズムと比較して$\tilde{\mathcal{O}}(n {+} \sqrt{n}\delta/\mu)$の通信複雑性を向上する。 Katyusha X で提案されたフレームワークを応用し、$\tilde{\mathcal{O}}(n {+} n^{3/4}\sqrt{\delta/\mu})$通信複雑性を持つ直接加速版 AccSVRS も開発する。 既存の結果とは対照的に、複雑さの境界は完全に滑らかで、不調なケースでは優れている。 さらに, AccSVRS法の厳密性を検証するために, ほぼ一致した下界を確立する。

関連論文リスト

• Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
  複素勾配問題に対する2つの分散化ZO推定器を提案する。 我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
  論文  参考訳（メタデータ） (2024-10-03T15:04:01Z)
• Accelerated Variance-Reduced Forward-Reflected Methods for Root-Finding Problems [8.0153031008486]
  そこで本研究では,Nesterovの高速前方反射法と分散還元法を新たに提案し,根絶問題の解法を提案する。 我々のアルゴリズムは単ループであり、ルートフィリング問題に特化して設計された非バイアス分散還元推定器の新たなファミリーを利用する。
  論文  参考訳（メタデータ） (2024-06-04T15:23:29Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Finite-Time Error Bounds for Greedy-GQ [20.51105692499517]
  We show that Greedy-GQ algorithm converges fast-time error。 我々の分析は、ステップサイズを選択するために、より高速な収束ステップサイズを提供する。
  論文  参考訳（メタデータ） (2022-09-06T15:04:57Z)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。 本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
  論文  参考訳（メタデータ） (2022-07-18T12:03:26Z)
• Robust Sparse Mean Estimation via Sum of Squares [42.526664955704746]
  本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。 我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
  論文  参考訳（メタデータ） (2022-06-07T16:49:54Z)
• 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)
• DoCoM: Compressed Decentralized Optimization with Near-Optimal Sample Complexity [25.775517797956237]
  本稿では,Douubly Compressed Momentum-assisted tracking algorithm $ttDoCoM$ for communicationを提案する。 我々のアルゴリズムは、実際にいくつかの最先端のアルゴリズムより優れていることを示す。
  論文  参考訳（メタデータ） (2022-02-01T07:27:34Z)
• The Complexity of Nonconvex-Strongly-Concave Minimax Optimization [43.07732143522183]
  本稿では,非強凹型(nc-sc)滑らかなミニマックス問題の近似定常点を求めるための複雑さを確立する。 提案された$Omega-strong$lyconcaveサブ2問題を一般複雑性と平均複雑性の両方で展開する。 提案する有限和設定では,提案するアルゴリズムは条件数にほぼ依存している。
  論文  参考訳（メタデータ） (2021-03-29T18:53:57Z)
• Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations [54.42518331209581]
  私たちは発見するアルゴリズムを見つけます。 epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using $(epsilon,gamma)$surimateランダムランダムポイント。 ここでの私たちの下限は、ノイズのないケースでも新規です。
  論文  参考訳（メタデータ） (2020-06-24T04:41:43Z)
• Nonconvex Zeroth-Order Stochastic ADMM Methods with Lower Function Query Complexity [109.54166127479093]
  ゼロ次法(ゼロ次法、英: Zeroth-order method)は、機械学習問題を解決するための効果的な最適化手法のクラスである。 本稿では,非有限項問題を解くために,より高速なゼロ階交互勾配法乗算器 (MMADMM) を提案する。 我々は、ZOMMAD法が、$epsilon$-stationary pointを見つけるために、より低い関数$O(frac13nfrac1)$を達成することができることを示す。 同時に、より高速なゼロオーダーオンラインADM手法(M)を提案する。
  論文  参考訳（メタデータ） (2019-07-30T02:21:43Z)

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

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