提出分布式在线优化算法，实现平方根级遗憾，适用于连续子模最大化。
Dec-BFTRL: Squre-Root Regret for Decentralized Online Upper-Linearizable Optimization under Separation Access with Application to Continuous Submodular Maximization
- 基于屏障正则化跟踪领袖，通过近似投影映射动作
- 每轮遗憾为√T量级，通信仅需累积对偶状态
- 适合分布式优化与子模最大化场景
研究在分离访问条件下，于动作集上进行去中心化在线上界线性化收益的优化，应用于在线连续递减回报（DR）子模最大化。提出去中心化屏障跟随正则化领袖（Dec-BFTRL）算法，将每个代理的策略与所有本地目标的平均值进行评估。每个代理通过近似规范投影将内部迭代映射为可行动作，仅需通信累积的代理梯度对偶状态，并调用局部 HybridNewton 算法近似最小化通信后的 BFTRL 潜能函数。对于每个代理，网络聚合期望遗憾为 $ ilde{O}( oot T)$。在 $T$ 轮中，每个代理使用 $T$ 次邻居混合步骤和 $ ilde{O}(T)$ 次分离查询。给出了四种包装实例，覆盖三类 DR-子模最大化问题。
原文摘要 · Abstract (English)
We study decentralized online optimization of upper-linearizable payoffs over an action set under efficient separation access, with applications to online continuous diminishing-return (DR) submodular maximization. We propose Decentralized Barrier Follow-the-Regularized-Leader (Dec-BFTRL), and evaluate each agent's played action against the average of all local objectives. Each agent maps an internal iterate to a feasible action through an approximate gauge projection, communicates only a cumulative surrogate-gradient dual state, and invokes the local HybridNewton procedure to approximately minimize its post-communication BFTRL potential. For every agent, we achieve expected network-aggregate regret of $\widetilde O(\sqrt{T})$. Over $T$ rounds, each agent uses $T$ neighbor-mixing steps and $\widetilde O(T)$ separation-oracle calls. We give four wrapper instantiations covering three DR-submodular maximization problems.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。