Compiling Combinatorial Prediction Games

Frederic Koriche
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:2756-2765, 2018.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v80-koriche18a, title = {Compiling Combinatorial Prediction Games}, author = {Koriche, Frederic}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {2756--2765}, year = {2018}, editor = {Dy, Jennifer and Krause, Andreas}, volume = {80}, series = {Proceedings of Machine Learning Research}, month = {10--15 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v80/koriche18a/koriche18a.pdf}, url = {https://proceedings.mlr.press/v80/koriche18a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Compiling Combinatorial Prediction Games %A Frederic Koriche %B Proceedings of the 35th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jennifer Dy %E Andreas Krause %F pmlr-v80-koriche18a %I PMLR %P 2756--2765 %U https://proceedings.mlr.press/v80/koriche18a.html %V 80 %X 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.
APA
Koriche, F.. (2018). Compiling Combinatorial Prediction Games. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:2756-2765 Available from https://proceedings.mlr.press/v80/koriche18a.html.

Related Material