nips nips2013 nips2013-268 nips2013-268-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Stefanie Jegelka, Francis Bach, Suvrit Sra
Abstract: Recently, it has become evident that submodularity naturally captures widely occurring concepts in machine learning, signal processing and computer vision. Consequently, there is need for efficient optimization procedures for submodular functions, especially for minimization problems. While general submodular minimization is challenging, we propose a new method that exploits existing decomposability of submodular functions. In contrast to previous approaches, our method is neither approximate, nor impractical, nor does it need any cumbersome parameter tuning. Moreover, it is easy to implement and parallelize. A key component of our method is a formulation of the discrete submodular minimization problem as a continuous best approximation problem that is solved through a sequence of reflections, and its solution can be easily thresholded to obtain an optimal discrete solution. This method solves both the continuous and discrete formulations of the problem, and therefore has applications in learning, inference, and reconstruction. In our experiments, we illustrate the benefits of our method on two image segmentation tasks. 1
[1] F. Bach. Learning with submodular functions: A convex optimization perspective. Arxiv preprint arXiv:1111.6453v2, 2013.
[2] A. Barbero and S. Sra. Fast Newton-type methods for total variation regularization. In ICML, 2011.
[3] H. H. Bauschke and P. L. Combettes. Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, 2011.
[4] H. H. Bauschke, P. L. Combettes, and D. R. Luke. Finding best approximation pairs relative to two closed convex sets in Hilbert spaces. J. Approx. Theory, 127(2):178–192, 2004.
[5] A. Beck and M. Teboulle. A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM Journal on Imaging Sciences, 2(1):183–202, 2009. 8
[6] D. P. Bertsekas. Nonlinear programming. Athena Scientific, 1999.
[7] Y. Boykov, O. Veksler, and R. Zabih. Fast approximate energy minimization via graph cuts. IEEE TPAMI, 23(11):1222–1239, 2001.
[8] B.Savchynskyy, S.Schmidt, J.H.Kappes, and C.Schn¨ rr. Efficient MRF energy minimization via adaptive o diminishing smoothing. In UAI, 2012.
[9] A. Chambolle. An algorithm for total variation minimization and applications. J Math. Imaging and Vision, 20(1):89–97, 2004.
[10] A. Chambolle and J. Darbon. On total variation minimization and surface evolution using parametric maximum flows. Int. Journal of Comp. Vision, 84(3):288–307, 2009.
[11] F. Chudak and K. Nagano. Efficient solutions to relaxations of combinatorial problems with submodular penalties via the Lov´ sz extension and non-smooth convex optimization. In SODA, 2007. a
[12] P. L. Combettes and J.-C. Pesquet. Proximal Splitting Methods in Signal Processing. In Fixed-Point Algorithms for Inverse Problems in Science and Engineering, pages 185–212. Springer, 2011.
[13] F. R. Deutsch. Best Approximation in Inner Product Spaces. Springer Verlag, first edition, 2001.
[14] J. Douglas and H. H. Rachford. On the numerical solution of the heat conduction problem in 2 and 3 space variables. Tran. Amer. Math. Soc., 82:421–439, 1956.
[15] J. Edmonds. Submodular functions, matroids, and certain polyhedra. In Combinatorial optimization Eureka, you shrink!, pages 11–26. Springer, 2003.
[16] U. Feige, V. S. Mirrokni, and J. Vondrak. Maximizing non-monotone submodular functions. SIAM J Comp, 40(4):1133–1153, 2011.
[17] M. Frank and P. Wolfe. An algorithm for quadratic programming. Naval Research Logistics Quarterly, 3: 95–110, 1956.
[18] S. Fujishige. Lexicographically optimal base of a polymatroid with respect to a weight vector. Mathematics of Operations Research, pages 186–196, 1980.
[19] S. Fujishige. Submodular Functions and Optimization. Elsevier, 2005.
[20] S. Fujishige and S. Isotani. A submodular function minimization algorithm based on the minimum-norm base. Pacific Journal of Optimization, 7:3–17, 2011.
[21] H. Groenevelt. Two algorithms for maximizing a separable concave function over a polymatroid feasible region. European Journal of Operational Research, 54(2):227–236, 1991.
[22] D.S. Hochbaum and S.-P. Hong. About strongly polynomial time algorithms for quadratic optimization over submodular constraints. Math. Prog., pages 269–309, 1995.
[23] S. Iwata and N. Zuiki. A network flow approach to cost allocation for rooted trees. Networks, 44:297–301, 2004.
[24] S. Jegelka, H. Lin, and J. Bilmes. On fast approximate submodular minimization. In NIPS, 2011.
[25] S. Jegelka, F. Bach, and S. Sra. Reflection methods for user-friendly submodular optimization (extended version). arXiv, 2013.
[26] R. Jenatton, J. Mairal, G. Obozinski, and F. Bach. Proximal methods for hierarchical sparse coding. Journal of Machine Learning Research, pages 2297–2334, 2011. y
[27] P. Kohli, L. Ladick´ , and P. Torr. Robust higher order potentials for enforcing label consistency. Int. Journal of Comp. Vision, 82, 2009.
[28] V. Kolmogorov. Minimizing a sum of submodular functions. Disc. Appl. Math., 160(15), 2012.
[29] N. Komodakis, N. Paragios, and G. Tziritas. MRF energy minimization and beyond via dual decomposition. IEEE TPAMI, 33(3):531–552, 2011.
[30] A. Krause and C. Guestrin. Submodularity and its applications in optimized information gathering. ACM Transactions on Intelligent Systems and Technology, 2(4), 2011.
[31] H. Lin and J. Bilmes. A class of submodular functions for document summarization. In NAACL/HLT, 2011.
[32] L. Lov´ sz. Submodular functions and convexity. Mathematical programming: the state of the art, Bonn, a pages 235–257, 1982.
[33] S. T. McCormick. Submodular function minimization. Discrete Optimization, 12:321–391, 2005.
[34] O. Meshi, T. Jaakkola, and A. Globerson. Convergence rate analysis of MAP coordinate minimization algorithms. In NIPS, 2012.
[35] G.L. Nemhauser, L.A. Wolsey, and M.L. Fisher. An analysis of approximations for maximizing submodular set functions–I. Math. Prog., 14(1):265–294, 1978.
[36] Y. Nesterov. Smooth minimization of non-smooth functions. Math. Prog., 103(1):127–152, 2005.
[37] J. B. Orlin. A faster strongly polynomial time algorithm for submodular function minimization. Math. Prog., 118(2):237–251, 2009.
[38] B. Savchynskyy, S. Schmidt, J. Kappes, and C. Schn¨ rr. A study of Nesterov’s scheme for Lagrangian o decomposition and MAP labeling. In CVPR, 2011.
[39] A. Shekhovtsov and V. Hlav´ c. A distributed mincut/maxflow algorithm combining path augmentation and a push-relabel. In Energy Minimization Methods in Computer Vision and Pattern Recognition, 2011.
[40] P. Stobbe. Convex Analysis for Minimizing and Learning Submodular Set functions. PhD thesis, California Institute of Technology, 2013.
[41] P. Stobbe and A. Krause. Efficient minimization of decomposable submodular functions. In NIPS, 2010.
[42] R. Tarjan, J. Ward, B. Zhang, Y. Zhou, and J. Mao. Balancing applied to maximum network flow problems. In European Symp. on Algorithms (ESA), pages 612–623, 2006. 9