An Online Convex Optimization Approach to Proactive Network Resource Allocation

Tianyi Chen, Qing Ling, Georgios B. Giannakis

Research output: Contribution to journalArticle

25 Scopus citations

Abstract

Existing approaches to online convex optimization 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 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 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 sublinear dynamic regret and fit, provided that the accumulated variations of per-slot minimizers and constraints are sublinearly 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. Numerical experiments demonstrate the performance gain of MOSP relative to the state of the art.

Original languageEnglish (US)
Article number8027140
Pages (from-to)6350-6364
Number of pages15
JournalIEEE Transactions on Signal Processing
Volume65
Issue number24
DOIs
StatePublished - Dec 15 2017

    Fingerprint

Keywords

  • Constrained optimization
  • network resource allocation
  • online convex optimization
  • primal-dual method

Cite this