Back to Search
Start Over
Simultaneously Achieving Sublinear Regret and Constraint Violations for Online Convex Optimization with Time-varying Constraints
- Source :
- Proceedings of the 39th International Symposium on Computer Performance, Modeling, Measurements and Evaluation (Performance), 2021
- Publication Year :
- 2021
-
Abstract
- In this paper, we develop a novel virtual-queue-based online algorithm for online convex optimization (OCO) problems with long-term and time-varying constraints and conduct a performance analysis with respect to the dynamic regret and constraint violations. We design a new update rule of dual variables and a new way of incorporating time-varying constraint functions into the dual variables. To the best of our knowledge, our algorithm is the first parameter-free algorithm to simultaneously achieve sublinear dynamic regret and constraint violations. Our proposed algorithm also outperforms the state-of-the-art results in many aspects, e.g., our algorithm does not require the Slater condition. Meanwhile, for a group of practical and widely-studied constrained OCO problems in which the variation of consecutive constraints is smooth enough across time, our algorithm achieves $O(1)$ constraint violations. Furthermore, we extend our algorithm and analysis to the case when the time horizon $T$ is unknown. Finally, numerical experiments are conducted to validate the theoretical guarantees of our algorithm, and some applications of our proposed framework will be outlined.<br />Comment: 31 pages, it has been accepted at Performance 2021
- Subjects :
- Mathematics - Optimization and Control
Computer Science - Machine Learning
Subjects
Details
- Database :
- arXiv
- Journal :
- Proceedings of the 39th International Symposium on Computer Performance, Modeling, Measurements and Evaluation (Performance), 2021
- Publication Type :
- Report
- Accession number :
- edsarx.2111.07707
- Document Type :
- Working Paper