J. Audibert, S. Bubeck, and G. Lugosi, Minimax policies for combinatorial prediction games, Proceedings of the 24th Annual Conference on Learning Theory (COLT 2011), pp.107-132, 2011.
URL : https://hal.archives-ouvertes.fr/hal-00624463

J. Audibert, S. Bubeck, and G. Lugosi, Regret in Online Combinatorial Optimization, Mathematics of Operations Research, vol.39, issue.1, pp.31-45, 2014.
DOI : 10.1287/moor.2013.0598
URL : http://arxiv.org/pdf/1204.4710

M. A. Bashiri and X. Zhang, Decomposition-invariant conditional gradient for general polytopes with line search, Advances in Neural Information Processing Systems 30, pp.2687-2697, 2017.

A. Beck and M. Teboulle, Mirror descent and nonlinear projected subgradient methods for convex optimization, Operations Research Letters, vol.31, issue.3, pp.167-175, 2003.
DOI : 10.1016/S0167-6377(02)00231-6

A. Biere, M. Heule, H. Van-maaren, and T. Walsh, , 2009.

N. Cesa-bianchi and G. Lugosi, Prediction, Learning, and Games, 2006.

N. Cesa-bianchi and G. Lugosi, Combinatorial bandits, Journal of Computer and System Sciences, vol.78, issue.5, pp.1404-1422, 2012.
DOI : 10.1016/j.jcss.2012.01.001

N. Creignou, S. Khanna, and M. Sudan, Complexity Classification of Boolean Constraint Satisfaction Problems, SIAM Monographs on Discrete Mathematics and Applications, 2001.
DOI : 10.1137/1.9780898718546

A. Darwiche, Decomposable negation normal form, Journal of the ACM, vol.48, issue.4, pp.608-647, 2001.
DOI : 10.1145/502090.502091

A. Darwiche, A compiler for deterministic, decomposable negation normal form, Proceedings of the 18th National Conference on Artificial Intelligence, pp.627-634, 2002.

A. Darwiche and P. Marquis, A Knowledge Compilation Map, Journal of Artificial Intelligence Research, vol.17, pp.229-264, 2002.
DOI : 10.1613/jair.989

M. E. Dyer, L. A. Goldberg, and M. Jerrum, The Complexity of Weighted Boolean #CSP, SIAM Journal on Computing, vol.38, issue.5, pp.1970-1986, 2009.
DOI : 10.1137/070690201

A. L. Friesen and P. M. Domingos, The sum-product theorem : A foundation for learning tractable models, Proceedings of the 33nd International Conference on Machine Learning, pp.1909-1918, 2016.

D. Garber and O. Meshi, Linear-memory and decomposition-invariant linearly convergent conditional gradient algorithm for structured polytopes, Advances in Neural Information Processing Systems 29NIPS 2016), pp.1001-1009, 2016.

J. Hannan, Approximation to Bayes risk in repeated play, Contributions to the Theory of Games, pp.97-139, 1957.

E. Hazan, Introduction to online convex optimization . Foundations and Trends in Optimization, pp.157-325, 2016.

D. P. Helmbold and M. K. Warmuth, Learning Permutations with Exponential Weights, Journal of Machine Learning Research, vol.10, pp.1705-1736, 2009.
DOI : 10.1007/978-3-540-72927-3_34

M. Hutter and J. Poland, Adaptive online prediction by following the perturbed leader, Journal of Machine Learning Research, vol.6, pp.639-660, 2005.

A. T. Kalai and S. Vempala, Efficient algorithms for online decision problems, Journal of Computer and System Sciences, vol.71, issue.3, pp.291-307, 2005.
DOI : 10.1016/j.jcss.2004.10.016

W. M. Koolen, M. K. Warmuth, and J. Kivinen, Hedging structured concepts, Proceedings of the 23rd Conference on Learning Theory, pp.93-105, 2010.

W. Krichene, S. Krichene, and A. M. Bayen, Efficient Bregman projections onto the simplex, 2015 54th IEEE Conference on Decision and Control (CDC), pp.3291-3298, 2015.
DOI : 10.1109/CDC.2015.7402714

S. Lacoste-julien and M. Jaggi, On the global linear convergence of frank-wolfe optimization variants, Advances in Neural Information Processing Systems 28 (NIPS 2015), pp.496-504, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01248675

J. Lagniez and P. Marquis, An Improved Decision-DNNF Compiler, Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, pp.667-673, 2017.
DOI : 10.24963/ijcai.2017/93

Y. T. Lee, A. Sidford, and S. C. Wong, A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization, 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pp.1049-1065, 2015.
DOI : 10.1109/FOCS.2015.68
URL : http://arxiv.org/pdf/1508.04874

M. Mohri, General algebraic frameworks and algorithms for shortest-distance problems, 1998.

A. Nemirovski and D. B. Yudin, Problem Complexity and Method Efficiency in Optimization, J. Wiley and Sons, 1983.

G. Neu and G. Bartók, Importance weighting without importance weights : An efficient algorithm for combinatorial semi-bandits, Journal of Machine Learning Research, vol.17154, pp.1-154, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01380278

H. Poon and P. M. Domingos, Sum-product networks: A new deep architecture, 2011 IEEE International Conference on Computer Vision Workshops (ICCV Workshops), pp.337-346, 2011.
DOI : 10.1109/ICCVW.2011.6130310
URL : http://turing.cs.washington.edu/papers/uai11-poon.pdf

H. Rahmanian and M. K. Warmuth, Online dynamic programming, Advances in Neural Information Processing Systems 30, pp.2824-2834, 2017.

A. Rajkumar and S. Agarwal, Online decision-making in general combinatorial spaces, Advances in Neural Information Processing Systems 27, pp.3482-3490, 2014.

H. Robbins, S. Monro, S. Sakaue, M. Ishihata, and S. Minato, A Stochastic Approximation Method, Proceedings of the 21st International Conference on Artificial Intelligence and Statistics, pp.400-407, 1951.
DOI : 10.1214/aoms/1177729586

D. Suehiro, K. Hatano, S. Kijima, E. Takimoto, and K. Nagano, Online Prediction under Submodular Constraints, Proceedings of the 23rd International Conference on Algorithmic Learning Theory, pp.260-274, 2012.
DOI : 10.1007/978-3-642-34106-9_22

E. Takimoto and K. Hatano, Efficient Algorithms for Combinatorial Online Prediction, Proceedings of the-24th International Conference on Algorithmic Learning Theory, pp.22-32, 2013.
DOI : 10.1007/978-3-642-40935-6_3

E. Takimoto and M. K. Warmuth, Path Kernels and Multiplicative Updates, Journal of Machine Learning Research, vol.4, pp.773-818, 2003.
DOI : 10.1007/3-540-45435-7_6
URL : http://www.cse.ucsc.edu/~manfred/pubs/J55.pdf