We have read and appreciate all comments, due to page limit we will only address a subset of questions/concerns. We do not expect this will significantly change our performance. R1: Can you evaluate the coarseness of the approximation? By sampling 1000 random singular values with an L2 norm < 50 we get the following results. R4: Approximation = loss not necessarily convex: This is true.

We present a hybrid algorithm for optimizing a convex, smooth function over the cone of positive semidefinite matrices. Our algorithm converges to the global optimal solution and can be used to solve general large-scale semidefinite programs and hence can be readily applied to a variety of machine learning problems. We show experimental results on three machine learning problems (matrix completion, metric learning, and sparse PCA) . Our approach outperforms state-of-the-art algorithms.