nips nips2009 nips2009-45 nips2009-45-reference knowledge-graph by maker-knowledge-mining
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 bandit settings. 1
[1] A. D. Flaxman, A. T. Kalai, and H. B. McMahan, Online convex optimization in the bandit setting: gradient descent without a gradient, SODA, 2005, pp. 385–394.
[2] Satoru Fujishige, Submodular functions and optimization, Elsevier, 2005.
[3] M. Gr¨ tschel, L. Lov´ sz, and A. Schrijver, Geometric Algorithms and Combinatorial Optio a mization, Springer Verlag, 1988.
[4] Carlos Guestrin and Andreas Krause, Beyond convexity - submodularity in machine learning., Tutorial given in the 25rd International Conference on Machine Learning (ICML), 2008.
[5] J. 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 (1957), 97–139.
[6] Satoru Iwata, A faster scaling algorithm for minimizing submodular functions, SIAM J. Comput. 32 (2003), no. 4, 833–840.
[7] Satoru Iwata, Lisa Fleischer, and Satoru Fujishige, A combinatorial strongly polynomial algorithm for minimizing submodular functions, J. ACM 48 (2001), 761–777.
[8] Satoru Iwata and James B. Orlin, A simple combinatorial algorithm for submodular function minimization, SODA ’09: Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms (Philadelphia, PA, USA), Society for Industrial and Applied Mathematics, 2009, pp. 1230–1237.
[9] Adam Kalai and Santosh Vempala, Efficient algorithms for online decision problems, Journal of Computer and System Sciences 71(3) (2005), 291–307.
[10] N. Littlestone and M. K. Warmuth, The weighted majority algorithm, Proceedings of the 30th Annual Symposium on the Foundations of Computer Science, 1989, pp. 256–261.
[11] S. T. McCormick, Submodular function minimization., Chapter 7 in the Handbook on Discrete Optimization (G. Nemhauser K. Aardal and R. Weismantel, eds.), Elsevier, 2006, pp. 321–391.
[12] James B. Orlin, A faster strongly polynomial time algorithm for submodular function minimization, Math. Program. 118 (2009), no. 2, 237–251.
[13] Alexander Schrijver, A combinatorial algorithm minimizing submodular functions in strongly polynomial time, 1999.
[14] Matthew J. Streeter and Daniel Golovin, An online algorithm for maximizing submodular functions, NIPS, 2008, pp. 1577–1584.
[15] Martin Zinkevich, Online convex programming and generalized infinitesimal gradient ascent., Proceedings of the Twentieth International Conference (ICML), 2003, pp. 928–936. 9