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.
翻译：我们提出了一种新颖的去中心化无投影优化框架，将无投影方法扩展至更广泛的上线性化函数类别。该方法结合了去中心化优化技术与上线性化函数框架的灵活性，有效推广了传统的DR-子模函数优化。对于任意0≤θ≤1，我们在去中心化上线性化函数优化中实现了$O(T^{1-θ/2})$的遗憾界，通信复杂度为$O(T^θ)$，线性优化预言机调用次数为$O(T^{2θ})$。该框架首次实现了具有一般凸约束的单调上凹优化及非单调上凹优化的理论结果。此外，上述一阶反馈结果可进一步扩展至零阶、半赌博机及赌博机反馈场景。
相关内容
微信扫码咨询专知VIP会员