In online optimization, the goal is to iteratively choose solutions from a decision space, so as to minimize the average cost over time. As long as this decision space is described by combinatorial constraints, the problem is generally intractable. In this paper, we consider the paradigm of compiling the set of combinatorial constraints into a deterministic and Decomposable Negation Normal Form (dDNNF) circuit, for which the tasks of linear optimization and solution sampling take linear time. Based on this framework, we provide efficient characterizations of existing combinatorial prediction strategies, with a particular attention to mirror descent techniques. These strategies are compared on several real-world benchmarks for which the set of Boolean constraints is preliminarily compiled into a dDNNF circuit.
Frederic Koriche (CRIL UMR CNRS 8188, Univ. Artois)
Related Events (a corresponding poster, oral, or spotlight)
2018 Oral: Compiling Combinatorial Prediction Games »
Fri Jul 13th 09:40 -- 09:50 AM Room K11