An Online Learning Algorithm for Distributed Task Offloading in Multi-Access Edge Computing

TY - JOUR

T1 - An Online Learning Algorithm for Distributed Task Offloading in Multi-Access Edge Computing

AU - Sun, Zhenfeng

AU - Nakhai, Mohammad Reza

PY - 2020/4

Y1 - 2020/4

N2 - This paper addresses the problem of distributed task offloading centred at individual user terminals in a cellular multi-access edge computing (MEC) system. We introduce an online learning-assisted algorithm based on distributed bandit optimization (DBO) to cope with time-varying cost and time- varying constraint functions with unknown statistics on-the- go. The proposed algorithm jointly exploits the projected dual gradient iterations and a greedy method as well as a single broadcast communicating the MEC states to the users at the end of each decision cycle to minimize task computing-communication delay in the long run at user terminals. To track the performance of the proposed online learning algorithm over time, we define a dynamic regret to assess the closeness of the underlying delay cost of the DBO to a clairvoyant dynamic optimum, and an aggregate violation metric to evaluate the asymptotic satisfaction of the constraints. We derive lower and upper bounds for dynamic regret as well as an upper-bound for the aggregate violation and show that the upper-bounds are sub-linear under sub-linear accumulated hindsight variations. The simulation results and comparisons confirm the effectiveness of the proposed algorithm in the long run.

AB - This paper addresses the problem of distributed task offloading centred at individual user terminals in a cellular multi-access edge computing (MEC) system. We introduce an online learning-assisted algorithm based on distributed bandit optimization (DBO) to cope with time-varying cost and time- varying constraint functions with unknown statistics on-the- go. The proposed algorithm jointly exploits the projected dual gradient iterations and a greedy method as well as a single broadcast communicating the MEC states to the users at the end of each decision cycle to minimize task computing-communication delay in the long run at user terminals. To track the performance of the proposed online learning algorithm over time, we define a dynamic regret to assess the closeness of the underlying delay cost of the DBO to a clairvoyant dynamic optimum, and an aggregate violation metric to evaluate the asymptotic satisfaction of the constraints. We derive lower and upper bounds for dynamic regret as well as an upper-bound for the aggregate violation and show that the upper-bounds are sub-linear under sub-linear accumulated hindsight variations. The simulation results and comparisons confirm the effectiveness of the proposed algorithm in the long run.

KW - Aggregate violation

KW - dynamic regret

KW - multi-access edge computing,online learning

KW - projected dual gradient

UR - http://www.scopus.com/inward/record.url?scp=85086145641&partnerID=8YFLogxK

U2 - 10.1109/TSP.2020.2991383

DO - 10.1109/TSP.2020.2991383

M3 - Article

SN - 1053-587X

VL - 68

SP - 3090

EP - 3102

JO - IEEE Transactions on Signal Processing

JF - IEEE Transactions on Signal Processing

M1 - 9082169

ER -