提出大步长局部GD，用不稳定加速逻辑回归收敛。
Constant Stepsize Local GD for Logistic Regression: Acceleration by Instability
- 采用任意正步长，突破传统小步长限制。
- 收敛速率达$\mathcal{O}(1/ηK R)$，优于原有$\mathcal{O}(1/R)$。
- 适合异构数据场景，为联邦学习提供新思路。
现有针对异构目标的局部（随机）梯度下降分析要求步长$η\leq 1/K$，其中$K$为通信间隔，以保证目标函数单调递减。本文分析了在可分异构数据下，逻辑回归的局部梯度下降，允许任意步长$η>0$。在$R$次通信轮次和$M$个客户端下，经过初始不稳定阶段（约$\widetilde{\mathcal{O}}(ηK M)$轮），收敛速率达到$\mathcal{O}(1/ηK R)$。该结果优于一般光滑凸目标的$\mathcal{O}(1/R)$速率。分析借鉴了~\cite{wu2024large}中单机情形的不稳定性机制，但在本设定中，异构目标导致的大本地更新成为另一不稳定源。
原文摘要 · Abstract (English)
Existing analysis of Local (Stochastic) Gradient Descent for heterogeneous objectives requires stepsizes $η\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 $η> 0$. With $R$ communication rounds and $M$ clients, we show convergence at a rate $\mathcal{O}(1/ηK R)$ after an initial unstable phase lasting for $\widetilde{\mathcal{O}}(η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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。