2024/03/09 by Spencer Hutchinson, Tianyi Chen, Hutchinson, Spencer +3
Computer Science · Engineering · #Advanced Wireless Network Optimization #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC) #Optimization and Search Problems #Smart Parking Systems Research
paper · pdf · doi:10.48550/arxiv.2403.05786
openalex publication_date 2024/03/09 · openalex created_date 2024/03/13 · openalex updated_date 2026/07/28
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 O(√(T)) regret and no constraint violation. In the case of static linear constraints, this improves on the previous best known O(T2/3) regret under the same assumptions. In the case of stochastic time-varying constraints, our work supplements existing results that show O(√(T)) regret and O(√(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.