nips nips2013 nips2013-33 nips2013-33-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Srikrishna Sridhar, Stephen Wright, Christopher Re, Ji Liu, Victor Bittorf, Ce Zhang
Abstract: Many problems in machine learning can be solved by rounding the solution of an appropriate linear program (LP). This paper shows that we can recover solutions of comparable quality by rounding an approximate LP solution instead of the exact one. These approximate LP solutions can be computed efficiently by applying a parallel stochastic-coordinate-descent method to a quadratic-penalty formulation of the LP. We derive worst-case runtime and solution quality guarantees of this scheme using novel perturbation and convergence analysis. Our experiments demonstrate that on such combinatorial problems as vertex cover, independent set and multiway-cut, our approximate rounding scheme is up to an order of magnitude faster than Cplex (a commercial LP solver) while producing solutions of similar quality. 1
[1] Nikhil Bansal, Nitish Korula, Viswanath Nagarajan, and Aravind Srinivasan. Solving packing integer programs via randomized rounding with alterations. Theory of Computing, 8(1):533–565, 2012.
[2] Dimitri P. Bertsekas. Nonlinear Programming. Athena Scientific, 1999.
[3] Jacob Bien and Robert Tibshirani. Classification by set cover: The prototype vector machine. arXiv preprint arXiv:0908.2284, 2009.
[4] Yuri Boykov and Vladimir Kolmogorov. An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision. IEEE Transactions on Pattern Analysis and Machine Intelligence, 26:1124–1137, 2004.
[5] Gruia C˘ linescu, Howard Karloff, and Yuval Rabani. An improved approximation algorithm for multiway a cut. In Proceedings of the thirtieth annual ACM symposium on Theory of Computing, pages 48–52. ACM, 1998.
[6] Jonathan Eckstein and Paulo JS Silva. A practical relative error criterion for augmented lagrangians. Mathematical Programming, pages 1–30, 2010.
[7] Dorit S Hochbaum. Approximation algorithms for the set covering and vertex cover problems. SIAM Journal on Computing, 11(3):555–556, 1982.
[8] VK Koval and MI Schlesinger. Two-dimensional programming in image analysis problems. USSR Academy of Science, Automatics and Telemechanics, 8:149–168, 1976.
[9] Frank R Kschischang, Brendan J Frey, and H-A Loeliger. Factor graphs and the sum-product algorithm. Information Theory, IEEE Transactions on, 47(2):498–519, 2001.
[10] Taesung Lee, Zhongyuan Wang, Haixun Wang, and Seung-won Hwang. Web scale entity resolution using relational evidence. Technical report, Microsoft Research, 2011.
[11] Victor Lempitsky and Yuri Boykov. Global optimization for shape fitting. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR ’07), pages 1–8. IEEE, 2007.
[12] Ji Liu, Stephen J. Wright, Christopher R´ , and Victor Bittorf. An asynchronous parallel stochastic coore dinate descent algorithm. Technical report, University of Wisconsin-Madison, October 2013.
[13] F Manshadi, Baruch Awerbuch, Rainer Gemulla, Rohit Khandekar, Juli´ n Mestre, and Mauro Sozio. A a distributed algorithm for large-scale generalized matching. Proceedings of the VLDB Endowment, 2013.
[14] Feng Niu, Benjamin Recht, Christopher R´ , and Stephen J. Wright. Hogwild!: A lock-free approach to e parallelizing stochastic gradient descent. arXiv preprint arXiv:1106.5730, 2011.
[15] Jorge Nocedal and Stephen J Wright. Numerical Optimization. Springer, 2006.
[16] Pradeep Ravikumar, Alekh Agarwal, and Martin J Wainwright. Message-passing for graph-structured linear programs: Proximal methods and rounding schemes. The Journal of Machine Learning Research, 11:1043–1080, 2010.
[17] J. Renegar. Some perturbation theory for linear programming. Mathenatical Programming, Series A, 65:73–92, 1994.
[18] Dan Roth and Wen-tau Yih. Integer linear programming inference for conditional random fields. In Proceedings of the 22nd International Conference on Machine Learning, pages 736–743. ACM, 2005.
[19] Sujay Sanghavi, Dmitry Malioutov, and Alan S Willsky. Linear programming analysis of loopy belief propagation for weighted matching. In Advances in Neural Information Processing Systems, pages 1273– 1280, 2007.
[20] Aravind Srinivasan. Improved approximation guarantees for packing and covering integer programs. SIAM Journal on Computing, 29(2):648–670, 1999.
[21] Jurgen Van Gael and Xiaojin Zhu. Correlation clustering for crosslingual link detection. In IJCAI, pages 1744–1749, 2007.
[22] Vijay V Vazirani. Approximation Algorithms. Springer, 2004.
[23] Stephen J. Wright. Implementing proximal point methods for linear programming. Optimization Theory and Applications, 65(3):531–554, 1990. Journal of
[24] Zheng Wu, Ashwin Thangali, Stan Sclaroff, and Margrit Betke. Coupling detection and data association for multiple object tracking. In Computer Vision and Pattern Recognition (CVPR), 2012 IEEE Conference on, pages 1948–1955. IEEE, 2012.
[25] Ke Xu and Wei Li. Many hard examples in exact phase transitions. Theoretical Computer Science, 355(3):291–302, 2006.
[26] Ce Zhang and Christopher R´ . Towards high-throughput gibbs sampling at scale: A study across storage e managers. In SIGMOD Proceedings, 2013. 9