Decentralized Projection-free Online Upper-Linearizable Optimization with Applications to DR-Submodular Optimization
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917289529442304 |
|---|---|
| author | Lu, Yiyang Pedramfar, Mohammad Aggarwal, Vaneet |
| author_facet | Lu, Yiyang Pedramfar, Mohammad Aggarwal, Vaneet |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_18183 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Decentralized Projection-free Online Upper-Linearizable Optimization with Applications to DR-Submodular Optimization Lu, Yiyang Pedramfar, Mohammad Aggarwal, Vaneet Optimization and Control Computational Complexity Machine Learning 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. |
| title | Decentralized Projection-free Online Upper-Linearizable Optimization with Applications to DR-Submodular Optimization |
| topic | Optimization and Control Computational Complexity Machine Learning |
| url | https://arxiv.org/abs/2501.18183 |