发现联邦学习中存在不随客户端数变化的二阶偏差项，解释了为何平均无法完全消除误差。
Beyond Client Averaging: A Client-Independent Second-Order Stationary-Bias Component in Stochastic SCAFFOLD
- 揭示了客户端独立的二阶偏差机制，源于局部控制波动与梯度噪声的相互作用
- 证明当客户端数量增加时，$O(γ^2)$ 阶偏差仍存在且系数不为零
- 适用于一维同质固定步数场景，对理解联邦优化收敛性有重要意义
现有常步长分析表明随机SCAFFOLD存在主导的 $O(γ/N)$ 稳态均值偏差，高阶偏差在客户端增多时仍持续存在，但未识别出系数层面的首个客户端无关贡献。针对全参与、一维同质客户端、固定局部步数 $H$、有界加性梯度噪声的随机SCAFFOLD，我们统一证明 $N\ge2$ 时，$$ \mathbb{E}_{π_{γ,N,H}}[x]-x^\star = -\frac{f'''(x^\star)σ^2}{4f''(x^\star)^2}\fracγ{N} - \frac{f'''(x^\star)σ^2}{12f''(x^\star)} \frac{(H-1)(5H-1)}{H}γ^2 +O_H\left(\frac{γ^2}{N}+γ^3\right). $$ 因此客户端平均可抑制 $O(γ/N)$ 主导偏差，但若系数非零，无法消除客户端无关的 $O(γ^2)$ 项。其机制为间接：尽管直接控制项在全局平均中路径相消，但控制仍影响每轮局部轨迹及其二阶矩。新梯度噪声与持续控制波动生成局部二阶矩修正，非二次曲率将其转化为稳态均值偏差。该系数在二次目标下消失。数值实验验证了预测系数、其随客户端数增长的持久性及联合余项。结果限于一维同质固定-$H$设置。
原文摘要 · Abstract (English)
Existing constant-step analysis of stochastic \Scaf{} identifies a leading $O(γ/N)$ stationary mean bias and shows that higher-order bias can persist as the client count increases, but does not identify the first client-independent contribution at coefficient level. For full-participation stochastic \Scaf{} with one-dimensional homogeneous clients, fixed local-step count $H$, and bounded additive gradient noise, we prove, uniformly over $N\ge2$, $$ \begin{aligned} \mathbb{E}_{π_{γ,N,H}}[x]-x^\star ={}& -\frac{f'''(x^\star)σ^2}{4f''(x^\star)^2}\fracγ{N}\\ &- \frac{f'''(x^\star)σ^2}{12f''(x^\star)} \frac{(H-1)(5H-1)}{H}γ^2 +O_H\!\left(\frac{γ^2}{N}+γ^3\right). \end{aligned} $$ Hence client averaging suppresses the leading $O(γ/N)$ bias but does not remove the client-independent $O(γ^2)$ component when its coefficient is nonzero. The mechanism is indirect: although the direct control contribution cancels pathwise in the linear global average, the controls still alter within-round local trajectories and their second moments. Fresh gradient noise and persistent control fluctuations therefore generate local second-moment corrections that nonquadratic curvature converts into stationary mean bias. The coefficient vanishes for quadratic objectives. Numerical experiments are consistent with the predicted coefficient, its persistence as client count increases, and the stated joint remainder. The result is restricted to the one-dimensional homogeneous fixed-$H$ setting.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。