2020 IEEE International Symposium
on Information Theory
21-26 June 2020 • Los Angeles, California, USA
| Paper ID | D.1.6 | ||
| Paper Title | Coded Computing in Unknown Environment via Online Learning | ||
| Authors | Chien-Sheng Yang, University of Southern California, United States; Ramtin Pedarsani, University of California, Santa Barbara, United States; A. Salman Avestimehr, University of Southern California, United States | ||
| Session | D.1: Coded Computation | ||
| Presentation | Lecture | ||
| Track | Coded and Distributed Computation | ||
| Manuscript | Click here to download the manuscript | ||
| Virtual Presentation | Click here to watch in the Virtual Symposium | ||
| Abstract | Recently, there has been a significant increase in utilizing the cloud networks for event-driven and time-sensitive computations. However, large-scale distributed computing networks can suffer substantially from unpredictable and unreliable computing resources which can result in high variability of service quality. Thus, it is crucial to design efficient task scheduling policies that guarantee quality of service and the timeliness of computation queries. In this paper, we study the problem of computation offloading over unknown cloud networks with a sequence of timely computation jobs. We model the service quality (success probability of returning result back to the user within deadline) of each worker as function of context (collection of factors that affect workers). The user decides the computations to offload to each worker with the goal of receiving a recoverable set of computation results in the given deadline. Our goal is to design an efficient computing policy in the dark without the knowledge of the context or computation capabilities of each worker. By leveraging the coded computing framework in order to tackle failures or stragglers in computation, we formulate this problem using contextual-combinatorial multi-armed bandits (CC-MAB), and aim to maximize the cumulative expected reward. We propose an online learning policy called online coded computing policy, which provably achieves asymptotically-optimal performance in terms of regret loss compared with the optimal offline policy. | ||
Plan Ahead
2021 IEEE International Symposium on Information Theory
11-16 July 2021 | Melbourne, Victoria, Australia
