提出去中心化无投影优化新框架，首次实现带一般凸约束的上凹函数优化。
Decentralized Projection-free Online Upper-Linearizable Optimization with Applications to DR-Submodular Optimization
- 采用去中心化机制与上线性可逼近函数框架结合，避免投影操作。
- 在任意参数θ下，达到最优后悔率O(T^{1-θ/2})与通信复杂度O(T^θ)。
- 适用于一阶、零阶、半多臂及多臂反馈，拓展了非单调上凹优化场景。
我们提出一种新的去中心化无投影优化框架，将无投影方法推广至更广泛的上线性可逼近函数类。该方法结合去中心化优化技术与上线性可逼近函数框架，有效扩展了传统DR-子模函数优化的适用范围。对于任意0≤θ≤1，该方法在去中心化上线性可逼近函数优化中实现了后悔率O(T^{1-θ/2})，通信复杂度O(T^θ)，以及线性优化查询次数O(T^{2θ})。该方法首次实现了单调上凹优化与一般凸约束下的结果，以及非单调上凹优化在一般凸约束下的结果。进一步，上述一阶反馈结果被拓展至零阶、半多臂及多臂反馈场景。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。