jmlr jmlr2012 jmlr2012-84 jmlr2012-84-reference knowledge-graph by maker-knowledge-mining

84 jmlr-2012-Online Submodular Minimization


Source: pdf

Author: Elad Hazan, Satyen Kale

Abstract: We consider an online decision problem over a discrete space in which the loss function is submodular. We give algorithms which are computationally efficient and are Hannan-consistent in both the full information and partial feedback settings. Keywords: submodular optimization, online learning, regret minimization


reference text

Nicol` Cesa-Bianchi and G´ bor Lugosi. Prediction, Learning, and Games. Cambridge University o a Press, 2006. Abraham D. Flaxman, Adam Tauman Kalai, and H. Brendan. McMahan. Online convex optimization in the bandit setting: gradient descent without a gradient. In SODA, pages 385–394, 2005. ISBN 0-89871-585-7. Satoru Fujishige. Submodular Functions and Optimization. Elsevier, 2005. Martin Gr¨ tschel, Laszlo Lov´ sz, and Alexander Schrijver. Geometric Algorithms and Combinatoo a rial Optimization. Springer Verlag, 1988. Carlos Guestrin and Andreas Krause. Beyond convexity - submodularity in machine learning. In Tutorial given in the 25rd International Conference on Machine Learning (ICML), 2008. James Hannan. Approximation to Bayes risk in repeated play. In M. Dresher, A. W. Tucker, and P. Wolfe, editors, Contributions to the Theory of Games, volume III, pages 97–139, 1957. Elad Hazan and Satyen Kale. Beyond convexity: Online submodular minimization. In TwentyFourth Annual Conference on. Neural Information Processing Systems (NIPS), pages 700–708, 2009. Satoru Iwata. A faster scaling algorithm for minimizing submodular functions. SIAM J. Comput., 32(4):833–840, 2003. Satoru Iwata and James B. Orlin. A simple combinatorial algorithm for submodular function minimization. In SODA ’09: Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, pages 1230–1237, Philadelphia, PA, USA, 2009. Society for Industrial and Applied Mathematics. Satoru Iwata, Lisa Fleischer, and Satoru Fujishige. A combinatorial strongly polynomial algorithm for minimizing submodular functions. J. ACM, 48:761–777, 2001. Stefanie Jegelka and Jeff Bilmes. Online submodular minimization for combinatorial structures. In Lise Getoor and Tobias Scheffer, editors, Proceedings of the 28th International Conference on Machine Learning (ICML-11), ICML ’11, pages 345–352, New York, NY, USA, June 2011. ACM. ISBN 978-1-4503-0619-5. Adam Kalai and Santosh Vempala. Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 71(3):291–307, 2005. 2921 H AZAN AND K ALE Andreas Krause and Carlos Guestrin. Submodularity and its applications in optimized information gathering. ACM Transactions on Intelligent Systems and Technology, 2(4), July 2011. Nick Littlestone and Manfred K. Warmuth. The weighted majority algorithm. In FOCS, pages 256–261. IEEE Computer Society, 1989. S. Thomas McCormick. Submodular function minimization. In Chapter 7 in the Handbook on Discrete Optimization, pages 321–391. Elsevier, 2006. James B. Orlin. A faster strongly polynomial time algorithm for submodular function minimization. Math. Program., 118(2):237–251, 2009. ISSN 0025-5610. doi: http://dx.doi.org/10.1007/s10107-007-0189-2. Alexander Schrijver. A combinatorial algorithm minimizing submodular functions in strongly polynomial time. Journal of Combinatorial Theory, Series B, 80(2):346–355, 2000. Matthew J. Streeter and Daniel Golovin. An online algorithm for maximizing submodular functions. In NIPS, pages 1577–1584, 2008. Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the Twentieth International Conference (ICML), pages 928–936, 2003. 2922