Revisiting Smoothed Online Learning
  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.
