論文の概要: 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 を導いた立方正則化を用いたグローバル化戦略を開発し,グローバルサブリニアおよび線形収束率,高速スーパーリニアレートを証明した。
その結果,実データを用いた実験結果が支持され,通信の複雑さの観点から,ベースライン法と最先端法において数桁の改善がみられた。
関連論文リスト
- Symmetric Rank-One Quasi-Newton Methods for Deep Learning Using Cubic Regularization [0.5120567378386615]
アダムやアダグラッドのような一階降下や他の一階変種は、ディープラーニングの分野で一般的に使われている。
しかし、これらの手法は曲率情報を活用しない。
準ニュートン法は、以前計算された低ヘッセン近似を再利用する。
論文 参考訳（メタデータ） (2025-02-17T20:20:11Z) - Incremental Gauss--Newton Methods with Superlinear Convergence Rates [16.92437325972209]
Incrmental Gauss--Newton(IGN)法を明示的な超線形収束速度で導入する。
特に、有限サム構造を持つ非線形最小二乗で問題を定式化する。
また、より高速な超線形収束率を得るIGN法に対するミニバッチ拡張も提供する。
論文 参考訳（メタデータ） (2024-07-03T15:26:34Z) - Incremental Quasi-Newton Methods with Faster Superlinear Convergence
Rates [50.36933471975506]
各成分関数が強く凸であり、リプシッツ連続勾配とヘシアンを持つ有限和最適化問題を考える。
最近提案されたインクリメンタル準ニュートン法は、BFGSの更新に基づいて、局所的な超線形収束率を達成する。
本稿では、対称ランク1更新をインクリメンタルフレームワークに組み込むことにより、より効率的な準ニュートン法を提案する。
論文 参考訳（メタデータ） (2024-02-04T05:54:51Z) - Newton-CG methods for nonconvex unconstrained optimization with Hölder continuous Hessian [53.044526424637866]
我々は、H"古いヘッセンによる2つの微分可能な目的関数を最小化する非制約非制約最適化問題を考える。
まずニュートン共役法(Newton-conjugate, Newton-CG)を提案する。
本稿では,パラメータフリーなNewtonCG法において,優れた実用性能を示すための予備的な数値計算結果を提案する。
論文 参考訳（メタデータ） (2023-11-22T01:50:43Z) - Resource-Adaptive Newton's Method for Distributed Learning [16.588456212160928]
本稿では,Newtonの手法の限界を克服するRANLというアルゴリズムを提案する。
従来の一階法とは異なり、RANLは問題の条件数から著しく独立している。
論文 参考訳（メタデータ） (2023-08-20T04:01:30Z) - FedNew: A Communication-Efficient and Privacy-Preserving Newton-Type
Method for Federated Learning [75.46959684676371]
我々は、クライアントからPSにヘッセン情報を送信する必要がないFedNewという新しいフレームワークを紹介した。
FedNewは勾配情報を隠蔽し、既存の最先端技術と比べてプライバシー保護のアプローチをもたらす。
論文 参考訳（メタデータ） (2022-06-17T15:21:39Z) - 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) - Acceleration Methods [57.202881673406324]
まず2次最適化問題を用いて加速法を2つ導入する。
我々は、ネステロフの精巧な研究から始まる運動量法を詳細に論じる。
我々は、ほぼ最適な収束率に達するための一連の簡単な手法である再起動スキームを議論することで結論付ける。
論文 参考訳（メタデータ） (2021-01-23T17:58:25Z) - Random extrapolation for primal-dual coordinate descent [61.55967255151027]
本稿では,データ行列の疎度と目的関数の好適な構造に適応する,ランダムに外挿した原始-双対座標降下法を提案する。
一般凸凹の場合, 主対差と目的値に対するシーケンスのほぼ確実に収束と最適サブ線形収束率を示す。
論文 参考訳（メタデータ） (2020-07-13T17:39:35Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。