論文の概要: 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$確率勾配推定を逐次計算することができる。
本稿では、最適なアルゴリズムを確立するための、一致した上限を持つ新しい下界を示す。
関連論文リスト
- Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳(メタデータ) (2024-02-14T07:52:00Z) - Diffusion Stochastic Optimization for Min-Max Problems [33.73046548872663]
楽観的勾配法はミニマックス最適化問題に対処するのに有用である。
従来のバージョンでは大きなバッチサイズが必要であり,Samevareps-generativeOGOGと呼ばれる新しい定式化を導入,解析する。
論文 参考訳(メタデータ) (2024-01-26T01:16:59Z) - Faster Convergence with Multiway Preferences [99.68922143784306]
本稿では,符号関数に基づく比較フィードバックモデルについて考察し,バッチとマルチウェイの比較による収束率の解析を行う。
本研究は,マルチウェイ選好による凸最適化の問題を初めて研究し,最適収束率を解析するものである。
論文 参考訳(メタデータ) (2023-12-19T01:52:13Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。