Fugu-MT 論文翻訳(概要): Distributed Random Reshuffling over Networks

論文の概要: Distributed Random Reshuffling over Networks

arxiv url: http://arxiv.org/abs/2112.15287v5
Date: Thu, 23 Mar 2023 06:44:25 GMT
ステータス: 処理完了
システム内更新日: 2023-03-24 18:56:50.134903
Title: Distributed Random Reshuffling over Networks
Title（参考訳）: ネットワーク上の分散ランダムリシャフリング
Authors: Kun Huang, Xiao Li, Andre Milzarek, Shi Pu, and Junwen Qiu
Abstract要約: 凸関数と滑らかな対象関数の問題を解くために分散resh-upr (D-RR) アルゴリズムを提案する。特に、滑らかな凸対象関数に対して、D-RRはD-T収束率(T がエポック数を数える)を大域ドライブ間の距離で達成する。
参考スコア（独自算出の注目度）: 7.013052033764372
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: In this paper, we consider distributed optimization problems where $n$ agents, each possessing a local cost function, collaboratively minimize the average of the local cost functions over a connected network. To solve the problem, we propose a distributed random reshuffling (D-RR) algorithm that invokes the random reshuffling (RR) update in each agent. We show that D-RR inherits favorable characteristics of RR for both smooth strongly convex and smooth nonconvex objective functions. In particular, for smooth strongly convex objective functions, D-RR achieves $\mathcal{O}(1/T^2)$ rate of convergence (where $T$ counts epoch number) in terms of the squared distance between the iterate and the global minimizer. When the objective function is assumed to be smooth nonconvex, we show that D-RR drives the squared norm of gradient to $0$ at a rate of $\mathcal{O}(1/T^{2/3})$. These convergence results match those of centralized RR (up to constant factors) and outperform the distributed stochastic gradient descent (DSGD) algorithm if we run a relatively large number of epochs. Finally, we conduct a set of numerical experiments to illustrate the efficiency of the proposed D-RR method on both strongly convex and nonconvex distributed optimization problems.
Abstract（参考訳）: 本稿では,ローカルコスト関数を持つ$n$エージェントが,ネットワーク上のローカルコスト関数の平均を協調的に最小化する分散最適化問題を考察する。そこで本研究では,分散ランダムリシャフリング (d-rr) アルゴリズムを提案し,各エージェントのランダムリシャフリング (rr) 更新を起動する。 D-RR は滑らかな凸関数と滑らかな非凸関数の両方に対して RR の良好な特性を継承することを示す。特に、滑らかな凸目的函数に対して、D-RR はイテレートと大域最小化の間の二乗距離の点で$\mathcal{O}(1/T^2)$収束率(ここで$T$はエポック数)を達成する。目的関数が滑らかな非凸であると仮定すると、D-RR は勾配の平方ノルムを $\mathcal{O}(1/T^{2/3})$ の速度で$0$ に駆動することを示す。これらの収束結果は、集中型RR(定数因子まで)と一致し、比較的多数のエポックを実行する場合、分散確率勾配降下(DSGD)アルゴリズムより優れている。最後に,強い凸と非凸の分散最適化問題に対して提案したD-RR法の有効性を示す数値実験を行った。

関連論文リスト

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)
A New Random Reshuffling Method for Nonsmooth Nonconvex Finite-sum Optimization [6.314057999212246]
ランダムリシャッフル技術は、ニューラルネットワークのような大規模アプリケーションで使用される。本稿では,ノルムPRRが生成するランダムリシャッフル型反復が線形設定に収束することを示す。最後に,提案手法に適用可能な最終収束率を導出する。
論文参考訳（メタデータ） (2023-12-02T07:12:00Z)
Distributed Random Reshuffling Methods with Improved Convergence [8.112170817124444]
本稿では,GT-RR(Gdient Tracking with Random Reshuffling)とED-RR(Exact Diffusion with Random Reshuffling)の2つの分散ランダムリシャッフル手法を提案する。
論文参考訳（メタデータ） (2023-06-21T06:05:34Z)
Approximating a RUM from Distributions on k-Slates [88.32814292632675]
与えられた分布を平均で最もよく近似するRUMを求める一般化時間アルゴリズムを求める。我々の理論的結果は、実世界のデータセットに効果的でスケール可能なものを得るという、実践的な結果も得られます。
論文参考訳（メタデータ） (2023-05-22T17:43:34Z)
DR-DSGD: A Distributionally Robust Decentralized Learning Algorithm over Graphs [54.08445874064361]
本稿では,分散環境下での正規化された分散ロバストな学習問題を解くことを提案する。 Kullback-Liebler正規化関数をロバストなmin-max最適化問題に追加することにより、学習問題を修正されたロバストな問題に還元することができる。提案アルゴリズムは, 最低分布検定精度を最大10%向上できることを示す。
論文参考訳（メタデータ） (2022-08-29T18:01:42Z)
Provably Efficient Offline Reinforcement Learning with Trajectory-Wise Reward [66.81579829897392]
我々はPessimistic vAlue iteRaTionとrEward Decomposition (PARTED)という新しいオフライン強化学習アルゴリズムを提案する。 PartEDは、最小2乗ベースの報酬再分配を通じて、ステップごとのプロキシ報酬に軌道を分解し、学習したプロキシ報酬に基づいて悲観的な値を実行する。私たちの知る限りでは、PartEDは、トラジェクティブな報酬を持つ一般のMDPにおいて、証明可能な効率のよい最初のオフラインRLアルゴリズムである。
論文参考訳（メタデータ） (2022-06-13T19:11:22Z)
Non-convex Distributionally Robust Optimization: Non-asymptotic Analysis [16.499651513178012]
分散ロバスト最適化(DRO)は、分散シフトに対してロバストなモデルを学ぶために広く使われている手法である。目的関数はおそらく非滑らかであり,正規化勾配降下を有するにもかかわらず,非漸近収束を保証する。
論文参考訳（メタデータ） (2021-10-24T14:56:38Z)
Distributed stochastic optimization with large delays [59.95552973784946]
大規模最適化問題を解決する最も広く使われている手法の1つは、分散非同期勾配勾配(DASGD)である。 DASGDは同じ遅延仮定の下で大域的最適実装モデルに収束することを示す。
論文参考訳（メタデータ） (2021-07-06T21:59:49Z)
Convergence Analysis of Nonconvex Distributed Stochastic Zeroth-order Coordinate Method [3.860616339202303]
本稿では,$ZOn$局所コスト関数の合計により形成されるグローバルコスト関数を最小化する分散非最適化問題について検討する。エージェントは問題を解くためにzo座標法を近似する。
論文参考訳（メタデータ） (2021-03-24T03:07:46Z)
Parallel Stochastic Mirror Descent for MDPs [72.75921150912556]
無限水平マルコフ決定過程(MDP)における最適政策学習の問題を考える。リプシッツ連続関数を用いた凸プログラミング問題に対してミラー・ディクセントの変種が提案されている。このアルゴリズムを一般の場合において解析し,提案手法の動作中に誤差を蓄積しない収束率の推定値を得る。
論文参考訳（メタデータ） (2021-02-27T19:28:39Z)
Proximal and Federated Random Reshuffling [11.83842808044211]
ランダムリシャッフルのための2つの新しいアルゴリズムを提案する。 ProxRR と FedRR は複合凸有限和最小化問題を解く。 ProxRRは、各イテレーションの近位演算子を評価するアルゴリズムよりも高速です。
論文参考訳（メタデータ） (2021-02-12T18:59:24Z)

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

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