An Online Convex Optimization Approach to Proactive Network Resource Allocation

DOI10.1109/TSP.2017.2750109MaRDI QIDQ4621962zbMATH OpenOpenAlexFDO

Authors Tianyi Chen, Qing Ling, Georgios B. Giannakis

Publication date 8 February 2019

Published in IEEE Transactions on Signal Processing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1701.03974

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Communication networks in operations research (90B18) Convex programming (90C25)

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.

Cited in

(22)

• Predictive online convex optimization
• Decentralized online convex optimization based on signs of relative states
• Event-triggered distributed online convex optimization with delayed bandit feedback
• scientific article; zbMATH DE number 6469194 (Why is no real title available?)
• Dynamic online convex optimization with long-term constraints via virtual queue
• Distributed online bandit linear regressions with differential privacy
• Online bandit convex optimisation with stochastic constraints via two-point feedback
• Decentralized online convex optimization with compressed communications
• No-regret learning for repeated non-cooperative games with lossy bandits
• DIMIX: Diminishing Mixing for Sloppy Agents
• Adversarial bandits with knapsacks
• Online composite optimization with time-varying regularizers
• Online convex optimization using coordinate descent algorithms
• Regret analysis of an online majorized semi-proximal ADMM for online composite optimization
• Online dynamic submodular optimization
• Distributed constrained online convex optimization with adaptive quantization
• A decentralised strongly adaptive subgradient online learning algorithm over time-varying networks
• Distributed online adaptive subgradient optimization with dynamic bound of learning rate over time-varying networks
• Augmented Lagrangian methods for time-varying constrained online convex optimization
• On the dual gradient descent method for the resource allocation problem in multiagent systems
• Combinatorial multi-armed bandits with fairness constraints: an online convex optimization perspective
• Distributed online path-length-independent algorithm for noncooperative games over unbalanced digraphs

This page was built for publication: An Online Convex Optimization Approach to Proactive Network Resource Allocation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4621962)