Revisiting Smoothed Online Learning

Abstract

In this paper, we revisit the problem of smoothed online learning, in which the online learner suffers both a hitting cost and a switching cost, and target two performance metrics: competitive ratio and dynamic regret with switching cost. To bound the competitive ratio, we assume the hitting cost is known to the learner in each round, and investigate the simple idea of balancing the two costs by an optimization problem. Surprisingly, we find that minimizing the hitting cost alone is $\max (1,\frac{2}{\alpha })$-competitive for $\alpha$-polyhedral functions and $1+\frac{4}{\lambda }$-competitive for $\lambda$-quadratic growth functions, both of which improve state-of-the-art results significantly. Moreover, when the hitting cost is both convex and $\lambda$-quadratic growth, we reduce the competitive ratio to $1+\frac{2}{\sqrt{\lambda }}$ by minimizing the weighted sum of the hitting cost and the switching cost. To bound the dynamic regret with switching cost, we follow the standard setting of online convex optimization, in which the hitting cost is convex but hidden from the learner before making predictions. We modify Ader, an existing algorithm designed for dynamic regret, slightly to take into account the switching cost when measuring the performance. The proposed algorithm, named as Smoothed Ader, attains an optimal $O(\sqrt{T(1+P_T)})$ bound for dynamic regret with switching cost, where $P_T$ is the path-length of the comparator sequence. Furthermore, if the hitting cost is accessible in the beginning of each round, we obtain a similar guarantee without the bounded gradient condition, and establish an $\Omega (\sqrt{T(1+P_T)})$ lower bound to confirm the optimality.

References in corpus (8)

• Adaptive Online Learning in Dynamic Environments
• Improved Dynamic Regret for Non-degenerate Functions
• Online Learning with Switching Costs and Other Adaptive Adversaries
• Beyond Online Balanced Descent: An Optimal Algorithm for Smoothed Online Optimization
• Minimax Regret of Switching-Constrained Online Convex Optimization: No Phase Transition
• Multi-Armed Bandits with Metric Movement Costs
• Leveraging Predictions in Smoothed Online Convex Optimization via Gradient-based Algorithms
• Dimension-Free Bounds on Chasing Convex Functions

Cited by in corpus (2)

• Expert-Calibrated Learning for Online Optimization with Switching Costs
• Online Convex Optimization with Switching Cost and Delayed Gradients