Decentralized Projection-free Online Upper-Linearizable Optimization with Applications to DR-Submodular Optimization
This provides a novel framework for decentralized optimization with applications to DR-submodular functions, addressing a specific bottleneck in projection-free methods.
The paper tackles decentralized projection-free optimization for upper-linearizable functions, achieving a regret of O(T^{1-θ/2}) with communication complexity O(T^θ) and linear oracle calls O(T^{2θ}) for 0≤θ≤1, and extends results to various feedback types.
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.