Optimistic Safety for Online Convex Optimization with Unknown Linear Constraints
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909689089884160 |
|---|---|
| author | Hutchinson, Spencer Chen, Tianyi Alizadeh, Mahnoosh |
| author_facet | Hutchinson, Spencer Chen, Tianyi Alizadeh, Mahnoosh |
| contents | We study the problem of online convex optimization (OCO) under unknown linear constraints that are either static, or stochastically time-varying. For this problem, we introduce an algorithm that we term Optimistically Safe OCO (OSOCO) and show that it enjoys $\tilde{O}(\sqrt{T})$ regret and no constraint violation. In the case of static linear constraints, this improves on the previous best known $\tilde{O}(T^{2/3})$ regret under the same assumptions. In the case of stochastic time-varying constraints, our work supplements existing results that show $O(\sqrt{T})$ regret and $O(\sqrt{T})$ cumulative violation under more general convex constraints and a different set of assumptions. In addition to our theoretical guarantees, we also give numerical results that further validate the effectiveness of our approach. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_05786 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Optimistic Safety for Online Convex Optimization with Unknown Linear Constraints Hutchinson, Spencer Chen, Tianyi Alizadeh, Mahnoosh Machine Learning Optimization and Control We study the problem of online convex optimization (OCO) under unknown linear constraints that are either static, or stochastically time-varying. For this problem, we introduce an algorithm that we term Optimistically Safe OCO (OSOCO) and show that it enjoys $\tilde{O}(\sqrt{T})$ regret and no constraint violation. In the case of static linear constraints, this improves on the previous best known $\tilde{O}(T^{2/3})$ regret under the same assumptions. In the case of stochastic time-varying constraints, our work supplements existing results that show $O(\sqrt{T})$ regret and $O(\sqrt{T})$ cumulative violation under more general convex constraints and a different set of assumptions. In addition to our theoretical guarantees, we also give numerical results that further validate the effectiveness of our approach. |
| title | Optimistic Safety for Online Convex Optimization with Unknown Linear Constraints |
| topic | Machine Learning Optimization and Control |
| url | https://arxiv.org/abs/2403.05786 |