論文の概要: Distributed Random Reshuffling over Networks

• arxiv url: http://arxiv.org/abs/2112.15287v1
• Date: Fri, 31 Dec 2021 03:59:37 GMT
• ステータス: 処理完了
• システム内更新日: 2022-01-03 15:42:42.978536
• Title: Distributed Random Reshuffling over Networks
• Title（参考訳）: ネットワーク上の分散ランダムリシャフリング
• Authors: Kun Huang, Xiao Li, Andre Milzarek, Shi Pu, and Junwen Qiu
• Abstract要約: D-RR は滑らかな凸関数と滑らかな非対象関数の両方に対して RR の優越性を継承することを示す。 これらの結果は、中央集権RR(定数因子まで)と一致する。
• 参考スコア（独自算出の注目度）: 6.730456494479324
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we consider the distributed optimization problem 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 combines the classical distributed gradient descent (DGD) method and Random Reshuffling (RR). We show that D-RR inherits the superiority 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 (here, $T$ counts the total number of iterations) in terms of the squared distance between the iterate and the unique minimizer. When the objective function is assumed to be smooth nonconvex and has Lipschitz continuous component functions, 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).
• Abstract（参考訳）: 本稿では,ローカルコスト関数を持つ$n$エージェントが,ネットワーク上のローカルコスト関数の平均を協調的に最小化する分散最適化問題を考察する。 本研究では,従来の分散勾配降下法 (dgd) 法とランダム回帰法 (rr) を組み合わせた分散ランダムリシャッフル法 (d-rr) を提案する。 D-RR は滑らかな凸関数と滑らかな非凸関数の両方に対して RR の優越性を継承することを示す。 特に、滑らかな強凸対象函数に対して、D-RR はイテレートと一意の最小値の間の平方距離の収束率 $\mathcal{O}(1/T^2)$ を達成する(ここでは、$T$ は反復の総数を数える)。 目的関数が滑らかな非凸でリプシッツ連続成分関数を持つと仮定すると、D-RR が勾配の平方ノルムを $0$ に、$\mathcal{O}(1/T^{2/3})$ の速度で駆動することを示す。 これらの収束結果は(定数因子まで)集中型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)

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

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