We study a family of algorithms, which we refer to as local update methods, generalizing many federated and meta-learning algorithms. We prove that for quadratic models, local update methods are equivalent to first-order optimization on a surrogate loss we exactly characterize. Moreover, fundamental algorithmic choices (such as learning rates) explicitly govern a trade-off between the condition number of the surrogate loss and its alignment with the true loss. We derive novel convergence rates showcasing these trade-offs and highlight their importance in communication-limited settings. Using these insights, we are able to compare local update methods based on their convergence/accuracy trade-off, not just their convergence to critical points of the empirical loss. Our results shed new light on a broad range of phenomena, including the efficacy of server momentum in federated learning and the impact of proximal client updates.


翻译:我们研究的是一套算法,我们称之为本地更新方法,将许多联合和元学习算法普遍化。我们证明,对于二次模型,本地更新方法相当于替代损失的一级优化。此外,基本的算法选择(如学习率)明确决定了代谢损失条件数与其与真实损失的匹配之间的权衡。我们得出新的趋同率,展示了这些取舍,并强调了它们在通信有限环境下的重要性。我们利用这些洞察力,能够比较基于其趋同/准确性交换的本地更新方法,而不仅仅是它们与经验损失临界点的趋同。我们的结果为一系列广泛的现象提供了新的启示,包括联结学习服务器动力的功效以及准用户更新的影响。

0
下载
关闭预览

相关内容

最新《联邦学习Federated Learning》报告,Federated Learning
专知会员服务
86+阅读 · 2020年12月2日
专知会员服务
52+阅读 · 2020年9月7日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
Federated Learning: 架构
AINLP
4+阅读 · 2020年9月20日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Arxiv
7+阅读 · 2021年4月30日
Arxiv
10+阅读 · 2021年3月30日
Recent advances in deep learning theory
Arxiv
50+阅读 · 2020年12月20日
Arxiv
14+阅读 · 2020年12月17日
Optimization for deep learning: theory and algorithms
Arxiv
104+阅读 · 2019年12月19日
Advances and Open Problems in Federated Learning
Arxiv
18+阅读 · 2019年12月10日
VIP会员
相关VIP内容
相关资讯
Federated Learning: 架构
AINLP
4+阅读 · 2020年9月20日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
相关论文
Arxiv
7+阅读 · 2021年4月30日
Arxiv
10+阅读 · 2021年3月30日
Recent advances in deep learning theory
Arxiv
50+阅读 · 2020年12月20日
Arxiv
14+阅读 · 2020年12月17日
Optimization for deep learning: theory and algorithms
Arxiv
104+阅读 · 2019年12月19日
Advances and Open Problems in Federated Learning
Arxiv
18+阅读 · 2019年12月10日
Top
微信扫码咨询专知VIP会员