Upper-Linearizability of Online Non-Monotone DR-Submodular Maximization over Down-Closed Convex Sets

We study online and offline maximization of nonnegative, non-monotone DR-submodular functions over compact convex down-closed sets $K\subseteq[0,1]^d$. A supplied feasible diagonal point $ζ{\bf 1}\in K$ gives an upper-linearizable comparison with coefficient $\underlineα(ζ)=\tfrac12-(1-2ζ)_+^2/[2(3-2ζ)^2]$. This gives $4/9$ at $ζ=0$ and $O(\sqrt T)$ expected online approximate regret with one gradient query and one projection per round, including stochastic gradients. The same coefficient admits $O(T^{3/4})$ regret with one noisy value query, or $O(\sqrt T)$ with two exact value queries. All objective queries lie in the cube. Our analytical offline upper bound at $ζ=0$ improves the bound $2(e^{-1/2}-e^{-1})$ established in 2011, even with exact values and full gradients. Two constructions extend it to positive diagonal levels; one has a finite representation below $1/8$ and a piecewise rational formula above it. Online-to-batch conversion gives offline approximation and sample complexity, while a constant-objective reduction transfers the upper bound to online optimization. Both general-class coefficients equal $1/2$ for $ζ\ge1/2$, and their deficits below this level have quadratic order. Analytic polynomial comparisons give coefficient $1/2$ for quadratics and $\max\{8/17,2\sqrt{3-4r}/(1+\sqrt{3-4r})^2\}$ for cubics, where $r=\min\{ζ,1/2\}$, with online and offline query implementations. Finally, for discrete submodular maximization, multilinear extension and established rounding give $\underlineα(ζ)-\varepsilon$ under one matroid constraint and $4/9-\varepsilon$ under a fixed number of knapsack constraints.

We introduce a novel framework for decentralized projection-free optimization, extending projection-free methods to a broader class of upper-linearizable functions. Our approach leverages decentralized optimization techniques with the flexibility of upper-linearizable function frameworks, effectively generalizing traditional DR-submodular function optimization. We obtain the regret of $O(T^{1-θ/2})$ with communication complexity of $O(T^θ)$ and number of linear optimization oracle calls of $O(T^{2θ})$ for decentralized upper-linearizable function optimization, for any $0\le θ\le 1$. This approach allows for the first results for monotone up-concave optimization with general convex constraints and non-monotone up-concave optimization with general convex constraints. Further, the above results for first order feedback are extended to zeroth order, semi-bandit, and bandit feedback.

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.