In this paper, we revisit the problem of smoothed online learning, in which the online learner suffersboth ahitting costandaswitching cost, andtargettwoperformance metrics: competitiveratio anddynamic regretwith 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 optimizationproblem.

We provide online convex optimization algorithms that guarantee improved fullmatrix regret bounds. These algorithms extend prior work in several ways. First, we seamlessly allow for the incorporation of constraints without requiring unknown oracle-tuning for any learning rate parameters. Second, we improve the regret analysis of the full-matrix AdaGrad algorithm by suggesting a better learning rate value and showing how to tune the learning rate to this value on-the-fly. Third, all our bounds are obtained via a general framework for constructing regret bounds that depend on an arbitrary sequence of norms.

Algorithm 1:Oracle-Efficient Smoothed Online Learningfor Real-valued Functions Input: T, 1 K 100 logT / . 2 fort 1toT do 3 Receivext.