Abstract
We consider the general problem of online convex optimization with time-varying budget constraints in the presence of predictions for the next cost and constraint functions, that arises in a plethora of network resource management problems. A novel saddle-point algorithm is designed by combining a Follow-The-Regularized-Leader iteration with prediction-adaptive dynamic steps. The algorithm achieves O(T(3β/4) regret and O(T(1+β)/2) constraint violation bounds that are tunable via parameter β ∈ [1/2,1) and have constant factors that shrink with the predictions quality, achieving eventually O(1) regret for perfect predictions. Our work extends the seminal FTRL framework for this new OCO setting and outperforms the respective state-of-the-art greedy-based solutions which naturally cannot benefit from predictions, without imposing conditions on the (unknown) quality of predictions, the cost functions or the geometry of constraints, beyond convexity.
Original language | English |
---|---|
Pages (from-to) | 1935 - 1949 |
Number of pages | 15 |
Journal | IEEE/ACM Transactions on Networking |
Volume | 31 |
Issue number | 5 |
DOIs | |
Publication status | Published - 2023 |
Bibliographical note
Green Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project https://www.openaccess.nl/en/you-share-we-take-careOtherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.
Keywords
- Network control
- network management
- online convex optimization (OCO)
- online learning
- resource allocation