提出新方法，显著提升去中心化在线子模优化的性能边界。
Improved Approximate Regret for Decentralized Online Continuous Submodular Maximization via Reductions
- 通过归约将去中心化子模优化转化为凸优化问题，提升算法效率。
- 在一般凸决策集上实现更优的近似后悔界，接近集中式设置表现。
- 适用于复杂决策集且无需投影，适合大规模分布式系统应用。
为扩展去中心化在线学习的应用范围，先前研究提出了若干针对去中心化在线连续子模最大化（D-OCSM）的算法——一种具有连续DR-子模奖励函数的非凸/非凹设置。然而，其近似后悔界与凸设置下的结果存在较大差距。此外，若关注无投影算法（可高效处理复杂决策集），甚至无法恢复集中式设置下的近似后悔界。本文首先证明，在一般凸决策集上，上述两个问题可同时解决；对于向下封闭决策集，第二类问题可被解决，同时第一类问题也得到显著缓解。核心技巧是两种从D-OCSM到去中心化在线凸优化（D-OCO）的归约，分别利用D-OCO算法改进两类情况下的近似后悔界。
原文摘要 · Abstract (English)
To expand the applicability of decentralized online learning, previous studies have proposed several algorithms for decentralized online continuous submodular maximization (D-OCSM) -- a non-convex/non-concave setting with continuous DR-submodular reward functions. However, there exist large gaps between their approximate regret bounds and the regret bounds achieved in the convex setting. Moreover, if focusing on projection-free algorithms, which can efficiently handle complex decision sets, they cannot even recover the approximate regret bounds achieved in the centralized setting. In this paper, we first demonstrate that for D-OCSM over general convex decision sets, these two issues can be addressed simultaneously. Furthermore, for D-OCSM over downward-closed decision sets, we show that the second issue can be addressed while significantly alleviating the first issue. Our key techniques are two reductions from D-OCSM to decentralized online convex optimization (D-OCO), which can exploit D-OCO algorithms to improve the approximate regret of D-OCSM in these two cases, respectively.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。