Robust Online Learning for Resource Allocation -- Beyond Euclidean Projection and Dynamic Fit
This work addresses the issue of constraint violations in online resource allocation for applications like network management, offering an incremental improvement by refining performance metrics and algorithms.
The paper tackles the problem of cumulative constraint violations in online learning for resource allocation by introducing a new performance measure, hCFit, and proposes non-causal algorithms that guarantee sub-linear growth of this measure in slowly changing environments with noisy feedback, demonstrating performance gains over state-of-the-art methods in numerical experiments.
Online-learning literature has focused on designing algorithms that ensure sub-linear growth of the cumulative long-term constraint violations. The drawback of this guarantee is that strictly feasible actions may cancel out constraint violations on other time slots. For this reason, we introduce a new performance measure called $\hCFit$, whose particular instance is the cumulative positive part of the constraint violations. We propose a class of non-causal algorithms for online-decision making, which guarantees, in slowly changing environments, sub-linear growth of this quantity despite noisy first-order feedback. Furthermore, we demonstrate by numerical experiments the performance gain of our method relative to the state of art.