Hierarchies of Relaxations for Online Prediction Problems with Evolving Constraints
This work addresses computational challenges in online learning for combinatorial prediction problems, offering a trade-off between computation time and regret bounds, though it is incremental in nature.
The paper tackles online prediction problems with evolving combinatorial constraints, where the optimal benchmark predictor is computationally hard to compute, and provides polynomial-time prediction algorithms that achieve low regret against these benchmarks by combining random playout and Lasserre semidefinite hierarchies.
We study online prediction where regret of the algorithm is measured against a benchmark defined via evolving constraints. This framework captures online prediction on graphs, as well as other prediction problems with combinatorial structure. A key aspect here is that finding the optimal benchmark predictor (even in hindsight, given all the data) might be computationally hard due to the combinatorial nature of the constraints. Despite this, we provide polynomial-time \emph{prediction} algorithms that achieve low regret against combinatorial benchmark sets. We do so by building improper learning algorithms based on two ideas that work together. The first is to alleviate part of the computational burden through random playout, and the second is to employ Lasserre semidefinite hierarchies to approximate the resulting integer program. Interestingly, for our prediction algorithms, we only need to compute the values of the semidefinite programs and not the rounded solutions. However, the integrality gap for Lasserre hierarchy \emph{does} enter the generic regret bound in terms of Rademacher complexity of the benchmark set. This establishes a trade-off between the computation time and the regret bound of the algorithm.