nips nips2010 nips2010-219 nips2010-219-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Ariel Kleiner, Ali Rahimi, Michael I. Jordan
Abstract: We present a novel algorithm, Random Conic Pursuit, that solves semidefinite programs (SDPs) via repeated optimization over randomly selected two-dimensional subcones of the PSD cone. This scheme is simple, easily implemented, applicable to very general SDPs, scalable, and theoretically interesting. Its advantages are realized at the expense of an ability to readily compute highly exact solutions, though useful approximate solutions are easily obtained. This property renders Random Conic Pursuit of particular interest for machine learning applications, in which the relevant SDPs are generally based upon random data and so exact minima are often not a priority. Indeed, we present empirical results to this effect for various SDPs encountered in machine learning; these experiments demonstrate the potential practical usefulness of Random Conic Pursuit. We also provide a preliminary analysis that yields insight into the theoretical properties and convergence of the algorithm. 1
[1] U. Alon, N. Barkai, D. A. Notterman, K. Gish, S. Ybarra, D. Mack, and A. J. Levine. Broad patterns of gene expression revealed by clustering analysis of tumor and normal colon tissues probed by oligonucleotide arrays. Proc. Natl. Acad. Sci. USA, 96:6745–6750, June 1999.
[2] S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
[3] S. Burer and R.D.C Monteiro. Local minima and convergence in low-rank semidefinite programming. Mathematical Programming, 103(3):427–444, 2005.
[4] S. Burer, R.D.C. Monteiro, and Y. Zhang. A computational study of a gradient-based log-barrier algorithm for a class of large-scale sdps. Mathematical Programming, 95(2):359–379, 2003.
[5] G. Calafiore and M.C. Campi. Uncertain convex programs: randomized solutions and confidence levels. Mathematical Programming, 102(1):25–46, 2005.
[6] K. Clarkson. Coresets, sparse greedy approximation, and the frank-wolfe algorithm. In Symposium on Discrete Algorithms (SODA), 2008.
[7] A. d’Aspremont. Subsampling algorithms for semidefinite programming. Technical Report 0803.1990, ArXiv, 2009.
[8] A. d’Aspremont, L. El Ghaoui, M. I. Jordan, and G. R. G. Lanckriet. A direct formulation for sparse pca using semidefinite programming. SIAM Review, 49(3):434–448, 2007.
[9] M. Grant and S. Boyd. CVX: Matlab software for disciplined convex programming, version 1.21. http://cvxr.com/cvx, May 2010.
[10] E. Hazan. Sparse approximate solutions to semidefinite programs. In Latin American conference on Theoretical informatics, pages 306–316, 2008.
[11] C. Helmberg. A cutting plane algorithm for large scale semidefinite relaxations. In Martin Gr¨ tschel, o editor, The sharpest cut, chapter 15. MPS/SIAM series on optimization, 2001.
[12] C. Helmberg and F. Rendl. A spectral bundle method for semidefinite programming. SIAM Journal on Optimization archive, 10(3):673–696, 1999.
[13] L. K. Jones. A simple lemma on greedy approximation in Hilbert space and convergence rates for projection pursuit regression and neural network training. The Annals of Statistics, 20(1):608–613, March 1992.
[14] G. R. G. Lanckriet, N. Cristianini, P. Bartlett, L. El Ghaoui, and M. I. Jordan. Learning the kernel matrix with semidefinite programming. Journal of Machine Learning Research (JMLR), 5:27–72, December 2004.
[15] L. Lov´ sz and S. Vempala. Fast algorithms for logconcave functions: Sampling, rounding, integration a and optimization. In Foundations of Computer Science (FOCS), 2006.
[16] A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on Optimization, 19(4):1574–1609, 2009.
[17] Y Nesterov. Smooth minimization of non-smooth functions. Mathematical Programming, 103(1):127– 152, May 2005.
[18] Y. Nesterov. Smoothing technique and its applications in semidefinite optimization. Mathematical Programming, 110(2):245–259, July 2007.
[19] G. Obozinski, B. Taskar, and M. I. Jordan. Joint covariate selection and joint subspace selection for multiple classification problems. Statistics and Computing, pages 1573–1375, 2009.
[20] J. Platt. Using sparseness and analytic QP to speed training of Support Vector Machines. In Advances in Neural Information Processing Systems (NIPS), 1999.
[21] J.F. Sturm. Using sedumi 1.02, a matlab toolbox for optimization over symmetric cones. Optimization Methods and Software, Special issue on Interior Point Methods, 11-12:625–653, 1999.
[22] W. Sun and Y. Yuan. Optimization Theory And Methods: Nonlinear Programming. Springer Optimization And Its Applications, 2006.
[23] K. Q. Weinberger, F. Sha, Q. Zhu, and L. K. Saul. Graph laplacian regularization for large-scale semidefinite programming. In Advances in Neural Information Processing Systems (NIPS), 2006.
[24] E. Xing, A. Ng, M. Jordan, and S. Russell. Distance metric learning, with application to clustering with side-information. In Advances in Neural Information Processing Systems (NIPS), 2003. 9