← 피드로
[Submitted on 31 Aug 2026 (v1), last revised 30 Sep 2026 (this version, v3)]
Abstract: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 wrapper instantiations covering four up-concave or DR-submodular maximization problems.
Submission history
From: Yiyang Lu [view email]
[v1]
Mon, 31 Aug 2026 05:29:54 UTC (40 KB)
[v2]
Sat, 5 Sep 2026 21:45:56 UTC (39 KB)
[v3]
Wed, 30 Sep 2026 02:47:16 UTC (39 KB)
추출 본문 · 출처: arxiv.org · https://arxiv.org/abs/2608.30271