Smoothed Online Decision Making in Communication: Algorithms and Applications

Evolution of the 5G network introduces much higher QoS standards and energy saving objectives, which requires a more refined and smoothed online control method in many scenarios. To address this challenge, we study the online decision problem with switching costs where the agent incurs both a convex hitting cost and an additional switching cost of changing decisions, i.e., Smoothed Online Convex Optimization (SOCO). While there have been a wide variety of online algorithms designed, their theoretical performance relies on certain assumptions about loss functions, e.g., linearity and smoothness, predictability, or prior knowledge of regularity measures of environment. This paper addresses this limitation by developing a universal algorithm IOMD-SOCO that applies to general convex loss functions without predictions. We show that IOMD-SOCO achieves an order-optimal, universal dynamic regret bound. We also propose its parameter-free versions, i.e., without requiring the prior knowledge of path length of the comparator sequence, and achieve the same-order regret bound. We are the first to provide dynamic regret bounds for SOCO with general convex loss functions via parameter-free algorithms. Our numerical experiments show that IOMD-SOCO indeed achieves a substantial performance improvement. We also discuss potential applications of SOCO in communication networks.