Decentralized Projection-free Online Upper-Linearizable Optimization with Applications to DR-Submodular Optimization

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.

We study adversarial online maximization of nonnegative, non-monotone DR-submodular functions over compact convex down-closed sets. A learner commits each action before observing its objective and competes with the best fixed action in hindsight. We prove a comparator-uniform first-order inequality that gives coefficient $4/9$, improving the online $0.401$ benchmark, with one gradient query and one projection per round and $O(\sqrt T)$ expected approximate regret. If $ζ{\bf 1} \in K\subseteq[0,1]^d$, the coefficient improves to $\underlineα(ζ)=\tfrac12-(1-2ζ)_+^2/[2(3-2ζ)^2]$. The proof is a direct ordered-coordinate argument with an objective-independent rational action. Conversely, a three-group symmetry-gap construction yields an offline oracle upper bound $β_*=0.470438681380894\ldots$ at $ζ=0$, even with exact value and full-gradient responses. A parameterized extension and exact finite-instance bounds define an upper function for every $ζ$. The lower and upper bounds match at $1/2$ for $ζ\ge1/2$, and show that the optimal deficit from $1/2$ is $Θ((1/2-ζ)^2)$ as $ζ\uparrow1/2$. For coefficient-revealed polynomials we obtain $1/2$ for quadratics and a geometry-dependent cubic coefficient starting at $8/17$, including $0.49$ at $ζ=1/5$. A constant objective sequence yields an offline $(4/9-\varepsilon)$ approximation with polynomially many first-order queries on the cube and projections, without requiring a supplied positive lower bound on the optimum. We also give nonanticipating adaptive-adversary and value-feedback guarantees, including $O(T^{3/4})$ regret with one noisy value per round.

Decentralized online convex optimization (D-OCO) is a popular framework for distributed applications with streaming data. To tackle the communication bottleneck, previous studies have investigated D-OCO with compressed communication and proposed several algorithms that are variants of online gradient descent (OGD). However, for D-OCO with exact communication, the best existing algorithms are variants of follow-the-regularized-leader (FTRL). In this paper, for the first time, we propose two FTRL-type algorithms for D-OCO with compressed communication. Compared with OGD-type algorithms, our algorithms are more elegant in both algorithmic design and theoretical analysis. The key insight is that the dual update mechanism of FTRL allows us to make a simple application of the technique for average consensus with communication compression. More specifically, our first algorithm considers the full-information setting, and can match the existing regret bounds. Our second algorithm is designed for the bandit setting, and can significantly improve both the regret bounds and communication costs of existing algorithms.