# Online Optimization for Randomized Network Resource Allocation with Long-Term Constraints

arXiv: https://arxiv.org/abs/2305.15558 · HTML: https://mlsanity.com/paper/2305.15558/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 28 references that are in the map.
- First posted on arXiv 24 May 2023.

## Builds on (most cited first, 5 of 5)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach](https://mlsanity.com/paper/1901.08511/) (2019)
- [Online Convex Optimization with Time-Varying Constraints](https://mlsanity.com/paper/1702.04783/) (2017)
- [An Online Convex Optimization Approach to Dynamic Network Resource Allocation](https://mlsanity.com/paper/1701.03974/) (2017)
- [Regrets of Proximal Method of Multipliers for Online Non-convex Optimization with Long Term Constraints](https://mlsanity.com/paper/2204.10986/) (2022)

## Built on by (most cited first, 1 of 1)

- [Online Optimization for Network Resource Allocation and Comparison with Reinforcement Learning Techniques](https://mlsanity.com/paper/2311.10023/) (2023)

## Abstract (arXiv)

In this paper, we study an optimal online resource reservation problem in a simple communication network. The network is composed of two compute nodes linked by a local communication link. The system operates in discrete time; at each time slot, the administrator reserves resources for servers before the actual job requests are known. A cost is incurred for the reservations made. Then, after the client requests are observed, jobs may be transferred from one server to the other to best accommodate the demands by incurring an additional transport cost. If certain job requests cannot be satisfied, there is a violation that engenders a cost to pay for each of the blocked jobs. The goal is to minimize the overall reservation cost over finite horizons while maintaining the cumulative violation and transport costs under a certain budget limit. To study this problem, we first formalize it as a repeated game against nature where the reservations are drawn randomly according to a sequence of probability distributions that are derived from an online optimization problem over the space of allowable reservations. We then propose an online saddle-point algorithm for which we present an upper bound for the associated K-benchmark regret together with an upper bound for the cumulative constraint violations. Finally, we present numerical experiments where we compare the performance of our algorithm with those of simple deterministic resource allocation policies.