Fugu-MT 論文翻訳(概要): The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication

論文の概要: 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$確率勾配推定を逐次計算することができる。本稿では、最適なアルゴリズムを確立するための、一致した上限を持つ新しい下界を示す。

関連論文リスト

Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
離散部分モジュラー問題を連続的に最適化するために,$textbfMA-OSMA$アルゴリズムを提案する。また、一様分布を混合することによりKLの発散を効果的に活用する、プロジェクションフリーな$textbfMA-OSEA$アルゴリズムも導入する。我々のアルゴリズムは最先端OSGアルゴリズムによって提供される$(frac11+c)$-approximationを大幅に改善する。
論文参考訳（メタデータ） (2025-02-07T15:57:56Z)
Optimal Decentralized Smoothed Online Convex Optimization [9.449153668916098]
マルチエージェントSmoothed Online Convex Optimization(SOCO)問題について検討し,通信グラフを通してN$エージェントが対話する。そこで本研究では,マルチエージェントSOCOのための,真に分散化されたアルゴリズムACORDを提案する。通信グラフが時間とともに任意かつ適応的に変化する場合でも,我々の結果は維持される。
論文参考訳（メタデータ） (2024-11-13T05:59:04Z)
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)
A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization [53.14532968909759]
ALEXRと呼ばれる,効率的な単ループプリマル・デュアルブロック座標アルゴリズムを提案する。本研究では, ALEXR の凸面および強凸面の収束速度を滑らか性および非滑らか性条件下で確立する。 CFCCO の ROC 曲線の下での GDRO および部分領域の実験結果から,提案アルゴリズムの有望な性能を示す。
論文参考訳（メタデータ） (2023-12-04T19:00:07Z)
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)

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