論文の概要: Distributed Second Order Methods with Fast Rates and Compressed Communication

• arxiv url: http://arxiv.org/abs/2102.07158v1
• Date: Sun, 14 Feb 2021 14:06:45 GMT
• ステータス: 処理完了
• システム内更新日: 2021-02-16 15:15:17.970937
• Title: Distributed Second Order Methods with Fast Rates and Compressed Communication
• Title（参考訳）: 高速通信と圧縮通信を用いた分散二階法
• Authors: Rustem Islamov and Xun Qian and Peter Richt\'arik
• Abstract要約: 分散最適化のための通信効率の高い第2次手法を複数開発する。 我々は大域的な部分線型および線形収束率と高速超線形速度を証明した。 結果は実データセットでの実験結果と共にサポートされます。
• 参考スコア（独自算出の注目度）: 6.069611493148631
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We develop several new communication-efficient second-order methods for distributed optimization. Our first method, NEWTON-STAR, is a variant of Newton's method from which it inherits its fast local quadratic rate. However, unlike Newton's method, NEWTON-STAR enjoys the same per iteration communication cost as gradient descent. While this method is impractical as it relies on the use of certain unknown parameters characterizing the Hessian of the objective function at the optimum, it serves as the starting point which enables us design practical variants thereof with strong theoretical guarantees. In particular, we design a stochastic sparsification strategy for learning the unknown parameters in an iterative fashion in a communication efficient manner. Applying this strategy to NEWTON-STAR leads to our next method, NEWTON-LEARN, for which we prove local linear and superlinear rates independent of the condition number. When applicable, this method can have dramatically superior convergence behavior when compared to state-of-the-art methods. Finally, we develop a globalization strategy using cubic regularization which leads to our next method, CUBIC-NEWTON-LEARN, for which we prove global sublinear and linear convergence rates, and a fast superlinear rate. Our results are supported with experimental results on real datasets, and show several orders of magnitude improvement on baseline and state-of-the-art methods in terms of communication complexity.
• Abstract（参考訳）: 分散最適化のための通信効率の高い第2次手法を複数開発する。 我々の最初の手法NEWTON-STARはニュートンの手法の変種であり、その高速局所二次速度を継承する。 しかし、Newtonの方法とは異なり、NewTON-STARは勾配降下と同じ反復通信コストを楽しんでいます。 本手法は目的関数のヘッシアンを最適に特徴付ける未知のパラメータを用いるため実用的でないが、強い理論的保証により実用的変種を設計できる出発点として機能する。 特に,未知のパラメータを反復的に学習するための確率的スパーシフィケーション戦略を,コミュニケーション効率良く設計する。 NEWTON-STARにこの戦略を適用すると、次の方法であるNEWTON-LEARNにつながり、条件番号とは無関係に局所線形および超線形率を証明します。 適用する場合、最先端の手法と比較して、この手法は劇的に優れた収束挙動を示すことができる。 最後に,次の手法である CUBIC-NEWTON-LEARN を導いた立方正則化を用いたグローバル化戦略を開発し,グローバルサブリニアおよび線形収束率,高速スーパーリニアレートを証明した。 その結果,実データを用いた実験結果が支持され,通信の複雑さの観点から,ベースライン法と最先端法において数桁の改善がみられた。

関連論文リスト

• Unified Convergence Theory of Stochastic and Variance-Reduced Cubic Newton Methods [55.51077907483634]
  広範に知られているキュービックニュートン法について検討し,分散低減のための一般的な枠組みを提案する。 本研究では,大規模なバッチを伴わずにそのようなメソッドを使用できる可能性を検討するとともに,すべてのメソッドが動作するのに十分な,非常に単純な仮定を用いる。
  論文  参考訳（メタデータ） (2023-02-23T12:18:28Z)
• Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [115.64182929032334]
  そこで本稿では,制約のないmin-max問題の大域的サドル点を求めるために,正確にかつ不正確なニュートン型手法を提案し,解析する。 1次法と比較して、min-maxの2次法の研究は比較的限られている。
  論文  参考訳（メタデータ） (2022-10-23T21:24:37Z)
• FedNew: A Communication-Efficient and Privacy-Preserving Newton-Type Method for Federated Learning [75.46959684676371]
  我々は、クライアントからPSにヘッセン情報を送信する必要がないFedNewという新しいフレームワークを紹介した。 FedNewは勾配情報を隠蔽し、既存の最先端技術と比べてプライバシー保護のアプローチをもたらす。
  論文  参考訳（メタデータ） (2022-06-17T15:21:39Z)
• On the efficiency of Stochastic Quasi-Newton Methods for Deep Learning [0.0]
  深部記憶ネットワークのための準ニュートン学習アルゴリズムの動作について検討する。 準ニュートンは効率が良く、よく知られたAdamの1次実行よりも性能が優れていることを示す。
  論文  参考訳（メタデータ） (2022-05-18T20:53:58Z)
• Basis Matters: Better Communication-Efficient Second Order Methods for Federated Learning [5.400491728405083]
  Em Basis Learn (BL) はニュートン方式の通信コストを大幅に削減できることを示す。 Em BL法と双方向圧縮機構を併用して通信コストを削減する新しいNewton-type法(BL1)を提案する。 条件数に依存しない局所線形および超線形の速度を証明した。
  論文  参考訳（メタデータ） (2021-11-02T19:09:41Z)
• A Boosting Approach to Reinforcement Learning [59.46285581748018]
  複雑度が状態数に依存しない意思決定プロセスにおける強化学習のための効率的なアルゴリズムについて検討する。 このような弱い学習手法の精度を向上させることができる効率的なアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2021-08-22T16:00:45Z)
• Random extrapolation for primal-dual coordinate descent [61.55967255151027]
  本稿では,データ行列の疎度と目的関数の好適な構造に適応する,ランダムに外挿した原始-双対座標降下法を提案する。 一般凸凹の場合, 主対差と目的値に対するシーケンスのほぼ確実に収束と最適サブ線形収束率を示す。
  論文  参考訳（メタデータ） (2020-07-13T17:39:35Z)
• A Hybrid-Order Distributed SGD Method for Non-Convex Optimization to Balance Communication Overhead, Computational Complexity, and Convergence Rate [28.167294398293297]
  通信負荷の少ない分散勾配降下法(SGD)を提案する。 各イテレーションにおける計算複雑性を低減するために、ワーカノードは、方向微分をゼロ階勾配推定で近似する。
  論文  参考訳（メタデータ） (2020-03-27T14:02:15Z)
• Interpolation Technique to Speed Up Gradients Propagation in Neural ODEs [71.26657499537366]
  本稿では,ニューラルネットワークモデルにおける勾配の効率的な近似法を提案する。 我々は、分類、密度推定、推論近似タスクにおいて、ニューラルODEをトレーニングするリバースダイナミック手法と比較する。
  論文  参考訳（メタデータ） (2020-03-11T13:15:57Z)
• On Newton Screening [14.040371216692645]
  我々はNewton Screening (NS) と呼ばれる新しいスクリーニング手法を開発した。 NSは、一段階局所収束を達成するという意味で、最適収束特性を有することを示す。
  論文  参考訳（メタデータ） (2020-01-27T11:25:33Z)

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

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