Optimistic Safety for Online Convex Optimization with Unknown Linear Constraints
<|reference_start|>Optimistic Safety for Online Convex Optimization with Unknown Linear 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{\mathcal{O}}(\sqrt{T})$ regret and no constraint violation. In the case of static linear constraints, this improves on the previous best known $\tilde{\mathcal{O}}(T^{2/3})$ regret with only slightly stronger assumptions. In the case of stochastic time-varying constraints, our work supplements existing results that show $\mathcal{O}(\sqrt{T})$ regret and $\mathcal{O}(\sqrt{T})$ cumulative violation under more general convex constraints albeit a less general feedback model. In addition to our theoretical guarantees, we also give numerical results comparing the performance of OSOCO to existing algorithms.<|reference_end|>
@article{hutchinson2024optimistic,
    title={Optimistic Safety for Online Convex Optimization with Unknown Linear
  Constraints},
    author={Spencer Hutchinson, Tianyi Chen, Mahnoosh Alizadeh},
    journal={arXiv preprint arXiv:2403.05786},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.05786},
    primaryClass={cs.LG math.OC}
}