现有去中心化在线优化算法的性能保证过于保守，可能误导算法选择。
Several Performance Bounds on Decentralized Online Optimization are Highly Conservative and Potentially Misleading
- 用性能估计问题方法精确计算算法最坏情况表现
- 部分已有保证保守程度达数个数量级，实际可节省20%损失
- 某些算法在早期阶段通信收益不明显，需调参优化
我们采用性能估计问题方法分析去中心化在线优化算法，该方法可自动计算优化算法的精确最坏情况性能。分析表明，若干现有性能保证非常保守，有时甚至相差多个数量级，可能导致算法选择错误。此外，从最坏情况性能来看，某些算法在相当长的时间内无法从节点间通信中获益。通过调整步长，我们改进了经典方法，使实际最坏情况遗憾降低最多达20%。
原文摘要 · Abstract (English)
We analyze Decentralized Online Optimization algorithms using the Performance Estimation Problem approach which allows, to automatically compute exact worst-case performance of optimization algorithms. Our analysis shows that several available performance guarantees are very conservative, sometimes by multiple orders of magnitude, and can lead to misguided choices of algorithm. Moreover, at least in terms of worst-case performance, some algorithms appear not to benefit from inter-agent communications for a significant period of time. We show how to improve classical methods by tuning their step-sizes, and find that we can save up to 20% on their actual worst-case performance regret.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。