nips nips2011 nips2011-39 nips2011-39-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Dan Garber, Elad Hazan
Abstract: In recent years semidefinite optimization has become a tool of major importance in various optimization and machine learning problems. In many of these problems the amount of data in practice is so large that there is a constant need for faster algorithms. In this work we present the first sublinear time approximation algorithm for semidefinite programs which we believe may be useful for such problems in which the size of data may cause even linear time algorithms to have prohibitive running times in practice. We present the algorithm and its analysis alongside with some theoretical lower bounds and an improved algorithm for the special problem of supervised learning of a distance metric. 1
[1] Michel. X. Goemans and David P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. In Journal of the ACM, volume 42, pages 1115–1145, 1995.
[2] Sanjeev Arora, Satish Rao, and Umesh Vazirani. Expander flows, geometric embeddings and graph partitioning. In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, STOC ’04, pages 222–231, 2004.
[3] Amit Agarwal, Moses Charikar, Konstantin Makarychev, and Yury Makarychev. O(sqrt(log n)) approximation algorithms for min uncut, min 2cnf deletion, and directed cut problems. In Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, STOC ’05, pages 573–581, 2005.
[4] Sanjeev Arora, James R. Lee, and Assaf Naor. Euclidean distortion and the sparsest cut. In Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, STOC ’05, pages 553–562, 2005.
[5] Eric P. Xing, Andrew Y. Ng, Michael I. Jordan, and Stuart Russell. Distance metric learning, with application to clustering with side-information. In Advances in Neural Information Processing Systems 15, pages 505–512, 2002. 8
[6] Alexandre d’Aspremont, Laurent El Ghaoui, Michael I. Jordan, and Gert R. G. Lanckriet. A direct formulation of sparse PCA using semidefinite programming. In SIAM Review, volume 49, pages 41–48, 2004.
[7] Gert R. G. Lanckriet, Nello Cristianini, Laurent El Ghaoui, Peter Bartlett, and Michael I. Jordan. Learning the kernel matrix with semi-definite programming. In Journal of Machine Learning Research, pages 27–72, 2004.
[8] Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
[9] Philip Klein and Hsueh-I Lu. Efficient approximation algorithms for semidefinite programs arising from max cut and coloring. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, STOC ’96, pages 338–347, 1996.
[10] Sanjeev Arora, Elad Hazan, and Satyen Kale. Fast algorithms for approximate semide.nite programming using the multiplicative weights update method. In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS ’05, pages 339–348, 2005.
[11] Sanjeev Arora and Satyen Kale. A combinatorial, primal-dual approach to semidefinite programs. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, STOC ’07, pages 227–236, 2007.
[12] Elad Hazan. Sparse approximate solutions to semidefinite programs. In Proceedings of the 8th Latin American conference on Theoretical informatics, LATIN’08, pages 306–316, 2008.
[13] Garud Iyengar, David J. Phillips, and Clifford Stein. Feasible and accurate algorithms for covering semidefinite programs. In SWAT, pages 150–162, 2010.
[14] Garud Iyengar, David J. Phillips, and Clifford Stein. Approximating semidefinite packing programs. In SIAM Journal on Optimization, volume 21, pages 231–268, 2011.
[15] Kenneth L. Clarkson, Elad Hazan, and David P. Woodruff. Sublinear optimization for machine learning. In Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS ’10, pages 449–457, 2010.
[16] Elad Hazan. Approximate convex optimization by online game playing. abs/cs/0610119, 2006. CoRR,
[17] Kenneth L. Clarkson, Elad Hazan, and David P. Woodruff. Sublinear optimization for machine learning. CoRR, abs/1010.4408, 2010.
[18] Shai Shalev-shwartz, Yoram Singer, and Andrew Y. Ng. Online and batch learning of pseudometrics. In ICML, pages 743–750, 2004.
[19] James Hardy Wilkinson. The algebric eigenvalue problem. Claderon Press, Oxford, 1965.
[20] Gene H. Golub and Charles F. Van Loan. Matrix computations. John Hopkins University Press, 1989.
[21] Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In ICML, pages 928–936, 2003. 9