A Model for Optimizing Recalculation Schedules to Minimize Regret

In this paper we analyze online problems from the perspective of when to switch solutions when the cost is of doing so is high – we call such a solution change a “recalculation.” We analyze this problem under the assumption we have algorithms that achieve per-round regret (which can be otherwise thought of as point-wise error, or other well-studied quantities) of the form \(O(1/t^\varepsilon )\) after seeing t data-points. We study schedules with a constant number and an increasing number of recalculations in the total number of datapoints, and we examine when achieving optimal cumulative regret is possible.