An Online Convex Optimization Approach to Dynamic Network Resource Allocation

Tianyi Chen, Qing Ling, Georgios B. Giannakis

Abstract

Existing approaches to online convex optimization (OCO) make sequential one-slot-ahead decisions, which lead to (possibly adversarial) losses that drive subsequent decision iterates. Their performance is evaluated by the so-called regret that measures the difference of losses between the online solution and the best yet fixed overall solution in hindsight. The present paper deals with online convex optimization involving adversarial loss functions and adversarial constraints, where the constraints are revealed after making decisions, and can be tolerable to instantaneous violations but must be satisfied in the long term. Performance of an online algorithm in this setting is assessed by: i) the difference of its losses relative to the best dynamic solution with one-slot-ahead information of the loss function and the constraint (that is here termed dynamic regret); and, ii) the accumulated amount of constraint violations (that is here termed dynamic fit). In this context, a modified online saddle-point (MOSP) scheme is developed, and proved to simultaneously yield sub-linear dynamic regret and fit, provided that the accumulated variations of per-slot minimizers and constraints are sub-linearly growing with time. MOSP is also applied to the dynamic network resource allocation task, and it is compared with the well-known stochastic dual gradient method. Under various scenarios, numerical experiments demonstrate the performance gain of MOSP relative to the state-of-the-art.

Introduction

In rapidly evolving environments like cloud computing networks, resource allocation decisions must be made sequentially under uncertainty. Traditional Online Convex Optimization (OCO) frameworks typically evaluate performance using "static regret"—the difference between the algorithm's cumulative loss and that of the best single fixed decision in hindsight. However, in non-stationary settings where workloads and costs shift unpredictably, a static benchmark is often insufficient. This paper proposes a framework that competes against a dynamic benchmark (the best sequence of decisions) while managing adversarial, time-varying constraints.

Problem Context and Novelty

Most existing OCO literature assumes constraints are fixed and known a priori. In reality, constraints like power budgets or bandwidth availability are often revealed only after a decision is made and can change over time. The authors address this by requiring constraints to be satisfied in the long term, allowing for occasional instantaneous violations.

Comparison of the proposed approach with existing literature across benchmark types and constraint handling.

As shown in the table above, this work is unique in its ability to handle dynamic benchmarks alongside both long-term and adversarial constraints, a combination not fully addressed by prior research.

The Modified Online Saddle-Point (MOSP) Algorithm

To solve this problem, the authors introduce the Modified Online Saddle-Point (MOSP) algorithm. MOSP is a primal-dual scheme with a critical modification: the primal update incorporates the exact constraint function from the previous time step as a penalty, rather than a linear approximation. This allows the algorithm to better track the feasible region as it evolves.

The MOSP algorithm iterates through primal and dual updates to minimize regret and constraint violations.

The dual update acts as a "virtual queue," tracking accumulated constraint violations to ensure long-term feasibility. Crucially, MOSP is fully predictive, making decisions for time $t$ using only information available up to $t-1$.

Experimental Evaluation

The algorithm was tested on a synthetic cloud network resource allocation task involving 10 mapping nodes and 10 data centers. Two primary scenarios were evaluated:

  1. Stationary Case: Costs and workloads follow i.i.d. distributions.
  2. Non-Stationary Case: Costs and workloads are driven by sinusoidal processes to simulate "bursty" or trending traffic.

MOSP was compared against the Online Dual Gradient (ODG) method, a causal adaptation of the widely used Lyapunov optimization framework.

Key Results and Insights

  • Theoretical Performance: The authors proved that MOSP achieves $O(T^{2/3})$ dynamic regret and dynamic fit. If the degree of environmental variation is known, this can be improved to $O(T^{1/2})$.
  • Dynamic Regret vs. Fit: "Dynamic Fit" measures cumulative constraint violations. MOSP demonstrated superior stability in maintaining low fit compared to ODG, especially in non-stationary environments.
  • Cost Efficiency: In non-stationary simulations, MOSP actually outperformed the per-slot optimum on average. By leveraging the flexibility of long-term constraints, it can "over-serve" during low-cost periods to compensate for high-cost periods.

Conclusion and Future Work

MOSP provides a robust framework for dynamic network resource allocation under adversarial conditions. While highly effective, its performance is bounded by the "variation budget" of the environment—if changes are too extreme, sub-linear regret is unattainable. Future research directions include improving step-size tuning and reducing communication overhead for large-scale decentralized implementations.

Summary updated

Abstract

Existing approaches to online convex optimization (OCO) make sequential one-slot-ahead decisions, which lead to (possibly adversarial) losses that drive subsequent decision iterates. Their performance is evaluated by the so-called regret that measures the difference of losses between the online solution and the best yet fixed overall solution in hindsight. The present paper deals with online convex optimization involving adversarial loss functions and adversarial constraints, where the constraints are revealed after making decisions, and can be tolerable to instantaneous violations but must be satisfied in the long term. Performance of an online algorithm in this setting is assessed by: i) the difference of its losses relative to the best dynamic solution with one-slot-ahead information of the loss function and the constraint (that is here termed dynamic regret); and, ii) the accumulated amount of constraint violations (that is here termed dynamic fit). In this context, a modified online saddle-point (MOSP) scheme is developed, and proved to simultaneously yield sub-linear dynamic regret and fit, provided that the accumulated variations of per-slot minimizers and constraints are sub-linearly growing with time. MOSP is also applied to the dynamic network resource allocation task, and it is compared with the well-known stochastic dual gradient method. Under various scenarios, numerical experiments demonstrate the performance gain of MOSP relative to the state-of-the-art.
BibTeX
@article{chen2017online,
  author = {Tianyi Chen and Qing Ling and Georgios B. Giannakis},
  title = {{An Online Convex Optimization Approach to Dynamic Network Resource Allocation}},
  journal = {IEEE Trans. Signal Process.},
  year = {2017},
  url = {https://openreview.net/forum?id=38pM_mEY2gg},
}
Figure