强凸条件下，无需已知延迟也能实现更优的在线优化性能。
Revisiting Multi-Agent Asynchronous Online Optimization with Delays: the Strongly Convex Case
- 提出延迟版Follow-the-Leader算法FTDL，利用函数强凸性
- 在未知延迟下实现O(d log T)的后悔界，优于之前的O(√dT)
- 适用于强凸损失函数场景，适合分布式优化研究者
我们重新研究带有延迟的多智能体异步在线优化问题：每轮仅一个智能体活跃决策，其反馈经未知延迟后被所有智能体接收。尽管已有研究在最大延迟d已知或反馈到达顺序具特殊性质的假设下建立了O(√dT)的后悔界，但这些假设在实际中未必成立。本文发现，在损失函数为强凸的情况下，可消除上述假设，并将后悔界显著改进至O(d log T)。为此，我们首先提出经典FTRL算法的延迟变体FTDL，虽简单但需全函数信息作为反馈；进一步，为处理仅能获取梯度反馈的通用情形，结合代理损失函数设计了近似版FTDL。实验表明，该近似算法在强凸情况下优于现有方法。
原文摘要 · Abstract (English)
We revisit multi-agent asynchronous online optimization with delays, where only one of the agents becomes active for making the decision at each round, and the corresponding feedback is received by all the agents after unknown delays. Although previous studies have established an $O(\sqrt{dT})$ regret bound for this problem, they assume that the maximum delay $d$ is knowable or the arrival order of feedback satisfies a special property, which may not hold in practice. In this paper, we surprisingly find that when the loss functions are strongly convex, these assumptions can be eliminated, and the existing regret bound can be significantly improved to $O(d\log T)$ meanwhile. Specifically, to exploit the strong convexity of functions, we first propose a delayed variant of the classical follow-the-leader algorithm, namely FTDL, which is very simple but requires the full information of functions as feedback. Moreover, to handle the more general case with only the gradient feedback, we develop an approximate variant of FTDL by combining it with surrogate loss functions. Experimental results show that the approximate FTDL outperforms the existing algorithm in the strongly convex case.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。