Fugu-MT 論文翻訳(概要): Local Steps Speed Up Local GD for Heterogeneous Distributed Logistic Regression

論文の概要: Local Steps Speed Up Local GD for Heterogeneous Distributed Logistic Regression

arxiv url: http://arxiv.org/abs/2501.13790v1
Date: Thu, 23 Jan 2025 16:09:26 GMT
ステータス: 翻訳完了
システム内更新日: 2025-01-24 15:57:35.322720
Title: Local Steps Speed Up Local GD for Heterogeneous Distributed Logistic Regression
Title（参考訳）: 不均一な分散ロジスティック回帰のためのローカルGDの高速化
Authors: Michael Crawshaw, Blake Woodworth, Mingrui Liu,
Abstract要約: 局所的なステップで$O(1/KR)$、十分に大きな$R$通信ラウンドで$O(1/KR)$の収束を示す。任意の問題に適用される局所GDの既存の収束保証は、少なくとも$Omega (1/R)$である。
参考スコア（独自算出の注目度）: 13.332982107151434
License:
Abstract: We analyze two variants of Local Gradient Descent applied to distributed logistic regression with heterogeneous, separable data and show convergence at the rate $O(1/KR)$ for $K$ local steps and sufficiently large $R$ communication rounds. In contrast, all existing convergence guarantees for Local GD applied to any problem are at least $\Omega(1/R)$, meaning they fail to show the benefit of local updates. The key to our improved guarantee is showing progress on the logistic regression objective when using a large stepsize $\eta \gg 1/K$, whereas prior analysis depends on $\eta \leq 1/K$.
Abstract（参考訳）: 我々は、分散ロジスティック回帰に適用された局所勾配Descentの2つの変種を異質で分離可能なデータで解析し、O(1/KR)$ for $K$ローカルステップと十分に大きなR$通信ラウンドで収束を示す。対照的に、任意の問題に適用される局所GDの既存の収束保証は、少なくとも$\Omega(1/R)$であり、ローカル更新の利点を示すことができない。改善された保証の鍵は、大きなステップサイズ$\eta \gg 1/K$を使用する場合のロジスティック回帰目標の進捗を示すことであるが、事前の分析は$\eta \leq 1/K$に依存する。

関連論文リスト

Convergence of Unadjusted Langevin in High Dimensions: Delocalization of Bias [13.642712817536072]
問題の次元が$d$になるにつれて、所望の誤差内で収束を保証するのに必要なイテレーションの数が増加することを示す。私たちが取り組んだ重要な技術的課題は、収束を測定するための$W_2,ellinfty$メートル法に一段階の縮約性がないことである。
論文参考訳（メタデータ） (2024-08-20T01:24:54Z)
Convergence Analysis of Decentralized ASGD [1.8710230264817358]
本稿では,ノード間の部分同期や制限的ネットワークトポロジを必要としない分散非同期SGD(DASGD)に対する新しい収束速度解析法を提案する。我々の収束証明は、固定段数と任意の非滑らかで同質でL字型の目的函数を仮定する。
論文参考訳（メタデータ） (2023-09-07T14:50:31Z)
Gradient Descent Converges Linearly for Logistic Regression on Separable Data [17.60502131429094]
変動学習率による勾配勾配降下は損失$f(x) leq 1.1 cdot f(x*) + epsilon$ロジスティック回帰目標を示す。また、ロジスティックなレグレッションを緩やかなレグレッションに適用し、スペルシ・エラーのトレードオフを指数関数的に改善する。
論文参考訳（メタデータ） (2023-06-26T02:15:26Z)
Almost Linear Constant-Factor Sketching for $\ell_1$ and Logistic Regression [74.28017932704704]
我々は,従来の難解なスケッチとターンタイルストリーミングの結果を$ell_1$とロジスティック回帰で改善する。また、入力空間の間隔で1+varepsilon$近似を出力するトレードオフも行います。我々のスケッチは、データ依存正規化器が個々のロジスティック損失の分散に対応するような、正規化されたロジスティック回帰を近似するために拡張することができる。
論文参考訳（メタデータ） (2023-03-31T18:12:33Z)
Faster Convergence of Local SGD for Over-Parameterized Models [1.5504102675587357]
現代の機械学習アーキテクチャは、しばしば非常に表現力が高い。不均一なデータ設定における過パラメータ化関数に対する局所SGD(またはFedAvg)の収束を解析する。一般凸損失関数に対しては、$O(K/T)$の誤差が成立する。非剰余関数に対しては、どちらの場合も$O(K/T)$の誤差が証明される。確立された収束率を、合理的に小さなステップサイズで一定の要因に密着した問題インスタンスを提供することで、結果を完成させる。
論文参考訳（メタデータ） (2022-01-30T04:05:56Z)
Communication-efficient SGD: From Local SGD to One-Shot Averaging [16.00658606157781]
複数の作業者に対して並列化することで,勾配降下(SGD)の高速化を検討する。そこで本研究では,反復数の増加に伴って通信頻度を小さくすることで,全体の通信を減らし,局所的なSGD方式を提案する。
論文参考訳（メタデータ） (2021-06-09T01:10:34Z)
Faster Convergence of Stochastic Gradient Langevin Dynamics for Non-Log-Concave Sampling [110.88857917726276]
我々は,非log-concaveとなる分布のクラスからサンプリングするために,勾配ランゲヴィンダイナミクス(SGLD)の新たな収束解析を行う。我々のアプローチの核心は、補助的時間反転型マルコフ連鎖を用いたSGLDのコンダクタンス解析である。
論文参考訳（メタデータ） (2020-10-19T15:23:18Z)
Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。 i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文参考訳（メタデータ） (2020-07-16T06:44:44Z)
On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems [75.58134963501094]
本稿では,勾配降下(SGD)の軌跡を解析する。我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
論文参考訳（メタデータ） (2020-06-19T14:11:26Z)
A Unified Theory of Decentralized SGD with Changing Topology and Local Updates [70.9701218475002]
分散通信方式の統一収束解析を導入する。いくつかの応用に対して普遍収束率を導出する。私たちの証明は弱い仮定に依存している。
論文参考訳（メタデータ） (2020-03-23T17:49:15Z)
Non-asymptotic Convergence of Adam-type Reinforcement Learning Algorithms under Markovian Sampling [56.394284787780364]
本稿では、ポリシー勾配(PG)と時間差(TD)学習の2つの基本RLアルゴリズムに対して、最初の理論的収束解析を行う。一般の非線形関数近似の下では、PG-AMSGradは定常点の近傍に収束し、$mathcalO(log T/sqrtT)$である。線形関数近似の下では、一定段階のTD-AMSGradは$mathcalO(log T/sqrtT)の速度で大域的最適化の近傍に収束する。
論文参考訳（メタデータ） (2020-02-15T00:26:49Z)

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