On Local Regret
This work addresses online decision-making problems for hypothesis classes where offline optimization is hard, offering a novel approach to improve learning efficiency in such scenarios.
The paper tackles the challenge of online learning when finding the best hypothesis offline is difficult by introducing local regret, which aims to perform nearly as well as nearby hypotheses, and presents a general algorithm to minimize it with arbitrary locality graphs, demonstrating speed improvements on problems like online disjunct learning, online Max-SAT, and online decision tree learning.
Online learning aims to perform nearly as well as the best hypothesis in hindsight. For some hypothesis classes, though, even finding the best hypothesis offline is challenging. In such offline cases, local search techniques are often employed and only local optimality guaranteed. For online decision-making with such hypothesis classes, we introduce local regret, a generalization of regret that aims to perform nearly as well as only nearby hypotheses. We then present a general algorithm to minimize local regret with arbitrary locality graphs. We also show how the graph structure can be exploited to drastically speed learning. These algorithms are then demonstrated on a diverse set of online problems: online disjunct learning, online Max-SAT, and online decision tree learning.