論文の概要: Versatile Single-Loop Method for Gradient Estimator: First and Second Order Optimality, and its Application to Federated Learning

• arxiv url: http://arxiv.org/abs/2209.00361v1
• Date: Thu, 1 Sep 2022 11:05:26 GMT
• ステータス: 処理完了
• システム内更新日: 2022-09-02 13:37:03.047638
• Title: Versatile Single-Loop Method for Gradient Estimator: First and Second Order Optimality, and its Application to Federated Learning
• Title（参考訳）: 勾配推定器の可変単ループ法:一階と二階の最適性とそのフェデレート学習への応用
• Authors: Kazusato Oko, Shunta Akiyama, Tomoya Murata, and Taiji Suzuki
• Abstract要約: 本稿では,SLEDGE (Single-Loop-E Gradient Estimator) という単一ループアルゴリズムを提案する。 既存の手法とは異なり、SLEDGEは、(ii)2階最適、(ii)PL領域における、(iii)少ないデータ以下の複雑さの利点を持つ。
• 参考スコア（独自算出の注目度）: 45.78238792836363
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: While variance reduction methods have shown great success in solving large scale optimization problems, many of them suffer from accumulated errors and, therefore, should periodically require the full gradient computation. In this paper, we present a single-loop algorithm named SLEDGE (Single-Loop mEthoD for Gradient Estimator) for finite-sum nonconvex optimization, which does not require periodic refresh of the gradient estimator but achieves nearly optimal gradient complexity. Unlike existing methods, SLEDGE has the advantage of versatility; (i) second-order optimality, (ii) exponential convergence in the PL region, and (iii) smaller complexity under less heterogeneity of data. We build an efficient federated learning algorithm by exploiting these favorable properties. We show the first and second-order optimality of the output and also provide analysis under PL conditions. When the local budget is sufficiently large and clients are less (Hessian-)~heterogeneous, the algorithm requires fewer communication rounds then existing methods such as FedAvg, SCAFFOLD, and Mime. The superiority of our method is verified in numerical experiments.
• Abstract（参考訳）: 分散還元法は大規模最適化問題を解くのに大きな成功を収めているが、それらの多くは累積誤差に苦しむため、定期的な勾配計算が必要となる。 本稿では,勾配推定器の周期的リフレッシュを必要としない有限サム非凸最適化のために,SLEDGE (Single-Loop mEthoD for Gradient Estimator) という単一ループアルゴリズムを提案する。 既存の方法とは異なり、SLEDGEは汎用性の利点がある。 (i)二階最適性 (ii)pl領域における指数収束、及び (iii)データの不均一性が少ないほど複雑さが小さくなる。 これらの特性を生かして,効率的なフェデレーション学習アルゴリズムを構築する。 出力の1次および2次最適性を示し,pl条件下での分析も行う。 ローカル予算が十分に大きく、クライアントが(ヘッセン)〜ヘテロジニアスである場合、アルゴリズムは通信ラウンドを減らし、FedAvg、SCAFFOLD、Mimeなどの既存のメソッドを必要とする。 本手法の優位性を数値実験で検証した。

関連論文リスト

• Asymptotically Unbiased Instance-wise Regularized Partial AUC Optimization: Theory and Algorithm [101.44676036551537]
  One-way partial AUC (OPAUC) と Two-way partial AUC (TPAUC) はバイナリ分類器の平均性能を測定する。 既存の手法のほとんどはPAUCをほぼ最適化するしかなく、制御不能なバイアスにつながる。 本稿では,分散ロバスト最適化AUCによるPAUC問題の簡易化について述べる。
  論文  参考訳（メタデータ） (2022-10-08T08:26:22Z)
• A Variance-Reduced Stochastic Gradient Tracking Algorithm for Decentralized Optimization with Orthogonality Constraints [7.028225540638832]
  直交制約付き分散最適化のための新しいアルゴリズムを提案する。 VRSGTは、サンプリングと通信の複雑さを同時に低減する直交制約付き分散最適化のための最初のアルゴリズムである。 数値実験では、VRGTSは現実の自律的なサンプルにおいて有望な性能を持つ。
  論文  参考訳（メタデータ） (2022-08-29T14:46:44Z)
• Accelerated Proximal Alternating Gradient-Descent-Ascent for Nonconvex Minimax Machine Learning [12.069630105460766]
  AltGDA(Alternating Table-descentascent)は、様々な機械学習アプリケーションで広く使われている計算最適化アルゴリズムである。 本論文では,最小限の最適化問題を解くために,単一ループの高速なループ勾配計算アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-12-22T04:33:27Z)
• Near-Optimal High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [63.304196997102494]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 既存の非滑らか凸最適化法は、負のパワーまたは対数的な信頼度に依存する境界の複雑さを持つ。 クリッピングを用いた2つの勾配法に対して, 新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box Optimization Framework [100.36569795440889]
  この作業は、一階情報を必要としない零次最適化(ZO)の反復である。 座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
  論文  参考訳（メタデータ） (2020-12-21T17:29:58Z)
• BAMSProd: A Step towards Generalizing the Adaptive Optimization Methods to Deep Binary Model [34.093978443640616]
  最近のBNN(Binary Neural Networks)の性能は大幅に低下している。 BNNの効果的かつ効率的なトレーニングを保証することは未解決の問題である。 そこで本研究では,BAMSProdアルゴリズムを用いて,深部二元モデルの収束特性が量子化誤差と強く関連していることを示す。
  論文  参考訳（メタデータ） (2020-09-29T06:12:32Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Fast Objective & Duality Gap Convergence for Nonconvex-Strongly-Concave Min-Max Problems [52.08417569774822]
  本稿では,円滑な非凹型最小値問題の解法に焦点をあてる。 既存のアルゴリズムの多くは、深層学習(ディープAUCなど)の可能性のため、実際は遅い。
  論文  参考訳（メタデータ） (2020-06-12T00:32:21Z)
• The Strength of Nesterov's Extrapolation in the Individual Convergence of Nonsmooth Optimization [0.0]
  ネステロフの外挿は、非滑らかな問題に対して勾配降下法の個人収束を最適にする強さを持つことを証明している。 提案手法は,設定の非滑らかな損失を伴って正規化学習タスクを解くためのアルゴリズムの拡張である。 本手法は,大規模な1-正規化ヒンジロス学習問題の解法として有効である。
  論文  参考訳（メタデータ） (2020-06-08T03:35:41Z)

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

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