論文の概要: The Min-Max Complexity of Distributed Stochastic Convex Optimization
with Intermittent Communication
- arxiv url: http://arxiv.org/abs/2102.01583v1
- Date: Tue, 2 Feb 2021 16:18:29 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-04 10:03:08.432890
- Title: The Min-Max Complexity of Distributed Stochastic Convex Optimization
with Intermittent Communication
- Title(参考訳): 間欠通信による分散確率凸最適化のMin-Max複雑性
- Authors: Blake Woodworth, Brian Bullins, Ohad Shamir, Nathan Srebro
- Abstract要約: 間欠的通信環境における分散凸最適化(ログファクタまで)の分極的複雑性を解消する。
本稿では、最適なアルゴリズムを確立するための、一致した上限を持つ新しい下界を示す。
- 参考スコア(独自算出の注目度): 61.60069865891783
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We resolve the min-max complexity of distributed stochastic convex
optimization (up to a log factor) in the intermittent communication setting,
where $M$ machines work in parallel over the course of $R$ rounds of
communication to optimize the objective, and during each round of
communication, each machine may sequentially compute $K$ stochastic gradient
estimates. We present a novel lower bound with a matching upper bound that
establishes an optimal algorithm.
- Abstract(参考訳): 間欠的通信設定における分散確率凸最適化(対数係数まで)の最小限の複雑性を解消し、M$マシンが目標を最適化するために$R$ラウンドの通信に対して並列に動作するようにし、各通信において各マシンが$K$確率勾配推定を逐次計算することができる。
本稿では、最適なアルゴリズムを確立するための、一致した上限を持つ新しい下界を示す。
関連論文リスト
- Federated Conditional Stochastic Optimization [110.513884892319]
条件付き最適化は、不変学習タスク、AUPRC、AMLなど、幅広い機械学習タスクで見られる。
本稿では,分散フェデレーション学習のためのアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-10-04T01:47:37Z) - PRECISION: Decentralized Constrained Min-Max Learning with Low
Communication and Sample Complexities [25.153506493249854]
min-max最適化問題に対する適応型マルチエージェント学習手法を提案する。
また,反復回数を削減できるPrecisionというアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-03-05T00:26:10Z) - Optimal Algorithms for Stochastic Complementary Composite Minimization [76.20428372514958]
統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。
予測と高い確率で、新しい過剰なリスク境界を提供する。
我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
論文 参考訳(メタデータ) (2022-11-03T12:40:24Z) - 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) - Distributed stochastic proximal algorithm with random reshuffling for
non-smooth finite-sum optimization [28.862321453597918]
非滑らかな有限サム最小化は機械学習の基本的な問題である。
本稿では,確率的リシャフリングを用いた分散近位勾配アルゴリズムを開発し,その問題の解法を提案する。
論文 参考訳(メタデータ) (2021-11-06T07:29:55Z) - The Minimax Complexity of Distributed Optimization [0.0]
分散最適化に適用可能な古典的なオラクルフレームワークの拡張である「グラフオラクルモデル」を紹介します。
私は「間欠的コミュニケーション設定」の具体例に焦点をあてる
コンベックス設定におけるSGD(Local Descent)アルゴリズムの理論的特性を解析する。
論文 参考訳(メタデータ) (2021-09-01T15:18:33Z) - Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
高精度リコール曲線(AUPRC)に基づく領域の最適化について検討し,不均衡なタスクに広く利用されている。
我々は、$O (1/epsilon4)$のより優れた反復による、$epsilon$定常解を見つけるための新しい運動量法を開発する。
また,O(1/epsilon4)$と同じ複雑さを持つ適応手法の新たなファミリを設計し,実際により高速な収束を享受する。
論文 参考訳(メタデータ) (2021-07-02T16:21:52Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。
本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文 参考訳(メタデータ) (2021-06-02T22:03:36Z) - Convergence Analysis of Nonconvex Distributed Stochastic Zeroth-order
Coordinate Method [3.860616339202303]
本稿では,$ZOn$局所コスト関数の合計により形成されるグローバルコスト関数を最小化する分散非最適化問題について検討する。
エージェントは問題を解くためにzo座標法を近似する。
論文 参考訳(メタデータ) (2021-03-24T03:07:46Z) - Byzantine-Resilient Non-Convex Stochastic Gradient Descent [61.6382287971982]
敵対的レジリエントな分散最適化。
機械は独立して勾配を計算し 協力することができます
私達のアルゴリズムは新しい集中の技術およびサンプル複雑性に基づいています。
それは非常に実用的です:それはないときすべての前の方法の性能を改善します。
セッティングマシンがあります。
論文 参考訳(メタデータ) (2020-12-28T17:19:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。