nips nips2003 nips2003-171 nips2003-171-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Thore Graepel, Ralf Herbrich, Andriy Kharechko, John S. Shawe-taylor
Abstract: We present a modified version of the perceptron learning algorithm (PLA) which solves semidefinite programs (SDPs) in polynomial time. The algorithm is based on the following three observations: (i) Semidefinite programs are linear programs with infinitely many (linear) constraints; (ii) every linear program can be solved by a sequence of constraint satisfaction problems with linear constraints; (iii) in general, the perceptron learning algorithm solves a constraint satisfaction problem with linear constraints in finitely many updates. Combining the PLA with a probabilistic rescaling algorithm (which, on average, increases the size of the feasable region) results in a probabilistic algorithm for solving SDPs that runs in polynomial time. We present preliminary results which demonstrate that the algorithm works, but is not competitive with state-of-the-art interior point methods. 1
[1] B. Borchers. SDPLIB 1.2, A library of semidefinite programming test problems. Optimization Methods and Software, 11(1):683–690, 1999.
[2] R. O. Duda, P. E. Hart, and D. G. Stork. Pattern Classification and Scene Analysis. John Wiley and Sons, New York, 2001. Second edition.
[3] J. Dunagan and S. Vempala. A polynomial-time rescaling algorithm for solving linear programs. Technical Report MSR-TR-02-92, Microsoft Research, 2002.
[4] F. Glineur. Pattern separation via ellipsoids and conic programming. M´moire e de D.E.A., Facult´ Polytechnique de Mons, Mons, Belgium, Sept. 1998. e
[5] T. Graepel. Kernel matrix completion by semidefinite programming. In J. R. Dorronsoro, editor, Proceedings of the International Conference on Neural Networks, ICANN2002, Lecture Notes in Computer Science, pages 694–699. Springer, 2002.
[6] T. Graepel and R. Herbrich. Invariant pattern recognition by Semidefinite Programming Machines. In S. Thrun, L. Saul, and B. Sch¨lkopf, editors, Advances o in Neural Information Processing Systems 16. MIT Press, 2004.
[7] M. Gr¨tschel, L. Lov´sz, and A. Schrijver. Geometric Algorithms and Combinao a torial Optimization, volume 2 of Algorithms and Combinatorics. Springer-Verlag, 1988.
[8] C. Helmberg. Semidefinite programming for combinatorial optimization. Technical Report ZR-00-34, Konrad-Zuse-Zentrum f¨r Informationstechnik Berlin, u Oct. 2000.
[9] Y. Li, H. Zaragoza, R. Herbrich, J. Shawe-Taylor, and J. Kandola. The perceptron algorithm with uneven margins. In Proceedings of the International Conference of Machine Learning (ICML’2002), pages 379–386, 2002.
[10] A. B. J. Novikoff. On convergence proofs on perceptrons. In Proceedings of the Symposium on the Mathematical Theory of Automata, volume 12, pages 615–622. Polytechnic Institute of Brooklyn, 1962.
[11] G. Pataki. Cone-LP’s and semi-definite programs: facial structure, basic solutions, and the symplex method. Technical Report GSIA, Carnegie Mellon University, 1995.
[12] F. Rosenblatt. The perceptron: A probabilistic model for information storage and organization in the brain. Psychological Review, 65(6):386–408, 1958.
[13] K. C. Toh, M. Todd, and R. T¨t¨nc¨. SDPT3 – a MATLAB software package uu u for semidefinite programming. Technical Report TR1177, Cornell University, 1996.
[14] L. Vandenberghe and S. Boyd. Semidefinite programming. SIAM Review, 38(1):49–95, 1996.