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

arXiv:2501.18183v3 Announce Type: replace-cross Abstract: 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-heta/2}) with communication complexity of O(T^{heta}) and number of linear optimization oracle calls of O(T^{2heta}) for decentralized upper-linearizable function optimization, for any 0le heta 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.

Source: arXiv cs.LG | 2026-10-01