Online convex optimization for dynamic network resource allocation

Tianyi Chen, Qing Lingy, Georgios B Giannakis

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

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 applied to the dynamic network resource allocation task, and shown to outperform the well-known stochastic dual gradient method.

Original languageEnglish (US)
Title of host publication25th European Signal Processing Conference, EUSIPCO 2017
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages136-140
Number of pages5
ISBN (Electronic)9780992862671
DOIs
StatePublished - Oct 23 2017
Event25th European Signal Processing Conference, EUSIPCO 2017 - Kos, Greece
Duration: Aug 28 2017Sep 2 2017

Publication series

Name25th European Signal Processing Conference, EUSIPCO 2017
Volume2017-January

Other

Other25th European Signal Processing Conference, EUSIPCO 2017
CountryGreece
CityKos
Period8/28/179/2/17

Bibliographical note

Funding Information:
Work in this paper was supported by NSF 1509040, 1508993, 1509005, NSF China 61573331, NSF Anhui 1608085QF130, and CAS-XDA06040602.

Keywords

  • Network Resource Allocation
  • Nonstationary Optimization
  • Online Learning
  • Online convex optimization

Fingerprint Dive into the research topics of 'Online convex optimization for dynamic network resource allocation'. Together they form a unique fingerprint.

Cite this