Dec-BFTRL: Squre-Root Regret for Decentralized Online Upper-Linearizable Optimization under Separation Access with Application to Continuous Submodular Maximization
2026-08-31 • Artificial Intelligence
Artificial IntelligenceMachine Learning
AI summaryⓘ
The authors study how multiple agents can cooperatively make decisions online to maximize certain kinds of rewards that show diminishing returns, without relying on a central coordinator. They propose a method called Decentralized Barrier Follow-the-Regularized-Leader (Dec-BFTRL), where each agent updates its choice based on local information and limited communication with neighbors. Their approach ensures that over time, the agents collectively make decisions that perform nearly as well as the best fixed choice in hindsight. They also demonstrate how this method applies to different continuous optimization problems with diminishing returns.
decentralized optimizationonline optimizationdiminishing returnssubmodular maximizationregret analysisgauge projectiongradient methodsHybridNewtonseparation oracle
Authors
Yiyang Lu, Mohammad Pedramfar, Vaneet Aggarwal
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 four wrapper instantiations covering three DR-submodular maximization problems.