Optimistic Safety for Online Convex Optimization with Unknown Linear Constraints
This work addresses safety and efficiency in online optimization for applications like resource allocation, though it is incremental as it builds on prior results for specific constraint types.
The paper tackles online convex optimization with unknown linear constraints, introducing the Optimistically Safe OCO (OSOCO) algorithm that achieves Õ(√T) regret and no constraint violation, improving on previous Õ(T^{2/3}) regret for static constraints.
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.