論文の概要: Constant Stepsize Local GD for Logistic Regression: Acceleration by Instability
- arxiv url: http://arxiv.org/abs/2506.13974v1
- Date: Mon, 16 Jun 2025 20:29:00 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-06-18 17:34:59.234113
- Title: Constant Stepsize Local GD for Logistic Regression: Acceleration by Instability
- Title（参考訳）: ロジスティック回帰のための局所GDの定ステップ化:不安定による加速
- Authors: Michael Crawshaw, Blake Woodworth, Mingrui Liu,
- Abstract要約: 我々は,任意の段数 $eta > 0$ を用いて,分離可能な異種データを用いたロジスティック回帰のための局所勾配 Descent の解析を行った。
我々の分析は、非常に大きなステップサイズによって不安定が引き起こされる、citewu2024largeの単一マシン解析と並行して行われる。
- 参考スコア（独自算出の注目度）: 13.332982107151434
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Existing analysis of Local (Stochastic) Gradient Descent for heterogeneous objectives requires stepsizes $\eta \leq 1/K$ where $K$ is the communication interval, which ensures monotonic decrease of the objective. In contrast, we analyze Local Gradient Descent for logistic regression with separable, heterogeneous data using any stepsize $\eta > 0$. With $R$ communication rounds and $M$ clients, we show convergence at a rate $\mathcal{O}(1/\eta K R)$ after an initial unstable phase lasting for $\widetilde{\mathcal{O}}(\eta K M)$ rounds. This improves upon the existing $\mathcal{O}(1/R)$ rate for general smooth, convex objectives. Our analysis parallels the single machine analysis of~\cite{wu2024large} in which instability is caused by extremely large stepsizes, but in our setting another source of instability is large local updates with heterogeneous objectives.
- Abstract（参考訳）: 異種目的のための局所(確率的)グラディエントDescentの既存の解析では、$\eta \leq 1/K$をステップ化する必要がある。
対照的に、我々は、任意のステップサイズ$\eta > 0$ を用いて、分離可能な異種データを用いて、ロジスティック回帰のための局所勾配 Descent を解析する。
$R$通信ラウンドと$M$クライアントでは、初期不安定位相が$\widetilde{\mathcal{O}}(\eta K M)$ラウンドで持続した後、$\mathcal{O}(1/\eta K R)$で収束を示す。
これは、一般的な滑らかで凸な目的に対して既存の $\mathcal{O}(1/R)$ レートを改善する。
我々の分析は、非常に大きなステップサイズによって不安定が引き起こされる~\cite{wu2024large} の単一マシン解析と平行しているが、我々の設定では別の不安定の原因は、不均一な目的を持った大きなローカル更新である。
関連論文リスト
- From Continual Learning to SGD and Back: Better Rates for Continual Linear Models [50.11453013647086]
以前見られたタスクの損失を、$k$の繰り返しの後、忘れること、すなわち、分析する。
実現可能な最小二乗の設定において、新しい最上界を創出する。
我々は、タスクを繰り返しないランダム化だけで、十分に長いタスクシーケンスで破滅的な事態を防げることを初めて証明した。
論文 参考訳（メタデータ） (2025-04-06T18:39:45Z) - Local Steps Speed Up Local GD for Heterogeneous Distributed Logistic Regression [13.332982107151434]
局所的なステップで$O(1/KR)$、十分に大きな$R$通信ラウンドで$O(1/KR)$の収束を示す。
任意の問題に適用される局所GDの既存の収束保証は、少なくとも$Omega (1/R)$である。
論文 参考訳（メタデータ） (2025-01-23T16:09:26Z) - Convergence of Unadjusted Langevin in High Dimensions: Delocalization of Bias [13.642712817536072]
問題の次元が$d$になるにつれて、所望の誤差内で収束を保証するのに必要なイテレーションの数が増加することを示す。
私たちが取り組んだ重要な技術的課題は、収束を測定するための$W_2,ellinfty$メートル法に一段階の縮約性がないことである。
論文 参考訳（メタデータ） (2024-08-20T01:24:54Z) - Generalization and Stability of Interpolating Neural Networks with
Minimal Width [37.908159361149835]
補間系における勾配によって訓練された浅層ニューラルネットワークの一般化と最適化について検討する。
トレーニング損失数は$m=Omega(log4 (n))$ニューロンとニューロンを最小化する。
m=Omega(log4 (n))$のニューロンと$Tapprox n$で、テスト損失のトレーニングを$tildeO (1/)$に制限します。
論文 参考訳（メタデータ） (2023-02-18T05:06:15Z) - An Improved Analysis of Gradient Tracking for Decentralized Machine
Learning [34.144764431505486]
トレーニングデータが$n$エージェントに分散されるネットワーク上での分散機械学習を検討する。
エージェントの共通の目標は、すべての局所損失関数の平均を最小化するモデルを見つけることである。
ノイズのない場合、$p$を$mathcalO(p-1)$から$mathcalO(p-1)$に改善します。
論文 参考訳（メタデータ） (2022-02-08T12:58:14Z) - 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) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳（メタデータ） (2020-06-04T17:51:00Z) - A Simple Convergence Proof of Adam and Adagrad [74.24716715922759]
我々はAdam Adagradと$O(d(N)/st)$アルゴリズムの収束の証明を示す。
Adamはデフォルトパラメータで使用する場合と同じ収束$O(d(N)/st)$で収束する。
論文 参考訳（メタデータ） (2020-03-05T01:56:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。