PF-LSA 算法解决个性化联邦学习异质性难题
Best of Both Worlds in Federated LSA: Speedup When Possible, Personalization Always
一篇联邦学习理论论文，提出的 PF-LSA 算法不用预知异质性程度，就能同时拿到个性化收敛和线性加速两种保证，做 TD 学习的可以看看。
arXiv 论文研究个性化联邦线性随机逼近（LSA），该框架涵盖个性化时序差分学习。论文提出 PF-LSA 算法，将各 agent 的本地随机更新与全体 agent 的平均更新混合，计算成本与标准联邦方法持平。理论上证明 PF-LSA 在无需预知异质性程度的情况下，同时实现两项保证：各 agent 收敛到个性化解，且在问题相似时随 agent 数量获得线性加速。分析基于将误差分解为共识与分歧两部分：共识误差快速衰减，分歧误差在低异质性场景下可忽略。
Best of Both Worlds in Federated LSA: Speedup When Possible, Personalization Always
We study personalized federated linear stochastic approximation (LSA), a framework which notably encompass personalized temporal difference learning. In this setting, heterogeneous agents collaborate to solve distinct linear fixed-point equations, each corresponding to an agent-specific learning problem. A central open question in personalized learning is whether a single method can adapt to an unknown level of heterogeneity by converging to each agent's personalized solution in all regimes while achieving a linear speedup in the number of agents when their learning problems are sufficiently similar. We answer this question affirmatively by introducing PF-LSA, a minimalist algorithm that mixes each agent's local stochastic update with the average update across agents, at no additional computational cost relative to standard federated methods. We prove that PF-LSA, achieves best-of-both-worlds guarantees without any prior knowledge on the level of heterogeneity. Our analysis is based on a sharp decomposition of the error into consensus and disagreement components. The consensus error decays rapidly, whereas the disagreement error decays more slowly but becomes negligible in low-heterogeneity regimes.
